OSNews

Many years ago, while sitting at the... don't mind... I had the idea of calculating if a password could be "guessed" by brute force until our sun explodes. Or sun, not out Sun. :-)

Here are my thoughts, just for your entertainment:

Because it's not possible to "uncrypt" a password that has been crypted one time, I can only try a passphrase and see if it's valid (first crypt it, then compare).

Of course, I applied stupid assumptions, as "you can try as often as you want" and "each try lasts 1 second until you get the result". Valid assumptions included things like "how many characters can be entered using the (german version of the) keyboard". This makes Z = { A, B, C, ..., Z, a, b, c, ..., z, 0, 1, ..., 9, +, -, *, /, #, ... } the alphabet on which to operate.

On the german keyboard, there can be 192 different characters to be entered in a password, this is |Z| = 192.

So every position in the password can contain one of the 192 characters. This makes 192 possibilities for a 1 character password, 192 * 192 possibilities for a 2 character password and 192 ^ i possibilities for a i character password.

Given the "advice" that the password has a maximum length of m characters, all lengths from 1 to m have to be tested. This makes sum(i = 1 ... m) |Z|^i tries, with 1 second time required by each try, t = 1s.

The sun explodes in 5000 million years (assumption, even incorrect regarding what will really happen to the sun, but I don't care). The formula was something like ( t * sum(i = 1 ... m) |Z|^i ) / 60 * 60 / 24 / 365.2425 * 10^6 <= 5000, to be resolved to m.

Long story short: If I remember correctly, I "found out" that - under the circumstances assumed above - a password with the length of 5 characters could be guessed before the sun explodes, but a longer password, from 6 characters up, can't always.

As we all know, passwords in general should be 8 characters in minimum, and not the own name, the name of the wife, the pet, the car or something similar "easy". :-)

Edited 2009-05-23 19:05 UTC

However your assumption of 1 guess per second is extremely flawed... Depending on the cipher type used, a modern quad core processor running john the ripper can do between about a thousand per second (OpenBSD blowfish) to about 120 million per second (MS Lanman), combine that with clustering and you can have insane speeds...
Not to mention cracking using Cell processors and GPUS, who knows how fast that could be.

The strength of the target cipher has a big effect, openbsd's blowfish is very slow to brute force, the md5 based hash used on most linux systems is also quite slow, old des is considerably quicker but the windows hash types - lanman and ntlm - can be tried much more quickly.

Then consider rainbow tables, all of the unix hash types mentioned above are salted, that is an arbitrary but known value is used as an additional seed for the encryption.... Although this value is known so it doesn't make it more difficult to repeat the crypt operation, in order to create a rainbow table you would need to encrypt each possible password with each possible salt, rendering the attack infeasible... The windows hash types don't use salts and are susceptible to rainbow tables.

Also the available charset... You know you can use control chars in your password, tho depending where you try to log back in a gui keybinding could easily get in the way. Whereas other ciphers like lanman are not even case sensitive, thus massively reducing the available passwords.

Another amusing thing to note, is that on windows systems prior to vista both ntlm and lanman are used by default, that is even tho your password is stored using the stronger (but still pretty bad) ntlm cipher, it will also be stored using lanman as well... Throw a rainbow table at a lanman password and you'll have it in a few minutes, throw pure brute force at it and it's still only a matter of hours with a modern machine.