Password Infomania - Part One
By Benjamin
Rich
I recently read an interesting
article in 2600 about the pitfalls involved in choosing a
secure password. Since it's a techie issue and something many
people should be aware of (but aren't), I thought I should
recount some of the tips and background on passwords, password
selection, and how your password might be compromised. More
importantly, I'd like to show you how the weakest link in
any security structure is often the human link, and how you
can maximize the security integrity of your home or office
environment just by choosing more effective, harder to crack
passwords.
Password Storage
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.
Passwords that are highly important - such as the root password
to a multi-user system (your Linux 'root' password, your Windows
'administrator' password, etc.), or for most Internet mail accounts
and shopping accounts - are stored using one-way encryption.
This ensures that no matter where it is - even when it's on
the system where no one should, in naive theory, be able to
get - the password is never in a form in which it can be easily
compromised. When your password is entered (for instance, when
you login to your mail or your computer), the characters you
enter in plaintext are encrypted using the one-way algorithm,
and then the final result is compared to the stored 'hash,'
the encrypted information. Only if they match will you be allowed
in, not if they are simply the same password (since no one but
the user and the algorithm knows what the actual password is).
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."
Password Cracking
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:
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).
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.
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.