3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Congratulation: you have built a machine to give a random solution to the first preimage problem, which can trivialy be turned into one generating collisions. Here is a variant of your machine: it can tell that the number you typed is also the SHA-256 of the ASCII string Password $\endgroup$ – fgrieu Mar 17 '15 at 18:18
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Could you detail how one would use this machine (as described in the question, it is actually a random-first-preimage-machine) to sign different jar files or similar non-random data? Or do you simply want to use the machine as a RNG? $\endgroup$ – Paŭlo Ebermann Mar 17 '15 at 22:08
  • $\begingroup$ I think I need a picture of sorts. I would only use the output of the machine. $\endgroup$ – Maarten Bodewes Mar 17 '15 at 22:58
  • $\begingroup$ You could use the value as well to derive a key and hide some information, still with the same signature. $\endgroup$ – Maarten Bodewes Mar 17 '15 at 23:32
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.