[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Re: dpkg-sig support wanted?

Scripsit Florian Weimer <fw@deneb.enyo.de>
> * Jochen Voss:

>> I found the example at http://www.cits.rub.de/MD5Collisions/ quite
>> impressive.  They have two different valid PostScript files with
>> identical MD5 sums.  I don't know how much computing time they used,
>> though.

They claim a few hours:

| Based on [WY05] and the analysis described in [Da], we implemented
| an attack to find random collisions for the MD5 compression
| function. It took just a few hours on a customary PC.

> None, many of these examples were created before the collision
> generation tools were generally available.

They did create or use a collision, as anyone can verify simply by
downloading the files. Whether or not they used a generally available
tool is not important to the fact that a collision was actually

> The "exploit" uses some properties of Postscript files which make
> them not very desirable for storing electronic documents which
> cannot be altered.

There is absolutely no reason to put the word exploit in scare quotes

You might want to notice that the "properties" you apparently think
invalidate the example are also shared by many common formats for
software. An ELF binary can easily be crafted to contain a blob of
initialized data whose contents are only used for checking whether to
enable some malicious machine code that is always present - and this
would not be easily detectable at all.

The only thing that would seem to make it less than straightforward to
craft a similar attack consisting of two different .deb files with the
same MD5 sum of which one behaves maliciously, is the need to trick
the CRC-32 in the gzip trailer for data.tar.gz simultaneously with
tricking MD5.

But a CRC-32 is, to put it mildly, not much of a defense against a
determined attacker! All it takes to beat *that* is finding at most 33
different MD5 single-block collisions in sequence; it is then a matter
of extremely simple linear algebra find a nontrivial combination of
them that cancel out each other's effect on the CRC.

Note that the gzip compression format allows blocks of compressed data
to specify use of the "no compression" algorithm, so injecting your
collisions in a gzipped data stream is trivial, too.

> (Note the "rub.de" part of the URL.  A clear warning sign.)

The nice thing about ad hominem arguments is that you can make them
without ever having to argue the merits of your case.

Henning Makholm                           "I always thought being *real* sad
                                        would be *cooler* than acting *fake*
                                 sad, but it's not. It's not cool at *all*."

Reply to: