Ethereum Hash Decision Tree

Transcript

Uh, thank you for coming for uh, the hash session and uh, thanks to Zuko to allow me to talk speak first. Um, actually uh, I think we will uh, fit into uh, 30 minutes with this uh, discussion, hopefully. So, it's it's all about um, which hash function Ethereum should use. So, we had the same question two and three years ago and at that time there was no alternative to algebraic hash functions and there was big Poseidon initiative, but now Poseidon initiative has largely finished uh, because modern proof systems allow us to to do the same things as with classic

hashes. And uh, today I would like to to talk and discuss with you and hear your feedback on this sensitive choice. So, if not Poseidon, then what? Uh, and uh, to there is of course not an easy answer to that. I'll try to narrow I'll describe potential answers. I'll try to narrow uh, the decision list and um, also I would like uh, of course would welcome uh, discussions and feedback on from you. In particular, when I mentioned some Ethereum parameters because when I looked them up there was some kind of ambiguity and not all the numbers uh, in all the tables are like probably they

are not 100% correct. And most importantly, uh, there are numbers that are supposed to scale up. In particular, if we aim for like gigagas per second or something like this. If we plan to significantly uh, scale up all the operations, uh, well, the numbers will grow and uh, it's up to many of you to uh, to tell me where we can potentially have bottlenecks even if we don't have bottlenecks right now. So, in this in the first slide, I tried to um summarize uh the main cases where hash functions enter big amounts of computation in the

Ethereum protocol. Um and well, there are like five six main use cases and a few smaller ones. So, uh one big case is um the signing. In particular, on the next iteration kind of in the future of post-quantum signing at consensus layer, we plan to have uh Linux XMSS signatures. And well, whatever modification of Linux XMSS comes out of uh OTS.gov and SICS.gov, well, it will be anyway uh uh well, hundreds of uh hash calls per signature. And if I understand this correct, we'll have at least several thousand of validators per slot. So, not

not not million, but several thousand we will have. This actually means that we'll have millions of uh hash function calls or compression function calls per slot. Um and actually, what what really matters there is that uh since XMSS is a stateful signature, we must uh care of uh well, the key generation takes significant time because well, the key generation time is proportional to the lifetime of a signature. And if we think of every validator to be able to sign uh 2 to the 30 times uh at most, and this actually uh well,

um the the enumeration of the signatures will go slot by slot. So, even if particular validator is not uh signing um at the slot, maybe we'll still kind of the the number will anyway increase so that it will simpler for us to uh care of uh I repeat the signatures. So, the actual numbers may be actually smaller. And this this sort of means that even if we have like two to the if we uh support to the 30 signatures, then we may uh we should be able to support to the the 40 hash calls uh to for key generation.

>> You can always prune it a little bit. >> Yeah, yeah, yeah, of course. Uh so, well, this is the not number set set in stone. So, if this appears to be too high, we have to arrange something. So, what may be really important here is that if this key gen uh is bottlenecked in some kind of esoteric places or maybe not so esoteric, for example, at hardware wallets uh and in particular in various MPC scenarios, uh unfortunately, the the particular choice of a hash function plays little role there. So, it will be one way or another. So, two to the 40 or two to the 39 hash calls it it will happen. So, and kind of pruning decisions will have much

more impact than a particular hash function choice. So, for aggregation of the signatures, uh there So, the the current solution is a variation of block on on lean VM. And uh So, if we take the same arithmetic, we it's probably means that uh for if we think about aggregating 1,000 signatures per call, uh per kind of per proof, for example, this means that uh we have to prove two to the 17 hash calls, which in turn uh get an estimates of uh uh commitment size that our witness uh uh the number of hands our witness will

be about several billions of bits. Uh and this is a potential the Uh So, we we have So this step must be within a very small number of seconds. Uh and of course if it does not, it's probably not uh kind of a a total disaster. This maybe means that we would aggregate fewer signatures per per iteration. And this would probably mean that our aggregation topology will be more decent more centralized and less redundant. So if we aggregate not 1,000 by but 400 signatures per proof, this would mean

that our kind of aggregation tree will be sort of more narrow. If it makes any sense. So of course feel free to interrupt me because this is supposed to be a workshop. It's not kind of my presentation. Uh so feel free to interrupt and express opinions. So um then the big case is the state tree and uh uh if we going to implement a new uh hash function there and replace the current MPT. So right now uh if I understand the math correctly, we um uh compute about 2 to the 17 uh calls uh the hash function when um computing a block.

