4 ms·

Here is the explanation: 1. Generate a gif for each possible digit in the first column 2. Append collision blocks to each gif to make a 16 way collision 3. R

by soheil 10y ago

Here is the explanation: 1. Generate a gif for each possible digit in the first column 2. Append collision blocks to each gif to make a 16 way collision 3. Repeat for each digit 4. Hash the final product 5. Replace each digit with the correct digit From https://www.reddit.com/r/programming/comments/5y03g9/animated_gif_displaying_its_own_md5_hash/ https://www.reddit.com/r/programming/comments/5y03g9/animate...

helb 10y ago
Create your own MD5 collisions – https://natmchugh.blogspot.cz/2015/02/create-your-own-md5-collisions.html https://natmchugh.blogspot.cz/2015/02/create-your-own-md5-co... (2015, on HN here, but without any significant traction: https://news.ycombinator.com/item?id=9003429 https://news.ycombinator.com/item?id=9003429) The software used is "HashClash", seems it supports SHA1, too: https://marc-stevens.nl/p/hashclash/index.php https://marc-stevens.nl/p/hashclash/index.php
kevinSuttle 10y ago
Oh man. Thanks! That makes so much more sense with the explanation.
taneq 10y ago
Why would you do it that way, rather than: 1. Pick a target MD5 2. Make whatever cutesy animation you want showing that number 3. Append collision blocks to the resulting gif to make it match the target MD5
- corndoge 10y ago
  Got a code snippet?
- cardigan 10y ago
  Because this attack is not feasible against MD5 with current state of the art cryptanalysis. Instead collisions between files are demonstrated by appending bytes to two files until their hashes match.
  - taneq 10y ago
    Ah darn, for some reason I thought there was a practical preimage attack on MD5. I must have been thinking of CRC32 (which is just useless for this sort of thing.) My mistake.
    - dom0 10y ago
      CRCs are linear, all 'attacks' are efficient on them.
- deleted 10y ago
  [deleted]
Manishearth 10y ago
Some more info on why the 16 way collision isn't hard: This is a Nostradamus attack. For any Merkle-Damgard hash function (MD5, SHA1, SHA2 -- this is a crucial part of why the recent SHA1 collision can be used to create arbitrary colliding pdfs), if hash(A) = hash(B), hash(A+C) = hash(B+C) assuming A and B are at block size boundaries (pad them if not). So you can always add the same suffix to colliding strings and get new colliding strings. Now, a preimage attack is beyond your means. Given a string, it's hard to find something that hashes to the same thing. But, given two strings, it's possible to mix crap with both of them till they give you the same hash. This is reasonably fast for MD5, and expensive (but still within the means of folks like Google) for SHA1. So what you do is you first create images for each digit. Pair them up. Now, take each pair, and append crap to both instances till you find a collision. Now you have 8 colliding pairs. Now, applying the hash(digit0 + crap0) = hash(digit1 + crap1), hash(digit0 + crap0 + crap01) = hash(digit1 + crap1 + crap01). Appending the same suffix (crap01) to both will still get you a collision. Now, pair up each pair. Let's say we take the digit0/digit1 pair and pair it with digit2/digit3. Find a collision between digit0+crap0 and digit2+crap2. Let's say that hash(digit0 + crap0 + morecrap0) = hash(digit2 + crap2 + morecrap2). Realize that this is also equal to hash(digit1 + crap1 + morecrap0) and hash(digit3 + crap3 + morecrap2) (since we can add the morecrap suffix to the already-colliding digit+crap combinations to get new collisions). Now, we have a four-way collision. Repeat with the other pairs and you have 4 of these. Now do the same process, and get 2 8 way collisions. Repeat to get 1 16 way collision. Ultimately you'll have something like - hash(digit0 + crap0 + crap01 + crap0123 + crap01234567) - hash(digit1 + crap1 + crap01 + crap0123 + crap01234567) - hash(digit2 + crap2 + crap23 + crap0123 + crap01234567) - ... - hash(digit6 + crap6 + crap67 + crap4567 + crap01234567) - ... - hash(digitF + crapF + crapEF + crapCDEF + crap9ABCDEF) which is a 16 way collision, of 16 gifs of different digits, followed by some crap for each one. This only requires 15 collision attacks, which isn't hard with MD5. Needs more than a million dollars for SHA1, though.
- makomk 10y ago
  It's moderately expensive even with MD5. Ideally you'd like to use the same prefix and use the collision itself to choose between the two. This is easy with code, trickier with images, and even trickier with text-based PDFs but still possible: https://www.makomk.com/~aidan/selfmd5-lastfix.pdf https://www.makomk.com/~aidan/selfmd5-lastfix.pdf

