Public SourceMage Discussion List

[Mads Laursen <smgl AT dossen.dk>]

On 30/08/05 15.05, Sergey A. Lipnevich wrote:
> Quoting Seth Alan Woolley <seth AT positivism.org>:
> 
> >
> > size of tarball doing what exactly?
> 
> The first way that comes to mind to generate a hash collision is to add 
> bytes to
> the file until the collision is achieved. If we include both the hash 
> value and
> the tarball size in the DETAILS, we're drastically reducing chances of hash
> collision going unnoticed.

That is actually wrong. Most hash functions use the Merkle-Damgaard
structure[1], which explicitly include the length in the hashed data,
in the final block. So actually finding a collision of a different
length would be (at least) as difficult as finding one of the same
length. At least, that is how I understand it.

On an interresting note it is possible to extend any collision (but
you have the two different, colliding files must be extended with the
same data), and that is in fact the base for the attack against md5 on
postscript files: Create the a collision that will fit in the
beginning of a postscript file and create a conditional postscript
document that prints two different meanings, depending on the content
of the collided region. If the document comes after the collision, it
can be altered to show anything and the two files in the pair will
still have the same hash.

1: 
http://en.wikipedia.org/wiki/Cryptographic_hash_function#Merkle-Damg.C3.A5rd_hash_functions

/dossen

Attachment: pgpBNM3XWUZ4e.pgp
Description: PGP signature