Uh So by kind of this is sort of estimate from the number of accounts touched by an average transaction. And of course again similarly as with aggregation to this pretty much the same number of hash function calls translate again to about 2 to the 30 uh to maybe 2 to the 32 uh calls to execute in order to create a proof. So that's a non-negligible number. Um so and this comes to an account where in in item five, you when we going to prove Ethereum blocks with ZKVMs, that's the number of uh uh hash function calls we're going to make in order to craft a proof about 2

to the 30 hash function calls. And right now, this is the the number uh that uh has to go to uh GPUs. So I uh on one hand, we expect that proof systems become faster and more parallelized, and maybe GPUs with the same workload, uh maybe we could switch to CPU in the future. But on the other hand, if we going to scale up with the number of transactions, and again, this uh target of gigagas per second, then probably means that uh the number of hash function calls to prove and the number of hash function calls to create such a proof will again increase. So, maybe the GPUs is the the we we we will not be able to avoid uh

such such a help uh in the near future. So, there are like further use cases like uh merklization uh of the consensus layer uh with SSZ or uh or DAS schemes and such as future future DAS like Lin DA. So, there will be some hash function computations, but probably not big. So, if my understanding is like the current Lin DA proposal don't involve like huge really huge uh uh hash function configuration, but this may change if we allow bigger blobs.

>> Indeed, I think we essentially need to Merkle hash every like every blobs time two because it's uh it's an element encoded, but >> Right, right. So, if with rate 1/2, that's uh kind of the the total blocks blob size times two and uh yeah. For the moment, this is not going to be a bottleneck, but it maybe maybe in some future. Oops. Okay. So, let's look into the hash function zoo with which we're going to solve these problems. So, some some pictures to to scare. So, on the in the left corner, there is one round

of a classical hash function Blake 2s. So, what's interesting there? So, of course, the the letters are non-readable. They're not supposed to be. But what's what happens actually here? There are like uh 16 words. Each word is 32 bit. And they're going to add it modular modulo 2 to the 32 and XOR into other other blocks. So, there are some when you have the message to be hashed, it's uh sporadically inserted into the into the rounds. And uh there are some uh

in addition to XORs and additions, for diffusion, there are some uh rotations. Uh bit rotate circular bit rotations. So, what's interesting here? So, one thing that is interesting that the structure of all these rounds is pretty much the same. What unfortunately you don't see here is that the rotation indices are different. So, they create some sort of a mess and they're non-repeating exactly in order to have different uh diffusion uh in different uh sub rounds.

But on the other hand, this kind of difference and variety in uh rotation, it also means that some parts of the hash function may be weaker or maybe stronger than the other and it it's not trivial to to reason about the security of individual components of such a design. Well, the entire construction is fast and it's kind of heuristically difficult to attack this function. But why it is difficult? It's also difficult to say.

There are like a lot of things that make cryptanalyst work really hard uh but sometimes it's difficult to quantify. So, go to the numbers. So, such thing repeats for 10 rounds with the same message input and this is one call to Blake 2s. So, this means that the entire state is 500 uh 12 uh bits at and in fact, if this smaller boxes are viewed as a part of the secret key, then this entire construction is in fact a block cipher, block cipher that operates on uh a 500-bit block and a 500-bit key.

Uh and for this block cipher, uh the very nice part is that it's inside this orange box plus some extra operations. And nice thing is that this function F is actually uh the the construction this function F which turns this block cipher into a compression function. Nice thing about it is that uh there is um a security proof, concretely the indifferentiability proof that sort of tells us that uh if we assume that the block cipher here is ideal, uh well, I don't kind of it's ideal shortly speaking is uh idealization of a cipher saying saying that it's basically a set of

randomly chosen uh bijections. And uh it sort of it's proven that uh if the cipher is ideal, then the entire construction is indifferentiable from random oracle. And this by itself give uh allows us to use uh the compression function and then hash function in multiple constructions and to instantiate random oracle. That's uh which may not happen for all other hash functions, but fortunately both of Blake2b and Blake2s uh which are actually very similar, this uh construction holds.

