Bitcoin Forum

A mathematician friend of mine pointed out that there are very few if any hash protocols that have survived for 10 years or more. What would Bitcoin's solution be if SHA256 were to be cracked tomorrow?

I don't think that broken cryptography could ever be the end of BitCoin if it becomes popular. Since the block chain can be forked without losing too much data, modifications to all aspects of BitCoin are possible. If SHA-256 was broken, a new version of BitCoin would be released that would switch to a stronger hash function for addresses. Changing the hash function used for blocks might not be necessary if the weakness still required some non-trivial amount of computation. The new version would ignore SHA-256 blocks after a certain point in time, but most old transactions would survive.

In case the weakening of SHA-256 is gradual instead of sudden (much more likely, IMO), BitCoin could stretch the process of switching to a different hash algorithm over a long time. First accept SHA-512 (or whatever) in addition to SHA-256, then use SHA-512 by default, and finally stop accepting SHA-256 for new blocks.

Wouldn't the users lose their coins?

So it's possible to switch "on the fly" to a new hash function? Wouldn't all the old transactions then be compromised (because they could be trivially recomputed)?

SHA-256 has already been weakened by a factor of 16 (according to my friend. I can't find documentation on that, but I trust him). That's 16 out of 2^256, so not a huge deal, but still.

After thinking about this some more, I've realized that breaking the hash function used in blocks would be more disastrous than I had originally thought. But it should still be possible to change the hash function "on-the-fly" by including secure hashes of each real block in the old chain with the new BitCoin release. Some mechanism of doing this (hopefully more elegant) would also have to be used for a gradual hash change.


Everyone's balance is publicly available, so it should always be possible to preserve this data, no matter what changes are made to BitCoin.

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.

SHA-1 lasted over ten years before being significantly weakened. Now, even 15 years in, full SHA-1 still has no known collisions. RIPEMD-160 has also held up for over ten years, as has GOST, Tiger, and probably others.

As I understood it the Hash algorithms that are used are completely replacable, and should the demise of SHA-256 become apparent we could switch to another Hashing algorithm, starting a new chain, and users would buy that new currency with their old coins, creating an inflation of the old coins and creating request for the new version, just like creating new services that rely on BC does now.

I don't think moving to a new version would be hard  ;D

or you just grandfather the current blockchain to be accepted against their SHA256 hashes but also reject any new valid SHA256 hashes.

When you think about the number of possible hashes and hash collision; it only becomes a problem if the collision you find (if by accident or on purpose) actually matches someones account. If everyone person on the planet had a BitCoin address, your odds that a collision is going to be someone's account is still so small as to make the use of it impractical.

When you can target a specific BitCoin address with the collision, then it becomes a problem. Otherwise, you're likely to end up with an account that has only 1BTC in it or no account at all.

According to my current understanding of how Bitcoin works (admittedly sketchy), if SHA-256 is broken in such a way as to decrease the difficulty of computation by (say) 5 orders of magnitude, then the difficulty factor could be adjusted by 5 orders of magnitude.   Same way it responds if a bunch of fast machines start generating blocks all of a sudden, only measured in orders of magnitude instead of just a factor of two or five or so. 

I guess the "breaking" part comes in because the Byzantine agreement part would fail since a guy who is secretly breaking Bitcoin's SHA-256 would be dominating the "computing power" and thus have more than the 50% of the resources needed to forge transactions?

So would the world stop all transactions while a patch is developed and put into place, then once that's done, ask everyone to recreate their transactions from the point of discovery onwards? Let's say it's a large organisation and they put through 10,000 transactions an hour - that could be a lot of work to redo.



Let's hope quantum computing theory doesn't become reality then.

If the hash were broken, the merkel tree hashes seem to be the place to attack. The transaction signatures are even based off of these, so you might be able to fake a signature of another transaction. I'm not sure if this is possible (would require a lot of thinking I'm not capable of right now).

Anyhow... The reason why I'm posting is that I think this is not an issue. Hashes are traditionally broken gradually. If we wanted to change the hash function, I think the steps would be:
1) New client distribution.
2) New client starts/requires new hash on transaction after date X in order to consider them valid. (old versions stop working if enough people shift to the new version)
3) New client issues transfer to self of old bitcoin with new hash.

The new client would prioritize (ie, proof-of-work would be greater) on all transactions that include a new hash, so trying to fork off a transaction on an old hash would not get you anywhere.

