johoe (OP)
|
|
December 16, 2014, 08:16:08 PM |
|
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.
|
Donations to 1CF62UFWXiKqFUmgQMUby9DpEW5LXjypU3
|
|
|
Supercomputing
|
|
December 16, 2014, 08:25:22 PM |
|
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. 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
Legendary
Offline
Activity: 1400
Merit: 1013
|
|
December 16, 2014, 08:32:17 PM |
|
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
Legendary
Offline
Activity: 1400
Merit: 1013
|
|
December 16, 2014, 08:38:17 PM |
|
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
Legendary
Offline
Activity: 1260
Merit: 1019
|
|
December 16, 2014, 08:38:41 PM |
|
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
Moderator
Legendary
Offline
Activity: 4242
Merit: 8702
|
|
December 16, 2014, 08:44:01 PM |
|
because every commit to the code is tracked on the GitHub
BC.i sometimes uses forced pushes which conceal the prior revisions.
|
|
|
|
Supercomputing
|
|
December 16, 2014, 09:02:40 PM Last edit: December 16, 2014, 09:16:43 PM by Supercomputing |
|
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
Legendary
Offline
Activity: 1260
Merit: 1019
|
|
December 16, 2014, 09:24:06 PM |
|
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
Legendary
Offline
Activity: 1974
Merit: 1077
^ Will code for Bitcoins
|
|
December 16, 2014, 10:58:20 PM |
|
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/1PLn3ru1n7wERPP1BLVV9oAEGGuXUP1eoCDoes 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
Moderator
Legendary
Offline
Activity: 4242
Merit: 8702
|
|
December 17, 2014, 12:40:55 AM |
|
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
|
|
December 17, 2014, 02:17:19 AM |
|
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
|
|
December 17, 2014, 06:56:59 AM |
|
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 (OP)
|
|
December 17, 2014, 10:18:44 AM Last edit: December 17, 2014, 12:36:28 PM by johoe |
|
There have been again some bad transactions this night, including this big one from bitcoin gambling guide: https://blockchain.info/tx/6bde86ea2a9892d955443d2bf3d716fa2c0c8947e2cddcc54e2a61930405f3dfThe 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/45615ef3bba30a29561249a581e59b6e2b44e7612219735a1afdf3f76dbff849I 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.
|
Donations to 1CF62UFWXiKqFUmgQMUby9DpEW5LXjypU3
|
|
|
stv
Newbie
Offline
Activity: 27
Merit: 0
|
|
December 17, 2014, 10:25:14 AM |
|
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
Newbie
Offline
Activity: 27
Merit: 0
|
|
December 17, 2014, 10:32:10 AM |
|
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. 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
|
|
December 17, 2014, 12:26:29 PM |
|
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?
|
Misspelling protects against dictionary attacks NOT
|
|
|
Billyboy402
|
|
December 17, 2014, 12:51:29 PM |
|
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
|
THIS ACCOUNT WAS HACK > SORRY FOR ANY ONE THAT HAS DEALT WITH THIS ACCOUNT.
|
|
|
LFC_Bitcoin
Legendary
Offline
Activity: 3668
Merit: 10272
#1 VIP Crypto Casino
|
|
December 17, 2014, 02:15:53 PM |
|
When can we assume bc.i have sorted this fuck up out?
|
|
|
|
CIYAM
Legendary
Offline
Activity: 1890
Merit: 1086
Ian Knowles - CIYAM Lead Developer
|
|
December 17, 2014, 02:17:35 PM Last edit: December 17, 2014, 02:28:26 PM by 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
Legendary
Offline
Activity: 1260
Merit: 1019
|
|
December 17, 2014, 02:24:41 PM |
|
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.
|
|
|
|
|