5
$\begingroup$

If one were to create a SHA256 hash using 256 coin flips converted to hex (which, as I understand it, is as "entro-phized" as one can capture in SHA256) then take that hash as a string, combine that with a hash of the word "cat" and hash the resulting 512 character string, would the resulting hash from that exercise be any less random than our "perfect" hash we began with?

My thinking is the final string would capture the same amount as the original randomness as what we started with because the "extra" entropy can not be captured and is lost. Is this the case and am I thinking about this correctly? Would hashing something with high entropy with something simpler ever cause a lower amount of randomness or does it only go up?

Thanks to anyone who can help explain this a little better.

$\endgroup$
6
$\begingroup$

A deterministic function $f(X)$ of a random variable $X$ never has greater entropy than the original random variable $X$.

(Side note: If you're not familiar with the technical terms random variable and expectation, or the definition of entropy in terms of them, I recommend you read up on some elementary probability theory first—the rest of this post will not make sense without these keywords! In the sequel, ‘entropy’ can be taken to mean Shannon entropy or min-entropy—both work, and coincide on uniform distributions, but cryptography works primarily in min-entropy. See this answer for a brief discussion of what entropy means from a crypto perspective.)

At best, if $X$ is a random $k$-bit string with uniform distribution and thus $k$ bits of entropy, the maximum possible, and if $f\colon \{0,1\}^k \to \{0,1\}^k$ is a permutation (a.k.a. bijection), then $f(X)$ also has $k$ bits of entropy. If $f$ is not a permutation, then $f(X)$ has strictly less than $k$ bits of entropy—although perhaps not much less.

In this case, $f$ is SHA-256, which we might model by a uniform random choice of map $F\colon \{0,1\}^k \to \{0,1\}^k$. There are almost certainly fewer than $2^k$ distinct outputs, because very few such possible values of $F$ are permutations. Specifically, fix an output $y \in \{0,1\}^k$; for each input $x \in \{0,1\}^k$, we have $\Pr[F(x) = y] = 1/2^k$, and $F(x)$ is an independent random variable for every $x$, so \begin{align*} \Pr&[\exists x. F(x) = y] = 1 - \Pr[\forall x. F(x) \ne y] \\ &= 1 - \Pr[F(0) \ne y]\,\Pr[F(1) \ne y]\cdots\Pr[F(2^k - 1) \ne y] \\ &= 1 - (1 - 1/2^k)^{2^k}. \end{align*} which, by linearity of expectations, is also the expected fraction of distinct outputs. As $k \to \infty$, this converges to $1 - e^{-1} \approx 0.632$.

Thus, over a uniform random choice of $F$, the expected entropy of $F(X)$, or $\mathbb E_F\bigl[H[F(X)]\bigr]$, is about one bit less than the entropy of $X$, or $H[X]$, where $H$ is the entropy operator.

What about iterating SHA-256? Do we lose a bit of entropy every time, so that $\operatorname{SHA-256}^{256}$ has zero entropy? No. If we independently chose another function $G\colon \{0,1\}^k \to \{0,1\}^k$, then over a uniform random choice of $F$ and $G$, the expected entropy of $F(G(X))$ might be about two bits less than the entropy of $X$. But that's a bad model for iterating SHA-256, because we are restricted to the case $F = G$, in which case $F$ and $G$ are as far from independent as possible.

Rather, there's a good chance that for any fixed function $F$, there are many cycles on which $F$ is a permutation, and restricted to which $F$ thus preserves entropy. There's usually one main big cycle, which lends itself to a drawing of a giant hairy rho: $\rho$. In the limit as $\ell \to \infty$, $F^\ell(X)$ maps $X$ to an independent uniform random point on one of the cycles, the choice of cycle being weighted by the number of points on and leading to that cycle.

But in practical terms for cryptography engineering? Usually we treat $\operatorname{SHA-256}(X)$ as a uniform random variable independent of everything else in the system (except where length extension attacks might be relevant) with entropy equal to that of $X$, or 256, whichever is smaller.

$\endgroup$
0
$\begingroup$

If you have two N bit values, one with $K < N$ bits of entropy and the other with $T<N$ bits of entropy then the result will be approximately $\text{max}(N,T+K)$ bit of entropy. Additionally, rehashing loses entropy at roughly a rate of 0.7 due to collisions (just think of the balls and bins probabilities) so the entropy is slightly less.

$\endgroup$
  • $\begingroup$ I have to press you for further explanation of your 0.7 collision statement. I can't see how repetitive hashing loses entropy. That would tend to 0 entropy in the limit and make KDFs rather pointless. $\endgroup$ – Paul Uszak Aug 21 '17 at 22:22
  • $\begingroup$ If you have a N bit hash it has $2^N$ possible outcomes. If this hash is a PRF then it is likely not a surjective function when you consider all N bit inputs. Thus, iterative hashing will yield more results in some set of fixed points or cycles. $\endgroup$ – Thomas M. DuBuisson Aug 21 '17 at 23:17
  • $\begingroup$ Would you be willing to answer more fully if I ask a formal question? $\endgroup$ – Paul Uszak Aug 21 '17 at 23:32
  • 1
    $\begingroup$ I assume the 0.7 figure quoted by @ThomasM.DuBuisson is probably an approximation to $1 - 1/e$, the expected fraction I derived in my answer of outputs reached by a uniform random function. $\endgroup$ – Squeamish Ossifrage Aug 22 '17 at 17:01
  • $\begingroup$ Yes, @SqueamishOssifrage has the math I was too dense to provide. $\endgroup$ – Thomas M. DuBuisson Aug 22 '17 at 20:24
-2
$\begingroup$

So this is what you're proposing:-

hashes

Cutting through your question to the crux:-

Would hashing something with high entropy with something simpler ever cause a lower amount of randomness or does it only go up?

There are two scenarios that have simple answers.

  1. This is a one off and you never repeat the hashing with "Cat". Then the entropy will be 256 bits plus a few from the other hash input. You are correct in that the entropy can never go down. It can however go up in non linear increments. If the binary sequence representing "Cat" happens to appear in the left hand 256 bits, the overall entropy will only go up very slightly as the frequency component of those letters will just be incremented. Think of it as compressing "CatCatCat...". It's just another cat :-) So output =~ 262 bits.
  2. If you constantly repeat this hashing with new coin tosses, and keep the cat in there, the entropy calculation will ignore it and you'll be left with just the random bits from the left hand side. This is termed a bit fixing source, and is a common occurrence in true random number generators. If you were using JPEG generation as an entropy source, the file headers and other JPEG artefacts would be your cats. Output = 256 bits in this case.

There is also a more complex scenario that I won't go into (unless pressed) concerning the actual entropy content of a randomness extractor /hash function. No one really knows the answer to this one though, and output < 262 bits.

So in conclusion, yes it can go up but certainly doesn't go down.

$\endgroup$
  • 5
    $\begingroup$ This is false on its face. A deterministic function of a random variable never has greater entropy than the random variable alone. As a pathological example, if $f\colon \{0,1\}^k \to \{0,1\}^k$ is the constant zero function $x \mapsto 0^k$ (i.e., a string of $k$ zeros), then no matter what the entropy of $X$ is, $f(X)$ has zero entropy. In the context of cryptography, ‘entropy’ practically always refers to the attacker's state of knowledge, so if the attacker knows the string ‘Cat’ is involved, that contributes nothing to the entropy of the design. $\endgroup$ – Squeamish Ossifrage Aug 22 '17 at 17:03
  • $\begingroup$ @SqueamishOssifrage What if the attacker doesn't know about the cat? And who mentioned an attacker? $\endgroup$ – Paul Uszak Aug 22 '17 at 20:27
  • 5
    $\begingroup$ If you're discussing entropy, then you're talking about someone's state of partial knowledge. Since this is crypto.SE, presumably that someone is an attacker. If the attacker doesn't know about the string ‘cat’, and you want security based on that assumption, then you must convincingly quantify the distribution of what could be there as far as the attacker knows. That's what entropy summarizes. $\endgroup$ – Squeamish Ossifrage Aug 22 '17 at 21:41

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.