Password strength

From Wikipedia, the free encyclopedia

Password strength is a measurement of the effectiveness of a password as an authentication credential. The strength of a password is a function of length, complexity, and randomness.[1]

Although passwords serve an essential role in computer security, they must also be reasonable and functional for the end user. Passwords that are too strong will almost certainly be written on paper, which some consider a security risk.[2] In contrast, others argue that forcing users to only remember passwords necessitates weak passwords, and thus poses a much greater security risk. After all, most people are good at securing their wallets or purses, which is a great place to store a written password. [3]

Using strong passwords lowers overall risk of a security breach, but strong passwords do not replace the need for other effective security controls. Risks are posed by several means of breaching computer security which are unrelated to password strength. Such means include: software vulnerabilities, phishing, keystroke logging, social engineering, dumpster diving, etc.

Contents

[edit] Bit Strength

The most common practice of measuring password strength is to measure in terms of "bit strength", which is the same method used to measure the strength of encryption.[4][2] Bit strength simply represents the total number of possible permutations in a password. For example, a password with eight-bit strength has 256 different possibilities.

Passwords are made up of ASCII characters, which include all lower case and uppercase letters, in addition to all numbers and symbols (punctuation included). Although every character on a computer keyboard technically occupies eight bits of space, characters used in passwords never use eight bits of space--they are limited to only 6.5 bits at a maximum.[2]

[edit] Calculating Bit Strength

Bit strength can be calculated by taking the total number of possibilities for each character, and multiplying by the total length. The number of variations per character is contingent upon:

For example, ignoring entropy, a password policy that requires lowercase letters, uppercase letters, numbers and symbols results in 95 variations per character, which equals 6.5 bits. If the password is eight characters long, the bits-per-character is multiplied by the overall length (6.5 x 8) to produce the total bit-strength (52 bits).

[edit] Entropy in Bit Strength

Whereas password policy defines a theoretical limit for the number of variations per character, the science of information entropy is necessary to accurately determine the number of variations per character.

NIST uses the following guidelines for estimating password entropy (ie, randomness)[4]:

  • the entropy of the first character is four bits;
  • the entropy of the next seven characters are two bits per character
  • the ninth through the twentieth character has 1.5 bits of entropy per character;
  • characters 21 and above have one bit of entropy per character;

This leads to findings that in the absence of a password policy, an eight-character password has an 18-bit strength. Yet, even with a password policy that requires at least one number, one symbol, and mixed case, an eight-character password only achieves an estimated 30-bit strength.[4]

[edit] Bit Strength Threshold

Some basic benchmarks have been established for a satisfactory bit-strength to protect against certain types of password cracking. In 1999, an Electronic Frontier Foundation project broke 56-bit DES encryption in less than a day.[5] In 2002, distributed.net cracked a 64-bit key in 4 years, 9 months, and 23 days.[6] Meanwhile, distributed.net estimates that cracking a 72-bit key using current equipment will take about 1,453 years.[7] No currently expected increase in computer power will be sufficient to break 128-bit or 256-bit encryption. Due to currently known limitations in physics, no digital computer is capable of breaking 128-bit or 256-bit encryption.[8] Whether or not quantum computers will be able to do so in practice is still unknown.

As a result, there can be no exact answer for a password strength sufficient to resist brute force attack in practice. Clearly 56-bits is too low, whereas some may find 64-bits acceptable. NIST recommends 80-bits for the most secure passwords, which can nearly be achieved with a 95-character character set (e.g., original ASCII) with a 12-character random password (12 x 6.5 bits = 78).[4]

[edit] Randomness versus Entropy

Random and entropy are often confused, and this difference is important in choosing passwords. A random sequence is one without a pattern, or alternatively without a generating algorithm. For instance, the number pi (3.1415926...) has no discernible pattern, passes statistical tests for randomness, and yet is useless for encryption keys or passwords as it has low entropy. Any particular segment of that sequence is entirely predictable by calculation or lookup of the digits of pi. Entropy in this context requires unpredictability (by an attacker) and pi has none, at least for an enterprising attacker. [9]

People are notoriously remiss at achieving entropy. In one analysis of over 3 million eight-character passwords, the letter "e" was used over 1.5 million times, while the letter "f" was only used 250,000 times. True entropy would have each character being used about 200,000 times. The most common number used is "1", whereas the most common letters are a, e, o, and r.[9]

[edit] Entropy Sources

