Password strength

Password strength is a measurement of the effectiveness of a password as an authentication credential. Specifically, it estimates how many trials an attacker who does not have direct access to the password would need, on average, to correctly guess it. The strength of a password is a function of length, complexity, and randomness.cite web | url = http://www.us-cert.gov/cas/tips/ST04-002.html | title = Cyber Security Tip ST04-002 | work = Choosing and Protecting Passwords | format = HTML | publisher = US CERT | accessmonthday = April 10 | accessyear = 2008]

Using strong passwords lowers overall risk of a security breach, but strong passwords do not replace the need for other effective security controls. The effectiveness of a password of a given strength is strongly determined by the design and implementation of the authentication system software, particularly how frequently password guesses can be tested by an attacker and how securely information on user passwords is stored and transmitted. Risks are also posed by several means of breaching computer security which are unrelated to password strength. Such means include: wiretapping, phishing, keystroke logging, social engineering, dumpster diving, side-channel attacks, software vulnerabilities etc.

Determining password strength

There are two primary ways passwords are created, automatically (using randomizing equipment) or by a human. The strength of randomly chosen passwords can be calculated with precision. More commonly, passwords are generated by asking a human to choose a password, typically guided by a set of rules or suggestions; an example is at account creation time for computer systems. In this case, only estimates of strength are possible, since humans tend to follow patterns in such tasks. In addition, lists of commonly chosen passwords are widely available for use in password guessing programs. All passwords on such lists are considered weak, as are passwords that are simple modifications of entries in such lists. Either can be quickly tried. For some decades, investigations of passwords on multi-user computer systems have shown that 40% or more are readily guessed using only computer programs, and more can be found when information about a particular user is taken into account during the attack. Fact|date=September 2008

Entropy or bit strength

It is standard in the computer industry to measure password strength in terms of information entropy, a concept from information theory. Instead of the number of guesses needed to find the password, the base-2 logarithm of that number is taken to be the equivalent of the number of "bits" in a password. A password with, say, 42 bits of strength as calculated this way would be as strong as a string of 42 random bits. Put another way, a password with 42 bits of strength would require 2⁴² attempts to exhaust all possibilities. Thus, adding a bit of entropy (or its equivalent) to a password doubles the number of guesses required. On average, an attacker will have to try half the possible passwords before finding the correct one.

Random passwords

Random passwords consist of a string of symbols of specified length taken from some set of symbol using a random selection process where each symbol is equally likely to be selected. The symbols can be individual characters from a character set, syllables designed to form pronounceable passwords, or words from a word list, to form a passphrase. For passwords that are generated by a process that selects at random a number, "N", of symbols from a set of possible symbols, where each symbol is equally probably, the number of possible passwords can be computed by multiplying the number of symbols in the set by N. Random passwords are often produced using a computer program. Such a program can be customized to ensure that the resulting password complies with a local password policy; perhaps, for instance, by always producing a mix of letters, numbers and special characters.

The strength of a random password can be calculated by computing the information entropy produced by the process producing it. If each symbol in the password is produced independently, the entropy is given by the formula

:$H\; =\; Llog\_2\; N\; =\; L\; \{log\; N\; over\; log\; 2\}$

where "N" is the number of possible symbols and "L" is the number of symbols in the password. The function log₂ is the base-2 logarithm. "H" is measured in bits. [Schneier, B: "Applied Cryptography", Second edition, page 233 ff. John Wiley and Sons.]

:

Thus an eight character password of single case letters and digits would have 41 bits of entropy (8 x 5.17). The same length password selected at random from all printable ASCII characters would have 52 bit entropy; however such a password would be harder to memorize and might be difficult to enter on non-U.S. keyboards. A ten character password of single case letters and digits would have essentially the same strength (51.7 bits).

The strength of random passwords depends on the actual entropy of the underlying random number generator. "See Random password generator#Stronger methods."

Human generated passwords

People are notoriously remiss at achieving sufficient entropy to produce satisfactory passwords. Some stage magicians exploit this inability for amusement, in a minor way, by divining supposed random choices (of numbers, say) made by audience members. 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. A uniform distribution would have had 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.

