5
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ What do you mean by "rate of bits"? $\endgroup$ – Elias Apr 12 '17 at 11:01
  • $\begingroup$ When I have a stream generating one block of random numbers of size S bits per step, and put them through a hash giving N bits, then the rate of random numbers is reduced from S per step to N per step by the factor S/N. So what I meant was very simple. $\endgroup$ – michael Apr 12 '17 at 11:22
  • $\begingroup$ I'm not sure if this helps or hinders, but you realise that H does not have to be a cryptographic hash function or secure at all if A and B are true entropy sources? It just has to produce uniformly random output. A simple matrix multiplication will work, and that matrix can be of arbitrary size so you could easily have a "block" size of 100 kbits. $\endgroup$ – Paul Uszak Apr 12 '17 at 11:44
3
$\begingroup$

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:-

avalanche effect graph

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If SHA is not a good random oracle (what I understand), what does it mean in terms of random numbers generated by my mentioned appoach? $\endgroup$ – michael Apr 12 '17 at 11:24
  • 1
    $\begingroup$ @michael I don't think that has been quantified but if possible you should just use SHA-256. $\endgroup$ – Elias Apr 12 '17 at 11:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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