about the cryptopocalypse

Last weekend, Bitcoin reported that several Android-based wallets were insecure and that bitcoin were stolen from them - all because the individual transactions (authenticated by a ECDSA signature) used a poor source of randomness. When you use a poor source of randomness in a DSA (or ECDSA) signature, you may reuse one of the values in the signature, the k value. Reusing k can expose the private key - something Sony knows well, as it was the flaw that exposed a private key in the PS3.

But the Bitcoin apps used SecureRandom, which as the name implies is actually supposed to be cryptographically secure. On Android, it's the recommended, "cryptographically secure" library... and it wasn't secure. And the results have been as catastrophic as they can be - long term private keys have been recovered. Why? Mathematically speaking, we understand why - but why do we rely on DSA, when it has this horrendous property? We know that random number generators will fail. Whether it's this instance, Mining Your P's and Q's, or Debian's openssl bug - even in seemingly highly secure or reliable instances... we still shouldn't trust the random number generator fully. While every algorithm requires strong randomness for key generation, only DSA requires strong randomness for every signature - RSA does not. It's time to stop letting DSA hold a gun to our heads.

Fortunately, we have a solution, and it doesn't necessarily require moving to another algorithm. We can incrementally fix DSA. The k value doesn't necessarily have to be random - it just must be unique and secret. RFC 6979 is a mechanism to generate a unique number based off the key and message, to ensure it's not reused. Dubbed "deterministic DSA" - you can generate signatures with this technique that are completely compatible with any DSA signature-checking implementation. With all the problems DSA has given us, deterministic DSA (or another scheme that does not rely on randomness for every single signature) really needs to be the standard way of generating signatures...

http://ritter.vg/blog-cryptopocalypse_followup.html