NIST uses the following scheme to estimate password entropy (i.e., randomness):cite web | url = http://csrc.nist.gov/publications/nistpubs/800-63/SP800-63V1_0_2.pdf | title = Electronic Authentication Guideline | format = PDF | publisher = NIST | accessmonthday = March 27 | accessyear = 2008]

* 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 suggests that, in the absence of a sensible password policy, an eight-character password has 18-bit equivalent strength. Yet, even with a password policy requiring at least one number, one symbol, and mixed case, an eight-character password only achieves an estimated 30-bit strength.

Bit strength threshold

As a practical matter, passwords must be both reasonable and functional for the end user as well as strong enough for the intended purpose. Passwords that are too difficult to remember may be written on paper, which some consider a security risk.cite web | url = http://www.indevis.de/dokumente/gartner_passwords_breakpoint.pdf | title = Passwords are Near the Breaking Point | format = PDF | publisher = Gartner | Author = A. Allan | accessmonthday = April 10 | accessyear = 2008] In contrast, others argue that forcing users to remember passwords without assistance necessitates weak passwords, and thus poses a greater security risk. According to Bruce Schneier, most people are good at securing their wallets or purses, which is a "great place" to store a written password.cite web | url = http://www.schneier.com/blog/archives/2005/06/write_down_your.html | title = Schneier on Security | work = Write Down Your Password | format = html | Author = Bruce Schneier | accessmonthday = April 10 | accessyear = 2008]

Some basic benchmarks have been established for password 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 using specially designed hardware.cite web | url = http://w2.eff.org/Privacy/Crypto/Crypto_misc/DESCracker/HTML/19980716_eff_descracker_pressrel.html | title = EFF DES CRACKER MACHINE BRINGS HONESTY TO CRYPTO DEBATE | format = HTML | publisher = EFF | accessmonthday = March 27 | accessyear = 2008] In 2002, "distributed.net" cracked a 64-bit key in 4 years, 9 months, and 23 days.cite web | url = http://stats.distributed.net/projects.php?project_id=5 | title = 64-bit key project status | format = HTML | publisher = Distributed.net | accessmonthday = March 27 | accessyear = 2008] Currently, "distributed.net" estimates that cracking a 72-bit key using current hardware will take about 403,784.9 days or 1,105.5 years.cite web | url = http://stats.distributed.net/projects.php?project_id=8 | title = 72-bit key project status | format = HTML | publisher = Distributed.net | accessmonthday = March 31 | accessyear = 2008] No currently expected increase in computer power will be sufficient to break 128-bit or 256-bit encryption using random keys via a brute-force attack. Due to currently understood limitations from fundamental physics, there is no expectation that any digital computer (or combination) on Earth will be capable of breaking 128-bit or 256-bit encryption via a brute-force attack.cite web | url = http://www.schneier.com/crypto-gram-9902.html | title = Snakeoil: Warning Sign #5: Ridiculous key lengths | format = HTML | author = Bruce Schneier | accessmonthday = March 27 | accessyear = 2008] Fact|date=June 2008 Whether or not quantum computers will be able to do so in practice is still unknown, though theoretical analysis suggests such possibilities.Fact|date=September 2008

As a result, there can be no exact answer to the password strength required to resist brute force attack in practice. NIST recommends 80-bits for the most secure passwords, which can nearly be achieved with a 95-character choice (e.g., the original ASCII character set) with a 12-character random password (12 x 6.5 bits = 78).

Character selection and length

For a password of a given length, the number of permitted symbols determines its maximum possible strength. (See table above.) For example, the printable characters in the ASCII character set (roughly those on a standard U.S. English keyboard) include 26 letters (each either upper or lower case), 10 numbers, and 33 symbols (i.e., punctuation, grouping, space, etc.), for a total of 95 symbols. Because national keyboard implementations vary, there are perhaps 88 printable characters which can be used nearly everywhere. "See" keyboard layout. If the allowed characters are only single case alphabetic, an eight-character password will have 26⁸ possible values (about 38 bits worth). With 88 allowed characters, a password of the same length will have 88⁸ possible values (about 52 bits), a much larger number, requiring (on average) sixteen thousand times more work for a successful brute force attack. A single case alphabetic password of comparable strength would require 11 characters.