So, what else is interesting there? So, there are some numbers uh how it performs uh natively and uh how many ends um are used in for example flock proof system, but um I'm afraid that kind of the numbers alone, they don't give much, so they always should be understood in the context. So, I don't pretend that we should kind of uh uh just com- just compare the numbers, but I want to give you a bigger picture. So, what's interesting apart from performance here for Blake2s? So, performance is actually I will later show, but it's actually really good. Uh what is not so great is that the

cryptanalysis records for for Blake2s. And when I talk about cryptanalysis records, I'm of course talking about the part which is not covered by security proof. I'm talking about this assumption then uh this uh uh construction inside a block cipher is ideal. And uh uh there are uh two ways to uh reason about the security of hash functions here. So, one way is to show that this assumption that we use here is not uh doesn't hold. It means we're going to show that this ideal the cipher is not ideal uh to show some sort of a distinguisher.

And for for Blake uh, such distinguisher exists for 2/3 of, uh, of the hash function. But, the existence of a distinguisher doesn't mean that you can attack the full hash function. Actually, vice versa. Collision and pre-image attacks, even on very reduced Blake2s, are not known. This actually means there is very big gap between, uh, what we, uh, can sort of attack in the idealized world, uh, to provide to show some sort of a distinguisher, and trying to violate random oracle construction.

There's a very big gap between this and collision and pre-image resistance. So, collision and pre-image resistance is given by much, much smaller number of rounds because we have actually no attacks. So, well, as I will show later, there is an attack on Blake3 on two out of seven rounds, and we expect, because they are similar, that also two rounds can be attacked, but we don't know this. So, the attacks between two functions don't carry, uh, to each other. But, this difference between, uh, ability to distinguish something from random and collision and pre-image attacks will also come up in the future, and I will highlight on that.

So, uh, Blake2 is actually standardized as RFC and is used in tons of libraries across the world. It's widely adopted for more than 10 years already, already almost 15 years, I think. Uh, so, it's and it's super fast and adopted in that disregard, there is no problem. So, Blake3 is the further iteration of of Blake2. It's it's even faster, in particular when in parallel hashing. The design is very similar, but unfortunately, the design is not the same, and what's what's worse is like two things. The first of all, this internal round is different. It's not exactly the same as in Blake2.

Unfortunately, it's not can be seen here, but you shall trust me that in fact the distribution of message words is um different compared to Blake2 to Blake2. And this is why if I take an attack on Blake3, which Zooko will talk about uh in in his talk, the very recent, I I cannot use it for Blake2. So, I I try I ask uh my AI assistant uh to to to translate an attack into Blake2, and it cannot. So, maybe some smarter will will be able to. But by default, it doesn't translate. So, it's not something you take it and apply. It just doesn't work as is. It is separate work. So, maybe and possibly that the same number of rounds will be attacked,

but it's not clear. So, that's why we cannot count for for a Blake for for cryptanalysis of Blake3 all the previous cryptanalysis papers because because kind of by default they don't apply. There exist some results, and then what's interesting there is that um there is a distinguisher uh which violates this uh uh randomness property. It's It is just uh slightly above uh 2 to the 128 complexity. It's valid because the state is actually very big, and distinguisher makes sense up to the 2 to the 5 112.

But at the same time, the scaring fact is that it covers all the seven rounds. So, if we think about uh 192-bit security, then it just doesn't hold to random oracle uh proof. Even if we can prove it, it it uh this construction then idealization assumption is not uh valid. But anyway, uh there is no right now indifferentiability proof for Blake3. Uh uh maybe and it's possible that it can be crafted, but it's not something that's kind of available right now on the market.

Um, yeah, but kind of performance is still great. And uh what have been recently found is two-round collision attack. Um, okay. Another interesting design, so I will ask you to concentrate on it because it's one of I think our favorites is SHA-3. It's the the famous standard in in hashing uh designed almost 20 years ago and being a standard for 15 years. It's notable for uh much uh lower performance compared to to Blake's. So, roughly two or three x factor.

Uh but uh what actually we we get from losing this performance. So, what's actually advantage of SHA-3? Advantage is that if we uh well, uh it's it's much bigger state compared to Blake two. But in fact, if we look into uh end count for proof systems and counted not per compression function, but per bit hashed, uh then uh the numbers are actually close.

