2
$\begingroup$

Given an RNG and a PRNG.

We define RNG(k) to mean that the RNG produces k random bits.

We define PRNG(k, seed) to mean that the PRNG uses seed to produce k pseudo-random bits.

Case 1: - Generate n random bits using just the RNG.

bits = RNG(n)

Case 2: - Generate n random bits using the PRNG, and using the RNG as a seed

seed = RNG(n/2)

bits = PRNG(n, seed)

My question is whether there is any practical or even theoretical difference to these in terms of security?

  • From an outsider, I am assuming that both would seem to be completely random bits.

  • How does the amount of random data fed to the PRNG from the RNG affect the randomness? My intuition is that if the PRNG is fed less than 256 bits of random data, then the result from the PRNG can be calculated by brute force.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Just to be clear: Is RNG = TRNG with cogs, lasers and high voltage? $\endgroup$
    – Paul Uszak
    Aug 4, 2019 at 16:02
  • $\begingroup$ Most hardware RNG:s have visible bias in the sampling. So you whiten them with cryptographic algorithms. $\endgroup$
    – Natanael
    Aug 4, 2019 at 16:37
  • 1
    $\begingroup$ @Natanael Not sure that 'bias' is the right word here. From comment elsewhere: I would strongly steer everyone away from 'whitening' TRNG output. It's a crutch for poor raw entropy measurement, misunderstood extraction and undermines the value proposition of a TRNG project. Better to get the extractor right instead, based on information theory. I guess this isn't relevant to this question though. Just asking for clarification whether RNG = TRNG? $\endgroup$
    – Paul Uszak
    Aug 4, 2019 at 16:47
  • $\begingroup$ @PaulUszak Yep, RNG = TRNG, and the PRNG is cryptographically secure. $\endgroup$
    – WeCanBeFriends
    Aug 4, 2019 at 20:27
  • $\begingroup$ @PaulUszak it depends entirely on the design. You can't always smooth out raw bits internally without software. Decay timing don't lend itself well to be used as raw output bits without processing, for example. Same with thermal noise which follows some spectral distribution, in addition to bias in the sensor. You estimate entropy during design and testing, not by measuring bits. At best you can look at raw bits to detect degradation. But you need whitening to actually use it for anything needing dense entropy, like asymmetric cryptography. $\endgroup$
    – Natanael
    Aug 4, 2019 at 22:17

2 Answers 2

Reset to default
2
$\begingroup$

In 99% of cryptography there is no practical difference between your cases as long as $ |seed| = \frac{n}{2} \ge 128$. Computational indistinguishability means that the streams from both cases will appear properly random. Our current knowledge is insufficient to invert a good well seeded CSPRNG (your PRNG). Information theory suggests that inversion can't be ruled out, but we can't do it as yet. Perhaps tomorrow or the day after. See P=NP and Kolmogorov/algorithmic complexity.

The missing 1%. For the truly dedicated who use one time pads (OTPs), there is a huge difference between the cases. Information theory dictates that case 1 can create a OTP. Case 2 specifically requires $ |bits| < \frac{n}{2} $. Otherwise the output is theoretically invertible. In this case though, the above theorem implies that the output from PRNG need only to not introduce bias. It need not be cryptographically secure, nor even a dedicated PRNG. A simple random matrix will do. But it begs the question of why bother if you already have a functional TRNG running at a similar rate?

Consequently, your RNG is more random than your PRNG from a certain perspective. It's the same differentiator that separates /dev/random from /dev/urandom in blocking *nixes.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ @WeCanBeFriends I guess that I just seem to attract quite a lot of repetitive anonymous punishment voting from a small cabal of individuals. Check the chatroom to find them. $\endgroup$
    – Paul Uszak
    Aug 4, 2019 at 22:12
  • 2
    $\begingroup$ @WeCanBeFriends My para.1 covers your situation. The common technique sans TRNG is to seed a CSPRNG with 128 bits or more of entropy and be done with it. The technique scales from IoT devices to large servers. I added the 1% material because you asked about theoretical differences. A different question is in order if you have trouble getting the 128 bits together in the first place. $\endgroup$
    – Paul Uszak
    Aug 4, 2019 at 22:18
  • 1
    $\begingroup$ @WeCanBeFriends What specifically do you find helpful about this answer? The first sentence isn't wrong, just not very informative. The rest of the answer has little substance. The inversion part sounds silly. You don't defeat an algorithm simply by knowing something and waving your arms around. Cryptanalytic attacks are nothing like that. $\endgroup$
    – Future Security
    Aug 5, 2019 at 3:36
  • 2
    $\begingroup$ @FutureSecurity What I got from the answer, was that practically speaking, there is no difference. One thing that popped into my mind was that the PRNG may weaken the security of the system, if used in this way. However, IIUC this answer states that this is not the case, unless we are talking about information theoretic security. I may have jumped to conclusions, however what I got was that from a computational complexity viewpoint, using 128 bits and expanding to 256 bits with a PRNG is as secure as just using a 256 TRNG. Unless I misunderstood the answer $\endgroup$
    – WeCanBeFriends
    Aug 5, 2019 at 12:44
  • 1
    $\begingroup$ @WeCanBeFriends Essentially, that's it! There was a $\ge$ sign there though:-) Clearly $ 2^{256} > 2^{128}$, but that's pretty moot as far as the practicalities of the expansive PRNG theme of your question is concerned. Or a practical attack, although I have noticed an ill-defined trend towards 256 bit thingies... $\endgroup$
    – Paul Uszak
    Aug 5, 2019 at 13:50
2
$\begingroup$

It takes a lot of effort to flip a coin 256 times. If you need to encrypt a message that's 512 bits long, it takes twice as much effort. Worse, your coin tosses are not perfectly uniform.

But if you pass the seed through a modern hash function like SHAKE128, the nonuniformity is inconsequential, and you have the potential handle not only 512-bit messages but arbitrarily long messages securely at no additional cost to your thumb!

…provided, of course, that you pay attention to what you're doing with the bits. Don't use these bits with RC4, for instance, and make sure to authenticate, not just encrypt, messages, and generally study the security of a construction as a unit rather than cobbling together parts like AES, HMAC, MD5, ECB, and PDQB.

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.