SHA v. 3 Algorithm Candidates Finalized

[RHorning]

An interesting article (via Slashdot) came up that I think is of interest to the Bitcoin community:

http://www.h-online.com/security/news/item/NIST-s-search-for-the-super-hash-just-five-candidates-left-in-SHA-3-final-1151325.html

I know that Satoshi has at least planned for this, but it certainly is worth a look.  What the non-geeks who use Bitcoin should know about this:  The NIST is conducting a strong mathematical review of these algorithms in an attempt to find their weaknesses.  It may be possible that these algorithms may be "better" than the current SHA v. 2 algorithm that is being used in Bitcoin currently.  In other words, think of it like a mathematical "safe" for your Bitcoins that can have a much stronger system that is harder to break apart, presuming these algorithms work out.

There has been an ongoing investigation and request for ideas on how to strengthen the SHA algorithm, with a sort of "contest" to the cyber-security community for quite a while.  This news is mainly that the list of candidates has been narrowed down and that some kind of final decision is going to happen "soon" in terms of which algorithm is going to be considered an "official" standard for hashing.

[da2ce7]

I like Grøstl, it is very cool. 

[grondilu]

An interesting article (via Slashdot) came up that I think is of interest to the Bitcoin community:

I think it's important to be ready for a change in the sha function when it's necessary.  It might require a change of both the software and the block chain, I guess.

However, there is no reason to jump into it until SHA256 is cracked.

I also hope it will not lead to any weirdness/incoherence in the code or in the blockchain.

What I'd like to see is a fork of bitcoin with this new hash function, so that people/market can decide which is better.

[Bruce Wagner]

I was just going to ask...  is the bitcoin app designed to allow an upgrade in the hashing algorithm?   And, yes, what would happen to the blockchain?

[galeru]

Bitcoin has powerful scripting capabilities I assume will just be expanded to include the new hashes for the security of actual bitcoins and transactions.

As for using SHA-256 as a proof of work, it doesn't really have to be collision-free, since the data that is hashed is pretty well pre-determined.  Since all that matters is that it's difficult to solve, I don't think the blockchain will need to be upgraded with a different hash.

[appamatto]

An interesting article (via Slashdot) came up that I think is of interest to the Bitcoin community:

http://www.h-online.com/security/news/item/NIST-s-search-for-the-super-hash-just-five-candidates-left-in-SHA-3-final-1151325.html

I know that Satoshi has at least planned for this, but it certainly is worth a look.  What the non-geeks who use Bitcoin should know about this:  The NIST is conducting a strong mathematical review of these algorithms in an attempt to find their weaknesses.  It may be possible that these algorithms may be "better" than the current SHA v. 2 algorithm that is being used in Bitcoin currently.  In other words, think of it like a mathematical "safe" for your Bitcoins that can have a much stronger system that is harder to break apart, presuming these algorithms work out.

There has been an ongoing investigation and request for ideas on how to strengthen the SHA algorithm, with a sort of "contest" to the cyber-security community for quite a while.  This news is mainly that the list of candidates has been narrowed down and that some kind of final decision is going to happen "soon" in terms of which algorithm is going to be considered an "official" standard for hashing.

I had been following this, and I was partial to CubeHash.  I hope they publish the reasons for dropping it soon.

CubeHash is cool because it is very tunable.  For bitcoin, you one could use a CubeHash with a high number of rounds and only one message block, like CubeHash32-1-512 (the exact notation has changed a bit recently...).  This would be bad everyday use, but for bitcoin it would add security without any real cost because CPUs are doing constant hashes anyway.

[RHorning]

I was just going to ask...  is the bitcoin app designed to allow an upgrade in the hashing algorithm?   And, yes, what would happen to the blockchain?

I'd have to dig through the archives for an exact quote from Satoshi, but the main thing would be trying to deal with the impact of having the current SHA v. 2 algorithm somehow attacked to make it trivially easy to create an arbitrary hash.  For example, the MD5 signatures, which unfortunately are still being used to prove cryptographic security on some software files, have a known weakness in its design where there are multiple numbers which can be used to create the same hash and in fact the hash can be "broken" if used in something like Bitcoin.  It is so bad of a weakness for MD5 that any certification authority based upon that hash algorithm should simply be ignored completely, including security certificates on "secure" http connections or software claiming MD5 certification.  I suppose it is better than nothing, but not much more than that and can be used to fool somebody into thinking that some software is much more secure than claimed.  The U.S. Government refuses to recognize MD5 as a valid hash for security purposes and insists upon the SHA v. 2 for all similar kinds of cryptographic security.

