Yet another reason to use salted passwords


#1

The Register has a good article on some entrepreneurs making 500GB
tables
available for cracking six types of hash, including MD5 and SHA-1.

It makes the good point that crackers already have access to these kinds
of
tables, and the use of salts makes this kind of approach more
unmanageable.
Since using salts is relatively easy, it doesn’t make sense to skip the
extra step.


#2

Never even heard of this before. Good article… and thanks Bill !


#3

On 11/10/05, Bill K. removed_email_address@domain.invalid wrote:

The Register has a good article on some entrepreneurs making 500GB tables
available for cracking six types of hash, including MD5 and SHA-1.
http://www.theregister.co.uk/2005/11/10/password_hashes/

It makes the good point that crackers already have access to these kinds of
tables, and the use of salts makes this kind of approach more unmanageable.
Since using salts is relatively easy, it doesn’t make sense to skip the
extra step.

Interesting. I looked at the salted login gem and there seemed to be
a lot of steps that required a bunch of i18n stuff to be installed.
Is there a simple way to get salted logins without requiring a lot of
dependencies to be also installed?


#4

The normal login generator is actually salted too.


#5

2005/11/10, Joe Van D. removed_email_address@domain.invalid:

Interesting. I looked at the salted login gem and there seemed to be
a lot of steps that required a bunch of i18n stuff to be installed.
Is there a simple way to get salted logins without requiring a lot of
dependencies to be also installed?

If you don’t mind the new dependencies, LoginEngine installs in two
steps:
svn export http://opensvn.csie.org/rails_engines/plugins/engines
vendor/plugins/engines
svn export http://opensvn.csie.org/rails_engines/plugins/login_engine
vendor/plugins/login_engine

Then, read the docs in login_engine (which boil down to):
cd vendor/plugins/login_engine
rake import_login_engine_schema

Edit application.rb, application_helper.rb as required, add a line to
application.rhtml, then you’re done !

Hope that helps !

François Beausoleil
http://blog.teksol.info/


#6

On 11/10/05, Kyle M. removed_email_address@domain.invalid wrote:

The normal login generator is actually salted too.

Honestly, I don’t know too much about encryption stuff. But the salt
for the normal login generator is stored inside the application code.
So, if an attacker is able to get a copy of the database and the code,
he then has the salt.

But, he’s not able to use any pregenerated data to compare the
encrypted database contents against, right?

Does the salted login generator provide any extra protection than the
normal login generator?


#7

On 11/10/05, Joe Van D. removed_email_address@domain.invalid wrote:

Interesting. I looked at the salted login gem and there seemed to be
a lot of steps that required a bunch of i18n stuff to be installed.
Is there a simple way to get salted logins without requiring a lot of
dependencies to be also installed?


Rails mailing list
removed_email_address@domain.invalid
http://lists.rubyonrails.org/mailman/listinfo/rails

You can use the LoginEngine [1], which according to the docs is the
SHLG rolled into an engine, but with the localization requirements
removed.

Pat

[1] http://rails-engines.rubyforge.org/wiki/wiki.pl?LoginEngine


#8

Well, you have to have the salt somewhere accessible from the
application. The application has to read it to work. I guess you
could design the system so that part of it is behind an additional
layer of security (i.e. make the hashing happen on another, extremely
locked down server via RPC), but that’s making your life difficult for
perhaps a marginal gain.

The only thing that concerns me is that someone would look over my
shoulder at my salt, or that they would look on my computer while I’m
in the bathroom or something. I’ve been meaning to push it into
another file and require it, so that way i don’t have to see it as
often


#9

On 11/10/05, Pat M. removed_email_address@domain.invalid wrote:

encrypted database contents against, right?

Does the salted login generator provide any extra protection than the
normal login generator?

Is each generated salt also stored in the database?


#10

On 11/10/05, Joe Van D. removed_email_address@domain.invalid wrote:

Does the salted login generator provide any extra protection than the
normal login generator?

The salted login generator creates a random salt for each account,
then hashes the password against that salt.

Pat


#11

On 11/10/05, Joe Van D. removed_email_address@domain.invalid wrote:

But, he’s not able to use any pregenerated data to compare the
encrypted database contents against, right?

Does the salted login generator provide any extra protection than the
normal login generator?

Is each generated salt also stored in the database?

yep


#12

On 11/10/05, Pat M. removed_email_address@domain.invalid wrote:

On 11/10/05, Joe Van D. removed_email_address@domain.invalid wrote:

Is each generated salt also stored in the database?

yep

Maybe I’m just being dense here (not an encryption expert by any
means), but I fail to see what all this gains you.

Assuming the point of the salt value is to make the password more
difficult to decrypt and that in order to decrypt the password I would
need access to the encrypted string:

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.)

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?


Regards,
John W.
http://johnwilger.com


#13

On 11/10/05, John W. removed_email_address@domain.invalid wrote:

difficult to decrypt and that in order to decrypt the password I would
need access to the encrypted string:

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.

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.

Honestly, I don’t know the advantages of how the SHLG is implemented.
I just have a superficial understanding of how it’s implemented.

Pat


#14

