ZK Whiteboard Sessions - S3M1: How to Build Hash Functions, with Jean-Philippe (JP) Aumasson

Transcript

[Music] Welcome to this module of the ZK  Whiteboard Sessions. I'm Nico, I'll be your host today,  and our guest is JP. Hi, JP. Hi, thanks for having me. It's great  to have you because we're going to be talking about hash functions, and you  are one of the designers of BLAKE, right? Yes, BLAKE, the BLAKE hash function  and the subsequent versions, BLAKE 2 and BLAKE 3. Nice. So  what's the agenda for today? So we're going to talk about hash functions,  cryptographic hash functions. So we're going to start with what is a hash function,  what does it do, why, and then what does it mean for a hash function to be secure?  There's not one single notion of security.

And then we're going to see how  to construct a hash function, how does it look like under the hood,  from the mode to the algorithm. And I'll also give you a few examples of hash  functions. And then we'll try to explore what does it mean for a hash function  to be a good or useful hash function? What does it mean to be  efficient? For what, for whom? And then we'll explore a bit more of security. How can you attack a hash function? I'm  not going to give you a recipe about how to break any hash function, but the  general strategy and particularly differential cryptanalysis. And finally,  we'll move on to the ZK part of this podcast.

We're going to talk about  ZK-friendly hash functions, also called algebraic hash functions like  Poseidon, and maybe conclude with Fiat-Shamir, and where you use hash functions.  Sounds great. So let's start. So hash functions. So how do we  spell hash functions? H-A-S-H. And start. And function. Function. Okay. So first of all, again, it's cryptographic  hash functions. If you look on the internet, there's also hash functions as used  for databases, for other purposes, which do not have the security  features of a hash function.

So hash functions, we are recording  this in Lausanne, Switzerland. They're also called the Swiss army knife  of cryptography because they're really ubiquitous. They're everywhere in your pocket. You have a hash function, you have hash  functions all over the place. For example, you have hash functions in signatures,  signature schemes, because when you sign a blockchain transaction with ECDSA or  8025, you don't directly process the message, you process a hash of the message, because it  gives you something of fixed size, and that's what your signature scheme will process.  So by extension, also in certificate, chain certificate management, where you essentially  have a kind of blockchain in a certification.

Hash functions, they are also used in, for  example, RNGs, random number generators or random bit generators. For example, in the  Linux kernel, the hash function is used, specifically BLAKE2, for processing the  entropy pool. Also used in KDF constructions. So KDF stands for Key Derivation  Functions, an object that derives keys from source material. For example, HKDF.  So guess what the hash stands for.

And also PRF, so Pseudo Random  Functions, which is just a fancy way to say hash function, where you have  a key, a secret. So to compute the result, you need to know that key. If you don't  know that key, you can't compute the result. And PRFs also give you a secure MAC message  authentication code. So if you have a secure PRF, you can use it as a MAC, but not the other  way, not always. And also in ZKS-NOX, you have all the cryptography that exists, except maybe  cyphers, but all this commitment and whatnot.

ZK-Erasing, Fiat-Shamiring, Merkle-Trees.  So even if there's something missing here, we don't mention cyphers, encryption,  decryption. It's only about integrity, data integrity, and not confidentiality,  or very rarely or in weird cases. Okay, so that's what hash functions are about.  But if you've never seen hash functions, you might be like, okay, what does a hash function do? So let's show a hash function  from a very abstract perspective.

So when I give crypto classes, I  first tell people, what is an RMG, a deterministic Random Number Generator, where  you start from a seed or a key of fixed size, and you generate an output of arbitrary  size. And they usually say that a hash function is kind of the opposite.  So I'm going to draw a lozenge. Okay, so that is my artistic view of a hash  function. It's a transformation. It maps an input. I'm going to write it m, like message.  And the output, I'm going to write it h, small h, like hash, also called,  well, hash value, fingerprint, checksum, digest as well. But the industry  standard is h, which is very confusing.

So you have h of m equals h. That's the simplest  thing you can imagine. One input, one output. So how do they differ? So m, a mathematician  would write that it belongs to the set of all bit strings of arbitrary size, even the  empty string. I guess there's a one there. I'm missing a one, yes. Nice. And this output value belongs to the set of bits of a  fixed size that I'm going to write n. So we go from any message, even the  empty message, you can hash one byte, one megabyte, one gigabyte, however many  bytes you want. But you're always going

to get something of the same size. Always n bits. Always n bits. I'm going to ask, what is n? Yes. So it can be whatever you want.  But if you want it to be secure, typical choices for n are 256 bits.  I'm going to explain why later. You can make it longer, maybe 512 or even  more, if for some reason you need the hash to be longer. For example, well, I said before  that I should not do, you choose an encryption, but I was lying. So in RSA or  AEP, it's a mode to use RSA.

In this construction, you use a hash  function called the mask generation function, something like that, which is instantiated  with a hash function. And in that case, you need the hash to be a bit longer than that, maybe 1000 bits or something. So that's  one example where you need a long hash. Anyway, so it's tempting to  think, oh, the longer it is, the more secure it is, because the number  is bigger. It makes me feel better. Yeah, it also feels like it's easier to go from something big to something  bigger, you know, like... Yeah, you compress data. So in  terms of information theory, in terms of thermodynamics,  you lose information. Yeah.

So hash functions also use a one-way  function. It's also called a one-way function, because if you lose information,  you go from something gigantic, you can't go back. And so there's  something called the pigeonhole principle. I don't know how to draw a pigeon, so I'm  not going to try to. But the idea is if you have like, I don't know, four boxes  and five pigeons. So those are pigeons. Right. See, that's the wing, the head. Yeah, yeah.

