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
hash pair, I can trivially do a brute-force search for
suffix. But given multiple different known matching pairs of
hash, is there a better than brute-force way of finding the value of
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:
- Defender chooses a secret
key at random;
- As many times as the attacker likes, indexed by
- Attacker chooses a message
- Attacker queries defender for
- Defender computes
tag[i] = mac(key, msg[i]);
- Defender responds with
- 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
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.