Public SourceMage Discussion List

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

On Wed, Aug 31, 2005 at 12:01:58PM +0200, Mads Laursen wrote:
> 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'.

Understood.  I thought you meant to take just the length inside the 
hash, not that we were including the hash within another hash.  You 
confused me by just saying "collision of different length" in reference 
to M-D structure.

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

I'd actually have to look into this in more detail.

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

Yeah, and similar to the birthday paradox is the fact that we provide a 
lot of hashes (I think around 8000) that reduces the complexity to 
attack by lg2 8000 (about 13 bits) already.  :)

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

Depends on what we mean by collision, I think.

Seth

-- 
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: pgpwdsgqIp1h_.pgp
Description: PGP signature