Introducing hashsma.sh

Transcript

Separately from my obsessive optimization project with uh with the NuCypher folks and Project 11 and Ethereum Foundation, we launched this Hash Mash Auto Research contest. And I'll tell you the results of it, but first I'll please indulge me in one of my favorite topics, which you probably all already know, but just in case I'll go fast, why you should use secure hashes for everything and never anything else. Okay, you guys already know this, but let me tell you real quick. Everything already depends on secure hashes, right?

And secure hashes are sufficient for everything you would ever want, as long as you don't want public key encryption. Right? Any questions? Next? All right. Okay. If you make a digital signature or something and it's uses hash-based, then I'll put it like this. The adversary can already exploit all of your users if he can break their hash function. He can already log in on their accounts and take over all their devices and sell all their Ethereum and everything.

So, if you uh if you use any other system than hash-based, you're adding a way that the adversary can exploit your users. And if you don't, you're not. >> [snorts] >> So, this is the incontrovertible rigorous argument that hash-based anything else that is not hash-based is strictly less safe than hash-based. The end. And by the way, I learned this from Daira and Mahawood like 15 years ago when we were doing a project that later turned into Sphinx that later turned into SLHDSA.

But, I spoke to Daira in the hallway a minute ago and Z said Z learned it from me. So, I'm very proud that maybe this was an argument I came up with 15 years ago or whatever. But, the way I remember it during Emma came up with it. Okay, any argument? Is this Everyone agree? >> I mean, yeah, more or less, right? But, it depends cuz if you're building out like, you know, IOPs and commitment schemes out of your hash functions, then you're >> Maybe you should Maybe you should do that.

>> I mean, yeah, but like, yeah, like I do agree, but just just to be pedantic, you know, if you're building out, you know, IOPs and commitment schemes and other things out of your hash functions, then you may be layering in additional assumptions um and vulnerabilities potentially. >> Okay, yeah, so it's hard to make an IOP in a a what? What's the other thing? >> Well, just like commitment schemes. >> A commitment scheme, it's hard to make it such that >> Oh, just >> to break it, the attacker would absolutely have to find a collision in the underlying hash function. >> Yeah, yeah, they don't have to find a collision to break this scheme.

>> Oh, well, the whole random oracle thing that Dimitri was on about, right? Like, this this argument is only true if Like, the attacker can currently exploit all your users if he can come up with the collision in the hash function that your users are currently using, right? He can root their laptop if he does if he can come up with the collision. If [snorts] he can come up with the distinguisher, he can't root their laptop. So, this argument only applies for things that are secure ba- are necessarily secure if the hash can't be collided. It doesn't apply to things where the hash has to be a random oracle. Does that make sense?

>> Yes, well Um but this kind of random oracle requirement is not something just completely different. that some can be also seen some sort of defense in depth. So even kind of if the hash is broken as a random oracle and protocol is formally broken, it can be still practically secure. Just when you find the practical collision, everything is broken immediately. But kind of when the something hash is not super random, it's not it doesn't mean it's practically broken. So just random oracle is just a stronger assumption.

>> Yeah, that's a good point. Like you like if like you were arguing for uh SHA-3 because it has more random oracle flavor or whatever you call it, in in differentiability or whatever. That's a that's a really good point. Yeah. That it's stronger um it's only an added it'd be way better. I'd much rather have a hash that's also indistinguishable from a random oracle in addition to being collision resistant. Definitely, right? Um >> Uh if I was going to be extremely pedantic, Groth16 doesn't depend on hashes, so technically it's not in the

everything else camp. >> It's not? >> It it doesn't depend on hashes. >> Well, so it's just on curves. But I'm being pedantic there. >> Well, my point is if you deploy a thing that uses Groth16, now the adversary can exploit your users if he can either collide some hash that they currently rely on or break Groth16. And that's just because everyone already relies on the collision resistance of a hash.

So, anyway, all right. Now on with the actual story about what's new. Um No, no, no. One more pedantic argument. Uh For a long time now, Darrel Emma Hopwood and I were arguing this. And thanks to Justin Drake, this is now all the rage and everyone's talking about this, which is super intelligent AIs being even scarier than quantum computers, than Crocs. Right? Anyway, so um here's my argument that Sphinx uh is safe even if there's a super

