On 11/08/2011 09:09 AM, Invisible wrote:

> As I recently wrote, this is the utterly counter-intuitive thing about
> combinatorics. The exponential function works in such a way that X
> digits can be trivially crackable, but X+Y, where Y is a fairly small
> number, can be utterly infeasible to crack.

Number of common | Number of combinations | Crack time at
dictionary words |                        | 10^6 guesses / second
-----------------+------------------------+-------------------------
         1        |                  8,000 | ~8 milliseconds
         2        |             64,000,000 | ~1 minute
         3        |        512,000,000,000 | ~6 days
         4        |  4,069,000,000,000,000 | ~130 years
         5        | ###################### | ~1.039 million years

So a 1-word password is trivially breakable, 2 is trivial, 3 is vaguely 
challenging (for one desktop PC), and 4 is for all intents and purposes 
unbreakable unless you have a fairly large quantity of hardware and/or 
unusually fast hardware. 5 is probably unbreakable no matter what 
hardware you have.

It's quite surprising that a 2-word password is weak as hell, and yet a 
4-word password is really very strong. You would have thought it would 
require a 20-word password or something to get good security...

All of these calculations of course assume that the words involved are 
/truly random/. If they're picked by a human, they aren't random. For 
example "correct horse battery staple" is almost all nouns. Words like 
"dog" are far more likely to be picked than "sifaka". (It's a kind of 
lemur. Go look it up.)

You could probably do some sort of statistical analysis to order the 
search in terms of more common words first, and it would probably go 
much, much faster.

Post a reply to this message