IBM®
Skip to main content
    Country/region [select]      Terms of use
 
 
      
     Home      Products      Services & solutions      Support & downloads      My account     

developerWorks > Security >
developerWorks
Protecting passwords: Part 2
e-mail it!
Contents:
Password authentication
Password selection
More advice
Throwing dice
Passphrases
Application-selected passwords
Conclusion
Resources
About the authors
Rate this article
Subscriptions:
dW newsletters
dW Subscription
(CDs and downloads)
Authenticating users

Gary McGraw (gem@cigital.com), Cigital
John Viega (viega@cigital.com), Cigita

01 Sep 2000

In the previous installment we introduced the concept of passwords as a pervasive authentication mechanism. We pointed out some of the problems inherent in storing passwords and provided an example program for password storage. In this installment, we turn to the meat of password systems -- authenticating users.

Password authentication
The steps to take to authenticate a user based on a password seem simple:

  1. Read the username
  2. Figure out the salt used to encrypt the original password
  3. Read the password, turning echo off 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

The following code sample is a simple program that implements the algorithm above. Click here to see sample code.

We've been careful not to fall into any of the traps we fell into when writing the original password-storing program from the previous installment. Nonetheless, there is a new problem with the code sample above -- no security conscious action is taken when a user tries to log into an account but fails to do so!

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 they want to break into. It is almost as bad as if they had a copy of the hashed password. What we have created is not a password system, but a delay mechanism.

One thing we can do is to lock the account after a 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 users 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, or similar information?

The best approach is to have the people provide the 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 about 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 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 will need to be reset every time a valid login occurs. This introduces the risk that an attacker will get to try 49 passwords every time the valid user logs in (then counting 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.

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 that's not the case. People pick things that are easy to remember. That fact can narrow down the effectiveness of passwords tremendously. There are several programs, such as Crack, 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, and 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 also can be remarkably effective when you know the person whose password you are trying to guess. It is definitely 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 informed, and must choose another password.

The software can also give the user recommendations for choosing good passwords. That is an O.K. idea, but it often backfires if your suggested process isn't absolutely excellent, because if you give people a process to use, they are likely to follow it. Consequently, people will pick passwords that look well-chosen, but are not. For example, we have seen programs give the following advice:

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

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

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 your mother's initials). For example: 033156!glm

That's a much better password than "good!advice" was. It might have been an O.K. password, except that passwords chosen by people using your program are bound to look very similar. Crack programs will adapt to check passwords that are constructed using this technique. While they're at it, they'll 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, "I am Ozymandius, king of all kings!", and use the password: IaO,koak!

This advice can easily be followed, and is a lot harder to attack than the last two pieces of advice. Of course, some people will get lazy, and steal your quote. You need to make sure to reject it. People who know the source of the quote might be led to quotes that an attacker might guess if they know your advice. For example, you might choose another quote from the same poem, or by the same author. Or you might 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. They are also likely to take the entire contents of Bartlet's Quotations, and generate the matching password for each quote, adding those passwords to their dictionary of passwords to try. They will also take, say, 20 reasonable modifications of the algorithm and generate those passwords, too.

You are much less likely to accidentally suggest a poor password 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 their first choice. For example:

  1. Enter new password: viega
  2. Can't accept: that's your user name.
  3. Enter new password: john
  4. Can't accept: it's an easily guessed word.
  5. Enter new password: redrum
  6. Can't accept: I read the Shining, too.
  7. Enter new password: dk$
  8. Can't accept: That password is way too short.

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.

It is reasonable to combine these two techniques. First, let the user try a few passwords, and 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 might want to choose from a set of suggestions, and provide one or two at random.

More advice
Sometimes it is actually better to give generic advice, without password examples. Here are some suggestions you might want to make:

  • 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 might be found in a dictionary, names book, on a map, etc.
  • Consider incorporating numbers and punctuation into your password.

Note: 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 can 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 the chart below. 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.

For example, let's say we begin throwing dice,and roll a four, a six, and a one. For our first character, we would use a "#". If the roll does not show up in the chart below, then we have to roll again. That should happen a bit more than once every 10 throws, on average. On the off chance that 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 eight times (fewer than 53 bits of security). We recommend at least 10 letters (about 64 bits). As we mentioned in our previous article, 20 rolls should provide adequate security for any use (about 128 bits).

First dieSecond dieThird dieCharacter
1 or 211a
1 or 212b
1 or 213c
1 or 214d
1 or 215e
1 or 216f
1 or 221g
1 or 222h
1 or 223i
1 or 224j
1 or 225k
1 or 226l
1 or 231m
1 or 232n
1 or 233o
1 or 234p
1 or 235q
1 or 236r
1 or 241s
1 or 242t
1 or 243u
1 or 244v
1 or 245w
1 or 246x
1 or 251y
1 or 252z
1 or 253A
1 or 254B
1 or 255C
1 or 256D
1 or 261E
1 or 262F
1 or 263G
1 or 264H
1 or 265I
1 or 266J
3 or 411K
3 or 412L
3 or 413M
3 or 414N
3 or 415O
3 or 416P
3 or 421Q
3 or 422R
3 or 423S
3 or 424T
3 or 425U
3 or 426V
3 or 431W
3 or 432X
3 or 433Y
3 or 434Z
3 or 4350
3 or 4361
3 or 4412
3 or 4423
3 or 4434
3 or 4445
3 or 4456
3 or 4467
3 or 4518
3 or 4529
3 or 453`
3 or 454~
3 or 455!
3 or 456@
3 or 461#
3 or 462$
3 or 463%
3 or 464^
3 or 465&
3 or 466*
5 or 611(
5 or 612)
5 or 613_
5 or 614-
5 or 615+
5 or 616=
5 or 621{
5 or 622[
5 or 623}
5 or 624]
5 or 625|
5 or 626\
5 or 631:
5 or 632;
5 or 633"
5 or 634'
5 or 635<
5 or 636,
5 or 641>
5 or 642.
5 or 643?
5 or 644/
5 or 645SPACE
5 or 646TAB
5 or 65 or 6AnythingRoll again

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 them. The argument goes that if you have it written down, then someone might find it and read it. Yes, that is certainly true. However, if you do not write it down, then you have to choose something that is easy to remember. If it is easy to remember, it will probably be easy for programs like Crack to break. We would much rather see people choose quality passwords and write them down, because we think they are less likely to be compromised that way. There is nothing wrong with keeping a sheet of passwords in your wallet, as long as you maintain control over your wallet, and never leave that sheet lying around.

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 one by Counterpane (see Resources), 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 offload the burden of having to manage multiple passwords. Such a tool is far better than using the same password on multiple accounts.

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

Passphrases
Passphrases are just passwords. There isn't any real difference between the two, except in the obvious meaning of the terms themselves: "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. Often, there is nothing keeping a passphrase from being a single word.

Using a phrase instead of a word is usually a good idea, as they tend to be harder to break. However, phrases can be guessed, too. Programs like Crack could check everything in a quotation book, 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, or removing letters -- 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 five bits of entropy per word. You do a lot better if you choose a string of random words. If you have a dictionary with 8,192 words to choose from, and you choose each one with equal probability, then each word has 13 bits of entropy. If you choose 10 words from this dictionary, you would not have to worry about your password being cracked through brute force.

Much like passwords, you can create high-quality passphrases by rolling dice. The Diceware home page (see Resources) has a dictionary of 7,776 words, from which you can select randomly by rolling dice. Here's 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, such as 62,142. That number is looked up in the Diceware word list, giving one word of a passphrase. Each word you select with Diceware gives about 12.9 bits of entropy; however, you should expect that your passphrase has less entropy if it happens to be a logical sentence, or if it is short enough to be opened by brute force. (The Diceware page recommends a minimum passphrase of five words, and suggests that users throw out passphrases that are 13 characters or shorter. This advice is reasonable).

Application-selected passwords
Of course, it's not very reasonable to make your users do all the dice throwing we have been recommending. You can, though, 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. Below is a function that generates a totally random password. It uses the random library we developed in a previous installment of this column.


char *get_random_password(int numchars)
{
 static char letters = 
 "abcdefghijklmnopqrstuvwxyz"
 "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
 "0123456789"
 "~`!@#$%^&*()_-+={[}]|\\:;\"'<,>.?/";

 char *s = malloc(numchars+1);
 int i;
 for(i=0;i<numchars;i++)
 {
 s[i] = letters[secure_random_int(strlen(letters))];
 }
 return s;
}

