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).
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 232 possible CRC32 values, so when we choose 216 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 216 MD5 colliding blocks, we need just 16 of them to use Joux's multicollision trick . 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 H0 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
MD5(H0,M(0,0)) = MD5(H0,M(0,1)) = H1 (1)
Next, we continue computing another 15 pairs of colliding blocks,
always using the previous hash context as our initialization vector
have the same MD5 hash starting from context H0.
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 216 colliding blocks with same MD5 hash.
That is enough for our birthday paradox attack.
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.Shortly, the RPM file is organized into special blocks, each block is preceded by a tag. A tag tells the type of the following block, its length and some other parameters. We are interested in the SIGTAG_MD5 tag, which describes a block where MD5 checksum of the archive is stored. This block of of the BIN (binary) type, with length of 16 bytes (obviously). But we could change the tag by changing the block's size so that we could put the colliding block there, after the original MD5 sum itself. We assume that the rpm installer only compares the first 16 bytes of the block to the checksum of the rest of archive. We haven't tried it out yet or studied closely the rpm installer's source code, so no guarantees. Other option might be insterting a new block into rpm containing our MD5 colliding block, or changing the SIGTAG_SIZE tag's type and size to store the colliding block after the size. To be sure, one would have to inspect rpm installer's source code, but we are quite convinced that there is a place to put the colliding block where it would not be checked.