How to Choose the Right Cryptographic Key Generation Algorithm

Conversations about cryptography are common 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 random. This also requires that the key utilized in that algorithm 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, PRNGs 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:

• Uncorrelated Sequences – No sequence of any given link should be correlated to any other sequence of the algorithms output. One cannot take a given stretch of numbers (say 16 bits) and use that to predict subsequent bits. 
• Long Period – Ideally the series of digits (usually bits) should never have any repeating pattern.  However, the reality is that there will eventually be some repetition. The distance (in digits or bits) between repetition’s is the algorithm output period. The longer the period the better the more effective the PRNG (James, 1990; Ripley, 1990).
• Uniformity – In cryptographic applications, the output of a PRNG will most likely be represented in binary format. There should be an equal number of 1’s and 0’s (Ripley, 1990), though not distributed in any discernable pattern.  The sequence of random numbers should be uniform, and unbiased. If you have significantly more (or significantly less) 1’s than 0’s then the output is biased (Soto, 2012).
• Computational Indistinguishability – Any subsection of numbers taken from the output of a given PRNG should not be distinguishable from any other subset of numbers in polynomial time by any efficient procedure. The two sequences are indistinguishable. That does not, however mean they are identical. It means there is no efficient way to determine specific differences.

The German Federal Office for Information Security (BSI) has established four criteria for quality of random number generators:

• K1  A sequence of random numbers with a low probability of containing identical consecutive elements.
• K2  A sequence of numbers which is indistinguishable from 'true random' numbers according to specified statistical tests.
• K3  It should be impossible for any attacker to calculate, or otherwise guess, from any given sub-sequence, any previous or future values in the sequence.
• K4  It should be impossible for an attacker to calculate, or guess from an inner state of the generator, any previous numbers in the sequence or any previous inner generator states.

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 previous outputs from that PRNG. Furthermore, 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, the data of the current state of the PRNG also cannot be used to produce any previous or subsequent numbers in the sequence.

The United States National Institute of Standards and Technology (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 difficult to 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 that you do not 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.

References and Further Reading

• Selected articles on Key Management (2012-16), by Ashiq JA, Chuck Easttom, Dawn M. Turner, Guillaume Forget, James H. Reinholm, Matt Landrock, Peter Landrock, Steve Marshall, Torben Pedersen and more  
• Lagged Fibonacci Random Number Generators for Distributed Memory (1997), by S. Aluru. In Journal of Parallel And Distributed Computing 45, 1–12, New York City, NY, McGraw-Hill Publishing

• 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)