Bitcoin Forum

Hello,

So my understanding is that Bitcoin relies at its core on SHA-256 to ensure it is secure and works. Since RIPEMD-160 is just a shortening layer, and nobody seems to worry about the ECDSA secp256k1 curve, let's talk about SHA-256 and Bitcoin.

It is just a matter of time before SHA-256 gets broken. By brute-force we are fine (centuries, or centuries/2 with quantum computing).
But what about flaws in the "design", like every other cryptographic hashing algorithm before, it will be broken down by cryptanalysts. Question is when? 5 years? 10 years?

2nd Question: how is Bitcoin network going to react? Are there already plans for this?

Some links I gathered while quicksearching on the subject:
http://security.stackexchange.com/questions/6458/security-of-sha256-and-bitcoins
https://bitcointalk.org/index.php?topic=18211.0
https://www.google.com/search?q=quantum+sha256
https://bitcointalk.org/index.php?topic=3008.0
http://en.wikipedia.org/wiki/Post-quantum_cryptography
https://bitcointalk.org/index.php?topic=7769.0
http://en.wikipedia.org/wiki/Comparison_of_cryptographic_hash_functions#Cryptanalysis

Every world cryptographer has no reservations about SHA-224, SHA-256, SHA-384 or SHA-512, which is why a few of them including Bruce Schneier (who submitted Skein) thought the new SHA-3 standard wasn't necessary just yet, but NIST chose one anyways a month ago. http://csrc.nist.gov/groups/ST/hash/sha-3/winner_sha-3.html

I would assume bitcoin is fine, and they can probably go to SHA-3 whenever it needs to be done

SHA-1 is the problem http://www.schneier.com/blog/archives/2012/10/when_will_we_se.html
"A collision attack is therefore well within the range of what an organized crime syndicate can practically budget by 2018, and a university research project by 2021"

If SHA-256 is ever found to have a flaw, it won't allow anyone to spend or "steal" your coins.  It won't allow someone to create counterfeit coins. It might allow someone to increase the number of coins they mine, and it might allow someone to double-spend coins that they own, but the bitcoin community is aware of this weakness and is likely to notice if something like this starts to happen.

Changing the proof-of-work hashing algorithm would be a pretty significant change, but if it is discovered that there is a weakness in SHA-256, there would be enough incentive that it would likely be accepted by the community and a new proof-of-work algorithm would likely be implemented pretty fast.  Until it was, spending bitcoin through the blockchain might be a bit difficult (since people would be wary of accepting bitcoin that might be double-spent).

Of course if we are talking about 10 or more years from now, a large percentage of bitcoin denominated transfer may not go through the blockchain, so that the delay waiting for a new proof-of-work algorithm might not significantly affect the ability for individuals to engage in commerce.

Catastrophic breaks in hashes are pretty much unheard of these days.  What happens is that they get weaker gradually, with plenty of warning.  For example, MD5 is considered to be totally broken now, and should never be used.  On the other hand, if it was used in bitcoin transactions, those transactions would still be totally safe, for at least a few more years, because all of the attacks require conditions that can't be met in the bitcoin system.  As in, if we changed one of the NOPx opcodes to OP_LOL_CHECKMD5SIG which used MD5(MD5(key)) instead of RIPE-MD160(SHA256(key)), it would still take decades to crack, probably centuries.

And your estimate of how long a brute force attack on SHA-256 would take is wrong, it isn't centuries, it is billions and billions of years, minimum.  If you converted the entire mass of the sun into energy, and used all of that energy to increment a counter using the absolute limit of physics for minimum energy used to flip a bit, you'd get to around 2²²⁵.  You'd need 2³¹ suns of similar mass to finish just iterating through all of the possible inputs.  So, billions of stars, or trillions or quadrillions if you want to actually perform the hashes too.

There are no "plans" exactly, on what to do next, but it is widely understood that we can swap out the primitive operations when needed.  We might not be alive then, why should we presume that the people that will actually be doing the work want to follow our plans instead of making their own?

Hash twice? Oh, wait, already done...

I completely agree with what you are saying.
It seems very true.

If I had to make a list of risks to Bitcoin, flaws in any of the underlying mathematical primitives would be right at the bottom. ECC is old enough now that it's been widely studied. You do see breaks in very new forms of cryptography like pairing-based crypto, but ECC seems ok.

Catastrophic failure is far more likely to be caused by unnoticed bugs in the implementation. Bitcoin is phenomenally complicated and there are many subtle ways to break it.

