3 ms·

Exactly. If you test 1 million scripts per second, it will still take you quarter a million years on average to get the collision.

• dalke 14y ago
  You underappreciate what computers can do these days. 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-cracks-every-standard-windows-password-in-6-hours/ 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.
  • drharris 14y ago
    This assumes that those .js files on Mega will stay the same for those 2.5 years (or semester). Much more likely is that those files will be updated somewhat regularly, and any attempt to collide a specific hash will be rendered irrelevant.
  • lawnchair_larry 14y ago
    This is incorrect and doesn't apply for several reasons. It does not find collisions. It finds a pre-image (which is already known - it's the JavaScript file) for very short message lengths. Very different.
  • rorrr 14y ago
    What you're describing is very different. They are searching for the shortest possible text that will result in the same hash. It's possible to generate hashes very fast because the texts are so short. 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.
    • dalke 14y ago
      I don't believe that it's different. All you're looking for is the small bit of extra characters which converts the desired malicious Javascript into the target MD5. 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.
      • rorrr 14y ago
        Another thing you didn't catch is the difference between MD5 and the broken Windows password algorithm. 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.
        • dalke 14y ago
          The link and numbers I used were in regards to MD5. I even quoted "The cluster can try 180 billion combinations per second against the widely used MD5 algorithm." 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' You may think that perhaps the copies are keeping track of the entire string. However, this is not correct. Indeed, it would make the MD5 rather useless, because it would limit processing to available memory. How would one MD5 a multi GB file with only a small amount of RAM?