Bad signatures leading to 55.82152538 BTC theft (so far) - page 5.

JoelKatz

legendary

Activity: 1596

Merit: 1012

Democracy is vulnerable to a 51% attack.

Quote from: bigbeninlondon on August 11, 2013, 03:10:26 PM

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.

smolen

hero member

Activity: 524

Merit: 500

Quote from: bigbeninlondon on August 11, 2013, 03:10:26 PM

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

bigbeninlondon

hero member

Activity: 742

Merit: 500

Quote from: JoelKatz on August 11, 2013, 02:44:05 PM

Quote from: bigbeninlondon on August 11, 2013, 10:03:49 AM

Quote from: piotr_n on August 11, 2013, 10:01:57 AM

Quote from: bigbeninlondon on August 11, 2013, 10:00:09 AM

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.

JoelKatz

legendary

Activity: 1596

Merit: 1012

Democracy is vulnerable to a 51% attack.

Quote from: bigbeninlondon on August 11, 2013, 10:03:49 AM

Quote from: piotr_n on August 11, 2013, 10:01:57 AM

Quote from: bigbeninlondon on August 11, 2013, 10:00:09 AM

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.

Andreas Schildbach

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

piotr_n

legendary

Activity: 2053

Merit: 1356

aka tonikt

Quote from: smolen on August 11, 2013, 10:32:02 AM

Quote from: piotr_n on August 11, 2013, 10:16:31 AM

Quote from: bigbeninlondon on August 11, 2013, 10:11:59 AM

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

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.

Mike Hearn

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.

jl2012

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 X_n, for n = 1, 2, 3, ........ be a sequence of random numbers that being used as k for signature

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

X₁ = Y₁

X_n = SHA256(SHA256(X_n-1)+Y_n), 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 Y_n is constant, X_n is still a pseudo-random number guaranteed by SHA256.

Mike Hearn

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.

smolen

hero member

Activity: 524

Merit: 500

Are affected phones based on Qualcomm chipset?

piotr_n

legendary

Activity: 2053

Merit: 1356

aka tonikt

Quote from: Mike Hearn on August 11, 2013, 11:24:38 AM

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?

Remember remember the 5th of November

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.

BurtW

legendary

Activity: 2646

Merit: 1138

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?

smolen

hero member

Activity: 524

Merit: 500

Quote from: Luke-Jr on August 11, 2013, 11:20:02 AM

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.

bigbeninlondon

hero member

Activity: 742

Merit: 500

Quote from: piotr_n on August 11, 2013, 10:16:31 AM

Quote from: bigbeninlondon on August 11, 2013, 10:11:59 AM

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.

Mike Hearn

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

BurtW

legendary

Activity: 2646

Merit: 1138

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.

piuk

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.

Luke-Jr

legendary

Activity: 2576

Merit: 1186

Quote from: physalis on August 11, 2013, 07:29:22 AM

Quote from: Luke-Jr on August 11, 2013, 12:40:08 AM

Quote from: chriswilmer on August 10, 2013, 11:11:45 PM

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

Quote from: physalis on August 11, 2013, 07:29:22 AM

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

Quote from: CIYAM on August 11, 2013, 07:53:29 AM

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?

smolen

hero member

Activity: 524

Merit: 500

Quote from: BurtW on August 11, 2013, 10:45:47 AM

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?

Quote from: BurtW on August 11, 2013, 10:45:47 AM

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

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