15
$\begingroup$

Suppose I have a 128-bit random binary string (128 bits of entropy), then I hash it using SHA-256, then I take the first 128 bits of the output hash. Does the taken bit string still have (almost) 128 bits of entropy or the entropy is reduced to 64 bits? (I mean another 64 bits of entropy probably lies in the second 128 bits of the output hash).

I am confused because in the definitions of cryptographic hash functions that I have read in the past it was said that if one bit of input is changed then every bit of the output changes with a probability of $1/2$. It seems from this we can deduce that our truncated output still has (almost*) the same entropy as the input. Is that right?

*: I added 'almost' to mean ignoring the possible hash collisions.

$\endgroup$
8
  • $\begingroup$ Related to this. It does not change the problem that you use a 256-bit hash truncated to 128 bits, or a 128-bit hash. The entropy is slightly reduced from the original 128 bits, because of the collisions in the 128-bit hash; there are almost no collisions in the 256-bit hash. $\endgroup$ Mar 26, 2015 at 21:29
  • $\begingroup$ I am not concerned about small entropy reductions due to collisions, etc. I read elsewhere in this site that the entropy rate (entropy per bit) is reduced proportionally when we get a longer output than input using a hash function. That means the entropy rate of our output hash will be 128/256=0.5 bits per bit, so the entropy of the first 128 bits of the output should be 128*0.5=64. Is that right or not right?! $\endgroup$
    – user40602
    Mar 26, 2015 at 21:32
  • 3
    $\begingroup$ The reasoning that keeping half the bits keeps half of the entropy is wrong, because the 256 bits of the hash of a 128-bit string are far from random. There is marginally less entropy in the hash truncated to 128 bits than there is in the 256-bit hash. Analogy: if you take the 2-bit hash that hashes 0 to 01 and 1 to 10, there's 1 bit of entropy in the output for random input. Truncate that to the first bit, and you still have 1 bit of entropy in its output. $\endgroup$ Mar 26, 2015 at 21:36
  • 3
    $\begingroup$ I am pretty sure @fgrieu is correct, as input to the hash is handled as the key; imagine a known plaintext encrypted with a block cipher and truncated, the effect the key has on transforming the plaintext is what you are trying to measure $\endgroup$ Mar 27, 2015 at 1:11
  • 5
    $\begingroup$ @Stephen Touset: if your split a string of independent random bits (with even distribution, or at least the same distribution for all bits), then the entropy spreads evenly. However if the bits are correlated, the sum of the entropy in each half can be greater that the original entropy. In the extreme example of a two-bit string where the first bit is drawn by coin toss, and the second bit decided as the opposite of the first, there's one bit of entropy in the whole string, in the first bit, and in the second bit. $\endgroup$ Mar 27, 2015 at 7:04

2 Answers 2

20
$\begingroup$

Expected entropy in the output of a random oracle

The expected entropy in the output of a $h$-bit random oracle fed with random $h$-bit input is close to $h-0.8272$ bit, for even moderate $h$ (e.g. at least $32$). As $h$ grows, that expected entropy becomes arbitrary close to $h-\eta$ bit with $$\begin{align}\eta&=\frac 1{e\ln(2)}\sum_{i=1}^\infty\frac{\ln(i+1)}{i!}\\ &=0.82724538915300508343173\dots\text{bit}\end{align}$$ where the sum is given by A193424.

Proof, where I'll be using $a\approx b$ as a convenient shorthand for $\displaystyle\lim_{h\to\infty}\frac a b\ =\ 1$

  • For a particular distribution implemented by the oracle, let $n_j$ be the number of output values appearing exactly $j$ times among the outputs for all inputs. The exact entropy $H$ for that particular distribution can be computed from the $n_j$ by applying the definition of entropy, giving $$\begin{align}H&=\sum_{j=1}^{2^h}n_j\;\frac j {2^h}\;\log_2\left(\frac{2^h}j\right)\\ &=\frac h{2^h}\sum_{j=1}^{2^h}j\;n_j\;-\frac 1{2^h}\sum_{j=1}^{2^h}n_j\;j\;\log_2(j)\end{align}$$ where we have (by merely counting what all inputs lead to) $$\sum_{j=1}^{2^h}j\;n_j\;=2^h$$ thus $$h-H=\frac 1{2^h}\sum_{j=1}^{2^h}n_j\;j\;\log_2(j)$$
  • For fixed $j$ and as $h$ grows, by counting of the possibilities, we can establish that for random distribution, odds that any particular value is reached $j$ times is $\displaystyle\approx\frac 1{e\;j!}$. Thus for fixed $j$ and as $h$ grows, the expected $n_j$ is $\displaystyle\approx\frac{2^h}{e\;j!}$.
  • In the exact expression of $h-H$, all the terms in the sum are non-negative. To obtain an asymptotic of the expected $h-H$ when $h$ grows, we can thus replace $n_j$ by its expected value, and obtain that when $h$ grows the expected value of $h-H$ is $\displaystyle\approx\frac 1 e\sum_{j=1}^\infty\frac{j\;\log_2(j)}{j!}$.
  • The stated result follows by defining $i=j-1$, and removing the sum's first term, which is zero.

I've been unable to locate an earlier mathematical derivation. The closest I found is an empirical estimation of $\eta$ to 4 decimals by Andrea Röck: Collision Attacks based on the Entropy Loss caused by Random Functions, WEWoRC 2007, slides; with more in her thesis.

