Seven Years in Poseidon

Transcript

can hear. Yeah. So, yeah. As Justin said, we're going to quickly uh having talk about I'm gonna do a quick survey of about 10 15 minutes about some attacks um in the last years of of about yeah the first idea of in the room was like in 2018 discussed uh that about that quick notation I know some of you are maybe jet lag or the first of the day like I marked the slides that are more important with the red stars the rest of the time you can get sleep.

So uh so this uh I just want to highlight that we have this pos initiative that started like last year that is led by by by Dimmitri and me and George were giving some help and this is a mix of uh us just instead of a workshop and and attacks bounties on on Poseidon and we as well like to be try to be a bit more natural because we have this this kind of let's say central role of with having the image as well one of the creator and and and the works foundation as well this natural advisory board with the big names in the space like JP or elements on DRA and so on and the we plan to end this initiative by the January 2027.

Um so this is like a recap of the uh initiatives. Uh we have a bounties. Uh we have a research grants that we we get this year. We did three workshop. We'll do the fourth workshop in in about two three weeks. There's some uh special research awards to some special papers. And we have some um some other bundes not listed here. I think there is like that it's really tight uh on a groer basis and it's about 600k for 2025 for 2026 I think we're still in discussion on on the budget so uh I said uh the the structure was actually formalized in a paper in 2019

by by Lorenzi Dimmitri Christian Roy and Mark and um for people that never seen It is about it looks like this. I will not go in details. I I think I hope that many of you have seen this already. But it contains some um some some easy operation in some uh field over FP. this operation or some magous multiplication some addition that is marked with this RC and S is the nonlinear nonlinear part of the function this box that for as before Justin was said for qualar is exponentiating a field over an exponent tree and yeah this the degree of this

box that change depending of the prime chosen for colar is six so for three and the number First round is the the number of the the full rounds that are a bit more heavy and are less and the partial round that are the one marked in the middle. As you see the the partial rounds have a different matrix because it's a different color and the the sbox and the and the constant addition happens only to the first to the first line and not to all. Um in the course of this year we have seen some some some attacks on radius around and um actually there are like four uh at least like three various of possible attacks. Uh of

course like you can start to brute force and try to guess uh outcome of the of the of this function. Then you have statistical attacks. But today in this talk we cover only some algebraic attacks and basically like you can you can split the attacks in in in three three ways. You have like in interpersonal attack and we will see during this talk that is about solving unar polomial or by variat or in in more complex situation you actually you want to use like the atomic bomb that is grow basis. Um so u the in the algebraic attack in what you in order like to to kind of um simplify the attacker uh perspective the

outer of of the formalized this problem that's called a sec problem that is constra input and constra output problem and basically like you you fix some zero in the input and the output in this case like the last state is zero in the input and the output if people are able to solve this problem And to what we challenge in the bounties, what means is finding a a pre-image attack and yeah for example some of the bounties were about solving the the SEC one problem. So meaning one problem means that actually the zero on on to to fix is is is only one. So you have like one zero fixed in the input and one zero fixed in the in in the output. And the

way you try to formalize the attack is that it's kind of uh the natural way is you you run posedon in a in a in a in a way that you you map the first input to the to the to to an x and you actually run run through posedon. At the end you obtain in a symbolic way a polomial uh x in the states in the final states. And basically if you um if if you if you fix and try to solve px equals to zero it means that you find a solution to this this like polomial uh this polomial and you basically you have a pre-image for for like at least for the last zero of the of the

so um this was was kind of well known but the first one to actually formalize this attack was uh was was in this paper by var and bubier Lauren and Perin in 2022 and it was as a response of the first attempt to to have a bounties in in in Ethereum was done I think in 2021 and the way they did it is like in this kind of standard way at least in in in finding roots of polomial and there's a variation of the Robin or Ken counterinos algorithm that is actually you just need one root while this the more generic IC algorithm is actually focus on finding all the roots of the

polomial. But in the case of of oppos you only need one root and the algorithm is is actually works in this way you basically uh you compute this this polomial over this uh the algebraic closure of of this ring that is like x p minus x this contains all the solution to the to the to the algebraic closure and basically you compute the the gcd between this new polomial and your original polinomial and of course this This this will will have a new polomial that that contains the solution of the W you want to solve and you basically factor it and the reason you can factor now is because this this new polomial

error is actually a low degree usually it's a maximum degree too so it's really trivial and if we map how much this cost the first cost is the most heavy one so the first and the second are kind of driving the the complexity asic complexity and yeah the notation here is that MD is the is the cost of multiply polomial over FP and this this actually depends how you do it it can cost like if you use blue stand it actually cost a bit less so I say this this was was done and in the previous version of uh the hash function crypto analysis competition in 2021 they contain other hash functional uh the the authors of the previous paper

they were able to break some uh some bounties on the reduced bound uh reduced round of of posum and yeah but uh the question now is uh can we actually do better than this so indeed like the prime that we use in pose they're not like random they're are kind of kind of some special properties right and my answer is yes we can do actually better than that and how um so basically like the idea And you will see in the next slide that I'm actually one of the author of of this that we use this this this idea is we u we leveraged this paper of 2015 of Gren Vanderhovven and Ler that basically used this really

