Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 3 down vote accepted

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.

My thanks to @fgrieu for helpful comments on this answer.

share|improve this answer
    
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 at 7:51
1  
@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 at 10:20
1  
@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 at 9:42
1  
I asked the question on math.se, with reference to this answer. –  fgrieu Mar 21 at 7:41
1  
@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 at 8:04
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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