Potential vulnerability of hash function?

[slush]

Hi,

I discussed bitcoins with my friend today, he is something-like-mathematician. I told them that bitcoins are safe, because:

* are built on widely used and not-yet-broken hashing function
* when somebody find weakness of this hash function, it will be probably big problem also for other companies - banks, army etc.
* if weakness will be found, it will not be only bitcoin specific. In this case, bitcoin software can switch it's hash function in nearest software version to something not yet broken before massive attack to bitcoin mining infrastructure

I hope that are correct arguments, aren't they? He was almost ok with that, just with this comment, which don't let me sleep. Please correct me, if it is wrong in some point:

Some new block of 50BTCs is valid, when hash itself fullfill some requirement, so we can crosscheck it's validity. Something h = f(x) where f is hashing function, x is salt we use for validity check and h is hash itself. But we do not looking forward some specific 'h', just kind of 'h' which fullfill defined requirements. So breaking this is much more easier than breaking whole hashing function in terms 'give me _specific_ "h" and I will give you salt "x" which matches h=f(x)" as is valid for already broken MD5, for example. There are plenty of valid 'h' hashes, so we are not forced to full break of hashing function!

This vulnerability is just teoretical - we both don't say that we know how to break hashing function in this way! I just noticed that breaking hashing function for purposes of generating bitcoins is many-degree easier and does not mean that attack can be publicly used for breaking of general encryption. So teoretically there can be attack which can be used on bitcoin mining, but will not be in public interest, because common usage of hashing function will still be valid.

Am I correct or I missed something big in my ideas? Unfortunately I didn't find any detailed bitcoin algorithm or protocol description and I found source codes too much obscure to find these details directly here.

Thanks,
Marek

[theymos]

If you find some way of hashing faster, the generating difficulty will just get higher. You might control the network's CPU power for a while, but if you can figure out a SHA-256 shortcut, everyone else will, too.

[slush]

If you find some way of hashing faster, the generating difficulty will just get higher. You might control the network's CPU power for a while, but if you can figure out a SHA-256 shortcut, everyone else will, too.

I think you missed main point. It is not about rising 'difficulty', GPU mining etc. It is just about that we believe that curent hashing function is safe *because* outer world also believe in that in banking, army etc. Yes, they use same hashing method, but very probably in different manner!

When you have h = f(x), it is completely another task to
* find *some* x for *specific* h (which can be hashed password for banking account somewhere in Great Bank)
* find *some* x for *some* h (which is valid bunch of 50BTCs)

There is nothing as non-breakable hashing function. People believed for many years that MD2 is nonbreakable, until 1997. Then they believed that MD5 is strong enough. Until around 2008 when collisions was found (by the way the man who found collisions is from the same city as me). So this is just question of time when sort of collisions will be available also for hash function used in bitcoin (sha256?). And I'm just asking if current architecture of hashes is not more vulnerable to (partial) collisions than mainstream usage of hashes (as you have to find *specific* 'x' for breaking bank account).

Marek

P.S. I believe that a) I'm wrong in some point (but don't know in what yet) and b) this is just teoretical discussion and this not keep me out of bitcoin idea.

[theymos]

"Breaking" Bitcoin's non-standard use of SHA-256 means finding a way of creating a proof-of-work hash without doing all of the normal hashing work. But in almost all cases, you would still have to do some non-negligible amount of work. All this does is make hashing quicker for you, and this is a problem that can be solved with difficulty adjustments.

"Breaking" SHA-256 is exactly like creating a new computer chip that can do hashing 20x faster per watt than everyone else.

[slush]

I try to ask differently.

Does Bitcoin mining in way that everybody looks at the same time for the salt of the*same* hash? Say we know the next block is about finding salt for hash "112431234bffa"? Or we are trying to find *any* hash where second, fourth and the last characters will be "2" (for example)? Or

If the first case, everything looks perfectly for me, it was original intention to hash function to be strong in this case. But for second example there are *plenty* of hashes like that (probably 21 millions) and there can exist method which is 1e7 faster than computing hashes by "normal way". Finding md5 collisions is almost instant on the poor hardware.

Again, I'm not telling I have this method, but I want to know if I'm absolutely out (I hope) or there is really possibility to break bitcoin and *not* compromise hash function itself. Just because bitcoins may use hashing in non standard way.

[slush]

I will tell you one funny example from my life. Maybe you catch my worries on that.

Before many years, my friend met one well known girl from my country. She is pretty and popular, so he trotted out with it and said he get her phone number. I also liked her and was a little angry that I missed chance to meet her too. And because he didn't want to tell me her phone number .

So I told him one: "Okay, I will never know her phone number, but, please, tell me just md5 hash of it! You know that hashes are irreversible, so you do not tell me her number, but I will have a feel that I have a piece of her! He agreed, but was very 'lol' with my request - he called me a nerd .

But he was quite surprised and confused, because I told him her phone number after few minutes! I never called to this number, but it is great example that people too much rely on things they don't understand. Of cource we have only few notations of phone number in our country and approximately tens of millions unique phone numbers, so it was quite easy to break hash by bruteforce by knowing so little information.