And you want to squeeze those stupid pigeons  in those four boxes. So however you do it, you're always going to have at least  one box with two or more pigeons. So if you try to do it like this,  like, okay, and to put it there. So if your output space is smaller  than your input space, inevitably, you're going to have what cryptographers  call... Collisions. You're following. So a collision is a pair of messages, M1 and M2, which satisfy two conditions. So the first  one is very complex. It's called difference.

They're not the same. And the second one is also pretty straightforward.  They have the same hash value. So spoiler, that will be something that  you want to avoid. But what does it mean to avoid? It should be harder to find  those messages, but inevitably, they exist. And you have plenty of them because this is  much bigger than that. So we live with that. But from the perspective of the attacker and  from the perspective of their time, budget, computer size, universe, physical limitations,  B not being equal to NP, it should be hard.

Which brings us to the security  definitions of a hash function. What does that mean to be secure? M  is big, H is small, M is of any size. I'm going to keep this. I'm going to write this out. So this is maybe the most  important part of the presentation. Because when you hear about what  makes a hash function secure, oh, collision, preimage, second preimage.  What does that mean? So preimage is the problem where you are given an output  H, a real output H with a real value.

And you're given a challenge to  find some M such that H of M is equal to H. Then you can ask, okay,  how is H chosen? Is it randomly? What is the distribution? But from my perspective, this kind of misses the water compared to  the fundamental notion of security of your hash function. These are just consequences of  the single definition, which is the following. So you want that thing, that transformation,  which we see as a black box, except that it's white. And it should behave. So behave means  what you observe as an observer, as a user.

It should behave in the same way than a randomly  chosen function. So I said randomly chosen, not random, because this thing is  deterministic. It's not probabilistic. You give it the M twice, you get the same  H. But if you chose it as random among all the possible functions that map an input  to this kind of output, the function will have no specific pattern. If you flip one bit  here, this thing will be completely different.

It will be like if you chose a new  value randomly. So a consequence of that, if you don't have any pattern, any  structure, there's no shortcut, no backdoor, nothing whatsoever. One consequence is that  this problem, the primage problem, is hard. Because H is some function, I don't know what it  is. You have not a way to solve that. So finding M from H, then by repeatedly trying like an  idiot again and again different messages.

So writing out the whole function essentially,  like the table of the whole function, right? Yeah, so you don't need to store it in memory  because you can fire and forget. But you try M, you try another one, until you get lucky.  Now we're going to do advanced mathematics. What is the probability? What is the expected  number of attempts until you find the right one? So you have 2 to the N possible values  of H, because it's a string of N bits. So if N is large, this is very large, exponential.  So you try, you try, you try, you try. And on average, you're going to hit the lucky  value after maybe half the possible values.

So why is that the case? It's some quite basic  probabilities. Okay, you have one chance over two. So the expected value in that case will be 2 to  the N over 2, which you can just write at 2 to the N minus 1. And if N equals 256, and if we do a  subtraction, it gives you 255, which is huge. Yes. And even if N were only 128, it would be 2 to  the 127. Still gigantic. Which is still gigantic.

And if the effort is that amount of  computation, whatever the computation is, you're safe. Yeah, it's never going to  happen. In comparison, I think the number of operations to mine one Bitcoin block  could be close to 2 to the 80 hashes. Yeah, that's what I remember. And if you count  the bit operations of all the SHA-256 you do, maybe you get closer to 2 to the  90. It's exponential, so it grows. Yeah, for some reason, a huge factor.

So here you need 2 to the N attempts, so you're  going to take quite some time. Now for collisions, it's different. Collision, people  think, oh yeah, birthday paradox. But the birthday paradox, I'm not a mathematician,  so I like things explained in a very simpler way. For my brain to process it. So here,  spoiler, the answer will be 2 to the N over 2.

Okay. Which is equal to the square  root of 2 to the N. And why? Why is it that smaller? Why is it quadratically smaller than that? Because if N  is 256, then you end up with 128. So instead of this. So the reason is  the following. Here you're not looking for one message, you're looking for two messages. So you're looking for a pair of  messages. So let's say you try going to introduce the symbol N. N  is the number of messages you try.

So you have M1, M2, blah, blah, blah, until M to  the N. So if you just have those messages, well, you have N messages, but what you're looking for  is a pair. So how many pairs do you have here? That's going to be capital N squared, right? Yeah, the order of capital N squared. So  technically it's N times N minus 1, or 2, but it's approximately N squared.  And now what we want, what we want, I'm going to write here, is we want to have  N squared approximately equal to 2 to the N.

Mm-hmm. So if you flip the quadratic, it means that N must be square root of 2 to the N. Okay.  So, yeah, prim edge, collisions. But you're saying these two  are consequences of the fact... They are consequences of the fact  that the function behaves like a random one. And... A randomly chosen function. Like a randomly chosen, yeah. You fell in the trap that I did not create  intentionally. And another consequence of that is the following, and we'll get back  to this later. Any transformation...

So let's say, instead of this being infinite,  we say just a really huge value, whatever N, which is much bigger than N. And  here we still have N, whatever. So whatever this function is, there's  always a way to describe it as equations. So here, let's say that each edge, h1, h2, those  are the bits of this guy of h. So you have this up to h, hN, right? So you can write h1 as  a function of the bits of this guy, f1 of m.

