2
$\begingroup$
  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?

$\endgroup$
  • 1
    $\begingroup$ Somewhat related: How much entropy is lost if 1 character is fixed in HMAC SHA-512? $\endgroup$ – e-sushi Jan 24 '17 at 11:08
  • $\begingroup$ Yes, but in this question I am specifically interested in the relationship between the input entropy and the output entropy in general. $\endgroup$ – cryptonoob400 Jan 24 '17 at 11:19
  • $\begingroup$ "Now the standard length of a 512 bit hash is 128 characters [...]" No, don't mix up the string representation (a.k.a. "serialization") of the hash output with the hash output itself. The output of a 512-bit hash function is a 512-bit sequence. That may be represented as eight 64-bit words, sixteen 32-bit words, 64 bytes or as a 128-digit hexadecimal numeral written out in ASCII, but those representations stand to that output in the same relation that the numeral 42 stands to the number forty-two. $\endgroup$ – Luis Casillas Jan 24 '17 at 19:25
  • $\begingroup$ True, I have edited the question and made it more precise, you have already interpreted my k as bits, good. So let's talk in the same units of measurement, thus k is now the bits of the output, and remember that the hash output is also a secret, where k bits are revealed. $\endgroup$ – cryptonoob400 Jan 25 '17 at 10:34
  • $\begingroup$ I think your actual question is: is a KDF (in this case unfortunately just a hash) irreversible? And the answer is: yes, loosing bits of the output doesn't tell you anything about the input; it does however make it possible to guess the password (entropy source) with a quickly growing amount of certainty. $\endgroup$ – Maarten Bodewes Jan 25 '17 at 10:59
4
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ My theory is that either a maximum 4*k bits are revealed, or that the entropy loss is proportional in % from the output to the input. It would be good if somebody would know the exact answer. $\endgroup$ – cryptonoob400 Jan 24 '17 at 11:20
  • 1
    $\begingroup$ @cryptonoob400 I checked this experimentally. You can see the code I used at github.com/hicksc/crypto.stackoverflow/blob/master/43235/… $\endgroup$ – Chris Jan 24 '17 at 13:37
  • $\begingroup$ I'm wondering: if I know 6 nibbles of hash output then how can I be 100% sure that it only matches a single input value (out of 6 nibbles of input "entropy")? Wouldn't I have at least a tiny bit of uncertainty left? I would expect something like $2^{24} - 1 \over 2^{256 - 24}$ uncertainty. What about 128 bit / 128 bits of input? Did you test that experimentally as well? $\endgroup$ – Maarten Bodewes Jan 24 '17 at 15:11
  • $\begingroup$ @MaartenBodewes Unless you are able to search the entire input space (and assuming a fixed padding - since SHA-512 does expect the input to be a multiple of 1024 bit), you can't be sure. But the formula isn't right: Assuming a random oracle instead of a hash, the probability for any input to have the same prefix of length $k$ (in bits) is $1 / 2^{k}$, and any of the other $2^n - 1$ inputs could be a partial collision, so in total $(1 - 1/2^{k})^{2^n - 1}$ for having no other partial preimage. With $k=24, n = 24$, this is $(1 - \frac{1}{2^{24}})^{2^{24} - 1}\approx 0.36788$. $\endgroup$ – tylo Jan 24 '17 at 16:33
  • $\begingroup$ My formula isn't right - that's probably true. But I'm not sure that this answer is correct either. $\endgroup$ – Maarten Bodewes Jan 25 '17 at 0:19
4
$\begingroup$

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.
$\endgroup$
  • 1
    $\begingroup$ Great job framing the answer in terms of a security game. $\endgroup$ – Chris Jan 24 '17 at 20:51
  • $\begingroup$ All right, I would also like to point out that the SHA512 hash is also a private key, I thought that was obvious the way I phrased the question. So only k bits are revealed from it, althought both the revealing of the hash or the entropy would be a total compromize. $\endgroup$ – cryptonoob400 Jan 25 '17 at 10:30
  • $\begingroup$ @Luis Casillas Didnt you wanted to say n-k-512, so if 4 bits are revealed, then I'd have to add 516 bits of entropy to get 0 entropy loss. So 516-4-512=0, similarly if we have 512bit entropy, then 512-4-512=-4 bits of entropy lost. $\endgroup$ – cryptonoob400 Jan 25 '17 at 10:45
1
$\begingroup$

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.

$\endgroup$

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.