0
$\begingroup$

I'm thinking about the evaluation of a cipher or separate cipher round as a PRNG. In general, we can encrypt consecutive natural numbers and check them with some randomness test. But PRNGs don't work like this. They use their output like a new input.

Shouldn't it be like that the ciphers should have long periods in such a test? Do they have long periods? If not, they should not be considered good PRNGs, correct? And is it possible that a cryptographically secure PRNG will have a short period for some inputs?

$\endgroup$
3
  • $\begingroup$ It is a problem. Any theory about period length for AES applied to itself?. One should test some sequences. If you are not close to the expected, then we can say your cipher is not a PRP. $\endgroup$
    – kelalaka
    Jan 26 at 15:03
  • $\begingroup$ Ok, and then if we are not close to the expected period it cannot be a secure cipher? What is expected period in 128-bit cipher? They wrote there is could be about 2^127? But how can we check it? It is to big to check it computationally. $\endgroup$
    – Tom
    Jan 26 at 15:23
  • $\begingroup$ That is the problem, you look for some possible biases in small samples. And the better is using some good ciphers, hash functions to produce PRNG like NIST 800-90A Rev 1 $\endgroup$
    – kelalaka
    Jan 26 at 15:32
3
$\begingroup$

They use their output like a new input.

That's not correct, generally CS-PRNG's keep a state and use separate bits (or possibly the state run through a PRF) as output.

Shouldn't it be like that the ciphers should have long periods in such a test?

Yes, and the same goes for the CS-PRNG's. Yes, if you can trigger a CS-PRNG to repeat a long enough pattern then something is wrong. There are many other reasons why a PRNG is broken of course. It may be biased or how an attacker could get the state back, for instance. Beware that a cipher is not necessarily a CS-PRNG.

And is it possible that cryptographically secure PRNG will have short period for some inputs?

When correctly seeded they should have unpredictable output. If you can seed according to the specifications and it is still computationally feasible to get into a cycle then no, then it would not be cryptographically secure.

Generally you should not get repeated output as long as the seed is unique. Secure hash functions are often used to accomplish this.

$\endgroup$
8
  • 1
    $\begingroup$ "They use their output like a new input." I think they're thinking of fast key erasure CSPRNGs, which create enough extra data to re-seed themselves after every request (and never release that extra data to the user, instead just mix it into their state). That IS recommended, but isn't the same as using their output as a new input since it's never outputted to the user. $\endgroup$ Jan 26 at 20:44
  • $\begingroup$ @SAIPeregrinus I didn't bring my magic ball, maybe Tom can clarify. I do sure hope that this is what Tom means :) $\endgroup$
    – Maarten Bodewes
    Jan 26 at 20:47
  • $\begingroup$ Yeah, it's a sensible guess, but people have all sorts of misunderstandings. Just figured I should mention it in case they were thinking of it and needed the name. And clear up the distinction that it's not the output of the CSPRNG, but rather the internal generator stream that gets fed back. That distinction matters, if you used the public output it would weaken security. $\endgroup$ Jan 26 at 21:05
  • $\begingroup$ All PRNG repeat eventually. You (and possibly even the universe) just won't live long enough to see it. $\endgroup$ Jan 27 at 13:51
  • $\begingroup$ Yeah, that's in my answer; it should not be computationally feasible to get into a cycle. $\endgroup$
    – Maarten Bodewes
    Jan 27 at 14:00

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.