so as for why the PuTTY P-521 bug happened: they wrote the implementation in September 2001, which is a month before Windows XP was released. Win9x had no good random number generator APIs, so they came up with an alternative trick using SHA512 to generate deterministic but non-predictable nonces. but, of course, SHA512 outputs are 512 bits long, not 521 bits, and they just left the other 9 bits at zero, which resulted in this problem. the code was not reviewed since, so it never got fixed.
without digging into the full details of how the determinism stuff interplays with the protocol stack, their solution actually might have worked out ok if they had generated a second hash to fill the last 9 bits.
if they had happened to write this implementation just a month or two later, they could've written it to use CryptGenRandom on XP or later, and fallen back to the deterministic approach on Win9x, and this bug would've been avoided.
@foone yup. and after thinking about it, their weird deterministic solution definitely would've worked if they had extended the hash to the full 521 bits, since it doesn't count as nonce reuse if it's the exact same message and key (you're basically just doing the same computation again, so the result is no different). such a tiny oversight - nine bits! but unfortunately with ECDSA any bias in k is catastrophic.
@gsuberland@foone This is one of the things I like about curve25519.
It's deterministic but all the design work is done for you so there's no need to provide any randomness or design your own hash or whatever. They went out of their way to avoid footguns.
@gsuberland@foone As a non-cryptographer, I always reach for curve25519 + AES-GCM because this pairing seems to be the hardest to make catastrophic mistakes with.
after thinking about this some more: yeah, if they had extended the hash (e.g. second SHA512 call with some constant appended to the input) to fill out the other 9 bits, it would've been absolutely fine. the signature determinism isn't a problem because it only occurs with the exact same key and message, so you're just redoing the same maths.
slight correction: they wrote the DSA implementation in 2001, then reused it for ECDSA about 15 years later (so about 7 years ago), but missed that the 512<521 discrepancy is a critical problem for ECDSA whereas with DSA it didn't really matter. so it's the same deal but just a slightly different timeline.