Using Poor Random Numbers

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.

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

The Problem: rand

I once 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 derived from rand easy to guess. The code that defines rand looks like the following, from the Rand.c file in the Microsoft Visual C++ 7 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 in 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 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 on my computer. ' 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 on my computer. #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 on my computer. 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 on my computer. 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. (Note that the numbers output by each code snippet might change with different versions of operating system or the run-time environment, but they will always remain the same values so long as the underlying environment does not change.)

IMPORTANT
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! The story originally broke on BugTraq and can be read at http://online.securityfocus.com/archive/1/3791.

Here's another example. Interestingly, and perhaps ironically, there was a bug in the way the original CodeRed worm generated random computer IP addresses to attack. Because they were predictable, every computer infected by this worm attacked the same list of random IP addresses. Because of this, the worm ended up reinfecting the same systems multiple times! You can read more about this at http://www.avp.ch/avpve/worms/iis/bady.stm.

Another great example of a random number exploit was against ASF Software's Texas Hold 'Em Poker application. Reliable Software Technologies now Cigital, http://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 http://www.cigital.com/news/gambling.html.

Cryptographically Random Numbers in Win32

The simple remedy for secure systems is to not call rand and to call instead a more robust source of random 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, Windows XP, and Windows .NET Server 2003.

At a high level, the process for deriving random numbers by using CryptGenRandom is outlined in Figure 8-1.

Figure 8-1. High-level view of the process for creating random numbers in Windows 2000 and later. The dotted lines show the flow of optional entropy provided by the calling code.

NOTE
For those who really want to know, random numbers are generated as specified in FIPS 186-2 appendix 3.1 with SHA-1 as the G function.

CryptGenRandom gets its randomness, also known as system entropy, from many sources in Windows 2000 and later, 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).

• An 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 http://developer.intel.com/software/idap/resources/technical_collateral/pentiumii/RDTSCPM1.HTM).

• Low-level system information: Idle Process Time, Io Read Transfer Count, I/O Write Transfer Count, I/O Other Transfer Count, I/O Read Operation Count, I/O Write Operation Count, I/O Other Operation Count, Available Pages, Committed Pages, Commit Limit, Peak Commitment, Page Fault Count, Copy On Write Count, Transition Count, Cache Transition Count, Demand Zero Count, Page Read Count, Page Read I/O Count, Cache Read Count, Cache I/O Count, Dirty Pages Write Count, Dirty Write I/O Count, Mapped Pages Write Count, Mapped Write I/O Count, Paged Pool Pages, Non Paged Pool Pages, Paged Pool Allocated space, Paged Pool Free space, Non Paged Pool Allocated space, Non Paged Pool Free space, Free System page table entry, Resident System Code Page, Total System Driver Pages, Total System Code Pages, Non Paged Pool Lookaside Hits, Paged Pool Lookaside Hits, Available Paged Pool Pages, Resident System Cache Page, Resident Paged Pool Page, Resident System Driver Page, Cache manager Fast Read with No Wait, Cache manager Fast Read with Wait, Cache manager Fast Read Resource Missed, Cache manager Fast Read Not Possible, Cache manager Fast Memory Descriptor List Read with No Wait, Cache manager Fast Memory Descriptor List Read with Wait, Cache manager Fast Memory Descriptor List Read Resource Missed, Cache manager Fast Memory Descriptor List Read Not Possible, Cache manager Map Data with No Wait, Cache manager Map Data with Wait, Cache manager Map Data with No Wait Miss, Cache manager Map Data Wait Miss, Cache manager Pin-Mapped Data Count, Cache manager Pin-Read with No Wait, Cache manager Pin Read with Wait, Cache manager Pin-Read with No Wait Miss, Cache manager Pin-Read Wait Miss, Cache manager Copy-Read with No Wait, Cache manager Copy-Read with Wait, Cache manager Copy-Read with No Wait Miss, Cache manager Copy-Read with Wait Miss, Cache manager Memory Descriptor List Read with No Wait, Cache manager Memory Descriptor List Read with Wait, Cache manager Memory Descriptor List Read with No Wait Miss, Cache manager Memory Descriptor List Read with Wait Miss, Cache manager Read Ahead IOs, Cache manager Lazy-Write IOs, Cache manager Lazy-Write Pages, Cache manager Data Flushes, Cache manager Data Pages, Context Switches, First Level Translation buffer Fills, Second Level Translation buffer Fills, and System Calls.