And since you have all those bits, it's going  to look like a combination of additions and multiplication, what ZK people also call  a polynomial. So it might be m1 times m2 plus n1 times m2 times m3 plus blah, blah, blah,  blah. And on average, for a random function, if you write this equation down, each of the possible  terms will appear with a probability 1 over 2. So you see, if we have N bits, you have m1, m2,  m3, m4, up to mN. So you have so many combinations of those bits. And the equations will be gigantic  because you have an exponential number of...

I mean, can we see this as having  capital N variables in this polynomial? Yeah, exactly. So that's huge. So here I  did it with bits because it's simplest, but you can consider it with respect to  whatever is your favourite finite field, whatever your favourite encoding. But in any case, the equation should be huge, hard to find. And there's two dimensions here  to consider. The first one is the degree. The degree of the polynomial. The  degree is the maximum number of terms in a monomial and the  density of the equation.

So how many monomials? Exactly, how many terms. And if the density is  low, which means the equation will be sparse, it's easier to attack. And also if all those  equations are kind of correlated in some way, it's not what you expect from  a randomly chosen function. Right. That's something you might be able to  exploit. But if those questions are really random looking, a consequence would be that pre-imagined  collisions would be super hard to find. Okay. Okay, let's move on to how that  box... Yeah, how do we make these? Yeah. We have this magical object. Yeah,  it's not that magic, it's pretty boring.

Okay, super, I'm gonna get rid of it.  Okay, people got what's a hash function. So we want to process a message  of undefined arbitrary size. It can be one bit, it can be zero bit, it can be a gazillion bits. How do  you do that? Divide and conquer. So you break your message down into  different blocks. So M will be the concatenation of blocks. So M1, M2,  until whatever is your last block. And each block will be of  the same size. So concretely, those can be of, for example, 1024  bits. Or more or less, it depends.

So we start with something  that has an undefined length? Yeah. Arbitrary length. And it could be any size.  Yeah. So here you might have... Sorry, just to make sure we have... So  these chunks that are fixed length. Yeah. But we might have like some  variable number of them. Exactly, so there can be... And  you might also wonder, yeah, but what if M is not... If the size of  M is not a multiple of the chunk size? There's a little trick. A little padding trick  to add filler bits to the last chunk. Okay. So there's different ways to do it.  But typically, you might add 00s and maybe an encoding of the size of the  message. Which can be the bit size here.

There's a few things to get  right, which is super important. But it's pretty boring. So  I'm not going to detail that. Okay, so now we're going to process the chunks one by one. So you start from the  beginning. You have the first box. You see now we're doing a square, not an orange. You'll see why. And then what's entering  to this box would be the first message. Then you get an output, another  box, another message, chunk, yada yada. And you repeat it again and again.  And at the end, you get the final hash value.

That's oversimplified because you're not seeing how this box is working. What  is the box? What is the box? It's a secret. Okay. I can't tell a secret. And you start from the value that we might call  H0. So this value that is modified iteratively by the message blocks is sometimes called  the chaining value. Because it's a chain. You see, it's like a blockchain. It's a  chain of blocks. Blockchain before Bitcoin. Also called the state because it's  stateful, obviously. If you have a different message block here, that value will  be different. Unless you're really not lucky.

So what you want is that this guy depends on  each single bit from each of those blocks. Yeah, that's how all hash functions work. But it  doesn't tell you how the transform is done. So there's two ways to do  it. So I'm going to write scientific terms here. The first  one is actually called the Sponge. And it is based on a permutation. A permutation.

Okay. I'm guessing you're going to  explain what this means in a second. Yep. Okay. Permutation. And the second one, it's  sometimes called the Merkle-Damgård construction. Because those two guys, they had  the same idea around the same time in the 80s. Is it the same Merkle as the trees? Exactly. Ralph Merkle. Yeah. He was really into hashing. And those are based  on a keyed permutation. Oh, sounds more complex. Yeah. Because we have a key. We have a secret.

But I told you there's no secret in a hash  function. What is also a keyed permutation? Are you asking me? Yes. Oh, I'm not sure I know. Not sure. So it's also a block cypher. So you see, you can create cyphers from hashes and you can  create hashes from cyphers. It's so intertwined. I'm going to start with the first one, the  sponge. So this came, I think, in the early, mid 2000s, 2008, something like that.  And this was formalised and analysed by Johan Dement, one of the authors of AES.

And they did a really series of papers to build  a very theoretical framework, a very convincing resource why it's not completely done. So how  does it work? First, what is a permutation? It's typically abbreviated P. You know, we  are creatives in crypto. P like permutation. So permutation is something that takes, let's say, a state S, and it gives you another  state S' of the same size in such a way that you can compute the inverse. Oh, S' and get  back to S. So you don't lose information.

It is a bijection. You can go  whichever way you want. In practice, you only need to implement  the forward permutation. So does that mean a permutation, are we  flipping around the order of bits? Or are we... So it's not a permutation. Yeah, people often get  confused by this. Like, oh, we permute the bits. No, what is permuted is the actual  state as a value. It's not about the encoding or the bits. So you  see this like a gigantic number. And for example, one number is mapped to  another one, but there is no collision. So this state S, it's a series of bits.  In Keccak, SHA-3 is typically 1600.

And we see it as two parts. I'm going to  explain why later. So we draw two wires into P. But P already sees it as one single input,  which is the concatenation of the two. Why? Not just to make it more complicated,  but because we're going to do that. We're going to take our M1, our first  message block, and inject it, add it, XOR it to this part of the state, which will  then get permuted. Okay, so this symbol here means XOR? So here's the XOR, because most of  the time it's an XOR when you deal with bits.

