Bitcoin Forum
April 24, 2014, 11:54:01 PM *
News: Due to the OpenSSL heartbleed bug, changing your forum password is recommended.
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 3 4 5 6 7  All
  Print  
Author Topic: Bad signatures leading to 55.82152538 BTC theft (so far)  (Read 27413 times)
BurtW
Hero Member
*****
Online Online

Activity: 1050

I no longer support vanity addresses


View Profile

Ignore
August 10, 2013, 10:53:13 PM
 #1

I have only seen this discussed in the newbies section so I thought I would open a thread here for a more technical discussion of this issue.

Several people have reported their BTC stolen and sent to https://blockchain.info/address/1HKywxiL4JziqXrzLKhmB6a74ma6kxbSDj

As you can see the address currently contains 55.82152538 stolen coins.

It has been noticed that the coins are all transferred in a few hours after a client improperly signs a transaction by reusing the same random number.  As discussed here:

http://en.wikipedia.org/wiki/Elliptic_Curve_DSA

the reuse of the same k value allows anyone to be able to recover the private key.

It appears that this is what may be happening.

It appears that the bug occurs in both the blockchain.info android wallet and the Andreas Schildbach Android Wallet so I suspect a bug in a crypto library or an implementation detail shared by both applications.

This has been discussed in this thread https://bitcointalk.org/index.php?topic=251743.0 with the more technical posts being these two:

https://bitcointalk.org/index.php?topic=251743.msg2890179#msg2890179
https://bitcointalk.org/index.php?topic=251743.msg2890736#msg2890736

