Android RNG Weakness Renders Bitcoin Wallets Insecure
Iä! Digital Signature Algorithm! The Black Goat of the Woods with a Thousand Crypto Bugs!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: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).To sign, you generate a random k value, which must never be reused, Iä! Iä! never, and:    r = g^k % p % q
    s = k^-1 (H(m) + x•r) % q

The signature is (r, s).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):        H(m1) - H(m2)
    k = -------------
           S1 - S2

    x = ((S1•k) – H(m1))• r^-1 % q

This bug (also in an ECDSA implementation) is what broke the Playstation 3, too.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ä!