salting

Re: salting

Gareth Heyes — Tue, 26 Feb 2008 15:33:42 -0600

Yep great thread I have a open mind and this has really helped in future web development thanks everyone :)

Re: salting

Malkav — Tue, 26 Feb 2008 15:26:39 -0600

@gareth

no, the only point of generating long, highly entropic salts is to complexify bruteforcing. remember that *anything* is breakable with enough time and/or computational power.

if bob the evil h4x0r got your hashes and your salts, he will still have to compute a rainbow (best time/space tradeoff) for each and every salt+hash. with the whole keyspace if he cannot deduce it from out of the band means. that's a whole lotta more difficult, and should give you enough time to take action.

the assumption of security being a destination is dangerous, because there is *no* magic bullet. at no time, under no circumstance (even if your data is made of a single disk sunk into concrete then into marianna's)

we just make their work harder. the only problem is that the tradeoff between risk and usability is not linear. at first you take small steps (ie :properly configuring a firewall) and you thwart off 90% of attacks (ie : automated network level attacks) then you take a bigger step, for a much lower gain, enough still to thwart off kiddies. then another bigger one, lowering gain again. etc...

so yes, using per-user, long, high entropy salts are a small step, for a huge gain (making the cracking of a large DB irrealistic. come on. 100GB rainbow per-user, for 10K users ? much simpler to do rubberhose cryptanalysis in the admin's face)

i think kogir made an excellent writeup of the situation and concepts. your foo is strong as they say

Re: salting

Gareth Heyes — Tue, 26 Feb 2008 03:20:05 -0600

kogir Wrote:
> right next to the users' password hashes. This is
> effective even when the salts are known because
> any rainbow table an attacker creates will be
> valid only against a single user's password. The
> point of a salt is to force the attacker to brute
> force each user's password individually, not to
> keep them from brute forcing a single password.

The random salt is a good point and could be stored in the database but what happens when SQL injection occurs or an attacker gains access to the database? Surely the point of uniquely hashing a password is to prevent a password from being reversed and exposing other accounts that user has.

Re: salting

kogir — Tue, 26 Feb 2008 01:38:58 -0600

Gareth Heyes Wrote:
-------------------------------------------------------
> @kogir
>
> How do you store per user salts? What happens when
> a new user is created? If the salts are stored in
> the database then I can see major problems with
> this method.
>
> I fail to understand why I'm missing the point
> please provide me with a link to a rainbow table
> that does MD5(MD5($password . RANDOMSALT)), you
> would need a pretty big table to store all that
> information.

===========
Random Salt
===========
I store random, per user salts in the database right next to the users' password hashes. This is effective even when the salts are known because any rainbow table an attacker creates will be valid only against a single user's password. The point of a salt is to force the attacker to brute force each user's password individually, not to keep them from brute forcing a single password.

For example, given two users, A and B, with passwords Pa and Pb, I'll produce two random salts, Sra and Srb. Using any hash algorithm I want, F(), I store password hashes Ha = F(Sra + Pa) and Hb = F(Srb + Pb) in the database for verification when authenticating A and B.

When a user A logs in, I look up the salt (Sra) and compute F(Sra + ). If F(Sra + ) matches what's in the database, the user is authenticated.

Computing a rainbow table for user A would require me to compute F(Sra + ) for all passwords I wish to precompute. This rainbow table would be useless in cracking user B's password because F(Sra + ) != F(Srb + ) for all values of .

It's true that attacking a single user's password is only as hard as brute forcing a single password, but all the effort expended in brute forcing A's password is useless in brute forcing B's password.

===========
Static Salt
===========
Using a static salt, Ss, would result in hashes of the form F(Ss + ) being stored in the database. Ha would be F(Ss + Pa) and Hb would be F(Ss + Pb). No matter how random Ss is when you first generate it, it's not random when used to compute Ha and Hb. If Pa == Pb, then Ha == Hb, and a rainbow table attack is now useful. You can now find users with the same password hashes and crack them all at the same time.

This holds true even for F() = MD5(MD5( + StaticSalt))

=======
Summary
=======
The only benefit a salt can provide is to force the attacker to treat each hash individually. Even if Ha and Hb match, if a random, per user, salt is used, then Pa and Pb won't match. Discovering Pa does not reveal Pb.

With resources like Aamzon S3 and EC2, for a few thousand dollars I can make a rainbow table that completely covers hashes for typical length passwords, given Ss and F(), in under a week. The mere fact that a rainbow table doesn't yet exist does not make static salts any less useless. The goal is to make creating such a table intractable.

It is possible to pick a hash function F() that is so computationally expensive that brute forcing a even a single user's password would be infeasible, but such functions are usually too burdensome to run on a web server handling reasonable traffic.

I hope this makes sense.

Re: salting

Malkav — Tue, 19 Feb 2008 10:25:42 -0600

more than happy to be useful to you. i have been most impressed with the hackverlets :)

Re: salting

Gareth Heyes — Tue, 19 Feb 2008 03:24:10 -0600

@Malkav

Thanks for the feedback

How are collisions relevant though? Surely that relates only to data verification because you can produce the same hash for different values. I was suggesting using a salt as well as a random pass of MD. But I'll defo take your advice thanks :)

Re: salting

Malkav — Tue, 19 Feb 2008 03:01:15 -0600

Gareth Heyes Wrote:
-------------------------------------------------------
> Please stop reading if this is too paranoid for
> you :P....
>
> Thinking about this a bit more I think the ideal
> method would be to use the username and a salt
> then a random amount of MD5 (or other hashing
> algorithm) My thinking behind this is that it is
> then difficult for an attacker to reproduce the
> sequence without access to the code (and then it's
> pretty much game over).
>
> When I mention random I mean a fixed method based
> on each site so for example site1 may use
> MD5(MD5(MD5(username . salt . password))), site2
> may use MD5(MD5(salt . password . username) etc,
> Now even with a large amount of computing power
> and time it becomes very hard to construct a
> rainbow table.

please gareth, please. attacker not having access to your algorithm is a most naive approach. and as to the pseudorandom multiple pass md5, i don't think it's a really sensible approach, here's why :

1 : if the user still has to use his credentials, the auth algorithm will have to know the number of md5 pass, meaning you'll have to persistently stock the information, rendering it vulnerable in the same way as the original salting technique

2 : relying on the secret of the algorithm to preserve the security of the output has traditionnaly been a bad idea (cf A5/1).

for a cryptographer, MD5 is broken. between collisions and birthday attack, both which are computationally feasible fairly easily (birthday being less pratical), your hash has few chance to survive on teh interweb.

if your authentication method is strictly password centric (monofactor) then i would recommend that you use classic salting method, relying on a pseudorandom nonce, factorial of multiple user-unique parameters, then a long hash function such as whirlpool. of course multiplying the number of bits is just a runaway. but that should keep your hash secure for the few years to come (unless some guy find a good, non NP-complete way to factorize large integers. but then we'll have *much* more problems than a few hash broken)

this will do the trick for enduser app, but then i'll recommand a much more macho method for heavyweight access. two factor is way cool, but three factor (smartcard, overly long pin, and biometric checks. have, know, is.) with a bunch of overly large, unfriendly, stupid and loyal to the death guys.

oh the NSA called btw, they want their paranoia back. now.

Re: salting

The-Wildcat — Mon, 18 Feb 2008 15:16:43 -0600

Hehe i like this paranoid stuff ;)

So you can use a per page salt (stored in defines or something similiar) rather than a per page method. Or combine both of them
Or you can merge 2 (salted or anything else) MD5 substrings to obfuscate the used algorithm or something similiar ^^

Re: salting

Gareth Heyes — Mon, 18 Feb 2008 05:51:04 -0600

So for example :-

Password : test
Salt : 123

8ddee7c48c3ad374e14c08d9c2502aeb

I've hashed the value with a certain amount of MD5's and a special sequence

Re: salting

Gareth Heyes — Mon, 18 Feb 2008 05:47:45 -0600

Please stop reading if this is too paranoid for you :P....

Thinking about this a bit more I think the ideal method would be to use the username and a salt then a random amount of MD5 (or other hashing algorithm) My thinking behind this is that it is then difficult for an attacker to reproduce the sequence without access to the code (and then it's pretty much game over).

When I mention random I mean a fixed method based on each site so for example site1 may use MD5(MD5(MD5(username . salt . password))), site2 may use MD5(MD5(salt . password . username) etc, Now even with a large amount of computing power and time it becomes very hard to construct a rainbow table.

Re: salting

Gareth Heyes — Mon, 18 Feb 2008 02:35:39 -0600

@fragge

Cool I like that method :)

Re: salting

fragge — Sun, 17 Feb 2008 23:14:58 -0600

Re: salting

Gareth Heyes — Sun, 17 Feb 2008 07:08:03 -0600

@kogir

How do you store per user salts? What happens when a new user is created? If the salts are stored in the database then I can see major problems with this method.

I fail to understand why I'm missing the point please provide me with a link to a rainbow table that does MD5(MD5($password . RANDOMSALT)), you would need a pretty big table to store all that information.

Re: salting

kogir — Sun, 17 Feb 2008 03:03:46 -0600

@Gareth Heyes

You're missing the point. The goal of properly implemented salting is to make *creating* a rainbow table intractable.

If I use sufficiently long and random *per user* salts, I can make it such that you have to start over and brute force each user's password by itself. None of the work done to crack user A's password can be reused to help crack user B's password.

See examples under http://en.wikipedia.org/wiki/Salt_%28cryptography%29

If you're looking for a good standardized password hashing algorithm, I recommend the key derivation functions in PKCS#5 v2.1 ftp://ftp.rsasecurity.com/pub/pkcs/pkcs-5v2/pkcs5v2_1.pdf

Re: salting

Gareth Heyes — Sun, 03 Feb 2008 04:56:53 -0600

@rsnake

That's the idea making a double hash + salt it's very unlikely that a rainbow table will exist.

Re: salting

rsnake — Sat, 02 Feb 2008 22:12:38 -0600

That only works because no one has built a rainbow table with double MD5 hashes. So it's good for newbies, but if they know which hashing algo you use (which is often the case if they can get the password files/database), and they are at all motivated, it's just a matter of computational time to compute one, or compute a table based on common passwords.

The point of a salt is to make it not just unique but unique per hash. So that if it's ever compromised a rainbow table would have to be constructed for each possible salt as well (per hash). That makes it exponentially larger and more difficult to compute.

Re: salting

Gareth Heyes — Sat, 19 Jan 2008 17:46:28 -0600

@DoctorDan

Finding a collision wouldn't matter for brute forcing password because the point of MD5 twice + salt is making the hash difficult to use in a rainbow table.

Re: salting

DoctorDan — Sat, 19 Jan 2008 16:29:13 -0600

I don't think doing two MD5s helps at all. If you're bruteforcing (without a dictionary), you're bound to find a collision no matter how many times you hash it. Granted, it won't be the same password- but it will work in your system.

-Dan

Someone please correct me if I'm wrong on this, by the way!

Re: salting

nEUrOO — Tue, 15 Jan 2008 08:17:32 -0600

why would this be safer than a pseudo-random string?

Re: salting

CrYpTiC_MauleR — Sat, 12 Jan 2008 20:37:09 -0600

Gareth Heyes Wrote:
-------------------------------------------------------
> I prefer a large random salt and md5 twice:
> MD5(MD5($salt . $password))

Yeah I use a 32-64 char mixed random salt and use SHA-512, of course that is overkill, but safest method I know =oP

Re: salting

Gareth Heyes — Sat, 12 Jan 2008 17:28:06 -0600

I prefer a large random salt and md5 twice:
MD5(MD5($salt . $password))

Re: salting

Anonymous User — Sat, 12 Jan 2008 04:54:47 -0600

What about salting with Unicode chars?

salting

majak — Fri, 11 Jan 2008 15:20:33 -0600

is there some standard on how to salt passwords?
somthing like hashed = hash(salt+password)?
i have already seen hashed = hash(hash(salt)+hash(password)).
and my own invention:-) is

while (length(password)<20) password+=password;
hashed = hash(password);

how do you salt passwords and what method would you (not) recommend?