Conversations about cryptography are common place in the cyber-security world. One can find security professionals discussing everything from PKI to issues with RSA. But while we are discussing issues with algorithms, implementation of cryptographic protocols, authentication algorithms, and other such topics, we often lose sight of a fundamental part of the entire process – key generation.
Whether your preferred symmetric cypher is the U.S. Government endorsed AES, the open source BlowFish from Bruce Schneier, or the Russian GOST cipher, they all have one thing in common: they need a key. Certainly, security professionals are aware that these algorithms utilize an encryption key, but there is often too little discussion of how that key gets generated.
Ideally, the output of any encryption algorithm, will appear very nearly to be random. This also requires that the key utilized in that algorithm also be nearly random. This brings us to pseudo random number generators. They are called ‘pseudo’ because the output is not truly completely random.
Pseudo-random number generators (PRNGs) are algorithms that can create long runs of numbers with good random properties but eventually the sequence repeats. Thus, the term ‘pseudo’ random number generators.
The algorithms essentially generate numbers that, while not being truly random, are random enough for cryptographic applications. In addition to being used for generating symmetric cipher keys, PRNG’s are also used to generate Initialization Vectors for use with stream ciphers.
So the question becomes, is the PRNG you are using to generate your keys and your initialization vectors, random enough? There are some well-established PRNG algorithms such as Yarrow; Blum, Shub; and some of the Lagged Fibonacci Generators. But it is not sufficient to memorize a few algorithms that are currently considered good choices. A security professional should know what makes a good PRNG. There are four properties any good PRNG should have:
The German Federal Office for Information Security (BSI) has established four criteria for quality of random number generators:
To be suitable for cryptography any PRNG should meet K3 and K4 standards. That means that any given sequence from the output of a PRNG cannot be used to predict any future, or even any previous outputs from that PRNG. Furthermore, that even if one has access to the internal state of a PRNG, for example by examining the code at a particular stop point in the execution, that the data of the current state of the PRNG also cannot be used to product any previous or subsequent numbers in the sequence.
The United States NIST has a document describing in detail how a PRNG should be tested to ensure that it is suitable for cryptographic purposes. This 131 page document is fortunately, not a difficult read. It outlines very specific tests that can be conducted on the output of any PRNG to see if that output is ‘random enough’ for cryptographic purposes.
The good news is not that you need to become a mathematician capable of creating your own PRNG algorithm. However, when selecting cryptographic software, modules, and hardware, you need to be able to ask intelligent questions of the vendor, so that you can determine if they are using a good PRNG. A poorly chosen PRNG will weaken the security of the rest of your cryptographic solutions.
Modern Cryptography: Applied Mathematics for Encryption and Information Security (2015), by Chuck Easttom
Yarrow-160: Notes on the design and analysis of the yarrow cryptographic pseudorandom number generator (1999, August), by j. Kelsey, B. Schneier, & n. Ferguson. In International Workshop on Selected Areas in Cryptography (pp. 13-33). Springer Berlin Heidelberg.
A review of pseudorandom number generators(1990), by F. James. In Computer Physics Communications, 60(3), 329-344.
A Statistical Test Suite for Random And Pseudorandom Number Generators For Cryptographic Applications (2001) by National Institute of Standards and Technology NIST (2001)
Random number generators: good ones are hard to find (1988) by S.K. Park, & K.W. Miller. In Communications of the ACM, 31(10), 1192-1201
Thoughts on pseudorandom number generators (1990), by B.D. Ripley. In .Journal of Computational and Applied Mathematics, 31(1), 153-163.
A Simple Unpredictable Pseudo-Random Number Generator (1986), by L. Blum, M. Blum, M. Shub. In Society for Industrial and Applied Mathematics, 15(2).
Concrete Security of the Blum-Blum-Shub Pseudorandom Generator (2005), A. Sidorenko, B. Schoenmakers . Cryptography and Coding, 3796
A selection of books by Chuck Easttom
Photo Binary Code courtesy of Christiaan Colen (CC BY-SA 2.0)