If a similar kind of exploit was ever found for the SHA v. 2 algorithm, "bitcoins" protected by such a hash could be "cracked" where any bitcoins protected by the hash could be spent before the "owner" has a chance to use them.  That would be the real danger here more than anything else.  Essentially anybody could create another "wallet" to at least be able to spend an arbitrary transaction.  It would likely take some considerable computer resources to get that done even with such a crack of the SHA v. 2 algorithm.

Depending on how bad of a cryptographic hole would be found, there could be either a transition period from the old to a new block recognizing previously created bitcoins or simply an abandonment of Bitcoin for some other system.  A more gradual replacement of the block chain would obviously be preferred spanning the frame of such a transition, and would likely happen over the course of a year or more in an ideal situation.  There are a number of ways that "old bitcoins" might be recognized with such a transition, and if a few "cracked" bitcoins came across too it wouldn't necessarily be the end of the world either for most people, especially if the bulk of the community came across early in the transition process.  It would still be an ugly process if that was to happen, and a few people complaining about their "identity" being cracked where they lost some of their money, even if that wasn't true and they were simply making that up to get sympathy from the community.

The important thing to note here is that a great many other people rely upon the same algorithm for many similar secure documents, and that there is at least an attempt to improve that security by people who really know what they are doing.

[davout]

I was just going to ask...  is the bitcoin app designed to allow an upgrade in the hashing algorithm?   And, yes, what would happen to the blockchain?

I'd have to dig through the archives for an exact quote from Satoshi, but the main thing would be trying to deal with the impact of having the current SHA v. 2 algorithm somehow attacked to make it trivially easy to create an arbitrary hash.  For example, the MD5 signatures, which unfortunately are still being used to prove cryptographic security on some software files, have a known weakness in its design where there are multiple numbers which can be used to create the same hash and in fact the hash can be "broken" if used in something like Bitcoin.  It is so bad of a weakness for MD5 that any certification authority based upon that hash algorithm should simply be ignored completely, including security certificates on "secure" http connections or software claiming MD5 certification.  I suppose it is better than nothing, but not much more than that and can be used to fool somebody into thinking that some software is much more secure than claimed.  The U.S. Government refuses to recognize MD5 as a valid hash for security purposes and insists upon the SHA v. 2 for all similar kinds of cryptographic security.

If a similar kind of exploit was ever found for the SHA v. 2 algorithm, "bitcoins" protected by such a hash could be "cracked" where any bitcoins protected by the hash could be spent before the "owner" has a chance to use them.  That would be the real danger here more than anything else.  Essentially anybody could create another "wallet" to at least be able to spend an arbitrary transaction.  It would likely take some considerable computer resources to get that done even with such a crack of the SHA v. 2 algorithm.

Depending on how bad of a cryptographic hole would be found, there could be either a transition period from the old to a new block recognizing previously created bitcoins or simply an abandonment of Bitcoin for some other system.  A more gradual replacement of the block chain would obviously be preferred spanning the frame of such a transition, and would likely happen over the course of a year or more in an ideal situation.  There are a number of ways that "old bitcoins" might be recognized with such a transition, and if a few "cracked" bitcoins came across too it wouldn't necessarily be the end of the world either for most people, especially if the bulk of the community came across early in the transition process.  It would still be an ugly process if that was to happen, and a few people complaining about their "identity" being cracked where they lost some of their money, even if that wasn't true and they were simply making that up to get sympathy from the community.

The important thing to note here is that a great many other people rely upon the same algorithm for many similar secure documents, and that there is at least an attempt to improve that security by people who really know what they are doing.