I don't say in any way that inventors of bitcoin don't know technology they used! I just want to know *exactly* what is doing with bitcoin hashes and I'm not satisfied with 'it is well known hash function, it must be safe'! Unfortunately I did not find enough resource to know that, so I have to ask here. Please point me to some specification if exists, I will be glad to read that in detail!

Marek

[Gavin Andresen]

Everybody is looking for:

h = f(x), where h < TARGET

I think you're asking if there is some weakness in SHA256 (or hashing in general) that can make solving that problem trivial.

It seems unlikely to me, but I'm not a professional cryptographer.  If TARGET were '4', then the problem is equivalent to:
h = f(x) where h = 0 OR h=1 OR h=2 OR h=3

Maybe there's some tricky method that reuses work and makes solving the TARGET=4 case more than 4 times easier than solving for TARGET=1 (which is "find this specific hash")... but I just don't see that doing anything more than what has already been pointed out in previous posts:  it is just a quicker way of hashing, so difficulty would go up.

[wumpus]

I understand your worries, but your topic title is way too pretentious. You did not really find a vulnerability in the hash function.

[slush]

Everybody is looking for:

h = f(x), where h < TARGET

Thanks a lot, it is exactly what I asked for.

Just one more question. TARGET is constant (respective related to difficulty) or is different for each next block? I'm asking because if range (0, TARGET) is slowly shrinking regards to rising difficulty, it means that after 'breaking' of sha, there will be much limited amount of coins to find (because range will be almost zero).

Maybe naive, but TARGET_LOW < h < TARGET_HIGH where interval is changing regards to block we are finding right now, we can manage independently:
* difficulty, respective range inside which hash must be in (in critical situation TARGET_HIGH - TARGET_LOW = 1 to ensure that specific hash must be found)
* amount of coins to find (by moving range somewhere else on next block).

[RHorning]

"Breaking" Bitcoin's non-standard use of SHA-256 means finding a way of creating a proof-of-work hash without doing all of the normal hashing work. But in almost all cases, you would still have to do some non-negligible amount of work. All this does is make hashing quicker for you, and this is a problem that can be solved with difficulty adjustments.

"Breaking" SHA-256 is exactly like creating a new computer chip that can do hashing 20x faster per watt than everyone else.

It depends on how the the SHA-256 algorithm is broken.  If somebody creates a quantum computer with 400 qubits and is able to create any arbitrary SHA-256 hash with any other prefix or expected "proof of work" with a Big O(1) level of difficulty, Bitcoins as a program would simply be screwed and potentially attacked as if somebody just brought on a million new machines into the network.  It actually would be worse, as somebody with this kind of computing power would literally be able to create as many new blocks as fast or as slow as they cared, depending strictly on the speed of the computer to spit out new blocks.  This could conceivably happen in this situation about a thousand times per second or more, which would set up a DOS attack on the network like you've never seen before.  Difficulty could conceivably go to infinity in this situation and still not stop the flood of new blocks.  They would also all be valid new blocks, at least according to the current algorithm, and could not be rejected based upon increased difficulty.

Luckily, most current quantum computers are insanely expensive (that are genuine quantum computers) and have right now a dozen qubits as the largest register they are working with.  There is reason to believe that Moore's law applies to Quantum computing, so it is something to worry about in terms of future plans for the currency, but I put this on the order of an issue decades away, if even that.  It is also something which can be defeated at least temporarily by increasing the number of bits in the hash.

Quantum computers and in particular Shor's Algorithm (http://en.wikipedia.org/wiki/Shor%27s_algorithm) is a known weakness to encryption algorithms that depend on the public/private key method for them to work, of which the SHA-256 algorithm is certainly a member of that class of algorithms vulnerable to this kind of attack.   This algorithm isn't O(1), but it is awfully close.  What keeps it from being used is mainly a lack of hardware capable of carrying out the methodology, not a lack of ideas for it to work.

It is possible that some sort of conventional Von Neumann architecture-type computer (what most people call simply a "computer") would be able to "partially break" the algorithm where hashing would be made considerably easier than is currently the case.  In that situation, it would merely be a refinement of the algorithm and speeding up the process, in which case increasing the difficulty would protect the network at least for awhile (in terms of years of protection).  Even then, it would be wise to look at replacing the algorithm with something else.

That is ultimately the salvation for Bitcoins, and at some point in the future there will have to be a change in the basic algorithm used to creating blocks and used within Bitcoins.  We should be planning for that eventuality, even if now it is purely hypothetical.  The worst situation is an immediate and mandatory upgrade like happened to 0.3.9.

[theymos]

It depends on how the the SHA-256 algorithm is broken.  If somebody creates a quantum computer with 400 qubits and is able to create any arbitrary SHA-256 hash with any other prefix or expected "proof of work" with a Big O(1) level of difficulty, Bitcoins as a program would simply be screwed and potentially attacked as if somebody just brought on a million new machines into the network.

I did say "almost all cases". That would affect non-Bitcoin things, too. It'd be a case where everyone using SHA-256 is screwed.

[RHorning]

