Most people assume the myriad of passwords they use to log into applications, sites and service providers are relatively safe. They feel relatively safe, rather than extremely safe, because they have read of ongoing breaches and witnessed first hand the advances in computing and subsequently hacking power. Most people are realistic about the complexity of their password selections. Few are among the “14-plus characters, upper and lower case, symbol laden, not-to-be-found-in-the-dictionary” group. The average person’s passwords may seem fairly unique, but they are memorable … and therefore they are vulnerable.

Password hacking usually evokes images of a bad guy going to the login page at web service, entering the target’s username–most often an email address–and guessing at the password. Many people feel safe because they have been locked out of their own accounts after forgetting or mis-keying a password multiple times. They know their passwords aren’t bullet proof but feel confident it would take a hacker more than three attempts to guess correctly. This lockout feature adds to a mistaken sense of security.

That is because lockouts and similar protections do little to stop modern password hackers. They know the username and password before they visit the login page. They cracked it offline hours, days or months before.

The hacker’s paradise

Per Thorsheim, security professional and password guru, says an online attack against an individual account via the login screen has many limitations, the most important being the incredibly slow rate at which passwords can be tested. “Tools are available to speed up the process, but they can easily be defeated or at last slowed using rate-limiting countermeasures such as account lockout,” he explains.

Offline attacks, on the other hand, are a hacker’s paradise. According to Thorsheim, the only limitation on how fast passwords can be cracked offline is the power of the software and hardware at the attacker’s disposal. And when modern hackers say fast, they mean it. Thorsheim and others say they can make billions of guesses per second using computers and graphics cards available at the local Best Buy.

In the typical offline password hack, a database of login credentials is obtained via an orchestrated or accidental breach. In these cases, hackers are not targeting an individual account holder but rather going for volume attempting to crack a bunch of passwords to gain access to many accounts. “Most major leaks involve some kind of attack against an online service, with data copied out of databases and then cracked offline,” explains Thorsheim.

The trouble with hashes

Of course, most organizations do not store passwords in the clear or what is known as plain text. Instead they convert the user’s chosen password to an unrecognizable string of characters using a process called a hash. A hash is an algorithm that when applied to plain text returns a fixed-length unrecognizable string of data. The idea is that a hashed version of the password can be safely stored in the database, protected should the database ever be compromised. (See Figure 1)

Figure 1

Password = “fido”SHA-1 Hash = “cc22 a138 b5b0 4eb0 6600 eabb 1a1c d19c cf50 e930”

A key component of a hash is that it is unidirectional and cannot be reversed. There is no way to apply a cryptographic or other technique to a hash result and determine the original input used to create it.

Another characteristic of a good hash is that even a slight change in plain text input will result in a major change in hashed output. This makes it impossible to narrow down passwords by examining inputs and outputs and refining the password. In other words, reviewing the hash of “fidu” or “f1do” or even “Fido” (capital “F”) will not provide clues to help crack “fido”. (See Figure 2)

Figure 2

Password = “fido”SHA1 Hash = “cc22 a138 b5b0 4eb0 6600 eabb 1a1c d19c cf50 e930”

Password = “fidu”SHA1 Hash = “cd63 b4db 3b4d 50ed 2d51 670b 3e94 80df ac29 52c2”

Password = “f1do”SHA1 Hash = “a608 e978 b625 151b 9772 5011 ca5f 47b6 80a6 90d9”

Password = “Fido”SHA1 Hash = “c6ea b332 4465 7a4c 4c75 1fa4 7215 5eef 159a a4c8”

In an offline hack, the compromised database of credentials consists of a list of plain text usernames and their corresponding hashed passwords. The hash value for password is not accepted by a system for login, so the trick for the hacker is turning those hashed passwords back into ‘fido’ and other plain text versions.

How do they do it? They apply the same hash key used by the system to a plain text password and then compare the hashed version to the list of hashed passwords from the compromised database. If the hash matches any in the database, the hacker has a winner and that accountholder has a problem.