DoS attacks, problems with the way people use the software: not using encrypted wallets, malware that can steal from encrypted wallets, privacy leaks, failure to make backups, etc. All of these can give Bitcoin a bad name and scare people away.

A collision or preimage attack on SHA256 wouldn't have any effect on bitcoin, as far as I can tell. This does not increase the brute-forcing ability of finding m + nonce where h < difficulty.
A collision attack on RIPEMD160 would be worrisome, but you still need to know the private key of the public key being hashed, and private key ECDSA operations are many magnitudes slower than hashing.

worst case we would have to do some kind of rollback.

I hear this a lot, but is it really true?

You can't print BTC without sha256 and you can't steal peoples money without EC. Both are very secure as has been noted - even algorithmic weaknesses would likely only lower the brute forcing time, not remove it.

Sure you might scam and cheat a few guys clients if you found some bug or isolated them, but is there really something that could cause a complete breakdown when the 2 main principles are SO iron clad?

Now light clients and online wallets is another story... what we need is faster/smarter clients so everyone can do some verification.

There are plans: The "important people" meet online and make overnight hard fork to some other hashing scheme.

.. while persisting the blockchain db backups prior to the crash as hardcoded into the new fork.

The effect would be minor I think.

Effect on bitcoin network and security might well be minor.

However: effects on other stuff that uses sha-256 that can't be switched quickly might be major, no?

