Thursday, October 29, 2015

Passwords, Password Cracking, and Pass Phrases

Yesterday I was contacted by a journalist who had questions about passwords.  I tried to convey some concepts to her, but when her response was "Wow.  You must really like math!"  I knew I had failed to communicate.  The story may have accomplished some purpose, but not one that would please a technical audience.  Below, I try again.

The story was partly prompted by a new password policy at UAB, where I work.  The basic policy is that you should have a 15-character password, but the quid pro quo for that is that you will only have to change your password once per year.

How Often to Change Passwords

We'll talk about the 15-characters below, but quickly about the one year.   The original "wisdom" about changing your passwords every thirty days was based on the fact that the average computer hacker using an average computer would need about thirty days to crack a password.  By changing your company's passwords every thirty days, if a hacker had managed to grab your /etc/passwd file or to dump all of your Windows hashes, by the time they had cracked the passwords, they would all be obsolete.  Now many Windows passwords can be cracked in seconds and most in less than a day.

There are still times to change the passwords more frequently.  Specifically:
  • any time you feel that someone may have observed you enter your password 
  • any time you have been exposed to malware or phishing
  • any time you have a change in administrative/trusted computing personnel (people who may know 'shared passwords' or passwords to routers/switches/servers)
  • whenever you are changing hardware or lose control of your devices (lost/stolen/sold computer/laptop/phone)
 Other than those times, there is really no reason to change your passwords, but an annual refresh still seems reasonable. 

Classes of Password Problems

Password re-use

One of the biggest problems that we face today with passwords is that people use the same passwords everywhere! Some studies have suggested that as many as 55% of adults use a single password on all websites! (See, for example, this 2013 UK study, or this June 2015 study by Harris Interactive, showing that 59% of Americans re-use passwords because it is too hard to remember them!)
Why is password re-use such a big deal? Because of the common problem of even the largest websites getting hacked and losing passwords!

  • 000Webhost - Just this week a major provider of free webhosting services had 13 million userids and passwords stolen (See story in Forbes or from Troy Hunt).
  • Ashley Madison - 11 million passwords have been cracked! CNN Ashley Madison passwords cracked, including the most popular passwords: 123456, password, 12345, 2345678, and qwerty. Other common passwords were "helpme", "midnight", and "yamaha".
  • Adobe - in 2013 150 million Adobe software users (that is YOU if you have ever downloaded Adobe's PDF Reader or Flash Player) had their userids, password hashes, and password "hints" leaked. Crackers soon made short work of millions of those passwords by matching hashes of leaked passwords and combining multiple hints to determine the underlying password.
  • LinkedIn - in 2012, hackers revealed that they had stolen 6.5 million userids and passwords from LinkedIn!

It is now generally accepted that every time one of these "major password dumps" hits the Internet, criminals use automated programs to test these userid and password combinations at all of the other bank, credit card, and merchant shops where you may have used the same userid and password on another account.  Many people make the error of treating their Email password as an "unimportant" account, failing to recognize that if I have your email password I now know where you bank (if you receive electronic statements), who you communicate with (and with your password, I *AM* you), and when you will be traveling!

Overly simple passwords
Many people who think they are being clever actually choose common passwords used by other people who thought they were being clever. A study in 2008 listed the 500 most common passwords at that time, and many of the continue to be widely used, including "clever" passwords such as "ncc1701" (the number of the Starship Enterprise), "bond007", and "qwertyui".)

One of my first exposures to the password problem came from the notorious "Morris Worm" which crashed the entire Internet back in the 1980s by using a simple password guessing list to break in to servers on the Internet. After each server was compromised, it would then try to break in to every other server it could find, starting by testing the 432 hard-coded passwords against every account it could find, and moving on to more complex cracking techniques. Robert Morris the Hacker, was the son of Robert Morris the Unix pioneer at Bell Labs. The Senior Morris had published a paper in 1979 called Password Security: A Case Study. After his death, a slashdotter revealed that he had discovered the senior Morris capturing other Bell Labs employees' passwords -- which may actually have been the source of the password list the younger Morris ended up using in his worm!

When I was a young Systems Programmer working at Samford (in 1989) I used the Morris Password list to require users at Samford to change their password if they were using any of those words. We added a few other common passwords to the list that we found our local users liked, including: bulldogs, bulldog!, ROLLTIDE, samford, and aubie1.

Password Cracking

 Let's talk about cracking alphabets:

