Stealing Coins
I think there is a pretty significant crypto flaw in Bitcoin as currently implemented. I’m not sure it is exploitable now (I’m not a real cryptohacker) but it is more than plausible that will be in the near future.
The flaw would enable anonymous stealing of coins from arbitrary bitcoin addresses. And no it doesn’t involve solving any of the hard problems that keep existing crypto systems secure. It is simply a potential correctable logic flaw in the implementation.
I would like bitcoins to succeed, so I’d rather not jump up and down in public yelling about flaws in public. Is there an appropriate place to discuss these types of issues?
It’s open source software, better to discuss it now than try to keep it a secret for someone else to discover and they may not be willing to share any details.
It’s best if you tell it to me privately so it can be fixed first.
I just e-mailed you my e-mail address. (or you could PM me here)
Once it’s fixed or proven not to work, could you post the details here? I’m very curious. =)
I think I know what he means, but I was certain that the odds of doing it a bit too random to make an attack out of it.
Red, thanks for telling me privately first! Please go ahead and post it (and relieve the suspense for everyone!)
His point is that transactions paid to a Bitcoin Address are only as secure as the hash function. To make Bitcoin Addresses short, they are a hash of the public key, not the public key itself. An attacker would only have to break the hash function, not ECDSA.
Satoshi pointed out that my scenario still required the hash function to be broken. That is true, but I was surprised to learn how successful some have been with that. MD4 and MD5 are obvious examples. But work is well underway at colliding SHA-1 and siblings like SHA-256.
What hash is being used in this part of Bitcoin?
He is also skeptical that you could you could use something other than a generated keypair.
On this point, I’m pretty confident that it is a simple matter of mathematics. I didn’t pay enough attention to this until I learned about “blind signing” of documents.
It turns out you can take a document and multiply it by a random number. Then have someone sign the jumbled file. Finally, you divide your random number out of their signature and the result is still a valid signature for the original document. Who’d figured that would work!
Anyway, if keypairs are only secure if they are based upon pairs of primes. Then nothing changes any of the math if the numbers are not prime. They are just much easier to factor.
I’d be perfectly happy for some crypto guy to prove me an idiot. It effects some features of a previous project I created that relied on the same association. I didn’t think of this then either.
Very nice. another reason why I love open source
As I understand it then, and please correct me if I’m wrong
Since the hash of the public key is smaller than the actual public key itself, one need only find a collision that matches the hash and when that collision is found you’ll know the public/private key combo. Then you simply spend coin using the known ones and the other clients will think it’s a valid transfer because the clients are only concerned that your hash matches the hash of the victim and the transaction is recorded for all time.
Currently the hash is 35 characters long, alpha-numeric 26 (upper case) +26 (lower case) +10 (numbers) = 62 possible per character So we have 541,638,008,296,341,754,635,824,011,376,225,346,986,572,413,939,634,062,667,808,768 possible combinations.
So I think we have about half of much work to do compared to going brute force against the main private/public key. Never hurts to plan for the future Wink
Quote from: Red on July 25, 2010, 07:22:14 PM
Satoshi pointed out that my scenario still required the hash function to be broken. That is true, but I was surprised to learn how successful some have been with that. MD4 and MD5 are obvious examples. But work is well underway at colliding SHA-1 and siblings like SHA-256.
What they often don’t mention though is collision generating still takes a lot of CPU time.
If I figure out that Public Key 123456 generates Hash ABCD and Public Key 654321 also generates Hash ABCD I’m still left without the Private Key.
But from what you are saying, all I need is Public Key 654321 and I can spend coin pretending to be Public Key 123456.
From what I was told, bitcoin is using one of the 160 bit hashes for generating bitcoin address.
The SHA-1 family of hash algorithms are some of the most commonly used. SHA-1 is a 160 bit hash.
Here is a paper that claims to find SHA-1 collisions in 2^52 crypto operations. And optimally secure hash would take 2^80 operations. 2^52 time is still large, but it is getting into cluster and botnet range.
http://www.ictlex.net/wp-content/iacrhash.pdf
The MD5 hashes can already be crashed in seconds on laptops. That was why it was retired from certificate based signatures.
And yes what I’m saying is I think you can think of a public key as two secret numbers mathematically combined together. And the private key as those two numbers kept separately. The thing that make the system secure requires that the two secret numbers be really large prime numbers.
But if they are really large non-prime numbers the combination math still works, it is just must faster to break the algorithm.
I’ll do a little more googling and see if I can substantiate my claims. I was hoping someone could dismiss them out of hand though.
Quote from: knightmb on July 25, 2010, 07:44:02 PM
If I figure out that Public Key 123456 generates Hash ABCD
and Public Key 654321 also generates Hash ABCD I’m still left without the Private Key.
But from what you are saying, all I need is Public Key 654321 and I can spend coin pretending to be Public Key 123456. You would still have to sign it with public key 654321. You need to find a collision using a public key for which you know the private key.
When you claim a Bitcoin Address transaction, you give your public key that matches the hash, then you must sign it with that key.
Red’s point is that it’s easy to quickly generate insecure public keys which you could break and find the private key after you find a collision.
He points out that if the public key was required to be a secure one, one which must have required significant work to find the prime numbers, that would increase the strength above that of the hash function alone. Someone trying to brute force would have to take time generating a key for each attempt.
Quote from: satoshi on July 25, 2010, 08:01:40 PM
You would still have to sign it with public key 654321. You need to find a collision using a public key for which you know the private key.
When you claim a Bitcoin Address transaction, you give your public key that matches the hash, then you must sign it with that key.
Red’s point is that it’s easy to quickly generate insecure public keys which you could break and find the private key after you find a collision.
He points out that if the public key was required to be a secure one, one which must have required significant work to find the prime numbers, that would increase the strength above that of the hash function alone. Someone trying to brute force would have to take time generating a key for each attempt.
Yeah, I thought the private key had to be in the mix somewhere. It kind of adds another randomness though, you have to find the hash that collides with another public key and at the same time, the private key has to be weak enough to break. I’m not saying it’s impossible, but it introduces 2 variables into the reverse collision finding.
Basically, one would build a rainbow table of weak private keys and then have to compare those to public hashes and then have to hope that someone out there has a hash that happens to be a part of that attack. Not impossible of course, but how feasible even if computers were 100 times faster in 10 years?
[edit] ok, re-read what you wrote, the public key is generated from the private key, not independently. So just finding a weak public key is the issue.
QuoteHere is a paper that claims to find SHA-1 collisions in 2^52 crypto operations. And optimally secure hash would take 2^80 operations. 2^52 time is still large, but it is getting into cluster and botnet range. 2^80 is if you can use a birthday attack. You can’t use a birthday attack for this, so the difficulty is the full 2^160 bits. Although, if you were trying to crack any one of 1 million (2^20) transactions, you could do a partial birthday attack 2^160/2^20 = 2^140.
Bitcoin Addresses are the only place where 160-bit hash is used. Everything else is SHA-256. They’re calculated as:
bitcoinaddress = RIPEMD-160(SHA-256(publickey))
Correct me if I’m wrong (please, and I’ll gladly eat crow) but I think it would be hard to use an analytical attack on RIPEMD-160 in this case. An analytical attack prescribes a certain range or pattern of inputs to try that will greatly increase your chance of finding a collision. Here, you don’t have that kind of control over RIPEMD-160’s input, because the input is the output of SHA-256. If an analytical attack helps you find an input to RIPEMD-160 that produces a collision, what are you going to do with it? You still have to get SHA-256 to output that value, so you would still have to break SHA-256 too.
For brute force, RIPEMD-160(SHA-256(x)) is no stronger than RIPEMD-160 alone. But for analytical attack, it seems like you must analytical attack both RIPEMD-160 and SHA-256. If I’m wrong, then the strength is the same as RIPEMD-160 and the SHA-256 only serves as one round of key strengthening.
Quote from: satoshi on July 25, 2010, 08:48:01 PM
bitcoinaddress = RIPEMD-160(SHA-256(publickey))
Correct me if I’m wrong (please, and I’ll gladly eat crow) but I think it would be hard to use an analytical attack on RIPEMD-160 in this case.
I think you are correct on the analytical attack. At least a far as I understand (minimally) the mathematical genius that is analyzing them.
I was worried it was the simpler:
bitcoinaddress = RIPEMD-160(publickey)
So the way I read it.
Given two numbers p and q. Which for RSA are supposed to be large primes.
Then n = p*q
The public key is the two fields (n, e). e is called the public exponent and appears to be chosen from a set of common values. The private key is also two fields (n, d). d is called the private exponent it it is derived by knowing e, p-1, and q-1.
The trick is, it is really hard to factor n into p & q. Therefore it is equally as hard to find p-1 and q-1
My postulation is that if n is arbitrary, and e is one of the common values, then there are lots of different p, q pairs that would work. The less prime the numbers the easier to find p and q, and therefore p-1 and q-1. And if you have a big block of arbitrary data that give you lots of flexibility in trying to collide a hash.
(That is the point where I could be totally off base though. Really interested, if a crypto geek knows better than me.)
I did read that the key generation algorithms create p and q such that they are “very likely prime” but it is too much work to know for sure. This leads me to believe non-primes don’t cause any obvious FAILs. I could be wrong though.
Sorry, actually it’s ECDSA (Elliptic Curve Digital Signature Algorithm) not RSA. I shouldn’t have said “prime numbers”. ECDSA doesn’t take much time to generate a keypair.