# Technical details of attack on Android bitcoin usage of SecureRandom

Reports are surfacing that Android's Java SecureRandom class has issues and isn't totally secure.

A specific example of how this issue translates to applications is bitcoin, where reports are stating that the bitcoin wallet is at risk of theft. With bitcoin specifically, the reports say that "colliding R values" can result.

• Why did SecureRandom fail to output secure pseudorandom bits?
• What exactly are "colliding R values", why is that a problem, and how can it be resolved?
-

It looks like there are really two potential problems. From the mailing list

all private keys generated on Android phones/tablets are weak and some signatures have been observed to have colliding R values, allowing the private key to be solved and money to be stolen.

Recall that with bitcoin

Transactions are cryptographically signed records that reassign ownership of Bitcoins to new addresses. Transactions have inputs - records which reference the funds from other previous transactions - and outputs - records which determine the new owner of the transferred Bitcoins, and which will be referenced as inputs in future transactions as those funds are respent.

Each input must have a cryptographic digital signature that unlocks the funds from the prior transaction. Only the person possessing the appropriate private key is able to create a satisfactory signature; this in effect ensures that funds can only be spent by their owners.

So, first, if all private keys generated on an Android device are weak, anyone could (potentially) figure out your private key and basically transfer the money in your wallet to themselves. Weak private keys would be the result of the RNG not being very random in practice so there is only a small pool of random numbers being used to generate the private key (e.g., in the debian openssl key generation bug, there were some 65k private RSA keys being used due to a poor RNG, that is small enough to be enumerable).

Now, specifically on to what you asked about colliding R values. Bitcoin uses ECDSA for signing. For my description below, I'll use non-EC DSA to describe the problem for simplicity.

In DSA, the private key is a randomly generated value $x$ and the public key consists of $(p,q,g,y)$. For details on $p$, $q$ and $g$ see Parameter Generation. $y$ is computed as $y=g^x\bmod{p}$.

To compute a signature of a message $m$, we compute:
$r=(g^k\bmod{p})\bmod{q}$ (where $k$ is a randomly chosen value)
$s=k^{-1}(H(m)+xr)\bmod{q}$ (where $H$ is a hash function)

The signature is then $(r,s)$. I'm assuming that it this $r$ that they are saying is colliding. This could happen if the RNG is weak and you generate the same $k$ twice.

So, the question then is why would colliding $r$ values cause a problem. As I said, a colliding $r$ comes from generating the same value $k$ twice. I found the following note on wikipedia interesting:

With DSA, the entropy, secrecy, and uniqueness of the random signature value k is critical. It is so critical that violating any one of those three requirements can reveal the entire private key to an attacker. Using the same value twice (even while keeping k secret), using a predictable value, or leaking even a few bits of k in each of several signatures, is enough to break DSA.

In December 2010, a group calling itself fail0verflow announced recovery of the ECDSA private key used by Sony to sign software for the PlayStation 3 game console. The attack was made possible because Sony failed to generate a new random k for each signature.

This works as follows (adapted from here)

Say you have two signatures with colliding $r$ values. Call them $(r,s_1)$ and $(r,s_2)$.

Compute: $s_1-s_2=k^{-1}(H(m_1)+xr)-k^{-1}(H(m_2)+xr)$
Redistribute: $s_1-s_2=k^{-1}(H(m_1)-H(m_2)+xr-xr)=k^{-1}(H(m_1)-H(m_2))$
Thus: $k=(H(m_1)-H(m_2))/(s_1-s_2)$, so you know $k$.
Then you compute the private key $x$ as $x=((s\cdot k)-H(m))\cdot r^{-1}\bmod{q}$ using one of the signatures.

So, even if your private key is not weak (say you generated it on another machine then moved it to the android device), signing two transactions with the same $k$ allows someone to discover your private key.

Recommendation for resolving the problem
The bitcoin folks are recommending that bitcoin software developers switch to /dev/urandom, then in their apps have all users generate a new private key, and transfer all bitcoins to the new private key.

Note
The problem only seems to affect Android's SecureRandom class. Presumably Google could fix SecureRandom, in which case Android devices could switch back to using SecureRandom (instead of /dev/urandom). Private keys would still need to be regenerated.

Why SecureRandom Fails
The details of why SecureRandom fails to generate good random numbers were presented at RSA-CT 2013 in this paper. The problem happens when creating a self seeding instance of SecureRandom (i.e., no seed, either through the constructor or through setSeed method, is passed by the programmer). The seed is stored in a buffer with the seed data, a counter, and padding. In the case where no seed is passed by the programmer, a bug in the code caused a pointer into the buffer to not be updated, which causes other code to overwrite portions of the seed. This data should be appended to the seed instead. See Figure 4 of the linked paper.

The result is that there is only 64 bits of entropy in the buffer. This is much, much too low.

-
Interestingly, self-seeding of SecureRandom is typically the recommended practice as we expect SecureRandom to self seed properly but don't expect a programmer to seed it properly. –  mikeazo Aug 13 '13 at 12:49