Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Take a hash function H() to be something like SHA-256 and message m. If you are given H(m) and H(H(m)), can you use this info to help derive m?

Also interested in knowing how you analyze this problem to come up with your answer.

share|improve this question
add comment

migrated from security.stackexchange.com Jan 18 at 17:41

This question came from our site for Information security professionals.

2 Answers

A hash function is a hash function: a deterministic, public function with no secret parameter. Everybody can compute SHA-256, and they all get the same results when applied on the same inputs.

Therefore, if you give H(m) to the attacker (who tries to recover m: a preimage attack), giving him H(H(m)) too does not grant him any extra actual help -- because he already has it: given H(m), he can compute H(H(m)) himself (and H(H(H(m))) and so on).


In the question above, the attacker is shown x = H(m) (for an unknown message m) and challenged to find a message m' such that H(m') = x. Another, distinct but interesting setup, is the following: suppose that the attacker is shown y = H(H(m)) for some unknown message m, and is challenged to find m'' such that H(H(m'')) = y. This raises two questions:

  1. Is this new challenge (finding a preimage for double-hash, not for the simple hash) harder, easier, or equivalent to the original preimage attack ?
  2. Does showing H(m) in addition to H(H(m)) (but still challenging the attacker with finding a preimage for the double-hash, not for the simple hash) help him ?

We suppose that the hash function is "perfect", i.e. acts as a random oracle. For a perfect hash function, the best attack for preimages is luck, i.e. trying different inputs until a match is obtained. If the hash outputs data in a set of size N, then luck works with an average cost of N invocations of the hash function. For a 256-bit perfect hash function, N = 2256.

Now for the double-hash: if H() acts as a random oracle, then so does H(H()), albeit with a slightly reduced output set. Indeed, the outer hash works over the 256-bit output of the inner hash; H, as a random oracle which offers 256-bit outputs, is expected to produce, for all possible 256-bit inputs, about (1-(1/e))N distinct outputs (to say things otherwise: if H produced all possible 256-bit outputs when applied over all possible 256-bit inputs, then H would be a permutation over the set of 256-bit values, which would be very surprising and is not expected from a random oracle). Therefore, the double-hash produces outputs in a set of size about 0.632*N, and that's also the cost of the generic preimage attack on the double-hash. BUT remember that this cost is expressed in the number of invocations of the attacked function. Invoking the double-hash means computing H twice. So we are talking about 1.264*N invocations of H. This yields our answer to my first question: finding a preimage for the double-hash is about 26.4% harder than finding a preimage for the simple hash.

So this also answers my second question: does knowing H(m) helps the attacker finding a preimage for the double-hash ? Indeed it does, because he can then search for a preimage for the simple hash, in cost N instead of 1.264*N, and any solution will also be a solution for the double-hash.


Generalized result

Let H(n) be the n-hash (n nested invocations of the hash function). Let Cn be the challenge of finding a preimage for H(n) (attacker is given x = H(n)(m) for an unknown m, and his goal is to find an input m' such that H(n)(m) = x). Then the following holds:

  • The cost of solving Cn rises when n increases: though the output space of H(n) reduces with bigger n values, the individual cost of each invocation of H(n) increases and more than cancels the gains obtained through the space reduction. (This result holds until n becomes close to the square root of N, at which point things become more complex to analyze.)
  • When the attacker tries to solve Cn, giving him additional values H(k)(m) for values k > n does not help him, because he could have trivially computed them himself (H(n+1)(m) = H(H(n)(m)), and so on). If obtaining these extra values was a good idea, then he would do it right away.
  • When the attacker tries to solve Cn, giving him an additional value H(k)(m) for a value k < n indeed helps him, because it allows him to solve Cn by solving the comparatively simpler Ck.

Of course, we are speaking only theory here; with hash functions offering an output of more than 100 bits, the involved costs are way too high to be envisioned. In practice, preimages on simple hash or double-hash are unfeasible -- unless the hash function is not "perfect" and we can exploit a structural weakness of that specific hash function, at which point anything goes.

share|improve this answer
add comment

What you're describing is a hash chain which is the mechanism used in the S/KEY one-time password system. From what I know about cryptographic hash functions, subsequent hashing of messages should not weaken the hash in anyway, especially if you're using a strong hash function. It would still be possible (with enough computing power) to obtain the input to the current hash, but hashing multiple times shouldn't make it easier for an attacker to derive the original message.

However, I am not entirely sure how to prove this cryptographically - perhaps Thomas Pornin will be kind enough to provide that answer.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.