TL;DR - Mega designed their own cryptosystem. Not surprisingly, it's broken: They used CBC-MAC as a one-way hash function, but CBC-MAC is not a one-way hash function.
[Edit] Huge thanks to tptacek for the thorough explanation. He did make one mistake in that I was being dumber than he thought. I believed that being able to create a static file with matching hashes would be too much hassle to be worth bothering with, other replies have stated that this is not the case, hence the MAC route.
[2nd Edit] Ok, so it looks like I may not have been as dumb as I thought I was, good discussions further down.
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.
CBC-MAC is an unusual choice, and is known to be particularly hard to get right. Very few new systems are designed with CBC-MAC anymore.
The "industry standard" choice for a MAC in a new system is probably HMAC-SHA2; if you wanted to use a cipher core instead of a hash function for your authentication tag, you'd probably use something like OMAC (or, better, EAX mode, which does both authentication and encryption at the same time).
Long story short, you're not wrong, CBC-MAC was a weird choice.
Also, MD5 isn't broken for second preimage attacks.
People like to repeat the blanket statement that MD5 is trivially broken, but in this case, it isn't. Still, it wouldn't be advisable to use here because it's broken in enough other scenarios that it makes people uncomfortable in general now. If they did use MD5, it's still a nation-state or significant crypto breakthrough before anyone could attack it.
I haven't looked closely at the code, but the author of the article speculates that the code was implemented by people who are unfamiliar with cryptography. I think that's a pretty reasonable explanation. Cryptography looks deceptively simple, but it's actually a complex and specialized field that takes years to get good at. Even experts in the field routinely build cryptosystems that are later discovered to be flawed. After all, they're building roadblocks that are designed to prevent everyone---even well-funded experts from the future---from finding a clever way around. Oh, and while they're at it, they have to consider CPU and RAM constraints, too.
Many developers don't treat crypto with the respect that it demands, and, unfortunately for end-users, this is the result.
Mega has to include the lengthy JS AES code anyway and did not want to add more files just for MD5 or SHAx. By building a mac/hmac on AES they save code size