Random Number Generation and Key Derivation

In all of the examples so far in this chapter, when a secret key was necessary, it has been specified as an input parameter to the method. This is all well and good in the abstract, but somewhere in your program you will need to generate a good sequence of bytes to use as a random key for an encryption or keyed hash algorithm. How one generates good values to use as secret key material is the subject of this section. We now discuss two smaller portions of the cryptographic object hierarchy that are still extremely important to writing crypto-aware applications—random number generators and secret key derivation classes.

Generating Pseudo-Random Numbers

The ability to generate a random number, or a random sequence of bytes, is core to almost every cryptographic protocol. If Alice and Bob want to share a secret key so that they can later exchange encrypted information, they need to generate a random sequence of bytes to use as the secret key. An adversary that is able to predict the sequence of bytes Alice and Bob generate with high accuracy would later be able to eavesdrop on their encryption conversation. Obviously, we want our sources of random numbers to generate values that defy prediction by an adversary.

The random number generators included in the .NET Framework are properly classified as pseudo-random number generators (PRNGs). We say that a function is a pseudo-random number generator if it is computationally unfeasible to predict the next number the function will output given all the previous numbers that have been output. More precisely, if a function f(x) outputs a sequence of bits x₀, x₁, x₂, and so on, we say that f(x) is a pseudo-random bit generator if the probability of correctly determining x_n given x₀, x₁, and so on, x_n-1 is within an infinitesimally small amount of ?. That is, a computationally feasible process can do no better than random guessing to predict the next output bit of the function f.

The .NET Framework PRNGs work by collecting seed information from various portions of the operating system and then using this seed information to generate a cryptographically strong sequence of random numbers that cannot be predicted with better-than-guessing accuracy. Generating truly random numbers is quite difficult; the best sources of random bits are special-purpose devices that use physical systems to produce randomness. Some computer processors now include on-chip circuitry for generating random bits, and the PRNG provided in the .NET Framework will leverage this hardware when it is available to the operating system.

In the .NET Framework cryptographic object model, classes implementing random number generators descend from the abstract RandomNumberGenerator class. Every subclass of the RandomNumberGenerator class implements two methods for getting sequences of random bytes from the generator—GetBytes and GetNonZeroBytes. These routines accept an array of bytes as input and fill the array with random bytes or random non-zero bytes, respectively. It will almost always be the case that you will want to use the GetBytes() method to generate your random sequences of bytes; only exclude zero bytes if you have an application-specific reason for needing to eliminate randomly chosen zeros. The following is a code snippet for generating a random 256-bit Rijndael key using the .NET Framework's RandomNumberGenerator class:

// Create a new instance of the default implementation of the
// RandomNumberGenerator abstract class.
RandomNumberGenerator rng = RandomNumberGenerator.Create();
// Create an array that will hold the random values
byte[] rbytes = new byte[32]; // 256 bits/8 bits per byte = 32 bytes
// Fill the array with random bytes
rng.GetBytes(rbytes);

The default implementation class for RandomNumberGenerator is the RNGCryptoServiceProvider class, which is a wrapper on top of the PRNG provided in Windows by CryptoAPI. Unlike other random number generators with which you may be familiar, such as the rand() or random() functions in the C language library or even the System.Random class in the .NET Framework, the CryptoAPI PRNG does not produce reproducible sequences. That is, it is not possible to generate multiple instances of RNGCryptoServiceProvider that will reproducibly return the same sequences of random numbers.

Deriving Keys from User Input

The RandomNumberGenerator class is great for generating pseudo-random numbers to use as cryptographic keys, but long strings of random digits are difficult for users to remember. For many applications, users want to be able to perform cryptographic operations using a password or passphrase as the encryption “key.” In general, passwords make lousy cryptographic keys because to be memorable, passwords are generally not sufficiently random. Also, passwords tend to be composed of characters that are easy to type on a keyboard, so they do not uniformly use all possible values. To bridge the gap between user-friendly passwords and crypto-friendly sequences of bytes, cryptographic algorithms have been developed to derive key material from a password. This section describes one such algorithm that is included in the .NET Framework cryptography classes.

The DeriveBytes abstract class in the cryptographic object hierarchy represents any algorithm that derives bytes suitable for use as key material from another input. The PasswordDeriveBytes class implements one such algorithm that is an extension of the PBKDF1 algorithm defined in the PKCS #5 v2.0 standard and is documented in IETF RFC 2898. This algorithm accepts four values as input—a password, a salt value, an iteration count, and a cryptographic hash algorithm. The algorithm repeatedly applies the hash algorithm to a combination of the password and the salt, ultimately returning a sequence of bytes after running for the specified number of iterations.

The following code snippet shows how to derive an array of 16 bytes from a password string:

String password = "MySecretPassword";
// use no salt (second argument is a zero-length array)
PasswordDeriveBytes pdb = new PasswordDeriveBytes(password, new byte[0]);
byte[] derivedBytes = pdb.GetBytes(16);

In this example, no salt is used for simplicity. Using salt makes attacks against the algorithm harder, but like initialization vectors for symmetric ciphers, you have to know the salt to be able to derive the same sequence of key bytes from a given password. Salt values need not be kept secret. As the next example shows, we can persist salt in an encrypted file just as we do with initialization vectors.