intelligent quantum computer, as long as that super intelligent quantum computer can't break hashes. And everything else isn't. Like this this column is the quantum computers and this quantum column is the the AIs. This may also be somewhat wrong. Dimitri's looking skeptical. All right, but let me tell you about hash functions, cuz that's actually new information. Ready? Oh, there's some more ancient non-new information. Uh I'll come back to that. You guys want to hear about the history of hash functions?

Real quick? Um Once upon a time in 2000 4, was it? Wang published collisions in MD5 that were actual real full collisions in MD5. And then like 5 months later, published collisions in SHA-1 and everyone panicked because we assumed she would then show publish an algorithm for how to collide SHA-256 too as well.

And those were the only three hash functions back then, so we'd have no secure hash functions left. So that was why we organized the SHA-3 contest hastily at that point, which produced Keccak and the original Blake, but SHA-256 never broke. So, that's interesting. And in fact, what happened was >> [sighs] >> over time. So, this is kind of the same time period, 2000 to 2025. And the uh the height here is the number of rounds in each one. So, SHA-256 has 64 rounds.

And over the years, the amount of rounds that you can find a collision in has very gradually increased. And the intuition that some people apparently have is that it's going to be like it's it's harder and harder it's harder and harder to find collisions in more rounds. Like this the progress is going to be slower and slower. This is going to asymptotically level off over the decades, I guess, is the intuition. And so, the Keccak team and the the Blake folks, now I I partic- I didn't have anything to do with the original Blake but I helped with Blake 2S and Blake 3, and Jean-Philippe Aumasson, the other Blake authors and me agreed that, "Hey,

look, uh 14 rounds is like way too many. Like rounds, you know, 11 through 14 are are are are useless. So, we'll do 10." And then we did it again. Um and yeah, the the SHA-3 authors just cut the rounds in half at one point. Um and this Where's that little light thingy? This um knee This is hard to see, but this knee right here is earlier this year.

Uh cryptographers raised the number of rounds that you can find an actual practical collision at SHA-256 from like 31 to like 37 overnight. But that was that was like in May, okay? And this dot here is when the last 7 days since we lost launched Hash Smash, there's a small improvement to it. So I guess I'm not sure what the moral here is that like it's not asymptotically leveling off at all because this is a big jump.

And and then look at at at at Blake. Um there's a like like like we're just I was just arguing about there's two subjective interpretations of the total lack of progress on actually colliding Blake for 20 years straight. Um one is that no one really tried very hard and and the other is that it's just impossible to collide Blake. But we have a two-round Blake 3 collision which is actually practical or semi-practical.

And I was asking my AI cuz I'm not really an expert on this stuff. So I asked my AI why didn't any Oh, so this is this is one of the Hash Smash results. There's two new results from Hash Smash from the first 7 days. Well, there's three results. The third one is no Hash Smashers have done anything to SHA-3. >> [laughter] >> Right? There's only three targets on Hash Smash. Well, I maybe I should have explained that part. So we launched this thing called Hash Smash and it's an outer research program and we picked three targets with Poseidon coming soon. And the three targets are SHA-256, SHA-3, and Blake 3.

And we got a whole lot of contributions from people, but almost all of them were just executing ideas that were already in the human-written science literature, right? But it turns out this one was never published in the science literature. This is two Oh, okay, hold on. This is no longer a timeline from ancient history to the current day, this is now the number of rounds of a thing. So, SHA-256, can you even see that? It's kind of blurry. Yeah.

SHA-256 has 64 rounds. And 31 of them, oh no, wait, 37 of them you can collide. So, so it's sort of more than half broken if you think of it like that. But, if if they're like exponentially hard to extend, and if the progress is going to level off over the decades, then it's fine. SHA-256 will never break. Um anyway, SHA-3 has 24 rounds, and already before we started this, five were totally collidable, and six were kind of kind of not, I guess, realistically. I don't remember the exact

