thu, 24-nov-2005, 10:49

The University has been requring certain departments to sit through a 15 minute presentation on using good passwords. One of the handouts had a chart showing how long it takes to crack passwords by how long they are and how many types of characters they've got in them. I'm interested in the subject because I typically assign passwords to my users when they start work. I wrote a simple program that takes words from the dictionary that are between 9 and 15 letters long, and which don't end in 'ing', 's', or 'ed'. The program then splits the word in the middle somewhere, inserts a random number, a random symbol, and capitalizes one of the following letters in the word.

For example, the script gets the word 'misdirection', inserts a '1' and a '%', and then capitalizes one of the letters in the word. The resulting password is 'misdi1%recTion'.

That password is composed of the letters [a-zA-Z], symbols [!@#$%^&*+=;:?], and numbers [0-9], so the set of characters to search for is 26 + 26 + 13 + 10 = 75. The password is 14 characters long, so the space a brute force attack has to search is 7514 = 1.8 x 1028 which is a huge number.

I did a few experiments with my workstation, which has an AMD Opteron 246 processor inside. Performing a brute force attack requires encrypting all these possible combinations until a match is found. So the type of encryption used is important. My computer can perform about 450,000 encryptions per second if the encryption is the old style DES encryption used on most proprietary Unix platforms. But all of my servers are running Linux, which uses md5 style passwords, and my computer can only do about 3,500 encryptions per second. So 1.8 x 1028 possible passwords / 3,500 encryptions / second means it'll take about 1.6 quadrillion years on my computer to crack it (or half that time on average).

Unfortunately, most passwords aren't cracked using brute force, they're cracked by using a dictionary attack, and since my passwords are generated using a dictionary, that means they're considerably more vulnerable. The question is, does my method of randomly inserting a number and symbol in the middle of a dictionary word (as well as randomly upper casing a letter) defeat a dictionary attack?

I don't know the answer. But I've done some experiments with pathologically bad passwords to see what might happen. On my computer a simple dictionary word is cracked within seconds. And a simple dictionary word with numbers appended (I tried 'barf51') is cracked in two and a half hours. So the jury is still out on my method. But I'll bet that my method isn't as safe as I thought it was at first. It's certainly better than the user that uses her husband's name, the name of the dog, or their license plate number for a password. Most cracking software has information about the typical behavior of users built into it, so it will start by searching the space defined by their username, their domain name, and common names. 'cswingle11' would be a pretty poor choice for me. 'misdi1%recTion' would undoubtably be better.

The only way to really generate passwords is to do it in such a way that there isn't a pattern (like a dictionary word) that the computer can identify and use to reduce the number of combinations the cracking program needs to test. So a better approach to passwords is probably to use a database of common phrases, and pull the first letters from the phrase, insert some random cases, symbols and numbers, and use that. Perhaps the 'fortune' command offers som possibilities here:

    $ fortune -n 80 | head -1
    There is no distinctly native American criminal class except Congress.

So: 'tindnaccec' --> TindnAcceC --> TindnA7#cceC

That's 7512 = 3 x 1022 and because it's effectively random (unless cracking tools learn about the 'fortune' database and how it might be manipulated. . .), it'll take 286 billion years for a computer equivalent to mine to crack this.

Sounds like a Python script in the making.

tags: sysadmin 
Meta Photolog Archives