4
$\begingroup$

Suppose I've got a list of "passwords" that are hashed using the same suffix, so basically what we do is hash = md5_digest(prefix+suffix), with suffix being a constant.

Now, if I know a single prefix and hash pair, I can trivially do a brute-force search for suffix.

But given multiple different known matching pairs of prefix and hash, is there a better than brute-force way of finding the value of suffix? Is there an algorithmic vulnerability of MD5, relying on the internal state that would allow me to do this? Or, alternatively, to construct a fake prefix that would generate a known hash when concatenated with the unknown suffix?

Update: Please don't suggest alternative hashing schemes, as I'm not designing a system or anything, I just want to understand how MD5 works.

Update 2: Okay, I might not have made myself clear enough. I'm not interested in any other "solution" for the simple reason that my problem isn't "how do I secure this system?" but "how does this specific algorithm behave?". Yes, I do know the difference between a hash algorithm and message authentication, yes, I do know HMAC, yes I do know MD5 is broken.

$\endgroup$

migrated from security.stackexchange.com Mar 9 '17 at 8:05

This question came from our site for information security professionals.

  • $\begingroup$ No, bruteforce is the best you can do. $\endgroup$ – Rápli András Mar 6 '17 at 18:21
  • $\begingroup$ @Pascal I've simplified the situation, but you can think of it as a message signing scenario, where the message is concatenated with a fixed secret key, and the md5 digest is published along with the message. So I can send various messages and observe the digest, and the question is: how safe is my secret key? Is there a cryptographic vulnerability in MD5 that would allow an attacker to significantly reduce the search space? $\endgroup$ – biziclop Mar 6 '17 at 23:32
4
$\begingroup$

is there a better than brute-force way of finding the value of suffix? Is there an algorithmic vulnerability of MD5, relying on the internal state that would allow me to do this?

The best attack better than brute-force I could found is described in this paper, it has a complexity of 2^123.4 and a memory complexity of 2^45×11 words. AFAIK this is not practical

Or, equivalently, to construct a fake prefix that would generate a known hash when concatenated with the unknown suffix?

This is not equivalent to your first question. Your first question is a preimage attack, meaning finding the original value (prefix + suffix) that generated the hash.

This question can be interpreted in two ways:

  • You're asking for an algorithm that can generate a second pre-image, meaning a second value different from the original one that produces the same hash. In this case there is no known second pre-image attack against MD5
  • You're asking if it's possible to find a collision for a given hash using a fixed part in the message. To this question I only know there are algorithms to efficiently find collisions for a given MD5 but I don't know if those methods can be adapted to use a fixed part in the message (The suffix)
$\endgroup$
-1
$\begingroup$

Assuming you're dealing with a message-signing scenario, use HMAC.

It's designed as a safe keyed hash. If you do something like what you're proposing, e.g.

signature = md5(secret || message)

there are weaknesses that allow attacks (for secret prefix, you can google length extension attacks). See Stop using unsafe keyed hashes, use HMAC for a starting point.

The linked text especially states that "md5 with a secret suffix is completely broken", and that's basically what you propose to use. If you're set on using md5, that's still viable when you use hmac-md5. But note that there are some serious weaknesses in md5 and that attacks on md5 won't get any worse, just better, so I'd counsel against using md5 as your hashing primitive.

$\endgroup$
  • $\begingroup$ Just to clarify things, I'm not proposing to use anything. I'm asking about a scenario because I'm interested in the exact ways MD5 is broken. $\endgroup$ – biziclop Mar 7 '17 at 10:26
  • $\begingroup$ Maybe it would help if you changed your question so it actually asks what you want to know? "In what exact ways is md5 broken" significantly differs from your actual question. $\endgroup$ – Pascal Mar 7 '17 at 10:43
  • $\begingroup$ I simply want to know whether it's possible to recover a common suffix from a series of known prefix/hash pairs. (Or equivalently, to construct a prefix that, when prepended to the unknown suffix, produces a known hash.) I'm not designing a message protocol, I'm not building a system, I'm not even trying to break a system. It's just a straightforward question about the strength/weakness of MD5 in a specific area. Thanks for pointing me in the direction of the paper about chosen prefix attacks. $\endgroup$ – biziclop Mar 7 '17 at 11:01
  • $\begingroup$ @biziclop : ​ How is "construct a prefix that, ... produces a known hash" equivalent to "recover a ... of known prefix/hash pairs."? ​ ​ ​ ​ $\endgroup$ – user991 Mar 8 '17 at 15:32
  • $\begingroup$ @RickyDemer Both would allow an attacker to produce a valid hash for a chosen prefix. $\endgroup$ – biziclop Mar 8 '17 at 16:06
