Considerations for Passwords in Secure Systems

Introduction

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.

A Little History of Password Usage

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.

The TENEX Password Bug

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.

Problems With Passwords in Smart Cards

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.

Securing the Password File

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.

An Example of Using a Hashed Password System

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:

  • When a user creates his or her password, the password is hashed and the hash is stored in the password database
  • When a user attempts to login, the password entered at the login terminal (the trial password) is hashed
  • The hash of the trial password is compared with the password stored in the password database
  • If the two hashes are identical, we assume the user entered the correct password.

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:

  1. Prompt the user for a password.
  2. Generate a random salt (i.e.- a random string of bits.)
  3. Prepend the salt to the password.
  4. Hash the salted password.
  5. Store the salt and the salted password in the password database.

The process of checking the password is now:

  1. Retrieve the user's salt from the password database.
  2. Prompt the user for a password.
  3. Append the password to the salt.
  4. Hash the salted password.
  5. Compare the result from step 4 with the salted password in the password database.

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.

Generating Keys From Passwords

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:

  1. Generate a random salt.
  2. Append the salt to the user's password.
  3. Hash the salted password.
  4. Hash the hash of the salted password.
  5. Repeat step four some fixed number of times.
  6. Use the resulting hash as an encryption key to encrypt a message.
  7. Prepend the salt and iteration count (the number of times you hashed the hash) to the encrypted message.
  8. Store or send the message.

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:

  1. Recover the salt and iteration count from the beginning of the message.
  2. Prompt the user for the password.
  3. Append the salt to the password.
  4. Hash the salted password.
  5. Hash the previously generated hash until you have hashed N times (N being the iteration count from the message header.)
  6. Use the resulting hash as a key to decrypt the message.

What Hash Algorithm Should I Choose?

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 was considered a good choice until very recently. SHA-256, SHA-384, and SHA-512 are probably better choices for new applications.

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.

Best Common Practices for Software Developers

  • Do not store passwords "in the clear."
    • Store a salted hash of a password in the password database.
    • Choose a reputable hash algorithm such as SHA-256, SHA-384, or SHA-512 when producing the password hash.
  • Consider creating a system that supports multiple hash functions. Support an administrative interface that allows the system management staff to disallow the use of a particular algorithm if it is "broken."
  • Only consider storing passwords "in the clear" if there is a clear performance penalty with using hashed passwords and the passwords are stored in a physically secured tamper-resistant memory module.
  • Require the user to assign a new password when an account is created. Do not use default passwords for new accounts.
  • Support an administrative interface that allows system management staff to require passwords to:
    • have a minimum number of upper case letters
    • have a minimum number of lower case letters
    • have a minimum number of digits
  • Consider checking user supplied passwords against a dictionary of common words. If a user's password is a common word, alert the user that the password may not be secure.
  • If you check passwords against a dictionary of common words, support an administrative interface that allows system management staff to add new common words or new dictionaries against which passwords are checked.
  • After accepting a password from a user, then salting and hashing it's contents, write over the buffer that stored the password with zeros.
  • If you need to cache a password, cache the salted hash of the password and not the password itself.
  • If you need to create a symmetric encryption key from a pass-phrase, use a password based encryption algorithm such as described in PKCS#5 or PKCS#12.
    • Choose random salts of appropriate length: 80 bits should be sufficient for most applications.
    • Hash at least 1000 times.
  • For web applications, do not store encrypted passwords in client-side cookies. Consider using some other cookie-based authenticator.

Bibliography

Comments