13. Password Authentication

Kyle: What’s the password?
Gregory: Uh, I don’t know.
Kyle: Guess!
Gregory: Uh, bacon.
Kyle: Okay.

—SOUTH PARK: BIGGER, LONGER AND UNCUT

This chapter presents a discussion of the most popular form of authentication—the password. Some security experts argue that passwords do not make for good security. We agree that’s usually the case, but passwords can be a highly effective supplement to other kinds of authentication. In practice, the question is moot. Disagreement by all the security experts in the world cannot kill the password. The fact of the matter is that passwords are likely to be used for many years to come, because they seem very simple.

In Chapter 3 we discussed different kinds of authentication technologies, including biometrics, cryptographic authentication, and password authentication. As we say there, we believe the only proper way to do authentication is to use multiple forms of authentication at once. Nonetheless, the password is certainly the most important category of authentication to be familiar with, if only because its use is so widespread. Almost everyone who has used a computer in the 1990s knows what a password is. For better or for worse, username/password pairs are the most popular method for authenticating users. The underlying premise of passwords is that the user and an authenticating agent (for example, the user’s machine) share a secret—the password. When it comes time to authenticate, the user types the password. If it matches the one stored by the authenticating agent, the connection is approved.

Like many security technologies we have discussed, the idea is simple and elegant, but getting everything exactly right is harder than it first appears. In this chapter we focus on the problem of storing passwords and authenticating users with passwords. Both of these things are a lot harder to get right than you may think!

Password Storage

The first hurdle to overcome in any password system is the privacy problem. Most people don’t want other people to be able to read (or use) their passwords. If your code stores someone’s password in plaintext, it can be read at will. Even worse, if your security isn’t absolutely perfect, other people can read the password too.

So how can we solve these problems? Some administrators say, “Trust us. . . . we won’t read your password unless you need us to do so.” Of course, there is no reason to believe that. In any case, even if the people running the service are telling the truth, they may be forced to reveal your password by a court of law. But let’s say that’s fine with you; you trust the organization running the authenticating agent. The question then becomes one of what they are doing to protect your password from attackers.

One solution is to encrypt your password. This solution is nontrivial though. To encrypt and decrypt your password, a key is required. This transforms the question from a password storage problem into a password key storage (and use) problem. Of course, the authenticating software needs the password key to be able to validate you when you log in. We don’t want our authentication software to require human intervention if we can help it, so the key probably needs to sit somewhere that our software can access it. The problem is that if the software can access it, a successful attacker can too. Our goal thus becomes finding a way to make the cryptographic key as hard as possible to find. This is a form of “security through obscurity,” which is a practice to avoid if at all possible. It turns out that hiding keys isn’t a very easy problem anyway. (We discuss key hiding in Chapter 15.)

Fortunately, there is a better way. In fact, that better way not only removes the key storage problem, it also solves the password storage problem too. In a nutshell, the authenticating entity in our solution stores and uses a cryptographic hash of the password.

Here’s what happens when a user types in the password. The password gets sent to the authentication agent, which hashes it, and compares the hash with its stored hash. If the two hashes are the same, authentication succeeds. Now the authenticating entity no longer needs to hold on to the plaintext password. But that doesn’t mean the machine can’t hold on to it. We’ve said that the authenticating agent performs the password check. We implied that the agent then “forgets” the password. A hostile administrator could hold on to it, maybe in a secret file of users’ passwords. Maybe an attacker could gain access to this file. Or maybe the administrator is an attacker. There’s obviously no need for the administrator to compromise the system in question, given the access we expect an administrator to have. The problem is that lots of people tend to use the same passwords on different machines to make their lives less complicated. Any smart attacker will try your old passwords on new accounts before trying anything else. Next, an attacker will try variations on your old passwords. There are some complex solutions to this problem (we can use public key cryptography, for example), but for today, we fall back into trusting the administrator and the authentication system.

