ZK14 - 7 years in Poseidon: Survey of (algebraic) attacks on Poseidon & Poseidon2-Antonio Sanso

Transcript

Hello. Hi everyone. Uh, as I say, I'm Antonio working at the Y in the cryptography team. Today, we're going to talk about, of course, Poseidon, as the title says. Um, let's see if this work quick notation. I'm between you and and the break. So, I put red stars in the slides. You want to want to pay attentions. The rest you can sleep, whatever. Um yeah so little disclaimer uh I'm not a symmetric cryptographer u this a hash function so you expect is a symmetric presentation is not and I'm telling you you why actually um po is an algebraic oriented hash functions so it's you

expect there will be like a lot of symmetric cryptography but there is instead a lot of algebraic and of course and public key crypton analyze it can go inside it and we're going to see some of it today. So it all started with this paper from 2019 u presented u by grai dimitri rashberger roy and shoner and let's see the ingredients of pose before to see how the the hash function is we need some ingredients it's really simple so we have fun fields over a prime p um you have this element of addition so

this like really simple addition over this finite field. Then you have this stuff called sbox that you exponentiate with an exponent d over a finite field and there is some matrix multiplication. That's it. If you know these four ingredients, you're an expert of pose. Let's see how you basically like pose looks like this. You have rounds and you have two kind of rounds. You have external rounds. So full rounds, internal call partials and again full rounds.

And the full rounds are different from the partial on the s number of sboxs. The partial rounds they have only the exponentiation only on the first line and the full rounds they put all the exponentiation on all the rounds on all the lines that are called states. So d is the degree of the sbox. That's really low if you want pos to be fast and the number of total rounds is the number of full plus number of partials. So we see some attacks today but you have like four category of of attacks in poset. You have of course the brute force attacks you can just like try statistical attacks and algebraic

attacks. And this the f the focus of today's presentation. And basically depending of which problem you attack you try to different things you you interpolate univaried polomials and try to solve for roots but varied polomial and for some instances you use the atomic bomb that is called grubner basis and is not part of today's talk. So back into 2021 we at the AF we already did some um bounties was called ZK hash function crypalist bounties was not only about posedon was about generic algebraic functions rescue was one of that and of course posedon was included

and the problem there that is a is a proxy for pre-image attack is soal seco problem stands for constrainted inputs and constrainted output. You basically this is the big box is pose and you basically you fix a number of input on the zero and you try to force some number of zero at the output and depending of how many zero um the problem differs. A little flashback that is going to be important for the second part of the presentation and in 2021 snark was more popular than Stark and Stark was over big primes. So back then like stark was over 256 primes

that are the primeus usually in the elliptic curve and um so we had this challenges that need to solve problems. In particular we had challenging to solve one problem and one stands for the number of zero you expect in the input and number of zero you expect in the output and basically how you want to try to solve this one problem. Simple again you fix it zero in the input and the first state the a you put random constant the first state you put symbolically x you run posedon and in the end you will have this polomial p of x so now you have a univari polomial of

degree d to the error we had so of course if you run pos with full round the degree of the polinomial is going to be huge but for the bounties we had this reduced round pos so the r was let's say manageable was of the order of 2 to the 30 2 the 35 so you have big polomial of this order and you need to solve for a a single root so as long as you find a root of this univari polinomial over f you manage to break this reduced round version of posedon and get the bounty so here We got some of the people that got the bounties was this paper

algebraic attacks against some arithmeticization oriented primitives and how did they do that? So again they solve a univariate system what's the way of doing that of course you can again try brick force but the standard way to do it is the so-cal rabin or cast can just algorithm that sounds madful but is not so difficult. So basically you want to solve for find a single root for a polomial f that I noticed that I will call P later. So let's call it P.

And what you do is you use another polinomial at the beginning. You use this polinomial Q and you compute Q that is like XP minus X mod F. That's the polinomial you want to find the root. So the the the degree of this polomial is going to stay tight to the degree of f. It doesn't go it cannot go bigger than that. And then you compute the gcd of these two polomials and you have a new polinomial r any factor. Now r is usually really small is the degree of r is in average one or two. So you basically you you found a

root of the initial polinomial f or I call it step two p with this with this algorithm. Now how much does it cost? So basically the most expensive steps is the first and it's about OMD. MD is the the the the cost of multiply two polomials of degree D. So the more rounds the more costly is actually to factor um a polomial but that's it basically if you want to find and solve C1 is about finding a root of this huge degree polomial they did it for some rounds and um this this is like the the numbers. So as you

see the the degree of the polomial was between 20 to to to 40 and well they managed to to break um some rounds of posum more than we expected back then. So the the thing improve it start to to actually improve a bit attacking wise of course. Um another things that actually discover is this this kind of technique that uh will be more important in the second part of the final part of the talk and this this skipping round attacks.

