1
$\begingroup$

This is probably one of those embarrassingly simple questions, but here goes. Consider the following two constructs:

  1. CSPRNG made out of a block cipher (AES) with a counter such as

    1

  2. CSPRNG made out of a secure hash function with a counter (Java SecureRandom's SHA1PRNG) such as

    2

The common denominator is the provision of a counter. What's the point of the counter as you could simply do state' = F(state) once you have state established? So the state would be the seed alone, and it would be iteratively processed to produce the random stream. What does the counter bring to the party?

$\endgroup$
5
$\begingroup$

A counter has a practical advantage: it makes a random stream seekable instead of purely sequential. Which doesn't matter for a CSPRNG but does for a DRBG and parallelization.

But it also works around two possible issues with recursive calls to a hash function: the cycle length, and fixed points.

Hitting a fixed point would be particularly nasty; what should have been a random number generator would start generating the same value forever.

In practice, the risk is negligible unless your function is not a secure hash function, or has a really small block size. The cycle length is not an issue either, if only because storing all the observed values before biases become exploitable is not practical.

Still, using a counter is reassuring. Hitting a fixed point would have zero security implications. Neither would a point with a very short cycle length.

$\endgroup$
  • $\begingroup$ Hitting a short cycle would be bad for security, but the chance of doing so is negligible. $\endgroup$ – CodesInChaos Nov 23 '17 at 7:41
  • 1
    $\begingroup$ It is assumed to be negligible. Having some kind of mitigation build into a secure algorithm when an assumption doesn't hold is a good way of future-proofing that algorithm (and even if you do not agree with this, it might well be a reason for adding the counter to the input). $\endgroup$ – Maarten Bodewes Nov 23 '17 at 11:02
  • $\begingroup$ A counter also has the primary advantage of simplicity, making it easy to analyze, implement, and verify. “Everything should be as simple as possible, but no simpler”. $\endgroup$ – rmalayter Nov 23 '17 at 12:00
3
$\begingroup$

The first random stream is just a block cipher in counter mode. If you think back to the security proofs of things like counter mode vs iterated encryption like CBC you'll remember the bounds were better on counter mode. More intuitively, a CBC-like operation could result in a short cycle, such as where $E(E(a)) == a$ - this could never happen when encrypting unique counter values.

The same concept of a short cycle can appear in the second construct as well, but I can't immediately see how adding one does anything besides change the case in which this would occur. Consider $H(S_i + H(S_i))$, if $H(S_i) = 0$ then we have a tight loop. With $H(S_i + H(S_i) + 1)$ we'd need $H(S_i) = -1 = 2^{160}-1$ to get the same loop. For what it's worth, I have not seen this particular construct before which is why I hinted for you to cite it.

$\endgroup$

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.