The Pointlessness of the MD5 "attacks"

[John Kelsey]

>From: Ben Laurie <ben at algroup.co.uk>
>Sent: Dec 22, 2004 12:24 PM
>To: David Wagner <daw at cs.berkeley.edu>
>Cc: cryptography at metzdowd.com
>Subject: Re: The Pointlessness of the MD5 "attacks"

...
>Assuming you could find a collision s.t. the resulting decryption looked 
>safe with one version and unsafe with the other (rather than gibberish), 
>which I find an even bigger stretch than the idea that you could find a 
>block that looked safe in one version and unsafe in another, I would 
>have said that the mere fact of using a pointless decryption to control 
>the action of the code would be suspect.

Hmm.  So maybe I'm missing something.  Here's my scenario:

a.  Alice decides to use GOST for encryption.  She finds an implementation in C from Eve, which includes the S-boxes hard-coded in.  Note that the specific S-boxes used for GOST are potentially pretty important for their security.  

b.  She also finds a review from some well-known cryptanalyst, Bob, discussing the requirements on the S-boxes, and verifying that the above implementation uses good S-boxes, which includes the md5 hash of the C source code.

c.   Alice downloads the C source code, and checks the md5 hash.  Since the hash is correct, she compiles the code, and starts using her known-secure version of GOST to encrypt sensitive data.

d.   Unknown to her, though, Eve has slipped in a changed version of the C source code, with the S-boxes changed in a way that makes the encryption much weaker.  

What prevents this attack from working?  Alice counts on a review done by someone competent and a hash of the source code, but the weakness of the hash function means that she's vulnerable to an attack.  The only thing that might keep it from working is if it happens to be impossible to choose a pair of sets of S-boxes so that one is weak, the other is strong, and the pair allows an md5 collision.  I don't know whether this is possible or not, but there's no inherent reason to think it's impossible--just making some of the 4-bit wide S-boxes in GOST non-bijective has pretty big security implications.  (Though 32 rounds covers a lot of sins in S-box selection, in terms of practical attacks rather than academic ones.)

...
>Indeed. Not the point I am making. In a nutshell, yes, it is scary that 
>Wang found collisions. No, it is not _more_ scary that you can use those 
>collisions to fool people who aren't looking anyway.

I think you can use them in ways that may fool people who *are* looking.  All you need is a legitimate reason to have a more-or-less arbitrarily chosen block of bits in a part of your program, and then the person reviewing the code says "okay, that's random-looking, but reasonable enough."  

As an alternative example, consider embedding a large prime number in your code, to be used as the modulus when you're doing Diffie-Hellman.  Someone reviews the code, and verifies that the number is prime and has all the other required properties.  Then, you swap in a different bitstring of equal length, but which is composite and yields a reasonably easy attack on Diffie-Hellman.  What prevents this?

>Ben

--John

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