Several current methods for generating entropy may improve password strength:

  • a pseudo-random number generator (PRNG) is an algorithm, often implemented as a software program, which attempts to implement a random number generator. The quality of these routines has been quite variable, and they are widely thought unsuitable for use in a security context, as for choosing passwords.[10] Computer language library routines are often limited in run length (to perhaps 2^32 or 2^64 values before the sequence repeats), and these are wholly inadequate for security use. RANDU is an infamous, very widely used, and very long-lived, incompetent random number routine for IBM mainframe environments. Some operating system calls (eg, /dev/random (though not /dev/urandom) both from the Linux kernel) are rather better. Many others, however, do not pass muster; for example, Windows 2000 and XP has had a flawed PRNG.[11]
  • a cryptographically secure pseudo-random number generator is a PRNG which is said to be suitable for cryptographic use, that is, for circumstances in which security is important. These are often dependent on hardware sources of entropy, such as a hardware random number generator (audio background noise, hard drive fluctuations, the Intel or VIA CPU randomness circuits, etc). Yarrow and Fortuna are software algorithms for managing such entropy for cryptographic or security use.
  • Internet sites which use some of the above techniques: Random.org (source is atmospheric noise); Hot Bits (source is radioactive decay of Krypton-85);
  • Manual methods of entropy generation are highly unlikely to be adequate (eg, pick a character, pick another character, ...), unless bound to a mechanical system or set of rules (eg, fair dice or the I Ching). Yet, statistical methods for ensuring entropy are quite sound in the negative sense of detecting patterns; although they have historically failed to distinguish between sequences having high entropy and those with merely random appearance. It has been a tricky figure/ground point throughout the history of probability and random number generation. In that light, consider that there are 10 numbers (10.5% of the printable ASCII characters set), 26 uppercase (27.3%), 26 lowercase (27.3%), and 33 symbols (34.7%). If a sequence has this distribution, chances are that it will be a better choice as a password than one without. Thus, a 12-character password with four symbols, three lowercase, three uppercase, one number, in addition to a final character (most likely alphanumeric), would appear to be a reasonable choice.

[edit] Character Selection & Length

One of the components in determining password strength is the set of permitted characters. The printable characters which can be produced on a U.S. English keyboard include 26 letters (all either upper or lower case), 10 numbers, and 33 symbols (i.e., punctuation, grouping, space, etc.). Because several ASCII characters vary between national implementations (at least four, and sometimes seven characters), there are about 88 printable characters which can be used nearly everywhere.[dubious – discuss]

Systems vary in which characters are allowed in passwords: sometimes not all printable characters are allowed. Some systems do not permit case differences (i.e., the upper-case "E" is considered equivalent to the lower-case "e"), others prohibit some of the remaining symbols. The space character is rarely permitted in passwords.[dubious – discuss] In a system password policy, these are alphabetic (upper and lower case), numeric, and 'special' characters.

In the past few decades, systems have slowly permitted more characters in passwords, but limitations are still common. The reason this matters is that brute force and pattern matching password crackers must exert more effort (Shannon used the termed 'work factor') to find a password. For instance, if the allowed characters are only upper case alphabetic, an eight-character password will have 26^8 possible values (38 bits). With 88 allowed characters, the same password will have 88^8 possible values (52 bits), a very much larger number requiring (on average) a significantly more work (perhaps prohibitive) of a successful brute force or pattern-matching attack. In addition, users commonly fail to choose passwords with high entropy (i.e., randomly) and thus make password cracking easier. For example, hacking results obtained from a MySpace phishing scheme in 2006 revealed 34,000 passwords, of which only 8.3 percent used mixed case, numbers, and symbols.[12]

[edit] Guidelines for strong passwords

Common guidelines for choosing good passwords are:[13][14][15][16]

  • Include numbers, symbols, upper and lowercase letters in passwords
  • Password length should be around 12 to 14 characters
  • Avoid passwords based on repetition, dictionary words, letter or number sequences, usernames, or biographical information like names or dates.

[edit] Examples of weak passwords

See also: Password cracking

As with any password, even in the weak category, some are weaker than others. For example, the difference in weakness between a dictionary word and a word with obfuscation (where certain letters in the password are substituted for numbers) may require a password cracking device to work a few seconds longer. The examples below illustrate various ways that weak passwords are constructed, all of which are based on very simple patterns which result in extremely low randomness: [9]

  • Default passwords: password, default, admin, etc
  • Dictionary words: chameleon, Red Sox, sandbags, etc
  • Wordlist with numbers: password1, deer2000, john1234, etc
  • Wordlist with simple obfuscation: p@ssw0rd, l33th4x0r, g0ldf1sh, etc
  • Wordlist doubled: crabcrab, stopstop, treetree, etc
  • Sequences: qwerty, 12345678, euidhtns, etc
  • Identifiers: jsmith123, 1/1/1970, 555-1234, etc

