What practical uses can random hash collisions be put to?

Question

Using magic, I've built a machine that instantly generates hash collisions. To try it out, I set the dial to SHA256 and typed in "e7cf3ef4f17c3999a94f2c6f612e8a888e5b1026878e4e19398b23bd38ec221a".

I hit the button and it showed me a long sequence of bytes starting with "09F7E02F1290BE211DA707A266F153B3...". I hit the button again and it showed me another long sequence of bytes starting with "F326BED0DD25CED6BC1799EAF74E7F8C...".

Every possible hash output has an infinite number of collisions. My machine is just picking one of those collisions at random.

What practical uses could I have for a machine like this? You can't reliably get a collision you want - such as one that starts with a given salt or is structured as a valid Bitcoin package - just one of the many random looking collisions.

Note that attempting to open the machine will cause it to disintegrate, leaving only a golden egg behind.

Answer 1

If it is for completely random data you could still make a program that uses the random looking input to make different choices. For instance, you could sign two .jar files in Java, using the SHA-256 hash over the file in the META-INF folder. Then you can use the different files a property to make one choice or the other. Basically you're replacing one of the data blocks in a hash tree or list (which is in turn signed for Java).

Of course, most hash collisions don't work like that. For instance, the MD5 collisions need to be pre-calculated, but they work for normal data + a postfix. Even then, the amount of attacks that can be launched is limited. Faking a signature is such a big attack that the rest is more or less inconsequential.

Answer 2

With a hash function that is vulnerable to length extension attacks, like SHA-256, you can turn any random collision into a collision with that random string concatenated with some (partially) chosen data.

In any use case where random initial data does not matter, you could use it to generate two documents which have the same hash value and thus the same signature in signature protocols that sign that hash of the document.

In many cases the initial bytes do matter, but even there you might be able to brute force them to conform to the expected format. For example, a (binary) Netpbm image which starts with a magic number and size, but can then contain any image data. Find two initial blocks that give a valid, but different sized images. Then you can length-extend them with the data you want, and since trailing data is usually ignored you will end up with two different images that are largely under your control but have the same hash.

If your magic machine supported changing the IV of SHA-256, you could also prepend chosen (common) data to the colliding documents. That would allow using it in even more circumstances.