7
$\begingroup$

In a recent answer to a question about CSPRNGs, it was stated that…

  1. Nondeterministic algorithms where there is no such requirement, and ideally could be replaced by a true random generator. Example: operating system random generators, where the practical solution has been to compose a deterministic pseudorandom generator with a physical noise source, to yield output that is both nondeterministic and pseudorandom.

This got me thinking that this could potentially lead to further confusion due the terminologies used, so I decided to wrap this into a question to have a place to point people to…

  • Can an RNG which relies — among other things — on a non-deterministic physical noise source still be called "pseudo" random?
  • If, where do we draw the line between a CSPRNG and a CSRNG?
  • And where do we place a TRNG in this picture? Or is a CSRNG always a TRNG and vice versa, making every other (cryptographically secure) RNG a CSPRNG even when non-deterministic physical sources are part of the RNG?

EDIT

It would be nice if your answer would include some pointers to according references that underline your explanation(s). After all, a trustworthy reference can replace a thousand opinions and related discussions.

$\endgroup$
5
$\begingroup$

There seems to be a lot of confusing terminology here. Let me define everything to the best of my knowledge.

  • RNG: Some mechanism that produces random numbers.
  • CSRNG: An RNG that is safe for cryptographic use.
  • PRNG: An RNG that is a deterministic algorithm based off of a seed.
  • TRNG: An RNG that is based off of some unpredictable physical process.
  • CSPRNG: A PRNG that is safe for cryptographic use. (Assuming the seed is picked correctly)

I've never heard the term CSTRNG, but I could imagine it meaning a TRNG which is cryptographically secure. In general conversation, this is redundant because TRNGs are assumed to be cryptographically secure regardless. Even though it is not explicitly defined that way.

Can an RNG which relies — among other things — on a non-deterministic physical noise source still be called "pseudo" random?

Depends how the noise source is used. If the source is used as a seed for a PRNG, then it is in fact pseudo, since most of the randomness is "made up" by the algorithm.

If every bit of output is influenced by a different bit of input, then it can be considered a TRNG.

If, where do we draw the line between a CSPRNG and a CSRNG?

From my understanding, a CSPRNG is a subset of CSRNG.

CSRNG means Cryptographically Secure Random Number Generator. It may be pseudorandom, it may not. The only requirement is that it is safe for cryptographic use.

CSPRNG means Cryptographically Secure Pseudo Random Number Generator. This has the same requirements of a CSRNG (hence it being a subset), with the additional requirement that it be some sort of deterministic algorithm that accepts a seed.

And where do we place a TRNG in this picture?

The best description I've ever heard of a TRNG is an RNG based off of physical noise that has a mathematical basis for how every bit is based off of a different part of said physical noise. (Paraphrasing)

Or is a CSRNG always a TRNG and vice versa

I could trivially make a TRNG by recording my voice and using the bytes from the recording as randomness without any processing. That isn't cryptographically secure, making it a TRNG but not a CSRNG. This isn't common because a TRNG that isn't good for cryptography is a waste of money for the most part.

However, there are CSRNGs that are TRNGs (See: random.org).

They are separate categories with separate requirements. They do overlap, but they do not depend on each other.

making every other RNG a CSPRNG even when non-deterministic physical sources are part of the RNG?

A PRNG with a seed derived from a TRNG is still a PRNG. This is actually how a lot of random entropy is generated quickly. It isn't efficient to generate megabytes of entropy using physical sources. (Have you ever tried generating a public/private key pair using /dev/random? It's harsh) It's usually done by using physical sources to seed a CSPRNG, which does the heavy lifting.

Also, there are a lot of RNGs that are not CSPRNGs. Xorshift, LFSR, ARC4Random (when it was based off of RC4), and Mersenne Twister to name a few. These algorithms have biases or other problems that render them bad for cryptograpic use. However, they still output numbers that seem random to the naked eye.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ A few mistakes here. 1) How would you categorise /dev/random as there is no measurable entropy? 2) Random.org is not proven to be a TRNG - it's probably a CSPRNG. 3) Megabytes can easily be generated truly using an interference laser /beam splitter /direct photon counter 4) Your recorded voice generator would be useless due to bias 5) What about Intel's RNG where entropy in < entropy out? $\endgroup$ – Paul Uszak Jun 30 '17 at 10:46
  • 2
    $\begingroup$ 1) You and I agree /dev/random is in a grey area. I'd consider it a TRNG due to every output being related to some physical process. 2) The randomness is derived from radio noise. 3) I don't know enough about those to comment. 4) That's the point. It's truely random in the sense that the output is determined by an unpredictable physical process, but it's not cryptographically secure. 5) That seems to be a CSPRNG that is periodically seeded with a TRNG. $\endgroup$ – Daffy Jun 30 '17 at 19:05