I'm actually more worried about the eventual weakening of the signature. They are using ECDSA, supposedly. It seems the best place to attack would be on a wealthy accounts private key. I think the recommendation from the experts is to use RSASSA-PSS. See: http://www.bsdcan.org/2010/schedule/attachments/135_crypto1hr.pdf

I guess all these things are easy to fix after a few people get eRobbed (just create a new address and transfer to yourself). Plus it's easy to see who you got robbed by. I think we should have a user entered blacklist, so if it makes some high priority news, you can effectively "taint" some money such that no one will generate a block with transactions from that account in it. That would provide at least a theoretically disincentive to a would-be robber.

I would say, as good practice, we all get used to _NOT_ using the address book feature. This should probably be removed, and you should just get the latest address from the other party through an alternate channel whenever you want to send them BTC.

When the SHA-3 winner is announced, and after some time in real use, would it be a good idea to switch to that?

The winner of this year's necromancy award is thesam !
------------

SHA1 even with its weakness still requires a large amount of computation to be broken.
So it's reasonable to think that SHA-256 even with weakness will require very large amounts of computation to be broken.

Still, that of course won't fix the quantum computer problem, but when quantum computers come, we will have much bigger problems - such as SSL/SSH will be useless.

I like Grøstl it seems to be the best hash of the lot.

Despite some of the oversimplified solutions earlier in this thread, "switching" to a new hash means creating a new (possibly derived from the existing one) protocol and an entirely new network (possibly based on a genesis block offering BitCoin funds to the SHA-256 addresses that had them outstanding). Back in 2010, there was only a single client, and reinventing everything may have seemed like a simple solution. But beginning with 2011, we are starting to see alternative implementations of BitCoin, and by the time SHA-256 is broken, we will no doubt have many various possibilities. If SHA-3 is due out soon, it might be early enough for all the implementors to agree on reworking the network around it...

Not really true, we can define a future switch block, after which a new set of rules applies. If all developers are notified early enough they can make the switch, and allow time for users to make the switch, when the block arrives old implementations will fork off creating their small network, while the new clients take over the main chain (assuming most of users have made the switch).

Evolving the system is hard, but it's not impossible. It would however be nice to have a nicer protocol (yes I know, I've been saying that for ages :D)

No. As long as SHA-256 is used for any blocks in the chain, the entire chain is compromised by a client forging a new block that can sit in-place of the real one in history.

So lets say I can create SHA-256 collisions fairly easily, and I want to replace an old transaction somewhere in the block chain.

I create an alternate version of the transaction with the same hash... and then?  Whenever clients happen to connect to my node to get old transactions I feed them the bogus version?

How do I get a majority of the network to accept the bogus version as valid, when the majority of the network probably already has already downloaded the old, valid version?

Same question if I'm creating duplicate (old) block hashes instead of duplicate transaction hashes.


I suppose I could try to double-spend with two transactions that hash to the same value... and hope that the merchant's bitcoin accepts Transaction Version 1 while the majority of the rest of the network accepts Transaction Version 2 (where I pay myself).   But if SHA-256 ever gets close to being broken I'm sure bitcoin will be upgraded so new clients only accept upgraded hashes for new blocks/transactions.

Wouldn't changing the hash to SHA-512 or 512-Bit Whirlpool (http://en.wikipedia.org/wiki/Whirlpool_%28cryptography%29) let's say.... from block 250.000, before anything is broken yet a wise move ?
Also, we could double private/public key lengths... just in case.

I mean that would give us extra reaction time in the event of quantum computers are invented or something else got broken...

RE: changing things now "just in case" :

No, I think it would be dumb to switch hashing algorithms or public/private keylengths now, for at least two reasons:

1. You'd just be switching from older technology that has the advantage of being well-tested and "battle-hardened" to something newer that you THINK will be more secure.

2. There are much more important things to work on.  If you know enough about crypto to evaluate whether Whirpool really is fundamentally more secure than SHA-256, please apply your knowledge to the problems we have right now, like making users' wallets more secure against trojans and malware...

SHA-256 will not be broken suddenly. Even SHA-1 has not yet been completely broken, but has gradually become considered less secure. We'll have plenty of time to switch to a newer hash. Maybe we'll do it at the same time we lift the 32-bit timestamp limit...

The SHA-3 candidates are more likely to be completely broken than SHA-256, since they are new.

OK, agreed. That answers first part of my question.

So about the second part:
What about making public/private keys longer without changing hashing algorithms ?