If the hacker is targeting a single, specific user and thus password the cracking process can be challenging. But if he has a compromised database with thousands or millions of records and simply wants valid credentials from any account holders, cracking the low hanging fruit is quite easy.

From brawn to brains

In the early days, the brute force attack was the prevailing method. The hacker would use an application or script to apply the hash to random combinations of characters and check the resulting hash against the database of actual hashed passwords in search of a match.

With modern computers and graphics cards, brute force attackers can do tens of thousands to hundreds of billions of attempts per second, says Thorsheim. “Even at such amazing speeds, however, we cannot test every combination possible with a-z, A-Z, 0-9 and special characters at lengths starting from 10-11 and upwards,” he says.

Fortunately for a hacker, that is where logical cracking comes to the rescue.

Dictionary attacks curb the time required by brute force attacks by hashing common words and combinations of words in search of matches. This attack recognizes the human tendency to select memorable passwords rather than a truly random series of characters. Most hackers rely on dictionaries of real words to expedite the cracking process.

Advanced password hackers improve dictionary attacks by studying human password selection techniques and employing this learning to build custom dictionaries. For example, individuals commonly create a password by appending a memorable year to a word or name, such as adding a pet’s birth year to his name–“fido1999.”

It is easy to add to a custom dictionary attack, incorporating common pet, human, athletic team, city and other names, and even appending each with thousands of years and other number strings.
And as more and more password breaches have occurred, massive lists of actual passwords have been compiled. Hackers have combined these real selections into their custom lists to create super dictionaries.

Think about it this way. When a database containing 6.4 million LinkedIn passwords surfaced in an online forum in Russia in June 2012, a great deal of the work to crack them had already been done. Hacker dictionaries containing common words and names, slang words, combinations of words, word and number combos had already been hashed using SHA-1. It was simply a means of comparing the dictionaries to the compromised dataset.

It took just seconds for password cracking specialist Jeremi Gosney to break the first 20% of the hashed LinkedIn passwords. Using his custom dictionary of more than 500 million real passwords collected from breaches, leaks and various other sources, he was able to crack 1.4 million without lifting a finger. By applying some basic logical password selection rules to the effort, he had recovered more than half within two hours. In two weeks he had successfully cracked 90% of the 6.4 million hashed passwords.

Hackers get smarter post RockYou hack

The doors to the password-cracking world literally blew open late in 2009 when the online gaming site, RockYou.com, was hacked. Nearly 32 million passwords were posted to the Internet in plain text.

The impact of the breach went far beyond the compromised site, as the data became a goldmine for anyone wanting to understand human password selection. For the first time, researchers and hackers had an actual dataset of massive proportion to explore, rather than one created via surveys, extrapolations and academic research. It was as if everyone in the state of California showed up at DEFCON to share their personal passwords with attendees.

RockYou redefined the dictionary attack by providing a glimpse into our secret password creation techniques.

Just weeks after the leak, security firm Imperva published an analysis of the password database. The findings were telling, though perhaps not surprising. Individuals tend to select the easiest, most basic passwords that meet the system’s requirements.

• More than one of every 100 users selected “12345” or “123456”
• One of three chose a password of six or fewer characters
• 60% used only alpha-numeric characters
• Nearly half used names, slang words, dictionary words or other trivial passwords such as consecutive numbers.

And hackers learned even more by examining the patterns. Incredibly common were names or words combined with numbers or dates (fido1999); words and their mirrors (fidoodif); and adjacent letters on a keyboard (asdfghj).

They learned more subtle patterns as well that further enabled the fine-tuning of their custom dictionaries.

When numeric characters are required, users tend to put them at the end of the password (fido123). If symbols are required, they tend to be used in between combined words (fido$1999) or at the end of the password (fido1999&). When uppercase letters are required, they tend to be used at the beginning (Fido) or at the beginning and end (FidO). Substitution of numbers for certain letters is common, such as “1” in place of “i” (f1do) or “3” in place of “e” (h3llo).

