I’m not a security expert either, but I have stayed in a Holiday Inn so
take a crack at an answer
On 11/10/05, Pat M. firstname.lastname@example.org wrote:
I’m not a security expert (or even at all knowledgeable) by any means.
I just know how the SHLG works…it creates a random salt and stores
it in the db, then hashes the password against it. So you’re right,
if you have access to that then you probably have access to all the
other data you want. I think.
You also have to consider compromise of other systems. Most users don’t
separate passwords for every single account they own. If a cracker gets
Doe’s password on foo.com http://foo.com, he’s like to have the
for John D.'s account on Amazon and maybe his bank. It’s also possible
the password data is separated from other databases of value that are
in uncompromised systems.
b) regardless of “a”, if the salt value is stored right there next to
the encrypted password, doesn’t that defeat the purpose of having the
Again, not a security expert, but that seems pretty valid to me. I
suppose the advantage is that all the salts are different, so you
can’t just brute force hash your dictionary and get all the passwords.
You’d have to brute force the dictionary for each salt, if you want
to get all the passwords in the DB.
Look at it from the cracker’s viewpoint.
Case 1: No Salt
Without a salt, you generate possible passwords, hash them, and store
into a massive table. If you have a list of likely passwords, like a
dictionary, it substantially reduces the size of the generated table. If
limit the presumed length of passwords, you can reduce the number of
possible passwords. Depending on the size of your table, you might not
hit on some of the really long and complicated passwords. If you have to
worry about someone using a 15 character long password, the size of your
table goes up significantly even if you restrict possible passwords to
combinations of dictionary words.
Case 2: Fixed Salt
The password scheme has a single hash that’s reused, which is how the
login_generator works. We can’t use the tables we generated for cracking
foobar.com http://foobar.com, because the salt is different. So we
regenerate the table by prepending the known salt to the list of likely
passwords.The table generation doesn’t take an insignificant of time, so
cracker is having to spend his valuable time on your measly system.
Case 3: Varying Salt
Now we move to the salted_login_generator system that uses different
We have the same problem as the static salt case, but it’s magnifed by
single password we want to decrypt. The salted_login_generator also
the starting password, combines that hashed password with a salt, and
hashes the salt+hashed-password again. Does this extra hash step slow us
down? Well, it adds an extra SHA-1 computation for each possible
Case 4: We have no clue about the possible passwords
Each letter in our password could be one of the 26 letters, either lower
upper case, and the numerals (and maybe punctuation symbols). So each
in our password could take at least 26 + 26 + 10 = 62 possibilities,
disregarding other symbols for now.
To cover passwords with length of 1, we generate 62 guesses.
To cover passwords with length of 2, we generate 62 * 62 guesses.
To cover passwords with length of n, we generate 62^n guesses.
For some perspective, 62^8 = 218,340,105,584,896 according to my irb.
Take a look at the completed rainbow table for SHA-1:
They use a “mixalpha-numeric” character set, which is the 62 characters
have above. Limiting the password (plaintext) length range to 1-7
characters, it took 8 months and 47 days to generate the 30.52 Gb table
a Pentium 4 2GHz and 512 MB RAM. And you’d get about 99.33% success
client-side? I believe Yahoo mail used the code from