Reused R values again

[JorgeStolfi]

If someone would have done it intentionally he would have swept the 590 BTC that I found this week-end.

I do not think malice is likely, but I won't exclude it either.  There may be several reasons why a malicious programmer failed to sweep those coins. E. g. after the bug was discovered, he may have been afraid of being caught (especially if he is some BCI staff, hence a natural suspect, hence with his internet connections under watch).

[Aceman]

Is it wrong to think of Johoe somewhat as a hero to the BTC community?

[bcearl]

Or did just someone read the security alert and saved his money?

This clearly makes more sense to me since all the work of re-engineering the RNG is not worth the few satoshis left. You did a good job saving the big share.

[bcearl]

BTW., if someone with skill would manipulate the RNG intentionally, he would do it this way:

https://bitcointalk.org/index.php?topic=883793.0
https://www2.informatik.hu-berlin.de/~verbuech/klepto-ecdsa/
http://www.reddit.com/r/Bitcoin/comments/2p2kcd/how_perfect_offline_wallets_can_still_leak/

[amaclin]

BTW., if someone with skill would manipulate the RNG intentionally, he would do it this way:

... aaaaaand if skull not enough, he will fail with the error in his javascript, which gives security hole to "Joe Who" instead of himself.

(just wondering about dates. on the December,5 this was published
on December,8 - bc.i failed
in my country we have a proverb: "at catcher the animal runs")

[JorgeStolfi]

BTW., if someone with skill would manipulate the RNG intentionally, he would do it this way:

https://bitcointalk.org/index.php?topic=883793.0
https://www2.informatik.hu-berlin.de/~verbuech/klepto-ecdsa/
http://www.reddit.com/r/Bitcoin/comments/2p2kcd/how_perfect_offline_wallets_can_still_leak/

Wow...

Understandably, harware wallet manufacturers tend to present their products as 100% safe, and hide or dismiss their risks.  But, at the very least, you must trust the manufacturer (and trust that they didn't hire that programmer that BCI just fired  ), as well as all the people who may have access to it along the path from the factory to your pocket.  As customers grow confident in such devices, the payoff for an attack via malicious fake devices could be huge, and criminals may invest proportionally in carrying out the attack.

[CIYAM]

I have not made an uninitialised variable mistake in over 10 years (and I code in C++ where this can be a serious issue).

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?).

You can't promote yourself to be a secure website for storing money if you can't even manage to audit simple code issues like initialisation.

My recommendation would be not to use blockchain.info for storing funds - they are clearly not up to the job of actually securing it.

[lontivero]

people who have been the victim of blockchain.info's incredible incompetence.

Are you sure this is incredible incompetence? The transactions are no reusing the same R values but there are an (unknown) patterm instead. That cannot be incompetence nor accident, it has to be programmed as it is in bc.i by developers (very talented developers indeed).

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

Very good finding @bcearl, that paper describes what I think could happend (because of incompetence or not) and the conclusion is hard to swallow.

[CIYAM]

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).

[amaclin]

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.

[lontivero]

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.

[amaclin]

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?

[johoe]

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 )

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) ? 

[amaclin]

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

how do you determine 1) ?

1. It is definitely deposit to BTC-e
2. 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

[goosoodude]

@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.

smoothie@lealana.com

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.

[o3u]

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

[johoe]

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 

[newIndia]

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.

[itod]

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.

[lontivero]

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.