From: Ben Laurie <[EMAIL PROTECTED]> Sent: Dec 22, 2004 12:24 PM To: David Wagner <[EMAIL PROTECTED]> Cc:
[email protected] 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 [EMAIL PROTECTED]
