2
$\begingroup$

Was that just a coincidence, or did the 2 "shattered" pdf files whose SHA-1 hashes are identical had to be small in size (412KB) to make the collision attack easier?

$\endgroup$
1

2 Answers 2

3
$\begingroup$

No, in fact it was demonstration of how powerful the attack was. Larger file sizes would give more input bits that could be manipulated and controlled by the attacker. The size of the files would be trivial to increase with a length extension attack.

Subsequent work in the SHAmbles attack was even more powerful in constructing collisions between data with arbitrary start values, which could be arbitrarily large amounts of different data for the different files.

$\endgroup$
3
  • $\begingroup$ It is not actually about larger files, it is about the degree of freedomness in the file format. $\endgroup$
    – kelalaka
    Mar 12 at 14:10
  • $\begingroup$ But since large files require more time for hashing, wouldn't this rise the difficulty of finding collisions? $\endgroup$
    – oqdn
    Mar 14 at 18:39
  • $\begingroup$ Large files will linearly increase the cost of a single hash function evaluation, but the control of more bits gives the attacker the potential to reduce the number of overall evaluations needed. $\endgroup$
    – Daniel S
    Mar 15 at 14:10
1
$\begingroup$

It is definitely easier to find short collisions. But 412 KiB isn't small, it's extremely large in this context.

The two files differ only in bytes 0xC0 through 0x13F (192 through 319), so it is more accurate to say that they found a 320-byte collision, or a 128-byte collision, depending on how you look at it.

The two 320-byte files not only have the same SHA-1 digest, but leave the SHA-1 algorithm in the same internal state. As a result, you can append a suffix of any length to those two prefixes and the two resulting files will also have equal SHA-1 digests.

It's possible, if you're careful, to come up with a suffix that results in two valid PDF files that display two different JPEG images, which is what they did. This is totally separate from the process of finding the colliding prefixes. If you didn't know how to break SHA-1, and were given these two prefixes by a NSA mole, you could still construct visibly different PDF files from them, just by using information from the publicly available PDF and JPEG standards.

$\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.