Pages:
Author

Topic: Bad signatures leading to 55.82152538 BTC theft (so far) - page 5. (Read 65144 times)

legendary
Activity: 1596
Merit: 1012
Democracy is vulnerable to a 51% attack.
Fine, you never hit "actually zero" if you always must assume the possibility of your code having bugs in it.  But assuming you code properly, a collision from a random number generator having probability X becomes probability 0 if you iterate until you get a unique number for an address based on historical usage.
No, because hardware is not perfect. Keeping the old values around increases the chance that a hardware failure will cause you to use one of them. You have a probability that is so absurdly small on one side that you can't ignore probabilities on the other side just on the grounds that they are very small. If you get to assume the code is proper, why don't I get to assume that a properly-code RNG won't produce collisions?

Quote
Additionally, this approach places less trust in delivered libraries, which is obviously (according to the topic of this discussion) a good approach.
That's a completely different issue. I agree that it might make sense to do this to protect against a broken RNG even while it makes no sense to do this to prevent the absurdly improbable collisions from a working RNG.


hero member
Activity: 524
Merit: 500
a collision from a random number generator having probability X becomes probability 0 if you iterate until you get a unique number
and random number generator becomes random permutation generator
hero member
Activity: 742
Merit: 500
If a wallet were to keep track of the k values per address, could that then mitigate these kinds of issues?
If you have an actually working RNG, the chance of picking up the same 256 bit value for a second time is basically zero.
Sure, but keeping track would make "basically zero" into "actually zero".  And since the wallet has your private keys anyway, adding a small dictionary seems trivial and doesn't add any vulnerability.  What's the downside?
No, it wouldn't make it actually zero. You have to consider the possibility that the code that checks has a bug in it, fails due to a hardware problem, and so on. If you account correctly, you may find that the added complexity (especially since now you're keeping the old values around instead of getting rid of them) actually increases the chances of a value being reused.

Fine, you never hit "actually zero" if you always must assume the possibility of your code having bugs in it.  But assuming you code properly, a collision from a random number generator having probability X becomes probability 0 if you iterate until you get a unique number for an address based on historical usage.  Additionally, this approach places less trust in delivered libraries, which is obviously (according to the topic of this discussion) a good approach.  

K must be unique per address per transaction and random.  It is known that most math libraries use PSEUDO-RANDOM generators.  So random is not always guaranteed.  But you CAN guarantee through code that K is unique per address per transaction, even if you cannot guarantee randomness.
legendary
Activity: 1596
Merit: 1012
Democracy is vulnerable to a 51% attack.
If a wallet were to keep track of the k values per address, could that then mitigate these kinds of issues?
If you have an actually working RNG, the chance of picking up the same 256 bit value for a second time is basically zero.
Sure, but keeping track would make "basically zero" into "actually zero".  And since the wallet has your private keys anyway, adding a small dictionary seems trivial and doesn't add any vulnerability.  What's the downside?
No, it wouldn't make it actually zero. You have to consider the possibility that the code that checks has a bug in it, fails due to a hardware problem, and so on. If you account correctly, you may find that the added complexity (especially since now you're keeping the old values around instead of getting rid of them) actually increases the chances of a value being reused.
hero member
Activity: 483
Merit: 551
In case you missed it: I put up beta versions of Bitcoin Wallet with a fixed RNG and key-rotation.

https://bitcointalksearch.org/topic/important-android-key-rotation-271846
legendary
Activity: 2053
Merit: 1356
aka tonikt
I think the first step for everyone using the apps in question transfer their funds to a new address that hasn't been used before.
Bad idea, IMO.
You can reveal your key at the very moment when transferring out your funds - if someone intercepts your priv-key-compromising tx while routing it, he can try to spend your cons before you.