The only problem to worry now and in the future about is user incompetence - looking at the amount of hacks (or 'hacks' - see this thread: https://bitcointalk.org/index.php?topic=83794.0;all ) an average user or business owner knows little about protecting himself from losing BTC. I am afraid this will not change as more and more people are drawn into bitcoin. I believe this is where the Bitcoin Foundation could start doing something.

SHA-256 does have a flaw:  I don't understand it.  If you cant explain it to me then it is too complicated.

maybe this helps to figure it out?

nick@zero ~ $ echo "123" | sha256sum
181210f8f9c779c26da1d9b2075bde0127302ee0e3fca38c9a83f5b1dd8e5d3b  -
nick@zero ~ $ echo "124" | sha256sum
ca2ebdf97d7469496b1f4b78958f9dc8447efdcb623953fee7b6996b762f6fff  -
nick@zero ~ $ echo "125" | sha256sum
a5e45837a2959db847f7e67a915d0ecaddd47f943af2af5fa6453be497faabca  -
nick@zero ~ $ echo "verylongdatalongerthaneventhechecksumitselfjustaddingrandombitsnow9823480293849 20834092834029834029834028934092834" | sha256sum
3dff4001b5954d595b6d6b3a4ec3971c2eef82da397e6a81a514090052918ed7  -

now let's mine for a bit

nick@zero ~ $ for nonce in {0..999}; do echo $nonce x`echo $nonce | sha256sum`; done | grep x00
691 x0024839ec9632d382486ba7aac7e0bda3b4bda1d4bd79be9ae78e7e1e813ddd8 -
964 x00ae0900e3ba03583e3561d76de50754935c10913065d737f9cf4c8e86e54bda -
996 x009cbb4830299d01fc84a6a56d4f07707d7d073673f6cde576027bafbac75168 -

ah, found 3 blocks, cool

Ugh, no they can't. Since ASIC devices will be obsolete then. And if they are as expensive as today, well you can guess what happens then.

I think there will be pressure not to change the protocol even if such a need arises because so many people have invested in ASICs (and AFAIK in most cases those ASICs cannot be repurposed to do anything other than mine Bitcoins). I hope this does not kill Bitcoin one day.

In general, everyone can mine the chain he wants to mine. If sha256 is "broken" ("easily collidable"), there is no sense to use ASIC. They are instantly worthless scrap because the sha256-fork can be "fake-mined" with no effort.

So that "pressure" you're talking about is like demanding noone was to mine any other chain. That's absurd.

There are two parties, those heavily invested in gpu mining and those who preordered and heavily invested in asic mining.
EDIT: Guess the asic manufacturers are sitting on a unpredictable risk when a algo change is seriously considered at anytime.

thing is: it isn't likely. In fact I'd go as far as saying: it's totally predictable: won't happen.

the greater risk is bitcoin failing and that's not great either.

biggest risks for ASIC manufacturers are, in order of decreasing severeness:

• fail to deliver due to fuckup
• problems/delays in production
• competition
• exchange rate crash will diminish new orders

I did not necessarily mean SHA256 would have to be broken, a flaw somewhere else in bitcoin or problems with scalability (or anywhere else) might one day make it more convenient or safe to adopt some changes to the protocol.


Those heavily invested in GPU mining are fortunate enough to be able to use their GPUs for other purposes or simply sell it.
They can only hope that by the time that happens they will have paid off their hardware and the difficulty increase will require even faster ASICs to remain profitable.

In that case I agree: there will be much pressure not to do it. Changing the protocol for convenience or some little safety is probably not worth the loss of trust that would ensue.

Such a transition wouldn't need to be sudden.  For mining, which will probably never be broken, there is no reason why we couldn't accept two different hash schemes with a sunset of the old hash scheme many years in the future.

Do you mean a rule like: the block is valid if it has sha256 proof-of-work of difficulty x OR SHA3 proof-of-work of difficulty y?

That would not make much sense in the supposed case of sha256 being broken.

https://en.bitcoin.it/wiki/Contingency_plans#SHA-256_is_broken

True, it wouldn't make much sense in that case.  But I'll bet you every single bitcoin that I own that there will not be a catastrophic break in SHA256 that makes a change in the mining scheme urgent on a timeline of less than a decade.

MD5 is hopelessly broken, but none of the attacks would help with mining.  I am very, very, very confident that SHA256 will not suffer a catastrophic break even worse than what has been found with two decades of work on MD5.

I'm with you on that one. Totally hypothetical discussion we're having here. We must be bored.

I think that is a good thought experiment:  If you replaced all uses of SHA256 in Bitcoin with MD5, what attacks would be possible? (please check my work, I am not an expert on hash collisions)

Well, to generate a collision (http://en.wikipedia.org/wiki/Md5#Collision_vulnerabilities):

Block hashing would be safe, for now; the block header that is hashed is only 80 bytes long, much less than the 128 bytes of wiggle room needed to find a collision.

I believe an attacker could easily produce two different non-standard transactions that hashed to the same txid. That would be a disaster, they could split the blockchain and/or double-spend by broadcasting one version of the transaction to half the network and the other to the other half of the network.

To split the chain the attacker would mine a block containing the 'poison' transaction hash, and then broadcast two versions of the same block, containing the two different-but-same-hash transactions. Half the network would think that block contains 't1', and half 't2'.  Everything would be just fine until the attacker spent the outputs of t1 and/or t2... then Bad Things would happen.

Double-hashing doesn't help at all:  If HASH(t1) == HASH(t2)  then HASH(HASH(t1)) == HASH(HASH(t2))

---

I do agree with everybody who points out that SHA256 isn't close to being broken. If it does ever start to get close, then I'm sure we could figure out a backwards-compatible fixes and phase them in (something like "a block's coinbase transaction must include a SHA3-based transaction merkle root", create a new version of OP_CHECKSIG that used SHA3, roll out a new alert system that used SHA3, etc).

Heh, I meant safe for my transactions, not safe for the network.

Also, I'm not sure that the known collision attacks would work for a transaction.  The two examples given are for Postscript and X.509, both of which are notorious for allowing arbitrary garbage.  I'm not sure that the garbage hiding capacity of bitcoin transactions will allow the necessary alignment.

If sha-256 was "broken" in the way md5 is "broken"  (possibility to create a collision if certain prerequisites are given), would this imply that it's also easy to find nonce so that md5(nonce+data) < diff ("create a collision with 0000000000*")?

I'm not sure wether or not "easy collision-finding" implies easy mining, but it might be true (maybe depending on the algorithm used).

I can't even judge which might be harder to accomplish: "easy collision-finding" or "easy mining".

Thanks Gavin for reminding me about the same-hash-transaction-construction-attack, I hadn't considered this here up to this point.

In case easy collision finding implies easy mining, that attack is moot, though, because the chain will be dead anyway due to cheap mining.

No, it doesn't imply that at all.

As far as I know, no one has ever actually tried to attack a hashing algorithm in a way that would make mining easier.  But all hashing attacks require certain freedoms in the inputs, and the scheme we use for mining doesn't really give an attacker much room to work with.  Go look at the header (https://en.bitcoin.it/wiki/Block_hashing_algorithm) and think carefully about where each field comes from and how much freedom an attacker has to change it.  The Merkle root in particular is a pain in the ass.  Even if you could run SHA256 backwards and create valid inputs from desired outputs, you'd still have the problem of creating valid(!) transactions for those hashes.

The most realistic attack would be a statistical test that could estimate the likelihood of finding a valid block if we iterate all 2³² possible nonces.  If this test was 100% accurate, the attacker could just change his generate transactions until he found one that the test said would produce a block, and then iterate the nonces.  If a test like that was discovered, and then kept secret, the holder of it could monopolize mining.

Just not being secret is enough to mitigate this attack.  If the test is public, everyone will use it, and difficulty will quickly scale up by a factor of 4 billion.  No big deal.  But in reality, the test won't be perfect, it will be weak, and again, difficulty scaling works off of the apparent hashing power of the network, and this would just make the network appear to be hashing faster than it really is.

Assuming the collision of HASH(t1) and HASH(t2) is performed with MD5 and

[t1 - in hex]
d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f89
55ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5b
d8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70

[t2 - in hex]
d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f89
55ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5b
d8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70

then the collision hash is: 8bcec679bc54a3634116e859d16c32d4

but if instead of HASH(HASH(t1)) we do HASH(HASH(t1)+t1) (where the + means append) then we get:

HASH(HASH(t1)+t1) = 3d4d97fb6f2b9638a4b881e7db1aefaf and
HASH(HASH(t2)+t2) = 78849bd73dda9f9c1a946d06766d08f2

So maybe one possibility down the track would be to change the double hashing technique?

oh, ok. Then it indeed makes sense to think about what would be possible to do with a collision attack.


So "easy mining" attack tends to be harder and less likely to be found than a collision attack? Makes even more sense then to think about the implications.

I can't really judge this, but assuming md5 was used in bitcoin seems to be a good way to think about that.

Except that bitcoin is sha256(sha256(x))

But does a hash value like HASH(t1) actually appear anywhere? In practical Bitcoin situations, we only have double-hash values like HASH(HASH(t1)), right?

I'd consider a Hash algorithm 'broken' if, for a given hash value H, we can generate data G (within reasonable time) with HASH(G)=H.

But if SHA256 gets broken, it would by no means imply that the double-SHA256 used by Bitcoin was also broken.

Yes, I agree that (regardless of the fact that SHA256 is not even remotely close to be broken in any way) this kind of 'nested double hashing' would have been safer. Also because it avoids loss of entropy that the current double-hashing suffers from (even though it's probably insignificant).

The example was taken from molecoin, a new altcoin I invented to explain stuff to people within the limits of an 80 column terminal.

This is why it's important not to allow the transaction to end with arbitrary data. The MD5 collision attack basically renders any previous blocks, in the data being hashed, irrelevant. You can construct a 1KB and a 1GB file with the same hash, as long as you can put in a certain 128 byte block at the end that is aligned on a 64-byte boundary (as far as I understand).

I think you mean at the beginning because when I tried MD5(t1+MD5(t1)) it produced the same hash as MD5(t2+MD5(t2)).

For what values of t1 and t2?

These ones (found them doing a search for the shortest MD5 collision):

so t1 = t2. doesn't suprise that anyfunc(t1) = anyfunc(t2), right?

that's not a collision. for a collision t1 != t2 and func(t1) = func(t2) must be true.

If you look even more closely you'll see there are other differences also. :)

molecular,

Take another look.

oh, holy shit... I'm sorry!

No worries - initially I thought they looked the same as well (and ran a diff against them to be sure they were not).

:)

maybe this is relevant: Double hashing: less entropy? (https://bitcointalk.org/index.php?topic=86947.20) (also contains suggestins of chaning double hashing scheme)

Meni, sipa, Gavin and more big brains talk there, so I don't understand enough to even evaluate the relevance ;)

Now back to the economy subforum where noone really notices that I don't have a clue what I'm talking about.

Of course, MD5 is a sequential algorithm. So if MD5(t1)=MD5(t2), then also MD5(t1+x)=MD5(t2+x) for any random data x. Whereas MD5(x+t1)≠MD5(x+t2).

I think the same holds for Sha1 and Sha2 (including Sha256), however no Sha1 or Sha2 collisions are known.

I guessed so (but lack the mathematical skills to know for sure) - the idea was to change the "double hashing" approach so that even if collisions can be found it won't help (unless you can work out collisions that satisfy the "appended double hash" approach which I assume must be much more difficult).

Irrelevant Stuffs:

October 2, 2012

The National Institute of Standards and Technology (NIST) today announced the winner of its five-year competition to select a new cryptographic hash algorithm, one of the fundamental tools of modern information security.

The winning algorithm, Keccak (pronounced “catch-ack”), was created by Guido Bertoni, Joan Daemen and Gilles Van Assche of STMicroelectronics and Michaël Peeters of NXP Semiconductors. The team’s entry beat out 63 other submissions that NIST received after its open call for candidate algorithms in 2007, when it was thought that SHA-2, the standard secure hash algorithm, might be threatened. (http://www.researchgate.net/publication/225616238_A_combinatorial_analysis_of_recent_attacks_on_step_reduced_SHA-2_family) Keccak will now become NIST’s SHA-3 hash algorithm.

“Keccak has the added advantage of not being vulnerable in the same ways SHA-2 might be,” says NIST computer security expert Tim Polk. “An attack that could work on SHA-2 most likely would not work on Keccak because the two algorithms are designed so differently.”

Polk says that the two algorithms will offer security designers more flexibility. Despite the attacks that broke other somewhat similar but simpler hash algorithms in 2005 and 2006, SHA-2 has held up well and NIST considers SHA-2 to be secure and suitable for general use.

What then will SHA-3 be good for? While Polk says it may take years to identify all the possibilities for Keccak, it immediately provides an essential insurance policy in case SHA-2 is ever broken.

Block 300,000+ hash: SHA3((SHA256(SHA3-tree))) = Your ASIC is obsolete. Discuss.

It probably won't happen that way.

Unless there is a good reason to abandon SHA-256 quickly, we could, for example, accept blocks that meet the difficulty target using two (or more) different hash schemes.  This would allow old hashing gear to keep operating while a new scheme is brought online.

not without damn good reason.

while that increases security against collision attacks, it decreases security against mining shortcuts.

That's a huge complication in preparation for a solution to pretty much a non-problem. If there are problems with sha256 we just switch, which we would have to to even with your preparation, right?

It seems I was wrong. The only thing that can be done is add an arbitrary, but identical, prefix to the 128 byte block in question:

"Furthermore, current collision-finding techniques allow to specify an arbitrary prefix: an attacker can create two colliding files that both begin with the same content." (1) (http://en.wikipedia.org/wiki/Md5#Collision_vulnerabilities)

An abrupt change in hashing schemes would be very costly.  If a huge flaw was discovered in SHA256, that cost would be worth it.

But without a flaw, there is no reason to rush.  My scheme would allow new devices to start up gradually, and allow old devices to fade out gradually.

But the difficulty of SHA3 surely won't be the same as SHA2, so the target can't be the same. If SHA3 is more difficult, no one will use it, if SHA3 is less difficult, everyone will use it. Adding a separate target for each algorithm will add a whole bunch of headaches.

SHA-3 is more efficient than SHA-256 as far as I know. But it wouldn't become an advantage until we have SHA-3 ASICs (assuming that SHA-256 ASICs are widespread when this were to happen) since it's not that much more efficient.

found this from a quick search: http://www.ecrypt.eu.org/hash2011/proceedings/hash2011_07.pdf

They actually set up FPGAs to test, and Keccak is actually 5-6x faster than SHA2. I don't feel like reading the paper in-depth, so I don't know how much data they were testing or how this might apply to GPUs, but slightly interesting nonetheless.

And as far as ASICs go, again things just boil down to which algorithm is faster (in whichever manner you mine) deciding who will mine with which algorithm, it won't do anything to ease the way into SHA3.

Right. But the point is that with this setup (allowing both SHA-256 and SHA-3 proof-of-work) as long as SHA-3 ASICs don't exist and SHA-256 ASICs do, no one will use SHA-3. So there would be a softer transition from SHA-256 to SHA-3, than there would be when defining some hard cut-off point (where SHA-256 POW is no longer valid).

There would be no difference between this and simply making a cut off point at some point down the road, IMO, as you say yourself no one will use SHA3. It is pointless and adds unnecessary complexity.

I do think there would be a difference. Developing SHA-3 ASICs and targeting the release date to exactly when the cut off point occurs is pretty damn difficult. If people were told that SHA-3 can now be used, businesses would slowly start developing SHA-3 ASICs, and they would be able to put them to use as soon as they finish development.

Ah that's true, my bad.

If the transition is made to another hashing algorithm, such as Sha3, I hope (for reasons discussed here (https://bitcointalk.org/index.php?topic=86947.0;all)) it will be Sha3(Sha3(x)+x) i.e. 'nested' double hashing, rather than just Sha3(Sha3(x)). Or perhaps Sha3(Sha256(x)+x).

Couldn't find this (https://en.bitcoin.it/wiki/Contingency_plans#SHA-256_is_broken) in the thread.