Public SourceMage Discussion List

[Seth Alan Woolley <seth AT positivism.org>]

On Wed, Aug 31, 2005 at 02:36:57AM +0200, Mads Laursen wrote:
> 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.

That's not true.  That's actually the first weakness given in the 
wikipedia article.  If you have two things that hash to the same:

lkdjflsdkfds12 = 43345
sdfdfsfsdfdd12 = 43345

Even if you include the length, adding the same data to it will yield 
the same hash in the iterative hashes that most hashes are:

lkdjflsdkfdssdddsssddf22 = 56653
sdfdfsfsdfddsdddsssddf22 = 56653

See how the lengths are both identical and the appending of the length 
is meaningless?

It's still another collision.

Adding a length to a hash outside the hash is one more level of 
difficult for an attacker attempting to use massive appends to gain a 
collision (which is a totally different way than the technique above).  
Sergey is trying to prevent:

sfsfasdfs = 46643
sfsfasdfsfsdfasdfamaliciouscodefsdfsdfadfd = 46643

Completely different problem.

See extract from the article you already linked to :):

>>>
The popularity of this construction is due to the fact, proven by Merkle 
and Damgård, that if the compression function f is collision-resistant, 
then so is the hash function constructed using it. Unfortunately, this 
construction also has several undesirable properties:

    * length extension -- once an attacker has one collision, he can 
    find more very cheaply.

    * second-preimage attacks against long messages are always much more 
    efficient than brute force

    * multicollisions (lots of messages with the same hash) can be found 
    with only a little more work than collisions
<<<            

Hope that clarifies,

Seth

> 
> 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



> _______________________________________________
> SM-Discuss mailing list
> SM-Discuss AT lists.ibiblio.org
> http://lists.ibiblio.org/mailman/listinfo/sm-discuss


-- 
Seth Alan Woolley [seth at positivism.org], SPAM/UCE is unauthorized
Quality Assurance Team Leader & Security Team: Source Mage GNU/linux
Linux so advanced, it may as well be magic http://www.sourcemage.org
Secretary Pacific Green Party of Oregon http://www.pacificgreens.org
Key id FDCEE733 = 5302 B414 64C4 6112 3454  E082 99F0 69DC FDCE E733

Attachment: pgpG3Pp2fLaXA.pgp
Description: PGP signature