So, are you sure there can never be a program which allows such an exploit? I've seen programs that had embedded components (state machines in particular) which were not easily human-readable, and had themselves been generated by computer. And even large graphics, sound, or video sequences can really change the meaning of a program's actions in some ways; those might be susceptible to the requirements of the attack. I agree it's hard to see how to exploit the existing MD5 collision attacks in programs that would look innocent, but I don't see what makes it *impossible*.
That's not what Ben is saying at all. He's saying that once you give the adversary the power to do the sorts of things that are required for this (like being able to replace a give C with C'), there are easier ways for the attacker to get the desired result than playing with collisions.
I do, however, feel the need to be a bit pedantic and say that tables for state machines are seldom random (for some suitable definition of random). Nor are graphics, sound, nor video. Inserting the artifacts into them you need to make this work is really, really obvious for the same reasons that Shamir and Van Someren showed that finding key material is so easy.
I have an attack that I just came up with that pretty much proves Ben's point. I can, using this technique, make any MD5 preimage give you any desired hash value. It's trivial, once I can replace code C with C'.
Give up? Answer below.
Hint: it works just as well against SHA1. Or SHA-256. Or Whirlpool. Or pick your hash.
Answer:
patch the md5 software. put in a table that gets searched -- when you see hash x, return y. if you want to be clever, obfuscate the check and the result. toss in some xoring so you don't have the direct target and result hashes there, so simple grepping doesn't give the trick away. But once you can replace C with C', why bother doing bit-flipping when you can just compile the code you want, and replace the code that rats you out?
--------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