The top 5000 passwords used on RockYou list were shared by 20% of users. That means that even if this list has been hashed, any hacker–or even a basic computer user–could crack more than 6 million accounts in no time. With only a bit more work, the number of cracked accounts would reach 16 million as a basic dictionary attack matched names, slang words, and dictionary words.

With half the database cracked before the morning coffee was cold, the hacker could then move to more the sophisticated customized dictionary attacks and ultimately brute force attacks to take down others. (See Figure 3)

Figure 3 – Top 20 passwords from rockyou.com

Password	Number of users
123456	290731
12345	79078
123456789	76790
Password	61958
iloveyou	51622
princess	35231
rockyou	22588
1234567	21726
12345678	20553
abc123	17542
Nicole	17168
Daniel	16409
babygirl	16094
monkey	15294
Jessica	15162
Lovely	14950
michael	14898
Ashley	14329
654321	13984
Qwerty	13856

Strengthening passwords

Any hacker or statistician will say that there are two fundamental elements to password strength: size of the available character set and length of the password.

The size of the character set is crucial in determining the strength of a password. It stands to reason that if the pool of potential characters gets bigger, it becomes more difficult to determine each character in a password. This is the reason that, overtime, password requirements have progressed beyond numbers or letters to require alpha-numeric combinations, upper and lower case letters and symbols.

With each addition, the size of the character set available for use in the password grows and so too does its strength. The following chart shows the impact of an increasing number of usable characters on the total number of possible password combinations. For the demonstration below, a super short, four-character password is used–of course no one would use such as short password, unless it was for something insignificant like PIN-protecting a bank card. ( See Figure 4)

Figure 4 – Impact of Character set on number of possible 4-digit passwords

Character set	Formula	Combinations
Digits (0-9)	10 ^ 4	10,000
Lowercase Letters	26 ^ 4	456,976
Case insensitive letters and digits	36 ^ 4	1,679,616
Lowercase and uppercase	52 ^ 4	7,311,616
Lowercase, uppercase , and digits	62 ^ 4	14,776,336
Lowercase, uppercase, digits, and symbols	95 ^ 4	81,450,625

The number of characters also impacts the strength of a password. The increase in strength rises exponentially, not linearly, as the number of characters increase. The following chart shows the impact of adding characters to a password that uses upper and lowercase letters as well as digits. (See Figure 5)

Figure 5 – Impact of password length on number of possible combinations

Number of characters	Formula	Combinations
Password length = 4	62 ^ 4	14,776,336
Password length = 5	62 ^ 5	916,130,000
Password length = 6	62 ^ 6	56,800,000,000
Password length = 7	62 ^ 7	3,521,614,000,000
Password length = 8	62 ^ 8	218,340,110,000,000

Passwords vs. passphrases

The RockYou hack showed that left to their own devices, individuals gravitate toward weak passwords. As evidence, Imperva research found that 30% chose six or fewer characters and less than 4% included special characters/symbols.

Some in the authentication community believe that the use of a phrase in place of a password can help address each of these weaknesses and thus passphrases have been gaining favor.

First, phrases tend to be longer than passwords and thus have an inherent strength advantage that comes with additional characters. Even if the phrase selected consists of common dictionary words, its sheer length can add some level of strength. For example, the phrase “i graduated with honors from high school in kalamazoo” is certainly stronger than the word “graduated.”

Phrases can easily include, or be required to include, upper and lowercase letters as well as numbers and even symbols. This means phrases can benefit from the strength of large character sets. Example: “I graduated with honors & a 3.8 GPA from high school in Kalamazoo.”

Perhaps most importantly, many feel phrases are easier for users to remember than strong passwords. This means the unfortunate tendency to write down passwords on post-it notes or select the same password across sites can be lessened. The sentence above is meaningful and memorable so it should be easier to remember than a password like “gr@du8ED.” The phrase is also much harder to crack using brute force or custom dictionary attacks.

