Why does a Hashing Function produce good Random Numbers if Input is random?

Question

I've heard about using a hash approach to create random numbers based on two independent entropy sources A, B:

$h_{i} = H(a_i+b_i)$

$H$ could be for instance SHA-1, or SHA-256.

My questions are:

1)

I read that hashing an input of s Bits to an output of n bits will reduce entropy because of truncation. The accepted answer in

How much entropy is lost via hashing when you add known or low entropy data?

sounds totally reasonable for me. But what does it mean in terms of quality of randomness? When an input of, lets say, 1024 bits is hashed to 256 bits, of course entropy gets lost. But can't I say, that the "remaining" 256 bits are still good random numbers and not comromised by the truncation of length? Isn't it just the rate of available random bits which is reduced, not the quality of randomness?

2)

Why is a hash function $y=f(x)$ like SHA-1 a random oracle at all? So far I know, it means, that the set of arguments x is mapped to a set of results y, distributed equally over $2^{256}$ values in the case of SHA-256. Why is this the case? Is there a rigorous proof for that or is it only a working assumption? It would mean for my feeled understanding:

• An s-bit value $x_1$ feed into Hash results in n bits $y_1$,
• An s-bit value $x_2$ feed into Hash results in n bits $y_2$,
• When $x_2$ differs from $x_1$ in only one bit position, all bits of $y_1$ are totally "uncorrelated" to the bits of $y_2$, regardlesss of the changed bit position.

Is that right?

Although I feel that this should be the case for a good hash of course, I wonder if the goal is only approximately achieved or really accurate? (Even the word "uncorrelated" is difficult to grasp for me, since, in fact, there is some kind of correlation over the hash-algorithm)

Answer 1

1) Yes, the upshot is that the entropy rate is reduced to 2^block_size per pass irrespective of the input as long as the hash's input entropy is large enough. What constitutes large enough is contentious on this forum. Your linked question suggests all input entropy is extracted (subject to truncation of course). Other literature /questions suggests that it is halved*

As for quality it is more correct to talk about entropy rather than random numbers (which mean many things to many people). Entropy is entropy is uncertainty. As for the untruncated part above, your 256 bits, they contain 100% entropy or H = 1 bit /bit. The other 768 bits of possible entropy are discarded. What's kept is good. It can't be more random than random**. So you could either increase the hash block size or reduce the input length to avoid entropy wastage.

2) The goal of output bit non correlation is actually achieved. If it wasn't, many cryptographic random number generators (such as /dev/random and java.security.securerandom) would be biased and not feasible. This is down to a property called avalanche effect which can be measured. With some random inputs and fiddling about, you can arrive at a distribution such as:-

where you can see that 50% of the output bits will change if you change any particular input bit.

Notes.

*I wish we could resolve this open issue on crypto.SE as it makes answering this type of question difficult on the maths.

**A minorishly small caveat. Whilst you can't mathematically be more random than random, you can have a safety factor. If you're extracting randomness from an entropy source and you're just on the limit (Hout = Hin*), the entropy output can drop below 100%. This will depend on your apparatus, precision, temperature stability etc. If you include a safety factor of 10 so that Hin = 10Hout you could ostensibly say through squinted lips that the randomness is 10x better.

Answer 2

I mostly agree with your statements. To answer your questions:

1. Obviously the entropy reduces if the entropy of $s$ is greater than $2^n$. Using a good hash will however result in that maximum amount of entropy.

2. Indeed, SHA-1 is not a random oracle. It is a common assumption that a hash function acts like one. Since collisions for SHA-1 have now been practically found that assumption is clearly wrong. The practically used primitives, like compression functions and block ciphers, are thoroughly cryptanalyzed but not proven secure.