Skip to Content.
Sympa Menu

sm-discuss - Re: [SM-Discuss] Compromise on signatures

sm-discuss AT lists.ibiblio.org

Subject: Public SourceMage Discussion List

List archive

Chronological Thread  
  • From: Seth Alan Woolley <seth AT positivism.org>
  • To: sm-discuss AT lists.ibiblio.org
  • Subject: Re: [SM-Discuss] Compromise on signatures
  • Date: Tue, 30 Aug 2005 18:34:07 -0700

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




Archive powered by MHonArc 2.6.24.

Top of Page