Getting the key used for HMAC given the hash and the plaintext?

Question

I'm working on a little exercise to understand the drawbacks of poor library choices and I've been presented with the following scenario.

The HMAC function in python is being used (md5). I know the message being hashed as well as well as the resulting HMAC for this message. The key being used is generated by random.getrandbits(128).

The only thing I can think of is to put the random.getrandbits(128) in some kind of while loop and generate HMACs for the message until I find a match with the given HMAC.

Is there any way I can extract the key being used by the hmac function knowing the message, the function used to generate keys and the message digest, that does not involve brute-force?

Answer 1

Is there any way I can extract the key being used by the hmac function knowing the message, the function used to generate keys and the message digest, that does not involve brute-force?

None are known; this remains true even if you have a huge pile of messages that you picked, and their corresponding HMAC-MD5's.

Collision-resistance for MD5 is completely and utterly broken; we can easily find pairs of messages that have the same MD5 hash, and we have a surprising amount of flexibility in choosing most of the contents of these messages.

However, HMAC does not rely on collision resistance of its hash function; as far as we know, HMAC-MD5 is still secure. Now, we don't suggest people use it, but that's more of us btrying to get people away from anything that uses MD5, not of any specific known weakness.