4 ms·

Really? Can you generate a JS file (that will actually execute) with the same MD5 as alert('Hello World'); MD5 is 7ecf458bad499f6815cbc10ed597dd3a

by rorrr 14y ago

dlitz 14y ago
Practical collision attacks against real systems employing MD5 have been successfully carried out in places where people thought a lack of collision-resistance wasn't a problem. Cryptography software is hard enough to implement already; Let's not make it harder by building brand new systems using weak primitives when there are better alternatives available.
STRML 14y ago
I agree; it would be very difficult to do this: you would have to essentially define some padding area at the bottom of the file for random data (e.g. stored in a string) then generate data to go through all 2^64 possible hashes until you get a hit. I don't know if this is practical or not but it certainly sounds difficult.
- rorrr 14y ago
  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.
thefreeman 14y ago
I wouldn't say its easy, but the obvious known example is the forged microsoft certificates on the Stuxnet/Flame/Gauss viruses (widely believed to be developed with nation state backing / resources). edit: I don't know what I'm talking about :)
- lawnchair_larry 14y ago
  That example does not apply here. A collision attack doesn't help. You need a second preimage attack, of which a practical one doesn't exist for MD5. 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.)
  - kelnos 14y ago
    Fortunately, even the output of /dev/random is usually valid javascript, so that part isn't much of a concern ;)
  - drostie 14y ago
    That last point isn't particularly deep; the same techniques used in http://www.win.tue.nl/hashclash/rogue-ca/ http://www.win.tue.nl/hashclash/rogue-ca/ can be used for two files which are UTF-16 encoded and contains sections which are commented out. With this said, that is a collision attack and not a preimage attack and so your first point is crucial.
mzl 14y ago
While it might take some time to solve your particular problem, similar problems have been solved previously. Take a look at the hello and erase programs at http://www.mathstat.dal.ca/~selinger/md5collision/ http://www.mathstat.dal.ca/~selinger/md5collision/ for a nice example of constructed md5 collisions.
- rorrr 14y ago
  I think that's slightly different. It's based on if (data == x) then { good_program } else { evil_program } Generating a collision with a given MD5 hash is much more difficult.
waffenklang 14y ago
alert('Hello World'); // add random chars here until hash fits sure its not trivial, but not impossible.
- lawnchair_larry 14y ago
  Actually that particular attack is impossible as far as humans currently know.
  - CamperBob2 14y ago
    Are you saying that any given substring of characters will provably rule out a chunk of "hash space" for the entire message? Because that property sounds sort of interesting in itself.
    - lawnchair_larry 14y ago
      No, I'm not. Also "impossible" was a bad word for me to use. It's impossible in the "not enough time before the sun burns out" sense, not in the mathematical proof sense. 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.
- rorrr 14y ago
  Sure, it's not impossible if you throw a few trillion dollars at the problem and wait a few years for the computation to complete.
wnight 14y ago
No. But what if I was the consultant who wrote that file and I picked it particularly because it shared the hash of one of a family of malicious auto-generated files I had already created? 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.

Really? Can you generate a JS file (that will actually execute) with the same MD5 as alert('Hello World'); MD5 is 7ecf458bad499f6815cbc10ed597dd3a

by rorrr 14y ago

Really? Can you generate a JS file (that will actually execute) with the same MD5 as alert('Hello World'); MD5 is 7ecf458bad499f6815cbc10ed597dd3a

dlitz 14y ago

Practical collision attacks against real systems employing MD5 have been successfully carried out in places where people thought a lack of collision-resistance wasn't a problem. Cryptography software is hard enough to implement already; Let's not make it harder by building brand new systems using weak primitives when there are better alternatives available.

STRML 14y ago

I agree; it would be very difficult to do this: you would have to essentially define some padding area at the bottom of the file for random data (e.g. stored in a string) then generate data to go through all 2^64 possible hashes until you get a hit. I don't know if this is practical or not but it certainly sounds difficult.

rorrr 14y ago
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.

thefreeman 14y ago

I wouldn't say its easy, but the obvious known example is the forged microsoft certificates on the Stuxnet/Flame/Gauss viruses (widely believed to be developed with nation state backing / resources). edit: I don't know what I'm talking about :)

lawnchair_larry 14y ago
That example does not apply here. A collision attack doesn't help. You need a second preimage attack, of which a practical one doesn't exist for MD5. 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.)
- kelnos 14y ago
  Fortunately, even the output of /dev/random is usually valid javascript, so that part isn't much of a concern ;)
- drostie 14y ago
  That last point isn't particularly deep; the same techniques used in http://www.win.tue.nl/hashclash/rogue-ca/ http://www.win.tue.nl/hashclash/rogue-ca/ can be used for two files which are UTF-16 encoded and contains sections which are commented out. With this said, that is a collision attack and not a preimage attack and so your first point is crucial.

mzl 14y ago

While it might take some time to solve your particular problem, similar problems have been solved previously. Take a look at the hello and erase programs at http://www.mathstat.dal.ca/~selinger/md5collision/ http://www.mathstat.dal.ca/~selinger/md5collision/ for a nice example of constructed md5 collisions.

rorrr 14y ago
I think that's slightly different. It's based on if (data == x) then { good_program } else { evil_program } Generating a collision with a given MD5 hash is much more difficult.

waffenklang 14y ago

alert('Hello World'); // add random chars here until hash fits sure its not trivial, but not impossible.

lawnchair_larry 14y ago
Actually that particular attack is impossible as far as humans currently know.
- CamperBob2 14y ago
  Are you saying that any given substring of characters will provably rule out a chunk of "hash space" for the entire message? Because that property sounds sort of interesting in itself.
  - lawnchair_larry 14y ago
    No, I'm not. Also "impossible" was a bad word for me to use. It's impossible in the "not enough time before the sun burns out" sense, not in the mathematical proof sense. 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.
rorrr 14y ago
Sure, it's not impossible if you throw a few trillion dollars at the problem and wait a few years for the computation to complete.

wnight 14y ago

No. But what if I was the consultant who wrote that file and I picked it particularly because it shared the hash of one of a family of malicious auto-generated files I had already created? 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.