• System exception information consisting of Alignment Fix up Count, Exception Dispatch Count, Floating Emulation Count, and Byte Word Emulation Count.

• System lookaside information consisting of Current Depth, Maximum Depth, Total Allocates, Allocate Misses, Total Frees, Free Misses, Type, Tag, and Size.

• System interrupt information consisting of context switches, deferred procedure call count, deferred procedure call rate, time increment, deferred procedure call bypass count, and asynchronous procedure call bypass count.

• System process information consisting of Next Entry Offset, Number Of Threads, Create Time, User Time, Kernel Time, Image Name, Base Priority, Unique Process ID, Inherited from Unique Process ID, Handle Count, Session ID, Page Directory Base, Peak Virtual Size, Virtual Size, Page Fault Count, Peak Working Set Size, Working Set Size, Quota Peak Paged Pool Usage, Quota Paged Pool Usage, Quota Peak Non Paged Pool Usage, Quota Non Paged Pool Usage, Page file Usage, Peak Page file Usage, Private Page Count, Read Operation Count, Write Operation Count, Other Operation Count, Read Transfer Count, Write Transfer Count, and Other Transfer Count.

The resulting byte stream is hashed with SHA-1 to produce a 20-byte seed value that is used to generate random numbers according to FIPS 186-2 appendix 3.1. Note that the developer can provide extra entropy by providing a buffer of data. Refer to the CryptGenRandom documentation in the Platform SDK for more information about the user-provided buffer. 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 efficient because the calls to CryptAcquireContext (time-intensive) 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); if (m_hProv == NULL) throw GetLastError(); } 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() { try { 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; } } catch (...) { //exception handling } }

You can find this example code with the book's sample files in the folder Secureco2\Chapter08. When you call CryptGenRandom, you'll have a very hard time determining what the next random number is, which is the whole point!

TIP
For performance reasons, you should call CryptAcquireContext infrequently and pass the handle around your application; it is safe to pass and use the handle on different threads.

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 Windows 2000 and later 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 http://www.microsoft.com/technet/security/FIPSFaq.asp.

Cryptographically Random Numbers in Managed Code

If you must create cryptographically secure random numbers in managed code, you should not use code like the code below, which uses a linear congruence function, just like the C run-time rand function:

//Generate a new encryption key. byte[] key = new byte[32]; new Random().NextBytes(key);

Rather, you should use code like the following sample code in C#, which fills a 32-byte buffer with cryptographically strong random data:

using System.Security.Cryptography; try { byte[] b = new byte[32]; new RNGCryptoServiceProvider().GetBytes(b); //display results for (int i = 0; i < b.Length; i++) Console.Write("{0} ", b[i].ToString("x")); } catch(CryptographicException e) { Console.WriteLine(e.Message); }

The RNGCryptoServiceProvider class calls into CryptoAPI and CryptGenRandom to generate its random data. The same code in Microsoft Visual Basic .NET looks like this:

Imports System.Security.Cryptography Dim b(32) As Byte Dim i As Short Try Dim r As New RNGCryptoServiceProvider() r.GetBytes(b) For i = 0 To b.Length - 1 Console.Write("{0}", b(i).ToString("x")) Next Catch e As CryptographicException Console.WriteLine(e.Message) End Try

Cryptographically Random Numbers in Web Pages

If your application is written using ASP.NET, you can simply call the managed classes outlined in the previous section to generate quality random numbers. If you are using a COM-aware Web server technology, you could call into the CAPICOM v2 Utilitiesobject, which supports a GetRandom method to generate random numbers. The code below shows how to do this from an ASP page written in Visual Basic Scripting Edition (VBScript):

<% set oCC = CreateObject("CAPICOM.Utilities.1") strRand = oCC.GetRandom(32,-1) ' Now use strRand ' strRand contains 32 bytes of Base64 encoded random data %>

Note the GetRandom method is new to CAPICOM version 2; it was not present in CAPICOM version 1. You can download the latest CAPICOM from http://www.microsoft.com/downloads/details.aspx?FamilyID=860ee43a-a843-462f-abb5-ff88ea5896f6&DisplayLang=en.