5
$\begingroup$

The paper “Explicit Two-Source Extractors and Resilient Functions” (PDF) by Eshan Chattopadhyay and David Zuckerman is described by some as being a technological leap in RNG – opposed to slow and incremental benefits over time.

What benefits would a faster RNG have for cryptography in general? Does this make some formerly implausible scenarios possible?

$\endgroup$
  • $\begingroup$ one time pads need lots of randomness, so if you were using that to stream protected data, the generation rate will determine your bandwidth. $\endgroup$ – dandavis May 25 '16 at 3:05
10
$\begingroup$

This paper isn't about a faster RNG, and it's mostly only of interest in a computer science context rather than in an applied cryptographic context. These results reduce the theoretical requirements needed from two weak sources of randomness in order to combine them into a source of true randomness. However, in the applied world, we already have "enough" — a few bytes can seed a CSPRNG that will generate effectively infinite computationally-random bytes.

When systems today fall over due to randomness issues, it's usually due to systems-engineering failures: a good RNG wasn't used (despite them being widely and easily available), or not enough initial randomness was seeded (e.g., /dev/urandom on an embedded device), or a virtual machine was copied and restarted with the same initial random seed. These classes of problems aren't solved by improving our sources of randomness.

To your question directly, a faster RNG isn't of much practical use. A stream cipher seeded with enough randomness is effectively a DRBG, and can produce random bits extremely quickly — far more quickly than is needed for the overwhelming majority of use-cases. The operations that use that randomness typically execute far more instructions than do the operations to generate it.

Thomas Ptacek's response to this story on Hacker News is how I expect most crypto people feel about this.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Recreating a secure random objects with fresh entropy (in a loop) should probably in the list. If anything mucks up an entropy pool it's those kind of decisions. $\endgroup$ – Maarten Bodewes May 18 '16 at 21:49
  • $\begingroup$ "a few bytes can seed a CSPRNG that will generate effectively infinite computationally-random bytes." for sufficiently large values of "few". $\endgroup$ – Peter Green May 25 '16 at 23:44
4
$\begingroup$

Stephen correctly points out that the paper isn't about RNGs. I'll take the question literally, though, and remark that there are non-cryptographic applications that could potentially benefit from faster CSPRNG. Non-cryptographic users of PRNGs have to balance two concerns:

  • Speed
  • Biases

Faster generators tend to have more statistical biases, while less biased ones tend to be slower. Building a faster cryptographic PRNG would, effectively, give you more speed without introducing biases (or at least no biases observable to a computationally-bound adversary).

There are also PRNGs that, despite not being intended for cryptographic use, use cryptographic designs as part of a correctness argument. See for example Claessen and Pałka's splittable pseudo random number generators, which use cryptographic components not for security, but rather for correctness. This is an interesting elaboration of the previous point, however: correctness is lack of bias. But clearly, this is a case where faster crypto would allow faster non-cryptographic RNGs.

| improve this answer | |
$\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.