It depends on how the the SHA-256 algorithm is broken.  If somebody creates a quantum computer with 400 qubits and is able to create any arbitrary SHA-256 hash with any other prefix or expected "proof of work" with a Big O(1) level of difficulty, Bitcoins as a program would simply be screwed and potentially attacked as if somebody just brought on a million new machines into the network.

I did say "almost all cases". That would affect non-Bitcoin things, too. It'd be a case where everyone using SHA-256 is screwed.

In a worst-case situation, would the whole chain have to be restarted with a new genesis block, or do you think some algorithm from some arbitrary block number, say block 200000, would require the new hashing/cryptographically securing algorithm?

Apparently the NSA is trying to work on "stronger" hash algorithms and are willing to keep the effort to upgrade the algorithm as declassified material on the presumption that American civilians also need this kind of improvement to help protect network communications in general.  Undoubtedly there will be stronger algorithms found in the future, and there may also be something which avoids the use of prime factorization and other approaches which are currently used for securing these hashes.

Yeah, it will be something that will impact far more than Bitcoins, that is for sure.

[theymos]

In a worst-case situation, would the whole chain have to be restarted with a new genesis block, or do you think some algorithm from some arbitrary block number, say block 200000, would require the new hashing/cryptographically securing algorithm?

The chain will never be restarted.

SHA-256 is very strong.  It's not like the incremental step from MD5 to SHA1.  It can last several decades unless there's some massive breakthrough attack.

If SHA-256 became completely broken, I think we could come to some agreement about what the honest block chain was before the trouble started, lock that in and continue from there with a new hash function.

If the hash breakdown came gradually, we could transition to a new hash in an orderly way.  The software would be programmed to start using a new hash after a certain block number.  Everyone would have to upgrade by that time.  The software could save the new hash of all the old blocks to make sure a different block with the same old hash can't be used.

[slush]

Thank you guys, it answered many my questions. Simply, when hash will be broken, we will change algorithm.

[da2ce7]

"Breaking" Bitcoin's non-standard use of SHA-256 means finding a way of creating a proof-of-work hash without doing all of the normal hashing work. But in almost all cases, you would still have to do some non-negligible amount of work. All this does is make hashing quicker for you, and this is a problem that can be solved with difficulty adjustments.

"Breaking" SHA-256 is exactly like creating a new computer chip that can do hashing 20x faster per watt than everyone else.

It depends on how the the SHA-256 algorithm is broken.  If somebody creates a quantum computer with 400 qubits and is able to create any arbitrary SHA-256 hash with any other prefix or expected "proof of work" with a Big O(1) level of difficulty, Bitcoins as a program would simply be screwed and potentially attacked as if somebody just brought on a million new machines into the network.  It actually would be worse, as somebody with this kind of computing power would literally be able to create as many new blocks as fast or as slow as they cared, depending strictly on the speed of the computer to spit out new blocks.  This could conceivably happen in this situation about a thousand times per second or more, which would set up a DOS attack on the network like you've never seen before.  Difficulty could conceivably go to infinity in this situation and still not stop the flood of new blocks.  They would also all be valid new blocks, at least according to the current algorithm, and could not be rejected based upon increased difficulty.

Luckily, most current quantum computers are insanely expensive (that are genuine quantum computers) and have right now a dozen qubits as the largest register they are working with.  There is reason to believe that Moore's law applies to Quantum computing, so it is something to worry about in terms of future plans for the currency, but I put this on the order of an issue decades away, if even that.  It is also something which can be defeated at least temporarily by increasing the number of bits in the hash.

Quantum computers and in particular Shor's Algorithm (http://en.wikipedia.org/wiki/Shor%27s_algorithm) is a known weakness to encryption algorithms that depend on the public/private key method for them to work, of which the SHA-256 algorithm is certainly a member of that class of algorithms vulnerable to this kind of attack.   This algorithm isn't O(1), but it is awfully close.  What keeps it from being used is mainly a lack of hardware capable of carrying out the methodology, not a lack of ideas for it to work.

It is possible that some sort of conventional Von Neumann architecture-type computer (what most people call simply a "computer") would be able to "partially break" the algorithm where hashing would be made considerably easier than is currently the case.  In that situation, it would merely be a refinement of the algorithm and speeding up the process, in which case increasing the difficulty would protect the network at least for awhile (in terms of years of protection).  Even then, it would be wise to look at replacing the algorithm with something else.

That is ultimately the salvation for Bitcoins, and at some point in the future there will have to be a change in the basic algorithm used to creating blocks and used within Bitcoins.  We should be planning for that eventuality, even if now it is purely hypothetical.  The worst situation is an immediate and mandatory upgrade like happened to 0.3.9.

You can change the hash algorithm, the problem would be that the cypto that allows one to 'sign' a coin would also be broken, making bitcoin theft  possible.

[da2ce7]

You can change the hash algorithm, the problem would be that the cypto that allows one to 'sign' a coin would also be broken, making bitcoin theft  possible.

Maybe we should consider moving to something based upon http://en.wikipedia.org/wiki/Multivariate_cryptography for signing, as the hash can be changed, (made secure but making it longer).  The theft of coins is the real concern, as the network would be completely broken.