Below is code that implements the Diceware technique in software. It generates a random passphrase by choosing from a file called wordlist.dat (see Resources).


char *get_passphrase(int numwords, int ranchar)

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

Click here to see sample code.

Conclusion
Even though authentication is one of the simplest concepts in computer security, it's one of the hardest to get right. Today, we've just scratched the surface. In future installments, we will look at other authentication techniques you can use in software, such as public-key authentication and biometric authentication.

Resources

  • In Part 1 of this series, Gary and John focus on the challenges associated with storing passwords.

  • See Software strategies, Gary and John's article on how to devise a reasonably secure random number generator through software.

  • Find out more about reliable encryption technologies in Tried and true encryption.

  • Visit the MD5 algorithm implementation.

  • Find out more about password safes at Counterpane.

  • Visit the Diceware home page for a dictionary of high-quality passphrases.

  • See the wordlist.dat file.

  • The developerWorks columns by Gary and John have been updated and expanded in the book Building Secure Software, which also includes plenty of new material. Pick up a copy today -- your users will thank you.

About the authors
Gary McGraw is the vice president of corporate technology at Cigital (formerly Reliable Software Technologies) in Dulles, VA. Working with Consulting Services and Research, he helps set technology research and development direction. McGraw began his career at Cigital as a research scientist, and he continues to pursue research in software engineering and computer security. He holds a dual Ph.D. in Cognitive Science and Computer Science from Indiana University and a B.A. in Philosophy from the University of Virginia. He has written more than 40 peer-reviewed articles for technical publications, consults with major e-commerce vendors including Visa and the Federal Reserve, and has served as principal investigator on grants from Air Force Research Labs, DARPA, National Science Foundation, and NIST's Advanced Technology Program. He can be reached at gem@cigital.com.


John Viega is a senior research associate, Software Security Group co-founder, and senior consultant at Cigital. He is the principal investigator on a DARPA-sponsored grant for developing security extensions for standard programming languages. John has authored over 30 technical publications in the areas of software security and testing. He is responsible for finding several well-publicized security vulnerabilities in major network and e-commerce products, including a recent break in Netscape's security. He is also a prominent member of the open source software community, having written Mailman, the GNU Mailing List Manager, and, more recently, ITS4, a tool for finding security vulnerabilities in C and C++ code. Viega holds an M.S. in Computer Science from the University of Virginia. You can contact him at viega@cigital.com.



e-mail it!
Rate this article

This content was helpful to me:

Strongly disagree (1)Disagree (2)Neutral (3)Agree (4)Strongly agree (5)

Comments?



developerWorks > Security >
developerWorks
  About IBM  |  Privacy  |  Terms of use  |  Contact