Secure pseudo-random numbers

Edit:This password utilities library has now been substantially upgraded and open-sourced with an MIT license. You can find a .NET 4.0 version of the library and an example graphical interface in a Google Code Mercurial repository.

This is the third installment in a series about creating a C# utilities library that covers the following areas:

• Specifying password policies that can match most application requirements.
• Generating cryptographically-secure random passwords that satisfy a specified password policy.
• Measuring the strength (or more precisely, information entropy) of human-generated and machine-generated passwords.
• Using random salts and key stretching to make password hashes more secure than the original passwords.
• Measuring the additional strength added by iterative salted hashes. 
• Timing the password generation and password hashing processes.

To generate random passwords, you obviously need a good source of random numbers. To generate genuinely random numbers, you need access to special hardware or a subscription to a site like random.org. Failing that, you're restricted to using a pseudo-random number generator (PRNG for short). This works just fine for password generation as long as you have a suitable source of information entropy. Enter a .NET Framework class called RNGCryptoServiceProvider, which is a cryptographically-secure pseudo-random number generator (CSPRNG for short).

Unlike normal PRNGs, CSPRNGs are designed to pass rigorous statistical randomness tests. They're also designed to hold up well under serious attack, even when their initial or running state becomes available to an attacker.

The term "pseudo-random", as used by cryptographers, may be misleading to a non-technical reader. A CSPRNG expands a collection of random values, known as a seed, into a longer sequence of numbers. That sequence is reproducible given the seed, but for any good CSPRNG, a minor change in the seed yields a very different sequence. Therefore, as long as at least some portion of the seed is chosen via an adequately random process, an attacker is unable to predict the resulting sequence - even if the attacker can influence the remainder of the seed. Numerous important systems, ranging from military communications to the encryption that protects virtually all online transactions, rely on the functionally-equivalent security between "cryptographically-secure pseudo-random" and "random".

To create its seed, the RNGCryptoServiceProvider class draws its entropy from the same pool as the CryptGenRandom function, a FIPS-validated CSPRNG. These entropy sources include the current process ID, the current thread ID, the current tick count, the current local time, the global memory status, the amount of free disk space, the local computer name, the local user name, the cursor position, and so on.

A naive implementation of rolling a die with up to 255 sides using RNGCryptoServiceProvider might look something like this:

Then we roll a 6-sided die 1.2 million times and look at the results:

Ooops! That doesn't look right at all - the distribution is clearly favouring the lower numbers. This is a problem called modulo bias. There are several ways to overcome this. One of the quickest in terms of run-time involves specifically checking for modulo bias every time, and looks something like this:

Again we roll a 6-sided die 1.2 million times and look at the results:

That looks like a much better distribution. Although you could go overboard and run some serious tests.

Another complaint about using CSPRNGs is that they can be "slow". So let's generate some passwords with this die-rolling class and look at the performance:

Setup does take around 1/50th of a second, as reflected in the time taken to generate the first password. But after that, it's fairly fast - generating something in the region of 20,000 passwords a second. This is a clear example of the principle that slow is irrelevant to your customers, your management, and your stakeholders. Not fast enough is what's really relevant.

You can view and download Die.cs. The complete library, including this class, will be posted at the end of this series. In the next installment, we'll look at the password generator class.