# Entropy when iterating cryptographic hash functions

Consider a cryptographic hash function that maps $n$-bit strings to $n$-bit strings:

$$\DeclareMathOperator{\H}{H} \DeclareMathOperator{\SHA}{SHA-256} \H(x) : \left\{0,1\right\}^{n} \mapsto \left\{0,1\right\}^{n}.$$

Let $\H^i$ denote the result of iterating $\H$ $i$ times, i.e., $\H^1 = \H$, $\H^2 = \H \circ \H$, etc.

Suppose we choose $x \in \{0,1\}^n$ uniformly at random. What is the estimated amount of entropy in $\H^i(x)$? I'm most interested in the case $n=128$.

More specifically, I'm particularly interested in the following special case. Define a hash function $\H$ by truncating the output of $\SHA$ to $128$ bits, i.e.,

$$\H(x) = \SHA\left(x\right)\mid_{128}$$

With this definition of $\H$, what is the entropy of $\H^i(x)$ now, when $x$ is chosen uniformly at random from $\{0,1\}^{128}$? Does $\H$ maintain 128 bits of preimage resistance from $\SHA$, or is it significantly weakened? Are any other security properties of the underlying hash function weakened?

My estimate of the entropy after $i$ iterations is roughly $128- \lg i$ bits (as $i$ grows large). I don't have a proof of this, but I'll lay out my rough back-of-the-envelope calculations below.

Here is the general problem:

Problem 1. Let $F:\{0,1\}^n \to \{0,1\}^n$ be a random, i.e., chosen uniformly at random from the set of all functions with that signature. Let $F^i$ denote the result of iterating $F$ $i$ times. Let $X$ be uniformly distributed on $\{0,1\}^n$. Let $F$ be known to the adversary, and $X$ be secret. What is the entropy of $F^i(X)$?

I don't know how to solve that problem. But here is a related problem that I do know how to solve.

Problem 2. Let $F$ be as above. Let $f_i$ denote the fraction of $n$-bit values that can appear at the output of $F^i$. In other words, $f_i = |S_i|/2^n$, where we define $S_i$ to be the the set $S_i = \{F^i(x) : x\in \{0,1\}^n\}$ of all values that can appear as the output of $F$ iterated $i$ times. What is the value of $f_i$, as a function of $i$?

Note that the answer to the problem 2 gives us a heuristic rough estimate at the answer to problem 1. In particular, if we assume that $F^i(X)$ is approximately uniformly distributed on the set of all possible values (i.e., on $S_i$), then the entropy of $F^i(X)$ will be approximately $n - \lg f_i$.

And I can give you a reasonable solution to problem 2. In particular, using a crude heuristic, $f_i$ approximately satisfies the following recurrence relation:

$$f_{i+1} \approx 1 - e^{-f_i},$$

where $f_0 = 1$. The first few values of $f_i$ are $f_1=0.632$, $f_2=0.469$, $f_3=0.374$, $f_4=0.312$, $f_5=0.268$, $f_6=0.235$, $f_7=0.210$. This recurrence relation does break down when $i$ gets extremely large, certainly by the time $i$ reaches $2^{n/2}$ or so, but this might not be a major concern for the values of $i$ you care about in practice.

Asymptotically, when $i$ gets large enough (but not so large that it gets close to $2^{n/2}$), I think that a crude approximation to $f_i$ is

$$f_i \sim 2/i.$$

Thus, for large (but not too large) $i$, this gives us a crude estimate for the entropy of $F^i(X)$ as

$$n-\lg f_i \approx n+1-\lg(i).$$

Plugging in $n=128$ in your particular problem, we get $129-\lg(i)$ as an estimate of the entropy after $i$ iterations. This is within $\pm 1$ bit of my estimate at the top of the answer.

Incidentally, I have in my notes that a better approximation is $f_i \sim 2/(i+\log(i))$, but I don't know where I got this from, so it might be faulty. If that approximation is accurate, then a better estimate of the entropy of $F^i(X)$ is $n+1-\lg(i+\log(i))$.

Again, as a reminder, all of these estimates are only intended to be used when $i$ gets large (but not crazy large). When $i$ is small, you can calculate $f_i$ directly using the recurrence relation above. And all of these estimates are just estimates, that rely upon several approximations, which may be pretty crude.

• One critic: I do not see that that $f_{i+1}\approx1-e^{-f_i}$ takes into account the fact that the same function $F$ is iterated. Granted that makes no significant difference for small $i$, but I see no argument that it extends indefinitely (in particular, past the stage where most $n$-bit inputs have reached a cycle).
– fgrieu
Mar 19 '14 at 7:51
• @fgrieu, great point! For large enough $i$, this formula certainly becomes inaccurate. For instance, when $i \ge 2^{n/2}$, it is likely that the entropy will be about $n/2$ bits, and after a certain point it won't get any smaller no matter how much you increase $i$ (because typically when iterating a large random function, there is a single large cycle of length about $2^{n/2}$ that most inputs feed into). Thank you!
– D.W.
Mar 19 '14 at 10:20
• @Stephen Touset: the question would be more general if it asked the entropy in $H^i(x)$ with $x$ uniform, for some hash $H(x):\{0,1\}^{n}↦\{0,1\}^{n}$, as instantiated for $n=128$ by $x↦H(x)=\operatorname{SHA-256}(x)\mid_{128}$. In fact, that's what the present answer is about. It would be fine with me if the question was changed to that (I can remove my comments to the question, which only are about the different location of the truncation).
– fgrieu
Mar 20 '14 at 9:42
• I asked the question on math.se, with reference to this answer.
– fgrieu
Mar 21 '14 at 7:41
• @StephenTouset: Or, more simply said: truncating the output of a PRF yields a PRF. Notice that as worded now, the question truncates the output of SHA-256, at each use, effectively building a 128-bit hash. Initially, the question truncated the input of SHA-256. There is a simple reduction form the initial question to the current one: first truncation reduces to 128 bit of entropy, then there are a number of 128-bit hashes, then a final SHA-256 that is almost entropy-preserving.
– fgrieu
Mar 24 '14 at 8:04