1
$\begingroup$

Consider following simple RBG where SHA-256 of random noise (more than 200Bytes of 4 bits entropy per byte) is computed to produce 256 output bits

$\text{output} = \operatorname{SHA-256}(\text{randomNoise})$

Is security strength of collision resistance or pre-image resistance applicable to it i.e it provides 128 or 256 bit security?

According to NIST SP 800-90A section 10.1

The maximum security strength that can be supported by each DRBG based on a hash function is the security strength of the hash function for pre-image resistance

$\endgroup$

1 Answer 1

1
$\begingroup$

No.

Some clarification: SP 800-90A -> Recommendation for Random Number Generation Using Deterministic Random Bit Generators, as per your "DRBG" quotation. Yet your example is a TRNG covered by SP 800-90B -> Recommendation for the Entropy Sources Used for Random Bit Generation. But only in America. NIST does not have a monopoly on entropy nor random numbers.

The security strength of a TRNG is measured by the final output bias given that:-

$$ H_{out} \ngtr H_{in} $$

So post extraction, your 4 bit entropy source emerges with much better randomness, and a bias away from perfection bounded by the Leftover Hash Lemma:-

$$ \epsilon = 2^{-(sn-k)/2} $$

where we have $n$ = input bits at $s$ bits/bit of raw entropy from the source, $k$ is the number of output bits from the extractor (and ideally $\ll sn$). $\epsilon$ is the bias away from a perfectly uniform $k$ bit length string, i.e. $H(k) = 1 - \epsilon$ bits/bit. NIST accepts that $\epsilon < 2^{-64}$ for cryptographic applications.

Your $\epsilon \approx 2^{-272}$. So not bad assuming that your source does indeed produce 0.5 bits/bit of true entropy at all working temperatures.

$\endgroup$
4
  • $\begingroup$ I'm not sure what that $2^{-272}$ is. My reasoning is that when the input of SHA-256 is a multiple of 64 bytes and at least 128 bytes, the output is the result of a round function with 256-bit input the hash so far, which is very near full-entropy: and a 512-bit constant depending only on the length, with no entropy. For an ideal round function we would get 256−0.83…=255.07 bit of entropy, where 0.83… is from this. This is NOT the cryptographic strength (hence I don't make it an answer), only an upper bound/estimate of entropy in the result. $\endgroup$
    – fgrieu
    Apr 14 at 13:13
  • $\begingroup$ @fgrieu Err, it comes directly out of the lemma with crypt's numbers plugged in. It ties in exactly with NIST's assertion that entropy halves through hashing (if you use MD5 or AES with a 256 bit input). You see the lemma's effect much clearer if you use something like an 8 bit Pearson or CRC16 hashes to extract. $\endgroup$
    – Paul Uszak
    Apr 14 at 13:33
  • $\begingroup$ so this construction is safe to use 256 bit output as IV, Key nounce etc with 256 bit crypto primitives? $\endgroup$
    – crypt
    Apr 14 at 17:03
  • 1
    $\begingroup$ @crypt More than adequate, but what primitives are you talking about? Most block sizes are 128 bits, and even then IVs can be smaller given that a single key isn't over used. See crypto.stackexchange.com/q/78164/23115 and others relating to IV vs key. $\endgroup$
    – Paul Uszak
    Apr 14 at 17:11

Your Answer

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

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