How much original entropy is lost if a part of the hash is known?

Question

1. You have an entropy source of n bits
2. You hash it with SHA-512 for example
3. k bits of the SHA-512 output are publicly revealed, but the SHA-512 hash is also a private key to be protected (k<=512)

The question is how many bits are lost in the original entropy source by revealing/losing k bits in the hash?

Especially: the original entropy source has less entropy than the hash output size. Because if it has more or the same as the hash output then it will be equivallent to 512-k, the question is… what if it's less?

Answer 1

A good hash function like SHA-512 is thought to behave like a random oracle and reveal nothing about it's input, however if the source has less potential entropy (fewer bytes) than the hash output size then this can be exploited as a potential search problem.

If the original source has fewer bytes than the hash output size, and this number of bytes is a computationally feasible search problem (i.e. < 80 bytes) then revealing k bytes of the hash is equivalent to revealing up to k bytes of the input source, since the candidate preimages of the output can be found.

Thinking about the scenario in which fewer bytes of the hash are revealed than there are bytes of entropy in the input source, there will be many inputs which map to the same abbreviated hash output. Ideally however these inputs would be a random distribution from the input source and not reveal any of the source entropy until the hash output size was equal to the input size.

Extending this idea further it's obvious that something about the input entropy is revealed, since as the number of bytes revealed approaches the number of bytes input the number of possible preimages is reduced which reduces the entropy until the stage that there is none and we have (ideally) only one preimage.

I modelled this and found experimentally that for SHA512 the amount of entropy about the input which is lost for each byte of the hash function output known is approximately (ideally) one byte. This makes sense in the context of the definition of a cryptographic hash algorithm.

e.g.

Input value with 6 nibbles of potential entropy: $9840563$

First 6 SHA512 nibbles: $8ae967$

$8: 1049140 \approx 2^{20}$

$8a: 65275 \approx 2^{16}$

$8ae: 4099 \approx 2^{12}$

$8ae9: 270 \approx 2^{8}$

$8ae96: 13 \approx 2^{4}$

$8ae967: 1 = 1$

Answer 2

So you have a random string $Input$ with $n < 512$ bits of entropy. Thinking of it as a game, it's one where on each turn the adversary offers a guess for the value of $Input$, and if that guess is right then the adversary wins. Since $Input$ has $n$ bits of entropy, optimal adversaries will win, on average, in $2^{n-1}$ guesses.

So now let's modify the game by computing $Output = SHA512(Input)$, and showing $k$ bits of $Output$ to the adversary. The adversary's goal is still to guess $Input$, but the question is how much quicker they succeed.

Let's consider the limiting case where $k = 512$. Yes, all of the output hash bits are revealed to the adversary. If SHA-512 really is 512-bit preimage resistant (as it is claimed), then given only $Output$ it takes on average $2^{511}$ guesses to find any string $str$ such that $SHA512(str) = Output$, and that string may not be $Input$. But the attacker can directly guess $Input$ quicker than that. We conclude then that even revealing the full SHA-512 output doesn't make it any easier for the adversary to guess $Input$.

---

That may sound very unexpected, but what's going on here is two things. First, you did not specify your scenario explicitly, so I had to fill in the blanks, possibly in a way different than what you intended. You asked (my boldface):

The question is how many bits are lost in the original entropy source by revealing/losing 4*k bits in the hash?

Maybe you meant to ask something more like this: If we reveal $k$ bits of the output of the hash, how much entropy do the remaining $512 - k$ bits of the output have?

Second: Kerckhoff's Principle. When we say that $Input$ has $n$ bits of entropy, what we're implicitly assuming is that the adversary knows the probability distribution that $Input$ is sampled from and can use this knowledge to devise an optimal strategy for guessing its values. My observation then is that revealing the whole digest of a secret value preserves its secrecy up to the preimage resistance value for the hash function. And in this scenario the secrecy of the input is bounded by the assumed entropy value, which is lower than 512 bits.

---

And with that we can attack the reformulated question:

• If we reveal $k$ bits of the output of the hash, how much entropy do the remaining $512 - k$ bits of the output have?

Let' assume that any $k$ bit truncation of SHA-512 has $k$ bits of preimage resistance. In that case:

• If $512 - k < n$, then it's quicker for the attacker to guess the missing hash output bits, so their entropy can't be greater than $512 - k$. The entropy loss is at least $n + k - 512$.
• If $512 - k ≥ n$, then again because of preimage resistance the attacker's best strategy is to guess $Input$ directly.

Answer 3

There are two approaches to this question, a computational and an information-theoretic approach. It is unclear from the question which one is preferred.

I am going to assume that the number of output symbols that are not revealed ($512-k$) is larger than $n$, and consequently that $n$ is smaller than $512$.

Computationally, this is fairly easy to analyse. A hash function like SHA-512 in an application like this can reasonably be approximated by a random function. And for a random function, unless you know the preimage of the function value, each part of the function value is independent of every other part, so knowing $k$ of the output symbols does not help you determine the remaining $512-k$ output symbols.

For a random function, the only possible approach is to enumerate the inputs. If $k$ is large compared to $n$, you expect a random function to be injective (1-1), so you should be able to determine the input uniquely after enumerating half of all possible inputs ($2^{n-1}$).

If $k$ is small compared to $n$, you expect about $2^{n-k}$ possible preimages, each one leading to a different value for the $512-k$ output symbols.

If $k$ is approximately the size of $n$, you expect some collisions which makes exact (or even approximate) calculations tedious.

In either case, however, the expected effort involved in finding the output symbols is on the order of $2^n$ hash calculations, which means that this is the "computational strength" of the $512-k$ remaining output symbols.

Information-theoretically, we need to count the number of possible preimages. Assuming that SHA-512 can be approximated by a random function, we get as above, three cases: $k\ggg n$, $k\approx n$ and $k \lll n$. In the first case, you expect zero entropy. In the second case, you may have a small amount of uncertainty, while in the third case you have $n-k$ bits of entropy.