fascinating construction of the 18th century called a graphic transform and the graph transform is in order to work really good uh you need the the prime to be in this special form uh and we'll see that actually We the brand we are using even the qual is of this special form. Um so quick uh introduction of the graph transform of how it works. Basically the graph transform of a polomial P it works like this. You take your polomial and you apply this graphic transform uh that give you. So the polinomial p it gives you as an op new polinomial g that has the same degree of p but and the way how you do the transform is multiply the

polomial uh at zed you multiply with a polomial at minus zed and you evaluate at the square root of zed. Um hold hold on with me a second and I will show you that is useful but uh before then going ahead uh the the things to pay attention is this imagine that you start from the polomial and alpha i are on the root of of of the polomial. What you actually obtain with this transform you obtain a new polomial of the same degree of p but actually is the multiplication of the square root of all the roots. I mean the magic things of graph is that you actually you don't know alpha the root of you don't need to factor the polomial

and knowing alpha in order to to actually having a new polinomial with the square of the alpha this kind of really magic to me it's kind of working on the roots of the polinomial without knowing them and this actually turns to be useful and I just sketch the idea of the polinomial and uh it works like this uh uh again like the the prime is of this form So of the special form and you have s that is like t minus one / r and you basically like you compute the graphic transform of this original polinomial you can you can do n times and because like you can actually compose the the graphic transform and

then you have this polomial p that is the the the multiplication of uh z minus alpha iir R. And once you do that, you can actually use the FMA liter theorem and you have this observation like you have a beta I that is like alpha I to the R and what you actually obtain is that you are doing this. This means that the root of this trans end n time transform of graph transform is actually the they are the s root of unity because of uh the application of the mralitar theorem. And now actually you are

working on on on a subgroup and you can actually brute force the roots of this special polomial and yeah as as a result you actually found the roots of pild but actually you're not interested of the root of pild you're interested on the root of of of p. How do you do that? Um you better ask me if you're interested after this presentation because it's a bit longer but I can assure you that you can do easier than the original polomial. Um so the question is like do we have suitable bound instances or do we have suitable prime that we are interested in? Yes, one of this is I think this called Goldilock prime and this of this shape actually even the the

posed 256 challenge this the scholar field of BLS 12381 has this this this this for like we have this this paper that I think it's going to be in print in the next couple of days where we are use this attack to break pos bounties um now specifically we broke uh all the bounties, three of the four bounties on position 64 because this attack is actually three order of magnitude faster than the previous one on on on the cast just algorithm and actually a specification here I say we broke is kind of cheating because I mean I could

not break the bounty because I work at the foundation what actually happens is like we we're working on this without knowing each other on this idea in parallel and actually the people that broke the boundaries are gent and su but we actually eventually since we was the identical idea we decided to merge the papers and do a single one but technically they broke the bounties I didn't get any money of course out of it and here it shows that our attack is actually three order magnitude faster than the than the previous one that is as you see this like the seven is the paper that I showed before as this is like really really three times faster than than more or less than than the previous one just because we are using and leveraging the

shape of the of this kind of prime. Now uh this showed how to solve the CO one problem but what about CO2 problem. So what about if there are two zero we map to zero rather than one that is actually what we are interested because in order actually to break for real we you work on CO 56 problem. So but let's let's check two problem. So basically in this case you follow the same pattern before you you are mapping symbolically the first the first two input with x and y and you're uh you're fixing the zero in the input and you actually you try to solve some system of bar polinomial. So you have like P and X

in with the this B polinomials and you want to solve it and of course like you could use drop there but actually there is a more clever way to do it and this was applied uh by bar Oeller and Zeron and uh actually the date is is incorrect was 2025 was as a result of again the the bounty challenge we we we proposed at the foundation and actually they're using this this theorem that the polomial P and Q share a common root in the algebraic closure if the resultant P and Q is equal to zero and just like technically what is the resultant is the determinant of the

Sylvester matrix of P and Q again like for details you can catch me after this presentation and what they did with they solve many of the bounties on postm 31 and we have two actually instantiation of pos31 there are like uh uh developer and uh M31. So they actually did a great job on claiming many of the bounties and yeah for the rest like what about generic problem? So for generic problem use again I defined that before the the groer basis anatomic bomb and indeed like I'm not going to discuss about the groer basis now if you have any question like you can catch me after the the talk but

basically like you apply this generic attack for any g basically and it's the should be the fastest one for now if you have a better idea uh indeed like have some open problems for you like if you want to discuss about any of these um in the procedon workshop I think in a couple days. So one of the questions is like can we actually do better in basis for S3 and C4 or can we apply graph method for by polinomials or can interpersonal attack be improved in any way and that's it time for question otherwise I'll leave the chat >> one question [Music]

>> I was saying we have time for one question who wants to ask a I didn't know about the recent breaks. That's that's pretty cool. Um, how how good are you feeling about? >> Well, better and better every day for sure. >> Oh, >> yeah. I was more I was worried about small fields because originally was like told to be work like on bigger prime like 256 bits. L we shift our attention on smaller times that are like 31 bits.

I was worried at the beginning about it. I'm gaining some confidence as we go. >> Excellent. Thank you so much.