Basically what they did they they they did this mental model and they split posed in two parts. So pedon will be split in pi one and pi two and basically they managed to linearize the first part of posedon. So pi one will actually will not go uh through the s boxes. So the degree of the the polomial will not grow so much and uh they eventually they need to solve the the the polomial only for pi 2 and the degree will be will be less than solving the degree of the full p.

So back then they could skip maximum two rounds. So not too bad but something Um what happens after that is that u the same the subset of the co-author of posedon they came out with a new version of it called posedon 2 and poson 2 looks like this I mean doesn't look too crazy doesn't look like too different than before um let's see which one are the differences and uh the first things they that they start to to add the focus on on small primes this because Stark start to to work on small primes like at the beginning I remember they they moved to

Goldilocks but nowadays Starks runs over small primes like 31 bits. So this is the first things they move from big primes to small primes. The second things is that they add an extra matrix multiplication steps at the beginning and this is because reduce the skipping runs attack of one. So now the attacker cannot skip two rounds but only one just because of this extra matrix multiplication then and this is like one questionable choice and we'll see why the matrix in both the external and turnar rounds are non MDS while pos one had MDS uh matrix and um some other things they did is

like a manual things the round constants in the internal rounds are only added where the S box is. So this didn't change too much, but they were not useful and they they removed it. And uh what happens is last year we did a new uh crypto analysis initiative. This time only uh focus on pose and we use of course stark primes because we want to focus on real life instances of pose. One instance is for example is is this one uh this um this 64 bit primes and one things to to already notice is that p minus one is

smooth so it has a divisible by 32 and this is on purpose of course because we want roots of unity right want speed and um the question is now can we actually attacking wise can do any better when working with this polomial over the special primes I claim yes. So, and I'm going to show you how. So, there is this really old paper u it's actually a really old um technique from the 800 century 1800 century called graph transform that looks like this. um um basically it's kind of magic to me and u I want to just spend few minutes on it

and basically imagine you have this polomial p and of course you can always um write a polomial I go to the end on the on multiply the polomial so you don't know the roots you're actually can always to express a polinomial with the multiplication of the roots that you don't know and you have this polinomial of degree D. Now the magic things of graph is this. You can apply this transform in a really easy way and you will have a new polomial GP of the same degree D and is of this form Z minus alpha I squared. So you're actually squaring the roots of

the polomial without knowing them. I don't know about you but the first times I've seen it I found it really puzzling. I mean you're doing something acting on the root in a kind of homorphic way and in a really simple way. So you're squaring the roots without knowing them. So now why this is useful for actually finding the roots of polomial. You basically in a nutshell I'm not going to go through the algorithm but basically like you're starting for a polinomial you end up to a new different polomial and you're basically pushing the roots of the polinomial in the subgroup. So eventually you can actually finding the roots of the polinomial in a really simple way because you can brute force it and you reconstruct the roots of the original polinomial. So magic

um so we did it uh we did this paper with a few co-authors and um we actually indeed we were faster than than than classical uh pol root finding polinomial like canals were like few order of magnitudes faster than than the previous paper and um analytics to remember as well we here we are still talking about one so we're root finding root of a univar polinomial but in any root finding even barat or gro basis the last step mostly involves as a last step finding a root of a univariate polomial so this this is

going to be important for every CO problem and again this was a paper that brought with Joseeppe Gentai and Z so and um solving CEO problems again so in in this bounties we didn't we did not have only CCO one uh problem we had as well CCO2 problem now you understood the drill I hope so for CO1 we had the univer polinomial for CO2 we will have B polinomials. How do we do that?

We will have again two zero in the input. We have at this time two symbolic uh variable x and y. We go through poson and we will have two states with two polomials by variat. And what do we want to do it? We want to find a shared root between p and q. So we have a system of two polomials and where we want to find the roots and uh again we had people applying and uh and breaking our bounties was this paper uh ethereum post on bounties and how do you do that so again you can

solve barity system in different ways but the way they applied is using resultant and they use this really simple theorem and u I'm not going to go into this uh question of time but basically like they compute the resultant of this uh two polomials and what is the resultant is nothing else the determinant of a sylvester matrix if you don't know what it is no worries it's not this is nice too and here is how they did it they did the they broke again some of this reduced round uh bounties the computation is here that took some hours and some um CPUs and and so on. Another things that

they actually noticed is this and uh this is something that in my opinion is under appreciated. So if you're working on Poseidon attacks, this is something you want really to look into it. But basically they noticed that the the degree of the ideal but in if you don't know what an ideal is not important but basically like for the partial round the degree of the equation system grows less than expected at the beginning. So basically if you see there the degree is two RF plus RP in theory should be a two as well before the RP and there's not and they noticed that it was already known but they