3
$\begingroup$

(Disclaimer: I wrote the passage quoted in the question.)

  • Can an RNG which relies — among other things — on a non-deterministic physical noise source still be called "pseudo" random?

I would suggest that yes, this is reasonable, because a computationally unbounded adversary could distinguish its output from a true, full-entropy random stream, but the generators are designed to make those attacks impractically costly. So it's clearly not "true random" (full entropy), but "behaves like it" to an adversary.

Consider an adversary that has access to a black box instantiation of the Fortuna generator that incorporates a TRNG and a background thread that reseeds the generator periodically with random bits drawn from the TRNG, and exposes the PseudoRandomData operation as its sole public interface. The output of PseudoRandomData is computed with AES-CTR, and depends on the key and counter values at the time of the call. That key is a nondeterministic value (because of the way it depends on the TRNG output), but a simple brute-force attack on the output of a single call to PseudoRandomData recovers the value the key had at that time. This is unlikely to be enough to predict the output of later calls (because of true random reseeding), but it's certainly enough to distinguish Fortuna from a TRNG.

But of course such an attack is prohibitively costly, and the reason for this is that AES-CTR is a secure pseudorandom generator. The security of the Fortuna instance relies on the fact that it's the composition of a secure deterministic pseudorandom generator (in the conventional sense of the term) and a probabilistic reseeding mechanism.

  • If, where do we draw the line between a CSPRNG and a CSRNG?

I don't know exactly what line you're trying to draw here. Unlike for "pseudorandom generator" (the textbook notion, a function from bitstrings to bitstrings with an expansion factor such that when fed uniform random inputs the output cannot be efficiently distinguished from uniform random) and "pseudorandom function/permutation," I've not seen a definition for "CSPRNG" that I've found to be "nuts and bolts" practical. People routinely use the term to refer to stream ciphers like ChaCha, to the NIST SP 800-90A "deterministic random bit generators" (DRBGs), and to interfaces like /dev/urandom—but these are clearly three different types of object.

You might be trying to make a "true random" (full entropy) vs. "not true random" distinction here, but I've also found that this distinction is not very useful in practice. What I've found more useful in understanding the differences between various practical "(pseudo)random generators" is not whether they're "true random" or not, but to contrast deterministic vs. probabilistic algorithms:

  • Deterministic algorithm: Performing the same operations from the same initial state always yields the same result and final state. Often formulated as mathematical functions—stateless mappings from input values to output values.
  • Probabilistic algorithm: Performing the same operations from the same initial state yields a random result and final state (according to some distribution, not necessarily an uniform one). Sometimes formulated as probabilistic "experiments."

This can get confusing because the same algorithm can often be refactored and described either way. For example, CBC mode encryption is often described as either:

  • A probabilistic algorithm, where the random choice of IV is internal to the encryption algorithm;
  • A deterministic function, where the caller is required to input a random IV.

See, for example, Rogaway's "Nonce-based Symmetric Encryption" paper:

Abstract. Symmetric encryption schemes are usually formalized so as to make the encryption operation a probabilistic or state-dependent function $E$ of the message $M$ and the key $K$: the user supplies $M$ and $K$ and the encryption process does the rest, flipping coins or modifying internal state in order to produce a ciphertext $C$. Here we investigate an alternative syntax for an encryption scheme, where the encryption process $E$ is a deterministic function that surfaces an initialization vector (IV).

A similar thing can also be observed in the RNG world—for example, the NIST SP 800-90A DRBGs are formulated as deterministic functions, but they are evidently designed to be invoked with random inputs, in the context of a larger system that, when accessed as a black box, behaves probabilistically. People get confused over this, wondering for example whether the NIST DRBGs are suitable for use as stream ciphers. The answer there is that you could use a DRBG that way, but the more appropriate solution is to use a simpler algorithm designed to deterministically output a pseudorandom keystream from a key and a nonce, without all of the additional DRBG hooks that exist entirely for periodic reseeding.

But note that unlike with encryption where the normally exposed real-life interface is the deterministic one ("encrypt this message with this key and IV," which produces a deterministic result), the more usual public interface to OS random generators is not the DRBGs' deterministic interface, but rather a probabilistic interface ("read $n$ bytes from /dev/urandom," which produces a probabilistic result). So if you take the viewpoint of a user of /dev/urandom, invoking it through its public interface, it makes sense to call it both nondeterministic ("if I call it twice I'm likely to get different results, even if my program is in the same state before both calls") and pseudorandom ("the output cannot be distinguished from uniform random in any reasonable amount of time").

