Using Poor Random Numbers | Writing Secure Code, Second Edition

Using Poor Random Numbers

Oftentimes your application needs random data to use for security purposes, such as for passwords, encryption keys, or a random authentication challenge (also referred to as a nonce). Choosing an appropriate random-number generation scheme is paramount in secure applications. In this section, we ll look at a simple way to generate random, unpredictable data.


	A key is a secret value that one needs to read, modify, or verify secured data. An encryption key is a key used with an encryption algorithm to encrypt and decrypt data.

The Problem: rand

Recently I reviewed some C++ source code that called the C run-time rand function to create a random password. The problem with rand, as implemented in most C run-time libraries, is its predictability. Because rand is a simple function that uses the last generated number as the seed to create the next number, it can make a password easy to guess. The code that defines rand looks like the following, from the Rand.c file in the Microsoft Visual C++ 6 C Run-time (CRT) source code. I ve removed the multithreaded code for brevity.

int __cdecl rand (void) { return(((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff); }

Here s a version documented on page 46 of Brian Kernighan and Dennis Ritchie s classic tome The C Programming Language, Second Edition (Prentice Hall PTR, 1988):

unsigned long int next = 1; int rand(void) { next = next * 1103515245 + 12345; return (unsigned int)(next/65536) % 32768; }

This type of function is common and is referred to as a linear congruential function.

A good cryptographic random number generator has three properties: it generates evenly distributed numbers, the values are unpredictable, and it has a long and complete cycle (that is, it can generate a large number of different values and all of the values in the cycle can be generated). Linear congruential functions meet the first property but fail the second property miserably! In other words, rand produces an even distribution of numbers, but each next number is highly predictable! Such functions cannot be used in secure environments. Some of the best coverage of linear congruence is in Donald Knuth s The Art of Computer Programming, Volume 2: Seminumerical Algorithms (Addison-Wesley, 1998). Take a look at the following examples of rand-like functions:

' A VBScript example ' Always prints 73 22 29 92 19 89 43 29 99 95. ' Note: The numbers may vary depending on the VBScript version.  Randomize 4269 For i = 0 to 9     r = Int(100 * Rnd) + 1     WScript.echo(r) Next // A C/C++ Example // Always prints 52 4 26 66 26 62 2 76 67 66. #include <stdlib.h> void main() {     srand(12366);     for (int i = 0; i < 10; i++) {         int i = rand() % 100;         printf("%d ", i);     } } # A Perl 5 Example # Always prints 86 39 24 33 80 85 92 64 27 82. srand 650903; for (1 .. 10) {     $r = int rand 100;     printf "$r "; } // A C# example // Always prints 39 89 31 94 33 94 80 52 64 31. using System; class RandTest {     static void Main() {         Random rnd = new Random(1234);         for (int i = 0; i < 10; i++) {             Console.WriteLine(rnd.Next(100));         }     } }

As you can see, these functions are not random they are highly predictable.


	Don t use linear congruential functions, such as the CRT rand function, in security-sensitive applications. Such functions are predictable, and if an attacker can guess your next random number, she might be able to attack your application.

Probably the most famous attack against predictable random numbers is against an early version of Netscape Navigator. In short, the random numbers used to generate the Secure Sockets Layer (SSL) keys were highly predictable, rendering SSL encryption useless. If an attacker can predict the encryption keys, you may as well not bother encrypting the data! A reasonable story about the incident is at www8.zdnet.com/pcmag/issues/1508/pcmg0074.htm.

Another great example of a random number exploit was against ASF Software s Texas Hold em Poker application. Reliable Software Technologies now Cigital, www.cigital.com discovered the vulnerability in late 1999. This dealer software shuffled cards by using the Borland Delphi random number function, which is simply a linear congruential function, just like the CRT rand function. The exploit required that five cards from the deck be known, and the rest of the deck could then be deduced! You can find more information about the vulnerability at www.cigital.com/news/gambling.html.

A Remedy: CryptGenRandom

The simple remedy for secure systems is to not call rand and to call instead a more robust source of data in Windows, such as CryptGenRandom, which has two of the properties of a good random number generator, unpredictability and even value distribution. This function, declared in Wincrypt.h, is available on just about every Windows platform, including Windows 95 with Internet Explorer 3.02 or later, Windows 98, Windows Me, Windows CE v3, Windows NT 4, Windows 2000, and Windows XP.

CryptGenRandom gets its randomness, also known as entropy, from many sources in Windows 2000, including the following:

The current process ID (GetCurrentProcessID).
The current thread ID (GetCurrentThreadID).
The ticks since boot (GetTickCount).
The current time (GetLocalTime).
Various high-precision performance counters (QueryPerformanceCounter).
A Message Digest 4 (MD4) hash of the user s environment block, which includes username, computer name, and search path. MD4 is a hashing algorithm that creates a 128-bit message digest from input data to verify data integrity.
High-precision internal CPU counters, such as RDTSC, RDMSR, RDPMC (x86 only more information about these counters is at developer.intel.com/software/idap/resources/technical_collateral/pentiumii/RDTSCPM1.HTM).
Low-level system information, such as idle time, kernel time, interrupt times, commit limit, page read count, cache read count, nonpaged pool allocations, alignment fixup count, operating system lookaside information.

Such information is added to a buffer, which is hashed using MD4 and used as the key to modify a buffer, using RC4, provided by the user. (Refer to the CryptGenRandom documentation in the Platform SDK for more information about the user-provided buffer. I ll describe RC4 a bit later in this chapter.) Hence, if the user provides additional data in the buffer, this is used as an element in the witches brew to generate the random data. The result is a cryptographically random number generator.

You can call CryptGenRandom in its simplest form like this:

#include <windows.h> #include <wincrypt.h> HCRYPTPROV hProv = NULL; BOOL fRet = FALSE; BYTE pGoop[16]; DWORD cbGoop = sizeof pGoop; if (CryptAcquireContext(&hProv, NULL, NULL, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT)) if (CryptGenRandom(hProv, cbGoop, &pGoop)) fRet = TRUE; if (hProv) CryptReleaseContext(hProv, 0);

However, the following C++ class, CCryptRandom, is more useful as the calls to CryptAcquireContext and CryptReleaseContext, which create and destroy a reference to a Cryptographic Service Provider (CSP), are encapsulated in the class constructors and destructors. Therefore, as long as you do not destroy the object, you don t need to take the performance hit of calling these two functions repeatedly.

/* CryptRandom.cpp */ #include <windows.h> #include <wincrypt.h> #include <iostream.h> class CCryptRandom { public: CCryptRandom(); virtual ~CCryptRandom(); BOOL get(void *lpGoop, DWORD cbGoop); private: HCRYPTPROV m_hProv; }; CCryptRandom::CCryptRandom() { m_hProv = NULL; CryptAcquireContext(&m_hProv, NULL, NULL, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT); } CCryptRandom::~CCryptRandom() { if (m_hProv) CryptReleaseContext(m_hProv, 0); } BOOL CCryptRandom::get(void *lpGoop, DWORD cbGoop) { if (!m_hProv) return FALSE; return CryptGenRandom(m_hProv, cbGoop, reinterpret_cast<LPBYTE>(lpGoop)); } void main() { CCryptRandom r; // Generate 10 random numbers between 0 and 99. for (int i=0; i<10; i++) { DWORD d; if (r.get(&d, sizeof d)) cout << d % 100 << endl; } }

You can find this example code on the companion CD in the folder Secureco\Chapter 6. When you call CryptGenRandom, you ll have a very hard time determining what the next random number is, which is the whole point!

Also, note that if you plan to sell your software to the United States federal government, you ll need to use FIPS 140-1 approved algorithms. As you might guess, rand is not FIPS-approved. The default versions of CryptGenRandom in Microsoft Windows CE v3, Windows 95, Windows 98, Windows Me, Windows 2000, and Windows XP are FIPS-approved.

What Is FIPS 140-1?

Federal Information Processing Standard (FIPS) 140-1 provides a means to validate vendors cryptographic products. It provides standard implementations of several widely used cryptographic algorithms, and it judges whether a vendor s products implement the algorithms according to the standard. You can find more information about FIPS 140-1 at www. microsoft.com/technet/security/FIPSFaq.asp.