by soheil 10y ago

helb 10y ago

Create your own MD5 collisions – https://natmchugh.blogspot.cz/2015/02/create-your-own-md5-collisions.html https://natmchugh.blogspot.cz/2015/02/create-your-own-md5-co... (2015, on HN here, but without any significant traction: https://news.ycombinator.com/item?id=9003429 https://news.ycombinator.com/item?id=9003429) The software used is "HashClash", seems it supports SHA1, too: https://marc-stevens.nl/p/hashclash/index.php https://marc-stevens.nl/p/hashclash/index.php

kevinSuttle 10y ago

Oh man. Thanks! That makes so much more sense with the explanation.

taneq 10y ago

Why would you do it that way, rather than: 1. Pick a target MD5 2. Make whatever cutesy animation you want showing that number 3. Append collision blocks to the resulting gif to make it match the target MD5

corndoge 10y ago
Got a code snippet?
cardigan 10y ago
Because this attack is not feasible against MD5 with current state of the art cryptanalysis. Instead collisions between files are demonstrated by appending bytes to two files until their hashes match.
- taneq 10y ago
  Ah darn, for some reason I thought there was a practical preimage attack on MD5. I must have been thinking of CRC32 (which is just useless for this sort of thing.) My mistake.
  - dom0 10y ago
    CRCs are linear, all 'attacks' are efficient on them.
deleted 10y ago
[deleted]

Manishearth 10y ago

Some more info on why the 16 way collision isn't hard: This is a Nostradamus attack. For any Merkle-Damgard hash function (MD5, SHA1, SHA2 -- this is a crucial part of why the recent SHA1 collision can be used to create arbitrary colliding pdfs), if hash(A) = hash(B), hash(A+C) = hash(B+C) assuming A and B are at block size boundaries (pad them if not). So you can always add the same suffix to colliding strings and get new colliding strings. Now, a preimage attack is beyond your means. Given a string, it's hard to find something that hashes to the same thing. But, given two strings, it's possible to mix crap with both of them till they give you the same hash. This is reasonably fast for MD5, and expensive (but still within the means of folks like Google) for SHA1. So what you do is you first create images for each digit. Pair them up. Now, take each pair, and append crap to both instances till you find a collision. Now you have 8 colliding pairs. Now, applying the hash(digit0 + crap0) = hash(digit1 + crap1), hash(digit0 + crap0 + crap01) = hash(digit1 + crap1 + crap01). Appending the same suffix (crap01) to both will still get you a collision. Now, pair up each pair. Let's say we take the digit0/digit1 pair and pair it with digit2/digit3. Find a collision between digit0+crap0 and digit2+crap2. Let's say that hash(digit0 + crap0 + morecrap0) = hash(digit2 + crap2 + morecrap2). Realize that this is also equal to hash(digit1 + crap1 + morecrap0) and hash(digit3 + crap3 + morecrap2) (since we can add the morecrap suffix to the already-colliding digit+crap combinations to get new collisions). Now, we have a four-way collision. Repeat with the other pairs and you have 4 of these. Now do the same process, and get 2 8 way collisions. Repeat to get 1 16 way collision. Ultimately you'll have something like - hash(digit0 + crap0 + crap01 + crap0123 + crap01234567) - hash(digit1 + crap1 + crap01 + crap0123 + crap01234567) - hash(digit2 + crap2 + crap23 + crap0123 + crap01234567) - ... - hash(digit6 + crap6 + crap67 + crap4567 + crap01234567) - ... - hash(digitF + crapF + crapEF + crapCDEF + crap9ABCDEF) which is a 16 way collision, of 16 gifs of different digits, followed by some crap for each one. This only requires 15 collision attacks, which isn't hard with MD5. Needs more than a million dollars for SHA1, though.

makomk 10y ago
It's moderately expensive even with MD5. Ideally you'd like to use the same prefix and use the collision itself to choose between the two. This is easy with code, trickier with images, and even trickier with text-based PDFs but still possible: https://www.makomk.com/~aidan/selfmd5-lastfix.pdf https://www.makomk.com/~aidan/selfmd5-lastfix.pdf