2
$\begingroup$

It's widely accepted that both block ciphers and hash functions are great cryptographic primitives to build a CSPRNG.

I'm thinking of creating a protocol where, provided that there is a source of random to generate a root secret (which will become a key if used with a cipher or a seed if used with a hash function), this is used to feed an algorithm to generate an arbitrary amount of random data.

I have to decide on whether to use a block cipher (e.g. AES, or anyway any secure cipher with a block sie of 128-bit) or a secure hash function (e.g. SHA256).

I've made some considerations and I came up with a question that is blowing my mind.

First, let's see how both the approaches would be put in place.

  1. If a block cipher is used, the root secret is used as the key and then a 128-bit counter is gradually incremented and encrypted to create a stream of random data, which is exactly how the CTR mode works.

  2. If a hash function is used, the root secret is used either as a prefix which is then concatenated with counters, or used as the key of some construct such as HMAC (in this case the counters would be the data).

Now, a consideration needs to be done, and from this consideration originates my mind-blowing question.

With a block cipher, the same 128-bit sequence can never reappear again, until all the possible values of the counter are used (and hence the counter rewinds), which is impractical in any real-life scenario. Yes, if 128-bits of the random stream which originate from the block cipher are taken at a random offset which is not multiple of 128 bits (16 bytes) you will retrieve bits that are part of two distinct blocks and the same 128-bit sequence will appear more that once, but i'm not going to take in account this scenario for my question.

Which a hash function, instead, the same 128-bit (or 256-bit if we are using SHA256) can potentially reappear with two different nonces (and hence before the nonce rewinds). This probability is of course extremely unlikely and I believe that can be expressed with 1/2^N (where N is the bit-length), which is exactly the same "probability" that that value will naturally repeat with the block cipher construct.

Now, finally, my question:

With the block cipher construct, the same N-bit value cannot repeat, while with the hash function it may repeat, even though it's extremely unlikely. In a mathematical sense I guess that both "probabilities" can be equated, but...

In which way the probability/entropy/security is affected by the impossibility of repetition of the block cipher construct over the hash function construct? Which one would you choose?

And, another question:

What is the real entropy/security of any N-bit sequence of a random stream obtained by using one of the two constructs, provided that they originate from a fixed-length key?

Thank you for your attention and patience in reading all this :-)

$\endgroup$
  • 1
    $\begingroup$ Do you realise that both hash and cipher based RNGs are used very successfully in the real world, with little security differentiation? Would this fact make your question moot? $\endgroup$ – Paul Uszak Apr 9 '17 at 23:03
  • 1
    $\begingroup$ ever considered dual counter mode? its dual CTR instances with independent keys, and the outputs are XOR'd to produce the RNG output $\endgroup$ – Richie Frame Apr 10 '17 at 5:07
  • $\begingroup$ Yeah, I believe it will "solve" the "problem". $\endgroup$ – Deril Apr 11 '17 at 0:06

Your Answer

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

Browse other questions tagged or ask your own question.