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

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.