Reused R values again

[johoe]

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 k₁, k₂ in two different signatures have a known linear relationship k₂ = ak₁ + b with a, b ∈ Z, the private key d can be extracted from the two signatures without the knowledge of the values k₁, k₂, since it results in two linear equations with only d and k₁ 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₂ can be found adding G to R₁ 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.

[Supercomputing]

https://www2.informatik.hu-berlin.de/~verbuech/klepto-ecdsa/

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 k₁, k₂ in two different signatures have a known linear relationship k₂ = ak₁ + b with a, b ∈ Z, the private key d can be extracted from the two signatures without the knowledge of the values k₁, k₂, since it results in two linear equations with only d and k₁ 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₂ can be found adding G to R₁ 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.

That is what I was talking about all the day, they don't have to be identical at all and that why nobody will realise about the "bug" except the developer who introduced it.

Yes, I agree with you to a certain extent if the developer kept the application as closed source. However, in this case, it appears to be an honest mistake.

Please see:
https://github.com/blockchain/My-Wallet/commit/98d5a7ca59ef04d06ac6aee468634b12975a0f5c

[justusranvier]

For code to have been released into production with such a mistake is *clearly incompetence* and I am not talking about the particular dev (everyone makes mistakes) but by the organisation itself (where was the code review?).

I would not be surprised to learn that one person at BCI still works the same way he did back when the service launched and just pushes changes he makes directly to production servers with no review or testing.

[justusranvier]

This information is public from 2010, since the Sony PlayStation fiasco where they used R=4 to sign *all* the games in their online store.

It was known right from the beginning, when ElGamal published his signature scheme, on which Schnorr signatures are based, on which classical DSA is based, on which ECDSA is based.


From his 1985 paper:

Note 2: If any k is used twice in the signing, then the system of equations is uniquely determined and x can be recovered. So for the system to be secure, any value of k should never be used twice.

And should have been obvious to anyone who has implemented the cryptosystem too,  if k didn't have to be secret/unique you could just make it a parameter of the system and eliminate r and halve the size of the signatures.

I bet there would have been fewer of these errors over the years if k had a more informative name from the beginning. Maybe something like "ephemeral private key" to automatically make people notice that generating k randomly is as important as generating private keys randomly.

[amaclin]

Yes, I agree with you to a certain extent if the developer kept the application as closed source. However, in this case, it appears to be an honest mistake.

Please see:
https://github.com/blockchain/My-Wallet/commit/98d5a7ca59ef04d06ac6aee468634b12975a0f5c

bc.i had two updates on December,8
First one they published bug, few hours later they fixed it
github.com has only one commit - fixing unknown bug

[gmaxwell]

because every commit to the code is tracked on the GitHub

BC.i sometimes uses forced pushes which conceal the prior revisions.

[Supercomputing]

Yes, I agree with you to a certain extent if the developer kept the application as closed source. However, in this case, it appears to be an honest mistake.

Please see:
https://github.com/blockchain/My-Wallet/commit/98d5a7ca59ef04d06ac6aee468634b12975a0f5c

bc.i had two updates on December,8
First one they published bug, few hours later they fixed it
github.com has only one commit - fixing unknown bug

I was just able to reproduce the bug from the GitHub info:

