Security Briefs
Password Minder Internals
Keith Brown
Contents
Stretching and Salting the Master Password
Derived Keys
Password Reminders
Secret Management
Creating Good Passwords
Other Features and Future Direction
Conclusion
In my last column I introduced Password Minder, the tool I use to manage all of my passwords. It generates a long, random password for each site I visit, and makes it possible for me to use the most complex passwords possible, without ever having to see the actual password material or type it in manually. If you didn't have a chance to read that column, you should go do that now, otherwise this column won't make much sense!
This time, I'll take you on a tour of the guts of how Password Minder implements its cryptographic functionality, show a few more features, and ponder future directions. Let's start with a closer look at the cryptography in Password Minder.
Stretching and Salting the Master Password
I keep my main password file on my laptop. Nobody uses the laptop but me, thus it provides real defense against someone recovering my passwords; they'd have to steal my password file before they can even try to crack my passwords! (Of course, it's a lot easier to steal a laptop than a desktop computer, so as an added layer of security I also use the Encrypted File System for the most sensitive folders in my system.) But from time to time I need to roam with my passwords, so I built some extra protection into the latest version of Password Minder.
In early versions, I calculated the master key by simply hashing the master password and taking 128 bits of that hash value as the key. If you consider hashing to be a single step that can be performed in one clock cycle by someone who has specialized hardware, then as I mentioned in my last column, given a 12-character password, an attacker will need about 279 clock cycles to hash all possible keys in this keyspace. On a 3GHz machine, this would take over 14 million years, but given Moore's law and parallel computation, this number doesn't look quite so impressive. And keep in mind that I really didn't start with a 79-bit keyspace given that I didn't pick a truly random master password. However, although Moore's law means computers keep getting faster, humans don't seem to be getting better at remembering longer passwords!
So I fixed Password Minder to use a much stronger mechanism for calculating the master key from the master password. Instead of hashing just once, the password is hashed many times. The algorithm that I use comes from RSA Labs' Public Key Cryptography Standards (PKCS). PKCS#5 is a guideline that specifically describes how to implement password-based cryptography. The guideline recommends a function called the Password Based Key Derivation Function 2 (PBKDF2), which describes a technique for obtaining key material from a password—which is exactly what Password Minder needs to do.
The function works by seeding a cryptographic pseudo-random number generator with the master password and a salt value. With each round, the generator produces output that is XOR'd into the final result. You can choose how many bytes of output you need. In this case, since I use 256-bit keys, I need 32 bytes of output. The generator is based on the HMAC function, which is a message authentication code derived from a hash. You can choose which hash algorithm to use with HMAC, although SHA-256 is probably your best choice today, given the recommendations found in the book Practical Cryptography (Wiley, 2003). Unfortunately, the Microsoft® .NET Framework doesn't implement PBKDF2. There is a class called PasswordDeriveBytes that implements something akin to an older version of the algorithm, and the next release of the Windows® OS, codenamed "Longhorn," appears to have a class that implements the newer algorithm with SHA1. I couldn't wait for Longhorn though, and I prefer to use SHA-256, so I wrote my own implementation based on the .NET Framework SHA256Managed class. This class is shown in Figure 1.
Figure 1 Password-Based Key Derivation Function 2
using System; using System.Security.Cryptography; // implementation of PKCS#5 v2.0 // Password Based Key Derivation Function 2 // https://www.rsasecurity.com/rsalabs/pkcs/pkcs-5/index.html // For the HMAC function, see RFC 2104 // https://www.ietf.org/rfc/rfc2104.txt class PBKDF2 { // SHA-256 has a 512-bit block size and gives a 256-bit output const int BLOCK_SIZE_IN_BYTES = 64; const int HASH_SIZE_IN_BYTES = 32; const byte IPAD = 0x36; const byte OPAD = 0x5C; public static byte[] GetBytes(string password, byte[] salt, int iterations, int howManyBytes) { return GetBytes( System.Text.Encoding.UTF8.GetBytes(password), salt, iterations, howManyBytes); } public static byte[] GetBytes(byte[] password, byte[] salt, int iterations, int howManyBytes) { // round up uint cBlocks = (uint)((howManyBytes+ HASH_SIZE_IN_BYTES-1)/HASH_SIZE_IN_BYTES); // seed for the pseudo-random fcn: salt + block index byte[] saltAndIndex = new byte[salt.Length + 4]; Array.Copy(salt, 0, saltAndIndex, 0, salt.Length); byte[] output = new byte[cBlocks*HASH_SIZE_IN_BYTES]; int outputOffset = 0; SHA256Managed innerHash = new SHA256Managed(); SHA256Managed outerHash = new SHA256Managed(); // HMAC says the key must be hashed or padded with zeros // so it fits into a single block of the hash in use if (password.Length > BLOCK_SIZE_IN_BYTES) { password = innerHash.ComputeHash(password); } byte[] key = new byte[BLOCK_SIZE_IN_BYTES]; Array.Copy(password, 0, key, 0, password.Length); byte[] InnerKey = new byte[BLOCK_SIZE_IN_BYTES]; byte[] OuterKey = new byte[BLOCK_SIZE_IN_BYTES]; for (int i = 0; i < BLOCK_SIZE_IN_BYTES; ++i) { InnerKey[i] = (byte)(key[i] ^ IPAD); OuterKey[i] = (byte)(key[i] ^ OPAD); } // for each block of desired output for (int iBlock = 0; iBlock < cBlocks; ++iBlock) { // seed HMAC with salt & block index _incrementBigEndianIndex(saltAndIndex, salt.Length); byte[] U = saltAndIndex; for (int i = 0; i < iterations; ++i) { // simple implementation of HMAC-SHA-256 innerHash.Initialize(); innerHash.TransformBlock(InnerKey, 0, BLOCK_SIZE_IN_BYTES, InnerKey, 0); innerHash.TransformFinalBlock(U, 0, U.Length); byte[] temp = innerHash.Hash; outerHash.Initialize(); outerHash.TransformBlock(OuterKey, 0, BLOCK_SIZE_IN_BYTES, OuterKey, 0); outerHash.TransformFinalBlock(temp, 0, temp.Length); U = outerHash.Hash; // U = result of HMAC // xor result into output buffer _xorByteArray(U, 0, HASH_SIZE_IN_BYTES, output, outputOffset); } outputOffset += HASH_SIZE_IN_BYTES; } byte[] result = new byte[howManyBytes]; Array.Copy(output, 0, result, 0, howManyBytes); return result; } // treat the four bytes starting at buf[offset] // as a big endian integer, and increment it static void _incrementBigEndianIndex(byte[] buf, int offset) { unchecked { if (0 == ++buf[offset+3]) if (0 == ++buf[offset+2]) if (0 == ++buf[offset+1]) if (0 == ++buf[offset+0]) throw new OverflowException(); } } static void _xorByteArray(byte[] src, int srcOffset, int cb, byte[] dest, int destOffset) { int end = checked(srcOffset + cb); while (srcOffset != end) { dest[destOffset] ^= src[srcOffset]; ++srcOffset; ++destOffset; } } }
This all sounds really technical, but the idea is to require the solution of a little puzzle in order to turn a password into a master key. Say you require 216 iterations of PBKDF2 in order to calculate your master key. This would effectively stretch your password's strength by 16 bits because the attacker would need to perform 216 steps for each password he wants to try in a brute-force attack. And to ensure that he can't gain an advantage from an economy of scale by attacking a bunch of passwords at the same time, a unique salt value is added to the password before any of this stretching begins. Here's the declaration of my function that computes the PBKDF2 algorithm, showing the inputs it requires:
byte[] GetBytes(byte[] password, byte[] salt, int iterations, int howManyBytes);
Password Minder encodes your master password into a byte array and uses a unique salt value that is stored in your password file to initialize the algorithm. It asks for 32 bytes of output, which produces a 256-bit AES master key. The iteration count is entirely up to you.
Figure 2** Change Master Password **
On my laptop, 216 iterations of this algorithm takes about a second. I'm currently using 218 iterations, which takes under five seconds and is about as long as I'll tolerate waiting. But next year when I buy a new laptop, I'll be able to use more iterations. Password Minder accommodates this by asking how much stretching you want whenever you reset your master password via the dialog shown in Figure 2. The slider bar controls the number of iterations you want to use, with the leftmost setting currently at 216 iterations, and each tick to the right increasing the number of iterations by a power of two. The rightmost setting, 225, takes so long I've never even bothered to wait for it to finish. The beauty of this system is that as my hardware gets faster over the years, I can use a larger number of iterations, thus keeping pace with any attacker who manages to get a copy of my password file.
Derived Keys
Password Minder uses a unique key to encrypt each piece of data stored in your password file. These keys are ultimately derived from your master key, which is derived from your master password via a large number of iterations of PBKDF2. In an earlier version of Password Minder, I didn't bother deriving unique keys for each record, until someone noticed that this leaks information. If you have two user names or passwords that are the same, the ciphertext for those items will also be the same. As you'll see, it's trivial to derive unique keys for everything and avoid this problem entirely.
It turns out that this is a common requirement in cryptosystems. For example, to build a secure channel, you need four unique symmetric keys: one for authenticating the data stream sent from the client to the server, another for encrypting that same stream, and two more for doing the same thing for the data stream flowing in the opposite direction. It's easy to generate these keys given a single shared session key: you can just hash the session key along with some unique data for each type of key you need. Here's an example of how this might work:
EKcs = H(SK || "EKcs"); AKcs = H(SK || "AKcs"); EKsc = H(SK || "EKsc"); AKsc = H(SK || "AKsc");
H is a hash function such as SHA-256 and the pipes (||) represent concatenation. Here, SK represents the session key shared by client and server, EK is the encryption key, AK represents the authentication key, cs stands for client to server, and sc stands for server to client.
Password Minder uses PBKDF2 to derive its keys. And it derives these keys in a couple of stages. Stage one derives a unique record key from the master key, and stage two splits that record key into the two keys that are then used to encrypt the user name and password for that record. Here are the formulas for deriving these keys (along with the verification key, which I'll discuss shortly):
RK = PBKDF2(MK, RS); VK = PBKDF2(MK, "VERIFIER"); UK = PBKDF2(RK, "USERID"); PK = PBKDF2(RK, "PASSWORD");
PBKDF2 is used with SHA-256 (one iteration only). These definitions apply to the formulas: MK stands for the master key (derived from master password), RS represents the salt value for the record, RK is the record key, VK refers to the verifier key, UK is the user name key, and PK is the password key.
You see, whenever you add a new record, Password Minder generates a random salt value for that record. If you look at the XML file where Password Minder stores your encrypted passwords, you'll see this salt value for each and every record:
<record site='amazon.com' salt='LonjRW5...ujPwsOtA1w==' encryptedUserId='umfrDFlbMaFvjseYnAny1g==' encryptedPassword=' iVkOGPXDwVKtvCCEkzI1Cg==' lastReset='2003-02-28T00:01:28Z'/>
Password Minder uses this per-record salt value to derive the record key, and then uses a couple of fixed salt values, "USERID" and "PASSWORD", to split that key into the two keys used for encrypting the user name and password, respectively. The overall flow is shown in Figure 3.
Figure 3** Deriving Keys **
The verification key is used to verify the master password. When you're prompted for your master password, your input is run through the litany of PBKDF2 iterations to derive the master key, and from the master key a verifier is derived (I showed the formula earlier). The verifier is base64-encoded in the password file, and allows Password Minder to verify that you've entered the correct password. If the calculated verifier doesn't match what's in the password file, Password Minder will prompt you to reenter your password. After three failed attempts, Password Minder will shut down.
Because the verifier is produced from the master key via one-way hash operations, an attacker can't use the value of the verifier to deduce the master key, although that alone doesn't stop a brute-force attack. Given that the master key is 256 bits long, brute forcing it against the verifier isn't a useful tactic either.
Password Reminders
I have a few passwords that need to be changed from time to time so that they don't expire, and getting these passwords reset after they expire is a major hassle. The problem is, I don't log into some of these sites enough to notice that my password may be expiring soon. So I included a feature in Password Minder to remind me when a password is about to expire. The program tracks the date of your last password reset for each record, and allows you to specify the validity period for the password, which is typically 45 or 90 days. You can also control how soon Password Minder starts nagging you to reset this password (see Figure 4).
Figure 4** Set Expiration **
Whenever you launch Password Minder, it looks at each record and lets you know if a password needs changing. Once you change your password (which you'll typically do by having Password Minder generate a new random password), the program will record the current date and the reminder cycle will start all over again. This feature has saved me endless headaches!
As an example of how difficult crypto really is, keep in mind that many pseudo-random number generators factor the current time into their sequence generation logic, so exposing the time at which the password was generated is leaking a bit of information to an attacker. A future enhancement to the application might be to not store the exact time the password was reset/updated, but rather to round it to the previous four-hour boundary, for example.
Secret Management
In earlier versions of Password Minder, I was a bit lazy about managing the master key; the main form simply kept the master key in a byte array and passed it to the cryptography helper functions whenever they needed it. The newer version takes advice from the book Writing Secure Code (Microsoft Press®, 2002) and keeps the master key deep down in the helper class that actually needs it. The idea here is that if you must have a secret in your program, you should keep it as close as possible to the code that actually uses that secret. Passing the secret around exposes it more than is necessary. If an attacker is able to somehow compromise a section of your code, it would be best not to have your secret right there on the stack where it is easily obtained.
So I've encapsulated all the cryptography into a class called CryptMaster. This class is responsible for managing all the secrets in Password Minder: everything from collecting your master password to decrypting individual password records and driving the class that inserts those passwords as keystrokes in the input queue. What's interesting is that the resulting code was much cleaner after this refactoring. It seems like a lot of the precautions we take when writing secure code naturally helps us to build more robust and maintainable code as well.
One security precaution that could be added to CryptMaster is the use of pinned byte arrays. It is a good practice to keep keys in pinned byte arrays (as opposed to unpinned arrays) so that you can zero them out when they are not needed anymore. The garbage collector is free to move unpinned arrays during any collection, creating the possibility that passwords and keys will remain in memory for longer than required. Using the new SecureString functionality in the .NET Framework 2.0 can help in this regard. Rather than playing games with pinned byte arrays, Password Minder deals with the problem of secrets in memory by having a very brief process lifetime. This was discussed in my last column.
Creating Good Passwords
Whenever you need to store a new password, Password Minder offers the option to auto generate one for you. The beauty of using Password Minder is that you can generate very large, complicated passwords, and you'll never need to actually type them yourself!
My original implementation of this function always generated 10-character random passwords by using a random sampling of the 26 uppercase and lowercase English letters, in addition to digits and 32 punctuation characters. However, I quickly learned that this simple approach left me out in the cold when I encountered Web sites that restricted the types of passwords they would allow. Some Web sites won't allow any punctuation at all, for example. For the first few months of using Password Minder, I would just manually choose a password for these sites.
But once my friends started complaining about this same problem, I decided to let the user choose the character set and length of the password, and then let Password Minder create a random password given those constraints. Figure 5 shows the resulting dialog. The default password length is 20, which is too big for many sites, and sadly they often won't tell you how long your password can be. Usually they'll only tell you a minimum length. Nobody seems to expect people to use long passwords!
Figure 5** Auto Generate Password **
Windows accounts can have very long passwords. Heck, when I generate passwords for a service or IIS application pool, I ask Password Minder to generate a 75-character password. Why not? I'll never have to type or remember it, and using a long password doesn't impact performance. Windows supports passwords up to 127 characters long. Just be careful about creating accounts for users like this because if your users run Windows 9x, they'll be limited to 14-character passwords. Of course, from a theoretical perspective, the strength of a password is only as strong as the master key from which it was produced.
Other Features and Future Direction
Password Minder allows you to import or export passwords. This allows me to share some passwords with my wife for doing online banking and such. It also allows me to export passwords I'll need on the road to a file on a USB memory stick.
Another feature of Password Minder was added to support the few finicky applications that don't like the way Password Minder injects passwords into the input queue. If you ever run into this, just select the entry you want in Password Minder and press Ctrl+C to copy the cleartext password to the clipboard. You can then paste the password wherever you want. This can also be convenient if you find yourself needing passwords over and over. Password Minder clears the clipboard when it shuts down, so to use this feature you'll need to keep Password Minder running until you're finished pasting passwords.
The other day I was having trouble logging into a site, and I got tired of typing my master password over and over and waiting for it to calculate the master key. So I just left Password Minder open and copied and pasted passwords until the problem was solved. Just be careful if you use this feature to remember to close down Password Minder when you're finished.
One last feature bears mentioning. Sometimes you need to type your password twice. To avoid having to restart Password Minder, just press F5 to type the password and keep Password Minder running. When you need to type the password the second time, just click the Password Minder window to bring it to the foreground and press Enter like you would normally. This is useful when you're signing up for a new account and need to confirm your password.
As for future directions, the most interesting idea I've heard so far is to allow Password Minder to act as a Web service client. This would allow you to host your password file on a central Web server so you could use it from several different machines. It's an interesting idea, and when I get some spare cycles I may just add it. The main thing that scares me about this is having my mom log into a machine at some public kiosk and use her password file from there. You should always be wary of what you type into an untrusted machine. The combination of typing your master password on an untrusted keyboard along with having your password file available on a Web share gives me the heebie jeebies. This is not a feature I would enable by default!
A simpler feature that I'm working on right now is tracking usage for each record. By tracking how often a password is used, I can sort the list to bring the most heavily used passwords to the top. When you've got as many passwords as I have, a simple feature like this can make life much easier.
Conclusion
I hope you'll find Password Minder useful, either as a tool or as a sample of how to implement password-based cryptography. If you're doing the latter, I suggest reading the PKCS#5 specification, which you can find at PKCS #5: Password-Based Cryptography Standard. If you're thinking of implementing any sort of cryptography in your system, be sure to read Practical Cryptography by Niels Ferguson and Bruce Schneier to learn just how hard it really is to get this right. Consider hiring a professional cryptographer to look at your design and review your code. Crypto is the one link in an application that everyone assumes is strong. Make sure your assumption is correct!
Oh, and if you don't like Password Minder for one reason or another, find a tool that you do like and use it. Password Safe is another option. Given the large number of credentials we all need to manage these days, you'd be crazy not to find a tool to help you do it well. Just be sure to pick one from a vendor you really trust.
Send your questions or comments for Keith to briefs@microsoft.com.
Keith Brown is a co-founder of Pluralsight, specializing in developing and delivering high-quality training for software developers. Keith's most recent book, The .NET Developer's Guide to Windows Security, is available here.