So the what's ac- In terms of security, the cryptanalysis record is more than 50 papers on the on the webpage of of Keccak. It's more than actually for SHA-2. Uh and it's kind of super widely uh investigated and scrutinized uh hash function. So, there of course exi- it's uh it carries uh security proof. So, again this so-called sponge mode of operation it has uh uh the Keccak permutation, the bijective function inside, and it's proven that if the permutation is random, then the entire function is indifferentiable from

random oracle. So, we can use it in many places including Fiat-Shamir. Um well, in terms of distinguish and collisions, we have collision attacks uh on six out of 24 rounds, so 1/4 and distinguish on half of the rounds. Um Yeah, there is a variant of of SHA-3 uh called Kangaroo 12, which is uh not a modification like Blake 3, but it's just simple uh cut uh the Keccak uh the SHA-3 in in a half. So, just first 12 rounds of SHA-3 and because of that it's uh compatible uh to kind of most extent.

So, not of course compatible as uh single hash function, but compatible in terms of cryptoanalysis. So, all the cryptoanalysis uh that exists for SHA-3 carries to Kangaroo 12, but as long as we care about random oracle of differentiability, we probably shall ignore Kangaroo 12 because there exists a distinguisher on on on the full 12 rounds. SHA-256 is an old competitor, almost 25 years old. Um With uh what's interesting about it? It's super fast. It remains super fast and in particular with dedicated SHA instructions, it's uh very good performance. In terms of proving it's uh also very good. So, if you count the

number of and gates, it's also a relatively slow number. Uh it has excellent cryptanalytic records, so more than 45 papers. Um and collision and distinguish are close. So, we can Yeah, so the this number is increasing slowly, but not really fast and kind of round by round. So, we're still uh the security margin of course compared to to or uh SHA-3 is smaller. But most important for us is that actually SHA-256 as it is, it cannot be used as a random oracle replacement because of kind of this mode of

operation, it allows simple simple distinguishing attacks. So it's by itself is not indifferentiable from random oracle. It can be made so by modifications, by working with the first round and making message scheduling a little bit different. But what it result what will what we will have will not be a standard SHA-2. So we will kind of kind of lose one of big advantage of SHA-2 being a still a valid standard. So if we modify it to to have random oracle indifferentiability and also to have optimality for hashing 512-bit blocks, then these modifications will kind of make us do kind of a completely not

completely but a different variant of SHA-2 incompatible with what exists. Most importantly, so I think already so in in Ethereum if we choose so that probably different SHA-2s will coexist because there is right now already SHA-2 there is SHA-2 used in smart contracts. So precompile has been abandoned if I remember correctly but still Um so Um well for for this incompatibility in random oracle issues I would uh uh advise not actually consider

SHA-2. So um now some numbers um back into uh this table of use cases, most of which taken from numbers collected by uh other team members. I think Emil, you did a lot of benchmarks there. So, correct me if I'm wrong. So, what actually we do have here? So, for for key generation in XMSS, the range is from 10 to 40 minutes. Uh again, like SHA-2 is the best and SHA-3 is the worst. For uh aggregation of signatures, uh we have from uh 250 to 1,000 signatures uh per second.

Uh for um state hashing, so if we consider just uh plain compression function calls, then uh with Blake3, we can compute Merkle trees like up to four times as fast, but still the number is like 200 uh million compression calls. Uh this is I think more than enough for the current uh state. For uh EL signatures, that's a different uh beast. And right now, if I understand the numbers correctly, we have uh range from 60 to 200 uh signatures proven per second. Uh is it enough or not? It's

difficult to say right now because >> I think it will work because these things Thank you. These things parameters will be improved. In particular, um this was once fixed uh once Sphinxed um fixed quickly, but we can And uh for for instance, like recently, I tried a new set of parameters for Sphinxed. Uh much much better, much more optimized. And it was at like 800 Sphinx aggregated per second on CPU uh using Blake2s. But I I I guess it would translate in some like 200 for Keccak and 800 for Blake2s.

>> Oh, fantastic. Okay. Then there are some recursion numbers. So, again, if I understand correctly, so if we do like recursion when kind of we the verifier and the prover, they all use the same hash function then the the difference between them is the factor of three. And all this is kind of both numbers is tolerable to some extent. Right now, and what it was not clear for me is that how many threads, for example, was used here and this is the kind of way to squeeze more time by parallelization.

