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?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Hitting a short cycle would be bad for security, but the chance of doing so is negligible. $\endgroup$
    – CodesInChaos
    Nov 23, 2017 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, 2017 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, 2017 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.

Improve this answer
$\endgroup$

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.