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

[Eric Rescorla]

John Kelsey <kelsey.j at ix.netcom.com> writes:

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

But everything you've just said applies equally to my JavaScript
example. It's not a security vulnerability in the browser or the
data format that it displays differently depending on the context.
It's an intentional feature! 

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

I agree with this. I'm merely observing that many of those
data formats in practice have features that let you mount
isomorphic attacks even if you can't break the hash function.
And it's equally impractical for people to be experts on which
of them allow such dual interpretations. And because of this
the *incremental* insecurity offered by the current generation
of hash attacks is extremely small.

-Ekr

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