3
$\begingroup$

If entropy is hashed with SHA-256 for example, and the input has exactly 256 entropy bits, how much entropy is reduced after hashing due to collision? Is there any reference that explains how to calculate this?

$\endgroup$
7
  • $\begingroup$ Does this answer your question? Entropy preservation through cryptographic hash function $\endgroup$
    – kelalaka
    Dec 9, 2023 at 8:24
  • $\begingroup$ @fgrieu the answer includes that ...on $2^{256+𝑘}$ distinct inputs... $\endgroup$
    – kelalaka
    Dec 9, 2023 at 9:15
  • $\begingroup$ @kelalaka: yes this answer is helpfull, and explains why (and to a degree how much) increasing the number of possible inputs increases (slightly) the output entropy. However it does not consider a bounded input entropy, as the question does. $\endgroup$
    – fgrieu
    Dec 9, 2023 at 11:30
  • $\begingroup$ @fgrieu Another one, the half of the answer for 256 coin flipping If a SHA256 hash with high entropy is then hashed with one made from low entropy, is the resulting hash higher/same/lower entropy? $\endgroup$
    – kelalaka
    Dec 9, 2023 at 17:58
  • $\begingroup$ @kelalaka: that question is vague, so must not be selected as a dupe [Update: I mean we must not close the present Q as a dupe of that]. The most up-voted answer gets 0.632 bit entropy loss for $2^{256}$ uniform inputs (when it considers $2^{256}+k$ inputs they are uniform too, contrary to the present Q). That, and the 0.66 bit in Maarten's answer, are below the more accurate 0.827245 bit by only about 20%, thus close enough for many practical purposes. It confirms that the approximations made are sensible. $\endgroup$
    – fgrieu
    Dec 9, 2023 at 18:50

2 Answers 2

6
$\begingroup$

If entropy is hashed with SHA-256 for example, and the input has exactly 256 entropy bits, how much is entropy reduced after hashing due to collision?

With more than say 200 bits of entropy in an input distribution that we can computationally sample, it's computationally impossible to distinguish the output of SHA-256 from the uniform distribution, which has 256 bits of entropy. If we could, that would be a break of SHA-256 (argument: it's very unlikely there will be any collision in what we can sample in the input or output). Thus in the question there is no practical risk associated with (falsely) considering that no entropy is lost due to collisions. Still, the question stands for it's theoretical interest.

If the input distribution with 256 bits of entropy can take only $2^{256}$ values (equivalently: is uniform), then Shannon entropy is reduced by $\eta=0.827245389153$… bit for all practical purposes. Examples of such input sets: all the 32-byte strings; all 64-character uppercase hex strings in ASCII.

That can be rigorously derived for a model of SHA-256 as a random oracle or a random function, and input that consists of $2^{256}$ equally likely input bitstrings chosen in a way that allows to computationally sample from the distribution, or without referring to SHA-256. Such formulation is necessary because there are pathological input distributions with $2^{256}$ equally likely input bitstrings, thus 256 bits of entropy, loosing more or less than $\eta$ bits of entropy:

  • all the entropy is lost for the uniform distribution over any set of $2^{256}$ colliding values, which demonstrably exists;
  • no entropy is lost for the uniform distribution over a set with one preimage for each output that has a preimage, which we expect1 is every 256-bit bitstring.

After some back and forth, I remain uncertain about if we need the condition that the input can take only $2^{256}$ values. Removing that condition tends to modify the expected distribution of the output towards including more possible output values, but I doubt this can much changes the output entropy, if at all. I'll try to iron that out.

All the above generalizes to any unbroken cryptographic hashes wide enough for collision resistance and aiming at uniform output.

any reference

I derived $\eta=\displaystyle\frac 1{e\ln(2)}\sum_{i=1}^\infty\frac{\ln(i+1)}{i!}$ there in 2015, for uniformly random input the size of the output. I know no earlier formal derivation. There's an empirical estimation 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. There's a value to 6 decimals in a 2020 presentation (page 41) by William R. Cordwell and Mark D. Torgerson of Sandia National Labs, without attribution or method stated.

The extension to uniform input distribution that can take exactly $2^{256}$ values and the other stated properties is easy with a model of the hash as a random oracle or random function: the output entropy remains that of $2^{256}$ 256-bit values independently drawn uniformly at random.


Extension: if the input entropy $e$ is more than 256 bits, more entropy is lost by hashing with a 256-bit hash: over $\max(\eta, e-256)$. And if $e$ is even a little below 256-0.5 bits (including if we re-hash a previous hash), it's lost considerably less entropy than $\eta$ by one hash. The aforementioned Cordwell&Torgerson source states it's lost ≈20 bits after a million iterated hashes starting from full entropy, in line with this source. The lost entropy grows about logarithmically with the number of iterations (assumed computationally feasible, thus unlikely to include a sizable fraction of cycles).


1 For a random function, that's when the input set size is well over the coupon collector bound, which is the case for cryptographic hashes. For SHA-256 and with due consideration for it's Merkle-Damgård structure, an argument is that for fixed-size 119-byte input (the maximum size for 2 rounds) it enters in the last round 256 nearly arbitrary chaining bits and 440 fully arbitrary message bits, that is more than $2^{695}$ inputs in the Davies-Meyer round function, which is way above the coupon collector bound for 256-bit output.

$\endgroup$
1
  • $\begingroup$ upvoted both answers. thanks for the link to your older answer $\endgroup$
    – kodlu
    Dec 9, 2023 at 18:27
5
$\begingroup$

Let's assume that we have a uniform distribution. This is certainly not a given, but usually we assume that hash functions will try and have each output value be equally likely.

In that case we can use a calculation derived from the birthday problem to estimate the amount of collisions:

Approximation for the Probability of Collision: $$ P(\text{collision}) \approx 1 - \exp\left(-\frac{M^2}{2N}\right) $$

Expected Number of Collisions: $$ E \approx \frac{M^2}{2} \times \left( 1 - \exp\left(-\frac{M^2}{2N}\right) \right) $$

In these formulas:

  • $P(\text{collision})$ is the probability of at least one collision occurring.
  • $E$ is the expected number of collisions.
  • $M$ is the number of elements (or inputs) being hashed.
  • $N$ is the number of possible hash values.

The expected number of collisions $E$ in a hash table can be approximated using the formula: $E \approx \frac{1}{2} \cdot N \cdot \left(1 - \exp\left(-\frac{M^2}{2N}\right)\right)$, where $N$ is the number of possible hash values ($2^{256}$ in this case) and $M$ is the number of inserted elements ($2^{256}$ as well).

So the estimated number of expected collisions for $2^{256}$ inputs in a 256-bit hash function is approximately $2^{255}$. However, this includes multi-collisions.

We can also calculate the number of expected, distinct output values:

$$ U \approx N \left(1 - e^{-n/N}\right) $$

The estimated number of unique values obtained from randomly generating a 256-bit value $2^{256}$ times is approximately $2^{255.34}$.

So I'd estimate you'd loose less than a bit of entropy.

However, in the end you may want to have all output values to be equally likely. That will mean that you will need around twice the entropy as input. See here for more information.

$\endgroup$
1
  • $\begingroup$ upvoted both answers, the approximate approach is quite good $\endgroup$
    – kodlu
    Dec 9, 2023 at 18:28

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.