AFAIK, cracking SHA2 does absolutely not mean you can fake a transaction signature.
SHA2 security ensures that miners actually throw in some serious CPU resources.
If SHA2 was broken tomorrow, there would just be a freeze in the network, replacement of SHA2 and then back to business.
Seems like such an emergency case has been planned in advance by Satoshi by allowing broadcast to all the *official* clients of a message signed with his private key.

[RHorning]

AFAIK, cracking SHA2 does absolutely not mean you can fake a transaction signature.
SHA2 security ensures that miners actually throw in some serious CPU resources.
If SHA2 was broken tomorrow, there would just be a freeze in the network, replacement of SHA2 and then back to business.
Seems like such an emergency case has been planned in advance by Satoshi by allowing broadcast to all the *official* clients of a message signed with his private key.

It depends on how SHA2 was broken.  You might be able to "fake a transaction signature", as you certainly can do so if it was signed with an MD5 hash.  Back when MD5 was created, a similar kind of philosophy was suggested where it was thought that you needed incredible CPU resources to do a brute force attack.... and even for MD5 that is mostly the case.  But with some mathematical manipulation and narrowing potential candidates to break such a signature an MD5 hash can certainly be broken right now if it was used as a signature for transactions with Bitcoin.  MD5 hashes have been broken in such a way, and there hasn't been such a similar absolute mathematical proof that such an exploit is impossible with SHA v. 2.  All we know is that there is no public acknowledgement that such an attack has happened or anybody studying the problem who has come up with such an exploit.

Freezing the network only would work to help with an orderly transition from the SHA v. 2 network to whatever is decided upon for the replacement, if anything can be found at all.  It largely depends on how the hash was broken and how quickly "fake transaction signatures" can be generated from such an attack.  Presumably a more significant problem would be that block generation difficulty would skyrocket to insane levels where a series of valid nonces to create hashes of essentially all zeros would be the final block.  Block generation would also escalate considerably to the point that several blocks each minute, regardless of difficulty, would continue to be submitted to Bitcoin until the chain is frozen, indicating a problem with SHA v. 2 as an algorithm.  If you see the block count ticking up quickly after your client has been connected to Bitcoin for a while and you are pretty sure you have the strongest block chain fully downloaded, that would indicate the algorithm has been broken.

[Gavin Andresen]

This thread talks in detail about Bitcoin's use of hashing of ECDSA public keys to generate bitcoin addresses.

Executive summary:
  bitcoinaddress = RIPEMD-160(SHA-256(publickey))

So you'd need to break both RIPEMD-160 and SHA-256 hashing algorithms.  And the RIPEMD break would have to be quite extreme-- more than just "add some random data to force a hash collision" (which is how MD5 is broken), because it is hashing a SHA-256 hash, so you're not able to add some random data to be hashed.

[davout]

This thread talks in detail about Bitcoin's use of hashing of ECDSA public keys to generate bitcoin addresses.

Executive summary:
  bitcoinaddress = RIPEMD-160(SHA-256(publickey))

So you'd need to break both RIPEMD-160 and SHA-256 hashing algorithms.  And the RIPEMD break would have to be quite extreme-- more than just "add some random data to force a hash collision" (which is how MD5 is broken), because it is hashing a SHA-256 hash, so you're not able to add some random data to be hashed.

Maybe I'm missing something here, but I'm confused... How would getting knowledge of a public key be even remotely dangerous ?

[Gavin Andresen]

Maybe I'm missing something here, but I'm confused... How would getting knowledge of a public key be even remotely dangerous ?

If the hashing algorithms are broken I might be able to generate an ECDSA private/public key pair where the public key hashes to the same bitcoin address as one of your public keys.

If I can do that, then I can spend your coins.

On my list of things to worry about, this is just below "Asteroid impact destroys the earth" (but above "Aliens invade and make me their slave").

[Hal]

Actually one of the criteria for SHA-3 is speed, which is not particularly important for Bitcoin. We might consider using a different approach.

http://en.wikipedia.org/wiki/Provably_secure_cryptographic_hash_function

These hash functions are slow but have a degree of provable security.

There have also been various proposals for proof of work (POW) systems, including some that were designed to resist hardware optimization. Perhaps this could produce "fairer" generation where graphics cards and specialized hardware wouldn't have such an advantage. (However people with access to large networks of computers might dominate then.)