There are many other ways a password can be weak;[17] the core principle is that a password should include real randomness and not be trivially derived from a "clever" pattern nor should passwords be mixed with information that identifies the user: that is the purpose of the user name!

[edit] Examples that follow guidelines

The passwords below are examples that follow guidelines for a strong password. Since these passwords have been publicly published, they should never be used verbatim.

  • 4pRte!ai@3 — mixes uppercase, lowercase, numbers, and punctuation
  • Tp4tci2s4U2g! — built from a phrase that a user can memorize: "The password for (4) this computer is too (2) strong for you to (4U2) guess!" — mixes types of character as well
  • BBslwys90! — loosely based on a phrase that a user can memorize: "Big Brother is always right (right angle = 90°)!" — mixes types of character as well.
  • tDI"60Hs7Q — characters selected from two stanzas by different methods from a page randomly selected using a 10-sided die.

[edit] Password Policy

Main article: Password policy

A password policy is a set of designed parameters, often controversial, that ensure:

  • Implementation of strong passwords
  • Reasonable passwords for the user population

For example, password expirations are a topic often covered by password policies. Password expirations serve two purposes:[18]

  • Cracking: Considering that the time to crack a password may be 100 days, expirations that occur every 90 days ensure insufficient time to crack the password.
  • Compromise: In the event a password is compromised, changing it will cut off access to the attacker.

Some argue, however, that password expirations have become obsolete, since:[19]

  • Simplicity: Asking users to frequently change passwords encourages simple, non-resilient passwords.
  • Cracking: In general, passwords can either be cracked in a matter seconds/minutes/days, or in a matter of decades. 30/60/90 day password changes do not make sense in that context: either change daily or never.

[edit] Handling strong passwords

Among the hardest passwords to crack are long, random strings of characters, however, these passwords are also the hardest to remember. The imposition of strong random passwords may encourage users to write down passwords, store them in PDAs or cellphones, or share them with others as a safeguard against memory failure, increasing the risk of disclosure.

The following measures can increase acceptance of strong password use, if carefully used:

  • A training program. Also, update training for those found to disclose passwords.
  • Reward users of strong passwords by reducing the rate, or eliminating all together, the need for password changes (password expiration).
  • Compensate for disclosed passwords by building a vigilant account closure process for departing users and/or a process to show each user a last login notification banner.
  • Automate a password reset system as a safety net. This will also reduce Helpdesk call volume concerning password resets. However, easily guessable password reset keys bypass the advantages of a strong password system.

[edit] Memory Techniques

Password policies sometimes include memory techniques for remembering passwords:

  • Mnemonic passwords: Some users develop mnemonic phrases that generate seemingly random passwords: for instance, the first letter of each word. Another way to make "random" passwords more memorable is to use random words (see diceware) or syllables instead of randomly chosen letters.
  • Patterned passwords: Any pattern in a password makes guessing (automated or not) easier. As of October 2005, employees of the UK Government are advised to use passwords of the following form: consonant, vowel, consonant, consonant, vowel, consonant, number, number (for example pinray45). This pattern is called an Environ password[citation needed] and is case-insensitive. This pattern of alternating vowel and consonant characters causes the password to be pronounceable and thus more memorable. Unfortunately, such patterns severely reduce the password's information entropy, making bruteforce password cracking considerably more efficient.

[edit] Protecting Passwords

Computer users are generally advised "never write down a password anywhere, no matter what" and "never use a specific password for more than one account." These maxims, while sound in theory, ignore the reality that an ordinary computer user may have dozens of password-protected accounts. The multitude of accounts often ends up with users having the same password everywhere. A user's attempt to comply will often result in many forgotten passwords, even for important accounts. When inconsistent password complexity requirements prevent consistent use of complex passwords, overly simplified passwords are created to satisfy user frustration as well as aid in the ease of password memorization.

If passwords are written down, they should never be kept in obvious places such as address books, Rolodex files, under drawers or keyboards or behind pictures. Perhaps the worst, but all too common, method is a note near the computer. Better locations are a safe deposit box or a locked file approved for information of comparable sensitivity to that protected by the password. Software is available for popular hand-held computers that can store passwords for numerous accounts in encrypted form. Another approach is to use a single password for low security accounts and select separate, strong passwords for a smaller number of high-value applications such as online banking. Manual or offline forms of this approach are also in use. For example, a phone directory may be used to keep a map between computer accounts and password hints.