You just want it to be invertible. So XOR is the easiest for most computers.  So that's how Keccak works. But you may work with any other operation  that satisfies the requirements. So when you talk about Poseidon, it won't  be XOR. And it's very, very simple. And then you XOR another message block,  a different one, and you permute again. And when you want an output value, you  extract that value and it becomes your hash.

So extract just means reading this wire? Exactly, just reading this. And if you want more, you can have an H2, whatever.  It looks super simple, right? It's actually quite simple. There are some tiny details to get right. It's also been  called this approach, so a sponge. What a sponge is doing, if you have a sponge  in your bathroom, it absorbs water and you can squeeze the sponge and water leaks out. So that  construction was called the absorb and squeeze. So absorbing on this side  and squeezing on the other.

You absorb the water here and you squeeze  different water out there. And yeah, that's pretty simple. And based on this  idea, you can also generate other things like pseudorandom functions, where you first  introduce, inject a key and then your message. You can create a deterministic random  number generator. You can create output, hash output of variable  size. So it's very flexible. And it's quite simple because you  only have to design a permutation that takes one input and gives you  one output of the same size. So, Keccak is a sponge function. It was a hash  function submitted to the SHA-3 competition.

And it was selected as the foundation for  SHA-3. So now if you work with Ethereum, if you implemented an EVM, you know that Keccak is not exactly the same. It's 99%  the same, except for the padding. So the padding is the way you fill  the last bits to get a chunk. So yeah, those are sponges. It's pretty cool. And Keccak, SHA-3 and Poseidon,  of course, is a sponge.

I do have a quick question and  maybe we'll get to this later. How do we pick our permutation? And how do  we know that the overall thing is secure? Because if you tell me this is going  to behave like a random function or a randomly chosen function, I'm not sure  I'm going to believe you at this point. Yes, so yeah, that's a good question. I'm going  to answer first to the second one. So when you worry about the security of a hash function,  you worry about the security of two things. The first one is the mode. So the mode is  this construction. And the mode will assume that this thing is perfect for some  very precise definition of perfect. So we don't worry about P. We assume it's perfect, it's a perfect permutation. So you're going to  prove that this mode is secure, where secure

means that there won't be any way to compute  preimages or collisions faster than ideally. And this security notion that applies to the  mode is called indifferentiability from a random oracle. So random oracle is really an idealised  view of a hash function. Idealised even more than picking a random function, but idealised in  the sense that anytime you give an input, you have some guy in the background picking a truly  random, random as in quantum physics, output.

So what this notion of indifferentiability  gets you is the guarantee that if P is secure, is properly designed, then the mode will be  safe against collision attack, precision attack, and whatever other attacks you can imagine.  Any attack in terms of correlations between input and output, you can be, for example,  interested in attacks where you want this output to have a specific correlation with input  or to have some number of leading zeros here and number of leading ones there. Anything that is  statistically unlikely and that you want to find.

So that's indifferentiability. I'm going to write it because it's quite a  mouthful. Indifferentiability. Sometimes we also talk about  indistinguishability. Is that different? Yes, that's different. So, cool. Yeah,  it's not confusing at all, right? So indistinguishability, so small interlude, it's a notion that applies to keyed  hash function where you have a key. I'm going to write it here. So instead of just  hashing m, you hash a key and the message.

So the key is secret. And  let's say, as an attacker, you can query this box where you don't know  the key. You send an m and you get the output. You can't compute it or see yourself because  you don't know the key. So you know the key, you're going to give me the output and I do it a  gazillion times. But the trick is the following. When you give me the output, you flip a  coin and either you give me the output of the function or you give me a random  value. And you remember this random value because if I send the same message,  you're going to send the same value. Now, my goal is to distinguish the cases where  you give me the correctly computed output from the cases where you flip a coin  and give me something completely random.

So that's really important because most of the  security notions of symmetric cryptography is about emulating randomness. Doing  something that looks like garbage that is semantically secure in the sense  that there is nothing that really makes it different from an absolutely random  thing. So this is indistinguishability. But it's just for keyed hash functions. Yes. And I guess it's not  necessary for our topic today. Hold on.

Sorry. I need to focus. Yeah, yeah.  The spelling here is crazy. Indistinguishability. Sorry for  my writing. No, no, don't worry. Yeah. Sorry for the long  words. Indistinguishability. And what else we have? Yeah, and there's other notions. So we  mentioned random oracle, ideal cypher. Yeah. So we try to idealise things and  try to make something that outwardly from an observer's perspective  is not very different. Yeah. Sorry, I took you on a tangent  with indistinguishability. But indifferentiability, we said, I can't  make the difference between this thing, this construction, and a random oracle, you said.

Yeah. So if you have a function  that does that with a perfect p, and you get only the outputs, you can't  say, oh, I'm sure this guy comes from this construction and not from a random oracle  because of some structural properties. No. It will behave completely random. And intuitively, well, it's not very intuitive, but if you  get it, it starts to make sense. Yeah. But otherwise, yes, kind of confusing.

Okay. And these proofs of indistinguishability,  do they depend on some assumption of hardness? So the assumption is just optimism. Okay. Just saying that, okay, my  job is to secure the permutation. Then your guy's job is to create a secure p.  Yeah. So this is a different team, so to speak. Okay. That will create a transformation  which behaves well, which ultimately means being described as equations that are  very long, very high degree, very dense, and doing so in a simple way. So it's  trivial to create a good permutation.

You just take a lot of random equations.  You make computation that takes two hours. Yeah. But we want it to be fast and simple and  programmable. As in easy to compute. Yeah. And it's not enough to do something that just looks like complete garbage. It's  so confusing. It must be random. No, you need to have a rationale  behind. You need to be able to convince someone that it is resistant to  this type of attack and okay. So yeah, that was kind of an answer to your first  question, but we'll get back to this later.