Check out the two transactions posted here (which did lead to a theft of 0.9184236 BTC in this transaction https://blockchain.info/tx/211c135e58dc55bcce4c71dc02eae2dffc5a55387c29e8144bf1cd1e8878e52e)

@Xeno-Genesis

For you the bad transactions were
https://blockchain.info/tx/b6350f4339a59faf09bfc2a4086c2261598f46f257517ce53785145c964799bc
https://blockchain.info/tx/38fbb8a3ff718dd7c8006feb6aa9ed6add1772522781b0db95abb350a859220b

which use the same R-value in the signature.  It is strange that the same random number was generated in two transactions that are four days apart.  This doesn't fit the usual pattern. Which bitcoin client do you use?

The stealing transaction occured less then five hours after the transaction that reused the R-value.



Bitcoin must have unqualified fungibility to survive as a form of money.  We must support all efforts that protect and improve the fungible nature of Bitcoin and stand firmly against anyone or anything which threatens this essential property.
1398383641
Hero Member
*
Offline Offline

Posts: 1398383641

View Profile Personal Message (Offline)

Ignore
1398383641
Reply with quote  #2

1398383641
Report to moderator
1398383641
Hero Member
*
Offline Offline

Posts: 1398383641

View Profile Personal Message (Offline)

Ignore
1398383641
Reply with quote  #2

1398383641
Report to moderator
    mBitCASINOWIN BITCOINS IN OUR
24/7 LIVE DEALER CASINO

Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1398383641
Hero Member
*
Offline Offline

Posts: 1398383641

View Profile Personal Message (Offline)

Ignore
1398383641
Reply with quote  #2

1398383641
Report to moderator
smolen
Sr. Member
****
Offline Offline

Activity: 252


View Profile

Ignore
August 10, 2013, 11:47:04 PM
 #2

It has been noticed that the coins are all transferred in a few hours after a client improperly signs a transaction by reusing the same random number.  As discussed here  http://en.wikipedia.org/wiki/Elliptic_Curve_DSA the reuse of the same k value allows anyone to be able to recover the private key.
How long would it take to pool owners to start scanning mempool transactions and replace vulnerable ones?

Of course I gave you bad advice. Good one is way out of your price range.
TierNolan
Sr. Member
****
Offline Offline

Activity: 434


View Profile

Ignore
August 11, 2013, 02:16:10 AM
 #3

How long would it take to pool owners to start scanning mempool transactions and replace vulnerable ones?

You mean they should crack the private key for the address and then re-do the signature?  That seems only semi-legal.

It may not even fix the problem, all nodes receive all transactions directly.  It would make it slightly harder, the node would have to be always online, rather than only having to scan the block chain every hour or so.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
gmaxwell
Moderator
Hero Member
*
qt
Online Online

Activity: 1078


View Profile

Ignore
August 11, 2013, 02:26:33 AM
 #4

Of course, if these applications didn't constantly reuse addresses the exposure here— whatever the root cause ultimately turns out to be— would be a lot smaller.
chriswilmer
Hero Member
*****
Offline Offline

Activity: 574


View Profile WWW

Ignore
August 11, 2013, 04:11:45 AM
 #5

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?
Luke-Jr
Hero Member
*****
expert
Offline Offline

Activity: 1218



View Profile

Ignore
August 11, 2013, 05:40:08 AM
 #6

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

gmaxwell
Moderator
Hero Member
*
qt
Online Online

Activity: 1078


View Profile

Ignore
August 11, 2013, 05:48:21 AM
 #7

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?
No, no easy way to do that.  Plus the software to actually help you do that would be more complicated than the software required to make super-sure that this can't happen.  (e.g. select the nonce as sha256(message||privkey||random value) — though if your RNG is bad you also need to worry about weak keys))
chriswilmer
Hero Member
*****
Offline Offline

Activity: 574


View Profile WWW

Ignore
August 11, 2013, 05:49:09 AM
 #8

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?
No, no easy way to do that.  Plus the software to actually help you do that would be more complicated than the software required to make super-sure that this can't happen.  (e.g. select the nonce as sha256(message||privkey||random value) — though if your RNG is bad you also need to worry about weak keys))


Thanks!
piotr_n
Hero Member
*****
Offline Offline

Activity: 952



View Profile

Ignore
August 11, 2013, 11:49:08 AM
 #9

the reuse of the same k value allows anyone to be able to recover the private key.

It appears that this is what may be happening.

It appears that the bug occurs in both the blockchain.info android wallet and the Andreas Schildbach Android Wallet so I suspect a bug in a crypto library or an implementation detail shared by both applications.
Ouch...

Thanks for the info - I spent the whole morning triple checking if my wallet would not make a similar mistake, by a chance.
Seems that I'm fine, but you got me scared, sir Smiley

Check out gocoin - my original project of a bitcoin client written in Go, with some unique features.
dice64
Jr. Member
*
Offline Offline

Activity: 34


View Profile WWW

Ignore
August 11, 2013, 12:17:18 PM
 #10

I saw this write up a while ago, seems like there are some web wallets which use poor random number generation for every transaction, or as in this case a hardware wallet.

http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html
physalis
Sr. Member
****
Offline Offline

Activity: 308



View Profile

Ignore
August 11, 2013, 12:29:22 PM
 #11

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"?
While it makes sense for privacy reasons, it shouldn't need to be done just so you don't get your coins stolen.

If for example I give someone a bitcoin address so he can make recurring payments of some sort to me, I need to reuse that address. Everything else would just be a major pain in the ass.

piotr_n
Hero Member
*****
Offline Offline

Activity: 952



View Profile

Ignore
August 11, 2013, 12:33:26 PM
 #12

Yeah. The thesis that reusing an address is not "using Bitcoin correctly", is kind of weird, to say the least. Especially said as a solution for a guy who plays SatoshiDice... Smiley

Check out gocoin - my original project of a bitcoin client written in Go, with some unique features.
dice64
Jr. Member
*
Offline Offline

Activity: 34


View Profile WWW

Ignore
August 11, 2013, 12:47:11 PM
 #13

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"?
While it makes sense for privacy reasons, it shouldn't need to be done just so you don't get your coins stolen.

If for example I give someone a bitcoin address so he can make recurring payments of some sort to me, I need to reuse that address. Everything else would just be a major pain in the ass.

You can get every transaction which has been sent by that address and ensure none of its spent outputs have the same signature in the script. But the main problem is random number generation.

Even if you want to make recurring payments, you should still generate an address each time. Otherwise you seriously risk linking your address to your identity. It isn't a pain in the ass, its the best practice for anonymity, regardless of this current bad signature issue.
smolen
Sr. Member
****
Offline Offline

Activity: 252


View Profile

Ignore
August 11, 2013, 12:48:49 PM
 #14

How long would it take to pool owners to start scanning mempool transactions and replace vulnerable ones?
You mean they should crack the private key for the address and then re-do the signature?  That seems only semi-legal.
Accidentally disclosing private key by using flawed software is the same as accidentally publishing private key on this forum. The key holder effectively waives his right to bitcoins by disclosing the key.

Of course I gave you bad advice. Good one is way out of your price range.
piotr_n
Hero Member
*****
Offline Offline

Activity: 952



View Profile

Ignore
August 11, 2013, 12:52:35 PM
 #15

If one has a screwed up RNG, not reusing addresses does not make him anyhow safer, if the same generator is used to make new private keys.

Check out gocoin - my original project of a bitcoin client written in Go, with some unique features.
CIYAM
Hero Member
*****
Offline Offline

Activity: 910


Ian Knowles - CIYAM Lead Developer


View Profile WWW

Ignore
August 11, 2013, 12:53:29 PM
 #16

It's not much of a problem if you're using Bitcoin correctly (ie, not reusing addresses).

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

With CIYAM anyone can create 100% generated C++ web applications in literally minutes.

GPG Public Key | 1ciyam3htJit1feGa26p2wQ4aw6KFTejU
smolen
Sr. Member
****
Offline Offline

Activity: 252


View Profile

Ignore
August 11, 2013, 12:54:32 PM
 #17

The thesis that reusing an address is not "using Bitcoin correctly", is kind of weird, to say the least.
I'll just repost relevant part of my post from another forum

Even proper reuse of ECDSA private key makes it less secure. Satoshi did very good work protecting Bitcoin from possible future advances in cryptography - new addresses are created whenever it is appropriate, before first (and, ideally, the last) use public key is secret, only hash of it (address) is exposed to the public. But Satoshi did not forbid intentional address reuse, thus making key reuse possible.

CURVE    the elliptic curve field and equation used
G    elliptic curve base point, a generator of the elliptic curve with large prime order n
n    integer order of G, means that n * G = O

    Calculate e = \textrm{HASH}(m), where HASH is a cryptographic hash function, such as SHA-1.
    Let z be the L_n leftmost bits of e, where L_n is the bit length of the group order n.
    Select a random integer k from [1, n-1]. - This is what counts
    Calculate the curve point (x_1, y_1) = k * G.
    Calculate r = x_1 \pmod{n}. If r = 0, go back to step 3.
    Calculate s = k^{-1}(z + r d_A) \pmod{n}. If s = 0, go back to step 3.
    The signature is the pair (r, s).
And every (r, s) pair derived from the same dA and exposed to the public means more food for hyperlinearization and SAT-solvers. (Some day those two beasts will meet together and produce fertile offspring Smiley)

Of course I gave you bad advice. Good one is way out of your price range.
piotr_n
Hero Member
*****
Offline Offline

Activity: 952



View Profile

Ignore
August 11, 2013, 12:57:12 PM
 #18

Even proper reuse of ECDSA private key makes it less secure. Satoshi did very good work protecting Bitcoin from possible future advances in cryptography - new addresses are created whenever it is appropriate, before first (and, ideally, the last) use public key is secret, only hash of it (address) is exposed to the public. But Satoshi did not forbid intentional address reuse, thus making key reuse possible.
Of course - I fully agree with you and thanks for pointing it out.
But still, reusing addresses is one of the core features of Bitcoin - otherwise our life would be so much more complicated.
Bitcoin would have probably never got adopted, in the fist place, if one could not reuse an address.

Moreover, if this is so crucial for security, deterministic wallets do not seem to be a right way to go forward, do they?

Check out gocoin - my original project of a bitcoin client written in Go, with some unique features.
smolen
Sr. Member
****
Offline Offline

Activity: 252


View Profile

Ignore
August 11, 2013, 01:21:23 PM
 #19

Of course - I fully agree with you and thanks for pointing it out.
But still, reusing addresses is one of the basic features of Bitcoin - otherwise our life would be so much more complicated.
Bitcoin would have probably never got adopted, in the fist place, if one could not reuse an address.

Moreover, if this is so crucial for security, deterministic wallets do not seem to be a right way to go forward, do they?
I don't pretend to be an expert here, but looks like Bitcoin itself and deterministic wallets are right now out of reach for SAT-solvers and XSL attacks. We'll be alerted about progress in those areas by new yottahashes in mining difficulty Smiley

Of course I gave you bad advice. Good one is way out of your price range.
BurtW
Hero Member
*****
Online Online

Activity: 1050

I no longer support vanity addresses


View Profile

Ignore
August 11, 2013, 01:22:13 PM
 #20

I think we have discussed enough "politics" for now and would like to get back to the actual technical issue.  If I get a chance later today I plan to download the source code for the android wallet and see if I can locate the actual signature code and see what they are doing.

I saw this write up a while ago, seems like there are some web wallets which use poor random number generation for every transaction, or as in this case a hardware wallet.

http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html
Thanks for this write up.  It describes exactly what they are doing.

This is the crux here (cleaned up this a bit):
Quote
    Calculate e = HASH(m), where HASH is a cryptographic hash function, such as SHA-1.
    Let z be the Ln leftmost bits of e, where Ln is the bit length of the group order n.
    Select a random integer k from [1, n-1].
    Calculate the curve point (x1, y1) = k * G.
    Calculate r = x1 (mod n). If r = 0, go back to step 3.
    Calculate s = k-1(z + r dA) (mod n). If s = 0, go back to step 3.
    The signature is the pair (r, s).

The same k will lead to the same x1 coordinate, which will lead to the same r.

Bitcoin must have unqualified fungibility to survive as a form of money.  We must support all efforts that protect and improve the fungible nature of Bitcoin and stand firmly against anyone or anything which threatens this essential property.
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!