Interesting observation from that paper I don't remember ever seeing before:
Another slightly related security issue also arose from the fact that k has to be chosen by the signature algorithm. If two values k1, k2 in two different signatures have a known linear relationship k2 = ak1 + b with a, b ∈ Z, the private key d can be extracted from the two signatures without the knowledge of the values k1, k2, since it results in two linear equations with only d and k1 unknown.
It means that two R values don't have to be identical (reused) for their private keys to be breakable, it's enough for them to be "close" to each other, so that R
2 can be found adding G to R
1 relatively small number of times, few million for instance so it would be implementable in practice to check the neighborhood of every R value ever used against the complete set of R's. I know that two R values in theory should not ever be close to each other if RNG is decent, but we see in practice that not only they are close but often identical.
This is true but in the bc.i case it should not help. The R values produced by them are quite different. Although some are produced from similar k values, e.g. one byte shifted in the random number stream. But related R values are hard to find in this huge block chain database.
This observation also holds for related keys. Usually, two signatures with identical R value and different keys are not breakable. But if you know how the keys are related (e.g. they are generated from the same BIP32 master key and you know the master public key), then you can break them.
Okay, I think everything is clean now. I also scanned the weak addreses the broken RNG would usually produce and they are empty now. Some addresses were already swiped by blockchain.info. Looks like they used the weak-key generator I sent them today. This also means that users having a weak address in their Blockchain wallet should see a warning when they log into it the next time. With weak address I mean an address that was newly created by the buggy version of the Blockchain wallet.