corkami/collisionsHash collisions and exploitations
By Ange Albertini and Marc Stevens.
Q: Is it possible to make a file get an arbitrary MD2/MD4/MD5/MD6/SHA1/SHA2/SHA3, or the same hash as another file?
A: No.
Q: Can one create 2 different files with the same hash?
A: With MD5, in a few seconds on a standard computer. With SHA1, it's possible but not practical for end-users (Complexity: 2^61.2 Price: $11k).
Q: Can one make 2 different files get the same hash by appending stuff?
A: With MD5, in a few hours on a standard computer. With SHA1, it's possible but not practical for end-users (Complexity: 2^63.4 Price: $45K)
Q: Will the 2 files remain valid?
A: In general, yes, as most file formats tolerate appended data. OTOH files signatures will be likely broken.
Q: Can one make 2 different files with arbitrary contents and the same hash?
A: Yes, it can be instant by relying on special file structures:
Q: Which formats can I get instant MD5-colliding files pair for?
A: JPG, PNG, GIF, GZIP, Portable Executable, MP4, JPEG2000, PDF, DOCX/PPTX/XSLX, EPUB, 3MF, XPS. Just run the specific script.
Q: What about for SHA1?
A: For SHA1, JPG in a PDF is computed and implemented.
Q: What about formats already supported for MD5 (JPG, PNG...), but for SHA1 instead?
A: They're most likely supported with SHA1 too, but their collisions hasn't been computed.
Q: Are computations faster for similar (but different) contents?
A: No. Any tiny difference requires a full computation.
Q: Which formats don't have such shortcut?
A: ELF, Mach-O, Java Class, TAR, ZIP (among others...)
Q: Are classic collisions (in a few hours) still possible with these formats?
A: Yes, as long as any amount of appended data is tolerated (ie likely not ZIP or Class).
Q: Do you provide examples of collisions?
A: Yes.
The goal is to explore extensively existing attacks - and show on the way how weak MD5 is (instant collisions of any JPG, PNG, PDF, MP4, PE...) - and also explore in detail common file formats to determine how they can be exploited with present or with future attacks.
Indeed, the same file format trick can be used on several hashes (the same JPG tricks were used for MD5, malicious SHA-1 and SHA1), as long as the collisions follow the same byte patterns.
This document is not about new attacks (the most recent one was documented in 2012), but about new forms of exploitations of existing attacks.
Current status of known attacks:
get a file to get another file's hash or a given hash: impossible
get two different files with the same MD5: instant
make two arbitrary files get the same MD5: a few hours (72 hours.core)
make two arbitrary files of specific file formats (PNG, JPG, PE...) get the same MD5: instant
get two different files with the same SHA1: 6500 years.core
(*) example with crypt - thanks Sven!
>>> import crypt
>>> crypt.crypt("5dUD&66", "br")
'brokenOz4KxMc'
>>> crypt.crypt("O!>',%$", "br")
'brokenOz4KxMc'
MD5 and SHA1 work with blocks of 64 bytes.
If two contents A & B have the same hash, then appending the same contents C to both will keep the same hash.
hash(A) = hash(B) -> hash(A + C) = hash(B + C)
Collisions work by inserting at a block boundary a number of computed collision blocks that depends on what came before in the file. These collision blocks are very random-looking with some minor differences (that follow a specific pattern for each attack) and they will introduce tiny differences while eventually getting hashes the same value after these blocks.
These differences are abused to craft valid files with specific properties.