8
$\begingroup$

Everywhere I read, indistinguishability of output from true random is stated as a requirement for CSPRNGs. However nobody bothered to give the rationale for such a strong requirement.

Specifically, Yarrow and Fortuna both use a block cipher as the generator, and both limit the amount of output that can be produced by a particular key. The key is changed (aka rekey) once the limit is reached. Their reason is that since the block cipher does not generate duplicate output blocks in their design, the attacker can request for a large amount of output from the PRNG, find that there are no duplicate blocks, and determine that the output is not true random. So what?

The only information the attacker can get from this is the cipher's block size, and this doesn't weaken the security one bit. Furthermore this would have been public knowledge if the implementation was open source. I don't see how the lack of duplicate blocks would weaken our security.

|improve this question
$\endgroup$
  • $\begingroup$ "The only information the attacker can get from this is the cipher's block size, and this doesn't weaken the security one bit." [citation needed] $\endgroup$ – Stephen Touset Oct 5 '15 at 2:31
  • $\begingroup$ @StephenTouset When I thought about the problem, the lack of duplicate blocks will only be apparent if the attacker performs block-sized frequency analysis on the random output (and provided they requested sufficient output for meaningful analysis). They can just brute force through the common block sizes and once they hit a value that gives no duplicates, they can be pretty sure it's the block size we use. $\endgroup$ – wmjdgla Oct 5 '15 at 6:53
  • $\begingroup$ Now you need to demonstrate that a) this is the only thing the attacker can possibly learn, and b) that this can't possibly lead to an exploitable weakness. See points 4 and 2, respectively, in CodesInChaos' answer. $\endgroup$ – Stephen Touset Oct 5 '15 at 18:03
  • $\begingroup$ @StephenTouset Ah, that's precisely the point of my question. I'm hoping that someone could prove me wrong ;) Regarding your b) - if that was really a concern then block cipher implementations would have kept the block size information hidden, wouldn't they? $\endgroup$ – wmjdgla Oct 6 '15 at 7:51
  • $\begingroup$ A block cipher and random number generator have distinct and independent security requirements. $\endgroup$ – Stephen Touset Oct 6 '15 at 18:55
15
$\begingroup$
  1. We simply strive for crypto that's as close as possible to ideal. Indistinguishably is the strongest property we can demand from a PRNG/streamcipher.
  2. It's hard to predict which non ideal properties will lead to problems at some point in the future. For example the non ideal properties that lead to padding oracles, BEAST, CRIME or the RC4 biases were known for years before they were shown to be exploitable.
  3. Many security proofs assume indistinguishability, so if the PRNG is distinguishable, this weakens the proof. If the PRNG is distinguishable under certain conditions, even if it's a seemingly harmless distinguisher, then a proof relying on indistinguishability becomes useless if those conditions are met.

  4. Consider a message encrypted using a block-cipher in CTR mode. This has the property that no blocks in the key stream will be identical (just like Fortuna/Yarrow without re-keying). When the ciphertext contains identical blocks, the attacker knows that the corresponding plaintext blocks were different, because the corresponding key-stream blocks were different as well.

    Admittedly that's not a huge leak in most contexts, but it is a leak. It might lead to problems in some contexts, for example if the message only uses a few different values for each block.

|improve this answer
$\endgroup$
  • $\begingroup$ I think #3 is incredibly important. "Indistinguishable from random" is a class of systems which has mountains of proofs to draw upon to determine it's strength. If your system can be distinguished from random, then there are a multitude of very specific nuanced ways the system can fall apart, and its hard to have good documentation on how each one does or does not actually fall apart. $\endgroup$ – Cort Ammon Oct 5 '15 at 1:42
  • $\begingroup$ #2 is just as important, to me. Known shortcomings are obvious areas for analysts to attack, which they frequently do, and to devastating effect. $\endgroup$ – Stephen Touset Oct 5 '15 at 2:33
  • $\begingroup$ #4: I think this point can be clearer. True, it's a leak. But isn't this just an artefact of the mode of operation? Similar criticisms can be made of CBC mode - a modification to plaintext at a particular offset does not modify the ciphertext before that offset. Is there a leak? Yes. Is that a flaw? Hardly, though it becomes a flaw when the use-case demands that such info be kept hidden, but the implementer chose CBC which exposes it. So does the use case of CSPRNGs demand that we avoid the absence of duplicate blocks? I think your other points addressed this well enough. $\endgroup$ – wmjdgla Oct 6 '15 at 7:43
2
$\begingroup$

A PRNG must be indistinguishable from a true RNG only in a complexity theoretic sense. No polynomial (efficient) algorithm must be able to distinguish both. The fact that a true RNG has more collisions (by the birthday paradox) then a PRNG (say, running in counter mode) is not distinguishable by a polynomial algorithm.

|improve this answer
$\endgroup$
1
$\begingroup$

If you can distinguish a source from true random, then that can directly translate into less guesses required in order to brute force a decryption - recovering the internal RNG state, which may lead to further attacks into decryption or key recovery, depending on what other resources an attacker can control. If I know probabilities of some output bits are not exactly 50/50, then I can search them matching any skewed ratios, and that directly translates into a more efficient search. Depending on exactly how a source deviates from true random, and how easy it is to distinguish, this can translate into a few bits of key entropy gained in an attack, to the whole thing (the latter possible for a non-cryptographic RNG).

The re-keying in Yarrow and Fortuna are bolstering the algorithms against a potential and currently theoretical search of this type, although no practical attack based on distinguishing via lack of collisions is widely known or published at this time. The notes on the design of Yarrow cover the philosophy behind this, and this paper discussing nature of attacks on PRNG which shares some authors.

|improve this answer
$\endgroup$
  • $\begingroup$ I don't see why the generic distinguisher against CTR mode would lead to a key recovery attack faster than brute-force. $\endgroup$ – CodesInChaos Oct 4 '15 at 8:35

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.