Unit testing a library RNG and its seeding for practical security Suppose I have a cryptography library that provides me with a black-box random number generator that is supposed to be suitable for long-lived key generation.  (Under the hood it may be assumed to use some combination of /dev/random or equivalent, and stretching with a CSPRNG.)

I would like to write a unit test that can detect implementation errors that would result in practical failures of security.  For instance, it should reliably detect the infamous CVE-2008-0166 (Debian OpenSSL weak key generation) if applied to a version of OpenSSL with that bug.  Note that statistical tests as discussed e.g. in this earlier question will not do the job by themselves, because of the CSPRNG in between me and the guts of the black box (the CSPRNG itself has already been checked by use of test vectors).

How might this be accomplished?
You're not going to like this answer, but strictly speaking, you can't.

In a number of specific cases you can do what you want. For example, in the specific case of the Debian PRNG debacle, you could detect that (and as a matter of fact, bad keys generated by this PRNG failure were tracked down). But that's because the RNG was not seeded much at all and ended up with some small number of possible states. (I'm saying RNG not CSPRNG because I'm not considering any cryptographically insecure pseudo-random number generators.) 

But if the output stage of your PRNG comes from a suitable pseudo-random function, it will pass all your tests. AES in counter mode, an iterated hash function, and so on will all be just fine -- these outputs are themselves pseudo-random functions and therefore pass all your pseudo-random tests. It will be cryptographically secure from a mathematical reference point. If it is insecure, it will be insecure because of an operational failure, like the Debian problem, which was operational, not mathematical.

You are only going to find practical failures of a PRNG by white-box testing. You will have to have a reasonably smart crypto person to code-review it. You will have to look inside it to see if it is constructed correctly. 

Consider this as a badly-built PRNG: imagine a chip with a PRNG that is seeded with a completely random 64-bit number to which is added the chip's serial number, and then a high-quality output stage (Yarrow, SP 800-90 DRBG, etc.) generates random bits from that seed from then on. 

In other words, for the entire family of chips, there's a single 64-bit chunk of entropy E, and each chip has put into it E+1, E+2, ... E+N for the N chips we manufacture. Call this number E_n.

We'll presume that all re-seeding is broken and has no effect. You very likely won't be able to tell this from testing the output only. 

You might in some cases -- for example, let's suppose that the output is a naïve iterated hash. You might be able to detect that the substring R[i..i+31] is equal to SHA256(R[i-32..i-1]). But be lucky to detect that, because you'd have to explicitly check for it. 

Similarly, testing its output can tell you if the output function isn't a PRF, but not a lot more than that, and these days the errors aren't going to be because of the output function. Even dummies are going to get that right; look at the Debian debacle again. The problem was seeding, not pseudo-randomness.

You wouldn't find it if the bogus chip hashed in E_n along with each iterated hash, or if there was an HMAC. You wouldn't find it if there was a simple counter hashed in, either. You almost certainly wouldn't detect anything amiss if the PRNG used a cipher in counter mode with E_n as the key, either. (There are plenty of edge cases where you would -- for example, if you used DES in counter mode and happened to pick a weak key, you might detect that. Bear with me for the general case here.)

This completely bogus random number chip has only 64 bits of good randomness in the entire chip production, and yet no black box testing is going to detect that. You're only going to find the problem by auditing its design and implementation, not by testing its output.

I told you you weren't going to like my answer, but there it is. Black box testing will only detect a small class of stupid errors, and none of the evil ones.

Jon