Public SourceMage Discussion List

[Mads Laursen <smgl AT dossen.dk>]

On 30/08/05 18.34, Seth Alan Woolley wrote:
> 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

My point was actually, that this is possible, but since the original
source would be one of the files with hash 43345 in this example, the
only interesting collision is the other one with the _same_ hash
(which has the same length). The possiblity of creating pairs of files
that collide on a different hashvalue has no impact on the security of
the original file, the only collision with 'lkdjflsdkfds' in the above
example is still 'sdfdfsfsdfdd'.

> 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

This is indeed a more interesting collision, I just got the impression
that it is at least as much work as a collision of the same length,
since you need to construct the filler so that the input to the final
block "cancels out" the difference in length. And as far as I can
tell, there is no easy way to extend the length of this kind of
collision. For same length extensions it works because f(f(v,x),z) =
f(f(v,y),z) if f(v,x) = f(v,y) for some colliding data x and y, an
initialisation vector v and some additional data z. In the above case,
it would be needed to solve f(f(v,x),z1) = f(f(v,y),z2) where z1 and
z2 differ on the final padding (because it contains the length).

I appoligise if I misunderstood something, but it was late and it
sounded wrong, in my ears, that collisions of different length were
interesting enough to try to prevent. If I'm mistaken in that belief,
then I'd just like to say thank you for clearing it up.

/dossen

Attachment: pgpI3YPV2AiaW.pgp
Description: PGP signature