Sep. 26th, 2011


Sep. 26th, 2011 08:05 am
lederhosen: (Default)
Photos of my nephew over on LJ.
lederhosen: (Default)
This page has an interesting tool that lets you assess how hard a password is to detect via brute-force attacks.

Problem is, the accompanying discussion - and especially the advice on 'padding' as a technique for password security - relies on a really dangerous assumption.

Which of the following two passwords is stronger,
more secure, and more difficult to crack?



You probably know this is a trick question, but the answer is: Despite the fact that the first password is HUGELY easier to use and more memorable, it is also the stronger of the two! In fact, since it is one character longer and contains uppercase, lowercase, a number and special characters, that first password would take an attacker approximately 95 times longer to find by searching than the second impossible-to-remember-or-type password! [According to their calculator, a fast offline attack would take about 9.38 hundred trillion trillion centuries to crack this padded password.]

ENTROPY: If you are mathematically inclined, or if you have some security knowledge and training, you may be familiar with the idea of the “entropy” or the randomness and unpredictability of data. If so, you'll have noticed that the first, stronger password has much less entropy than the second (weaker) password. Virtually everyone has always believed or been told that passwords derived their strength from having “high entropy”. But as we see now, when the only available attack is guessing, that long-standing common wisdom . . . is . . . not . . . correct!

But wouldn't something like “D0g” be in a dictionary, even with the 'o' being a zero?

Sure, it might be. But that doesn't matter, because the attacker is totally blind to the way your passwords look. The old expression “Close only counts in horseshoes and hand grenades” applies here. The only thing an attacker can know is whether a password guess was an exact match . . . or not. The attacker doesn't know how long the password is, nor anything about what it might look like.

...except for what they can guess from common knowledge about how people handle passwords. At the point where your technique is available on a website, you can be pretty sure that other people might be aware of it.

So after exhausting all of the standard password cracking lists, databases and dictionaries, the attacker has no option other than to either give up and move on to someone else, or start guessing every possible password. And here's the key insight of this page, and “Password Padding”:

Once an exhaustive password search begins,
the most important factor is password length!

The password doesn't need to have “complex length”, because “simple length” is just as unknown to the attacker and must be searched for, just the same. “Simple length”, which is easily created by padding an easily memorized password with equally easy to remember (and enter) padding creates unbreakable passwords that are also easy to use.

At this point they overlook one vital point: there is no requirement that you search through all possible passwords in order of length. If you're writing a sophisticated brute-force approach, you can use information theory (which their page disparages) to work through that search in a more useful order.

For instance: let's start with a brute-force search, but add an extra character to the cracker's 'alphabet', ρ. When you get to a word containing 'ρ', you interpret it as follows: repeat the previous character X times, where X is indicated by the digit following the ρ (0=10).

Example: when you get to AbCρ8 , you test AbCCCCCCCCC (8 repeats). Letters a-z and A-Z following a ρ are interpreted as 11-62 repeats, respectively.

With this approach, you can represent padding of up to 63 repeating digits, at the cost of adding two letters to the 'length' of your brute-force search space, and one character to your alphabet.

The example they give has 21 '.'s in it, so under our compression scheme it would first be encountered as:


Compressed length of 6 characters, search alphabet of 96 characters including ρ: total ~ O(8E11) passwords to search before you get to their example.

So, while a dumb 'offline fast attack' scenario might indeed take 9.38 hundred trillion trillion centuries (at 100 billion guesses/second), a very slightly smarter scenario will take... a bit under ten seconds.

They go on to offer some tips on making padding more secure by using other mixes of characters, but if they're simple, these can still be defeated by slightly more sophisticated variants of the same approach used above. If they're not simple... well, then we're increasing the information entropy of the password, exactly the approach that they've just disparaged!

Sorry, but there's no magic way to generate passwords that are easy to remember and yet secure against high-powered brute-force, and I'm bothered that a 'security' company is telling people otherwise.


lederhosen: (Default)

July 2017

2324252627 2829

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Oct. 19th, 2017 10:45 am
Powered by Dreamwidth Studios