Stealing Coins

[Red]

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?

[knightmb]

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.

[satoshi]

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)

[Red]

You stopped my post just in time! :-)

[Quantumplation]

Once it's fixed or proven not to work, could you post the details here?  I'm very curious. =)

[knightmb]

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.

[satoshi]

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.

[Red]

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

[Red]

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.

[knightmb]

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 

[knightmb]

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.

[Red]

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.

[satoshi]

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.

[knightmb]

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.

[satoshi]

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.

[Red]

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)

[Red]

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.

[satoshi]

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.

[Red]

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

[Bitcoiner]

 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!