CIYAM
Legendary
Offline
Activity: 1890
Merit: 1086
Ian Knowles - CIYAM Lead Developer
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 01, 2012, 01:51:49 PM |
|
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
Donator
Legendary
Offline
Activity: 2772
Merit: 1019
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 01, 2012, 01:59:40 PM Last edit: November 02, 2012, 01:37:07 AM by Maged |
|
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.
|
PGP key molecular F9B70769 fingerprint 9CDD C0D3 20F8 279F 6BE0 3F39 FC49 2362 F9B7 0769
|
|
|
CIYAM
Legendary
Offline
Activity: 1890
Merit: 1086
Ian Knowles - CIYAM Lead Developer
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 01, 2012, 02:03:20 PM Last edit: November 02, 2012, 01:37:45 AM by Maged |
|
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. ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif)
|
|
|
|
DannyHamilton
Legendary
Offline
Activity: 3472
Merit: 4796
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 01, 2012, 02:20:54 PM |
|
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
Donator
Legendary
Offline
Activity: 2772
Merit: 1019
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 01, 2012, 02:58:36 PM |
|
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!
|
PGP key molecular F9B70769 fingerprint 9CDD C0D3 20F8 279F 6BE0 3F39 FC49 2362 F9B7 0769
|
|
|
CIYAM
Legendary
Offline
Activity: 1890
Merit: 1086
Ian Knowles - CIYAM Lead Developer
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 01, 2012, 03:03:41 PM |
|
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). ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif)
|
|
|
|
molecular
Donator
Legendary
Offline
Activity: 2772
Merit: 1019
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 01, 2012, 03:15:15 PM |
|
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). ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif) 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 ![Wink](https://bitcointalk.org/Smileys/default/wink.gif) Now back to the economy subforum where noone really notices that I don't have a clue what I'm talking about.
|
PGP key molecular F9B70769 fingerprint 9CDD C0D3 20F8 279F 6BE0 3F39 FC49 2362 F9B7 0769
|
|
|
Kazimir
Legendary
Offline
Activity: 1176
Merit: 1011
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 01, 2012, 04:19:04 PM |
|
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
Legendary
Offline
Activity: 1890
Merit: 1086
Ian Knowles - CIYAM Lead Developer
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 01, 2012, 04:24:30 PM |
|
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
Legendary
Offline
Activity: 1512
Merit: 1036
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 01, 2012, 04:57:00 PM |
|
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
Legendary
Offline
Activity: 1302
Merit: 1026
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 01, 2012, 05:22:53 PM |
|
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. if SHA256(SHA256(block)) < target block is valid elseif SHA3(SHA3(block)) < target block is valid else block is invalid
|
17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8 I routinely ignore posters with paid advertising in their sigs. You should too.
|
|
|
molecular
Donator
Legendary
Offline
Activity: 2772
Merit: 1019
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 01, 2012, 05:51:10 PM |
|
Block 300,000+ hash: SHA3((SHA256(SHA3-tree))) = Your ASIC is obsolete. Discuss.
not without damn good reason.
|
PGP key molecular F9B70769 fingerprint 9CDD C0D3 20F8 279F 6BE0 3F39 FC49 2362 F9B7 0769
|
|
|
molecular
Donator
Legendary
Offline
Activity: 2772
Merit: 1019
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 01, 2012, 05:57:29 PM |
|
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. 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?
|
PGP key molecular F9B70769 fingerprint 9CDD C0D3 20F8 279F 6BE0 3F39 FC49 2362 F9B7 0769
|
|
|
runeks
Legendary
Offline
Activity: 980
Merit: 1008
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 01, 2012, 06:52:27 PM |
|
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
Legendary
Offline
Activity: 1302
Merit: 1026
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 01, 2012, 07:07:58 PM |
|
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. 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.
|
17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8 I routinely ignore posters with paid advertising in their sigs. You should too.
|
|
|
Etlase2
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 01, 2012, 07:25:19 PM |
|
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
Legendary
Offline
Activity: 980
Merit: 1008
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 01, 2012, 07:30:40 PM |
|
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
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 01, 2012, 07:48:32 PM |
|
found this from a quick search: http://www.ecrypt.eu.org/hash2011/proceedings/hash2011_07.pdfThey 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
Legendary
Offline
Activity: 980
Merit: 1008
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 01, 2012, 08:18:40 PM |
|
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
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 01, 2012, 08:29:54 PM |
|
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.
|
|
|
|
|