Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

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

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


in reply to Re^5: 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

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


Comment on Re^6: On showing the weakness in the MD5 digest function and getting bitten by scalar context
Re^7: On showing the weakness in the MD5 digest function and getting bitten by scalar context
by Anonymous Monk on Aug 27, 2004 at 23:33 UTC
    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.
      Sure. If you reduce MD5 to about 30 bits.
      60 bits. My bad. Point stands.

      From the RFC (which you appear to be (mis)quoting) -- my highlighting:

      This document describes the MD5 message-digest algorithm. The algorithm takes as input a message of arbitrary length and produces as output a 128-bit "fingerprint" or "message digest" of the input.

      It is conjectured that it is computationally infeasible to produce two messages having the same message digest, or to produce any message having a given prespecified target message digest.

      The MD5 algorithm is intended for digital signature applications, where a large file must be "compressed" in a secure manner before being encrypted with a private (secret) key under a public-key cryptosystem such as RSA.


      Cryptographic hashes are supposed to prevent someone from doing either one.

      Nowhere in that do I see MD5 described as a "cryptographic hash"? Any application that uses a "digital signature" as a "cryptographic hash" based upon "conjectured...computational infeasibility" is a misapplication of the algorithm.

      If the application needs a "cryptographic hash", it should be using one.

      There are more uses of MD5 than are dreamt of in your philosophy, Horatio.

      Ah yes, my dear Josephine Hardy*, but how many of them are misuses?


      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

        Ok, you win. "Cryptographic hash" is not the formally correct terminology. I hang my head in shame. What I find interesting is that you dig up a quotation that says exactly what I've been telling you, but with different words, and use it to claim that I'm wrong.

        I wasn't quoting the RFC. It's interesting that they used almost the same language I did.

        You seem to think that your quotation says MD5 is a digital signature. It does not. It's telling you that MD5 can be used as part of a digital signature protocol.

        You also seem to think that the RFC is giving you a comprehensive list of all the allowable uses of MD5. It's not. It says "MD5 is part of this complete breakfast," but you don't have to eat it that way. If you want to learn what you should eat for breakfast, you have to study nutrition, not breakfast cereal advertisements.

Re^7: On showing the weakness in the MD5 digest function and getting bitten by scalar context
by halley (Prior) on Aug 30, 2004 at 14:00 UTC
    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 ]

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (11)
As of 2014-07-14 08:38 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    When choosing user names for websites, I prefer to use:








    Results (257 votes), past polls