Sounds good. Now let's move to the  number two, the other construction, which is the legacy from the  80s. Well, it's pretty good. And there's, first of all, there's none of  those two which is intrinsically superior to the others. It's different trade-offs. To  be fully honest, permutation-based is easier. But as you mentioned, the functional design,  BLAKE, BLAKE 3, they're not permutation-based because reasons. But yeah, ultimately it's  very similar. Good to describe how this works. Sounds good. So the other approach is  less flexible. In some ways, it's simpler.

In some other ways, it's not. So you  also start from an initial value, sometimes called the IV. And here  you're going to do something weird. Sorry, I'll just quickly interrupt you. I  guess the intern, this value is necessary in case we're hashing the empty message,  right? Like if we're hashing an empty message and we still want some output,  we need to start from something, right? Exactly. So yeah, if you hash the empty message, it's funny because when we submitted  hash functions to the NIST competition, one of the criteria was to support empty messages.  I'm like, who the hell is hashing empty messages?

Okay, you never know. So it's empty, but it's  not completely empty because the first block, M1, is filled with padding. So it will say,  hey, I have a message, but its size is zero. So you do that. And this thing here,  you'll do this little trick. An XOR. And here you'll do the same thing.  And then put another message block.

And if your message is just two blocks  long, that's what gives you the output. Okay, so what do we have here? Man, I really  suck at drawing those things. So this is an XOR. So here, this means that you take  the initial value, the input value before applying the transformation,  and you XOR it. So you memorise it, and then you XOR it, and then you forget it.  I'm gonna call this B, like block cypher. Because it's essentially a block cypher. It  behaves like a block cypher. It's kind of designed like one, except that you  may not use it to encrypt things.

Why is it a block cypher? Because  it's a keyed permutation. The small triangle here means that this  input will be the input for the key. Okay, so M1, H0, XOR H0, gives you H1. Okay,  this will be H1 here. So why do we do that? First of all, what is a keyed permutation?  If you fix this value, then for any input, you have a single output, and B is  reversible. It's a block cypher.

You can decrypt, you can go this  way, that way. So if I fix the key, then I get a regular permutation.  Exactly, you get a regular permutation. So doing this little trick here prevents you  from going backwards if you know M. So if you know H1 here, then you cannot compute  backwards, because you don't know the plain text in the first place, and you can't  guess it. So this is the approach that was used in old hash functions like MD5, MD5, like  SHA-1, and like the SHA-2 family, and also like, I can't spell my old hash function,  like 2, like 2, okay, and 3 to some extent.

So for example, in SHA-1, you had a hash value  of 160 bits, which means that this guy was of 160 bits, and the output was of the same size.  So you see the state is always the same size, because you just permute it around and exhort it.  The message chunks could be of different lengths? They're all the same size. I mean, sorry, are they also 160 bits? I don't know, they can be whatever.  They're typically larger. They're typically larger than an actual symmetric key.

There might be 512 bits.  Okay. And yeah, that's it. So if you have a block cypher that is wide enough, you can do that. But typically,  cryptographers haven't been directly using a block cypher designed to be a  block cypher as a hash function. Why? Because the block size was too short. Block size is this 160? Yes. Yeah. So like MD5, it was of size 128, which means that you could  find collisions in 2 to the 64.

Yeah, that's not great. Yeah.  So yeah, that's quite simple. Here, I draw the version where M is used as  a key, and you have this little thing here where you exhort the initial value. But there  are other combinations of exhorting things around. I think if you also want to hash  the message here, I think it also works. There are some ways that work, some  ways that don't work so well. But this happens to be the most used because  it's simple enough. And it's, yeah.

I guess same question here as last  time. I can look at this diagram, but why would this behave like  a randomly chosen function? Because cryptographers say so. Okay.  They have written plenty of papers. Now, the real answer is, again, you studied from  two levels, from the mode perspective. Yeah. And here, you assume that this be a perfect  block cypher, an ideal cypher, so to speak. And you don't worry about its internals. And  you prove that if you do it right, it's secure, it's indifferentiable from a random oracle.  But sometimes that needs a few more twists.

So you need a good padding. And you also need  those functions to be slightly different. Okay. So sometimes it's done by injecting another  value, like a counter. So here you have one, here you have two. To have this  high level of probable security, you also need this function to be different. For example, if you look at BLAKE2, we  had to do that to satisfy the highest level of theoretical security. So, yeah.  The disadvantage compared to the sponge, as you can see, is that here  you get one single input.

One single, sorry, one single output.  You don't get to choose the size of the output. You don't get to generate more output. Yeah. There's a few tricks  to do that. You can say, oh, I'm going to hash this again and again and again. Which is kind of what we did with BLAKE. But it doesn't really come out as naturally  as with the sponge. It's not as clean. But again, you don't worry about elegance.  You worry about speed, about security. Okay. Let's briefly mention the quantum attacks, so  to speak. Well, the impact of quantum computing on hash functions. So, again, as you  know, we're talking about hypothetical, actual quantum computers that could  do things that they can do right now.

But they might exist in the future.  Some future, yeah. Yeah, in five years. I mean, I always say in five years.  It's always in five years. Yeah. So, it's, again, simple, but not that simple. So,  we mentioned that for pre-image, the classical way to attack it by trying one input after the other  will take you approximately 2 to the n operations. Now, on paper, with a minus one on the expected  value, with a quantum computer, you have this search algorithm of Grover, so the Grover quantum  algorithm, which, with some kind of magic,

