Android RNG Weakness Renders Bitcoin Wallets Insecure
Iä! Digital Signature Algorithm! The Black Goat of the Woods with a Thousand Crypto Bugs!<p>I don't know the Bitcoin software involved at all, but I can sketch out an attack that might shed some light on it, and, more importantly, instill an appropriate fear of DSA into you:<p>To generate a DSA key, you come up with primes p and q and a generator g, which process is a paralytic non-Euclidian brain injury I will not attempt to describe. Then you do like Diffie Hellman: generate a random private key x and from it a public value y = g^x % p. The pubkey that validates signatures is the tuple (p, q, g, y).<p>To sign, you generate a random k value, which must never be reused, Iä! Iä! never, and:<p><pre><code>    r = g^k % p % q
    s = k^-1 (H(m) + x•r) % q
</code></pre>
The signature is (r, s).<p>If ever you should fail to heed these words and generate two signatures with the same k value, Iä Cthulhu Ftaghn! then simple high school algebra can be used to beat DSA. The attacker doesn't even need to know what the k was, and the attack is so fast you can just try it to see if k was repeated (I skipped the algebra and just dumped the formulas for the attack here):<p><pre><code>        H(m1) - H(m2)
    k = -------------
           S1 - S2

    x = ((S1•k) – H(m1))• r^-1 % q
</code></pre>
This bug (also in an ECDSA implementation) is what broke the Playstation 3, too.<p>You see that comment on the Bitcoin thread about the repeated r-values; a repeated r-value (r as in the r parameter of a DSA signature) just tells you that someone repeated a k. Iä! Iä!