(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").
