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.

(I updated the title, as I think there was some confusion as to the question)

Here's the question:

For example, if I have a bit stream that is 64K bytes long and there is about 16 *8 bits worth of entropy randomly dispersed in that byte stream, so I have 16*8 bits worth of entropy.

However, if I SHA256 that byte stream, I will now only have 32 bytes total rather than 64K bytes.

Some information has been lost of course, but perhaps all of the entropy is retained?

Another way of looking at the question, is the entropy of SHA256(10GB with 16 bytes of entropy) equal to SHA256(16 bytes with 16 bytes of entropy) and if not, how much exactly has been lost?

I'm having a hard time finding any literature which estimates entropy loss, just a lot of hand waving by various crypto engineers that it's all good.

Here's an algorithmic way of looking at it:

#!/bin/sh
HASHV=`echo <random secret> | sha256`
echo $HASHV
    while(true) ;
    do
    HASHV=`echo "$HASHV 00000000000000000000000000000000" | sha256`
    echo $HASHV
done

Will the entropy of HASHV decrease over time?

Anyone got anything specific? (refs to papers, books, etc are grand)

Relevant questions:

share|improve this question
    
CodesInChaos meant "The loss is neglible unless ...". – so normally most of the entropy is conserved, apart for the possibility of collisions. –  Paŭlo Ebermann Sep 17 '13 at 20:27
    
I thought it through a bit more, and I think what he means is that if the the number of bits of entropy > digest length will be impactful on entropy. (Obvious now that I think about it). Hopefully he will comment and link to how he actually calculated that effect. I could probably handle the detailed math, but he was a little too high level for me.. –  Blaze Sep 17 '13 at 20:28
    
Interesting proof here: class.coursera.org/crypto-preview/lecture/29, basically saying that if you are collision resistant on a small function, therefore you're collision resistant on the big function. He goes on to prove this by showing that a collision on the big function implies a collision on the small function. This is for a particular construct however. –  Blaze Sep 22 '13 at 0:07
add comment

1 Answer

up vote 12 down vote accepted

A simple way to imagine the effect of the hash function is a truncation. A "good" hash function ought to behave like a random oracle. If your source has entropy $s$ bits, then this means that the source somehow assumes $2^s$ possible values. When processed with a random oracle with an $n$-bit output, you force the $2^s$ input values into $2^n$ possible outputs.

When $s$ is smaller than $n/2$, then it is expected that the hash function will produce $2^s$ distinct values, and all your $s$ bits of entropy are preserved. When $s$ reaches $n/2$, collisions begin to appear, and each collision means a tiny fraction lost entropy. You still preserve most of it, though. When $s$ reaches $n$ (e.g. you hash an input with 256 bits of entropy, with SHA-256), then it is expected that you get about $0.6·2^s$ distinct output (you lost one third of the inputs to collisions), so the resulting entropy will be a bit more than $n - 1$ bits. When $s$ is higher than $n$, the output entropy will still rise, but never exceed $2^n$: you cannot have more than $2^n$ distinct outputs of $n$ bits...

To sum up, when hashing your input, you preserve almost all your input entropy, up to at most the output size of the hash function. To make things simple: when you hash with SHA-256 an input of entropy $s$ bits, then you get an output entropy at least equal to the lower of $s-1$ and 255 bits.

share|improve this answer
    
Interesting, so the length of the byte stream has no impact on the entropy? If I hash 10GB with 16 bytes worth of entropy, that has the same entropy as a hash of a byte stream of 16 bytes of full entropy? I'm working with something that could suffer an attack of that nature (shoving low entropy data into a pool in order to undermine the over all entropy of the system because it hashes). I've been told it works, I've just never seen the math behind it so I can verify it myself. –  Blaze Sep 17 '13 at 20:37
1  
@Blaze: No, the length does not matter; this is a consequence of assuming a hash behaves like a "random oracle". Cryptographic hashes are meant to be used this way, and any evidence that (e.g.) SHA-256 could not be would be considered a significant break. (This is a really good answer. P.S. (1-1/e) is "about 0.6"). –  Nemo Sep 17 '13 at 20:56
1  
Another way of looking at it, is that 16 bytes of entropy is a lot of entropy and so I never really have to worry about lose any amount of entropy over that due to the effects mentioned above. Thanks for the detailed comments though.. Very helpful! :) –  Blaze Sep 17 '13 at 20:58
    
Excellent answer. –  Stephen Touset Sep 17 '13 at 21:13
    
The answer is terrific! but it assumes the question is around a variable amount of entropy. I'm working with a constant sized amount of entropy (say, 16 bytes) and a variable sized bit stream. The random oracle side comment is a great hint though. Now I just have to figure out how it mathematically applies :) –  Blaze Sep 17 '13 at 21:50
show 1 more comment

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.