49. On the Possibility of Stealing Coins
49
On the Possibility of Stealing Coins
AS STATED BEFORE, Bitcoin uses asymmetric cryptography with a public and private key pair as a mechanism to receive and authorize spending of bitcoins. However, Satoshi decided to use as the Bitcoin address the hash of the public key rather than the public key itself. Satoshi did this for two reasons. One was to reduce the size of each transaction as the hash is only 160 bits long. The second benefit was that it conveniently added one more layer of security in case a “backdoor” or security flaw should one day be discovered in the asymmetric cryptography algorithm used by Bitcoin. To be able to spend bitcoins, a hacker would have to first derive the public key from the hash and then derive the private key from the public key. Bitcoin Magazine wrote an excellent article on this subject.2
This whole thread discusses the possibility that an attacker with a lot of computing power could spend the bitcoins stored in a bitcoin address. Since the bitcoin block chain is an open ledger, it can be inspected in order to identify a bitcoin address having a large balance, and so an attacker could focus on those addresses.
Satoshi concluded that this would be quite difficult, as it would require a brute force attack to find a public key with a matching hash. It also shows the value of open source code (code that is open for all to see) for security, as opposed to closed source.
The important parts of the threads, including Satoshi’s entire posting, are reproduced here:
Stealing Coins
Posted by Red, July 25, 2010, 05:08:03 PM
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?
Re: Stealing Coins
Posted by Satoshi, July 25, 2010, 05:45:22 PM
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)
Re: Stealing Coins
Posted by Satoshi, July 25, 2010, 07:06:23 PM
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.
Re: Stealing Coins
Posted by Red, July 25, 2010, 07:09:43 PM
Thanks Satoshi,
Here is what I sent him.
-----------
Public key cryptography depends on the fact that it is hard to factor large prime numbers. Everyone knows that. If bitcoins were transfers were assigned to a well formed public key, and an associated private key signature was required for future transfer I would concede that bitcoins crypto transfers were completely secure.
However, bitcoin transactions don’t seem to work that way (by my reading). Transactions assign coin amounts to a particular “bitcoin address”. Where the address is a hash of the public key.
To validate a transaction, nodes take the public key from the signature and use that to verify the actual signature. If the signature is valid, it then hashes the public key to confirmit matches the bitcoin address assigned in the previous transaction. If both match, by definition, the transaction is good.
The potential weakness is in associating the public key in the signature with the bitcoin address.
There is a many to one relationship between public keys and a given hash. Now, if finding a pair of prime numbers that creates a secure public/private key pair where the public key part hashes to a particular bitcoin address seems hard... it probably is.
However, that is not required.
All you need is ANYTHING representing a public key that hash collides with a know large bitcoin account. It does NOT have to be a secure key pair based on primes. It is simply has to work once and allow the transfer of the stolen money to another account. That is potentially much easier.
Some hashes are harder to collide than others. I’m not sure the strength of the hash being used. However, colliding any hash gets much easier if you don’t have to care about the content being hashed.
Because of the nature of public keys they look like random data. As I understand them, you can’t know if a public key is based upon secure math unless you succeed in factoring it. Therefore clients don’t try. They normally just do the validation of the signature and presume the public key was generated in a secure fashion if it worked.
NOTE: The following analysis needs double checking by a real cryptohacker. IANACR
So depending on the hash, you could use one of the up-andcoming hash collision algorithms to generate a colliding block of data which represents a public key. Then by reversing the public/private key math, generate an associated (but hardly secure at all) private key that would generate valid signatures.
You then take your insecure, easily factorable, key pair and generate a signed transaction that matches the target bitcoin address.
Since the transaction log, can’t validate the full public key the coins were intended for, it simple presumes it must have been the one presented.
By recording the full public key of the transfer target in the block list you can regain the intended strength. However, you lose the ability to pass around 34 character addresses.
If I’m off base, I apologize for wasting your time.
Cheers! Red
Re: Stealing Coins
Posted by Red, 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 MD5are obvious examples. But work is well underway at collidingSHA-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 bya 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.
Re: Stealing Coins
Posted by knightmb, July 25, 2010, 07:34:42 PM
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-numeric26 (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 : )
Re: Stealing Coins
Posted by knightmb, July 25, 2010, 07:44:02 PM
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 Key654321 and I can spend coin pretending to be Public Key123456.
Re: Stealing Coins
Posted by Red, July 25, 2010, 07:52:23 PM
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 take2^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.
Re: Stealing Coins
Posted by Satoshi, July 25, 2010, 08:01:40 PM
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 Key123456.
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.
Re: Stealing Coins
Posted by knightmb, July 25, 2010, 08:20:41 PM
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 keyand 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 in10 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.
Re: Stealing Coins
Posted by satoshi, July 25, 2010, 08:48:01 PM
Quote
Here is a paper that claims to find SHA-1 collisions in 2^52 crypto operations. And optimally secure hash would take2^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 patternof 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.
Re: Stealing Coins
Posted by Red, July 25, 2010, 09:04:01 PM
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)
Re: Stealing Coins
Posted by Red, July 25, 2010, 09:19:11 PM
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 findp 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.
Re: Stealing Coins
Posted by satoshi, July 25, 2010, 10:27:36 PM
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.
Re: Stealing Coins
Posted by Red, July 26, 2010, 12:46:04 PM
Quote from: satoshi on July 25, 2010, 10:27:36 PM
Sorry, actually it’s ECDSA (Elliptic Curve Digital SignatureAlgorithm) not RSA. I shouldn’t have said “prime numbers”. ECDSA doesn’t take much time to generate a keypair.
I’ll learn how elliptic curves work one day, but not today. I should have taken more finite math when I was I college. Who’d a thought it would have come in handy for anything!
By the way, nice idea and implementation of BitCoin Satoshi!
It opens a whole new world of possibilities. I particularly like the concept of distributed agreement without relying upon trust. I think that is the breakthrough concept.
Also, I think the idea of BitCoin mining was brilliant! I doubt you could have gotten the network bootstrapped any other way. I disagree that it’s a “fair way” to distribute coins, but hey the world is not fair! And really, I don’t think any other way would have generated as much user excitement.
By the way, I concede that there is no thread of stealing bitcoins from my earlier postulation. The double hash seems to assure that from my perspective. Nice call!
Incidentally, I’d still like to know what happens if you generate RSA keys based upon non-prime numbers though. I figure there are other systems out there that didn’t double hash. :-)
Re: Stealing Coins
Posted by Bitcoiner, July 27, 2010, 02:01:16 AM
I’m glad that there’s guys like Red out there keeping a sharp eye out on things! This thread also makes me appreciativeof open source software, since there’s so many smart and interested people on this forums that can validate the software and place an additional degree of trust in it. Not sure that Bitcoin could be too successful if it was closed source!
Re: Stealing Coins
Posted by bytemaster, July 28, 2010, 09:42:17 PM
It would seem to me that the obvious solution to minimize the risk of any potential attack is to make the potential “reward” small. Thus never keep too many coins in one address. If the economic value of the “prize” is less than the cost of breaking it then no one will bother trying. After saying that, I still think that it is best to keep things as hard as possible to crack.
Re: Stealing Coins
Posted by knightmb, July 28, 2010, 10:45:16 PM
It would certainly be hard by both luck and CPU/storage power to do this.
If you found a collision and a private key, that would do you no good since you would have to peg an account out of the 541,638,008,296,341,754,635,824,011,376,225,346,986,572,413,939,634,062,667,808,768 possible combinations of people using accounts.
So look at it two-fold. I find a collision in the hash and I find the private key. Now I have to hope my odds are that someone else is using that hash. Since there are more possible hash account numbers than every person every born on this planet and was each using a million addresses, the attack by it’s own nature, while interesting, just isn’t really feasible on alarge scale.
Last updated