>> I think it was using 10 heads. 10 of the performance cores of the Mac, I believe. >> Mhm. >> Yeah, the the pain with Keccak is that the R1CS matrices in Flock are just above 2 to the 15, so you need to go to the 16. So, you lose a factor of four versus Blake2 and Blake3. And then your PCS hashing, like Merkle hashing in the PCS is like I don't know, two or three times slower.

So, it's kind of painful. It's painful particularly when you want to prove a lot of hashes. >> Do you think that it's possible to split Keccak into smaller parts to be better aligned to powers of two? >> Yes, yes, definitely. It's not optimized, but I think so, yeah, yes. >> There is um >> [clears throat] >> um There's the mini shake. Have you seen that? It just they just didn't publish it like today, I think, or yesterday, the Keccak authors.

>> No, I didn't. >> It's It's just Keccak with 32-bit instead of 64-bit lanes. >> That's completely new design. >> It's about four times cheaper compared prove than the regular Keccak. >> Well, I uh you're more of an expert than me on that part but It's not It's not that new. It's It's been test It's been like It's been around. >> It's probably a a derivative from like smaller state, right? The 800 or 400? >> Right. So, it's already been examined in that context as being the 800-bit wide width. Like the crunchy crypto contest that they did had a lot of results on the 800-bit wide version of Keccak. And so that's

that's this, which actually they defined the Keccak authors defined because of um some talk about this stuff uh where um that guy Love Sukenoff, whatever his name is, said um suggested this that version would be more efficient for this. And so, I emailed the authors what he said. And so, that's why they defined it. But anyway, I think it's a good uh new candidate. >> Uh I don't I had a question about the proving numbers. Are these with Flock or with the GKR?

>> Um it would be better with the Hash Caster between. >> How much better? >> Eight times better? But did you say that it is four times? >> I guess MiniShake would be even more than four X because MiniShake would be uh you gain a two X from the state and you get the two X from the number of rounds, if I understand correctly. And so, you get four X in Flock and R1CS matrices. And then the Merkle hashing of the PCS is also uh four X faster. So, in the end, it's even more than four X. Like maybe five or six X faster. But maybe we could I don't know uh it seems that we could we could afford 800 bits of state and um

24 rounds. Like we only would need a 2x to be close to the performance we have today, I guess. >> The the mini shake spec recommends 12 rounds. >> 12 rounds, okay. >> And there's a some kind of formula for that where they recommend the number of rounds based on the rate and the capacity or whatever. And so that formula would recommend 11 or 12, I guess, but they chose 12. >> Yeah, well, the thing is I think the the Keccak authors somewhat uh uh underestimate the importance of random oracle instantiation in the sense that they they did have this uh

uh distinguisher um on many rounds since almost the beginning, but since uh the original NIST call didn't ask for something beyond collision and preimage resistance, and this distinguisher was of no use for collision on preimages. And it covers so many rounds that it was kind of very tempting for both cryptanalysts and for the Keccak team to just ignore this thing because well, if it doesn't give you collision, then what? Then why why bother with it? It's kind of we shall not increase we shall not use too many rounds just because there's some weird distinguisher. But if we going to

kind of care about random oracles more and more, so we we use protocols based on random oracles increasingly. So we use complicated Fiat-Shamir instantiations, for example, in we are there like huge chains of absorbing and squeezing into into hash when doing Fiat Shamir and it seems that if we if we require that internal component has no distinguishers whatsoever up to 2 to the 28 in order to kind of freely use in differentiability proof then we

may need more than 12 rounds. So this this number of rounds it's it's related to the degree of the Boolean function that grows here. So basically in every round they do end so the degree grows by factor of two in fact and that's kind of with every rounds it's the 2 4 8 16 and so on so you have actually more So you have to have sufficiently many rounds to to so that your degree goes beyond to the 128 or something like this.

Yeah. Want to say something Mel? >> I don't know maybe uh I agree that we care about random oracle. So maybe it would make more more sense in our case 24 like keeping the number of rounds 24 and just having the state because we don't need this 1600 bits of states. But then we are no longer it would no longer be a standard at all not even a paper on ePrint so >> Yeah. >> It would be mini shake 1128 with doubled rounds. It would be mini shake 128 plus another mini shake 128.

