Using Passwords to Derive Cryptographic Keys

Cryptographic algorithms encrypt and decrypt data by using keys, and good keys are hard to guess and long. To make cryptographic algorithms usable by human beings, we don't use very good keys we use passwords or pass-phrases that are easy to remember. Let's say you're using an application that employs the Data Encryption Standard (DES) cryptographic algorithm. DES requires a 56-bit key. A good DES key has equal probability of falling anywhere in the range 0 2^56 1 (that is, 0 to 72,057,594,037,927,899). However, passwords usually contain easy-to-remember ASCII values, such as A Z, a z, 0 9, and various punctuation symbols, and these values form a vastly reduced subset of possible values.

An attacker who knows that you're using DES and passwords gathered from your users need not attempt to check every value from 0 2⁵⁶ 1 to guess the key used to encrypt the data. He need only attempt all possible passwords that contain the easy-to-remember ASCII group of values; this is a really easy problem to solve for the attacker!

NOTE
I have to admit to being a Perl nut. In April 2001, on the Fun With Perl mailing list you can sign up at http://www.technofile.org/depts/mlists/fwp.html someone asked for the shortest Perl code that produces a random eight-character password. The following code was one of the shortest examples; it's hardly random, but it is cute!

print map chr 33+rand 93, 0..7

Measuring the Effective Bit Size of a Password

Claude Shannon, a pioneer in information science, produced a research paper in 1948 titled A Mathematical Theory of Communication that addressed the randomness of the English language. Without going into the math involved, I can tell you that the effective bit length of a random password is log2(n^m), where n is the pool size of valid characters and m is the length of the password. The following VBScript code shows how to determine the effective bit size of a password, based on its length and complexity:

Function EntropyBits(iNumValidValues, iPwdSize) If iNumValidValues <= 0 Then EntropyBits = 0 Else EntropyBits = iPwdSize * log(iNumValidValues) / log(2) End If End Function ' Check a password made from A-Z, a-z, 0-9 (62 chars) ' and eight characters in length. WScript.echo(EntropyBits(62, 8))

Here's the same thing in C/C++:

#include <math.h> #include <stdio.h> double EntropyBits(double valid, double size) { return valid ? size * log(valid) / log(2):0; } void main() { printf("%f", EntropyBits(62, 8)); }

IMPORTANT
The effective bit size of a password is an important variable when calculating its effective strength, but you should also consider whether the password can be guessed. For example, I have a dog, Major, and it would be awful of me to create a password like Maj0r, which would be easy for someone who knew a little about me to guess.

Do not underestimate the power of social engineering attacks. A friend of mine is a big fan of Victor Hugo's Les Mis rables, and recently he received a smartcard for his home computer. Not so surprisingly, I determined the PIN in one guess it was 24601, Jean Valjean's prisoner number.

Let me give you an idea of how bad many passwords are. Remember that DES, considered insecure for long-lived data, uses a 56-bit key. Now look at Table 8-1 to see the available-character pool size and password length required in different scenarios to create equivalent 56-bit and 128-bit keys.

Table 8-1. Available Characters and Password Lengths for Two Keys
Scenario	Available Characters	Required Password Length for 56-Bit Key	Required Password Length for 128-Bit Key
Numeric PIN	10 (0 9)	17	40
Case-insensitive alpha	26 (A Z or a z)	12	28
Case-sensitive alpha	52 (A Z and a z)	10	23
Case-sensitive alpha and numeric	62 (A Z, a z, and 0 9)	10	22
Case-sensitive alpha, numeric, and punctuation	93 (A Z, a z, 0 9, and punctuation)	9	20

If you gather keys or passwords from users, you should consider adding information to the dialog box explaining how good the password is based on its entropy. Figure 8-2 shows an example.

figure 8-2 an example of a password entry dialog box informing the user of the relative strength of the password the user entered.

Figure 8-2. An example of a password entry dialog box informing the user of the relative strength of the password the user entered.

IMPORTANT
If you must use passwords from users to generate keys, make sure the passwords are long and highly random. Of course, people do not remember random data easily. You need to find a happy balance between randomness and ease of recall. For an enlightening document about password weakness, read The Memorability and Security of Passwords Some Empirical Results at http://www.ftp.cl.cam.ac.uk/ftp/users/rja14/tr500.pdf.

More Info
In Windows .NET Server 2003 and later, you can validate password compliance with your corporate password policy by calling NetValidatePasswordPolicy. A C++ sample, ChkPwd, is included with the book's sample files in the folder Secureco2\Chapter08.

Another great document regarding random numbers in secure applications is an Internet draft written by Donald Eastlake, Jeffrey Schiller, and Steve Crocker: Randomness Requirements for Security, which replaces RFC 1750. This is a technical yet practical discussion of random number generation. At the time of this writing, the document had expired, but the last document name was draft-eastlake-randomness2-02. You may want to search for it using your favorite Internet search engine.