\( \)

Things to do in Portland when you're sick: Benchmarking Cryptographically Secure RNGs

Posted 13 May 2013 by Thomas M. DuBuisson

Random number generation isn't something that non-computer scientists or cryptographers think about very much. The fact is, it's a critical task for almost any secure system - keys, nonces, and passwords all need some entropy and that has to come from somehwere.

It is actually hard to design generators that give random or seemingly random values. It's harder to do so in a cryptographically secure manner - meaning that there is no practical way to predict part of the output even when given all previous or future values. It's even harder to design a generator that has high performance. If you find the task easy then you can probably make a good living writing research papers on the topic.

To complicate matters further, the dimensions for comparison are more than security and performance:

Fortunately, the world is large and, even in a language that fancies itself a niche, there are options. There are at least four packages on Hackage that are worth trying and the generators available in these packages fit into three catagories:

Intel-AES

Based on Intel's AES-NI example code, this package is a fast AES in counter mode. There is no backtracking resistance. It also doesn't currently build due to recent changes to crypto-api, but feel free to try my fixed up git repository.

CPRNG-AES

This is also an AES without backtracking resistance. Oddly, this is not AES in counter mode, it XORs a counter with the previously returned random bytes to obtain the IV - the reason for this design choice is unknown. CPRNG-AES is more popular than intel-aes, probably due to its cleaner build system.

Deterministic Random Bit Generator (DRBG)

DRBG is a collection of generators and modifiers. These generators are all naive English-to-Haskell translations of NIST SP 800-90. Included are Hash-based, HMAC-based, and a counter based generators. These generators are all backtracking resistant and allow additional input to be provided for prediction resistance. Modifiers take as input one or more generators and produce a new generator; the modifiers include automatically reseeding one generator with another, buffering generators, and XORing the output of two generators. The modifiers are all custom solutions, but the underlying generators successfully complete the NIST Known Answer Tests.

Crypto-API and Entropy

Crypto-api provides access to a "system generator" which actually uses either a system source like /dev/urandom or Intel's RDRAND instruction. Lumping this generator in with the above is questionable at best - the above generators are pseudo-random and result in the same output when given the same seed. The SystemRandom generator is IO-based and anything it generates is not reproducable - it's more like reading lazily from an infinitely long file.

Benchmarks

Since all of these generators can be incorporated into a project with near-identical ease, and most users aren't concerned with adherence to standards or other quasi-security arguments, the main difference remaining is performance. I've benchmarked six generators over a range of data-request sizes. The results will hopefully educate potential users about their choices as well as motivate continued development.

I'll present the mean values in the graph. This is slightly misleading as some generators, such as the buffered generators, have very odd densities, so take your grain of salt.

(all benchmarks are on an 3.1GhZ laptop with AES-NI and RDRAND)

Looking these numbers I have the following observations:

I re-ran the benchmarks, stepping the buffering generators one byte first. This means they get the advantage of precomputing an arbitrary number of bytes up front and just taking bytes off a bytestring to serve requests. The purpuse here is just to confirm we are talking about mere nanoseconds unless the generators need to compute more random data for the buffer.

Conclusion

I have high respect for all of these packages. They've all shown reasonable performance and include simple APIs (via the RandomAPI and CryptoRandomGen classes). Unless you need top-notch performance (in which case, use SystemRandom or Intel-AES), you'll probably be well served by selecting a package based on features, portability, and preferred API.