Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

This is probably the cryptography bug of the year. It's easy to exploit and bypasses signature verification on anything using ECDSA in Java, including SAML and JWT (if you're using ECDSA in either).

The bug is simple: like a lot of number-theoretic asymmetric cryptography, the core of ECDSA is algebra on large numbers modulo some prime. Algebra in this setting works for the most part like the algebra you learned in 9th grade; in particular, zero times any algebraic expression is zero. An ECDSA signature is a pair of large numbers (r, s) (r is the x-coordinate of a randomly selected curve point based on the infamous ECDSA nonce; s is the signature proof that combines x, the hash of the message, and the secret key). The bug is that Java 15+ ECDSA accepts (0, 0).

For the same bug in a simpler setting, just consider finite field Diffie Hellman, where we agree on a generator G and a prime P, Alice's secret key is `a mod P` and her public key is `G^a mod P`; I do the same with B. Our shared secret is `A^b mod P` or `B^a mod P`. If Alice (or a MITM) sends 0 (or 0 mod P) in place of A, then they know what the result is regardless of anything else: it's zero. The same bug recurs in SRP (which is sort of a flavor of DH) and protocols like it (but much worse, because Alice is proving that she knows a key and has an incentive to send zero).

The math in ECDSA is more convoluted but not much more; the kernel of ECDSA signature verification is extracting the `r` embedded into `s` and comparing it to the presented `r`; if `r` and `s` are both zero, that comparison will always pass.

It is much easier to mess up asymmetric cryptography than it is to mess up most conventional symmetric cryptography, which is a reason to avoid asymmetric cryptography when you don't absolutely need it. This is a devastating bug that probably affects a lot of different stuff. Thoughts and prayers to the Java ecosystem!



Interestingly, EdDSA (generally known as Ed25519) does not need as many checks as ECDSA, and assuming the public key is valid, an all-zero signature will be rejected with the main checks. All you need to do is verify the following equation:

R = SB - Hash(R || A || M) A

Where R and S are the two halves of the signature, A is the public key, and M is the message (and B is the curve's base point). If the signature is zero, the equation reduces to Hash(R || A || M)A = 0, which is always false with a legitimate public key.

And indeed, TweetNaCl does not explicitly check that the signature is not zero. It doesn't need to.

However.

There are still ways to be clever and shoot ourselves in the foot. In particular, there's the temptation to convert the Edwards point to Montgomery, perform the scalar multiplication there, then convert back (doubles the code's speed compared to a naive ladder). Unfortunately, doing that introduces edge cases that weren't there before, that cause the point we get back to be invalid. So invalid in fact that adding it to another point gives us zero half the time or so, causing the verification to succeed even though it should have failed!

(Pro tip: don't bother with that conversion, variable time double scalarmult https://loup-vaillant.fr/tutorials/fast-scalarmult is even faster.)

A pretty subtle error, though with eerily similar consequences. It looked like a beginner-nuclear-boyscout error, but my only negligence there was messing with maths I only partially understood. (A pretty big no-no, but I have learned my lesson since.)

Now if someone could contact the Whycheproof team and get them to fix their front page so people know they have EdDSA test vectors, that would be great. https://github.com/google/wycheproof/pull/79 If I had known about those, the whole debacle could have been avoided. Heck, I bet my hat their ECDSA test vectors could have avoided the present Java vulnerability. They need to be advertised better.


> Thoughts and prayers to the Java ecosystem!

some very popular PKI systems (many CA's) are powered by Java and BouncyCastle ...


BouncyCastle has its own implementation of ECDSA, and it’s not vulnerable to this bug.


>infamous ECDSA nonce

Why "infamous"?


It's more properly called 'k'. It's really a secret key, but it has to be unique per-signature. If an attacker can ever guess a single bit of the nonce with probability non-negligibly >50%, they can find the private key of whoever signed the message(s).

It makes ECDSA very brittle, and quite prone to side-channel attacks (since those can get attackers exactly such information.


There's an easy fix for that though -- generate k deterministically using the procedure in RFC6979 [1].

[1] https://datatracker.ietf.org/doc/html/rfc6979#section-3.2


> If an attacker can ever guess a single bit of the nonce with probability non-negligibly >50%, they can find the private key of whoever signed the message(s).

This doesn’t seem right. Why wouldn’t someone guess a bit 0, see if the recovered message makes sense, and if it doesn’t, then try bit 1?

It would make the entire scheme useless no? Am I missing something?


I think they have to get the bit repeatedly and then combine the biased signatures together mathematically to get the key.


That makes no sense, how can you get the private key from knowing 1 bit of the nonce?


See, cryptography engineering is sinking in!

Here you go:

https://toadstyle.org/cryptopals/62.txt

What's especially great about this is that it's very easy to accidentally have a biased nonce; in most other areas of cryptography, all you care about when generating random parameters is that they be sufficiently (ie, "128 bit security worth") random. But with ECDSA, you need the entire domain of the k value to be random.


Ok but for this scheme you need a large amount of signatures from the same biased RNG which makes sense. I thought that the GP was suggesting that you can recover the key from one signature with just a few bits.


"same biased RNG" largely reduces to "I use the same computer to generate all my signatures"; for example see the Debian RNG bug from 2008

and "large amount of signatures" could be "I sign every email I send to a mailing list" or "I use this key to sign some widely distributed software every two weeks"


When these bugs first came into fashion, the "bias" of the RNG was an implementation artifact, not some bug in /dev/random: it was the code you used to fill a bignum uniformly in the size of the nonce. So mentally substitute "same biased RNG" for "same implementation, with same keys".

Yes, the attacks require many signatures. Like the infamous Bleichenbacher RSA attack, which was originally dubbed "The Million Message Attack", in part as a jab at how impractical they were presumed to be, collecting thousands of signatures is often a very realistic attack; for instance, any system that generates signed messages automatically.


I guess like so:

https://cryptopals.com/sets/8/challenges/62.txt

E: Thomas beat me to it


I'm not particularly knowledgeable here, but I know it's extremely fragile, far beyond just needing to be unique. See "LadderLeak: Breaking ECDSA With Less Than One Bit of Nonce Leakage"


Thank you for that, that was a great explanation.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: