FIPS-Certified PRNGs, Part 1
What I really want to talk about is an issue with getting FIPS certification with the new NIST 800-90 DRBG. However, before I get to that, I want to make sure anyone reading these posts know some background.
- What is FIPS certification? If you don't know, it's simply a US Federal government program run by NIST (National Institute of Standards and Technology) that checks to make sure crypto products meet a minimum standard of quality. Any US government agency that wants to purchase a crypto product must purchase a FIPS-certified one, or else prove to some authorizing agency why they the uncertified product they want to buy is necessary. (FIPS = Federal Information Processing Standards.)
The original FIPS certification was all about hardware security modules. Later on, it was expanded to software. There are a number of tests a vendor has to pass in order to get certification. For example, a product has to get the correct answer when performing AES or DSA or SHA-256 or whatever algorithms are offered. However, not all crypto algorithms are FIPS-certifiable. That is, you might have an implementation of RC2 in your product, but you can't get that FIPS certified.
- What is a PRNG? The letters stand for Pseudo-Random Number Generator. Over the years, this has become a very common term and abbreviation. A PRNG is an algorithm that produces random bytes. Except the bytes are not truly random because it is possible to reproduce the output. The algorithm works by converting input "seed" material into output bytes that pass statistical tests of randomness. A PRNG will always produce the same output for a given seed. Change the seed and you get different output.
In order to get FIPS certification, a product has to use an approved PRNG algorithm. There was an algorithm described in the FIPS PUB 186-2 that was certifiable. As part of FIPS certification for this algorithm, the testers would verify that the implementation produced the right answers, just as with an encryption algorithm. The testers would supply a seed, the implementation would generate random bytes. The tester would compare the bytes generated with the expected output. If it matched, the product passed.
The internals of a PRNG have two main components: what it does with seed material and how it produces the actual random bytes. If someone invents a PRNG, they specify the operations on the seed material and the operations to perform when actual random bytes are requested.
Most PRNGs use a message digest (cryptographic hash) or block cipher algorithm to convert seed into random bytes. Furthermore, there are specific steps in a specific order to take when performing the operations. You might think, "What's the big deal? Just digest the seed and there's your output." Except a PRNG might need to generate more than one block of data. That is, suppose you use SHA-512 to digest the seed, you get 64 bytes of output. But suppose you need 256 bytes or more? What then? "Just digest the previous output to get the next output?" No, because then anyone looking at some output will know what the next output will be ("I see that with me, the SSL server used an RC4 key of 0x38 C2…, so I know with the next connection, they will use 0x7A 05…").
For that reason, and many more, building a PRNG is not trivial. And once a PRNG exists, and the crypto community studies it and finds it to be good, anyone implementing it should make sure they've implemented it correctly. "Yeah, I've implemented a PRNG algorithm pretty much as defined, but if it's not exact, so what?" Did you introduce a security flaw? Maybe not, but without study, how do you know for sure? The best thing to do is to implement an algorithm exactly as specified so you know you have not introduced flaws. And how do you know you've implemented it correctly? The best test is to make sure you produce expected output given a particular seed.
Back to the 186-2 algorithm. Over the years, several people found some issues with the this PRNG (I'm proud to say I was one of those people: I showed an example of two seeds producing the same output, and that to solve that problem an app should digest all seed material). Hence, NIST decided to develop a new algorithm
NIST recenly came out with that new algorithm and published it in NIST Special Publication 800-90. In that doc, they call the algorithm a "Deterministic Random Bit Generator" or DRBG. In fact, NIST now uses that term for the entire class of algorithms that produce random bytes from a seed.
I'd just like to say that I don't like this new term DRBG. The industry has been using the term PRNG for many years, why come up with a new one? And besides, isn't "Deterministic Random" an oxymoron?
Nonetheless, there's a new algorithm to get FIPS certified. In fact, NIST has said that in the future, the old 186-2 algorithm will no longer be certifiable. In the future, a product up for certification will have to implement 800-90.
Part 2 will talk about this new algorithm and FIPS certification.