One common implementation of a hash-based password storage mechanism is the POSIX crypt() call. The crypt() call doesn’t technically perform a one-way hash. It encrypts a string of zeros using a modified version of DES that essentially uses your password as an encryption key. In practice, this works out to be functionally the same as a one-way hash. The only person who should be able to produce the key that will produce the same ciphertext when encrypting all zeros is the person who legitimately knows the password. Unlike cryptographic hash functions such as MD5 and SHA-1, which can operate on arbitrary length strings, the crypt() call is pretty limited. It can only handle passwords of length 8 or less. If you have a 12-character password, only the first 8 characters really matter. The crypt() call ignores everything after 8. There are 95 different characters that can go into a password.¹ This means there are less than 2⁵³ unique passwords. This sounds like a pretty big number (multiple trillions), but it’s not that large in cryptographic terms. Let’s assume for a second that every password maps uniquely to a single piece of ciphertext. With a few hundred terabytes of storage, we could store every possible password and ciphertext pair, and look them up in a hurry. We’d need to precompute all the data, but we’d only have to do it once. With pretty reasonable resources, this may only take a year. A large enough organization could probably get it done in a few weeks at worst. When crypt() was designed, this kind of an attack (called a dictionary attack) was foreseen. People didn’t expect that ever making a complete, usable dictionary would be possible, even though these days it is. What they expected was that particular passwords would be very common (for example, dictionary words, proper nouns, and the like). To prevent a common database of passwords from being created, a step was added to the crypt() process. The string of zeros isn’t directly encrypted using your password as a key. What happens is that a 2-byte “salt” is chosen. A salt is basically some random, but completely public, data. Anybody can see what the salt is. The salt is concatenated to the password to create a key. In this way, when the same password gets put through crypt multiple times, it always encrypts to a different string (assuming you always get a different salt). In the case of crypt(), the salt is also used to modify DES, so that standard DES crackers can’t be used.

1. Actually, you can stick 128 different characters in a password programmatically. There are only 95 printable characters. Usually, you can input some control characters from the keyboard.

There are only 64 unique characters that can be used in the seed for the salt, and the seed can only be 2 bytes. Therefore, there are only 4,096 different seeds. This makes a comprehensive dictionary attack approximately 4,000 times harder (and approximately 4,000 times more space intensive). Under the salt approach, the space of possible keys (the key space) goes up from approximately 2⁵³ to 2⁶⁶. When crypt() was originally written, that was a huge key space. These days, it isn’t so big, especially given that the seed should be considered compromised. The seed is generally saved with the ciphertext because it is commonly assumed that an attacker is somehow able to get that text anyway. Unless the password database is made unreadable to all except those with special privileges, getting to the text is usually do-able.

It is important to try to protect the ciphertext. Once someone has it, he or she can try all 2⁵³ passwords, and will eventually find the password that encrypts to the given text. Many people believe that the government has the computational resources to perform such a crack in a matter of minutes, or perhaps even seconds. A brute-force attack is definitely within the reach of an organization with reasonable resources. Storing a full dictionary for every possible password with every possible salt would take a few million terabytes of disk space, which is currently possible, but only at an extraordinary cost. In a few years, it’s likely to be a more practical approach. Without a precomputed dictionary, it’s not too hard to get machines that can try on the order of 2¹⁸ different passwords per second. A sizable effort distributed across 8,000 or so machines of this quality would be able to crack absolutely any password in no more than 48 days. Of course, most passwords fall in a small set of a few million, making them much, much easier to crack. Note that these numbers pertain to precomputing every password and its crypted value, given a single salt, so it would actually take a massive amount of computing power to build a precomputed dictionary with all salts—somewhere in the scope of a decade.

We discuss desirable sizes for key spaces in Appendix A. Our preference lies with a key space of 128 bits or better. With passwords, this level of security would be nice. The problem is that the more bits of security you want, the longer passwords have to be. And people want shorter passwords, not longer ones. You would need to have a 20-character password, each character randomly chosen, to get 128 bits of security. That is way too many characters for most people. Plus, those characters each need to be completely random. Most people unfortunately tend to pick poor passwords, so that an attacker only has to search a small fraction of the space before finding a password.

