Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Re^4: On showing the weakness in the MD5 digest function and getting bitten by scalar context

by BrowserUk (Pope)
on Aug 27, 2004 at 19:21 UTC ( #386470=note: print w/ replies, xml ) Need Help??


in reply to Re^3: On showing the weakness in the MD5 digest function and getting bitten by scalar context
in thread On showing the weakness in the MD5 digest function and getting bitten by scalar context

t IS meant to be computationally infeasible to find two messages with the same hash.

Total bollocks!

It is mathematically IMPOSSIBLE to reduce every 32 byte message, to a 16-byte hash and and not have duplicates. If you believe otherwise I have an infinite compression algorithm that you might like to fund development of?

The only ignorance is that on behalf of those that don't understand simple logic--like you apparently.


Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
"Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon


Comment on Re^4: On showing the weakness in the MD5 digest function and getting bitten by scalar context
Re^5: On showing the weakness in the MD5 digest function and getting bitten by scalar context
by Anonymous Monk on Aug 27, 2004 at 21:18 UTC
    Which part of "computationally infeasible" did you not understand? But I think it's better stated, "meant to be computationally infeasible to find a different message with the same hash", with two subcategories of infeasibility: where the original message is known, and where it is not.

      See 386498. Then point me at the vulnerability that this discovery opens up?

      I recently ran a process that produced 100 million md5s of randomly generated data. I hit duplicates in that process on at least two runs. For my purposes, using the md5 Digest as a hashing function, I simply added a space to the end of the text to maintain uniqueness. For that application, the trailing whitespace was irrelevant.

      But 2 runs out of 4 or 5 of 100 million showed duplicates. A total runtime of less than 24 hours. Was I just extraordinarially (un)lucky? I don't think so. As I said in another thread recently, stats ain't my strong suite, but I think that the odds of generating 2 matching pairs from 500 million is probably well within statistical norms.

      However, if you gave me an md5, and asked me to find a plaintext that matched it, without giving me the plaintext you had used to generate it. That would be computationally infeasible. This, I belive, is what the md5 algorithm is intended to achieve.

      But if you need the original plaintext in order to generate the new plaintext?

      Alternatively, take my trojan binary and the md5 from some trusted piece of code, and then tell me what bytes I need to insert into data space (and where) within that binary in order for it's md5 to match that of the trusted piece of software. That would be a vulnerability that would make me consider md5 broken.


      Examine what is said, not who speaks.
      "Efficiency is intelligent laziness." -David Dunham
      "Think for yourself!" - Abigail
      "Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon
        I recently ran a process that produced 100 million md5s of randomly generated data. I hit duplicates in that process on at least two runs.
        Are you absolutely certain that the random data itself contained no duplicates? I would be very interested to see these MD5 collisions of yours.
        I think that the odds of generating 2 matching pairs from 500 million is probably well within statistical norms.
        Sure. If you reduce MD5 to about 30 bits.
        However, if you gave me an md5, and asked me to find a plaintext that matched it, without giving me the plaintext you had used to generate it. That would be computationally infeasible. This, I belive, is what the md5 algorithm is intended to achieve.
        This is known as the Preimage Problem. It's much more difficult than the Collision Problem (finding two messages with the same MD5). Cryptographic hashes are supposed to prevent someone from doing either one. You can answer "no they aren't" again if you want, but you will still be wrong.
        Alternatively, take my trojan binary and the md5 from some trusted piece of code, and then tell me what bytes I need to insert into data space (and where) within that binary in order for it's md5 to match that of the trusted piece of software. That would be a vulnerability that would make me consider md5 broken.
        There are more uses of MD5 than are dreamt of in your philosophy, Horatio.
        People are rat-holing on the "I can make two random-data chunks which have the same MD5 hash." Sure, that's an interesting data point.

        But my point is (and has been) that the complexity is far higher if you want to (1) engineer a new data stream which will match an original data stream's hash, while (2) maintaining a plausible protocol and formatting.

        • Forge a new JPEG image (same hash as the original image) which has no broken data fields.
        • Forge a new tarball which can still be decompressed.
        • Forge a new text file without using random line noise or dictionary gibberish.

        If you can do that, even once, THEN I will be impressed and reconsider the value of MD5's distribution fingerprinting.

        --
        [ e d @ h a l l e y . c c ]

Re^5: On showing the weakness in the MD5 digest function and getting bitten by scalar context
by iburrell (Chaplain) on Aug 27, 2004 at 21:34 UTC
    You are missing the point of the attack. One of the main properties of a cryptographic hash is that is hard to FIND a collision. There are certainly collisions, but with a secure hash function and a large enough size, it is practically impossible to find another input that produces the same hash. This is very important for many cryptographic protocols.

    This attack takes finding an MD5 hash collision from difficult brute force to relatively easy. This doesn't matter too much for many uses of MD5 where security isn't important.

      Maybe I am? Did you find something somewhere that suggested that they could start with an md5 and generate a plaintext with that md5?

      What I read, led me to believe that what they were saying is that they had discovered a way to take one piece of plain text, generate its md5, and then by manipulating the original plaintext, generate another plaintext with the same md5.

      But note. If I read it right, they need the original text to produce the new one.

      For password applications, this means they would need the original password in order to produce another piece of text that had the same md5. But why bother when you have the original password?

      So what other vulnerabilities arise from this discovery? If they start with the source or binary of some application that is downloadable and is checksummed with md5. They produce a modified version of that binary with the same md5. Will it run? Will it open a known port and listen for mother? Will it monitor the keyboard for passwords?

      Or, they have the text of an important message and it's md5. They produce a different message with the same md5. Will it cause the bank to transfer funds to their bank account? Or recall the nuclear bombers? Instruct the enemies operative in Washington to fall into the counter espionage trap at the cafe? Will it even be readable as English (French, German, Chinese or Swahili)?

      If the md5 is being used to stop them from knowing the text it was generated from (password), and they need to know that password to exploit the md5--no vulnerability.

      If there is open access to the plaintext, and the md5 is designed to ensure that the plaintext hasn't been altered, they can produce another plaintext with the same md5, but will it make any sense? Never mind actually do anything subversive, or to their advantage.

      Maybe I misunderstood what I read? Maybe, there is an application that allows the fact the the alternative plaintext is gibberish to be ignored and compromise something?


      Examine what is said, not who speaks.
      "Efficiency is intelligent laziness." -David Dunham
      "Think for yourself!" - Abigail
      "Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon
        Maybe I misunderstood what I read? Maybe, there is an application that allows the fact the the alternative plaintext is gibberish to be ignored and compromise something?
        Don't know if I got that correctly, but sabotaging a p2p network could be such an application. If a p2p network uses hashes to identify files, you could use this weakness to supply gibberish data (parts) to prevent successful downloads.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://386470]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (13)
As of 2014-10-23 12:53 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    For retirement, I am banking on:










    Results (125 votes), past polls