Looking at the use of the rainbow table mentioned below, assuming the
salt
value is known by the Bad Guy:
Case 1: No Salt
Rainbow table works great.
All passwords get cracked in 35 minutes.
Case 2: Fixed Salt
Pre-purchased Rainbow table won’t work. I need to generate one for this
particular salt, but once I have that, all passwords are cracked.
All passwords are cracked in 8 months + 35 minutes
Case 3: Varying salt:
Pre-purchased Rainbow table won’t work. I need to generate a unique
rainbow
table for each of my passwords.
Each password is cracked in 8 months + 35 minutes.
Case 4 is Case 1 - alpha numeric passwords, no salt.
The key here is that the salt values make the pre-calculated rainbow
tables
fail, and the Bad Guy needs to do more work to get what he wants.
One interesting case of the Fixed Salt is if you have some hardware
acceleration that you can use to hash your passwords. The salt can be
fixed, but locked in the hardware such that no-one can read it (you send
in
some text and it comes back hashed with the salt). This makes it so the
Bad
Guy has to search the entire hash range (or steal the hardware), which
for a
40 byte hash is 256^40, or this many possible entries:
2,135,987,035,920,910,082,395,021,706,169,552,114,602,704,522,356,652,769,94
7,041,607,822,219,725,780,640,550,022,962,086,936,576
From: Bill K. [mailto:[email protected]]
Sent: Thursday, November 10, 2005 11:13 PM
To: [email protected]
Subject: Re: [Rails] Yet another reason to use salted passwords
I’m not a security expert either, but I have stayed in a Holiday Inn so
I’ll
take a crack at an answer
On 11/10/05, Pat M. [email protected] wrote:
On 11/10/05, John W. [email protected] wrote:
a) If I have access to the database in order to get the encrypted
version of the password, doesn’t that mean I probably don’t need to
worry about decrypting passwords at that point since I already have
the rest of the data that was being protected? (Perhaps you should
store login information in a seperate database from everything else,
but I’ll bet this isn’t the case for the vast majority of
applications.)
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
have
separate passwords for every single account they own. If a cracker gets
John
Doe’s password on foo.com, he’s like to have the password for John D.'s
account on Amazon and maybe his bank. It’s also possible that the
password
data is separated from other databases of value that are stored 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
salt?
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
them
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
you
limit the presumed length of passwords, you can reduce the number of
possible passwords. Depending on the size of your table, you might not
get a
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, because the salt is different. So we have to 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 the 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
salts.
We have the same problem as the static salt case, but it’s magnifed by
every
single password we want to decrypt. The salted_login_generator also
hashes
the starting password, combines that hashed password with a salt, and
then
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
password
calculation.
Case 4: We have no clue about the possible passwords
Each letter in our password could be one of the 26 letters, either lower
or
upper case, and the numerals (and maybe punctuation symbols). So each
letter
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
I
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
with
a Pentium 4 2GHz and 512 MB RAM. And you’d get about 99.33% success
rate.
Has anyone used the Javascript SHA-1 scripts to compute the hash
client-side? I believe Yahoo mail used the code from
http://pajhome.org.uk/crypt/md5/
-Bill
