M55 is also known to be insecure: it's straightforward to find hash collisions with the MD5 function.
Can you generate a JS file (that will actually execute) with the same MD5 as
alert('Hello World');
GPU password crackers run at billions/second. "The cluster can try 180 billion combinations per second against the widely used MD5 algorithm" ( http://arstechnica.com/security/2012/12/25-gpu-cluster-crack... ). That's not exactly the same task, but close enough that I'll estimate the actual performance as 100,000 faster than what you estimated.
That takes you down to 2.5 years with 25 AMD Radeon HD6990 graphics cards, which costs $1000 each. For $100,000, based on your estimate, a dedicated and well-heeled hobbyist can probably find a match in a year.
Wait a few years and that price goes down quite a bit. In a decade it will likely be a semester project at some schools.
Even if I'm off by a factor of 100, GPUs are fast enough that a mid-sized organization would be able to brute force it, should they be motivated.
What we're talking about is not just generating some random text, but an actual JS file (that will execute malicious code that you want) with the same hash.
You take your JS payload, add a terminal "#", then generate the hash information for that content. This gives the initial hash state. Now set the brute force GPUs on a mission to search for the smallest string of non-newline bytes which, which added to that hash state, gives the desired MD5 result.
A problem is that this requires 2^128 bits to brute force, not 2^64 as was mentioned earlier. I didn't catch that. 2^64 is brute-forceable. 128 isn't.
And the fact that you still have to calculate MD5 for your WHOLE malicious javascript file, plus the comment with the random tail with all the random stuff you modify.
And no, you don't need to recompute the whole MD5 each time. Here's the Python code which shows that you can capture the hash state at an intermediate point:
>>> import hashlib
>>> h1 = hashlib.md5("This is the start")
>>> h2 = h1.copy(); h2.update(" # Blah!"); h2.hexdigest()
'a309b70b0bc8de4e7aad1d0ac6e14b16'
>>> h3 = h1.copy(); h3.update(" # Fnord!"); h3.hexdigest()
'a0a5979225e0ba46543856242daeab3c'
>>> hashlib.md5("This is the start # Blah!").hexdigest()
'a309b70b0bc8de4e7aad1d0ac6e14b16'
>>> hashlib.md5("This is the start # Fnord!").hexdigest()
'a0a5979225e0ba46543856242daeab3c'
edit: I don't know what I'm talking about :)
The difference is with the collision attack, the attacker controls the inputs and has to find any two valid messages with the same hash - any hash. That's what was done with forged certificates.
In this case, the hash you need to match against is fixed. You have one preimage, which is also fixed of course. You have to find a second preimage that also matches that specific hash. If you can do this at all, let alone "easily", you will significantly advance the field of cryptography.
(To raise the bar even higher, your second preimage has to be valid javascript that executes your malicious action.)
With this said, that is a collision attack and not a preimage attack and so your first point is crucial.
if (data == x) then { good_program } else { evil_program }
sure its not trivial, but not impossible.
I should have said impractical, but then people sometimes respond by talking about how fast GPUs are advancing, not getting just how far off they really are.
The best known attack to find a first pre-image is 2^123. To put this in perspective, using a slightly modified common analogy to describe how long 2^128 is:
"Imagine a computer that is the size of a grain of sand that can test inputs against a hash. Also imagine that it can test a hash in the amount of time it takes light to cross it. Then consider a cluster of these computers, so many that if you covered the earth with them, they would cover the whole planet to the height of 1 inch. The cluster of computers would find a valid pre-image on average in 1,000 years."
Even then, you would not have a useful preimage to mount an attack. You wouldn't even have ASCII. If you got ASCII, it wouldn't be syntactically correct javascript. If it was, it wouldn't do anything remotely malicious.
You would have to keep doing this until you randomly generated an input that happens to be valid javascript that performs your malicious action.
So, I rounded up to impossible.
That'd still be hard but much more likely.
This has implications for people who use tools like tripwire. If you didn't create the original file it might be the benign half of a set, if the details of your hashing are known to the attacker.