Is MD5 particularly vulnerable when given multiple MD5 hashes using a common, secret suffix?

Question

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.

Answer 1

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)

Answer 2

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.

Answer 3

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.