Using the MD5 collision attack on zip/gzip/bzip2 and Linux package formats

First, we will  have a look at the various zip formats. With the knowledge of computing MD5 colliding blocks for any initialization vector, the attacker could do similar tricks to these formats as well as described in the main paper (located at homepage of the project).

Various zip/gzip/bzip2 formats

1. Finding the right spot to place the block

• zip - a file in this archive can be put "stored", i.e. without compression
• bzip2 - there is a chunk called XXXX which is a filler block, i.e. its data are skipped over and are not interpreted (this way we avoid even the need of CRC32 collision)
• gzip - an "extra field" could be used to store the colliding block (headers are checked using CRC16, which is lower 16bits of CRC32 checksum of the header)

2. Creating concurrent MD5 and CRC32 collisions

The zip formats use CRC32 merely as an interity check against errors. We know that CRC32 itself is not cryptographically secure and it is fairly simple to find two binary strings having the same CRC32 checksum. However, we need to cause concurrent collision of CRC32 and MD5. This is not trivial, but not so hard either. Now the birthday paradox comes handy. There are 2³² possible CRC32 values, so when we choose 2¹⁶ colliding blocks with same MD5 hash, we have 50% chance of getting two blocks causing collision in MD5 as well as CRC32. We don't have to compute 2¹⁶ MD5 colliding blocks, we need just 16 of them to use Joux's multicollision trick [1]. We use the following notation: MD5(H, M) means MD5 computed with hash context H as initialization vector.

At first, we find the right place in the zip/gzip/bzip2 file and compute the MD5 hash context H₀ up to this position in the file we want to put colliding blocks into. Then, we compute first pair of colliding blocks, M_{(0, 0)} and M_{(0, 1)}. We know that
MD5(H₀,M_(0,0)) = MD5(H₀,M_(0,1)) = H₁ (1)

Next, we continue computing another 15 pairs of colliding blocks, always using the previous hash context as our initialization vector value:
H_i+1=MD5(H_i,M_(i,0))=MD5(H_i,M_(i,1)) (2)

have the same MD5 hash starting from context H₀. Moreover, using (1) and (2) we can swap M_{(i, 0)} for M_{(i, 1)} in the messages, while messages will still have the same MD5 hash. That gives us 2¹⁶ colliding blocks with same MD5 hash. That is enough for our birthday paradox attack.

3. Time estimate for finding concurrent MD5 and CRC32 collision

Linux package formats

RPM format

The signature section follows the lead in the RPM package file. It contains information that can be used to verify the integrity, and optionally, the authenticity of the majority of the package file. The signature is implemented as a header structure.

You probably noticed the word, "majority", above. The information in the signature header structure is based on the contents of the package file's header and archive only. The data in the lead and the signature header structure are not included when the signature information is created, nor are they part of any subsequent checks based on that information.

While that omission might seem to be a weakness in RPM's design, it really isn't. In the case of the lead, since it is used only for easy identification of package files, any changes made to that part of the file would, at worst, leave the file in such a state that RPM wouldn't recognize it as a valid package file. Likewise, any changes to the signature header structure would make it impossible to verify the file's integrity, since the signature information would have been changed from their original values.

Other package formats

References