Authenticating programs vary in which characters they allow in passwords. Some do not recognize case differences (e.g., the upper-case "E" is considered equivalent to the lower-case "e"), others prohibit some of the other symbols. In the past few decades, systems have slowly permitted more characters in passwords, but limitations still exist. Many hand held devices, such as PDAs and smart phones, require complex shift sequences to enter special characters. Systems also vary in the maximum length of passwords allowed, with some older systems limited to eight characters.

Users rarely make full use of larger characters sets in forming passwords. 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.cite web | url = http://www.wired.com/politics/security/commentary/securitymatters/2006/12/72300?currentPage=2 | title = MySpace Passwords aren't so Dumb | author = Bruce Schneier | format = HTML | publisher = Wired Magazine | accessmonthday = April 11 | accessyear = 2008]

Guidelines for strong passwords

Common guidelines for choosing good passwords are designed to make passwords less easily discovered by intelligent guessing: [Microsoft Corporation, [http://www.microsoft.com/protect/yourself/password/create.mspx Strong passwords: How to create and use them] ] Bruce Schneier, [http://www.schneier.com/blog/archives/2007/01/choosing_secure.html Choosing Secure Passwords] ] [Google, Inc., [https://www.google.com/accounts/PasswordHelp How safe is your password?] ] cite book
first = Teri
last = Bidwell
title =
publisher = Syngress Publishing
year = 2002
id = 1931836515]
* Include numbers, symbols, upper and lowercase letters in passwords
* Password length should be around 12 to 14 characters
* Avoid any password based on repetition, dictionary words, letter or number sequences, usernames, relative or pet names, or biographical information like (dates, ID numbers, ancestors names or dates, ...).

Examples of weak passwords

As with any security measure, passwords vary in effectiveness (i.e., strength); some are weaker than others. For example, the difference in weakness between a dictionary word and a word with obfuscation (i.e., letters in the password are substituted by, say, numbers -- a commonly chosen approach) may require a password cracking device to work a few seconds longer. The examples below illustrate various ways that weak passwords might be constructed, all of which are based on very simple patterns which result in extremely low entropy:cite book
last = Burnett
first = Mark
editor = Kleiman, Dave
title = Perfect Passwords
publisher = Syngress Publishing
date = 2006
location = Rockland, MA
pages = 181
isbn = 1-59749-041-5 ]

* Default passwords (as supplied by the system vendor and to be changed at installation time): "password", "default", "admin", "guest", etc.
* Dictionary words: "chameleon", "Red Sox", "sandbags", etc
* Words with number substitutions: "password1", "deer2000", "john1234", etc
* Words with simple obfuscation: "p@ssw0rd", "l33th4x0r", "g0ldf1sh", etc
* Doubled words: "crabcrab", "stopstop", "treetree", etc
* Commonly seen sequences: "qwerty", "12345678", "euidhtns", etc
* Numeric sequences based on well known numbers such as 911, 314159.. (pi) or 27182.. (e), etc
* Identifiers: "jsmith123", "1/1/1970", "555-1234", "your username", etc
* Anything personally related to you: license plate number, Social Security number, telephone number, student ID, birthday, relatives' or pets' names/nicknames/birthdays/initials, etc

There are many other ways a password can be weak; [Bidwell, p. 87] the core principle is that a password should include entropy (usually taken to be randomness) and "not" be trivially derived from any "clever" pattern, nor should passwords be mixed with information identifying the user.

Examples that follow guidelines

The passwords below are examples that follow some of the published guidelines for strong passwords. Since these example passwords have been published on Wikipedia, they should never be used as real passwords.

