[Dshield] Crypto Question

Valdis.Kletnieks at vt.edu Valdis.Kletnieks at vt.edu
Thu Mar 5 18:39:46 GMT 2009


On Wed, 04 Mar 2009 17:10:04 PST, John Hardin said:

> Believing (absent mathematical proof) that a hash is secure does not mean 
> there are no flaws in it.

I thought that we *were* discussing "believing something when there are good
vetted papers on the subject" - in other words, those of us who started saying
"Maybe migrating off MD5 would be a good idea" when the first good attacks on
it started showing up at crypto conferences.

For MD5, a good summary would be Kaminsky "MD5 to be considered harmful someday"
http://www.doxpara.com/md5_someday.pdf

And the two "handwriting is on the wall" papers:

[1] Antoine Joux, "Multicollisions in iterated hash functions. applications to cascaded constructions.,"
   2004.
[2] Xiaoyun Wang, Dengguo Feng, Xuejia Lai, and Hongbo Yu, "Collisions for hash functions md4, md5,
   haval-128 and ripemd," Cryptology ePrint Archive, Report 2004/199, 2004, http://eprint.iacr.org/.

It's the rare crypto system that's broken all at once (or more properly, very
few crypto systems reach wide usage only to break at once - the weak systems
that are broken easily get broken early).  So if the best known attack on
something is O(2**96), and somebody publishes something that's O(2**72), it's
time to worry even if 2**72 is still itself too large, because it's *likely*
that somebody will leverage that result to get it down around 2*56 at which
point it's well into "Game Over" territory.

> MD5 was believed secure until a collision was proven.

Lots of people believe in lots of things even when evidence is against it.
But we were discussing what good cryptographers believe after reading the
conference proceedings. ;)

> And what happens when a collision is found in SHA256?

Finding a collision doesn't mean *squat*.  In fact, it is an easy proof that
any hash algorithm that handles N bits *will* have collisions - just hash all
the number from 0 to (2**N)-1.  Now hash 2**N. Have a nice day. ;)  

The problem is when there is an *easy* way to generate *controlled* collisions.

And as I said before - if one of your hash functions suffers from that,
then it doesn't help to use a second hash to double-check.  You should just
*toss* the first hash, because any sane analysis will show there's only three
realistic states:

1) The first hash is genuine and valid so it passes, in which case a check
proves nothing.  Your second hash passes as well.
2) The first hash is a fake generated by a clued adversary, so it passes
anyhow. The check still proves nothing. Your second hash fails.
3) The first hash is a fake generated by an idiot, so it fails. Your second
hash probably fails as well.

Look at that - the second hash is doing all the work, except if you get attacked
by an idiot.  So why you bothering doing the first hash at all?

Most crypto schemes depend on the assumption that (2) doesn't happen.  If
(2) can happen, the scheme is *BROKEN*.  Don't use it. Period.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 226 bytes
Desc: not available
Url : http://lists.sans.org/pipermail/list/attachments/20090305/713048dc/attachment.bin 


More information about the Dshield mailing list