>> [laughter] >> in a trench coat >> Do you remember what's the capacity in there? Is it still 500 bits? >> I don't know. >> Um okay what's the next interesting thing? So >> Oh I I it's 256 bits. 256 >> Yeah. Yeah, that's the 128 in in the name, I guess. I think Minishake 128 means that the capacity is 256 bits. >> Okay. So, here's my subjective opinion why we should uh actually drop four candidates out of our consideration. And this is of course debatable because it's not something

like it's broken or it's it's not a fit. But the combination of reasons So, for for SHA-256, we have this problem with differentiability and and sub-optimality for 500 double bit inputs. So, that a fix would give us a non-standard. That's Congruent 12. That's the same thing. Well, maybe we have to reconsider this in the light of this Minishake. But at the moment, so this 12 rounds doesn't allow to use in as a random oracle. And right now we have collision attacks on impractical collision attacks on six rounds. Uh this would means that we we

our five rounds is kind of half of this uh security margin is only half. So, it's not as huge as before. So, uh for BLAKE3, we would love to have more analysis of it. So, I understand that kind of the cryptanalysis history of BLAKE has been impeded by the fact that it's actually difficult to analyze. This ChaCha-based designs, uh they have historically low cryptanalysis record because it's difficult to conduct an attack. And if kind of distinguishing attacks have not been in favor because most people cryptanalysts didn't care about random oracles. Uh but in fact, if we promote this idea that distinguishers are also

important, then we may see uh more attacks in different scenarios on on the Blake family and that's kind of it will improve its its history. Well, to which extent we don't know. So, we had the same idea with Poseidon 2 years ago to promote cryptanalysis and we promoted up to the fact that one of the functions have been discarded. So, yeah, let's let's see how it goes here. I actually don't believe it will happen for Blake 3. Um So for >> What do you think what will happen for Blake 3? >> That kind of new series of attacks will will damage it significantly.

I I personally do not believe, but I I believe in the absence of track records right now. So, for for Blake 2B, I think it's just too big a thing. Uh we don't need it in in many cases except maybe doing uh making it duplex object out of it for Fiat-Shamir, but in all other circumstances, I think Blake 2S is is enough. So, it's this huge state is great for parallel hash and cough long messages, but it's not the case we actually have in in Ethereum.

So, uh we are left with SHA-3 and Blake 2S actually. Um so, I've already commented about uh random oracles and and standard model. So, what bothers me a little bit, um I I'm happy to see counter arguments, is that uh for for SHA-2 for SHA-3, we have collision attacks on six rounds and distinguish us on 13 rounds. So, the gap between uh these two guys is like 1/4 of a hash function. So, this would mean that they are kind of little not terribly close, but but close. So, for Blake 2, uh the gap is much bigger. So, we have

no no collision or pre-image attacks on any number of rounds, but we have distinguish us on 2/3 of of of a function. So, this uh this puts us in a dilemma. So, we kind of if we if we stand uh that uh uh ran distinguishers are important, then we are always counteracted uh with people saying, "Well, there is no collision attacks. There are no pre-image attacks. Why we have so many rounds? Kind of even two rounds were not broken. Why why why kind of bother with this six-round weird distinguishers that prove nothing?"

And there is always kind of at it attempt in thing to to use to to do it faster, to optimize here and there, to cut this round that seemingly not really needed because well, there is no attack after all. Kind of this attack, it doesn't So, probably this distinguisher that we have in the middle, it doesn't even translate on any protocol that uses Blake as a random oracle. So, it it's only kind of it it bothers us because it doesn't allow us to use this security proof. But uh kind of if we uh use um Blake2, there will be always I think uh attempts to to do like to make a faster version because uh the attacks exist. The practical

attacks exist on much smaller number of rounds. For SHA-3, there is no such temptation. So, I I I personally argue that no temptation is good in terms of uh hash functions. >> [laughter] >> Yes. >> For Blake2s versus Blake 3, um it turns out both have the same like the number of bits uh of and sorry, of and gates in the circuit to compute them is has the same power of two. Like the next power of two is two to the 14. So, in Flock, it turns out the cost to prove Blake2s is similar to the cost to prove Blake 3.