*"4pRte!ai@3" — mixes uppercase, lowercase, numbers, and punctuation, evidence that there is a larger character set, forcing an attacker to do more work
*"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. If the phrase is not 'well-known', this password should have high entropy for an attacker, and be easier than to remember than many passwords.
*"BBslwys90!" — loosely based on a phrase that a user might memorize: "Big Brother is always right (right angle = 90°)!" — mixes character classes
*"tDI"60Hs7Q" — characters selected from two poetry stanzas by different methods from a page selected using an honest die. But likely to be hard to memorize.
*"l52@36291QBs(" - the serial number of a dollar bill with added random elements. The bill and its serial number are likely to be hard to connect to the user and so will have high entropy to an attacker.

Password policy

A password policy is a guide to choosing satisfactory passwords. Some are controversial. They are usually intended to:
* assist users in choosing strong passwords
* ensure the passwords are suited to the target population
* recommendations to users with regard to the handling of their passwords
* a requirement to change any password which has been lost or compromised, and perhaps that no password be used longer than a limited time
* some policies prescribe the pattern of characters which passwords must contain

For example, password expiration is often covered by password policies. Password expiration serves two purposes:cite web | url = http://lopsa.org/node/295 | title = In Defense of Password Expiration | format = HTML | publisher = League of Professional Systems Administrators | accessmonthday = April 14 | accessyear = 2008]
* if the time to crack a password is estimated to be 100 days, password expiration times less than 100 days may help ensure insufficient time for an attacker.
* if a password has been compromised, requiring it to be changed regularly should limit the access time for the attacker

Some argue, however, that password expirations have become obsolete,cite web | url = http://www.cerias.purdue.edu/weblogs/spaf/general/post-30/ | title = Security Myths and Passwords | format = HTML | publisher = The Center for Education and Research in Information Assurance and Security | author = Eugene Spafford | accessmonthday = April 14 | accessyear = 2008] since:
* asking users to frequently change passwords encourages simple, weak, passwords.
* if one has a truly strong password, there is little point in changing it, since the existing password is already strong. Changing passwords which are already strong merely introduce risk that the new password may be less strong.

Handling strong passwords

