Two weeks ago through Security Now! Episode #303, Steve Gibson declared that our current view on passwords is not entirely correct. The most common philosophy is to have a completely random string of characters composed of alphanumeric characters, special symbols, between eight and sixteen characters in length. The downside of such passwords is that as these increase in length and randomness they also increase in difficulty of both memorization and input by the user. He argues that the length of the password is more important than randomness and that with length both ease of input and memorization can be achieved.
To understand his argument we need to review how password cracking works. (If you’re not interested in knowing or already know, feel free to skip the bullets and the next four to five paragraphs) .
There are three genreal approaches to defeating a password system:
- The first is to use a commonly known password such as
password. By using a list of common passwords an attacker has a greater chance of entering a system. These lists exist and are out there both in public and in private malicious networks. There is one published by Twitter that they use as a reference of what not to allow as a password in their system. Look for similar lists, read them, analyze them, and don’t use them as a legitimate tool to protect yourself. If you’re programming a system that has to be protected, try Twitter’s example.
- The so-called “Dictionary Attack.” This another list-based approach. It consists of an attacker essentially using all the words and their variations available in a dictionary. One can argue that the previous technique is merely an abbreviated version of the dictionary attack. “But I type my password in 1337 speak, so it’s not in a dictionary word!” You think an attacker would not thought of that too?
- Brute-force. This is almost a last ditch effort: the attacker will attempt all and any possible combination of characters, starting by a, then b, then c, until the attacker, eventually, discovers the password by mere brute force. Dumb, brutish, and simple to implement.
We can see from the above list what has to be done so, as users, we are able to protect ourselves: make sure our password is not on a common list, that it is not a dictionary word. Now defending against a brute-force attack is trickier. First we need to understand how a brute-force attack is done – and this is where the heart of Gibson’s insight lives.
Breaking into a system through brute-force is exactly as breaking through a combination lock. Let me illustrate:
A combination lock possesses a set of grooved wheels with numbers on it going from zero to nine. Now imagine a single wheel lock where the wheel is set from zero to nine . In order to break it you need to either guess the number or simply try all ten of them. Since there are only ten numbers going through all of them is a snap as there are only ten possible combinations. If we add a second wheel the number of combinations exponentiates from ten to a hundred. A third wheel increases the number of combinations to a thousand, and so on. Given enough time one can go trying every combination until hit the right one.
A password system works in a very similar fashion. And the computer has a very distinct advantage – it is very quick, and every eighteen months it gets quicker. But as the string of characters to find becomes longer, it takes an increasing amount of time; even to the point that it becomes unfeasible to crack.
This approach exploits the one vulnerability common to all password systems: given enough time, all passwords are discoverable. This is where Gibson’s idea comes in – to use time and effort against the attacker.
A password system, by design, should have no upper limit. While the lower end of passwords will be decimated by a brute-force attack, the higher end will be much harder to reach since every character we add to the string increases the search space by the number of character possibilities the system allows. Even if a system requires a valid password to be of x length the attacker is always forced to claw his or her way up the ladder of possible passwords. One interesting side-efect of this idea is that one can now use easy-to-remember passwords through the usage of patterns – for example: appending twenty dots at the end of your password makes it 95^20 times stronger than before. Even if they’re just dots an attacker would have no way to know and is still forced to try every possible variation.
This is not to say that this is a fool-proof way to securing yourself. Your password can still be phished, key-logged, type-heard, etc. It can be captured, and used against you, and once that happens: game over.
This is just a hardening method – but it is still pretty darn cool.
- 370 Passwords You Shouldn’t (And Can’t) Use On Twitter TechCrunch article on Twitter’s banned password list. It also includes that list.
- And the most popular password is… ZDNet article on Imperva ADC’s analysis of rockyou’s leaked password database.
- “Consumer Password Worst Practices” by The Imperva Application Defense Center (ADC)(PDF) Imperva ADC’s analysis of rockyou’s leaked password database.
- Security Now 303: Password Haystacks The SN! Episode that introduces the idea. 01:01:48 for the impatient.
- Security Now 304: Your Questions, Steve’s Answers #119 Q&E session with follow-up on the previous week’s introduction.
- GRC | Security Now! Episode Archive The SN! Archive with transcripts hosted over at GRC.
- GRC’s | Password Haystacks: How Well Hidden Is Your Needle? GRC page demonstrating the concept. NOT a password strength meter!
- Wikipedia: Brute-force Search
- Wikipedia: Combinatorial Explosion