This is very well written. Listing the different but similar examples of hash breaking, and then highlighting the specific caveat, made the point crystal clear.
There are indeed valid reasons to use 512-bit hashes even if you think 256-bits are plenty:
EdDSA take advantage of the bigger hash to remove bias from the modulo L operation, and to separate a 512-bit hash into two independent numbers (one to feed the nonce, one to make the public key).
My own Monokex protocol suite uses 512-bit hashes because Monocypher uses Blake2b to begin with. Earlier versions even cut the hash in two instead of using HKDF.
In general, 512-bits hashes have designs that run faster on modern 64-bit CPUs. There is often little point in cutting down the size of the digest, even though the hash was chosen for its speed to begin with.
That said, if you’re using 512 bit hashes for security reasons, then you should also switch to bigger curves like Curve448. Otherwise the cryptanalist will just attack the curve, which now has become the weakest link.
The thing is, signature schemes like ECDSA and EdDSA (of which Ed25519 is an instantiation) require some random nonce at some point. That nonce must be between 0 and the order of the curve L, without any bias. If the attacker can detect even a slight bias in the way this number is generated, they can exploit it and recover the private key. The absolute worst bias is outright reusing the nonce, and that reveals your private key instantly. That’s how Sony lost its own PS3 master keys.
Bias is pretty bad.
Now you can’t just truncate down to |L| bits, because you’d overflow some of the time, and that introduces the dreaded bias. The obvious defence would be to test whether your random number exceeds L, then reject it and try again if it isn’t. Problem is, that’s not constant time, and now you have to worry about possible flows of information from secrets to timings. Workable, but not great.
Ed25519 has two cleverer defenses:
The order of the curve L is very very close to 2^252. So much so that numbers above 2^252 don’t even come up in random tests, or even in Google’s Wycheproof test vectors. If you just truncated your random number down to 252 bits, the bias would likely not even be noticeable.
Since this defence is specific to Curve25519, EdDSA also take the precaution of computing the modulo of a ludicrously large hash (512 bits), so that even if the bias of a crude modulo would have been noticeable, it is no longer. The likelihood of picking up the largest group of number (the one between L^something and 2^512) is so overwhelmingly low that it can be considered flat out impossible.
Oh, and EdDSA has a third precaution, which is to generate the random nonce deterministically, from the message and the private key. That way you can’t misuse the API and reuse a nonce like Sony did. That said, nothing prevents some clever fool from picking a random number by themselves. I personally would never write such an API (there are safer ways to get the same advantages), but some do take this approach.
I see now. I was under the mistaken impression that |L| all-1 bits fit in L (as a number), but that obviously makes no sense unless L itself is all-1s, which it isn’t. I didn’t realize it would overflow, my bad.
(Simple example for those still confused: Take L = 10, which is 0b1010. If you take the first 4 bits from a hash that starts with 0xff..., you’d take 0b1111. But 0b1111 > 0b1010, so it wouldn’t actually fit.)
To expand on your example, we could avoid overflow by taking the first 3 bits instead. That way you never exceed 10. The problem is that you’ll never select 8 or 9 that way, and that kind of bias can be exploited.
Similarly, you can take 4 bits, and do the modulo 10 to avoid overflow. But then numbers from 0 to 5 are selected twice as often as the numbers from 6 to 9.
Or you can take 8 bits before you take the modulo. Now numbers from 0 to 5 are selected 26 times, out of 51, and numbers from 6 to 9 are selected 25 times out of 51. Now the bias is much smaller, and possibly not as exploitable, if at all.
This is very well written. Listing the different but similar examples of hash breaking, and then highlighting the specific caveat, made the point crystal clear.
Nice article, I still think that if you can use 256 or even 512 bits without deteriorating the service in question, I’d personally go for that.
There are indeed valid reasons to use 512-bit hashes even if you think 256-bits are plenty:
That said, if you’re using 512 bit hashes for security reasons, then you should also switch to bigger curves like Curve448. Otherwise the cryptanalist will just attack the curve, which now has become the weakest link.
Why not just truncate the hash to |L| bits?
Noooo, you will break everything!
The thing is, signature schemes like ECDSA and EdDSA (of which Ed25519 is an instantiation) require some random nonce at some point. That nonce must be between 0 and the order of the curve L, without any bias. If the attacker can detect even a slight bias in the way this number is generated, they can exploit it and recover the private key. The absolute worst bias is outright reusing the nonce, and that reveals your private key instantly. That’s how Sony lost its own PS3 master keys.
Bias is pretty bad.
Now you can’t just truncate down to |L| bits, because you’d overflow some of the time, and that introduces the dreaded bias. The obvious defence would be to test whether your random number exceeds L, then reject it and try again if it isn’t. Problem is, that’s not constant time, and now you have to worry about possible flows of information from secrets to timings. Workable, but not great.
Ed25519 has two cleverer defenses:
The order of the curve L is very very close to 2^252. So much so that numbers above 2^252 don’t even come up in random tests, or even in Google’s Wycheproof test vectors. If you just truncated your random number down to 252 bits, the bias would likely not even be noticeable.
Since this defence is specific to Curve25519, EdDSA also take the precaution of computing the modulo of a ludicrously large hash (512 bits), so that even if the bias of a crude modulo would have been noticeable, it is no longer. The likelihood of picking up the largest group of number (the one between L^something and 2^512) is so overwhelmingly low that it can be considered flat out impossible.
Oh, and EdDSA has a third precaution, which is to generate the random nonce deterministically, from the message and the private key. That way you can’t misuse the API and reuse a nonce like Sony did. That said, nothing prevents some clever fool from picking a random number by themselves. I personally would never write such an API (there are safer ways to get the same advantages), but some do take this approach.
I see now. I was under the mistaken impression that |L| all-1 bits fit in L (as a number), but that obviously makes no sense unless L itself is all-1s, which it isn’t. I didn’t realize it would overflow, my bad.
(Simple example for those still confused: Take
L = 10, which is0b1010. If you take the first 4 bits from a hash that starts with0xff..., you’d take0b1111. But0b1111>0b1010, so it wouldn’t actually fit.)To expand on your example, we could avoid overflow by taking the first 3 bits instead. That way you never exceed 10. The problem is that you’ll never select 8 or 9 that way, and that kind of bias can be exploited.
Similarly, you can take 4 bits, and do the modulo 10 to avoid overflow. But then numbers from 0 to 5 are selected twice as often as the numbers from 6 to 9.
Or you can take 8 bits before you take the modulo. Now numbers from 0 to 5 are selected 26 times, out of 51, and numbers from 6 to 9 are selected 25 times out of 51. Now the bias is much smaller, and possibly not as exploitable, if at all.