If you have a one character password, and you restrict your password to only using the 26 lowercase alphabetic characters, guessing your password will take 26 guesses. abcdefghijklmnopqrstuvwxyz. Done! We've guessed your password!

If you have a TWO character password, how many guesses will it take? 26 SQUARED or 26^2 = 676 guesses, from aa, ab, ac to zx, zy, zz.

By raising the LENGTH of the password, we change the exponent. a 3 character password is 26^3, 4 characters = 26^4, 5 character = 26^5, etc.

By raising the SIZE of the alphabet, we change the BASE.
Lowercase = 26
Uppercase = 26
Numeric = 10
Special characters = 33
`~!@#$%^&*() -_=+[{]}\|;:'",<.>/?
(including the "space")

If we combine all of these, 26 + 26 + 10 + 33 = 95, we have a strong "alphabet" that resists crackers who have only been guessing "all lowercase" or "all lowercase plus numbers".

All the way back in the 1979 paper, Robert Morris warned about the dangers of password cracking and how simple passwords could be easily guessed by computers. In 1979, he calculated the time to crack various passwords, based on a combination of the length of the password and the size of the alphabet.

Now let's look at 1979 cracking times from the paper by Mr. Morris Senior:
n26 lower36 lower + numbers62 alpha + numbers95 printable charsall 128 ASCII chars
1 char 30 msec40 msec80 msec120 msec160 msec
2 chars800 msec2 sec5 sec11 sec20 sec
3 chars22 sec58 sec5 min17 min sec44 min
4 chars10 min35 min5 hrs28 hrs93 hrs
5 chars4 hrs21 hrs318 hrs112 days500 days
6 chars107 hrs760 hrs2.2 years29 yrs174 yrs

In 1979, a six character password with upper+lower+numeric+symbol would protect us from cracking for 29 years!  But today's computers are FAR faster than that! How does that compare to today's password cracking speeds?

To guess all 7-character lowercase passwords would be 26^7 guesses, or 8,031,810,176 (8 billion guesses!)

A secret about Windows passwords comes into play here. In environments that still use Windows XP, Windows defaults to a password storage mechanism called "LanMan Compatibility." That means that if your password is LONGER than 7 characters, Windows actually splits the password into two parts and hashes the first 7 characters as one hash, and the remaining 1-7 characters as a second hash. So, instead of a 14-character Windows XP password having a complexity:

26^14 = 64,509,974,703,297,150,976 (64 QUINTILLION guesses!)

It actually is stored as:

26^7 + 26^7 = 8 billion + 8 billion = 16 billion

Of course no one in their right mind is still running Windows XP! (right?)

Still, 16 billion guesses sounds like a lot, right? Unfortunately, not anymore.  How long would it take to crack a password that required 16 billion guesses?  If you have the right computer, LESS THAN ONE SECOND.

In December 2012, Ars Technica ran a story called 25 GPU Cluster Cracks Every Standard Windows Password in 6 hours!. The story is about a 5-server setup built with 25 Graphical Processing Unit cards (the video cards that the gamers love) that can guess 350 BILLION PASSWORDS PER SECOND!

So what do we do?

Even in Windows XP though, if we went to FIFTEEN characters, LanMan compatibility was broken, and we no longer divided the password, meaning that we now have:

26^15 if we use only lower case characters, or 95^15 if we use UPPER+lower+numeric+special characters!

95^15 = 463,291,230,159,753,366,058,349,609,375 (463 OCTILLION guesses!!!!)

463 OCTILLION divided by 350 Billion Passwords per second means . . .

1,323,689,229,027,866,760 seconds or
22,061,487,150,464,446 minutes or
367,691,452,507,740 hours or
15,320,477,187,822 days or
41,973,910,103 years

At UAB, we've decided that anyone who can wait 41 BILLION YEARS to crack your password is welcome to have all your data.

Of course we have to remember Moore's Law.

 Moore's Law suggests that computers double in speed every 18 months. While that doesn't sound like much, that means in 18 months it would only take 20.5 billion years. 18 months after that it would take 10.25 billion years. So in thirty-six 18 month periods, or 54 years, we would be able to crack that password in less than a year. That doesn't even take into consideration the fact that we will be able to harness additional computers together to use larger networks of computer to do the guessing.

Pass Phrases = 15 characters? How will I remember!?!?!

Remember that we not only need a LONG password, with a COMPLEX character set, we also need to make sure we don't re-use passwords across multiple sites!

There are two theories on how to do that.

One is to use password management software -- something like "LastPass" or "LogMeInOnce" -- I'm not going to address those packages here, other than to link to one review at PC Magazine -- The Best Password Managers for 2015 and to caution that MANY of the mobile phone apps that claim to be password managers are RIDICULOUSLY insecure! (See the article: ElcomSoft analyzes 17 Smartphones’ Secure Password Managers, Finds No Security).

The other theory, the one I like and use, is to use Pass phrases.

A pass phrase is a combination of words that is memorable TO YOU but that would not be something anyone else would know or use. Remember that the main trick criminals use to try to get your password is guessing commonly used passwords from a password list or dictionary BEFORE they start "brute-forcing" or guessing every combination of letters, numbers, and symbols. Password crackers come with dictionary files such as "10,000 most common passwords" and "100,000 most common passwords" and "English language names and places" and "Oxford English Dictionary Word List". We need to make sure OUR pass phrase is not on any of those lists.

Think of a memorable event. Or something you are unlikely to forget. Or a favorite book or movie. I'll give you an example of each of those.

Memorable Events
When my son got married we had an interesting situation. He hates cake. Always has. And yet WEDDING CAKES and GROOM'S CAKES are a major part of a wedding. My son did cookies instead of a groom's cake. So a password I used at about that time was:

theGROOMprefer$c00kies -- 22 characters. upper, lower, symbols, and numbers.

A common mistake people make with the numbers and symbols is to just put a "1!" at the end of their chosen word. Hackers know this, and cracking programs automatically check for that! I use common symbol and number substitions, such as replacing the letter "o" with the number zero (0), or replacing an "s" with a "$". E = 3, S = 5, A = @ are also some common substitions that are still easy to remember.

Unlikely to Forget
As many Christians do, I like to memorize scripture. I will often choose a password that relates to the site I'm visiting and invokes a Bible verse. For example, "" is a family tree website. One of my favorite Psalms, Psalms 1, says that people who meditate on God's word are "like a tree planted by rivers of water" so a good pass phrase for Ancestry for me might be:

th@tTR33fromPsalms1 -- 19 characters (That tree from Psalms 1). Upper, lower, symbols, number.

I also use passwords to remind myself or motivate myself. When my brother was adopting two sons from the Ukraine I had a password:


One of my Computer Forensics graduate students, Ran Sun, shared a presentation on passwords that included a link to this great article How a Password Changed My Life, where the author uses his passwords to remind himself to forgive someone, to encourage himself to stop smoking, and many other 'self-improvement' motivators.

Movies, Books, and Other tricks
One of my earliest password tricks was using a favorite book or movie title as a password. I remember telling one class about pass phrases and saying that one of my early passwords was "Robert Heinlein says the Moon is a Harsh Mistress". A bright student said "Oh! I see, take the first letter of every word to make your password -- RHstmiahm!" No. My password was actually: "RobertHeinleinsaysthemoonisaharshmistress". At that time 52^40. I don't care that it didn't use numbers or symbols.

Maybe your password is something related to an action by your favorite character: "Darth$@y$LukeIAMyourfather!"

or a combination of the author and his title "Hemingway&the0ldman&thesea"

or the year you first saw the movie: "1977.isawStarWarswithChad"

There are tons of ways to make a memorable pass phrase that will be memorable ONLY TO YOU!

The future of Password anti-cracking

The next technological trick to countering password cracking is to store the password hashes in a way that is more computationally complex. If an array of GPUs can guess 350 billion passwords per second, what is necessary is to make the process of guessing a SINGLE password require more computation time. Because a "real" user is only going to enter the password once, if it were to take even a full second for the password to be checked, that would be acceptable in most cases -- and yet it would make it much harder to "brute force" the account. bcrypt, an algorithm by Niels Provos and David Mazieres, is one such algorithm. Depending on the settings, it can reduce the number of password guesses per second down to under 20 even with a very fast computer! 20 vs. 350,000,000,000 will give the attacker a distinct disadvantage!

Last year at Password 2014 Conference in Norway, Thorsten Kranz presented a paper called On Password Guessing with GPUs and FPGAs (click for video of his presentation). This annual academic conference on passwords includes the "Password Hashing Competition" that discusses why bcrypt and scrypt are the best ways to store passwords.  For the uber-geeks, you will enjoy watching that!

No comments:

Post a Comment

Trying a new setting. After turning on comments, I got about 20-30 comments per day that were all link spam. Sorry to require login, but the spam was too much.