I want to test a C implementation of Hash_DRBG—which test_demo.c file I will modify to produce random binaries indefinitely to STDOUT as to be used by piping its output—using DIEHARDER for a research. I want to base my research around this research, however I don't find any mention of how it's seeded. NIST have several recommendation regarding the use of entropy source for PRNGs in this publication, however I am reluctant to test this PRNG with an entropy source such as a physical TRNG, as it also entails implementing a health check for said entropy source, which could somewhat drastically expand the scope of the research. However, NIST has released a document containing the example values for Hash_DRB, which includes entropy input for the initial and subsequent seeding along with other inputs. Should I use these pre-written entropy input to seed and reseed the PRNG for the testing, and what sort of implication could it have for the result? Also, is performing a health check really necessary for the purpose of statistically testing a PRNG using such test suite?
-
$\begingroup$ In addition to KATs you could also make a property test showing your implementation returns the same results as another implementation or even proving the equivalence. $\endgroup$– Thomas M. DuBuissonCommented Nov 1, 2023 at 14:41
2 Answers
In general, it's a good idea to test implementations of cryptographic algorithms. It's very easy to accidentally make a mistake in implementation, and testing using known inputs and test vectors is a good way to convince yourself of a correct implementation. This is especially true because Hash DRBG requires correct bignum arithmetic, and that can be tricky to get right.
In a real-life production scenario, you'd seed your DRBG with an input from the system CSPRNG (e.g., getrandom, getentropy, or /dev/urandom on Unix and CryptGenRandom on Windows). However, if you are merely testing the output using something like DieHarder, then using known, fixed inputs is fine and may aid in the reproducibility of your research. You could use such values as the SHA-256 hashes of increasing integers, for example.
Note, however, that passing a statistical test does not indicate that a PRNG is cryptographically secure. To be a cryptographically secure PRNG, the algorithm must pass the next bit test: that is, given a certain amount of output of the PRNG, it should not be possible to guess the next bit with better than even odds.
The next bit test allows all sorts of inquiry as to how the algorithm functions (and the details of the algorithm are assumed to be public knowledge) including its internal structure and the way it's seeded, not just statistical tests. The good news is that with Hash DRBG, with some assumptions about the underlying hash algorithm (which we believe apply to SHA-2, SHA-3, and BLAKE2), we don't know of any way better than brute force to attack it, so it passes the next bit test. Thus, while you are free to conduct research on Hash DRBG using statistical tests, it is not likely to lead to interesting results.
-
$\begingroup$ Thank you for your answer. However, I'd like to ask, does not passing a statistical test necessarily indicates that a PRNG us not cryptographically secure, or does it simply mean that the PRNG isn't "random enough"; i.e. randomness is not strictly necessary for cryptographical security? $\endgroup$– vnwrywnCommented Nov 2, 2023 at 10:31
-
$\begingroup$ Every output is equally likely from a CSPRNG. Thus, it's equally likely that the all-zeros output will occur as any other output of that length. The former will fail most statistical tests, even though the PRNG may be just fine. We expect that in general, a CSPRNG will fail some statistical tests from time to time, and that doesn't necessarily indicate a security problem. $\endgroup$– bk2204Commented Nov 2, 2023 at 11:32
Hi and welcome to the site.
On the basis that you "want to test a C implementation of Hash_DRBG", I'm assuming that you mean a perfect representation of their algorithm. You have no choice then but to test with NIST's example vectors.
Test vectors are common in the testing of cryptography. How else can you guarantee that a particular primitive has been correctly implemented? It's output might look randomish, yet not at the level the designers intended due to subtle differences, e.g. H = Hash(0x30 || V) instead of H = Hash(0x03 || V).
Randomness is pesky like that.
