██                                                                
              ██     ████                                                       
              ██     ████                                                       
                       ██                                                       
  ▒█████░   ████       ██      ██    ██   ██░████            ██▓█▒██▒   ░████▒  
 ████████   ████       ██      ██    ██   ███████            ████████  ░██████▒ 
 ██▒  ░▒█     ██       ██      ██    ██   ███░               ██░██░██  ██▒  ▒██ 
 █████▓░      ██       ██      ██    ██   ██                 ██ ██ ██  ████████ 
 ░██████▒     ██       ██      ██    ██   ██                 ██ ██ ██  ████████ 
    ░▒▓██     ██       ██      ██    ██   ██                 ██ ██ ██  ██       
 █▒░  ▒██     ██       ██▒     ██▒  ███   ██          ██     ██ ██ ██  ███░  ▒█ 
 ████████  ████████    █████   ▓███████   ██          ██     ██ ██ ██  ░███████ 
 ░▓████▓   ████████    ░████    ▓███░██   ██          ██     ██ ██ ██   ░█████▒ 

Leave Bernstein alone!

by silur

So what I hear about curve25519 being broken?

A couple of months ago (time of writing is 2019 may) there were some reddit rants about how you can multi-spend in monero because of the cofactors used in the elliptic curve design. There were multiple “solutions” to this non-existent (cryptographically) problem, but scientifically the best contribution around this storm was due to Mike Hamburg, who proposed a new compression method with minimal overhad to form prime-order groups… AGAIN.

See, the problem here is that the cofactor issue was addressed in anctient times by the people who knew where the boundaries of thoughtless optimizations and security are. People tell me the specifications and the mathematics were wrong.

No patrik, p*8 is not a prime!

Most “conventional” cryptographic papers starts with “let p be a prime”. Thankfully, the majority of programmers nowadays know what a deadly minefield cryptography can be and don’t go into implementation details (this leads to another problem if done on highlevel API usage). My problem here is that most implementors somehow fell into this thousand-year-old trap again. Operating over prime-order fields is super expensive. This is one reason why we only have “toy” hardware wallets for Monero at HCPP. So coders started to avoid using prime orders (Y U DO DIS??!?!?) and get closer to powers of two to speed up things. How can we get away with this when the base point order is still prime?

The connection between an element’s (especially the generator’s) and the group’s order is not that strong. We have Sylows theorem that states that the order of an element must be a divisor of the order of the group which is trivially going to be the same number with prime oder groups (we can’t have order of 1). If we introduce the cofactor to speed up our computations we can use the very same property to make forgery attacks.

However this actually trivial problem was looong addressed, got re-introduced and now re-solved by the community.

Taking the most attacked curve for example, curve25519 It has(?) a cofactor of 8 for the reason given in Theorem 2.1 in the paper.

In Section 3 we have:

If the subgroup of $E(F_{p^2})$ generated by the base point $(9; …)$ has non-prime order then the attacker can use the Pohlig-Hellman method to save time in computing discrete logarithms.”

There you are, 2005 and one of the most trivial criteria in the history of cryptography satisfied, PRIME ORDER. This “malleability” hack that super-smart people noticed could have been avoided if people would read and understand the security analysis section. Of course in reality this section was not just simply overlooked (i hope?) but misunderstood. In Menezes’ paper we see that if we keep this cofactor small then the situation is not that bad. But this only applies to the small-subgroup attack not the invalid-curve/k-torsion or kangaroo one, which has been addressed by Bernstein’s paper.

Social media scientists got too much into discussing how using small cofactors introduce malleability into a scheme and seemingly, in 2019 still nobody considers why we use the freakin` cofactors in the first place.

As I always say, the UX vs security is an eternal war and our work is to have a healthy balance between the two. I am rather fond of having OTP keys in my wallet and make my life as hard as I can to have my privacy, but this whole “extending elliptic curves to have a small cofactor” was a childish and trivial move, driven by “premature optimization” and now the blame has been put to cryptographers.

Don’t get me wrong, I DO support the Decaf method and ristretto groups because I want robust and secure libraries in the industry, I’ll have it “your way” and happily introduce some overhead because someone didn’t implement an algorithm according to the specs :) Decaf showed us a general methodology to compress edwards and montgomery curve points well, and is still a major academic contribution that I am happy and thankful for.