6
$\begingroup$

The way I understand it, stream ciphers are pretty much one time pads off-sourced to a PRNG (the seed is the key that generates the fake one time pad).

So why not just use one or more CSPRNGs (concatenated seeds, xored pad streams)?

Wouldn't breaking such a stream cipher be equivalent to breaking every single CSPRNG used?

Yet we have things like RC4 riddled with vulnerabilities, is it because performance is a concern? There are many applications where it's not, why not have something like I described for those cases?

$\endgroup$
1
  • 1
    $\begingroup$ It's worth noting that defining a "multiple stream cipher" encryption scheme is exactly the same mathematically as defining a single new stream cipher that just happens to produce the same output stream as your chosen stream ciphers XORd together. Consequently cryptographers prefer to work on a single strong stream cipher primitive that is also efficient. Indeed all modern stream ciphers are very strong, and use design elements of algorithms which came before. Simpler is almost always easier to analyze and (more importantly) easier to implement securely. $\endgroup$
    – rmalayter
    May 30, 2017 at 19:34

2 Answers 2

8
$\begingroup$

Yes, stream cipher is to OTP what CSPRNG is to true randomness.

Yes, breaking a stream cipher implemented with CSPRNGs XORed together (each independently seeded) demonstrably implies breaking each CSPRNG (or a side channel).

Yes, there has been less than perfect stream ciphers/CSPRNGs around. I guess that's for a large part because of efficiency concerns, and because their security was adequate for many of the intended uses (RC4 was designed with performance in mind, like 30 years ago; the first commercial use I saw of it was real-time decryption of Adobe Type Library fonts distributed encrypted on freeby CD-ROMs, with each font category unlocked by a 40-bit key).

I guess that we nowadays use single-CSPRNG stream cipher (like AES-CTR, Salsa, ChaCha..) because simplicity and speed are virtues. They are believed extremely secure, except for implementation attacks (penetration of platform, side channel).

$\endgroup$
2
  • 2
    $\begingroup$ @dingrite: For AES-CTR, there are side channels in the form of cache-based timing attacks. Or, more prosaically, for any cipher, plain old penetration of the platform. $\endgroup$
    – fgrieu
    Apr 15, 2017 at 14:20
  • 2
    $\begingroup$ @dingrite: All pure stream ciphers fail badly if the IV is reused, and do not provide integrity. But that's not unique to them: that applies equally to CTR and OFB modes (comparatively, CBC and CFB are less vulnerable). I see no other thing to be really careful about when implementing a stream cipher. $\endgroup$
    – fgrieu
    Apr 16, 2017 at 3:29
0
$\begingroup$

So why not just use one or more CSPRNGs

That's an extremely good question that has been asked elsewhere with no particular consensus amongst those scientists. There certainly wasn't a fundamental mathematical reason identified saying that you can't. Your hypothesis is correct. If you do:-

A ⊕ B ⊕ C

and only C is good, the construction is still secure even if they are all seeded from the same value as algorithmic ally different RNGs will produce totally different sequences. It is a mathematical feature that combining two poor stream sources produces a disproportionately large decrease in the overall error. And this error drops asymptotically to zero as more sources are combined. Yet this is never done (hypocritically with the exception of A5/1) with no mathematical explanation as to why not.

is it because performance is a concern? There are many applications where it's not

Again an excellent question that has no answer that I can find on this forum$. Excluding some initial short run biases, RC4 isn't that bad. Long run biases are so minuscule that there are currently no practical attacks. And it's very fast. If you add about 6 lines of code to it's output in the form of a Von Neumann extractor, all long run biases disappear. RC4 + VN would then be in the same situation as ISAAC with no known exploits. However there be a consequential speed reduction to only 6% of the original RND. Yet even the resulting ~10 million random bits /s is for some reason considered unacceptable. I too concur there must be an application out there somewhere that needs less than 10 Mb/s of random numbers.

To conclude, the cryptographic community (in as far as this forum goes any way) mysteriously prefers one single RNG that's as fast as humanly possible in all applications and environments from smart buttons to Xeons. So please don't consider this as any form of useful answer. Your good question just raises more questions.

Note.

$ My (possibly cinical) explanation is that using AES-CTR serves the interests of the NSA in allowing massive targetting of funding.

$\endgroup$
2
  • $\begingroup$ A5/1 does not simply XOR multiple stream ciphers together just because it's built from three LFSRs. $\endgroup$
    – forest
    Sep 8, 2019 at 7:28
  • $\begingroup$ Re-reading this answer, I see another mistake. While $A\oplus B\oplus C$ is as secure as the most secure keystream, this is not true if they are mathematically related as you claim. Example: $A = B$ and $C = A\oplus B$. $\endgroup$
    – forest
    Jan 6, 2020 at 7:29

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.