FIPS-Certified PRNGs, Part 2
In a previous post, I introduced FIPS certification and PRNGs. I pointed out that there's a new algorithm (800-90, now called DRBG for Deterministic Random Bit Generator) to be certified. In this post I'm going to talk about that algorithm and how to get it FIPS certified.
One of the twists in the 800-90 standard, is that it requires the implementation to come up with seed material. That is, most old PRNGs worked the same way:
- return to the user
- the user enters seed
- the PRNG can now generate random numbers based on the seed
800-90 works this way:
- collect seed material
- return to the user.
- the user can now enter more seed material or
- just call on the DRBG to generate random bytes.
Here at Voltage, we use the term autoseed. That means the PRNG/DRBG seeds itself.
So NIST is requiring that products up for FIPS certification must supply a DRBG that autoseeds. But that brings up the question, how can one test an implementation? With 186-2, it was possible to come up with seed/expected output pairs. But with 800-90, there's autoseeding. We can't guarantee what any seed will be in advance. Furthermore, if we enter a seed, we won't get the expected output because the autoseed will be different every time we run the test.
The answer is to require the implementation to turn off autoseeding in order to run the test. Then, the test supplies some data that is a substitute for the autoseed material, and possibly some more material that is a aubstitute for user-supplied seed. The implementation then generates random bytes and it is compared to an expected value.
This makes sense on one level. In order to test an implementation (make sure they follow the standard), make sure it produces expected output from a specific seed.
However, this also means introduing a security hole.
In order to get FIPS certification, an implementation must turn off autoseeding. But if a user somehow accidentally uses the PRNG/DRBG in FIPS testing mode, and they don't add their own seed, they'll get bad random output. After all, they're using a PRNG/DRBG that seeds itself, so why enter any new seed?
You might declare, "Then don't release the FIPS testing mode version of the PRNG/DRBG." However, one FIPS requirement is that the code tested is the code released. Furthermore, in order to get FIPS certification, it is necessary to perform these "Known Answer Tests" (KATs) at startup. When the user first launches the product, it must run some KATs to show that it is running properly.
It all means that in order to get FIPS certification, we must release the product with FIPS testing mode in there.
We've written our code in such a way that the FIPS testing mode is not publicly available. There are also some hoops to go through to get to that code. So the probability is extremely low – virtually zero – that a user will accidentally instantiate in FIPS testing mode. With some research, a user could figure out how to explicitly (as opposed to accidentally) instantiate in that mode, but why would they? So I'm not too worried.
Nonetheless, I don't like this requirement from NIST. I think that NIST should either not require the KAT, or allow an implementation to take out the FIPS testing mode before releasing.
By the way, I can think of one reason someone might make the effor to instantiate in FIPS testing mode, and that is to intentially create a security hole. Someone writing an app that they want to break themselves would appreciate this implementation. Of course, someone wanting to do this would have many, many more ways of inserting back doors. So taking away this code would not thwart them. But no one wants to add anything to help the attackers.