Update: In a 2020 presentation (page 41), William R. Cordwell and Mark D. Torgerson of Sandia National Labs give $0.827245$, without attribution.

My first empirical derivation was using a program which draws $2^h$ pseudo-random $h$-bit values and counts how many values are reached how many times; for $h=35$ (the largest I could do with 20GB RAM), three runs gave:

             run 1                run 2                run 3
  0  12640123427 36.79%   12640183855 36.79%   12640308584 36.79%
  1  12640408212 36.79%   12640365800 36.79%   12640104651 36.79%
  2   6320124091 18.39%    6320013534 18.39%    6320174710 18.39%
  3   2106681541  6.13%    2106762262  6.13%    2106726749  6.13%
  4    526645276  1.53%     526674914  1.53%     526679947  1.53%
  5    105334156  0.31%     105325000  0.31%     105330269  0.31%
  6     17561277  0.05%      17551924  0.05%      17556150  0.05%
  7      2507918  0.01%       2508727  0.01%       2505282  0.01%
  8       313971  0.00%        313943  0.00%        313406  0.00%
  9        34748  0.00%         34553  0.00%         34755  0.00%
 10         3424  0.00%          3542  0.00%          3546  0.00%
 11          291  0.00%           287  0.00%           292  0.00%
 12           31  0.00%            24  0.00%            24  0.00%
 13            4  0.00%             3  0.00%             2  0.00%
 14            1  0.00%             0  0.00%             1  0.00%
 15+           0  0.00%             0  0.00%             0  0.00%
entropy   34.172763 bit        34.172758 bit        34.172751 bit

Application to the question: the entropy for the output of SHA-256 truncated to its first $128$ bits when fed a random $128$-bit input is about $127.173$ bit, down from very close to $128$ bit before truncation (see final note). The truncation does not halve the entropy, because the halves are not independent. The right line of thought is that SHA-256 truncated to its first $128$ bits is a fine $128$-bit hash, and behaves like a random oracle.

Note: if we consider a random function from $\{0,1\}^{128}$ to $\{0,1\}^{256}$, most likely there is a small $k$ (most often $0$ or $1$, sometime $2$, rarely $3$ or more) such that $k$ outputs have exactly two corresponding inputs, $2^{128}-2k$ outputs have exactly one, and $2^{256}-2^{128}+2k$ outputs have none (odds that any output is reached three or more times are negligible).

Therefore, in this most likely case, the entropy on output of that function when fed a random $128$-bit input is $-k\;2^{-127}\log_2(2^{-127})-(2^{128}-2k)\;2^{-128}\log_2(2^{-128})$, that is $128-k\;2^{-127}$.

The best model we have for SHA-256 (not truncated) for $128$-bit input is a particular function chosen at random among functions from $\{0,1\}^{128}$ to $\{0,1\}^{256}$, thus we can conclude the entropy for the output of SHA-256 when fed a random $128$-bit input is likely exactly $128-k\;2^{-127}$ for $k\in\{0,1,2\}$, which is very nearly $128$ bit, down to about the 37th decimal places.

$\endgroup$
5
  • 2
    $\begingroup$ @D.W.: given your long-running interest in entropy loss by iterated hashing, you might like this which solves the question for the first iteration (asymptotically, and in practice). Also, it shows we can numerically explore the first few iterations, and the reference I cite gives estimates. $\endgroup$ Mar 27, 2015 at 19:39
  • $\begingroup$ And what should be said about entropy rate? (Regarding both full (256 bit) hash and truncated (128 bit) hash) $\endgroup$
    – user40602
    Mar 30, 2015 at 7:56
  • 1
    $\begingroup$ @user40602: the definition of entropy rate that I know is for a process; what would it be in the context of the question? $\;$ If that process is: generate a 128-bit random string and output its SHA-256 (resp. SHA-256 truncated to 128-bit), its entropy rate is $\approx128$ (resp. $\approx127.173$) bit per output symbol. $\endgroup$ Mar 30, 2015 at 16:02
  • 1
    $\begingroup$ It should be noted: Your statements are for the first application of this process. Iterating this method should not have a linear loss in entropy (otherwise $1/0.8272$ iterations would reach 0 entropy). In general, I think it helps to think of the difference in entropy as redundancy and not unused or lost entropy. Like in your example where the 2nd bit is the inverse of the first. $\endgroup$
    – tylo
    Nov 24, 2019 at 19:00
  • $\begingroup$ @tylo. Indeed. The problem of entropy lost (or added redundancy) after more than 1 iteration is a harder question. The best approximation I know is by D.W., originally on coderpunks, 1998 (text file), also on sci.crypt, 2001. I asked there but nobody answered. $\endgroup$ Nov 24, 2019 at 19:56
-1
$\begingroup$

Remember that a hash function does not create entropy (it can make it very hard to detect a lack of entropy though). Therefore, if the input has 128-bits of entropy, the output has 128-bits of entropy as a maximum. If the output size is 256 bits, then each output bit has $0.5$ bits of entropy. Taking $1/2$ the output bits will cut the entropy in half.

To be on the safe side (due to loss from collisions and such), it is safe to assume that the output is only $0.85 \times$input entropy.

To get a good understanding of what NIST requires associated with this topic (truncated output of functions on entropy) read NIST SP 800-90B.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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