Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: Red on July 25, 2010, 05:08:03 PM



Title: Stealing Coins
Post by: Red on 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?


Title: Re: Stealing Coins
Post by: knightmb on July 25, 2010, 05:19:29 PM
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.


Title: Re: Stealing Coins
Post by: satoshi on 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)


Title: Re: Stealing Coins
Post by: Red on July 25, 2010, 06:07:31 PM
You stopped my post just in time! :-)


Title: Re: Stealing Coins
Post by: Quantumplation on July 25, 2010, 06:09:40 PM
Once it's fixed or proven not to work, could you post the details here?  I'm very curious. =)


Title: Re: Stealing Coins
Post by: knightmb on July 25, 2010, 06:15:05 PM
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.


Title: Re: Stealing Coins
Post by: satoshi on 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.


Title: Re: Stealing Coins
Post by: Red on 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 confirm it 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-and-coming 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


Title: Re: Stealing Coins
Post by: 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 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.


Title: Re: Stealing Coins
Post by: knightmb on 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-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  ;)


Title: Re: Stealing Coins
Post by: knightmb on July 25, 2010, 07:44:02 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.


Title: Re: Stealing Coins
Post by: Red on 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 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.



Title: Re: Stealing Coins
Post by: satoshi on July 25, 2010, 08:01:40 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.


Title: Re: Stealing Coins
Post by: knightmb on July 25, 2010, 08:20:41 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.


Title: Re: Stealing Coins
Post by: satoshi on 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 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.


Title: Re: Stealing Coins
Post by: Red on July 25, 2010, 09:04: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)




Title: Re: Stealing Coins
Post by: Red on 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 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.


Title: Re: Stealing Coins
Post by: satoshi on 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.


Title: Re: Stealing Coins
Post by: Red on July 26, 2010, 12:46:04 AM
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.

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


Title: Re: Stealing Coins
Post by: Bitcoiner on 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 appreciative of 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!


Title: Re: Stealing Coins
Post by: mizerydearia on July 27, 2010, 06:14:38 AM
I'm glad that there's guys like Red out there keeping a sharp eye out on things! This thread also makes me appreciative of 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!

Actually, quite the opposite.  What you read may seem like intelligent conversation that makes sense and makes you feel more trustworthy, confident and excited about Bitcoin, but, like http://www.youtube.com/watch?v=lBp5ag6SJH4 it's just fabricated wording to sound good.</sarcasm>


Title: Re: Stealing Coins
Post by: bytemaster on 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.



Title: Re: Stealing Coins
Post by: knightmb on 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 a large scale.


Title: Re: Stealing Coins
Post by: Anonymous on July 29, 2010, 05:58:11 AM
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.



This might be a good idea to add to an eventual bitcoin backup integration.Not only back the wallet up but create a bitcoin address for each of your coins automatically.Say that you have  1000 bitcoins it should be trivial to create 1000 addresses which means if an address was somehow compromised you only lose 1 btc!A separate process could reassemble your coins in the amount you need to spend.Is this possible?



Title: Re: Stealing Coins
Post by: FreeMoney on July 29, 2010, 08:10:59 AM
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.



This might be a good idea to add to an eventual bitcoin backup integration.Not only back the wallet up but create a bitcoin address for each of your coins automatically.Say that you have  1000 bitcoins it should be trivial to create 1000 addresses which means if an address was somehow compromised you only lose 1 btc!A separate process could reassemble your coins in the amount you need to spend.Is this possible?


Would the downside be the cost of the "putting back together" transaction once they were in one wallet and you needed to spend a bunch of them together?


Title: Re: Stealing Coins
Post by: Anonymous on July 29, 2010, 10:13:13 AM
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.



This might be a good idea to add to an eventual bitcoin backup integration.Not only back the wallet up but create a bitcoin address for each of your coins automatically.Say that you have  1000 bitcoins it should be trivial to create 1000 addresses which means if an address was somehow compromised you only lose 1 btc!A separate process could reassemble your coins in the amount you need to spend.Is this possible?


Would the downside be the cost of the "putting back together" transaction once they were in one wallet and you needed to spend a bunch of them together?

Bank fees.....
 :)

Is there a formula you could use to work that out?I would be interested to know the comparison between the cost of real world bank fees and the reassemble process on different amounts of bitcoins.


Title: Re: Stealing Coins
Post by: FreeMoney on July 29, 2010, 10:32:12 AM
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.



This might be a good idea to add to an eventual bitcoin backup integration.Not only back the wallet up but create a bitcoin address for each of your coins automatically.Say that you have  1000 bitcoins it should be trivial to create 1000 addresses which means if an address was somehow compromised you only lose 1 btc!A separate process could reassemble your coins in the amount you need to spend.Is this possible?


Would the downside be the cost of the "putting back together" transaction once they were in one wallet and you needed to spend a bunch of them together?

Bank fees.....
 :)

Is there a formula you could use to work that out?I would be interested to know the comparison between the cost of real world bank fees and the reassemble process on different amounts of bitcoins.

My understanding is that right now you could combine a few in one block for free, then a few more, staying under the limit each time. But... the fee system will eventually become a bunch of competing fee systems as time goes on.