brings down the search in a list, the search in  a database, to a complexity that is of the order of square root of the size of the table, which  in our case means square root of 2 to the n. So, like, oh my god, it's much bigger  because we go from this to that. So, there's two things to consider here. So,  it's a big O, it's an order of magnitude. There's a constant factor, which might be  gigantic. It might be 10 billion times that.

It also involves the implementation  of the function as a quantum circuit. And if you implement, for  example, AES as a quantum circuit, the last estimates I've seen need a circuit  of depth approximately 2 to the power 70. So, you need a gigantic quantum circuit that  needs a pretty solid quantum computer, and it takes some computation time. So, you  need the coherence for quite a long time. So, it's not just about theoretical time, it's  about the hidden factors, and it's about the cost in terms of energy, time, engineering. So, it  won't be, in terms of cost efficiency, a square

root of what you would do here, because this is  easily parallelised on millions of GPUs. Anyway, it's not unlikely that, effectively, this ends  up being easier, whatever easier means than that. But if you have a hash function of 2 to the  156 bits, and the worst, worst, worst case, you're down to 128, which you're still on the safe  side. For collision, again, it's a bit tricky, because in theory, so it's 2 to the n over  2, really, approximately. With a classical.

With a classical. And quantum, there are some  algorithms, like the BHT, which tell you that it's this order  of magnitude, so n divided by 3, instead of divided by 2, which means that this  number is smaller. However, it also needs quite a large circuit and some memory. I bet the memory  might be, maybe, of the same order of magnitude. Not fully sure. But there was some debate  about whether the quantum collision finding algorithm would effectively be more  interesting than this one. Because, again, this can be parallelised in  a way that uses very little memory.

So from what I've read, I believe that this  will still be more efficient than whatever quantum. But you never know. You don't know how  quantum hardware will look like in 200 years. And worst case, can we just make  the length of our hash greater? So just make it a bit bigger. But I think  if I teleport myself 500 years from now, my guess is that 256 will still be  good. But people call me optimistic. So here the upshot is that the impact of  quantum computers is not as bad as it is for, let's say, factoring or discrete  log-based things like ECDSA, RSA,

Groth16, or whatever. Okay, so now  what is a... Let me also get rid of... We wanted to briefly talk about what is a cool  hash function. What is a good hash function? So you're designing a system. You're  an engineer. So if you're an engineer, you have to understand what you need  before selecting something in terms of functionality, in terms of speed, in terms  of security, in terms of integration time, maybe in terms of integral property, and  in terms of, oh, I already have this code.

So maybe I'm going to use what I already  have instead of choosing something else. But let's put aside all those engineering concerns and really focus on two things. The  first one is security. Go there. If you don't need security, maybe  you don't need a hash function in the first place. And the second one is efficiency. So is this how much energy I'm  expending per hash computation? So in some way, but it usually  boils down to speed. So how much time you wait between when you start the  computation and when you finish it. Okay.

Which is the simplest way to see  speed, how much time it takes, how long I have to wait. Now speed can  mean more things than that. Speed for what? Do you hash a lot of small  messages? Do you hash one gigantic, one huge message or many huge messages?  Because the speed might be different. For example, a few years ago, we designed a  small kid hash function that was called SipHash, which is not a hash, but it was  really optimised for small messages.

That's the first thing you consider.  And then how do you implement it? Can you pipeline? So you start hashing here  one message, you hash, but shortly after you start hashing another one before this one  completes. So can you pipeline the operations? So this brings us to the considerations around  parallelism. So I just like doing a few things at the same time. You can see parallelism at the  CPU core level, which usually relates to the use of SIMD instructions, single instruction, multiple  data, like AVX family, the SSE family, and so on.

Or it can be a multi-core level.  We have multiple core working at the same time and each core maybe  having some level of parallelism. Yeah, like GPU level, super multi-core. Do you have a cluster of GPUs that you can  use? You need to worry about communication costs and all those things. So there's  two basic ways to leverage parallelism. First, to focus on multi-core, because  it's simpler. Basically, I guess we'll talk a bit later. One simple way is, let's  say you have a message, M, you break it in.

It's maybe long, but you split  the computation in two parts. So you have two cores maybe. So you  hash like this, you hash like this. And then you merge the results and you get your  hash. This is the kind of linear parallelism approach that we applied in some variants of BLAKE  2. Yeah, the P versions, where P is for parallel. Just use multiple cores and  each instance was on its own, leveraging the core level SIMD instructions  to occupy different arithmetic units.

When we do this, because we  saw earlier the computation was this either a sponge or MD  construction, it was a chain, right? It was sequential. So how do we get  parallelism with these sequential operations? So you would just iterate over blocks in  two independent ways. But this is defined by your hash function. It's not something that  as an engineer, you have to implement manually. So you call a hash function and under the hood,  it will do that. There are some gotchas, some things to get right. The other way parallelism  is employed, and which might be more familiar to the people from the ZK space, is using what we  often do in computer science when we're stuck.

We use a tree. Okay, I'm going to stop at this level because it grows exponentially. So here  you have M1, M2, blah, blah, blah, up to M8. And you end up having the hash here. So  the way that is used is not necessarily, oh, my hash function is a tree. I think  the function MD6 was designed like that.

And BLAKE's tree design works a bit  like that, where you build a binary tree out of your messages, and you have a specific  way to pad each of those blocks. It's also used, well, I first got to explain what this is doing. Yes, what's happening in this tree.  Because this is not a Merkle tree, right? This is very different. No, it's kind of, so what I wanted to explain  was the Merkle tree way, where at each step, so here you use a hash function to hash those two  guys together, M1 and M2, which gives you a value here, x whatever. And here again, you use a hash  function to hash those two together, you get y.

