Remember when a password with eight characters comprised of a mix of upper and lowercase letters and digits was considered secure? Unfortunately, many people do not even go to the trouble of making passwords that good. Recent security breaches have revealed that some of the most popular passwords are “password”, “123456″ and “monkey”. We will come back to that a bit later.
So, why is the topic of passwords being covered on the FM Tech blog? Because passwords are a necessary part of our computing lives, both at home and at work. Poor password creation, management and storage impacts users, software developers and businesses. We are all responsible for knowing what we are up against and what to do about it.
The old way of thinking about passwords
The old eight-character high-complexity passwords were thought to be good enough because of some simple math, which we will review now as a basis for discussion.
An eight-character password comprised only of digits has approximately 108 (10 different values for each of eight characters) or 100,000,000 combinations (the actual value is 111,111,110 when including combinations less than eight characters). Including upper and lowercase letters in the password increases the number of different values per character from 10 to 62 (26 uppercase, 26 lowercase and 10 digits), yielding over 628 (222 with 12 zeroes after it) possible combinations.
With so many possible combinations, it seemed inconceivable that such a complex password would be easily compromised. At 1,000 guesses per second, it would take over 7,000 years to try all possible combinations of an eight-character password comprised of uppercase letters, lowercase letters and digits. Even a rate of 1,000,000 guesses per second would take seven years.
So, what is the problem?
The fall of big numbers
There are several problems with this type of thinking. First, using brute force over the total number of possible combinations to crack every password is not realistic. Very rarely would all combinations have to be tried before guessing the correct password.
If we assume that a password cracking program starts at the first combination and works its way to the last one, it will discover some passwords near the first combination, some near the last one and many somewhere in between. Thus, on average, a password will be cracked after approximately half of the possible combinations are tried. This reduces the seven years to three and a half, on average.
Next, guessing passwords at a rate of 1,000,000 per second, even when taking into account having to then use a hashing or encryption algorithm in order to test the result, is no longer such a computing hurdle. By using an off-the-shelf desktop computer and multiple graphics cards normally used for video games, it is now possible to guess and test 100 billion or more passwords per second!
At that rate, our supposedly-secure eight-character password would be compromised in less than half an hour.
Now, you may be thinking that it is not possible for anyone to effectively do this because no Web site would allow such ongoing, high speed guessing. However, keep in mind that no hacker in his or her right mind would bother to conduct such an attack online. The myriad of security breaches at companies such as Sony, LinkedIn, Last.fm, and Yahoo! clearly illustrate how easy it can be to get access to an entire database of accounts for an offline password attack.
Brute force attacks are so 20th century
Despite the computing power that is readily available today, running through all possible combinations of characters is inefficient and not the smart way to crack passwords. Such brute force methods might be useful for very difficult passwords, but most of the time there is a shorter path to success.
Today, I can go online and purchase, for a measly sum of US $5, a list of over 60 million passwords from the many companies whose databases have been breached over the past few years. These are actual passwords that people have used on sites and are made readily available to me. It is not unusual, though, for some serious crackers to have lists of 500 million or more passwords.
Armed with such a list, password cracking programs are able to try the passwords as-is (a dictionary attack) and create guesses using the most common patterns of characters from real passwords. As a result, solving passwords becomes significantly faster.
For example, when LinkedIn lost control of its database of 6.5 million passwords in June of this year, security researcher Jeremi Gosney was able to, with commodity hardware, crack 1.3 million of them in 30 seconds. Over half of all the passwords were then cracked in a little over two hours. By the time a full day had passed, more than four million of LinkedIn’s passwords were cracked.
So, why spend the time and electricity on a brute force combinatorial attack that could take an hour on a single password when you can get many millions done in a day?
Where do we go from here?
Next week, in part two, we will take a look at what we, as users of systems that are secured by passwords, can do to improve our security as well as detect potentially insecure Web sites before we give them our passwords. After that, we will take on the software developer’s view of things to see what we can do to better manage and protect passwords in Web services that we create.