But are passphrases inherently better than passwords? “We really don’t know yet, but a general belief is that they are,” says Thorsheim.

Still his optimism is cautious. “Cracked passphrases, like those found with the Linkedin breach, suggests that users select “common” phrases from movies, books and pop culture,” he explains. When common phrases are used, the strength benefits of length can protect against brute force attacks but do little to guard against custom dictionary attacks.

Phrase dictionaries are already in development across the hacker community. From the LinkedIn breach, Gosney found numerous examples of easy-to-crack common phrases:

• happy healthy wealthy and wise,
• elvis has left the building,
• big trouble in little china,
• save the cheerleader save the world,
• crisscross applesauce, and
• work smarter not harder.

Certainly a hashed version of Bartlett’s Familiar Quotations is part of the modern hacker’s toolkit.

If a phrase is simply a combination of words, the number of passphrases would seem to be infinite. But Thorshiem suggests otherwise, particularly if you assume perfect grammar, no misspellings and short sentences based on common words used by the average English speaking person. “As we apply all kinds of research into language statistics we may find that there are not that many combinations to test after all,” he says.

If words were misspelled on purpose and non-existing words, dialects or incorrect grammar was introduced, would it increase the robustness of the passphrase if attacked? Thorsheim thinks it would, but he warns it could also impair the user’s ability to actually remember the passphrase.

“Our understanding of “secure” must include usability aspects,” he says. “It can be easy to create a secure solution, but it is just as easy to make it incredibly difficult to use, with high costs and loss of customers as a direct consequence.”

The scarier truth

If one’s LinkedIn social network or RockYou online gaming account is compromised, it is an inconvenience and possibly an embarrassment, but many would argue it is not that big of a deal. The reality, however, is far scarier. Among the things the previous decade of breaches taught hackers is that people reuse passwords and password patterns.

In his exploration of the LinkedIn data leak, Gosney found three important words in the list of most common base words used within passwords. Among the usual suspects like “love” and “password” he found “linkedin”, “linked” and “link”. More than 1% of all passwords contained one of these terms.

What is the ramification of this? If an individual’s LinkedIn password is “bob&linkedin” there is a very good possibility that his facebook login is “bob&facebook”. If he uses the same configuration for his email login, a hacker has access to his email account. And that is where he can take advantage of a well-timed reset request at the user’s online banking site in order to get past some of the weaker mechanisms that purport to be multi-factor authentication at bank sites.

No matter how insignificant the site or service may be, any breach causes a frightening cascade of risk if a user chooses and reuses weak passwords.

Recommendations for users

A parking garage seems a fitting analogy for the state of passwords and protections. Imagine a car parked in a garage with thousands of other cars and a team of auto thieves loose in the garage. It is unlikely they came to steal an specific individual’s car. More likely they simply came to steal cars and they will pick the easiest ones first.

If the owner diligently applies a steering wheel lock or other security add-on, it is far more likely that the thieves will choose an adjacent car. That is not to say that they could not break the additional lock and make off with the vehicle, but it would make no sense when other cars are quicker and easier to obtain.

In the same way, if an individual employs strong techniques in the password or passphrase selection process, hackers will crack thousands, perhaps millions, of weak selections before cracking the stronger ones. It is likely that the breach would be identified and publicized as accounts were accessed fraudulently. Individuals with still-intact accounts–those with the strongest passwords–would have time to select a new one before the old was cracked.

Are passwords obsolete?

Thorsheim believes that a passphrase, or even a password, can provide more than sufficient security if implemented correctly by both system administrators and users. Though it starts with strong password selections, he says it requires much more. “Proper sending, storage and reset practices must be applied, but today most service providers simply don’t do it,” he says.

“I don’t think passwords and PINs will ever disappear,” he concludes. ” But lots can be done to improve the way they are generated, remembered, sent, stored and reset.”