Adding Users to a Password Database

Let’s consider the problem of adding a user to a file-stored password database in C (we cover authenticating the user in a bit). We assume that the user in question is sitting in front of the computer, and we can read the user’s input from standard input. First, let’s look at naive implementations with several problems. We discuss these problems and refine our program to fix them.

Here’s a program that adds a new user to a UNIX-style password database. You should change the value of PW_FILE as appropriate, and run touch on that file before using this program. Remember that this example code has some problems, so don’t use it in any production systems:

Now that we have something to talk about, we can turn to the question of what’s wrong with the previous code. The answer? Plenty. The most obvious thing is that when we run the program, the password gets echoed to the screen. We can fix that by adding an echo parameter to the read_line function, and then use the ioctl system call to cause the terminal attached to stdin to refrain from echoing if the parameter is set to zero. (We should also check to make sure there is a terminal connected to stdin. If input to the program is piped in, there won’t be.)

A second problem is that we’re misusing the crypt library. It’s fairly common to see crypt(pw, pw) in code. Unfortunately, this is very bad practice. The problem is that the seed is the first two characters of the password. The seed must be stored in the clear. Therefore, anyone who can see the password database only has to guess six characters instead of eight. Crack programs will find a break much more quickly. Plus, we’ve given up all the benefits of having a seed. All users who have the password “blah” will have the same encrypted password: blk1x.w.IslDw. A stored dictionary attack is a very feasible attack on most passwords in this case (storing several million of the most likely passwords only takes up a few dozen gigabytes of disk space). We really need to be selecting a random seed. Because the seed is public, it doesn’t actually matter much if we use “secure” random number generation to pick a seed. PRNGs seeded on the clock are okay for this purpose. The risk is that an attacker can have some influence on the random number, causing the seed selected to be more likely to be one for which the attacker has done extensive precomputation. In practice, this attack is far more theoretical than practical, because most crack programs are highly effective without ever needing to precompute anything. Still, we may as well play things safe and get our numbers from a reasonable random number source. For our example, let’s use the Linux-based random number library we developed in Chapter 10, but compromise by using “strong” random numbers that may not be 100% secure.

The third problem with the previous code is that we should be more paranoid about leaving around plaintext passwords for any longer than necessary, even in memory we control. Sometimes attackers will have access to a program’s memory as it runs, or may be able to force a core dump that can later be examined to reclaim the password. We should try to minimize these windows of vulnerability by minimizing the amount of time in which the password is stored in an unencrypted format. As soon as we read in the password, we should encrypt it, then “zero out” the memory containing the password. Even when we compare to make sure that two passwords are equal, to confirm that the user typed in the right password, we should compare them based on the resulting ciphertext, not based on the plaintext.

Also, we should make sure that the user’s password never gets saved to disk, even if the program swaps out. We can accomplish this easily with the mlock() system call, which makes sure a memory range stays locked in RAM. It takes two parameters: a pointer to a memory address and the number of bytes to lock. To undo the effects when the password has been erased from memory, use munlock(), passing the exact same arguments. Unfortunately, mlock() and munlock() can only be run by root. The risk of passwords being swapped out and read from there is probably minimal compared with setuid problems, if you’re careful about erasing passwords immediately after use.

A fifth problem is accessibility of the database. The user running this program must be able to read and write the database. This is not really a great idea in most cases. We’d even like to prevent anyone other than the program from reading the database if possible. If logins are coming in over the network, instead of on the local machine, it’s less likely that people will be able to read and modify the database. But if there’s an exploitable stack overflow, or some other problem that the attacker can leverage to run code, then mucking with the database is certainly not impossible! In the UNIX world, the answer to this problem is to use setuid programming. Setuid programming comes with its own set of risks, and is a complicated topic. For now, we’ll leave our code broken in this respect.

Based on our newfound insight, here’s a mostly fixed version of the example program (note that we don’t use mlock and munlock):

