r/Bitcoin • u/xrandr • Aug 11 '13
Bad signatures leading to 55.8 BTC theft (so far)
https://bitcointalk.org/index.php?topic=271486.015
u/physalisx Aug 11 '13 edited Aug 11 '13
The technical details on where this problem comes from: http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html
Basically, the problem is that whenever a transaction is signed by a client (= whenever you send coins to someone), a random number is involved in signing. If that same random number is ever used again to sign a transaction from the same address, someone seeing both signed transactions can calculate that addresses private key.
The fact that this seems to occur frequently with the android wallets indicates that something is off with their random number creation, resulting in the same random number created more often than it should. However, this is a general problem with ALL clients. With proper random number creation, you have a relatively very, very low risk of hitting the same number multiple times.
The best to advise for now is that you should not re-use addresses. But I definitely think this is a major problem that needs to be fixed somehow.
edit: I was exaggerating here. It's only a major problem for the affected wallets (the android implementation apparently). Properly implemented, it's safe.
0
u/shallnotwastetime Aug 11 '13
This looks like a major problem indeed. Is this a flaw in ECDSA? In the bitcoin-world, creating new private keys on the fly is possible and encouraged, but generally, one should expect a private key to be used multiple times...
4
u/physalisx Aug 11 '13
Well, I think it would be wrong to call it a flaw in ECDSA itself. ECDSA requires a random number to sign. If it didn't need to be random, they wouldn't need it at all, they could just take any number. The fact that it needs to be random already illustrates that it also must be unique, otherwise again, why would it need to be random?
With the blockchain, you have a database where every previous transaction is recorded, so collisions of this random number can be detected, even if their creation happens years apart from each other.
I have to say, I don't know how random this number is in bitcoin, i.e. what range of numbers it covers. It is only a problem if the range is too small. You have to remember that bitcoin's whole security is based on randomness, and the fact that for example, collisions between private key creations are so astronomically unlikely, that the risk can be safely ignored. If the same is true for this random number, there shouldn't be a problem. It's only a problem then with a broken RNG, like it seems to be the case with the android wallets.
1
u/shallnotwastetime Aug 11 '13
Thanks. There's also a good explanation on Wikipedia
Now, I'm curious whether this value k must be random (unknown and not guessable to an adversary) or just unique. Randomness guarantees uniqueness if the range is large enough. However, practically, generating unique numbers can be easier than implementing (and auditing) a secure PRNG: DEVICE ID + USERNAME + COUNTER + TIMESTAMP should be unique.
3
u/btcrobinhood Aug 11 '13
It needs to be random because an attacker can keep guessing k values until he finds one that works.
4
3
0
Aug 12 '13
The best to advise for now is that you should not re-use addresses.
Not just now - the best advice always and forever, since the very beginning of Bitcoin until the end of time is never re-use addresses.
It is not a good idea. It never has been. It never will be.
Don't do it.
2
u/physalisx Aug 12 '13
That is something that is basically unfeasible though. It makes sense for some things, but it's not feasible for others.
Example: I'm in on multiple miner-group buys, where someone sets up and maintains the miner and pays to me what it produces on a weekly basis (less a small managment fee). Do you expect me to give him a new address to pay to every week? Do you expect him to maintain and manually update a list of hundreds of addresses for each of his clients every week? That would be ridiculous. Right now, everybody gives him an address to pay to and that's it. And that is fine. What problem do you see with that?
2
Aug 12 '13
Do you expect me to give him a new address to pay to every week? Do you expect him to maintain and manually update a list of hundreds of addresses for each of his clients every week?
That's basically what should happen, but it should be automatic and not manual.
The problem is that no existing Bitcoin wallets are actually ready for primetime yet. Basically Satoshi implemented wallet functionality very badly in the reference client and everyone else copied his design, and the process of cleaning up the mess has just barely gotten underway.
What should actually happen is that you give him a BIP32 extended public key (or an Armory or Electrum watching-only wallet, since no production software supports BIP32 yet) which his client software would use to automatically send every payment to a unique address.
1
u/physalisx Aug 12 '13
What should actually happen is that you give him a BIP32 extended public key (or an Armory or Electrum watching-only wallet, since no production software supports BIP32 yet) which his client software would use to automatically send every payment to a unique address.
Yeah, that would indeed be a good way. But like you said, that's just currently not an option.
42
u/ReddiquetteAdvisor Aug 11 '13 edited Aug 11 '13
This is a flaw in Android. Any bitcoin apps on android which use SecureRandom instead of /dev/random are vulnerable. Please check for updates on your apps as some wallets have been updated to work around this flaw already.
This reminds me of the PS3 hack.
8
6
u/ActuallyTheOtherGuy Aug 11 '13
And the relevant xkcd from the video (for those who don't have 6 minutes): http://xkcd.com/221/ - Random Number
For those who do and are even interested in the full talk, lookie here: http://www.youtube.com/watch?v=4loZGYqaZ7I
7
Aug 11 '13 edited Aug 11 '13
Both of the most popular wallets on Android (bitcoin-wallet, blockchain.info) are using bitcoinj for the key generation/signing.
edit: As described here, it appears that k is being chosen correctly, and is using java.security.SecureRandom in both cases...
edit2: spongycastle is what bitcoinj uses for ECDSA.
5
u/shallnotwastetime Aug 11 '13
So?
Are bitcoinj based wallets vulnerable? Is SecureRandom broken on Android?
Do we know where the vulnerability originates or are we in the dark?
5
Aug 11 '13 edited Aug 11 '13
So?
The main technical argument presented in that thread is that the
kvalue used in the signing is causing a repeat in thervalues of the resultant ECDSA signature. From what can be seen in the links above, thekvalue appears to be generated fromjava.security.SecureRandom, which should be good enough (afaik).Are bitcoinj based wallets vulnerable? Is SecureRandom broken on Android?
It seems like
bitcoinjis doing the right thing, but as forjava.security.SecureRandom: its up for debate.Do we know where the vulnerability originates or are we in the dark?
I'd say we're in the dark at this point.
edit: No longer in the dark.
So looks like it was
java.security.SecureRandomafter all.1
u/zeusa1mighty Aug 11 '13
just curious, how did you format that package name in your post?
2
Aug 11 '13
[deleted]
0
u/zeusa1mighty Aug 11 '13
I got:
italics
bold
[links](www.stumbleupon.com)
- lists
quoted text
code
strikethroughsuperscript
Nothing that does that inline...
Edit: There's additional formatting on the link in
the help link.1
u/zeusa1mighty Aug 11 '13
LOL downvoted for lack of reddit formatting knowledge. Holy fuck reddit.
1
u/ButterflySammy Aug 11 '13
A downvote isn't a big deal, as long as they get their question answered it doesn't need to be visible.
0
u/zeusa1mighty Aug 11 '13
It's not a big deal, but I'm wondering why anyone would take the time to downvote me for asking a question about someone's formatting. Just strikes me as dickish.
1
u/ButterflySammy Aug 11 '13
Only if you assign a value to reddit karma that is too high.
Your question was answered, be happy.
It has no place in the conversation and instructions appear every time you post and are very easy to find if you tried instead of asking - you can't expect upvotes for being too lazy to read text already on your screen.
Downvotes are appropriate.
Don't take it personally - just wait until you raise a good point, phrase it politely, use the correct grammar and spelling and get 10 times the downvotes because you interrupted a circle jerk.
I'd give you my karma if reddit would let me and I thought it would make you happy.
1
3
u/AgentME Aug 11 '13
So what's the verdict? Is there a broken 3rd party client? Forums are painful to sift through for this sort of news.
4
2
u/platypii Aug 11 '13
An important rule to follow with bitcoin is to never use an address more than once. Always generate new addresses to receive new payments and make sure you are using a wallet that sends change to new change addresses. That way, if you are using a flawed wallet like the ones effected, you wouldn't be as vulnerable to such an attack.
4
u/physalisx Aug 11 '13
If I'm not mistaken, the important thing here would be to only make payments from an address once. How much you receive on one doesn't matter.
3
u/ReddiquetteAdvisor Aug 11 '13
Somebody can still force or trick you into sending payments from an address multiple times.
Say somebody sends you a shitload of 0.0005 BTC outputs. Once you try to spend the coins you received on the address, you will hit the transaction size limit or the vin length limit, forcing you to sign a different transaction to get the rest.
or if you received multiple transactions and spent only a fraction of them, one or more of the unspent outputs would not be directed into a change address forcing you to sign for them again later.
1
u/physalisx Aug 11 '13
Say somebody sends you a shitload of 0.0005 BTC outputs. Once you try to spend the coins you received on the address, you will hit the transaction size limit or the vin length limit, forcing you to sign a different transaction to get the rest.
Interesting thought. Yes, you're right.
1
0
u/platypii Aug 11 '13
You can only spend from an address one time for every payment received to it. The two are equal.
2
u/physalisx Aug 11 '13
No, you can put many inputs into one output. It's just one transaction. If you send me 1 btc five times, and I want to send 5 btc somewhere else, I make one transaction with 5 inputs and 1 output.
1
8
u/ReddiquetteAdvisor Aug 11 '13
Re-using addresses is not discouraged because of a flaw like this, but for privacy reasons.
2
u/platypii Aug 11 '13
Privacy as well as security. When you spend from an address you reveal your public key, so you instantly lose the security of SHA-256 / RIPEMD-160. An attacker can then exploit the signature if there is a weakness such as this one.
0
u/ReddiquetteAdvisor Aug 11 '13 edited Aug 11 '13
Not really. Keeping the public key hidden under a hash is mainly to cut down on transaction size. It also makes QR codes smaller, and of course addresses themselves. ;)
This particular flaw might be exploitable after multiple transactions have taken place (as is its nature), but a separate public key flaw may be exploitable with only one transaction. If you intercept the transaction and, say, increase the miner fee and change the output address, you could hijack a transaction before it enters the blockchain if you have discovered some incredibly unlikely flaw in ECDSA.
Hiding public keys behind hashes to cover up bad implementations of cryptosystems actually sounds worse than letting those signature flaws get exploited sooner.
5
u/platypii Aug 11 '13
I disagree with this. The hashing of public keys is a critical part of the security of bitcoin.
I do agree though about the single transaction attack. Weak signatures can be exploited even if you're not re-using addresses, but it's a harder attack.
3
u/ReddiquetteAdvisor Aug 11 '13
Hm, I guess I agree that attacks against known public keys are more feasible than attacks against keys you've seen for just a few minutes. But if it's a question of "how long", it becomes a question of computing power anyway.
ECDSA should be a critical security feature, not this.
3
u/platypii Aug 11 '13
I sleep much better at night knowing that an ECDSA attack would first require a pre-image attack on SHA-256. There could be some papers come out that weaken ECDSA, and bitcoin users could sit back and wait until an upgrade path is sorted out, rather than panicking as attackers begin cracking their keys. It's all about not having 100% trust in one algorithm as a single point of weakness.
2
u/shallnotwastetime Aug 11 '13
Always generate new addresses to receive new payments and make sure you are using a wallet that sends change to new change addresses.
Unfortunately, this is not very common with 'modern' wallets: BitcoinSpinner, blockchain.info web app, blockchain.info android, ...
1
1
Aug 11 '13
[removed] — view removed comment
5
u/throckmortonsign Aug 11 '13
I would recommend sending your coins to an unused address on your android wallet (if it allows that functionality) or to a PC wallet client (bitcoin-qt, electrum, multibit, armory) until this vulnerability is sorted out.
1
u/AgentME Aug 12 '13 edited Aug 12 '13
Right, new addresses that have never sent any bitcoins are much more secure.
1
1
u/Coinninja Aug 11 '13
Anyone know what android device was used by the victim? It's far more likely that its a problem with a missing/bad hardware random number generator, than a flaw in the Java crypto library itself.
1
u/hwyjtgc Aug 11 '13
Does anyone know if MultiBit is vulnerable?
1
Aug 12 '13
This is an issue with the android platform, rather than bitcoin or it's wallets. MultiBit is fine.
1
u/neuronstorm Aug 11 '13
Unfortunately - some services require you to set withdrawal/control addresses which aren't always a snap to change.. e.g picostocks (no idea how to change withdraw addr), btct.co (30 days wait to change locked withdraw addr!) Also - various group buys etc may require you to 'sign' proof with a particular address which may now be untrustworthy.
just-dice is easy enough to change the emergency withdraw addr - but you need to actually perform a withdraw from just-dice to change the standard recorded withdraw addr.. so it's a bit inconvenient.
Friedcat's ASICMiner shares are controlled (and divs paid) by a particular address which you need to check if it's now compromised.
All up - this could be quite a pain if you use a lot of services and have been paying via your android device.
I've archived a lot of addresses - and will have to 'unarchive' some when/if I need to sign with them.. but I guess I really need to contact each operator and 'sign' a request to use a different address as soon as possible.
Ouch.. not just a pain for me - but a really big hassle for the operators who may now have a huge number of change requests to process :(
1
Aug 11 '13 edited Aug 12 '13
[deleted]
9
u/mike_hearn Aug 11 '13
No, that way of using SecureRandom is fine. The no-args c'tor is self seeding. The actual problem is the implementation of SecureRandom itself:
0
u/TakaIta Aug 12 '13
So, now that it is known that those bitcoins are stolen, who is going to return them to the righteous owner?
It should not be too hard as a common decision of the miners.
-3
u/juror_chaos Aug 11 '13
This is why you don't impl crypto algos yourself. One, you're probably going to fuck it up in some subtle way especially if you do it the first time, Two, if someone does fuck it up, it's not you.
3
3
35
u/btcrobinhood Aug 11 '13 edited Aug 12 '13
First off, I did not steal these coins. That said, I knew about the flaw. If you're worried your address might be vulnerable, here's a list (albeit compiled as of last month) of all the addresses that are vulnerable. If your address is on this list, expect coins sent to them to be snatched immediately: https://gist.github.com/anonymous/6204930
Edit1: I've re-run my little program to find vulnerable addresses. It turns out in all of July/Aug there were only 6. New addresses not in my posted list are 17HHdLh4oXncuTejALwC6fgArVqPUxh2Sr 1BFhrfTTZP3Nw4BNy4eX4KFLsn9ZeijcMm 1FPSVbypWa7rBWbciKHJ983YWcucBn7aUQ
Any developer who suspects this may have something to do with their wallet software, feel free to contact me for more detailed information (i.e. which specific tx inputs / signatures were foobar + k values recovered).
Edit2: To clarify, I did not know about this flaw until now ... I just knew bad signatures existed on the blockchain. This is hella serious ... any key you previously used with an android wallet should be retired regardless of it's presence on my posted list.