tech factor or work factor. And then, when we started before Hash Smash launched, uh Blake 3, like the first round kind of doesn't count in my view. Like, obviously, you can find a collision in one round. Come on. Um and nobody had ever published an attack on the second round, and now it's quite quite practical to find a collision with this new result that was published on Hash Smash, um to find a collision in two rounds of Blake 3. So, I asked my AI, why was this not previously published by other cryptographers? Does it use any Like, is it a really novel, creative technique?

Um and my AI was like, "No, that's not really a new, novel, creative technique. That's just all the same techniques that we've been using for like 30 years applied to Blake 3." And it said, "The reason that it's not published is because the referees say that two rounds is just boring, and nobody wanted to bother publishing it." Do you think that's plausible? >> Yeah, I really do think so. >> Yeah. >> So, why I looked at one of these attacks So, uh I looked into one of these attacks on Blake3 and it's actually very legitimate uh attack, well typical differential cryptanalysis, but requires a lot of manual work. So, in the past it would be like

some >> Okay. So, uh in the past that would be like uh a solid paper uh several I know weeks or maybe even months of work. So, now you can do much much better with the AI. So, I I actually asked in one of these submissions I asked AI to explain me a lot and I kind of interacted with it for quite a long time and I will was able to extract some actually insights from from this attack.

So, what what they used, how they kind of Yeah, how they selected certain messages and and part of the state. So, this sort of kind of a digestion that we have all hoped uh to get from uh uh auto research. I think it's overall very uh informative. Yeah, then the question is how to handle 133 submissions. That's I don't know yet. >> [laughter] >> Yes, Dmitri is a volunteer judge for Hash Clash. Um and the AIs are outpacing the humans.

Surprise surprise. Um >> Could uh I'm going to provide an observation cuz I've been a avid auto researcher contributor. >> Uh-huh. >> When I started deciding which of these challenges um that I would focus on in different periods and in different runtimes, and I think it like aligns with a lot of what has been said, Um my AI said, "Well, there isn't much research on Blake 3, so let's just start with the top two." And I found that quite interesting now reflecting >> start with what?

>> Uh let's start with SHA uh 256 and SHA-3. >> Oh, interesting. >> Yeah, so directionally and trajectory-wise, when I started prompting my way through this, and I'm no experienced script analysis person, um mostly just good at the AI. Uh it kind of pushed me in this direction because it had existing literature. >> Right. >> So, I actually think that that's quite uh like I thought that to be an interesting observation after hearing some of the analysis today around just the fact that no one's done it yet means that it could actually be possible but the AI might actually struggle more um to find these attacks. Uh

I don't know. It was just one of the reflections that I had after doing like the initial survey of my like potential to get onto the leaderboard for these. It was like, "Okay, let's just focus on these two because I think your potential is higher." >> That's interesting. Um I wonder if the AI or you know, the AI is sort of like the the mean of everyone else's opinion and intelligence and knowledge and stuff. I wonder if the AI, like Dmitri, doesn't really connect Blake 3 to Blake 2 to Blake. Like Dmitri has a very rigorous argument about the internal function and

how it differs, but um one of the details Let me the reason I volunteered to help with Blake 2 way back when is because um Blake, the original Blake was in my view the most conservative uh option in the original SHA-3 contest. Um Keccak was like beautiful and elegant and novel. And Blake was using the ChaCha function which was already a a boring old stream cipher from earlier.

Um And the the mode of Blake was also a boring old mode that had already been studied for a couple of years by then. Um And in the competition NIST evaluated that the um the amount of cryptanalysis that had gone into Blake was even greater than the amount of cryptanalysis that had gone into Keccak during the competition. Which is interesting. And anyway, that's one of the main themes of the whole hash mash thing is uh the the Why you can't even see that.

That's great because that's the point of it is you can't see it. It's the undiscovered the the negative results, right? If if there's five new discoveries, I I don't know if this applies to like all of human science or all of AI science or if it only applies to cryptanalysis, but in terms of like which secure hash function to put into Ethereum or whatever. All you really care about what what you really want to know is how hard have people tried to break it and failed? That's that's really the That's >> [laughter] >> that's really the only Isn't that? I mean, I think that's basically the only thing. If I just learn one thing, I just learn that and that would tell me what to rely on.

