[ This article originally appeared in Security Technique Magazine in 2003. -Ed.]
There is no other system security component more ubiquitous than the simple password. The use of passwords on multi-user systems is so common today that it's difficult to remember there was a time when users did not use passwords to log onto a personal computer. The most common use of passwords is to authenticate a user to a system, but there are other uses for passwords. This document provides guidance to software developers as to how to properly implement systems that use or hold passwords. We begin with simple introduction to the concept of Password Based Encryption. Password Based Encryption (or PBE for short,) is a family of techniques which derive a pseudo-random string of bits appropriate for use as an encryption key. At first glance, this may seem to be a simple task. As we shall see, however, it is a little more difficult.
Passwords are traditionally used to authenticate users to systems or networks. The Unix /etc/passwd file, the Windows SAM database, and the Apache htpasswd utility are all examples of system components designed to securely store user authenticators. An examination of each of these systems finds that none of them actually store passwords. Instead, a hashed or encrypted version of the password (or pass phrase) is stored. To understand why may require a little history lesson.
Some of the original multi-user computer systems stored 'plaintext' passwords. This is to say, if your password was 'g78twin2', then the system stored 'g78twin2' in a database somewhere. There were some worries that someone might get access to this master database, but for the most computer security managers were confident in the file and database security features included in these old systems. People discussed improvements to the system, but without a compelling reason to ratchet up the security of password storage sub-systems, most everyone thought there were more important things to work on.
All this changed in the early 70's with a clever exploit of a vulnerability in the TENEX operating system. TENEX was a popular operating system for the PDP 10 system. For the time it was an advanced system with many innovative features. In the early 70's one of the more interesting features in computer system architecture was virtual memory. Virtual memory, for those unfamiliar with the term, refers to the use of special hardware to transparently swap data from memory to the hard drive when it hasn't been used in a while. This helps the system run more large, complex programs simultaneously. If one program hasn't accessed some of it's data in a while, it is written to disk and the memory is reallocated to a program with an urgent need for more memory. When a chunk of memory (called a "page") is written to disk, it is said that that page has been "paged out." When a program needs that memory again, the program is halted while the "paged out" data is read back into memory. This event is called a "page fault."
A group of clever hackers noticed that they could figure out if a page fault had occurred by keeping a close eye on the system clock. Hard disks of the day were expensive and slow. From the computer processor's perspective, it took an relatively long time to read data back from disk. A function that would take 200 microseconds to complete in memory could take as long as 200 milliseconds (that's 2 tenths of a second) to complete if there was a page fault in the middle of the function. Using the ability to accurately measure the time the system takes to check a password, these clever attackers were able to guess passwords with remarkable accuracy. Here's how they did it.
To check a password, the system compared each character in the stored password with the one provided by the user. If any of the character's didn't match, an error would be returned. The pseudo code might have looked something like this:
int i;
for( i=0; i<8; i++ ) {
if( stored_password[i] != trial_password[i] )
break;
}
if( i < 8 )
return( ERROR );
This code simply says when comparing a trial password with a stored password, check all eight characters in the password, if one of the characters in the trial password given by the user does not match the character in the stored password, break out of the loop. After the loop check to see if all eight characters were checked; if not, report an error. (Don't try to compile this code, it's meant to be a pseudo-code example...) If all eight characters were checked and none reported an error, then the trial password given by the user and the password stored in the system password database are the same.
A cursory examination of this code would imply that if an attacker was guessing passwords, they would have to try every valid password; checking all 2^64 possibilities. To avoid having to check so many passwords, the attackers devised a cunning plan. They placed their candidate password on a page boundary. This is where two chunks of memory join; by carefully crafting an attack program, the attackers put only the first part of a trial password on the first memory page. The remainder of the password was placed on the second memory page and then "swapped out to disk." They then asked the system to check their trial password, and measured how long it took.
What's the point of this exercise? If the first character they guessed was incorrect, the system would fail after reading only the first character in the first page. The password subsystem would not need to check characters two through eight and would not load the second page in from disk. Remember, the attackers found a way to accurately measure the time it took the system to check their 'trial' password. If the system did not generate a page fault while reading their trial password, then the first character in their guess was incorrect. They simply repeated this process until a page fault indicated they had found the right character in the first position of the password.
This technique also works for the remaining seven characters in the password. By storing different parts of the trial password on different pages, the TENEX hackers were able to guess the entire password in considerably fewer trials than the 2^64 guesses it should have taken. By applying this "timing attack" against trial passwords, first with the first character on the first memory page, then with two characters on the first page, and so on, the attackers created an attack with a 2^8 * 8 (or 2^11) worst case. Due to the birthday paradox, on average, they should be able to recover a password with 2^7 * 8 (or 2^10) guesses.
Modern password systems avoid timing attacks such as the one described here by hashing and salting, techniques described in the "Avoiding the Dictionary Attack" section below.
Some readers may be familiar with Smart Cards; they look like credit cards with electrical contacts in the upper left portion of the front face. Within the security industry, they're a well known technology and have been around for ages. Most modern cards contain a cryptographic coprocessor and secure storage for cryptographic keys. They're used extensively to provide mobile storage for secret or private keys. While there are noticeable barriers to widespread adoption, Smart Cards are great at what they do: securely move keys from one machine to the next.
When using a Smart Card, it is common practice to require the card's owner to log in with a password or PIN code. In the early days of Smart Card usage, the password used to authenticate a user to the smart card was stored in the clear in the smart card. In the next section, we'll talk about why this is a bad idea for multi-user systems, but Smart Cards were considered to be secure, single user systems. Furthermore, once a password was set, there was no protocol interface to get the password back out. Many developers thought this was sufficient to secure the password stored in the card. For many years, it was.
All this changed when some clever researchers pointed out that if you steal someone's smart card, give it a fake password, and take very accurate readings of the card's current and voltage use, you can mount an attack similar to the TENEX password attack. In the case of Smart Cards however, you don't necessarily perform a timing test, but a power usage test. Two types of "power attacks" work because the hardware inside the smart card uses a slightly different amount of power based on what instruction is being executed and the number of bits set in a particular register.
The assembly language instructions executed inside the smart card to check a password given to it might look something like this:
xor cx, cx ; Clear the CX register
top_of_loop:
cmp cx, 8 ; Have we looked at all 8 characters?
je are_equal ; If so, and we haven't found an error, then the password is correct
mov ah, [ds:si] ; Move the Nth character of the stored password to register AH
cmp ah, [es:di] ; Compare it with the Nth character of the trial password
jne not_equal ; If the two are not equal, exit the loop
inc cx ; Increment the password length counter, and pointers
inc si ; to stored and trial passwords
inc di
jmp top_of_loop ; jump to the top of the loop and check the next character
not_equal:
mov ah, FFh ; put a -1 in the AH register
jmp exuent_omnis
are_equal:
xor ah, ah ; clear the AH register
exuent_omnis:
ret ; return to the calling function
This code assumes that both passwords are 8 characters long, and will return a 0 in the AH register if the passwords are equal and a -1 in AH if the two are not equal. We further assume that the register pair DS:SI points to the password stored in the smart card, while the ES:DI register pair points to the password provided by the user.
By tracing the execution of this code, you can see that as soon as a bad character is found, we escape out of the password checking loop. Were we monitoring the power usage of the smart card as this password checking code was being run, we would see a different power signature for a loop that failed after checking one character than for a loop that checked all eight characters (or any other number of characters.) Because we could see how many characters we got right, we could attack the password checking code inside the smart card in the same way that TENEX based passwords were attacked.
The solution to this problem is usually considered to be hashing as described in the next section, "Passwords In the Clear." Certain classes of smart cards don't have the processing power to rapidly calculate the cryptographic hash for this scheme to be effective. In situations like this, it is sometimes considered acceptable to still store the password in the clear, but check it with a slightly different loop. The following code is considered more secure than the code above. Why? It avoids generating a power signature by executing exactly the same code, irrespective of whether the stored password matches the trial password.
xor cx, cx ; clear the cx and al registers
xor al, al
top_of_loop:
mov ah, [ds:si] ; XOR the Nth character of the stored and trial
xor ah, [es:di] ; password together, putting the result in the AH register
or al, ah ; OR the contents of the AH and AL registers, putting the result
; in the AL register
inc cx
cmp cx, 8
jne top_of_loop
bottom_of_loop:
mov ah, al
ret
This code effectively does the same thing. If the two passwords are identical, then when the Nth character of the given password is XORed with the Nth character of the trial password, the result will be zero. After XORing each of the characters in the two passwords together, we use a logical OR to combine the results. If two passwords are the same, the result will be zero. If the two are not the same, then the result will be non-zero.
This code should come with a caveat, however. Storing passwords "in the clear," is an inherently dangerous thing to do. If there is a flaw in the password handling code within the smart card, there is an outside possibility that it might be exploitable. There is also the possibility that an attacker could place an extremely sensitive power meter up to the smart card an try to measure the current drawn by the AL register. There is some data to indicate that this is not so far-fetched of an idea. Modern smart card systems take precautions to avoid this possibility, but there's no guarantee that today's safeguards won't be defeated by tomorrow's exploits.
If you are developing a smart card solution, and you feel you should use this approach, be prepared for the possibility of an exploit.
No matter how tempted you are, do not use this approach in a multi-user operating system.
Another problem with passwords is storing them securely. From reading about the TENEX bug, we already have the idea that storing passwords "in the clear" is a bad idea. There is another reason why cleartext passwords are a bad idea: password databases are a single point of failure for a security system. Imagine what would happen if an attacker was able to recover the password for every user on a system. The attacker could log in as any user, modify any file, and effectively steal any user's identity. Want to write an angry letter to your boss? Want to commit credit card fraud or try to hack into someone elses computer? You wouldn't do these things from your account, and neither would an attacker. One of the first places an attacker will go when a system is compromised is the user password database. If the attacker can assume someone else's identity, he or she can operate with fear of reprisal or capture.
It's clearly a good idea to protect access to the password database. But at the same time, the password database has to be accessible to authenticate users when they want to log in. In order to authenticate a user, some portion of the system must access the password database to check the authenticity of passwords given by users as they log in. Computer systems are good at granting full access or completely restricting access. It is an unfortunate truth that bugs in the software that manages access to the password database can be used by attackers to gain illicit access to it's contents.
There is also the problem of password database backups. If a user's password is stored in a database and that database is backed up, a clever attacker could attempt to steal the backup tape. Stealing the backup tape would work even if there is a great deal of security surrounding the computer system being attacked.
In response to these issues, it has become a common practice to hash passwords before storing them in a password database.
At this point we've talked a little about why passwords should be hashed (or encrypted) prior to storing in the password database. Now we will talk about how passwords are hashed. We assume that readers are familiar with hash functions, but if not, here is a brief introduction. Hash functions are used to convert a string of arbitrarily length into a fixed bit string. The data to be hashed is called the 'pre-image,' while the output of a hash function is called the 'hash' or 'digest.' Hash functions have many uses, but one of the most popular uses is to ease the comparison of two strings. Rather than comparing two strings directly, a developer can compare the hash of the two strings. This is advantageous as it allows software developers to optimize comparison techniques and to have a representation of the arbitrarily long string in a fixed length buffer. There is a class of hash functions called "cryptographic hash functions" or "message digest codes" that have a few more properties. The most interesting is the computational difficulty of finding a pre-image for a given hash. For the rest of this document, assume we're talking about cryptographic hash functions when we mention hash functions.
Systems that store password hashes effectively all do the same thing:
Lets try an example. Assume that my user name is 'mhamrick' and my password is 'dingo.' When I establish an account on a system I am asked for my initial password. I dutifully enter 'dingo' when prompted. Instead of storing 'dingo' in the password database next to my username 'mhamrick', the system stores the MD5 hash of 'dingo' which in hexadecimal is: f5 c2 26 e5 04 4e 5d f0 5c e4 9e 9e b0 bc ac 1c. When I come back to log in, I enter my username and password at the login prompt. The system uses my username as a key in the database to look up my password. Assuming everything works correctly, the login program retrieves 'f5 c2 26 e5 04 4e 5d f0 5c e4 9e 9e b0 bc ac 1c' from the database. If I entered my password correctly, it should hash to the same thing. The system compares the two hashes, finds them identical, and logs me in as user 'mhamrick.'
So, what happens if I enter the password in wrong. Lets first say that I transposed a few letters in the password as I was entering it in. Instead of entering 'dingo,' I entered 'dnigo.' The resultant hash of 'dnigo' is: f6 dc 32 60 da ac b2 61 ed 22 cd 32 72 0b aa 18. The two are clearly not the same, so when I enter 'dnigo', the system compares the hash in the password database with the hash of 'dnigo,' finds that they are not the same and rejects my login attempt.
The goal of a hashed password system is maintain system security even if an attacker has full access to the contents of the password file. If implemented correctly, even when an attacker is in possession of the password database, they are no closer to being able to correctly guess a user's password.Avoiding the Dictionary Attack
The next type of attack we want to resist is the "Dictionary Attack." Password crackers have noted that users frequently use easy to remember passwords such as names, locations, proper nouns, and so on. Certainly something like "wilddingo" is easier to remember than "7G4kex8d09." Choosing such an easy to remember word or word combination greatly reduces the number of trial passwords an attacker will check before finding a correct password. To speed things along, some system adversaries took a dictionary of common words and ran each entry through the password hashing algorithm. A database was then constructed of common words and their hashes, sorted by the hash. Once this database is created, it is a simple task to see if a hashed password is in the database of hashed dictionary words. In the early days of secure computing, there were an embarrassing number of break-ins using this technique.
To avoid the dictionary attack, modern systems will prepend a "random salt" to a password before applying the hash function. The salt is stored, unencrypted in the password database along with the salted and hashed password.
The password generation process using salted hashes looks like this:
The process of checking the password is now:
The purpose of the salt is to increase the number of "dictionary entries" for each password. When storing a non-salted hashed password, an attacker would only have to pre-calculate one hashed password for each password to populate his dictionary. With salted passwords, the attacker would have to create a dictionary entry for each pair of salt values and common words.
Another application of passwords is what's called Password Based Encryption (or PBE.) PBE is technique for generating an encryption key from a password.
PKCS#5 is one of the more popular PBE methods. It specifies the following algorithm:
Password Based Encryption is useful when you want to send an encrypted message to someone and distribute the decryption key via some out of band method; perhaps you are planning on phoning the recipient or writing down the password on a piece of paper and hand delivering it. When the message recipient has the encrypted message and the password, they decrypt the message with the following algorithm:
System developers should understand that what might be a good hash algorithm today could easily become a vulnerability tomorrow. Several message digest algorithms were well regarded for years before viable attacks were discovered against them. At the time this document was written, the Secure Hash Algorithm (SHA) family of hash algorithms were among the most widely used and well regarded. One should note that the original SHA algorithm (now called SHA0) was found to have some weaknesses. The revised SHA-1 algorithm is still considered a good choice. SHA-256, SHA-384, and SHA-512 are new additions to the SHA family that are internally very similar to the SHA-1 algorithm.
In general, you should choose a hash algorithm that produces twice as many bits as you need for your encryption algorithm. For instance, if you were generating a password-based key for use with the DES algorithm, SHA-1 would be an acceptable choice for hashing your salted password. This is because DES uses a 56 bit key and SHA-1 produces 160 bits of output. SHA-1 is therefore acceptable for generating up to 80 bit keys. AES (Advanced Encryption Standard) is capable of using a 128, 192, or 256 bit key. You would therefore want to use SHA-256, SHA-384, or SHA-512 to generate your key.