2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Maarten Bodewes Apr 4 '18 at 10:54
  • $\begingroup$ 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... $\endgroup$ – Faulst Apr 4 '18 at 12:11
  • $\begingroup$ 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 :) $\endgroup$ – Maarten Bodewes Apr 4 '18 at 12:50
  • 1
    $\begingroup$ 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 $\endgroup$ – Faulst Apr 4 '18 at 13:34
  • $\begingroup$ 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 :) $\endgroup$ – Maarten Bodewes Apr 4 '18 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.