>> Oh, interesting. >> yeah. And so, that's why initially lithium was like doing Blake 3 and then we benchmark it on Blake 2S and because it was the same power of 2 in flock, you only essentially you only pay at the PCS hashing which was I don't know 20% of the whole proving and so you lose 40% of 20% so it's not that lucky, it's fine. I don't know. >> Uh yeah. What else to speculate here?

So in in Blake 2 uh there kind of usually what uh the security of symmetric primitives is built on two things, confusion and diffusion. Confusion simply means that uh individual bits or bytes that modified non-linearly so that the values are not traced. Diffusion means that the values are spreaded across the state of mixed with with one another. So if we look a little closer what happens in Blake 2 and in SHA-3. So in Blake 2 uh the diffusion comes uh from individual source and additions

one words into another. In SHA-3 uh the diffusion comes from kind of a little bigger uh linear operations so the diffusion is somewhat faster. The confusion in Blake 2 uh comes from modular additions where carry bits are non-linear operations and they kind of carry the values from lower bits to higher. So in SHA-3 the uh there is no modular addition, there is just single operation called He uh or Hi whatever uh that does non-linear operation and it's

uniform to most extent. It's not kind of that imbalanced and as model or addition. So, it can be argued actually that the design of SHA-3 is somewhat simpler. It's kind of Well, it's still complex to my opinion, but it's kind of easier to analyze and maybe easier to reason about. So, it may happen that kind of you you can obtain on such a design you can obtain attacks faster, but this it will be low-hanging fruits. And after you you you pick this low-hanging fruits, then the next attacks will be kind of more more difficult to obtain

and given the structure of of SHA-3, it may be possible to prove certain properties about resistance to attacks. They exist already in some in some form, but I think they can be improved again using AI. That's actually can be very good point of outer research to strengthen the design by proving resistance to attacks. Whereas my personal opinion then in Blake and of it's it's more complex. It's difficult to analyze. We don't have attacks partly because the numbers all here they don't match up. So, we have we have problems with making an attack, but it

doesn't automatically mean that there is no attack there. It just means it's us humans cannot find them. We couldn't. So, what what will happen right now, we don't know. So, how much AI will empower our captain Alice, we don't know and but Zuko will tell us in the next slots with this new initiative. But but still kind of my personal feeling is that for SHA-3, this kind of structure makes it more transparent and whatever we will have on its security and insecurity in the future will be more easier to understand, easier to implement, easier to prove, even if kind of more rounds

will be broken, but this breaks of rounds will be more obvious for us. This is of course highly subjective. So, this At the same time, I have that I don't know how to break either of this. Yes. >> Allow me to retort. >> Sure. >> Actually, it's not really a retort. I just think it's really interesting what you just said. It's highly subjective. So, this is saying I which I think you're I agree with you on the objective half of it. That SHA-3 and Blake 2S have this different what you just said. You're all You're right about all that, of course.

And then the highly subjective part is is [clears throat] the is the increased simplicity or legibility more helpful to defenders or more helpful to attackers? Right? That's what you were just saying is the highly subjective part. That's really interesting and >> [cough and clears throat] >> I actually don't have a strong opinion on that. You're much more of an expert on it than I am. But But, it's interesting that you're like that's that's your subjective opinion.

And it lines up with two other subjective opinions you just showed us. The previous one was the gap between distinguisher and actual attack or or like useful attack or whatever you'd call it. To me, that's also a subjective opinion. Is Does that mean Yeah, that one. You were your subjective presentation of that was that this is a like a weakness or a risk in Blake2s and even because in the future someone might propose a reduced variant like Blake3 is a reduced variant already. So someone has already done

this thing that you were afraid they would do. Um but wouldn't it be also a valid subjective opinion that this is because Blake2s is that that there's a part of it which makes it stronger against pre-image or collision attacks even in the case of distinguishers than SHA-3? So this would be a strength of of of Blake2s that there this gap this gap could be subjectively seen as a strength of Blake2s versus SHA-3. That the gap is bigger.

Is that valid or not? >> Um I I have a related question. I know nothing about the attacks but are are like distinguisher attacks at all related to collision or pre-image resistance attacks? Do they like translate into one another or they just completely different? >> Well, that's the thing that these guys for bigger number of rounds they do not. That's why. So of course in the heart of every collision attack there is a distinguisher. It's basically it's relies some some difference propagates with certain probability higher than it must be. And it by itself is a distinguisher. But what we call here a distinguisher, it's super contrived