For our last example of stream-based cryptography, we combine symmetric ciphers, random number generation, and a key derivation function to create a robust, password-based file encryption and decryption program. The program shown in Listing 30.12 takes four command-line arguments:

• A string argument, either -e or -d, to indicate whether to encrypt or decrypt

• A password

• The name of the source file to encrypt or decrypt

• The name of the output file in which to store the encrypted or decrypted contents

For each file, a 128-bit random salt value is generated that is combined with the password to create a 256-bit Rijndael encryption key. A 128-bit random initialization vector is also used. The IV and salt values are stored at the beginning of the encrypted file, before the encrypted content, so that they can be recovered and used when decrypting the contents.

Listing 30.12. Password-Based Encryption and Decryption of Files

using System;
using System.IO;
using System.Security.Cryptography;
public class Encrypt {

  public static void EncryptFile(String password, String sourceFile, String destFile) {
    // Derive a 256-bit Rijndael key from the password
    // We first have to generate a random salt value
    RandomNumberGenerator rng = RandomNumberGenerator.Create();
    byte[] salt = new byte[16]; // 16 bytes == 128 bits
    rng.GetBytes(salt);
    // Now compute the Rijndael key
    PasswordDeriveBytes pdb = new PasswordDeriveBytes(password, salt);
    byte[] key = pdb.GetBytes(32); // 32 bytes == 256 bits
    // Create a new Rijndael object, it'll have a random key and IV
    Rijndael aes = Rijndael.Create();
    // set the key to be the derived key
    aes.Key = key;
    // create FileStreams for source and dest
    FileStream inStream = new FileStream(sourceFile, FileMode.Open);
    FileStream outStream = new FileStream(destFile, FileMode.Create);
    // We want to write the salt and IV out to the destFile unencrypted,
    // so in this case we can wrap a CryptoStream around the *sourceFile*
    // and read encrypted bytes from it
    CryptoStream encryptedInStream = new CryptoStream(inStream, aes.CreateEncryptor(),
 CryptoStreamMode.Read);
    // Write the salt out
    outStream.Write(salt, 0, salt.Length);
    // Write the IV out
    outStream.Write(aes.IV, 0, aes.IV.Length);
    // Now we're ready to encrypt. Read the bytes from the CryptoStream
    // in a loop until there aren't any more (end-of-file), writing to
    // the output file as we go. We need a buffer to hold what we're going
    // to read, and bytesRead tells us how many bytes in buffer are
    // valid ciphertext.
    int bytesRead;
    byte[] buffer = new byte[1024]; // read 1K at a time
    do {
      bytesRead = encryptedInStream.Read(buffer,0,1024);
      outStream.Write(buffer, 0, bytesRead);
    }  while (bytesRead > 0);
    // Done!
    inStream.Close();
    outStream.Close();
    return;
  }

  public static void DecryptFile(String password, String sourceFile, String destFile) {
    // Create a new Rijndael object
    Rijndael aes = Rijndael.Create();
    // Create an array to hold the IV read from the file:
    byte[] IV = new byte[aes.IV.Length];
    // Create an array to hold the salt read from the file:
    byte[] salt = new byte[16];
    // create FileStreams for source and dest
    FileStream inStream = new FileStream(sourceFile, FileMode.Open);
    FileStream outStream = new FileStream(destFile, FileMode.Create);
    // We want to read the IV out to the sourceFile unencrypted,
    // so in this case we can wrap a CryptoStream around the *destFile*
    // and write encrypted bytes into it.
    // The output bytes will be decrypted.
    // First, read the salt and IV
    inStream.Read(salt, 0, salt.Length);
    inStream.Read(IV, 0, IV.Length);
    // Compute the Rijndael key
    PasswordDeriveBytes pdb = new PasswordDeriveBytes(password, salt);
    byte[] key = pdb.GetBytes(32); // 32 bytes == 256 bits
    // set the key and IV of the aes object
    aes.Key = key;
    aes.IV = IV;
    // Create the CryptoStream
    CryptoStream decryptedOutStream = new CryptoStream(outStream, aes.CreateDecryptor(),
 CryptoStreamMode.Write);
    // Now we're ready to decrypt.
    int bytesRead;
    byte[] buffer = new byte[1024]; // read 1K at a time
    do {
      bytesRead = inStream.Read(buffer,0,1024);
      decryptedOutStream.Write(buffer, 0, bytesRead);
    }  while (bytesRead > 0);
    // We've read everything, so now call FlushFinalBlock() to write out
    // any remaining bytes
    decryptedOutStream.FlushFinalBlock();
    inStream.Close();
    decryptedOutStream.Close();
    return;
  }

  public static void Main(String[] args) {
    if (args.Length < 4) {
      Console.WriteLine("Usage: [-d | -e] password infile outfile");
      return;
    }
    switch (args[0]){
      case "-e":
        EncryptFile(args[1], args[2], args[3]);
        break;
      case "-d":
        DecryptFile(args[1], args[2], args[3]);
        break;
      default:
        Console.WriteLine("Usage: [-d | -e] password infile outfile");
        break;
      }
      return;
    }
}

The source code for the EncryptFile and DecryptFile routines is very similar to that of the corresponding routines in Listings 30.3 and 30.4, the major difference being the explicit addition of key derivation and the addition of the salt as a second parameter written out to the encrypted file.