The Pointlessness of the MD5 "attacks"

[Ben Laurie]

John Kelsey wrote:
>> 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.)

There is certainly no inherent reason to think its impossible. What 
prevents this attack _right now_ is that we don't know how to generate a 
collision that satisfies the required properties.

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

Blimey. Finally. An attack I can actually believe in. Excellent.

Indeed, here is such a pair:

D131DD02C5E6EEC4693D9A0698AFF95C2FCAB58712467EAB4004583EB8FB7F8955AD340609F4B30283E488832571415A085125E8F7CDC99FD91DBDF280373C5BD8823E3156348F5BAE6DACD436C919C6DD53E2B487DA03FD02396306D248CDA0E99F33420F577EE8CE54B67080A80D1EC69821BCB6A8839396F9652B6FF72A700000000000000000000000000000001B 
is prime

D131DD02C5E6EEC4693D9A0698AFF95C2FCAB50712467EAB4004583EB8FB7F8955AD340609F4B30283E4888325F1415A085125E8F7CDC99FD91DBD7280373C5BD8823E3156348F5BAE6DACD436C919C6DD53E23487DA03FD02396306D248CDA0E99F33420F577EE8CE54B67080280D1EC69821BCB6A8839396F965AB6FF72A700000000000000000000000000000001B 
is not prime

both have MD5 b4b12dc7ec1b9422f6596d2a863d7900.

Cool.

Cheers,

Ben.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

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