property like if we take these inputs in this combination, then the probability that the outputs are in this configuration is probability not 1 over 8 as it should be but 1 over 4. And you think why why do why do you care? It's like it's kind of weird property, never ever used. But on the same time, if we kind of in we don't have anything better than that when dealing with this random oracle things. So, we we have today have seen already this random oracle versus standard model discussion. So, a lot of problems when going from one world to another is that we can't kind of meaningfully say what it is for a function to be a random oracle. And the

same here. So, kind of uh we either say it is random oracle, no matter what, or you say kind of whatever property is found makes it not a random oracle. So, it's difficult to have like a middle ground here. You either abs- accept all the weird things uh kind of for all hash functions, like accept all the weird sort of distinguishers. Uh or you ignore them completely. And this is of course also super controversial.

And highly subjective. >> Does that answer your question? >> [laughter] >> Yeah, I think so. I mean, also like just looking at historical hash functions, like is it the case that like a distinguisher is later developed? Like are they the same kinds of techniques that you would use to build the attacks? Like >> Well, unfortunately for say SHA-2 and uh well, this is SHA-256. So, the nature of the construction that it well, it has a lot of modular additions, for example. And its diffusion is relatively slow. This construction is like make it slow diffusion and slow confusion and rotate

slow diffusion confusion rotate rotate rotate 64 rounds of slow things. For this kind of huge number of rounds, there is almost no thing that can distinguish it faster than kind of traditional collision attacks. So, if if something is good for collision, it's good as distinguisher. If there is some distinguisher, it will probably used for pre-image collision resistance. But, kind of this SHA-3 and BLAKE, they're kind of new designs that designers have learned how to make fewer rounds. Their rounds of SHA-3 and BLAKE are much more concentrated. Like, they're kind of much more intense.

And they have a lot inside. They have some structure, like in SHA-3, like non-linear non- structurized non-linear operations. They have uh patterns like uh in in in BLAKE. Uh like similar diffusion patterns, and so on. So, kind of the designers have learned how to combine structure with confusion and still be uh resistant to attacks. But, this structure that they use, like in reinforced concrete, we have like steel and and cement, and kind of this

structure in new hash functions, it allows for these distinguishers. It's kind of they were not possible before because the number of rounds was too big, but with new more structured hash functions, they started to appear. That's why these gaps, I think. Um mhm There I think there was once uh Yeah.

There is uh one one slide that summarizes um differences between SHA-3 and Blake, but most of it we have already heard about the performance numbers the diffusion and confusion, so the proofs and duplex for Fiat-Shamir, but well, it's it's a minor thing and not really big matter in selection. So, if someone How does Sorry. Uh, yeah. Uh, if someone wants to have some sort of a decision tree, uh, then it's sort of this. So, if uh, we want

uh, to support bigger inputs, to have bigger security margin, to have better uh, uh, kind of uh, we have uh or better security arguments, then we uh, we may be tempted to use SHA-3. And if kind of we are performance uh, bottlenecked, if kind of we see that with the with SHA-3 the latency of signature aggregation or it giving proven is intolerable, then it's in favor of of Blake2s. And also if we kind of uh, more care about collision and preimages and less about random oracle

distinguishers, then it's also in favor of of Blake2s. So, I think of course the decision is not made today, but the arguments mostly remain. Uh, yeah, well, that's that's my last slide and I welcome more discussion. >> Um, is there a reason to use SHA-3 versus SHAKE128, like a XOF with a smaller um, capacity? >> Um, yeah, well, it's kind of uh, newer thing. So, not all I think cryptanalytic results apply to

to Shake. So, well, since it has smaller capacity, this means that uh kind of it's potentially more vulnerable to to attacks and not not all previous attack vectors have been expanded uh to Shake, but well Yeah, that's some some sort of an option, I think. Uh Depends which which attacks I think for the security here security point of view I think one of the most important. So, which attacks translate? If you have to make all the attacks from from scratch, then it's it's it's a different story.

Well, if not, then thank you for your attention and Zucco must have uh the stage. >> Where did he go? >> [applause]