Collisions for hash functions: how to exlain them to your boss

[John Kelsey]

>From: Eric Rescorla <ekr at rtfm.com>
>Sent: Jun 13, 2005 5:09 PM
>To: "Weger, B.M.M. de" <b.m.m.d.weger at TUE.nl>
>Cc: cryptography at metzdowd.com, 
>	Stefan Lucks <lucks at th.informatik.uni-mannheim.de>
>Subject: Re: Collisions for hash functions: how to exlain them to your boss

...
>Yes, this is all true, but it's kind of orthogonal to my point,
>which is that if you're willing to execute a program, this 
>attack can be mounted *without* the ability to produce hash
>collisions. The fact that so few people regard PS, HTML, Word,
>etc. as software just makes this point that much sharper.
>As far as I can tell, the ability fo produce hash collisions just
>makes the attack marginally worse.

Hang on a minute.  The issue isn't whether your data format is being
executed (in some sense almost any nontrivial data format can be seen
as a scripting language interpreted by the viewer).  The issue is that
I can make two different documents, one of which displays exactly what
you tell me you want it to display, the other of which displays
anything I like, with the same MD5 (MD4, RIPEMD, SHA0, SHA1) hash
output.  You can view the document on a viewer you trust, without any
security vulnerabilities in the viewer/data format, but you still
get fooled.  

Saying "inspect the code/data/whatever" as an answer to this problem
isn't too useful, since an inspection intended to turn up security
problems may not turn up the fact that the executable code has some
region of data in it which could be varied in just the right way for
the MD5 or SHA1 attacks to work, without making it an invalid
program.  (I've been thinking about how these attacks apply to
validated software in voting and gaming machines....)

Fundamentally, it's just really hard to safely use a hash function for
which collisions can be found cheaply.  It requires every crypto
engineer to become an expert on both how the collision attack works
(and all the possible variants!) and also an expert on what ambiguity
may exist in each data format he may ever want to hash.  

There's an obvious solution to this in principle, though the huge
installed bases of MD5 and SHA1 make it painful....

>-Ekr

-John Kelsey

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com