| improve this answer | |
$\endgroup$
  • $\begingroup$ A good answer, but you've dismissed TRNGs too quickly. £M's of annual research funding is spent all over the world on ever faster optical TRNGs , quantum key distribution networks are founded on them and I build them. Fortuna to a TRNG is like Bells to Laphroaig. They have their uses just like single malts do. $\endgroup$ – Paul Uszak Jul 1 '17 at 20:37
2
$\begingroup$

I break it up like this:

  • CS understood for now to be cryptographically secure
  • PR or R an approximation of random or truly random (R,HR,TR all mean the same thing)
  • NG a number generator

The number generator is rewarded the CS until it is shown that the numbers are not good enough for any cryptography you thought you could use them for, then you drop the CS and put the word "weak" or "unsecure". It's punished with the P as soon as it is shown that the hardware source is not solely responsible for the number (Entropy in >= Entropy out, that is the line-drawn). If its pseudo random then there is the chance it is also weak, but being weak doesn't stop it being a PRNG, the middle-square method is a PRNG, Duel_EC_DRBG is a PRNG that was a CSPRNG.

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

I simply categorise them mathematically, based on entropy flow. So you can have three types. The categorisation relies on two kinds of entropy, output or deterministic and input or non deterministic. Some of this explanation will still be contentious as there are various definitions of entropy between the information science and cryptography disciplines.

Entropy in << Entropy out

This is the typical pseudo random number generator. A seed formed from true entropy initialises the generator, which then streams (almost) infinite amounts of deterministic and therefore repeatable entropy. This might be a linear congruential generator like Java's Random(), an AES + counter based generator or an RC4 + SHA1 monster like Windows' CryptGenRandom. Clearly a linear congruential generator is easily reversed and therefore insecure. So you might call it simple a PRNG. If secure and irreversible, then it's a CSPRNG. With the same seed /input entropy, the output is entirely deterministic and therefore repeatable.

Entropy in < Entropy out

This is a grey area where creations like /dev/random and some of the hyper fast beam splitters live. They're all hardware based. Raw hardware collected entropy is not clearly measured in these devices. In the case of /dev/random it's formed around non deterministic input entropy measured in jiffies. Not really SI units of measure. Similarly some beam splitters use AES based randomness extraction without a clear separation of entropy collected from the optical process, and the entropy arising from instrumentation noise which might be 25% of the signal. Being hardware based, raw entropy is biased and in these cases inadequately assessed so secure cryptographic functions are used to whiten the output. Hence these devices are somewhere between a CSPRNG and a TRNG. Their output is non deterministic, but greater than it should be for the amount of entropy flowing into the system.

Entropy in > Entropy out

This is the most secure type of generator. And also the slowest. They output a smaller amount of entropy than collected making them impossible to invert. For this reason alone, there is no concept of a cryptographic ally secure random number generator. They are naturally secure. This also means that cryptographic extraction functions needn't be used. Any TRNG using a block function like AES is automatically in danger of falling into the previous category due to block size issues. Simple matrix multiplication /compression extractors can be used on these generators with total security. You can if you so wish use hashes of all sorts, either cryptographic or not but only for the purposes of entropy compression. Their output is entirely non deterministic and never repeats.

To specifically answer bullet point one, yes you can call it pseudo. This is the point I was making for the second category (Entropy in < Entropy out). You an also call it a TRNG and people do, specifically devices like the Intel random number generator. It produces (allegedly) non deterministic output, yet there is much more output than expected from just a weird and under detailed phase oscillator. It is possible to stretch the raw entropy just like a key stretching function does. So this category is a bit of TRNG and CSPRNG mixed together. Hence the confusion.

| improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ What is this cryptographic definition of entropy? $\endgroup$ – Elias Jun 30 '17 at 7:08
  • 1
    $\begingroup$ Don't be mad, I'm didn't downvote you. I just want to know which definition you are using. With Shannon's definition a deterministic function like a PRNG cannot increase entropy so it has to involve some sort of computational argument. $\endgroup$ – Elias Jun 30 '17 at 11:11
  • $\begingroup$ @Elias There's a recurring theme in that no one in cryptography seems to have a name for the thing that's made when you compress data. Information , entropy ??? Shannon's formula is used to calculate it, information /linguistics researchers call it entropy yet cryptographers don't. But this is critical in categorising the types of RNG. And this can't be asked as there are already a 100 questions like what is entropy? None of them resolve it satisfactorily. $\endgroup$ – Paul Uszak Jun 30 '17 at 11:42
  • $\begingroup$ Complexity, perhaps? $\endgroup$ – forest Nov 4 '18 at 8:23
  • $\begingroup$ @forest Naw, that's not it. The best I've come up with is known entropy and unknown entropy. I think that covers both regular and cryptographic definitions. $\endgroup$ – Paul Uszak Nov 4 '18 at 13:25

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.