0

Imaging the following pseudo-code:

h = hash(sha512)
h.input(password)
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.

Improve this question
1
  • Consider the function h=(x^y) mod m. If you know h, x, and m, how do you find y?
    – Mark
    Commented Aug 20, 2014 at 20:57

1 Answer 1

Reset to default
1

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!

Improve this answer
2
  • 1
    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 'SO- stop being evil'
    Commented Aug 20, 2014 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
    Commented Aug 20, 2014 at 20:14

Not the answer you're looking for? Browse other questions tagged .