And then what we have is sort of almost the inverse. It's It's when people succeeded. And this is that subjective debate where Okay, if they if they succeeded three times to attack a a weakened version of A or a variant of A and they succeeded two times to attack a weakened version of B or a variant of B, what does that say about uh how much someone is trying to break A versus trying to break B and failing? I would almost say it tells you nothing, right? Like you like it could well indicate that people are trying to attack A more and

it could well indicate that um A is weaker. I just subjective, I guess. So so the best outcome of would be if we could directly access the negative results. Um I guess it's a tragedy of the commons where in normal old science, the way we've done it all along for the last few millennia, the the scientist who publishes this gets benefit, right? And the scientist who tried and failed is not going to gain anything by letting people know that he tried and failed. But but for the rest of us, what we want to

know is the one who tried and failed, right? So So, that is one of the next that is the next There's two next things we're going to try in Hash Smash. >> How do you assess whether a negative result is interesting? >> That's a great question. Totally that's So, we have some ideas, which are crazy stupid ideas. Maybe in a year or something we can review. Um okay, so the very first thing to do is the stupidest thing ever, which is um just add on to the Hash Smash website uh plea to please submit your negative

results. Like we we really want to know how hard you tried with what model and how many tokens to attack which of these three or four algorithms. And we'll like put your name in lights and give you credit if you submit it. That's step one. >> Well, negative results did play a big role in in history because the number of cryptanalysts was limited. And well, we knew that if prominent certain prominent cryptanalysts from University of I don't know New Foundland or Pittsburgh or whatever attacked primitive A, and didn't attack primitive B, we knew that well, probably

they tried and they probably failed. Well, maybe if there were like 10 groups and seven of at least a few of them did try to attack all the targets cuz there were not that many targets. There were also reasonably many but not too many cryptanalyst groups. And just from the from the absence of results, we could uh imply that kind of they tried and failed. Well, the less famous primitive B was kind of the less true it is, but for pretty much widespread constructions like Blake 2, we could still reasonably imply that well, people tried and failed. And from this fact, since

cryptanalysts they were pretty much the same all the time, well, some new people come, old people retire, but kind of the the strength of cryptanalysts remained more or less the same, and we could make some meaningful implications from the fact that they couldn't break it. They say, "Okay, if they couldn't break it now, it's unlikely that they will come up with a new attack tomorrow or in a year because this is the area that evolves evolved with predictable pace. Right now, the absence of results or kind of some negative results from interacting with AI, I don't know what it what it tells you because kind of today it fails, tomorrow it will not fail or it will or

you will you fail because you don't know how to ask. >> Yeah. >> What's your name? >> Mitchell. >> Oh, yeah. >> Yeah. Um so Yeah, so I I I tried um directionally going to towards uh black tree cuz I I like it and I thought it was um like I use it in other things as well. Um so but the yeah, the it was interesting. I think um what I I've been thinking about while you've been speaking, I also have kind of like a preference in my model and harness that I want to spend fewer tokens for obvious reasons and I think that actually may have played into this as

well after hearing you speak that it may have just thought, okay, too many tokens to try and um get onto the leaderboard for this because the incentive is to come up with that like greater lower down the um thing attack, too many tokens, let me get onto the leaderboard for these other two. Um so I think that that definitely would have played into it. Uh the other thing that um reflecting on last week when I was working deep in this, I guess, was around the um like the way that the existing papers were

being almost like added to the like research list, I was trying to like compress all of the papers so then they could become references so the AI could then spend less tokens to then come up with these different attack types and work out if they crossed the the the different type of hash functions as well. So that may have also played into it the fact that there was just more evidence to go from. Therefore I didn't have to spend as much tokens in order to generate new evidence or I also have like a fairly modest gaming PC that I run a lot of these computes on.

It may have just been like no, you kind of need a little bit more like CPU power. You need more. It's going to take that's another thing that often blocks if or creates the gate for opportunities in this is I kind of ask for a timeline and I'm like how long am I going to have to leave my computer on uninterrupted in order to do these things. I want to be able to either work on another challenge and I I I do remember like the Blake one was this is a two-day like runtime research endeavor.