actually empirically had an evidence that this actually the case and um in 2025 we had as well this other um paper called the algebra chip lounge and why I'm showing is only because one is basically before we say that you can only skip one round, right? Well, there is this appendix um of this paper chip lounge that um found a way to actually skip for two two rounds and at the end they write we leave as an open problem a more systematic study of this phenomenon. So I'm showing you that

actually reading appendix is important. Read appendix. Uh indeed I guess Simon and Alex read the appendix and they found a marvelous attack on poson 2. How the tax works? Basically I was telling before that um in poson 2 they are not actually using MDS metrics but they are using this special matrix that they cooked and they had that this kind of tensor like structure. So basically like the the external rounds as this uh matrix called me there's nothing else than the tensor product of of two smaller matrix P and M4.

And what they did is like they mentally wrote Poseadon in a different way. In the left is how is the original posed in the right is how they wrote Pedon. So dividing the M4 and the P and what matters it turns out that this matrix has some really special properties. I'm just listing two. The first is that they have real the the M the P no the M4 matrix has low um um values and low vectors and there's well low weight. So they have like small value and vector

with a low weight. So they managed to actually use this tractor to skip 10 rounds and counting. So yeah, that's uh this was really nice work. I invite you to to read this. This is really it's really kind of stunning and empas did other nice results as well that are worth reading. So what's now? Well, at least I can tell you what's now for for us for the foundation. We are using um heavily posed for the future especially in linearium and we are thinking to come back to poson one. So we are back to to pos one and um

what else status quo so poson is by far the most studied arithmetic oriented function but it's not enough. I mean we we we need more eyes. If you are an attacker, if you're a cryp analyst, please give a look into it. We need eyes. Um what showed this year is that we went from generic algebraic attacks to to tailor attacks. So this graph, this resultant, this this tensor. So there is stuff to look to be looked.

Please give a look into it. We we really need confidence on this new on this on this old now but new primitive and um another things that I'm a bit concerned myself is that where I want more eyes is that pose one so far has been studied mainly in the large prime regime. So we're using pos one in small primes and we need really need to have confidence into that and how we are trying to do that basically like we did a few steps this the present the future so we put $1 million on collisions uh the first one has been already claimed not the full three millions but

I think there was a three states collision so you can break the four four states you still get money up to $1 million And we have this uh crypto analysis initiative part two that uh well it start already. Sorry I I need to edit the slides but yeah it started and um well we will have a crypton analysis algebraic hash function on um Sunday. Please join if you're interested in the topic. We merge it with spring because it's the same same topic and planning for a post crypto analysis workshop invited only in Cambridge 13 to 15th. Ideally we plan to lock 10 15

mathematician in a room with food and and and drinks and see how it goes. And uh that's basically it. So, I think you caught us up somewhat. Um, I think we have time for maybe one or two questions. Does anyone have any questions? >> Thanks. Yeah, this is Kristen from Hey, thanks very nice overview. Maybe just a comment on this security margin if you want. So in sematic crypto we often try

to estimate the long-term security by looking at how many rounds you can attack and how many rounds the full thing has like a yes for example super trusted primitive has in its main version 10 rounds and the best attacks are like seven eight rounds so it's like two rounds margin and when you talk about attacks here people gets maybe scared a bit but putting this into perspective at the moment it looks like actually Poseidon especially Poseidon one and even Poseidon still seems to have more security margin than a yes right >> I agree that there the security margin still there and I mean we come from clarify basically >> come from two different like bias let's say of course like I'm more biased towards attacking so I put more emphasis

there >> the problem from my perspective and again like with all respect with for is that going from two to 10 round skip was a surprise >> and uh indeed like my focus was on having more eyes on on the primitive. So I really would love to see more people looking into it >> and again >> me too. Me too. >> Exactly. That's that's the emphasis for me is there like I would love to see the community working more towards having confidence on this primitive and again like I don't know is Christian for you was the same going from two round skip to 10 was kind of a thing and we came like a surprise at least to me

right thanks >> any other questions we have time Yeah. >> Um so at the end when you when you move back to Poseidon one that was because um the skipping wasn't possible because of the constant or because the matrix is different. >> So in in pos one the matrix are MDS. So basically if you see this tensor product structure is not present in position one because the the matrix are MDS. So there is some basically when when you choose the matrix for poseadon you're running a script and there are like mostly three checks or one depends if one is

sufficient if it doesn't pass you can run three different tests. The scary things from my perspective was that this test so pos two p the the matrix in pos 2 passed the test but they didn't catch this tensor and low weight values structure. So when you say MDS that is like there is no known tensor product that's >> yeah no yeah so far >> that that is a definition of MDS >> basically like you need to have uh the determinant should be uh the different zero for for all the minors so all the subset of the matrix and for big matrix like 24 by 24s well it's you need you

need to work to try the some matrix as MDS or you can choose like uh the the Boston paper koshi matrix and you can construct Koshi matrix being MDS or other forms of matrix. Thank you. >> Cool. All right. Thank you so much Antonio. >> Thanks.