PS.
Truecrypt uses Whirlpool almost from the beginning, i don't know if that makes the algorithm more trustworthy or not however.

PS2.
I just thought that by changing Hashing algo from SHA-256 to SHA-512 we are essentially increasing security, because that is simply the same algorithm, just with longer output.

This is why I left it open ended on time, and said after it saw real world use.
My idea was more of a long term idea.
Just wanted to know if the system would allow for a new hashing algorithm in the future.

If not for anything else, then for its name — yummy!  :)

Cheers,

It might be nice to add OP_WHIRLPOOL etc. to Script to ease a switch if one is ever needed.

Well, it sounds like a flag would be nice in this situation.

Value 0 = "classic" hash
Value 1 = sha512
Value 2 = whirlpool

What if the network could theoretically accept different hashes  (and perhaps different pub/priv keylengths ?)

I don't know If I'm thinking right here, because I'm not actually a C/C++ programmer.

That was my initial thought, but it won't help the fact that the tx and block itself are hashed with SHA-256...

Yeah, I suppose. I was thinking some transactions wouldn't need to be re-signed, but transactions use SHA-256 in inputs.

Sounds like a bad idea to me.  Instead if 1 security problem, you have 3. Security will be always as strong as the weakest hashing method you can choose.

Correct, the right way is to force inclusion of more than one hash.

+ 1
Well, didn't think of that.

EDIT:
Gentoo Linux (which I am a proud user of) uses this approach to decrease possibility of collision even further.
Gentoo's package management ford SHA-256 + SHA-1 + RMD 160 + size checking for every file.

Interesting discussion, hate to see it stopped there. Having 2 levels of hashing with different algorithms will be much safer.

In the New to BitCoin thread (http://forum.bitcoin.org/?topic=7269.0) it says

The cryptography used in BitCoin is so strong that all the world's online banking would be compromised before BitCoin would be, and it can even be upgraded if that were to start to happen.  It's like if each banknote in your pocket had a 100-digit combination lock on it that couldn't be removed without destroying the bill itself.  BitCoin is that secure.

I sensed a lot of complacency here. What it didn't mention is bitcoin network is much more accessible than online banking systems, which usually are monitored by security staff. 

If SHA256 is suddenly broken -- however a remote possibility it is -- very likely the fully automated Bitcoin network will suffer the most, as SHA256 is THE cornerstone bitcoin is built on, and all the eggs are in one basket. The banking industry on the other hand has many ways to make human intervention under similar circumstance. If all online banking service is  shut down, they still can run computers on their private network and physically secure the communication lines.

Please excuse my paranoia but unfortunately with the appreciation of btc, a single private/public key pair can now hold millions dollar of value, the incentive for finding and hacking any weakness has increased exponentially too

If SHA256 is "broken" there will be lots of research papers warning of it in plenty of time to update the algorithm. Or maybe the NSA will break it and keep it secret. Or maybe a giant asteroid will crash into the earth and wipe everyone out.

Re: quantum computing...
http://venturebeat.com/2011/05/27/first-quantum-computer-sold/

:D

Shor's Algorithm.  A quantum algorithm which can evidently be used to break RSA encryption.  $10M for a quantum computer is not a lot of money to many corporations or even individuals.

http://en.wikipedia.org/wiki/Shor's_algorithm

Just when you thought it was safe to go back into the water.

Would this actually a possibility?

For example make the "Hash" field of blocks 1024 bit long and include a SHA256, a 512 bit Grøstl hash, and 2 128bit whatever hashes.
To forge a block, you would then need to find something that has the same SHA256, Grøstl and 2 other hash values. This should be tough even with already "broken" hashes like a MD5 + CRC32 simultaneous collision.

Also it might make mining a bit more difficult, which is actually a good thing, as this makes it more accessible --> CPUs could for sure easily handle it and it makes mining less likely to be overrun by just a shipload of ASICs.

This past discussion is related to this topic:  http://forum.bitcoin.org/index.php?topic=360.0

this is just false, and it's unfortunate that people often claim this. it applies to the public-key encryption that bitcoin uses but to no other feature of the system. 'all the world's online banking' does not depend fully on sha-2 for its security, for example.

sha-2 is likely secure for the foreseeable future (although there's too much complacency around certain features of its use in bitcoin), so it may not make much difference in practice. i just hate to see the repetition of the false comparison between bitcoin and the security of unnamed 'banks' when it's patently false.