Of course, we still don’t like crypt() because it limits passwords to eight characters, and it limits the number of salts we can have. We could provide a replacement version of crypt that uses SHA-1 and the base64 code from the previous chapter (to convert the binary to something we can easily store):

This function has slightly different behavior from standard crypt, because the salt is a variable length. In particular, it is not valid to say sha1_crypt(typedpw, storedpw). With traditional crypt this kind of code is okay, because only the first 2 bytes of the second parameter are considered. Unfortunately, sha1_crypt could never distinguish a salt with a postpended SHA-1 hash from a salt alone, because the salt isn’t a fixed size, even if the salt were placed before the hash. Unlike traditional crypt, we place the salt after the hash, so that we can easily call sha1_crypt when checking a password.

When using a hash algorithm for storing passwords, people tend to look for something easier to implement than a randomly selected salt. The username seems like a good choice, but it is insufficient, because one purpose of the salt is to mask when someone has the same password on different machines. However, there is certainly no harm concatenating the username to the salt, because it further reduces the probability of a collision.

Password Authentication

Authenticating a user based on a password seems simple:

1. Read the username.

2. Figure out the salt used to encrypt the original password.

3. Read the password, turning off echo on the input.

4. Run crypt on it using the stored salt.

5. Wipe the memory in which the password was stored.

6. Check the two crypted strings for equality.

Here’s a simple program that implements the previous algorithm:

We’ve been careful not to fall into any of the traps we fell into when writing the original broken password-storing program. Nonetheless, there is a new problem with the previous code—no security-conscious action is taken when a user tries to log in to an account but fails.

Sure, the program stops after three bad login attempts. But so what? People can just run the program over and over again. As a result, attackers have unlimited time to try to guess the password of accounts into which they wish to break. It is almost as bad as if they had a copy of the hashed password. What we have created is not a password system, it’s only a delay mechanism.

One thing we can do is to lock the account after some fairly small number of bad login attempts (say five). Users should then be forced to interact with an administrator or customer support to get their account unlocked. A complication with this scheme is that it is difficult to authenticate a user when they go to get the locked account unlocked. How does one know it is not an attacker who happens to know a target’s social security number, and so forth?

The best way is to have the person provide their actual password. The problem is obvious: How do you distinguish people who genuinely can’t remember their passwords from attackers pulling a social engineering attack? An attacker will surely say, “I can’t remember my password!” over the phone, once the lockout number has been exceeded. One mitigation measure is to record when login failures occur. Automated attacks can cause many failed attempts within a single second or two. Another thing to do is to set the number of attempts before locking the account at approximately 50. If the user has actually forgotten the password, the user is unlikely to try 50 different passwords. A much more likely approach is to try to call customer support. Therefore, if the threshold of 50 is reached, then an attack is fairly likely, and you should expect the customer to be able to provide an actual password.

Obviously, a bad login counter needs to be reset every time a valid login occurs. This introduces the risk that an attacker gets to try 49 passwords every time the valid user logs in (then counts on the user to provide 49 more magic guesses). With a well-chosen password, this would not be too much of a problem. However, considering that users tend not to choose good passwords, what can be done? We recommend keeping track of bad login attempts over the long term. Every time a global counter gets above 200, make the user change the password in question. All counter information can be stored in the unused fields of the password file.

The problem with this technique is that an attacker can launch a deliberate denial-of-service attack by guessing the password incorrectly, thus locking out a legitimate user. If this becomes a problem, there are many possible solutions, such as a two-password login, the first of which does not have a lockout.

Password Selection

Everything we’ve said so far assumes that when a person selects a password, all possible passwords are equally likely. We all know this is not the case. People pick things that are easy to remember. This fact can narrow down the effectiveness of passwords tremendously. There are several programs, such as Crack (see this book’s companion Web site for links), that help an attacker try to guess passwords intelligently. Of course, we also have images from movies of “hackers” sitting down, and trying to guess someone’s password. They always seem to be able to do it fairly quickly. In reality, such a person would use Crack, or a similar program, instead of trying to guess from scratch. However, guessing can also be remarkably effective when you know the person whose password you are trying to guess. It is unfortunately common to be able to guess other people’s passwords in just a couple of tries!