And it just became a preference thing then. >> Um about what Demetri said about negative results the public being able to infer negative results. I really agree. Remember what he was saying about that about the fact that there were a few targets, they were prominent and important and there were a known set of cryptographers that were at work and you could infer that those teams would have looked at more or less all of those targets. That's very true and that's like pretty much the whole point of the SHA-3 contest and before that the AES contest. It's almost like the existence of the contest is just a way to overcome the problem of um

not being able to see negative results. Um so you you assemble all of the best cryptographers and you get them to staple their reputations to the fact that they're participating so they can't just slack after that. And then you get a bunch of candidates and then you winnow the candidate list so that there's only a few left in subsequent rounds. In the final round of SHA-3 there was five candidates that included Keccak, Blake, and three other candidates. And that's all to all so that if there are no new results posted against a candidate you can still with some confidence infer that the cryptographers did look at it.

So, that's kind of like we're trying to recapitulate that with Hash Clash in an open, accelerated, and AI-powered way so we can generate negative results by by lack of results, maybe. If um if time passes, this has only been 1 week, right? And we got these two tiny kind of like pretty pretty tiny results. Like the fact that there are results at all is cool, that proves something to me, that proves that it worked at all, right?

But nobody really cares that we moved we went from 104 bits of security to 95 bits of security when breaking we're finding a collision in 38 rounds of SHA-256. That's um a very far cry from affecting anyone, right? And likewise with the two-round attack I'm I'm not 100% sure but I kind of think just two the first two rounds don't count. Like the first two rounds are free, nobody cares about the first two rounds, I guess. I don't know. Um What was my point? Oh, but now if if if we keep running it and we keep getting evidence of participation, right? We have the same problem like somebody's going to say, "Oh, nobody does Hash Clash.

Uh we all moved on to the next one already." But uh maybe I guess if the number of submission counts keeps ticking up or if we get differential results, if somebody starts breaking more and more Blake 3, but doesn't break SHA-3 or vice versa, then we'll feel like we're learning something, right? Plus which this half-assed crazy scheme that Sriram and I have come up with to try to get people to tell us their negative results directly. Okay. Um What else? Um Mitchell, were you saying in the previous discussion with Demetrius' presentation were were you saying that you're benchmarking hash functions for Ethereum's purposes?

For choosing what to what what hash function Ethereum should use? Oh, it was someone else who left. It was someone else who was sitting there. Okay. Hm? Oh okay. All right. Any other questions? Thank you for listening. Go to Hash Mash. Uh tweet at me on on Twitter. >> Zooko, for people who have feedback like this, thank you.

>> Connor is from Project 11 and he is part of the Hash Mash team. >> Hello. For people who have feedback like this, which is invaluable, where can they tell us about it after this? Or where do you want them to tell us about it after this? >> I don't have a good answer to that because the Yukon folks may have a way that they would prefer. That's what So, my answer was tweet at me. >> Okay, let's do tweet at you for now. >> Okay, tweet tweet at Zooko for now, but hopefully there's a more structured way going forward.

>> Yeah, more feedback the better, definitely. >> Mitchell? >> I was um I was mentioning this yesterday to you, but um something I'm also working on for these negative results and somewhat inspired by a conversation is I'm trying to build like a almost like a deviation chain of all of the negative results and then actually hashing all of these negative results so then it builds some sort of compressed way for me to share it. >> Mhm. Yep.

>> So I'll continue to cook on that and I think it could be with the Yukon question that you just had they've got this discussions part. I think that's maybe part of it. >> Yep. >> You can submit a discussion. >> Yep. >> But I think one other opportunity we could consider is with when you do have a result that gets through appending and attaching one of these like chains of evidence of like almost like proof of work of how long it took, how many different pathways you went down and tokens. The only problem with that I find is that

it it's going to vary significantly based on the like context and the memory that the model that you're using has on how quickly you can get to a result. >> So you're saying asking the number of tokens in the model is not a good Yeah, I think I think that could >> Yeah, that could create irrelevant assumptions. >> Um >> I think it like a it would be like a good general number. However, I've definitely seen like some harnesses and that get to a result much more quickly >> Mhm.

