SHA-256 broken, collisions found... Bitcoin then?

[CIYAM]

For what values of t1 and t2?

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

[t1 - in hex]
d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f89
55ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5b
d8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70

[t2 - in hex]
d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f89
55ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5b
d8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70

[molecular]

For what values of t1 and t2?

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

[t1 - in hex]
d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f89
55ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5b
d8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70

[t2 - in hex]
d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f89
55ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5b
d8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70

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.

[CIYAM]

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

[t1 - in hex]
d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f89
55ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5b
d8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70

[t2 - in hex]
d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f89
55ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5b
d8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70

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.

[DannyHamilton]

For what values of t1 and t2?

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

[t1 - in hex]
d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f89
55ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5b
d8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70

[t2 - in hex]
d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f89
55ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5b
d8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70

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.

molecular,

Take another look.

[molecular]

For what values of t1 and t2?

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

[t1 - in hex]
d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f89
55ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5b
d8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70

[t2 - in hex]
d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f89
55ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5b
d8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70

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.

molecular,

Take another look.

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

[CIYAM]

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

[molecular]

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? (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.

[Kazimir]

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

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.

[CIYAM]

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

[deepceleron]

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

[kjj]

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.

Code:

if SHA256(SHA256(block)) < target
 block is valid
elseif SHA3(SHA3(block)) < target
 block is valid
else
 block is invalid

[molecular]

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

not without damn good reason.

[molecular]

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.

Code:

if SHA256(SHA256(block)) < target
 block is valid
elseif SHA3(SHA3(block)) < target
 block is valid
else
 block is invalid

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?

[runeks]

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

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)

[kjj]

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.

Code:

if SHA256(SHA256(block)) < target
 block is valid
elseif SHA3(SHA3(block)) < target
 block is valid
else
 block is invalid

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?

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.

[Etlase2]

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.

[runeks]

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.

[Etlase2]

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.

[runeks]

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

[Etlase2]

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,

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.