Quote
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
Topic: Reused R values again - page 8. (Read 121295 times)
Tomorrow we will see a dozen of flaw RNG searching for weak keys
Quote
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
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)
because every commit to the code is tracked on the GitHub
BC.i sometimes uses forced pushes which conceal the prior revisions. Quote
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
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
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:
Quote
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.
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. Interesting observation from that paper I don't remember ever seeing before:
Quote
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 R2 can be found adding G to R1 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
Interesting observation from that paper I don't remember ever seeing before:
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 R2 can be found adding G to R1 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.
Quote
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 R2 can be found adding G to R1 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.
Interesting observation from that paper I don't remember ever seeing before:
Quote
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 R2 can be found adding G to R1 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.
Interesting observation from that paper I don't remember ever seeing before:
Quote
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 R2 can be found adding G to R1 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.
Quote
blockchain.info didn't create the transaction themselves; it was relayed to them.
Of course. Transaction generated on https://sharedcoin.com/ service
with signatures created by javascript taken from bc.i on user device
-snip-
Is sharedcoin.com operative ? As I can see, it only redirects to blockchain.info wallet page.
AFAIK, blockchain.info mixing now takes place from within the wallet.
Hello,
I'm pretty sure that the owner of 1MKSW... broke the RNG:
https://blockchain.info/tx/a66d1ed3907902660ae12f97de22276f34185ede033583545f7440e049f7be2b
The address has no spents, the public key does not match any R value, but it is a weak key (I post a list as soon as I'm done computing it).
They did not find all weak keys, yet (hopefully their brute-forcer is slower than mine
) Stupid, that I didn't remember the parity of the public key the first time I brute forced 1.5 million keys. Now I have to run it again and my ECC multiplication is so slow 
I'm pretty sure that the owner of 1MKSW... broke the RNG:
https://blockchain.info/tx/a66d1ed3907902660ae12f97de22276f34185ede033583545f7440e049f7be2b
The address has no spents, the public key does not match any R value, but it is a weak key (I post a list as soon as I'm done computing it).
They did not find all weak keys, yet (hopefully their brute-forcer is slower than mine
) Stupid, that I didn't remember the parity of the public key the first time I brute forced 1.5 million keys. Now I have to run it again and my ECC multiplication is so slow 
@johoe,
I'll send you one of my brass coins (unloaded) to you for free.
PM me or email me your shipping information and I'll send it your way.
[email protected]
thanks for being honest! It is refreshing to have that around here.
I'll send you one of my brass coins (unloaded) to you for free.
PM me or email me your shipping information and I'll send it your way.
[email protected]
thanks for being honest! It is refreshing to have that around here.
A way to dox him
I think the bug was not malicious, only incompetence. We are lucky that johoe was monitoring it.
Quote
blockchain.info didn't create the transaction themselves; it was relayed to them.
Of course. Transaction generated on https://sharedcoin.com/ service
with signatures created by javascript taken from bc.i on user device
Quote
how do you determine 1) ?
1. It is definitely deposit to BTC-e2. It is mixer transaction (I am 99% sure - all other flawed transactions have this pattern)
May be there is one more bug in bc.i scripts.
I have never heard that there is public API for sharedcoin sending.
Hmm... May be it is another mixing service, which sends transactions through bc.i pushtx form. But I doubt.
UPD:
OK... 17c7o4YTN5JwjvdLLW9JpqZFc8wmiv9oEk - is change.
Let us look at the input#2 (last) of this transaction - 129b8GsK4bU71riV3hopab6wnqhPCLyeGn (0.05413333 BTC - Output)
This is https://blockchain.info/tx/b7408039ebbe5631891a79ba61d853ab427210df39a805f8fb6a35b3417198bf
also transaction with duplicate R ! Same person transferred 2.17 BTC to BTC-e deposit 1B87Sf84uYadF2TzJzJwg9k44UjZCWEWUF
output #3 (last)
prev from https://blockchain.info/tx/c26eb6b0c209783e0c035ae999020fbda198fe1a5595b69c1d51ecff0ab9f8c3
same person put 2.08 BTC to btc-e with dup-R tx
BTC-e admins definitely know who is it - they have email/name of this person
Quote
What can you say about this recent transaction?
https://blockchain.info/tx/dace266993417aa89bd8f68a45835533df16d82897c2228af23c5426ea2e3aa0
Let me start.
1) this transaction sent with sharedcoin / bc.i
2) 2.98507462 BTC sent to deposit address of BTC-E 1FuntC8m9SZwejEu5u8zNSbE8bbd1K5x52 (I can prove it)
3) duplicate R in signatures ( 0xf0650c1f66cfe7e317709437e1f830afa7485cad2bb45dabaeca2809a5e044f2 )
https://blockchain.info/tx/dace266993417aa89bd8f68a45835533df16d82897c2228af23c5426ea2e3aa0
Let me start.
1) this transaction sent with sharedcoin / bc.i
2) 2.98507462 BTC sent to deposit address of BTC-E 1FuntC8m9SZwejEu5u8zNSbE8bbd1K5x52 (I can prove it)
3) duplicate R in signatures ( 0xf0650c1f66cfe7e317709437e1f830afa7485cad2bb45dabaeca2809a5e044f2 )
The R value is not generated by the weak RNG.
blockchain.info didn't create the transaction themselves; it was relayed to them.
Also bc.i-bug transactions usually have different R values for each input, this has identical values for all three.
This clearly follows the old pattern that we have seen since September.
how do you determine 1) ?
Quote
The bug that is present since September is different. It is still going on and I can distinguish it from bc.i clearly.
OK, johoe.
Let me be Sherlock Holmes, and you will be his brother Mycroft Holmes
What can you say about this recent transaction?
https://blockchain.info/tx/dace266993417aa89bd8f68a45835533df16d82897c2228af23c5426ea2e3aa0
Let me start.
1) this transaction sent with sharedcoin / bc.i
2) 2.98507462 BTC sent to deposit address of BTC-E 1FuntC8m9SZwejEu5u8zNSbE8bbd1K5x52 (I can prove it)
3) duplicate R in signatures ( 0xf0650c1f66cfe7e317709437e1f830afa7485cad2bb45dabaeca2809a5e044f2 )
Is it the bug of bc.i or may be someone is using his own tool for sharedsend?
Quote
You can't promote yourself to be a secure website
Users do not pay bc.i for their security. bc.i earns money only with ads.
If you pay nothing - you receive nothing. And do not complain.
this not just about bci, you cannot use any 3rd party service that involves the creation of other addresses than your own.
Quote
You can't promote yourself to be a secure website
Users do not pay bc.i for their security. bc.i earns money only with ads.
If you pay nothing - you receive nothing. And do not complain.
The incredible incompetence is not the fact that a variable was uninitialised but the fact that this code made it into production.
Unlike most devs who post in this forum I have worked on security software and also financial software (at the level that is used to run an entire insurance company).
Such bugs never happen there (as anything that is critical is checked by senior programmers well before being released - this clearly did not happen at blockchain.info).
Unlike most devs who post in this forum I have worked on security software and also financial software (at the level that is used to run an entire insurance company).
Such bugs never happen there (as anything that is critical is checked by senior programmers well before being released - this clearly did not happen at blockchain.info).
Jump to: