P1: JDW
WL040C-01 WL040/Bidgoli-Vol III-Ch-01 June 24, 2003 10:39 Char Count= 0
4 PASSWORDSTable 1Output from the MD5 Test SuiteFor the Input String The Output Message Digest is“” (no password) d41d8cd98f00b204e9800998ecf8427e
“a” 0cc175b9c0f1b6a831c399e269772661
“abc” 900150983cd24fb0d6963f7d28e17f72
“message digest” f96b697d7cb7938d525a2f31aaf161d0
“abcdefghijklmnopqrstuvwxyz” c3fcd3d76192e4007dfb496cca67e13b
“ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmno d174ab98d277d9f5a5611c2c9f419d9f
pqrstuvwxyz0123456789”
“1234567890123456789012345678901234567890123456789 57edf4a22be3c955ac49da2e2107b67a
01234567890123456 78901234567890”a string that produces a given hash value should be very
difficult. It should also be difficult to find two arbitrary
strings that produce the same hash value. Also called a
message digest or fingerprint, several one-way hash func-
tions are in common use today. Among these are Se-
cure Hashing Algorithm-1 (SHA-1) and Message Digest-5
(MD-5). The latter was invented by Ron Rivest for RSA
Security, Inc. and produces a 128-bit hash value. See
Table 1 for an example of output generated by MD5.
SHA-1 was developed by the U.S. National Institute of
Standards and Technology (NIST) and the National Se-
curity Agency (NSA) and produces 160-bit hash values.
SHA-1 is generally considered more secure than MD5 due
to its longer hash value.
Microsoft Windows NT uses one-way hash functions
to store password information in the Security Account
Manager (SAM). There are no Windows32 Applications
Programming Interface (API) function calls to retrieve
user passwords because the system does not store them. It
stores only hash values. However, even a hash-encrypted
password in a database is not entirely secure. A crack-
ing tool can compile a list of, say, the one million most
commonly used passwords and compute hash functions
from all of them. Then the tool can obtain the system
account database and compare the hashed passwords in
the database with its own list to see what matches. This
is called a “dictionary attack” (see “Password Cracking
Tools”).
To make dictionary attacks more difficult, often a salt is
used. A salt is a random string that is concatenated with a
password before it is operated on by the hashing function.
The salt value is then stored in the user database, together
with the result of the hash function. Using a salt makes
dictionary attacks more difficult, as a cracker would have
to compute the hashes for all possible salt values.
A simple example of a salt would be to add the time of
day; for example, if a user logs in at noon using the pass-
word “pass,” the string that would be encrypted might be
“1p2a0s0s.” By adding this randomness to the password,
the hash will actually be different every time the user logs
in (unless it is at noon every day). Whether a salt is used
and what the salt actually is depends upon the operat-
ing system and the encryption algorithm being used. On
a FreeBSD system, for example, there is a function called
crypt that uses the DES, MD5, or Blowfish algorithms to
hash passwords and can also use three forms of salts.
According to Cambridge University professor of com-
puting Roger Needham, the Cambridge Multiple AccessSystem (CMAS), which was an integrated online–offline
terminal or regular input-driven system, may have been
among the earliest to implement such one-way func-
tions. It first went online in 1967 and incorporated
password protection. According to Needham: “In 1966,
we conceived the use of one-way functions to protect the
password file, and this was an implemented feature from
day one” (R. Needham, personal communication, April
11, 2002).
One-way hashing is still being used today, although it
does not address another weakness—in a networked envi-
ronment, it is difficult to transmit the password securely
to the server for verification without its being captured
and reused, perhaps in a replay attack. To avoid revealing
passwords directly over an untrusted network, computer
scientists have developed challenge–response systems. At
their simplest, the server sends the user some sort of chal-
lenge, which would typically be a random string of char-
acters called a nonce. The user then computes a response,
usually some function based on both the challenge and
the password. This way, even if the intruder captured a
valid challenge–response pair, it would not help him or
her gain access to the system, because future challenges
would be different and require different responses.
These challenge-and-response systems are referred to
as one-time password (OTP) systems. Bellcore’s S/KEY is
one such system in which a one-time password is calcu-
lated by combining a seed with a secret password known
only to the user and then applying a secure hashing algo-
rithm a number of times equal to the sequence number.
Each time the user is authenticated, the sequence number
expected by the system is decremented, thus eliminating
the possibility of an attacker trying a replay attack using
the same password again. One-time passwords were more
prevalent before secure shell (SSH) and secure sockets
layer (SSL) systems came into widespread use.PASSWORD CRACKING TOOLS
Password-Cracking Approaches
As mentioned earlier, passwords are typically stored as
values hashed with SHA-1 or MD5, which are one-way
functions. In other words, this entire encyclopedia could
be hashed and represented as eight bytes of gibberish.
There would be no way to use these eight bytes of data
to obtain the original text. However, password crack-
ers know that people do not use whole encyclopedias as
their passwords. The vast majority of passwords are 4 to