If you comment out line 29, your PRNG backend will not be initialized correctly
// Random number generator - requires a PRNG backend, e.g. prng4.js
// Initialize arcfour context from key, an array of ints, each from [0..255]
function ARC4init(key) {

Private Key:
20024245551370964114963921214810962636924048065379939224750754889731391894624(DEC)
953251A6CBDFCB91E38B958AB2B5013A503130194D8AA26083F7664E84FDFE49 (HEX)
5JwzcBP4uE5miuJW4tweMbFCz85pWmvXM7e2n6kSG8j9jwKFdTj (WIF)

Edit: Their quality assurance team should have caught this bug if the code was reviewed. It's too obvious.
1Mi8X7NHHYEQR95EnvQSciJ3ChCimt65SK (Bitcoin Address)

[amaclin]

I was just able to reproduce the bug from the GitHub info:

Tomorrow we will see a dozen of flaw RNG searching for weak keys  

[itod]

Yes, I agree with you to a certain extent if the developer kept the application as closed source. However, in this case, it appears to be an honest mistake.

Please see:
https://github.com/blockchain/My-Wallet/commit/98d5a7ca59ef04d06ac6aee468634b12975a0f5c

bc.i had two updates on December,8
First one they published bug, few hours later they fixed it
github.com has only one commit - fixing unknown bug

I was just able to reproduce the bug from the GitHub info:

If you comment out line 29, your PRNG backend will not be initialized correctly
// Random number generator - requires a PRNG backend, e.g. prng4.js
// Initialize arcfour context from key, an array of ints, each from [0..255]
function ARC4init(key) {

Private Key:
20024245551370964114963921214810962636924048065379939224750754889731391894624(DEC)
953251A6CBDFCB91E38B958AB2B5013A503130194D8AA26083F7664E84FDFE49 (HEX)
5JwzcBP4uE5miuJW4tweMbFCz85pWmvXM7e2n6kSG8j9jwKFdTj (WIF)

Edit: Their quality assurance team should have caught this bug if the code was reviewed. It's too obvious.
1Mi8X7NHHYEQR95EnvQSciJ3ChCimt65SK (Bitcoin Address)

This seems to be recovery address from the disaster, 914 BTC total, they've been slowly returning funds to users:
https://blockchain.info/address/1PLn3ru1n7wERPP1BLVV9oAEGGuXUP1eoC

Does this mean the problem was not limited to the reused R values, all transfers were compromised during the few hours while the bug was not discovered? If I understood you correctly, if you seed the RNG with time-stamps from that short period you bump into the transactions which haven't had reused R values, that's how you got this private key?

[gmaxwell]

Does this mean the problem was not limited to the reused R values, all transfers were compromised during the few hours while the bug was not discovered? If I understood you correctly, if you seed the RNG with time-stamps from that short period you bump into the transactions which haven't had reused R values, that's how you got this private key?

Also new wallets created.  And "this time period" is somewhat ambiguous due to caching. For all I know there is some browser tab up someplace running this code that could generate an address and and receive 1000 BTC at any moment.

[MrGreenHat]

Does this mean the problem was not limited to the reused R values, all transfers were compromised during the few hours while the bug was not discovered? If I understood you correctly, if you seed the RNG with time-stamps from that short period you bump into the transactions which haven't had reused R values, that's how you got this private key?

Also new wallets created.  And "this time period" is somewhat ambiguous due to caching. For all I know there is some browser tab up someplace running this code that could generate an address and and receive 1000 BTC at any moment.

Well, that's not absolutely horrifying, is it? damn.

[goosoodude]

Does this mean the problem was not limited to the reused R values, all transfers were compromised during the few hours while the bug was not discovered? If I understood you correctly, if you seed the RNG with time-stamps from that short period you bump into the transactions which haven't had reused R values, that's how you got this private key?

Also new wallets created.  And "this time period" is somewhat ambiguous due to caching. For all I know there is some browser tab up someplace running this code that could generate an address and and receive 1000 BTC at any moment.

That sounds bad. Blockchain.info should put a general warning on their page to clear the cache. Till now there has been no warning at all, they are trying to hide their incompetence.

[johoe]

There have been again some bad transactions this night, including this big one from bitcoin gambling guide:
https://blockchain.info/tx/6bde86ea2a9892d955443d2bf3d716fa2c0c8947e2cddcc54e2a61930405f3df

The other exposed addresses are 12bGnGuxW6LRyCE8peAYnAFxS7fzVnSALZ, 1BCzSb27A3Ky8HuLNeAE9L17EVjXvo66z
and 1ALzByRJDvFH18CSVZ3YsTdGUkg8fmD5Fw

I uploaded a list of public keys (in compressed hex format).  To get a list of weak R values just remove the 02/03 from the beginning of the line.  I leave it up to you to compute a list of weak addresses from it.

I found out, yesterday that it is possible to compute the private keys from this list alone without breaking the RNG but it is probably more difficult than just breaking the RNG  Using the same trick, I think I found a way to compute this list 30 times faster if I need to do that again.


Edit: This transaction looks suspicious
https://blockchain.info/tx/45615ef3bba30a29561249a581e59b6e2b44e7612219735a1afdf3f76dbff849
I think others know how to break the RNG.

Edit2: I just tried my download link and noticed that it downloads a Download.exe.  Is this site (sendspace) safe  to use?  I disabled the link for now.
Edit3: I changed the download link to solidfiles.com.

[stv]

http://programmers.stackexchange.com/questions/147134/how-should-i-test-randomness

Does not help against the attack from here, because the manipulated random numbers are provably indistinguishable, but it would have prevented the ridiculous bug in MyWallet.

[stv]

https://www2.informatik.hu-berlin.de/~verbuech/klepto-ecdsa/

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 k₁, k₂ in two different signatures have a known linear relationship k₂ = ak₁ + b with a, b ∈ Z, the private key d can be extracted from the two signatures without the knowledge of the values k₁, k₂, since it results in two linear equations with only d and k₁ 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₂ can be found adding G to R₁ 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.

It doesn't have too much to do with closeness. There is a linear relationship between any pair of two numbers in the “Z_n” (with n from Bitcoin's secp256k1 curve). The question is whether you know it. Easier “k” is much easier to break, because it results in identical “r” appearing in the blockchain. Anybody can detect them immediately. But for an evil programmer who manipulates the generation of “k”, there is much more potential to leak values, without having obvious appearances in the blockchain.

[bcearl]

Are they still not using deterministic “k” by now? Even a simple k = H(m||secretkey) would be better than any home-baked RNG that is considering Date().getTime().

Can some JS pro tell me what Browsers still don't provide good entropy from the operating system and why users should generate keys on them?

[Billyboy402]

with all this talk can  please have a noob friendly opinion

would green address it be a safer option ? or breadwallet for IOS ?
i want to keep a small wallet with $20 so i can buy beer and show my mates 

[LFC_Bitcoin]

When can we assume bc.i have sorted this fuck up out?

[CIYAM]

When can we assume bc.i have sorted this fuck up out?

They have already fixed the code - the main issue now is that people have not "refreshed their browser pages" who were using the buggy code (and of course the funds that have not been swept from the compromised keys) and people still using compromised addresses (I am assuming that blockchain.info would have sent all affected users an email - but not all may have received that email or acted on it).

[amaclin]

When can we assume bc.i have sorted this fuck up out?

Private keys are already compromised.
bc.i can not do anything with it now. They even can not determine who moves funds out "owner" or "hacker"
In fact they also can sweep funds.