Android RNG Weakness Renders Bitcoin Wallets Insecure

discussion on bitcointalk.org: https://bitcointalk.org/index.php?topic=271486.0

blogpost about weakness in java.security.SecureRandom: http://armoredbarista.blogspot.com.au/2013/03/randomly-faile...

Does it concerns only Bitcoin wallets? What about other encryption under Android - like files, etc?

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ä!

I don't think it's a very big deal.

For the most part, people who use bitcoin now are still very early adopters and are techies.

Also, IMHO, it would be idiotic to have significant bitcoin value stored on an Android phone, and very few people (if anyone) would do that.

People are saying it's a problem with Android's SecureRandom implementation. That would be a pretty big problem if it returns repeated random numbers.

But it seems strange that such a large obvious problem would make it into Android. The other explanation is that Android bitcoin developers are all implementing it incorrectly and either don't realize it or are trying to push the blame somewhere else.