Many software systems force the user to provide a password that meets basic quality standards. After a user types in a password, the software checks the quality of the password, and if there is a problem with it, then the user is told and must choose another password.

Optionally, the software can give the user recommendations for choosing good passwords. This is an okay idea, but it often backfires if the suggested process isn’t absolutely excellent, because if you give people a simple pattern to use, they are likely to follow it too closely. Consequently, people will pick passwords that appear to be well chosen, but are not. For example, we have seen programs give advice similar to the following:

Take two words that are easy for you to remember, and combine them, sticking punctuation in the middle. For example, good!advice.

This advice is not very good, actually. Most password-cracking programs including Crack itself try this kind of pattern, and ultimately break the password. Let’s try some slightly better advice:

One suggestion is to use a date that is important to you (maybe your mother’s birthday), and then combine it with a piece of punctuation and some text that is easy to remember, such as mom’s initials. For example, 033156!glm.

This is a much better password than good!advice. It may have been an okay password, except that passwords chosen by people using your program are bound to look very similar. Crack programs adapt to check passwords that are constructed using this technique. While they’re at it, they swap the orders of each piece.

Let’s look at some advice that’s even better:

Take a sentence that you can easily remember, such as a famous quotation or a song lyric. Use the first letter of each word, preserving case, and use any punctuation. For example, you may choose the quote “My name is Ozymandius, king of kings!” and use the password MniO,kok!

This advice can be easily followed, and is a lot harder to attack than the preceding two pieces of advice. Of course, some people will get lazy and steal your quote. You need to make sure to reject passwords that are obvious from the advice. People who know the source of the quote may be led to quotes that an attacker may guess if the attacker knows your advice. For example, you may choose another quote from the same poem, or by the same author. Or, you may choose another quote from poetry that is at least as famous, such as “Two roads diverged in a wood.” Attackers can make a list of probable candidates. For example, they may take the quotes from the top of each of our chapters. They are also likely to take the entire contents of Bartlett’s quotations and generate the matching password for each quote, adding those passwords to their dictionary of passwords to try. They may also take, say, 20 reasonable modifications of the algorithm and generate those passwords too.

You are much less likely to suggest a poor password accidentally by not trying to tell the user what process to go through when choosing a good password. Instead, just tell the user why you don’t like his first choice. For example,

The biggest problem here is that naïve users will not necessarily figure out how to pick better passwords. We have seen smart people (yet naïve users) sit there for 10 minutes trying to figure out a password the system will accept, eventually giving up in frustration.

A reasonable strategy is to combine these two techniques. First, let the user try a few passwords. If you do not accept one, say why. After a few failures, give a piece of advice. Just be careful about the advice you hand out. You may want to choose from a set of advice, and provide one or two pieces at random.

More Advice

Sometimes it is actually better to give generic advice, without password examples. Here are some pieces of advice you may wish to give:

• Passwords should be at least eight characters long.

• Don’t be afraid of using a really long password.

• Avoid passwords that are in any way similar to other passwords you have.

• Avoid using words that may be found in a dictionary, names book, on a map, and so forth.

• Consider incorporating numbers and/or punctuation into your password.