-1
$\begingroup$

You are looking at this backward, and at the wrong level of abstraction. It's backward because you really ought to start from the requirements instead of the implementation. This question hints at your requirements:

Now, if I know a single prefix and hash pair, I can trivially do a brute-force search for suffix. But given multiple different known matching pairs of prefix and hash, is there a better than brute-force way of finding the value of suffix?

Now the thing you note is that there is a standard security definition that meets these requirements: message authentication code (a.k.a. "MAC"). A MAC is supposed to have the property of existential unforgeability under chosen message attack ("EU-CMA"), which means that it's supposed to score well in this game-like scenario:

  1. Defender chooses a secret key at random;
  2. As many times as the attacker likes, indexed by i:
    • Attacker chooses a message msg[i];
    • Attacker queries defender for msg[i];
    • Defender computes tag[i] = mac(key, msg[i]);
    • Defender responds with tag[i].
  3. Attacker now guesses a (msg, tag) pair, and they win if and only if:
    • The guess' msg is not equal to any message that they queried during step #2;
    • mac(key, msg) = tag.

If we rename your scenario's variables suffix, prefix and hash, to key, msg and tag (respectively), we can see that any function that is a good MAC must score well in your scenario as well, because what you're describing is a MAC key recovery scenario: a scenario where the attacker's goal isn't to forge a (msg, tag) pair, but to guess the secret key. Note that if an attacker can recover the key, they can then trivially forge any (msg, tag) pairs of their choice; the EU-CMA property stronger than just resistance to key recovery, because it also allows for the attacker to win even though they don't know the key. They just have to forge one (msg, tag) pair.

So your scenario calls for a MAC, which means that you should use something that's designed to be a MAC. The most popular MAC is HMAC, an algorithm that constructs a MAC out of a traditional ("Merkle-Damgård structure") hash function. So in a scenario like what you describe, you should use something like HMAC-SHA2—definitely not some improvised MD5 construction!


Update: Please don't suggest alternative hashing schemes, as I'm not designing a system or anything, I just want to understand how MD5 works.

You probably feel that I'm not adhering to this request. I have a response to that: what do you mean by "how MD5 works"? Are you really seeking knowledge about its internals, or about what goals it tries to achieve? In any case, the latter should come before the former.

Now the issue with your question is that you're asking about a scenario where there's a secret value that's supposed to resist the attacker's guesses. But cryptographers in such scenarios don't use hash functions like MD5—they use keyed functions like MACs. So once we identify that your scenario is a standard MAC scenario, we don't actually need to answer this question:

Is there an algorithmic vulnerability of MD5, relying on the internal state that would allow me to do this?

...because we already know that we have another type of tool that solves the problem! So either we use some function that was designed and tested to be a good MAC, or we change the question to this:

  • If we need a MAC but what we have is a hash function, how do we construct a secure MAC our of our hash function?

That question has a standard answer—HMAC—and once we know that, we don't need to analyze scenarios like yours anymore in practice. It's just better to use standard tools that are known to fit the problem well than to improvise something with a less-fitting tool and then have to figure out whether it's safe.


Oh, and final note, don't use MD5 for anything. It's a broken hash function.

$\endgroup$
  • 1
    $\begingroup$ Thank you for your effort, it would be really helpful if I wanted to design a new system. Unfortunately it is also exactly the sort of answer that told me nothing that I didn't know already, nothing that I wanted to learn. Maybe this is the wrong forum altogether to ask theoretical questions about specific algorithms. $\endgroup$ – biziclop Mar 8 '17 at 10:20
  • $\begingroup$ @biziclop: The problem is that your question is like if an amateur started cutting idiosyncratically on an undiagnosed medical patient, and then asked a doctor: "Is what I just did good enough to cure appendicitis?" The doctor is going to tell you that first you diagnose the patient, and then you carry out the surgery the way they they teach it in med school. $\endgroup$ – Luis Casillas Mar 9 '17 at 4:36
  • $\begingroup$ @LuisCasillas Bad analogy. Better analogy: the question asks “I have this disability, how can I live with it?” Your answer says “but your leg shouldn't work that way, here's how a sane leg works”. That's not helpful. $\endgroup$ – Gilles Mar 9 '17 at 10:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.