And then you hash x, y, and you get this value,  and then you hash those two, and you get this. So at each node of the tree, you would call  a hash function. You would do the padding, you would do the iteration, and  you would end up having a value here. So that's what you have,  for example, in Bitcoin blocks. Okay, so that is a Merkle tree here. That's a Merkle tree, or a hash tree.  So it's binary, it can be ternary, it can be an octotree, like Filecoin is  doing. And then again, the choice of the ret and the dev is a performance,  simplicity, security consideration.

There's also some things to get right. So  I don't want to go too much into theory, but you may have to use different hash  functions at different levels to reach some theoretical security levels. For  example, this is also used in Sphinx. Which is a signature scheme. Which is a signature scheme, a post-mortem  signature scheme that only relies on hash function. So it's essentially building a  hyper-tree. A hyper-tree, a tree of trees.

Where the leaves are trees,  then everything is a tree. So signing is quite long, because  you essentially build a tree. And verification is much simpler, because you  essentially go from a leaf to the root. Yeah, like with Merkle trees. Yeah, so another way hash functions  are used is hash trees. But we are talking about parallelism. So  here, obviously, parallelism. Those two are independent from those  two, and so on. So it parallelises in a straightforward way. Then you have to  allocate it to your CPUs in a clever way.

So it's both the job of the implementer, the job  of the compiler, and the job of the CPU scheduler. It also depends on what you're doing on your CPU.  So that's why, so a small commercial pitch here. When we designed BLAKE3, which  is the best hash function ever. The best ever, yes. Yeah, this is the best hash function. Remember  this thing for this presentation. Seriously, our motivation when we did BLAKE2 first, and then  BLAKE3, was that, from my perspective, Keccak SHA-3 was too slow in terms of the number of  operations it was doing for its level of security.

You could reach the same level of security with  much fewer operations. And the user, I mean, it would be life-changing just for the user. And  BLAKE3 is extremely fast because of two reasons. We optimised out the number of runs, so the amount of computation in each  permutation. And we optimised also the layout, the tree. So unlike Keccak, we use a  tree, which makes it extremely, extremely fast. So faster permutation and tree,  which allows for parallelism. Yeah, because at the time when the SHA-3  candidates were designed, there was a bit less interest for multi-core parallelism.  And now we have highly parallel systems.

So we mentioned the mode, but we did not talk  much about what actually the function is doing, how the CPU is spending its  time when you compute a hash. And it will lead us to how to  attack hash functions. Okay, so what is actually a computer doing  when you hash? So when you compute, for example, BLAKE2 or BLAKE3, it  will iterate the following operations. So you're going to transform a  vector of three words, A, B, C, and D, where each of those is a 32-bit integer.

So this is happening inside the permutation? Yes, inside the key permutation.  Yeah, key permutation, yes. That's a 12. So we do three types of operations here. Addition,  integer addition, modulo to the 32, XOR, and word rotation, where you rotate the word by some number  of bits. And we repeat this with other offsets.

But essentially, all that BLAKE3 is doing  is repeating that over and again, and again, and again, and again. So it looks very, very  simple because if you modify, I don't know, one bit, if you modify the most significant  bit of this guy, then the most significant bit here will be modified. If you modify one  bit here, there will be one change here. So the way we attack or the way  we find weaknesses in this kind of algorithm is to track those differences, how  the differences propagate. And that's the whole principle of differential attacks. I'm going  to illustrate it in a very, very simple way.

Differential means observing differences?  Observing differences. So instead of just observing how one message is computed, you observe  two messages that are almost the same initially, maybe one or two changes, and you  see how the difference propagates. So what you may want to do, that is a strategy  that is called the perturb and correct. Perturb, and correct. Also, I mentioned this,  but inside VEX3, you do many rounds.

So the round is repeating that over again,  and again, and again. And the more rounds you compute, the more differences propagate in  a complex way, and the harder it is to track. So just to keep high level, the rounds happen  inside the permutation? And then we have this... So you can see this thing like a layer of  rounds, round, round, round, round. Which are almost the same. And the more rounds you  do, the more secure between speech marks it is. And if you do too few rounds,  then you're not going to get these crazy equations I mentioned.  So what you try to do, here we have, let's say we have two messages as input,  M and M1 and M2. Let's do M and M'.

And M and M', such that M XOR M'  are equal to some difference delta. Maybe one or two bit of difference. Sure, so all zeros and one ones? Yeah, for example. And then, we know that  statistically, there's a high chance of getting the differential delta one here, as  an output of the first compression. So here you give the first message block, we have  on the one side M1 and M1' for the other. So I wrote it once, but you compute it twice.  You compute it for M1, for M, M and M'.

So we'd also get a delta one prime, I guess? No, because that's the difference between the two. Sorry, sure. And then what you  do, so we have all the rounds. You're going to inject a block M2,  and for the other one, a block M2', which have some differences. So a difference, I don't know, we call it delta two.  So the result between those two. And what you've done, you've done your math, and you know that there's a high chance  that if there's a difference delta one here, and difference delta two there, then the  difference as an output will be zero. So even a difference in the output is zero,  it means that you get what? A collision.