• If you do use common words, consider replacing letters in that word with numbers and punctuation. However, do not use “similar-looking” punctuation. For example, it is not a good idea to change cat to c@t, ca+, (@+, or anything similar.

Throwing Dice

Password selection enforcement is a tradeoff between security and usability. The most usable system is one that never rejects a proposed password, even if it is incredibly easy to guess.² There is a great way for people to generate good passwords, but it turns out to be difficult to use. This technique requires three dice. To generate a single letter of a password, roll the dice, and then read them left to right, looking them up in Table 13-1. To avoid ambiguities as to which die is the farthest left, it can help to roll the dice into a box, then tilt the box until all dice are beside each other.

2. Actually, Microsoft’s notorious “Bob” was the most usable, and least secure. After three incorrect guesses, Bob would allow you to change your password.

Table 13-1 Throwing Dice for Passwords

For example, let’s say we begin throwing dice, and roll a 4, a 6, and a 1. For our first character, we would use #. If the roll does not show up in Table 13-1 then we have to roll again. This should happen a bit more than once every ten throws, on average. On the off chance your password looks anything like a real word, start over again.

This technique provides for a completely random distribution of passwords of a given length. At the very least, a user should roll 8 times (less than 53 bits of security). We recommend at least 10 letters (approximately 64 bits). Twenty rolls should provide adequate security for any use (approximately 128 bits).

The problem with this technique is that it is difficult for the user, who not only must roll tons of dice, but must somehow keep track of the resulting password.

By the way, some people recommend never writing down any password, just memorizing it. The argument goes that if you have written down a password, then someone may find it and read it. This is certainly true. However, if you do not write it down, then you have to choose something that is easy to remember. If a password is easy to remember, it will probably be easy for programs like Crack to break it. We would much rather see people choose quality passwords and write them down, because we think they are less likely to be compromised this way. There is nothing wrong with keeping a sheet of passwords in your wallet, as long as you keep good control over your wallet, and never leave that sheet lying around. There are definitely people who disagree with us, however.

One way to store a bunch of account/password pairs without having to worry about losing the paper is to use a password safe (such as PasswordSafe from Counterpane Labs, http://www.counterpane.com, which is an electronic program that encrypts your passwords on a disk). To get at a password, you need only open the safe. Of course, the “combination” to the safe is itself a password. The user has to be able to keep at least one password memorized, but can off-load the burden of having to manage multiple passwords. Such a tool is far better than using the same password on multiple accounts, for example.

Note that no password in the safe can be effectively stronger than the password that unlocks the safe (or the software implementing the safe), because if you can break open the safe, you get all the passwords inside it for free. Therefore, take special care to use good passwords with your safe.

Passphrases

Passphrases are just passwords. There isn’t any real difference, except in the connotations invoked by the term. “Password” encourages users to think short and sweet, whereas “passphrase” is meant to encourage the user to type in a complete phrase. Except when there are arbitrary length restrictions, there is nothing restricting a password from being a phrase. Unfortunately, often there is nothing to keep a passphrase from being a single word.

Using a phrase instead of a word is usually a good idea, because phrases tend to be harder to break. However, phrases can be guessed too. Programs like Crack could check everything in a quotation book, complete with varying punctuation and capitalization. But if you take a pretty long phrase from such a book and make three or four changes, such as word swaps, letter swaps, adding punctuation, removing letters, and so forth, then you probably have something that won’t be broken.

“Probably” is not a very strong word though. Plain old text taken from a book is estimated to have about 5 bits of entropy per word. You do a lot better if you choose a string of random words. If you have a dictionary of 8,192 words from which to choose, and you choose each one with equal probability, then each word has 13 bits of entropy. If you chose 10 words from this dictionary, you would not have to worry about your password being brute forced.

Much like passwords, you can create high-quality passphrases by rolling dice. The Diceware homepage (www.diceware.com) has a dictionary of 7,776 words, from which you can select randomly by rolling dice. Here is how it works. You roll five dice at a time, and read them from left to right. The values are read as a five-digit number; for example, 62142. That number is looked up in the Diceware word list, giving one word of a pass phrase. Each word you select with Diceware gives approximately 12.9 bits of entropy; however, you should expect that your pass phrase has less entropy if it happens to be a meaningful sentence, or if it is short enough to be brute forced. (The Diceware homepage recommends a minimum pass phrase of 5 words, and suggests that you throw out passphrases that are 13 characters or shorter. This advice is reasonable.)

Application-Selected Passwords

Of course, it is not very reasonable to make your users do all the dice throwing we have been recommending. You can, however, do the dice throwing for them. The only caveat is that you need numbers that are completely random. Using rand() to select a random character or a random word from a list just won’t cut the mustard. The following is a function that generates a totally random password. It uses the random library we developed in Chapter 10:

The following is code that implements the Diceware technique in software. It generates a random passphrase by choosing from a file called wordlist.dat (available on the book’s companion Web site). The public interface is

char *get_passphrase(int numwords, int ranchar)

This function returns a random passphrase of the specified number of words. If ranchar is nonzero, then a word is chosen at random from the passphrase, and a punctuation character or number is added at random, adding another 5.5 bits of entropy to the 13 provided by each word in the phrase:

One-Time Passwords

One of the biggest problems with password schemes is that the password tends to be really easy to compromise, even if the user happens to choose something that is hard to guess. In many cases, people send their passwords to other machines in the clear. Even when using passwords with “good” systems such as SSH, man-in-the-middle attacks are easy to launch and can be used to intercept passwords.

One-time passwords solve this problem. The idea is that the user and the server share some secret that is used to compute a series of single-use passwords. There are plenty of strategies to do this, all relying on cryptography. The user typically carries some physical token to help him or her authenticate. Examples include a piece of paper with the next 100 passwords, a small device that serves only to calculate passwords, or even a Palm Pilot.

Probably the most popular one-time password technology is SecurID, a commercial solution available from RSA Security at http://www.rsasecurity.com (shown in Figure 13-1). The form factor for the user is one of several types of physical devices. The simplest merely provides an LCD (Liquid Crystal Display) that shows the next password to use. Every 60 seconds, the value on the LCD changes. SecurID calculates its one-time passwords through a cryptographic mechanism that takes into account the current time and the rightful owner of the physical token. When a user logs in to a system (or enters a door protected with SecurID), he types in the password currently being displayed. In most cases, the user also types in a PIN. This strategy is great. It provides defense in depth, keeping casual thieves from getting far if they steal the physical device.

Figure 13-1 SecurID, from RSA Security.

Most other systems are based on challenge/response. The server provides a challenge and the user provides a response to that challenge. SafeWord, from Secure Computing (http://www.securecomputing.com/), is a popular commercial technology in this category.

Free solutions do not abound. The only free solutions widely used are ancient. All such solutions are based on S/Key, the original one-time password technology. The passwords were written in a day when people with access to the server were always trusted, and have not been updated for modern security requirements. S/Key vulnerabilities have been uncovered during the past few years, and more are believed to exist.

An additional problem with S/Key-based systems is that they were generally applied only to technologies that were fundamentally flawed anyway. For example, there are several implementations of one-time passwords for TELNET. Although it is true that there is no harm in sending a one-time password over the network unencrypted, it doesn’t provide much of a hurdle for attackers. An attacker can just wait for a TELNET session to establish, and then hijack it (tools like dsniff can help automate this attack).

S/Key security also ultimately relies on a password. The user types in a password, which is used to generate a sequence of one-time passwords. The one-time passwords are created by continually hashing the password and a seed. The passwords are used in reverse order, to avoid people taking one password and hashing it to get the next. This means that you can only use a finite number of passwords on which you need to agree at first use. When you’re done with those, you need to reseed the calculator (or get a new password list). This is somewhat inconvenient, especially when using a calculator.

Because this scheme is still password based, you can use Crack-like programs to attack it quite easily if you ever see a single password/challenge pair. Another effective attack against this system is an “over-the-shoulder attack,” during which someone watches you with your slip of paper as you type in a one-time password. For this reason, you’re better off using a calculator if possible.

We probably wouldn’t use S/Key in any production system without reimplementing it. Also, because S/Key has some usability problems (such as ultimately relying on a password), we probably wouldn’t use it anyway. Here we describe a simple way to do one-time passwords that you can use in your systems at no cost. It circumvents all of the problems we’ve discussed with S/Key so far.

This one-time password scheme uses a simplified version of the Yarrow random number generator. This generator requires a key and a counter. The nth random number is output by setting the counter to n, then encrypting it with the key.

The server obtains a key by reading random data from /dev/random. The key is then either installed in the calculator, or you can ask the code to give you the user’s next m passwords. Ultimately, it would be best to do the key generation on a machine that’s off-line, and install it on the server.

When it comes time to authenticate, the server generates a challenge. This code has the server always increasing the challenge by one. To prevent over-the-shoulder attacks, you may want to change our approach to skip around in the m passwords you’ve given to a user, and then only use some of those passwords.

The key and the passwords are all mapped to a series of 4,096 words. Each word holds up to 1.5 bytes of information.³ For example, a 128-bit key may be

3. We don’t use the modified Diceware word list because the thirteenth bit of information encoded is an odd-man out. It won’t save us any space, and makes encoding and decoding a bit more complex.

unite redly holds text shave rein sled odor demo wetly bred

The challenges are simply numbers. The one-time passwords are strings of words that encode 64 bits of information. For example, the valid response to the challenge of 100 using the previous key is as follows:

makes holly maker roved molar pouch

This technique should be safe for generating at least 2³² one-time passwords, assuming the calculator and the server never get compromised. This should be more passwords than people ever need with a single account. Also, you’re probably fairly safe only using the first two or three words for the one-time password, and ignoring the rest. This would require slight modifications to the code. Using only two words, the attacker would have a 1 in 12 million chance of guessing the correct password. Plus, if the cryptography is secure, no one password should give away information about others. Therefore, we really would expect an attacker to have to guess at least six million times before succeeding, on average. If we force account lockouts after a number of bad passwords, we should not have much fear of such an attack.

This code definitely needs to be tailored to suit your needs. It is incomplete in several ways. For example, it is not a complete application. There is no socket code on the server. Also, neither the client nor the server is persistent. They really should save information to disk, preferably in an encrypted format. On the client, you could use a PIN as a key to encrypt the information (this would likely be the weakest point of the system). A final issue is that we only represent keys and passwords as words. S/Key allows you to represent them as hex strings as well. Doing this, or allowing data to be represented as base64-encoded strings, would be a useful extension.

First, let’s look at the code that translates binary, byte-aligned data into a string of words. Here’s the interface:

Both word_encode and word_decode allocate their results using malloc. word_encode also adds padding characters (in this case, the equal sign) to the end when the length of the input is not a multiple of 3 bytes. The word_decode function requires the padding to be there to operate properly. We always end up with padding because we are encoding either a 128-bit key or a 64-bit counter. What we end up doing is stripping off padding before presenting a string to the user. We then add it back on when it comes time to decode.

The following is wordencode.c. It keeps a table of 4,096 words. If you’re concerned with keeping a large number of words in memory, you could stick solely with a hexadecimal translation or use a smaller table of words, and just require more words for representing the same number of bits. We’ve elided most of the word list for space; the complete source code can be found on this book’s companion Web site.

The one-time password code is broken into three parts: common functions between the server and the calculator (otp-common.c), server-side code (otp-server.c), and client-side code (otp-client.c). There is a header file, otp-common.h, that exports the common interface:

The function generate_raw_response produces the correct response as a 64-bit unsigned integer, given a key and a challenge. Here, we use the Blowfish algorithm, for the sake of simple implementation. You may want to consider switching to AES (which wasn’t in OpenSSL at the time of this writing) or to Triple DES. The generate_response function does the same thing, except returns the result as a string that it allocates using malloc. Note that this code requires the use of the OpenSSL library. Here’s the code:

The server code gives you functionality for creating (although not saving) new users, generating challenges, checking responses, and printing a list of the m next one-time passwords for a user (which would be useful for people not using calculators).

The calculator code has a notion of multiple accounts with a unique key for each account. Otherwise, it just relies on the functionality in otp-common.c.

Conclusion

Password authentication is full of tradeoffs. It’s difficult to walk the fine line between usability and security. In general, usability dictates having a shoddy password scheme that is easy for technical support to reset. This seems to be a good-enough solution for most organizations. Hopefully, the ubiquity of personal digital assistants will make one-time password schemes more practical in the future. Another promising prospect is to use a regular password along with a smart card, because some companies are working to make smart card readers ubiquitous.