>> than others. >> Yeah. >> So >> Okay, let me say one more thing about the negative results part. We have three ideas. The first one is super stupid and the third one is like I'm having AI psychosis and I'm like that's going to completely replace all of science for the rest of history. There's before and after this moment. And then the middle one is proof of work, but the third one is Okay, so the first one is ask people to tell you they have negative results. Like I I used this model, I spent this many tokens, I tried this technique, it didn't work. Okay, that's the first one.

Great. The second one is proof of work, which is like prove that you spent that many tokens. And that's an unsolved problem, but solvable. Um in various interesting ways. We could use TEEs, we could use that What's the name of that watermarking scheme that Google and Anthropic are inserting into their AIs? You could use the watermarking scheme to so the submitter would have to prove that they'd spent whatever, whatever. But then even if you did that, even if you could solve the proof of work problem, how do you know, like you say, uh it's just like it's not just stuck in a loop spent wasting wasting tokens trying the same thing over and over. Or this new submission is trying the same useless thing that all of the other submissions have ever

tried. So it's not any evidence of what we're looking for, which is whether Blake3 or SHA-3 is safer. >> [laughter] >> Right? So in order to solve that, you just need one more thing which changes all of science forever for history, which is a map of what's being tried. That's all. You just have to say I'll credit you with your negative result as long as it's different than all the other negative results I've already paid out for. >> Well, you have already like a hundred submissions for >> [laughter] >> for Blake for Blake3.

And if you open up like all the next rounds, like two and a half rounds or three rounds, and you will have there again like 30 and then maybe I don't know five submissions. That's already pretty informative. >> Wait, what are we What are we learning if we say you guys can start submitting for three rounds and then we get fewer submissions for three rounds than we got for two? >> You will get fewer and they will kind of have smaller gap from from exhaustive search. >> Right. And we kind of did this already up here because we opened it with 31 and 32 is the target for SHA-256.

And then we realized that a human cryptographer had already broken those before. And so we moved it over to 37 38. >> And then we open next few rounds and then you will see this curve kind of as usually has like for AES every next rounds makes it more difficult. >> Okay, so if we open a few more rounds we can see the curve. And that's yeah. That does sound promising.

Actually, we are going to do that. The the Yukon folks have already implemented I haven't seen it yet, but they told me that they implemented a generalization of the Pareto frontier where you can get on the leaderboard by increasing by improving any of the attacks on any number of rounds. So that would show us the whole curve, right? >> Yeah, actually I don't know how much it's supported now, but there can be like not one block collisions but two block collisions. So one thing that was exploited in late three is that you can inject the difference in the length and it immediately cancels with the first message block that goes into it and then you have like one and half rounds differential free. So one can imagine that

uh you can have like two block attack so that some non-zero difference goes into the intermediate state and then appears back uh as input to the second block and then being worked on. >> Yeah. What does that have to do with the predator frontier or what? >> It's kind of a variation of the head functional to your attack. >> Don't the two blocks of missions just show up? I mean, the two block attacks just show up.

>> I don't know that the one that I've seen it's one block at least for Blake 3. >> Oh. I thought this one was two block. No, that was just one block. It did use the length feature. >> I think that the length feature is used in this one. >> Okay. Oh okay. Okay, so that's one option is open up the things that people can attack and then we learn from seeing what they attack. Get a bunch of information from that. >> I'd say in the prompts evidence file you could also also ask for other any like fingerprints or footprints or any

attempts and how many do you have? >> In the >> And and then that could almost be like a just a signal that maybe that submission we should follow up with that solver and ask for like more of a digest. >> Asking the submitter to include what? >> Uh so, how long and if they had any submissions, if they had how many failed attempts >> Oh, so in a new successful attempt, please also summarize all the failed or attempted things you've tried.

>> summarize, but just indicate whether or not they were if that makes sense to them. >> Mhm. >> It becomes a like a follow-up as opposed to like crowding the evidence file potential just crap. >> Okay, so in the prompt say if you have tried if you like also include a com- a comment about how many other things you've tried before this. Right.

Yeah. Yeah. Yeah. Yeah. Yeah. I really like the fact that it relates to proof of work of all things. It really actually does. It's actually what we want is a verifiable proof that you spent work. Weird. Okay. Well, thanks for listening. That was super fun. Please tweet at me or whatever.

>> [applause]