Bitcoin Forum
December 13, 2018, 07:12:27 PM *
News: Latest Bitcoin Core release: 0.17.0 [Torrent].
 
   Home   Help Search Login Register More  
Pages: « 1 2 [3] 4 5 6 7 »  All
  Print  
Author Topic: Bad signatures leading to 55.82152538 BTC theft (so far)  (Read 58228 times)
BurtW
Legendary
*
Offline Offline

Activity: 2352
Merit: 1010

All paid signature campaigns should be banned.


View Profile WWW
August 11, 2013, 04:21:02 PM
 #41

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.
 


Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
1544728347
Hero Member
*
Offline Offline

Posts: 1544728347

View Profile Personal Message (Offline)

Ignore
1544728347
Reply with quote  #2

1544728347
Report to moderator
1544728347
Hero Member
*
Offline Offline

Posts: 1544728347

View Profile Personal Message (Offline)

Ignore
1544728347
Reply with quote  #2

1544728347
Report to moderator
1544728347
Hero Member
*
Offline Offline

Posts: 1544728347

View Profile Personal Message (Offline)

Ignore
1544728347
Reply with quote  #2

1544728347
Report to moderator
PLAY NOW
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1544728347
Hero Member
*
Offline Offline

Posts: 1544728347

View Profile Personal Message (Offline)

Ignore
1544728347
Reply with quote  #2

1544728347
Report to moderator
1544728347
Hero Member
*
Offline Offline

Posts: 1544728347

View Profile Personal Message (Offline)

Ignore
1544728347
Reply with quote  #2

1544728347
Report to moderator
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526
Merit: 1006


View Profile
August 11, 2013, 04:24:38 PM
 #42

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

bigbeninlondon
Hero Member
*****
Offline Offline

Activity: 742
Merit: 500



View Profile
August 11, 2013, 04:25:01 PM
 #43

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.
smolen
Hero Member
*****
Offline Offline

Activity: 525
Merit: 500


View Profile
August 11, 2013, 04:26:46 PM
 #44

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.

Of course I gave you bad advice. Good one is way out of your price range.
BurtW
Legendary
*
Offline Offline

Activity: 2352
Merit: 1010

All paid signature campaigns should be banned.


View Profile WWW
August 11, 2013, 04:28:13 PM
 #45

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?

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
Remember remember the 5th of November
Legendary
*
Offline Offline

Activity: 1806
Merit: 1001

Reverse engineer from time to time


View Profile
August 11, 2013, 04:29:38 PM
 #46

I don't think my application is affected https://bitcointalk.org/index.php?topic=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.

BTC:1AiCRMxgf1ptVQwx6hDuKMu4f7F27QmJC2
piotr_n
Legendary
*
Offline Offline

Activity: 1960
Merit: 1039


aka tonikt


View Profile WWW
August 11, 2013, 04:32:46 PM
 #47

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?

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
smolen
Hero Member
*****
Offline Offline

Activity: 525
Merit: 500


View Profile
August 11, 2013, 04:35:59 PM
 #48

Are affected phones based on Qualcomm chipset?

Of course I gave you bad advice. Good one is way out of your price range.
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526
Merit: 1006


View Profile
August 11, 2013, 04:42:10 PM
 #49

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.
jl2012
Legendary
*
Offline Offline

Activity: 1792
Merit: 1010


View Profile
August 11, 2013, 04:54:26 PM
 #50

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.

Donation address: 374iXxS4BuqFHsEwwxUuH3nvJ69Y7Hqur3 (Bitcoin ONLY)
LRDGENPLYrcTRssGoZrsCT1hngaH3BVkM4 (LTC)
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526
Merit: 1006


View Profile
August 11, 2013, 05:07:08 PM
 #51

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.
piotr_n
Legendary
*
Offline Offline

Activity: 1960
Merit: 1039


aka tonikt


View Profile WWW
August 11, 2013, 05:13:02 PM
 #52

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

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
Andreas Schildbach
Hero Member
*****
Offline Offline

Activity: 483
Merit: 500


View Profile
August 11, 2013, 05:17:00 PM
 #53

In case you missed it: I put up beta versions of Bitcoin Wallet with a fixed RNG and key-rotation.

https://bitcointalk.org/index.php?topic=271846.0
JoelKatz
Legendary
*
Offline Offline

Activity: 1582
Merit: 1004


Democracy is vulnerable to a 51% attack.


View Profile WWW
August 11, 2013, 07:44:05 PM
 #54

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.

I am an employee of Ripple. Follow me on Twitter @JoelKatz
1Joe1Katzci1rFcsr9HH7SLuHVnDy2aihZ BM-NBM3FRExVJSJJamV9ccgyWvQfratUHgN
bigbeninlondon
Hero Member
*****
Offline Offline

Activity: 742
Merit: 500



View Profile
August 11, 2013, 08:10:26 PM
 #55

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.
smolen
Hero Member
*****
Offline Offline

Activity: 525
Merit: 500


View Profile
August 11, 2013, 08:26:40 PM
 #56

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

Of course I gave you bad advice. Good one is way out of your price range.
JoelKatz
Legendary
*
Offline Offline

Activity: 1582
Merit: 1004


Democracy is vulnerable to a 51% attack.


View Profile WWW
August 11, 2013, 10:01:03 PM
 #57

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.



I am an employee of Ripple. Follow me on Twitter @JoelKatz
1Joe1Katzci1rFcsr9HH7SLuHVnDy2aihZ BM-NBM3FRExVJSJJamV9ccgyWvQfratUHgN
molecular
Donator
Legendary
*
Offline Offline

Activity: 2590
Merit: 1007



View Profile
August 11, 2013, 10:07:10 PM
 #58

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.
 

found the info that android uses apache harmony implementation:

BTW: The Android implementation is the one from Apache Harmony project. The main implementation is in the file org.apache.harmony.security.provider.crypto.SHA1PRNG_SecureRandomImpl.

EDIT: this might be the implementation (not sure, though): https://android.googlesource.com/platform/libcore-snapshot/+/ics-mr1/luni/src/main/java/org/apache/harmony/security/provider/crypto/SHA1PRNG_SecureRandomImpl.java

PGP key molecular F9B70769 fingerprint 9CDD C0D3 20F8 279F 6BE0  3F39 FC49 2362 F9B7 0769
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2590
Merit: 1746



View Profile
August 11, 2013, 11:02:19 PM
 #59

A forum newbie emailed me and suggested this link would be informative for the thread: http://www.scribd.com/doc/131955288/Randomly-Failed-The-State-of-Randomness-in-Current-Java-Implementations


Bitcoin will not be compromised
Andreas Schildbach
Hero Member
*****
Offline Offline

Activity: 483
Merit: 500


View Profile
August 11, 2013, 11:24:30 PM
 #60

A forum newbie emailed me and suggested this link would be informative for the thread: http://www.scribd.com/doc/131955288/Randomly-Failed-The-State-of-Randomness-in-Current-Java-Implementations

Yes, that's the document that started it all... and it was published >5 months ago.
Pages: « 1 2 [3] 4 5 6 7 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!