Among the hardest passwords to crack are long, high entropy character strings; they resist brute force attacks (ie, many characters) and guessing attacks (ie, high entropy). However, such passwords are often also the hardest to remember. The imposition of a requirement for such passwords in a password policy may encourage users to write them down, store them in PDAs or cellphones, or share them with others as a safeguard against memory failure. Some people consider each of these user resorts to be security risks. In practice, others suggest recognizing the reality of multiple complex passwords. Security expert Bruce Schneier [http://www.schneier.com/blog/archives/2005/06/write_down_your.html recommends writing down your password] :

The following measures may increase acceptance of strong password requirements, if carefully used:
* a training program. Also, updated training for those who fail to follow the password policy (lost passwords, inadequate passwords, etc).
* reward strong password users by reducing the rate, or eliminating all together, the need for password changes (password expiration). The strength of user-chosen passwords can be estimated by automatic programs which inspect and evaluate proposed passwords, when setting or changing a password.
* mandate a thorough and rapid account closure process for departing users and/or a process to display to each user the last login date and time in the hope that the user may notice unauthorized access, suggesting a compromised password
* allow users to reset their passwords via an automatic system. This should also reduce Helpdesk call volume. However, some such systems are themselves insecure; for instance, weak (or easily guessed, or insufficiently frequently changed) password reset keys bypass the advantages of a strong password system.

Memory techniques

Password policies sometimes suggest memory techniques to assist remembering passwords:
* mnemonic passwords: Some users develop mnemonic phrases and use them to generate high entropy (random appearing) passwords which are nevertheless relatively easy for the user to remember. For instance, the first letter of each word. Another way to make random appearing passwords more memorable is to use random words (see diceware) or syllables instead of randomly chosen letters.
* password patterns: Any pattern in a password makes guessing (automated or not) easier and reduces an attackers work factor. An example is from the UK. 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 passwordFact|date=August 2007 and is case-insensitive. The pattern of alternating vowel and consonant characters is intended to make passwords more likely to be pronounceable, and thus more memorable. Unfortunately, such patterns severely reduce the password's information entropy, making brute force password attacks considerably more efficient.

Protecting passwords

Computer users are generally advised to "never write down a password anywhere, no matter what" and "never use the same password for more than one account." This advice ignores the reality that an ordinary computer user may have dozens of password-protected accounts. Users with multiple accounts (and passwords) often give up and use the same password for every account. When varied password complexity requirements prevent use of the same (memorable) scheme for producing high strength passwords, overly simplified passwords will often be created to satisfy irritating and conflicting password requirements.

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." [ [http://news.com.com/Microsoft+security+guru+Jot+down+your+passwords/2100-7355_3-5716590.html?tag=nefd.pop Microsoft security guru: Jot down your passwords] , "News.com.com" Retrieved on 2007-05-07 ] 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."

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, location is a Post-It note on the computer monitor. Better locations are a safe deposit box or a locked file approved for information of sensitivity comparable 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.

Time needed for password searches

One way to judge the strength of a password is to estimate the time and computing power required for cracking. The time to crack a password is related to bit strength (see above), which is a function of the password's information entropy. Most methods of password cracking require the computer to produce many candidate passwords, each of which is checked. Brute force cracking, in which a computer tries "every" possible key or password until it succeeds, is the lowest common denominator of password cracking. More common methods of password cracking, such as dictionary attacks, pattern checking, word list substitution, etc, attempt to reduce the number of trials required and will usually be attempted before brute force.

The ability to crack passwords using computer programs is a function of the number of possible passwords per second which can be checked. If a hash of the target password is available to the attacker, this number can be quite large. If not, the rate depends on whether the authentication software limits how often a password can be tried, either by time delays, CAPTCHAs, or forced logouts after some number of failed attempts.

Individual desktop computers can test anywhere between one million to ten million passwords per second against a password hash. A user-selected eight-character password with numbers, mixed case, and symbols, reaches an estimated 30-bit strength, according to NIST. 2³⁰ is only one billion permutations and would take an average of 16 minutes to crack. When ordinary desktop computers are combined in a cracking effort, as can be done with botnets, the capabilities of password cracking are considerably extended. In 2002, distributed.net successfully found a 64-bit RC5 key in four years, in an effort which included over 300,000 different computers at various times, and which generated an average of over 12 billion keys per second.

Despite their capabilities, desktop CPUs are slower at cracking passwords than purpose-built password breaking machines. In 1998, the Electronic Frontier Foundation (EFF) built a dedicated password cracker using FPGAs, as opposed to general purpose CPUs. Their machine, Deep Crack, broke a DES 56-bit key in 56 hours, testing over 90 billion keys per second. The hashes widely used for storing passwords, such as MD5 and the SHA family, are designed for efficient implementation in hardware. Using key stretching algorithms, such as PBKDF2, to form password hashes can significantly reduce the rate at which passwords can be tested.

Perhaps the fastest way to crack passwords is through the used of pre-computed rainbow tables. These encode the hashes of common passwords based on the most widely used hash functions and can crack passwords in a matter of seconds. However they are only effective on systems that do not use salt, such as Windows LAN Manager and some application programs.

References

External links

* [http://psynch.com/docs/choosing-good-passwords.html Choosing Good Passwords — A User Guide] .
* [http://psynch.com/docs/password-policy-guidelines.html Password Policy Guidelines] .
* [http://www.modernlifeisrubbish.co.uk/top-10-most-common-passwords.asp Examples of common (and hence weak) passwords]
* [http://download.lawr.ucdavis.edu/pub/it/CambridgePWStudy.pdf The Memorability and Security of Passwords — Some Empirical Results (Study done by Cambridge University Computer Laboratory)]
* Bruce Schneier (December 14, 2006). [http://www.schneier.com/essay-144.html MySpace Passwords Aren't So Dumb] .
* [https://www.isc2.org/cgi-bin/content.cgi?page=738 Rainbow tables]
* [http://www.csoonline.com/read/120105/ht_passwords.html How to Write Better Passwords]
* [http://tools.ietf.org/html/rfc4086 RFC 4086: Randomness Requirements for Security]
* [http://www.searchlores.org/commonpass1.htm Frequently used passwords to avoid]