At a 2005 security conference, an expert from Microsoft was quoted as saying: "I claim that password policy should say you should write down your password. I have 68 different passwords. If I am not allowed to write any of them down, guess what I am going to do? I am going to use the same password on every one of them."[20] Security expert Bruce Schneier agreed: "I recommend that people write their passwords down on a small piece of paper, and keep it with their other valuable small pieces of paper: in their wallet." [3]

[edit] Time needed for password searches

Main article: Password cracking

One way to judge the strength of a password is to measure the time and computing power required for cracking. The time to crack a password is compared to bit strength, which is a function of entropy, length, and complexity. Most methods of password cracking require the computer to generate large numbers of passwords to check. Brute force cracking, where a computer tries every possible key or password, is the lowest common denominator of password cracking. More common methods of password cracking, such as dictionary attacks, pattern checking, word list substitution, etc, will invariably be attempted before brute force.

The ability to crack passwords is a function of:

  • Number of keys (passwords) per second a computer is able to generate
  • Number of computers working on the cracking effort

Individual desktop computers can generate anywhere between one million to ten million keys per second depending on age and power. For example, many of the individual computers used in the first 3DES cracking effort by distributed.net in 1997 were generating only around one million keys per second. Yet, when ordinary desktop computers are combined in a cracking effort, as is often done with botnets, the capabilities of password cracking are considerably extended. In 2002, Distributed.net completed a crack on a 64-bit RC5 key in four years, in an effort which included over 300,000 different computers at various times, which generated an average of over 12 billion keys per second.[6]

What do these key rates mean? Consider the average 18-bit strength password (seven lowercase and one number): 218 = 262,144 permutations. Because a single desktop computer can check at the very least one million passwords per second, this is obviously problematic. An eight-character password that is user-selected with numbers, mixed case, and symbols, only reaches an estimated 30-bit strength, according to NIST. 230 is a meager one billion permutations. For a 1997 desktop, it would take an average of 16 minutes to crack. [4]

Despite their capabilities, regular home desktop CPUs are particularly inefficient at cracking passwords in relation to purpose-built password crackers. Although it has long been common knowledge for government bodies such as the NSA, EFF conclusively proved in 1998 that a dedicated password cracker with FPGAs, as opposed to CPUs, is a vastly superior cracking device. Their single machine, Deep Crack, generated 18 billion keys per second.[5]

[edit] References

  1. ^ Cyber Security Tip ST04-002 (HTML). Choosing and Protecting Passwords. US CERT. Retrieved on April 10, 2008.
  2. ^ a b c Passwords are Near the Breaking Point (PDF). Gartner. Retrieved on April 10, 2008.
  3. ^ a b Schneier on Security (html). Write Down Your Password. Retrieved on April 10, 2008.
  4. ^ a b c d e Electronic Authentication Guideline (PDF). NIST. Retrieved on March 27, 2008.
  5. ^ a b EFF DES CRACKER MACHINE BRINGS HONESTY TO CRYPTO DEBATE (HTML). EFF. Retrieved on March 27, 2008.
  6. ^ a b 64-bit key project status (HTML). Distributed.net. Retrieved on March 27, 2008.
  7. ^ 72-bit key project status (HTML). Distributed.net. Retrieved on March 31, 2008.
  8. ^ Bruce Schneier. Snakeoil: Warning Sign #5: Ridiculous key lengths (HTML). Retrieved on March 27, 2008.
  9. ^ a b c Burnett, Mark (2006). in Kleiman, Dave: Perfect Passwords. Rockland, MA: Syngress Publishing, 181. ISBN 1-59749-041-5. 
  10. ^ Eastlake, D.; Schiller, J.; Crocker, S.. Randomness Requirements for Security (HTML). PRNG: Some Bad ideas. Retrieved on April 7, 2008.
  11. ^ Gregg Keizer. Microsoft confirms that XP contains random number generator bug (HTML). Retrieved on April 7, 2008.
  12. ^ Bruce Schneier. MySpace Passwords aren't so Dumb (HTML). Wired Magazine. Retrieved on April 11, 2008.
  13. ^ Microsoft Corporation, Strong passwords: How to create and use them
  14. ^ Bruce Schneier, Choosing Secure Passwords
  15. ^ Google, Inc., How safe is your password?
  16. ^ Bidwell, Teri (2002). . Syngress Publishing. 1931836515. 
  17. ^ Bidwell, p. 87
  18. ^ In Defense of Password Expiration (HTML). League of Professional Systems Administrators. Retrieved on April 14, 2008.
  19. ^ Eugene Spafford. Security Myths and Passwords (HTML). The Center for Education and Research in Information Assurance and Security. Retrieved on April 14, 2008.
  20. ^ Microsoft security guru: Jot down your passwords, News.com.com Retrieved on 2007-05-07

[edit] External links