3
$\begingroup$

This question already has an answer here:

Is it significantly easier to reverse a sha256 hash if you know that the input was a 32 byte output of sha256?

I assume for most outputs of sha256 there will be zero, one or two possible 32 byte inputs.

Mapping and storing all of the values is infeasible, but I am still worried that constraining the input to being exactly 32 bytes may weaken sha256.

Is this a valid concern?

$\endgroup$

marked as duplicate by Squeamish Ossifrage, Maarten Bodewes Sep 21 at 21:21

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

6
$\begingroup$

Answer

No, that would not be possible. It would be very weird indeed if a hash was suddenly invertible if the input was of a specific form - it would basically mean that the hash would be broken. Iterating over all the possible values of those 32 bytes is certainly not an option either.

Peculiarities

That does not mean that such a structure doesn't have it's peculiarities though, the first link provided by mikazo is a good summary of what to expect.

If you want to avoid such peculiarities then I would suggest you follow the suggestion by CodesInChaos to use a HMAC construct with a fixed key instead of SHA-256 directly. As e.g. length extension attacks not feasible with SHA-3 (Keccak) you can probably use that without reverting to a HMAC.

Notes

  • The inner state of SHA-2 is basically the output (after padding & inclusion of the message size); so a 32 byte input is certainly not an issue in itself, as the inner state is exactly the same size.
  • Your scheme may have some properties that can be compared with a hash based PRNG
$\endgroup$
3
$\begingroup$

Is it significantly easier to reverse a sha256 hash if you know that the input was a 32 byte output of sha256?

Assuming a random N-bit input ($N>3256$) versus a 256-bit input, for all practical intents and purposes, the difficultly is extremely difficult (read: not feasible by today's computational capabilities) for both.

If you are talking about a theoretical reversing attack, then you have to understand collisions. There are far fewer collisions that exist when the input is $N=256$ bits versus $N\gg256$ bits, or even when N is unknown. The input space for one is $2^{256}$ and (roughly) $\sum_{i}2^{i}$ (where $i=$ allowed bit sizes) for the other. Yes, there is likely several orders of magnitude more collisions for an output corresponding to the latter case, so you would have to sort through all of them which would be orders of magnitude more difficult. However, as a matter of practicality, this doesn't really matter.

I assume for most outputs of sha256 there will be zero, one or two possible 32 byte inputs.

On average, if you assume 256-bit inputs and outputs, and reasonable randomness, something like 1.5 inputs get mapped to a single output, but some outputs could have more, while others have zero. This leads me to the following point (outside of what you initially asked, but related to the Related Question linked above.

Tangential point

For equal sized inputs and outputs with a (deterministic) function that has random-looking mappings, then if you apply the function to itself $f(f(...f(x)))$, the final output space is certainly less than the input. In fact, the output space it is approximately $2/3$ of the size of the input space after each iteration. So if you apply $f()$ 10 times, then the output space is approximately $(\frac{2}{3})^{10}$, which is less than 2% of the original input space. This sounds horrible, but it really is insignificant when applied with SHA-256. Reducing the brute force attack time of SHA-256 by a order or magnitude or two is insignificant. Crypto and related hash algorithms are not affected by a reduction in security of just a few bits or so. (More info than you wanted, but I'm trying to be complete.)

$\endgroup$
  • $\begingroup$ This is a problem with your approach to size the output space after n iterations.While the 2/3 ratio is roughly true for the first step, based on the classic birthday problem formula 1−(1−(1/N))^(n−1) = 0.63212 when N = n = 2^256 $\endgroup$ – Louis LC Jul 22 '15 at 13:45
  • $\begingroup$ ... But on the second iteration, you cannot simply multiply this 0.63212 ratio by itself. You have to use the birthday formula again, only this time the number of people is smaller than before (n' = n x 0.63212). Using Wolfram Alpha's sequences I have calculated the results after a few iterations (for a smaller initial space of 2^16): 0.632, 0.469, 0.374... I have checked that these ratios hold true for a sha16 function (based on a truncated version of sha256). See jsfiddle.net/louislc/7o15yfto $\endgroup$ – Louis LC Jul 22 '15 at 14:08
  • $\begingroup$ Here is the Wolfram Alpha sequence: bit.ly/1IkLJH0 $\endgroup$ – Louis LC Jul 22 '15 at 14:14
2
$\begingroup$

Is it significantly easier to reverse a sha256 hash if you know that the input was a 32 byte output of sha256?

It depends on what you are comparing to.

Is it easier to reverse an SHA-256 hash of some SHA-256 hash than that of a random number? Sure, it can be. For example, it is easy to find that the preimage of

73641c99f7719f57d8f4beb11a303afcd190243a51ced8782ca6d3dbe014d146

is

5e884898da28047151d0e56f8dc6292773603d0d6aabbdd62a11ef721d1542d8

because that happens to be the SHA-256 hash of the ASCII string password. A dictionary attack is easy for such predictable inputs.

However, if you are concerned about whether you can turn $H(H(r))$ into $H(r)$, where $r$ is a large random number/string, then no, there is no practical weakness. There is no loss of security if $r$ is more than 256 bits and unpredictable by the attacker.

$\endgroup$

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