By Benjamin Rich

Passwords, on just about every system, are stored encrypted. The two general approaches to encryption are one-way and two-way encryption. One-way encryption is a method in which characters are encrypted so that the final outcome looks nothing like the original plaintext, and cannot be traced back or unencrypted - the algorithm cannot be reversed. Two-way is really more the type you hear about in spy movies, in which plaintext is translated into gibberish using a cipher, but can be translated back again using a special anti-cipher or key.

One-way systems are then of course more secure, since, failing a breakthrough in large number theory, it is completely impossible to trace the original plaintext from the resulting hash using any sort of magical algorithm. Two techniques are used in password "retrieval" (i.e. cracking your root password when you've been silly enough to forget it 1); that is, when we're talking about a password that can't be simply 'un-ciphered,' as by some clever WWII Bletchley Park operative "mathemagically."

These two techniques are known as 'brute-force' and 'dictionary' attack techniques. Both have their advantages and disadvantages, but both try to accomplish, in one way or another, the key goal when cracking one-way encryption - to reduce the monumental search-space for the plaintext password (your password), which, when encrypted using the one-way algorithm, will produce the stored hash.

Now indeed, some things might have become apparent. We want to crack let's say, an 8character password, because we happen to remember our root password was 8 letters, just not what it was. Let's assume we've used ASCII characters in our password (a-z, 0-9, !-?), which makes our search-space a whopping 256^8 possible passwords - but wait! Out of the 256 ASCII characters, the first 32 are non-displayable control codes (like beep, end-of-file, etc.) and the last 128 are 'extended' codes, like phi, the degrees sign, and DOS graphics corner brackets - thus, only 96 are really useable for password characters (in general) and finally, out of these 96, the DEL code is non-displayable again, so it's 95.

95^8 (2) is still, however, 66,342,000,000,000,000,000, which I hardly need to point out is gargantuan. To reduce this search space - which, with a computer capable of 1,000,000 password combination trials a second, would take 210 processing years to crack - more action is taken to increase the likelihood the desired solution will be found early in the exercise (3 days) instead of late (182 years).

This is accomplished in a variety of ways. We can prune the possible combinations by reducing the search-space, and that means using fewer characters in the search, or less password length. Many password retrieval programs allow you to enter wildcards (masking parts of the password you've forgotten - 'oh I know it starts with an m but I've forgotten the rest'). We can also make assumptions about the user's intelligence and inventiveness to reduce the possible character set - for instance, it's more likely a password has been constructed out of letters and numbers than it is it's been constructed out of letters, numbers, \$'s, #'s, and %'s. Of these, it's more likely # and \$ have been used that &, ^ and @, in general (this is not ironclad from statistics, but a good example). This can reduce the possible characters used from 95 down to anything as low as 26 (for people stupid enough to use only one set of letters), or 68 at a slightly more encompassing list size (including most symbols, upper and lower-case letters, and numbers).

Lastly, we can push more likely possibilities to the front of the queue so we increase our chances of reaching a solution faster - rather than doing a systematic search through the ASCII table, we can arrange letters ahead of numbers, numbers ahead of symbols, common letters ahead of less common letters, common symbols ahead of less common symbols, etc. With all this in mind - and with the fact that most people are lazy or unaware of password dynamics - most passwords can be cracked in under a week on a fast computer.

In any case, however, the more preferred method of attack is a polymorphic one, or a technique that second-guesses rather than dumbly applies near infinite lists of character combinations. For instance: trying English words; generating English-like possibilities; accounting for the clever l33t substitutions which their creators may believe makes their password 'not in the dictionary' and therefore 'uncrackable' - most of these comprise the 'dictionary' attack.

Put simply, most people do not make their passwords {^%F^&*# - they make them things like 'firefly' and 'swordfish' and possibly such ingenious non-words like 'blern' and 'st00pa' which all basically fall under the crushing wheels of a dictionary attack. No doubt, early dictionary attack crackers were literally the Aspell dictionary attached to a password checker, so that ubiquitous English words that people thought 'No one could ever possibly guess I would choose, hah ha!' could be entered ahead of 6,000 processing-years of random ASCII strings.

More advanced dictionary crackers use words which have been grabbed from web pages, articles, popular usage, movie scripts, etc. and so, therefore, homer simpson or crantastic, though both long and not in any dictionary, are potentially unsafe. Finally there is polymorphism and substitution, as stated above, which will give a list of tweaked words with common substitutions, or the ultimate in linguistico-hackery, a random English-sounding element generator (after all, even if you have been clever enough to enter something combining upper and lower case, numbers and symbols, and with a good length, if it still equates to crantastic, then it can be guessed by a program with knowledge of the rules of English phonetics and l33t substitutions) - though this is a challenge to say the least, some programs - notably many password generators - are capable of similar things already.

As a final sweetener, passwords can be guessed based on previously guessed passwords. As capitalized upon in the near-movie 'Hackers', while passwords can be, theoretically, combinatorial nightmares to guess, practically, they are often peerlessly simple: and thanks again to laziness, easily crackable passwords are replicated in many systems:
PHREAK:
Alright, what are the three most commonly used passwords?

JOEY:
Love, secret, and uh, sex. But not in that order, necessarily, right?

CEREAL:
Yeah but don't forget God. System operators love to use God. It's that whole male ego thing.
Many dictionary attack programs, upon finding a password, put it at the top of their dictionary file, since there is a good chance that someone else will have the same password (or a l33t variation).

### Footnotes

Footnote 1 Hopefully not for cracking someone else's root password. Not that you wouldn't have to have reasonably formidable skills to acquire the hash file first in order to crack it, and therefore, it is hoped, sufficient balls and sense of responsibility as a hacker to not do something immoral like that.

Footnote 2 The number of possible 8-character strings that can be made from 95 characters, not excluding repetition of characters in the string, etc. Notably, this is different from 95 Perm 8, which is a view of 8 characters from a possible space of all permutations of 95 characters - a subtle difference, but the answer is out by several trillion trillion trillion so it's worth noting that permutations should not be used to solve possible password combo problems like this one.

Benjamin Rich is the Web master of CSD.