But that was the idea of collision  attacks on MD5 and SHA-1. Perturb the state by some well-chosen difference,  and find out by analysing those small portions plus zero addition, and see that you  have a relatively high chance to get this, and then find a message that leads you to the  zero difference. Okay, just a quick question. Here are we drawing our Merkle-Damgård  thing again, and would we have this? Oh yeah, simplified by just seeing this  as a compression function. But in fact, you have the block cypher, and you have the small  thing, yeah. So for MD5, you have this part.

Just so we can keep... So yeah,  we could spend hours on that, but just want to give you the  general idea of differential attacks. And so if our permutation resists  this, if it's hard to find attacks, then we say it's a secure permutation, is that it? Exactly. So there's a few ways to gain confidence that your permutation will be  immune to that kind of attack. So the first one is just having many people try  for many years to find statistical patterns in it. And when they fail, then maybe it's  secure. And then you have slightly more formal arguments by the way you  combine and say, oh, if I do two rounds, I get this behaviour. Therefore, I can  infer that for this number of rounds,

I will have this level of this  metric or this level of linearity. So maybe to conclude, we're going to talk  of a different type of hash function. So currently, we talked of bits of  exhausts of zeros and ones. Yes. That's easy. How our computer works. Now, what do you do if your computer  cannot process zero and ones? It can't really do XOR easily. It  cannot do logical AND and logical OR. It can do the plus over the 32-bit integers.

Instead, your computer is a kind of mathematical  computers. It works over mathematical structures, like finite fields, like F or K. So  we're talking about our circuits or ZKVM. So it can be numbers, modulo some large  prime P, which is maybe a long of 31 bits, or long of 381 bits. Or it can be  polynomials. And if you want to simulate an XOR using those type of objects,  it's really hard and slow and inefficient. So if you want to hash on this type of  computer, you're not really going to use maybe BLAKE3 or Keccak. You're going to use  something designed for this computer that's

only doing the additions from this world  and the multiplications from this world. And when we mentioned that, so that's what  is called sometimes algebraic hash functions. And the best known one was... Or SNARK-friendly, right? Yeah. ZK-friendly or SNARK-friendly. Also  sometimes useful in other applications. And Poseidon was one of the first, if  not the first, that was really designed for this type of computer, but really  applying the foundational principles of hash function design. And it works in a  very simple way. So first, it's a sponge.

So you only need to design a permutation.  The rest is already done for you. Except, I guess, rather than XOR, we do addition? Kind of. It's even simpler than BLAKE3  because I mentioned two things. You need complex equations and you have  this idea of difference propagation. So you want to guarantee two things.  What is sometimes called confusion or complexity. So the correlation should  be very complex, high degree and so on. And the second one is diffusion, which is about  having this propagation evenly spread across all the states. So Poseidon does it in a very  simple way. So let's say you have four inputs.

You have four inputs. So each of those  inputs which will be an element of, for example, your finite field. These are chunks from our message? Typically, they are chunks of  the message that you split as blocks. And the first thing it will do,  again, you break down the computation as a series of rounds. These are  the rounds and then you repeat it. So you do first operation, which is about  confusion, which is about introducing high degree. And here we literally do high degree  because transformation is just an exponentiation where you multiply each value by itself a  number of times. So it can be three or five.

It's not too high because the higher the number,  the longer time it takes. But if you only do that, if you only do that, then the output here will  only depend on x1, not on those. So what you do, you apply a transformation where instead of  doing multiplications, you only do additions. So you're going to get four outputs, but  each of those outputs will depend on the four others. So it won't be a simple addition.  It will be an addition with coefficients, a combination of those two,  of the three, oh, no, what?

Four. A combination of those four with  different coefficients in a way that maximises the propagation of differences, but  also in a way that is efficient to compute. Is this what we call the round constants? The round constants, oh, they come  later. Okay. So here you add constants. Yeah. Why? Because otherwise the round  function will be the same at every round. Yeah. And if you only repeat the exact  same function, some type of attacks, like slide attacks, could work.  So that's why for every round, you do a simple addition with a constant  that is different for each round.

Okay. And you repeat that. And then we package 10 rounds together, call  that a permutation, and we play the course. It might still be too slow for some ZK proofs.  So what is very smart, what the designers did, they're like, okay, this is really solid.  If we iterate, it's very, very solid. However, sometimes you want more  diffusion than you want that. So some of the rounds are optimised by  removing some of the exponential part, which is slower than that. So they would iterate  some what they call full rounds with everything here and some partial rounds where you only  do one or two of those complex operations.

And I think Poseidon already has passed  the test of time. I think as we speak, there's also a competition by the  Ethereum Foundation to analyse new versions of Poseidon. And I know some people  are a bit nervous because it looks so simple. But from my perspective, I don't really  worry about Poseidon. The designers really know what they're doing and there's been  no bad surprise in terms of cryptanalysis. So yeah, I think that's pretty much  everything I had to say about hashing. We could have many more topics, but is there  anything else that we'd like to discuss?

I think that's it. Then this now ties in nicely  to everything we've seen in the rest of the whiteboard sessions. That we use hashes for  Fiat-Shamir, we use them for Merkle trees. Maybe the last quote, when you  use hashes for Fiat-Shamir, it's very important to do two things well,  to hash everything that must be hashed in the Fiat-Shamir proof, everything that  must be bound to the hash. For example, if you do a Schnorr, then you need to  hash over the challenge, the public key, the randomness. And also when you hash those two  elements together, it's important to have good domain separation between the different values,  particularly if they have a non-fixed size.

Otherwise, you could have collisions by having... Pretending that the sizes are different. Yeah, by having hashing twice the same thing, where it's the same encoding of two different  inputs, different sets of inputs. I see. All right. Thank you for that, and I hope that was  useful to the audience. Thanks. Thank you.