I'm pretty sure all the compromised keys have already been robbed, so I'd rather advise to wait for the fix, not moving any coins.
Scanning code would be rather trivial, but to use it on the fly one have to be powerful miner or have very well connected bitcoin network nodes. After funds arrive at fresh address they can be considered safe. Sitting funds protected by disclosed keys are up to the first person to grab.
I'm not going to exploit this situation, I'll just sit back and enjoy the chaos Smiley
Well, after all, considering what we have just learned, that not only the random K value, but also private keys are affected by the broken RNG - moving the coins ASAP to a properly generated address might be a less risky step, indeed. Smiley
legendary
Activity: 1526
Merit: 1134
For what it's worth more modern elliptic curve DSA schemes don't use a random number during signing, exactly to try and avoid this kind of problem (though in our case the keys are weak too - crypto can't really survive a weak RNG). As a result signatures are deterministic. I'm not sure if ECDSA with secp256k1 like we use can be upgraded to use such a scheme - if it could be, that's worth doing.
legendary
Activity: 1792
Merit: 1111
If we can't fully trust the random number provided by the system, I wonder if this would help:

Let Xn, for n = 1, 2, 3, ........ be a sequence of random numbers that being used as k for signature

Let Yn, for n = 1, 2, 3, ........ be a sequence of random numbers generated by the system.

X1 = Y1

Xn = SHA256(SHA256(Xn-1)+Yn), for n > 1

Which means when the first random number is generated by the system, we record its SHA256 hash. The hash will be used as a nonce for the next random random

Therefore, even if Yn is constant, Xn is still a pseudo-random number guaranteed by SHA256.
legendary
Activity: 1526
Merit: 1134
Anything that uses SecureRandom has issues. Yes, we are using a new provider that overrides the old one:

https://code.google.com/p/bitcoin-wallet/source/detail?r=04d2044880d88107ee4a939a516fb4be4cedeaf9&name=bitcoinj-0.10#

You should not assume that using OpenSSL directly is safe. On Jellybean+ the SecureRandom provider is just a shim over the OpenSSL RAND_* functions and Jellybean+ is also affected. However TLS connections are OK.

I realise there's going to be a lot of questions about what exactly is going on here, but I'm not on the Android team and can't talk on their behalf. It's up to them to document exactly how the RNG is broken. Suffice it to say, if you aren't sure if you're affected, you probably are but you are welcome to send me a private message detailing what you're doing and I'll let you know.

Note that reading from /dev/urandom is OK. The kernel level RNG is not broken.
hero member
Activity: 524
Merit: 500
Are affected phones based on Qualcomm chipset?
legendary
Activity: 2053
Merit: 1356
aka tonikt
Hello,

A few days ago user Xeno-Genesis alerted us to some weaknesses in the default Android SecureRandom implementation. You guys are on the right lines - SecureRandom isn't. More technical details will come in the following days. For now, please see the following announcement:

http://bitcoin.org/en/alert/2013-08-11-android
So Google screwed up.

Can you at least disclose if this is version specific, or is it any Android version that is affected?
legendary
Activity: 1862
Merit: 1011
Reverse engineer from time to time
I don't think my application is affected https://bitcointalksearch.org/topic/avanitygen-alpha-v02-vanity-address-generator-for-android-updated-11112-101612 as it uses OpenSSL 1.01e internally, so it should be safe I think. However if it is some Linux API that is responsible, then it might be affected too.
legendary
Activity: 2646
Merit: 1137
All paid signature campaigns should be banned.
Quote
Android Security Vulnerability
11 August 2013
We recently learned that a component of Android responsible for generating secure random numbers contains critical weaknesses, that render all Android wallets generated to date vulnerable to theft. Because the problem lies with Android itself, this problem will affect you if you have a wallet generated by any Android app. An incomplete list would be Bitcoin Wallet, blockchain.info wallet, BitcoinSpinner and Mycelium Wallet.

In order to re-secure existing wallets, key rotation is necessary. This involves generating a new address with a repaired random number generator and then sending all the money in your wallet back to yourself. If you use an Android wallet then we strongly recommended you upgrade to the latest version available in the Play Store as soon as one becomes available. Once your wallet is rotated, you will need to contact anyone who has stored addresses generated by your phone and give them a new one.

If you use Bitcoin Wallet by Andreas Schildbach, key rotation will occur automatically soon after you upgrade. The old addresses will be marked as insecure in your address book. You will need to make a fresh backup.

Updates for other wallet apps should be released shortly.
Can you tell us which secure random number generator has the problem and also what exactly is meant by the "repaired random number generator".  Are you installing a new secure random number generator provider?
hero member
Activity: 524
Merit: 500
Even with correctly chosen k values, there are still theoretical coin-stealing risks to address reuse.
I saw an odd hint in one of http://en.wikipedia.org/wiki/Nicolas_Courtois publications that some very novel approach is being developed in this area. For me that's enough to start worry.
hero member
Activity: 742
Merit: 500
I think the first step for everyone using the apps in question transfer their funds to a new address that hasn't been used before.
Bad idea, IMO.
You can reveal your key at the very moment when transferring out your funds - if someone intercepts your priv-key-compromising tx while routing it, he can try to spend your cons before you.

I'm pretty sure all the compromised keys have already been robbed, so I'd rather advise to wait for the fix, not moving any coins.

Revealing a key for an address that you should already assume is compromised doesn't sound like a serious issue.  More serious is letting coins sit in an address you should already assume is compromised.
legendary
Activity: 1526
Merit: 1134
Hello,

A few days ago user Xeno-Genesis alerted us to some weaknesses in the default Android SecureRandom implementation. You guys are on the right lines - SecureRandom isn't. More technical details will come in the following days. For now, please see the following announcement:

http://bitcoin.org/en/alert/2013-08-11-android

legendary
Activity: 2646
Merit: 1137
All paid signature campaigns should be banned.
Just some references:

http://developer.android.com/reference/java/security/SecureRandom.html
http://www.cs.cmu.edu/~srini/15-446/android/android-sdk-linux_x86-1.0_r2/docs/reference/java/security/SecureRandom.html

Can someone run the following on the phone?

sr = SecureRandom()
String sr.getAlgorithm()
String sr.getProvider().getName()

and let us know what you find so we know where to look next.
 

hero member
Activity: 910
Merit: 1005
Please see this announcement on the issue http://bitcoin.org/en/alert/2013-08-11-android

An update was made to the blockchain.info app yesterday (v 3.52) to fix the problem for newly generated private keys. If you are a user of the blockchain.info android app you can either login through the web interface and send any coins to a new address or update to the latest android app and send all coins to a newly generated address. Alternately please wait for another update will be issued shortly to automatically rekey all android wallets however more testing is needed.
legendary
Activity: 2576
Merit: 1186
This seems like a serious problem!

Apologies if I am asking a question with an obvious answer, but is there a way a user can easily check to see if the same random number was used for a second transaction before broadcasting it?
It's not much of a problem if you're using Bitcoin correctly (ie, not reusing addresses).
That can't possibly be your proposed solution to this problem - "Just never use a bitcoin address more than once"?
No, not the solution.
Just pointing out that this isn't a serious problem, just a problem that's pretty important to address.
On the other hand, if whatever's causing k to be the same is also causing the private keys generated to be weak, that of course definitely would be a very serious problem...
While it makes sense for privacy reasons, it shouldn't need to be done just so you don't get your coins stolen.
Address reuse has never been just a privacy issue.
Even with correctly chosen k values, there are still theoretical coin-stealing risks to address reuse.
And even ignoring coin-stealing risks and privacy issues, there are still other problems from address reuse (that slip my mind at the moment).

Hmm... so none of the clients mentioned re-use an address for change (as this is not something the end-user generally has any control over)?
If a client is reusing addresses like this, it reveals a fundamental misunderstanding of how Bitcoin works.
Then the question I'd be asking myself is, do I want to trust this author got k correct, or doesn't have other subtle problems in their implementation?
hero member
Activity: 524
Merit: 500
The culprit is either the random number generator passed in (if param instanceof ParametersWithRandom) or java.security.SecureRandom, which I would not totally discount as this would be the implementation for the android phone specifically.
Can someone fire debugger, put breakpoint on line with getRandom() and give the code test run?

EDIT:  from what I can tell (correct me if I am wrong) ECPrivateKeyParameters is not an instance of ParametersWithRandom so that leaves us to go dig into java.security.SecureRandom as implemented on the android phone.
Yes and IMHO the best way to find out is to debug the code
Pages:
Jump to: