The Pointlessness of the MD5 "attacks"

[Jon Callas]

> 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 majordomo at metzdowd.com