Generating a Key from a Password

If you're trying to encrypt data using a password, how do you convert the password into a key for symmetric encryption? The easiest way might be to simply convert the password to a byte array, and use this array as your key. However, this is a very bad idea and will lead to an easily cracked system. First of all, for a 256 bit encryption algorithm your passwords would all have to be exactly 32 bytes, or you would end up with not enough bits for the key; or worse, too many bits for the key, meaning that every password that starts with the same eight characters will work to decrypt the data.

In the English language, passwords will probably only contain the characters a-z, A-Z, 0-9, and perhaps some symbols. This means that only 70-75 of the possible 256 bit combinations for each byte will be used. In addition, not every symbol will be used with even frequency. Various estimates for the entropy in a single byte of an English language password vary from 1.3 to 4 bits. This means that in order to generate a good 256 bit key, you'll need a password that's anywhere from 64 to 197 bytes long!

Fortunately the .Net Framework has provided several ways for you to convert passwords to keys, all of which are much better alternatives than the simple method mentioned above. All of the methods I mention below will always generate the same key given the same set of inputs, so they can be use to effectively create password-based encryption in your code.

CryptDeriveKey

The PasswordDeriveBytes class is available in current releases of the framework, and contains two methods for you to generate keys.

One way of using PasswordDeriveBytes is as a simple wrapper around CAPI's CryptDeriveKey function. This is done by calling the appropriately named CryptDeriveKey method of PasswordDeriveBytes. When calling CryptDeriveKey, you'll be using the password found in the class constructor, but you'll need to pass in the cryptographic algorithm that you're generating a key for, the size of the key that you'd like to use, and the name of the hash algorithm you'd like to use to generate the key.  When calling CryptDeriveKey, the salt and iteration count that are set on the PasswordDeriveBytes object are not used, so even having different salts and iteration counts will produce the same key given that the rest of the inputs are also the same. (I'll discuss the use of the salt and iteration count later.)

Some sample code might clear up the use of CryptDeriveKey.

PasswordDeriveBytes cdk = new PasswordDeriveBytes("P@$$w0rd", null);

// generate an RC2 key
byte[] iv = new byte[] { 0, 0, 0, 0, 0, 0, 0, 0 };
byte[] key = cdk.CryptDeriveKey("RC2", "SHA1", 128, iv);
Console.WriteLine(key.Length * 8);
        
// setup an RC2 object to encrypt with the derived key
RC2CryptoServiceProvider rc2 = new RC2CryptoServiceProvider();
rc2.Key = key;
rc2.IV = new byte[] { 21, 22, 23, 24, 25, 26, 27, 28};
        
// now encrypt with it
byte[] plaintext = Encoding.UTF8.GetBytes("Message");
MemoryStream ms = new MemoryStream();
CryptoStream cs = new CryptoStream(ms, rc2.CreateEncryptor(), CryptoStreamMode.Write)

cs.Write(plaintext, 0, plaintext.Length);
cs.Close();
byte[] encrypted = ms.ToArray()

 

The sample generates a 128 bit key to use with the RC2 algorithm. This key is generated by using the SHA1 hash algorithm. The IV parameter to CryptDeriveKey is actually an out parameter -- it's supposed to represent the IV that you can use with your algorithm. However, current implementations just set this to an array of zeros, so you'll need an IV anyway. (Obviously my IV and password aren't the strongest in the world.)

I occasionally get asked what algorithms you can pass to CryptDeriveKey. Since CryptDeriveKey is a wrapper around CAPI, you need to pass a parameter that CAPI can understand. This means, it must be a string that CryptoConfig will map to a *CryptoServiceProvider class. (Actually, this is simplified a bit .... any algorithm that has the same OID as a CSP class will work, but for all intents and purposes, stick with the CryptoServiceProvider classes). In v1.1 of the framework, these classes are:

Hash Algorithms

String	Implementation
https://www.w3.org/2000/09/xmldsig#sha1	System.Security.Cryptography.SHA1CryptoServiceProvider
MD5	System.Security.Cryptography.MD5CryptoServiceProvider
SHA	System.Security.Cryptography.SHA1CryptoServiceProvider
SHA1	System.Security.Cryptography.SHA1CryptoServiceProvider
System.Security.Cryptography.HashAlgorithm	System.Security.Cryptography.SHA1CryptoServiceProvider
System.Security.Cryptography.MD5	System.Security.Cryptography.MD5CryptoServiceProvider
System.Security.Cryptography.SHA1	System.Security.Cryptography.SHA1CryptoServiceProvider

Symmetric Algorithms

String	Implementation
3DES	System.Security.Cryptography.TripleDESCryptoServiceProvider
DES	System.Security.Cryptography.DESCryptoServiceProvider
RC2	System.Security.Cryptography.RC2CryptoServiceProvider
System.Security.Cryptography.DES	System.Security.Cryptography.DESCryptoServiceProvider
System.Security.Cryptography.RC2	System.Security.Cryptography.RC2CryptoServiceProvider
System.Security.Cryptography.TripleDES	System.Security.Cryptography.TripleDESCryptoServiceProvider
Triple DES	System.Security.Cryptography.TripleDESCryptoServiceProvider
TripleDES	System.Security.Cryptography.TripleDESCryptoServiceProvider

PBKDF1

The other use of PasswordDeriveBytes is as an implementation of the PBKDF1 algorithm, specified in RFC 2898, section 5.1. (PBKDF stands for Password Based Key Derivation Function). PBKDF1 is a pretty simple algorithm:

1. Concatenate the Password and Salt: R0 = Pwd + Salt
2. Hash the result Iteration Count times: Rn = Hash(Rn - 1)
3. The result is the Rn where n = Iteration Count

As you can see, PBKDF1 uses a salt to reduce the risk of a dictionary attack.  Having a large salt will reduce the risk that an attacker can create a list of the output keys for a set of given passwords. Instead of just having to calculate one key, the attacker would have to calculate one key for each salt.  RSA, who developed the algorithm as a part of PKCS #5, recommends a salt of at least 64 bits.  A 64 bit salt would mean the attacker would need to generate 2^64 keys for each password in order to use a dictionary attack.

In addition, an iteration count is required. In general, the larger the iteration count, the stronger the resulting key. Here, RSA recommends a value of at least 1000. PBKDF1 uses either MD4, MD5, or SHA1 as its underlying hash algorithm, although PasswordDeriveBytes will not care if you use another hash algorithm.

In order to generate your key, you call GetBytes passing in the number of bytes you need for a key. One neat thing about the output of GetBytes is that getting two smaller byte arrays is the same as getting one larger one. For instance, two arrays of 20 bytes put together will be the same as a call to GetBytes(40). You can call GetBytes as many times as you need. PBKDF1 will only produce the number of bytes that the hash algorithm generates, but GetBytes will extend the result further, allowing you to get a large number of bytes out of your password.

The following sample is a rewrite of the CryptDeriveKey sample, using PBKDF1. In this case, I'm using a simple salt, an iteration count of 1000, and the SHA1 hash algorithm. I also use PasswordDeriveBytes to generate an IV for me.

// setup the password generator
byte[] salt = new byte[] { 0, 1, 2, 3, 4, 5, 6, 7 };
PasswordDeriveBytes pwdGen = new PasswordDeriveBytes("P@$$w0rd", salt);
pwdGen.IterationCount = 1000;
pwdGen.HashName = "SHA1";
        
// generate an RC2 key
byte[] key = pwdGen.GetBytes(16);
byte[] iv = pwdGen.GetBytes(8);
        
// setup an RC2 object to encrypt with the derived key
RC2CryptoServiceProvider rc2 = new RC2CryptoServiceProvider();
rc2.Key = key;
rc2.IV = iv;
        
// now encrypt with it
byte[] plaintext = Encoding.UTF8.GetBytes("Message");
MemoryStream ms = new MemoryStream();
CryptoStream cs = new CryptoStream(ms, rc2.CreateEncryptor(), CryptoStreamMode.Write);
        
cs.Write(plaintext, 0, plaintext.Length);
cs.Close();
byte[] encrypted = ms.ToArray();

 

PBKDF2

With the release of Whidbey, the frameworks will have an implementation of PBKDF2, in the class Rfc2898DeriveBytes. PBKDF2 is also defined in RFC 2898, in section 5.2. The big advantage of PBKDF2 over PBKDF1 is that the output from PBKDF2 is not bounded to the size of a hash algorithm's output. Although the .Net implementation of PBKDF1 does not impose this limitation on you, in order to be more secure I'd recommended that you move to PBKDF2 when you make the move to Whidbey. As you'll see, moving from PasswordDeriveBytes to Rfc2898DeriveBytes is trivial since Rfc2898DeriveBytes works in much the same way as PasswordDeriveBytes. You start by setting up a password, salt, and iteration count (PBKDF2 uses HMACSHA1 as an underlying pseudo-random generator). Then you call GetBytes repeatedly until you have enough data to encrypt with. The following code is a rewrite of the PBKDF1 code to use PBKDF2:

// Setup the password generator
byte[] salt = new byte[] { 0, 1, 2, 3, 4, 5, 6, 7 };
Rfc2898DeriveBytes pwdGen = new Rfc2898DeriveBytes("P@$$w0rd", salt, 1000);
        
// generate an RC2 key
byte[] key = pwdGen.GetBytes(16);
byte[] iv = pwdGen.GetBytes(8);
        
// setup an RC2 object to encrypt with the derived key
RC2CryptoServiceProvider rc2 = new RC2CryptoServiceProvider();
rc2.Key = key;
rc2.IV = iv;
        
// now encrypt with it
byte[] plaintext = Encoding.UTF8.GetBytes("Message");
MemoryStream ms = new MemoryStream();
CryptoStream cs = new CryptoStream(ms, rc2.CreateEncryptor(), CryptoStreamMode.Write);
        
cs.Write(plaintext, 0, plaintext.Length);
cs.Close();
byte[] encrypted = ms.ToArray();

 

As you can see, the only change to the code is replacing the PasswordDeriveBytes class with an Rfc2898DeriveBytes class.

Other changes for Whidbey include the ability to set a byte array password (on both PasswordDeriveBytes and Rfc2898DeriveBytes), which increases security by allowing you more control over the password object. (More on that in a future post.)

Hopefully this has provided some useful examples of how to generate a good cryptographic key using a password.

Comments

• Anonymous
  April 14, 2004
  The comment has been removed

• Anonymous
  April 15, 2004
  The comment has been removed

• Anonymous
  April 15, 2004
  Well, transmitting a salt or an IV in plaintext comes out to the same thing. A 64-bit salt or a 64-bit IV -- user's choice :). Either way, you've got some initialization (be it for the cipherstream or the hashing) being sent.

• Anonymous
  April 15, 2004
  Right, but if you choose to send the IV than you need to also send the salt because there's no way to calculate that (unless you have it hardcoded in your application, or have some other pre-determined way to create a common salt). This way, I only have to send the salt, and the IV can be calculated from the salt + password.

• Anonymous
  April 21, 2004
  The comment has been removed

• Anonymous
  April 21, 2004
  Pardon my typos in the preceding post (sunny day, on my deck, couldn't see screen), but I think the ideas are correct ...

• Anonymous
  April 21, 2004
  Sitting on the deck on a sunny day ...... you're making me jealous :-)
  
  I haven't seen a formal proof anywhere that iterations do not decrease the effectiveness of PBKDF2, in fact, it's pretty generally accepted that iteration count increases the effectiveness.
  
  Unfortunately I couldn't find any resources to point you at. Since the RSA people are the ones who came up with PBKDF2, I'd recommend starting a search over on their site to see if you can find anything. If you do find some information, please post it back here .... it'd be interesting to read.

• Anonymous
  April 21, 2004
  Thanks for the response. I tend to agree with your comment that "IC increases the effectiveness" (which I phrased as workfactor in my original post). As I acknowledged, the question was a knowingly "academic" one about pure-entropy, as opposed to overall practicality of the design. But that's fair game in the crypto business: an "provably academically secure" technique [admittedly within the bounds of cryptographic/probabilistic surety] is always more reassuring than a "merely practically hard" technique.
  
  I have indeed done a web search or two on this topic, but haven't found diddly. I was sort-of hoping you'd been more lucky. RSA is more likely to talk to Microsoft than to an "anonymous coward" like me ... :-)
  

• Anonymous
  August 06, 2004
  Hello, I'm very interested in Whidbey security and how to upgrade my application (.NET 1.1)when ASP .NET 2.0 will be released.
  If you have time, could you help me and follow the link :
  www.asp.net/Forums/ShowPost.aspx?tabindex=1&PostID=657449
  
  Thanks in advance for any help.

• Anonymous
  October 11, 2004
  I am doing some research on how I can efficiently encrypt data .NET 1.1 and decrypt with VC++ 6.0, I found the following links very useful: the old and the new? WINCRYPT.H Generating a Key from a Password CryptDeriveKey...

• Anonymous
  August 24, 2005
  There's a ton of new and enhanced security features coming with the v2.0 release of the CLR.  However,...

• Anonymous
  August 31, 2005
  There's a ton of new and enhanced security features coming with the v2.0 release of the CLR.  However,...

• Anonymous
  February 27, 2006
  Хранить пароли в открытом виде — это клиническая форма легкомыслия. Идеальное ре

• Anonymous
  July 17, 2006
  The comment has been removed

• Anonymous
  July 17, 2006
  The comment has been removed

• Anonymous
  February 20, 2007
  I have the following problem: A c++ application that get encrypted message from a NET application. The C++ is using Crypto API and the NET should be using what is availabel in the NET. Each App can Ecrypt/Decrypt its own but I can't get the C++ to decript NET encrypted Message. Using RC2, (RC4 is not valailabel on NET and AES not available on Windows 2000 without the NET frame work), the crypto API is using hashed password (MD5) and the NET is using : Password,Salt and IV. How the Salt and IV on the NET should be handled at the C++ end ?  

• Anonymous
  February 23, 2007
  You need to use the same algorithm to derive your key on both ends.  Both CAPI and .NET Support CryptDeriveKey which you should probably be using. -Shawn

• Anonymous
  April 03, 2007
  I have the same problem as Itamar above. We have old VB 6.0 code that uses the MS base cryptographic service written using calls to the advapi32.dll (things like CryptEncrypt, CryptCreateHash and so on). I ported the code to C# (still using CAPI) and it works fine in that I can encode a string in C# and decode it in the old code and vice versa. The problem is when I try to use the .Net native calls (SymmetricAlgorithm RC2 and other .Net classes). I can encrypt and decrypt in .Net, but the strings are not interchangeable between the two versions. As far as I can tell, I'm using the exact same parameters, at least the ones I can get to. For example, .Net won't let me set the provider name so it uses the enhanced MS provider while the old code uses the basic one. But even if I change the old code to use the enhanced provider, I cannot interchange strings between the two. This must mean that I'm missing some parameter that is set by default in either version. I am using CryptDeriveKey("RC2", "MD5", 40, iv) in C# and I'm positive these are the same parameters in CAPI (with iv being all zeros). Any ideas?

• Anonymous
  April 09, 2007
  The comment has been removed

• Anonymous
  May 12, 2009
  in what world does this make sense? "First of all, for a 256 bit encryption algorithm your passwords would all have to be exactly 8 bytes" 8 bytes * 8 bits/byte = 64 bits. 32 bytes * 8 bits/byte = 256 bits.

• Anonymous
  May 21, 2009
  Yep, you're right.  I've updated the post. -Shawn

• Anonymous
  June 16, 2009
  Even though this was written 4 years ago, this post is still beautiful and useful. I translated the russian comment above 'Хранить пароли в открытом виде — это клиническая форма легкомыслия. Идеальное ре ' (google translate provided: Store passwords in clear text - is the clinical form of levity. Perfect D) So to follow up with our Russian friend, how and where is a safe place to store the password?

• Anonymous
  February 10, 2010
  I've got a situation where I need to use Wincrypt and .Net to implement an AES encryption/decryption.  Basically I've got most of the application using .Net for AES, but I've got one piece that has to use non .Net and therefore I want to use Wincrypt.  However, I'm having issues generating the same key and as an end result the same encryption. The main issue I've figured is that Wincrypt has a very strict method to generate keys/perform the encryption. HOwever, the .Net side is the issue.  I can't seem to figure out how to duplicate the Wincrypt process in .Net.  Any ideas help would be greatly appreciated.

• Anonymous
  March 15, 2010
  The comment has been removed