# Can we attack a hash function if we only have the input x such that y = h(x)

This question deals with a "one-way" function $h$. Then, given the value $y = h(x)$, it is computationally infeasible to find $x$ directly from $y$.

(a) Suppose that Peter computes $y = h(x)$, where $x$ is Peter's salary, in Ringgits. If John obtains $y$, how can he determine Peter's salary $x$? (Hint: Adapt the forward search attack to this problem).

How do I explain the attack just by using cryptanalysis and forward search attack?

(b) Why does your attack not violate the one-way property of $h$?

Assuming he used forward search attack does not violate the one way property of $h$?

(c) How could Peter prevent this attack? We assume that John has access to the output of the function $h$, John knows that the input includes Peter's salary, and John knows the format of the input. Also, no keys are available, so Peter cannot encrypt the output value.

Second pre-image resistant to prevent this attack?

a) You can't reverse the hash function, but you can try to hash a lot of different x', and see if h(x') = y. Assuming you have second pre-image resistance, you should then have x'= x. This is possible only because you know that Peter's salary is in a small range (e.g. [0,10000]), so you can compute every hash.

b) Well, we didn't reverse the hash, we simply use a forward search attack... There is nothing more to say.

c) You suppose that you can't use a key, so I don't see how you can prevent the attack... Maybe concatenate x with a constant length secret value, if using a secret value without encrypting x allowed.

However, if you assume that Peter has a secret key he can use, one way of preventing this type of attack would be to use a secure way to compute the tag of x. You can take a look at HMAC, which is described in the link I provide.

• For (C), in the question: "Also, no keys are available". Personally I don't see it happening without a secret value or key, but hey, it's the question. – Maarten Bodewes Apr 4 '18 at 10:54
• I missed that point when reading the question. If only encryption is off the table, I guess we could mask x with a secret value before hashing it... – Faulst Apr 4 '18 at 12:11
• Agreed, although the difference between secret and key is, well, academic at best; as said, I don't see any other good solution. If you'd amend your answer (C) I'd be happy to vote up. Besides, James may not have seen HMAC yet :) – Maarten Bodewes Apr 4 '18 at 12:50
• Done, I chose to leave the HMAC reference, which is an interesting reference to look at for a crypto beginner, and not that hard to understand – Faulst Apr 4 '18 at 13:34
• Masking is dangerous. x could be small, for instance. I'd rather concatenate with a constant width value. Of course HMAC or SHA-3/KMAC will be more secure. No need to name me in the answer, I'm already in the comments :) – Maarten Bodewes Apr 4 '18 at 13:40