On 11/10/05, Tom F. removed_email_address@domain.invalid wrote:

number), and therefore not feasible.

Tom,
If we have a known salt – let’s say we hacked a system, see the
login_generator code and the stored salt – then we create a table where
each entry = hash ( known-salt + this-password-guess). I would think
changing the salt size has no impact on the table size.

If we have no idea what the salt might be, then the table size
definitely
gets huge because you’ll have to make guesses at a randomly generated
salt.
But I’m looking at it from the standpoint of a compromised database.
-Bill


#15

Why store the salt in the database?

From what we’ve read today, a good database of hashed passwords is 500GB.
If you add a single byte salt to that, then the size of the database
needed
to crack those passwords is 256 times the 500GB. Typically, salts are
fairly long, 16 bytes is a good place to start. In addition to the
password, this would need a database of 500GB * 2 ^ 128 (16 bytes is 128
bits). This is more data storage than atoms in the universe (a really
big
number), and therefore not feasible.

Perhaps we can generate the set of passwords needed. Well, for each
password we need to generate the equivalent of the same amount of data,
but
we don’t need to store it. Calculating a hash is a non trivial amount
of
work when done at scale, so it become computationally time consuming to
break a password.

Why have a salt per account? If I can use one of the previous
techniques to
break one password, that would tell me what the salt value is too. If I
use
the same salt, I can then use that knowledge to add that salt to every
other
password attack, and I’m back at only needing a single 500GB database to
break every other password in the DB. Storing the salt means I need to
generate my individual 500GB database that only helps me crack this
password. For, say, 100,000 passwords, this is impractical.

In summary:

  1. Salts significantly increase the size of the DB needed for an attack
    to
    the point where it’s impractical to use one at all
  2. Generating password hashes on the fly is too intensive to be
    practical.
  3. Individual salts make it so that each password attack must be treated
    as
    a separate attack, and cracking one doesn’t help you crack the next.

Given enough time and importance (i.e. if this was Bill Gates’ bank
account,
it might be worth it, but for my To Do list, no-one’s going to do this),
this system can be broken, but the salt makes it really hard.

As computation speeds increase, there will be a time where a single
password
with salt can be cracked in a reasonable amount of time, but we’re not
there
yet.


#16

You are correct, changing the salt size has no impact on the size of the
table to cover every single possible entry. The 500GB database is a
subset
of the possible entries, but these are the hashes for the most likely
entries, words like ‘password’ and ‘secret’ etc. The larger the salt
you
use, the more you get out of the set of likely entries, up to a certain
point.

Even knowing the salt, you have to do the hard work of calculating all
of
the likely entries for that salt. And for the next password you must do
it
again, because the salt is different.

Even when the password database is compromised, the attacker must attack
each password individually rather than all passwords at once.

The combination of needing to calculate (rather than using the
pre-calculated set) the entire likely set for each password and that you
have to do each password individually, just makes an attack a lot harder
to
do in a reasonable amount of time.


From: Bill K. [mailto:removed_email_address@domain.invalid]
Sent: Thursday, November 10, 2005 10:18 PM
To: removed_email_address@domain.invalid
Subject: Re: [Rails] Yet another reason to use salted passwords

On 11/10/05, Tom F. removed_email_address@domain.invalid wrote:

Why store the salt in the database?

From what we’ve read today, a good database of hashed passwords is 500GB.
If you add a single byte salt to that, then the size of the database
needed
to crack those passwords is 256 times the 500GB. Typically, salts are
fairly long, 16 bytes is a good place to start. In addition to the
password, this would need a database of 500GB * 2 ^ 128 (16 bytes is 128
bits). This is more data storage than atoms in the universe (a really
big
number), and therefore not feasible.

Tom,
If we have a known salt – let’s say we hacked a system, see the
login_generator code and the stored salt – then we create a table where
each entry = hash ( known-salt + this-password-guess). I would think
changing the salt size has no impact on the table size.

If we have no idea what the salt might be, then the table size
definitely
gets huge because you’ll have to make guesses at a randomly generated
salt.
But I’m looking at it from the standpoint of a compromised database.
-Bill


#17

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. removed_email_address@domain.invalid 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
have
separate passwords for every single account they own. If a cracker gets
John
Doe’s password on foo.com http://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 http://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:
http://www.rainbowcrack-online.com/?x=sha1

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


#18

On Nov 10, 2005, at 7:30 PM, Francois B. wrote:

If you don’t mind the new dependencies, LoginEngine installs in two
steps:

Personally, I more mind the fact that engines are an approach not
sanctioned by the core team. (note that no announcement of engines
ever took place on the ror weblog)


#19

I’ve talked this over with DHH in IRC, therefore I’m pretty sure I
understand his perspective.

In short, plugins and generators are sanctioned, engines are not.


#20

Where they are sanctioned or not, they are useful and serve a very valid
purpose.

How else can I as a developer extend rails in a manner that includes a
view?
There simply is no other way without creating an engine. A “sanctioned”
plugin is for module and class extensions only, but doesn’t handle
anything
such as controllers or views.

It is an EXTREMELY powerful concept to have the potential to build an
entire
application based off engines. Wouldn’t you say?

  • Nathan