Can HMAC leak the password? [duplicate]

Imaging the following pseudo-code:

h = hash(sha512)
h.input(message)
send h, message to client

If the user has the hash and the message, and the only missing variable is the password, then why can't you reverse engineer the password without brute forcing it? Math has taught me that if you have two out of three variables, then you can always work out the missing one.

marked as duplicate by Gilles, dr jimbob, TildalWave, Xander, MarkAug 20 '14 at 20:55

• Consider the function h=(x^y) mod m. If you know h, x, and m, how do you find y? – Mark Aug 20 '14 at 20:57

What Math has told you is correct if you assume uniqueness and equality. For example, from a = b + c, it follows that b = a - c. Why is that? Addition has an inverse function mapping a pair of integers to a unique integer again. If you think of + as a function with infix notation and two arguments. Think of - as the inverse of that function. Then you would get: a = +(b,c), and hence b = -(a,c).

The same way, you could think of hash as a function with two arguments. And the inverse would be some function hash'. I will discuss the existence of such hash' below. Then, we would get

h = hash(m,p).

However, we would not get m = hash'(h, p).

Why? The simple answer is that there does not exist a unique v such that given h we have that h = hash(v). The pigeonhole principle tells us that there must be collisions for hash (meaning that there must exist some h for which there are v1 and v2 such that hash(v1) = h = hash(v2)). This is because the length of the images under hash is fixed. The length of the inputs of hash, however, are not bounded. Therefore there is no function hash' that returns a single value. It would rather return something like a set of values.

Your question is why we cannot find such value(s) by (simply?) reverse engineering hash. The answer to this question lies in the way such hash functions are constructed. Their purpose is to compress and to obfuscate, meaning that a small variation in the input shall result in tremendous changes in the output. If you need more precise explanations, I recommend looking at a simple hash function like md5. The source code is publicly available. Just try to 'invert' it!

• The lack of uniqueness has nothing to do with how hard the function is to invert. Your last paragraph is correct, but the rest is irrelevant. – Gilles Aug 20 '14 at 19:37
• @Gilles - True. One obvious example of an easy to invert, non unique function (by not unique I mean not injective) is sin(x). If I ask you for to solve for x in c = sin(x), you can easily find all solutions x = {2n pi + sin^-1 (c), 2(n+1) pi - sin^-1 (c) } for integer n. – dr jimbob Aug 20 '14 at 20:14