Re: Salt -- Something I've Never Understood

If there were no salt, then someone could spend a few CPU years running every plausible password string through crypt() and make/distribute a reverse-mapping database. With a random salt, the size of such a database becomes much more infeasible to try to produce (you have to try each possible password with each possible salt string). But I doubt this is much of an issue these days, thanks to Moore's law and distributed computing.

There's also the fact that if two people have the same password, with (random) salt, that fact is not obvious by looking at their encrypted passwords. This is probably the most important reasoning: more information can be protected by using salt.

blokhead

Comment on Re: Salt -- Something I've Never Understood

Replies are listed 'Best First'.
Re: Re: Salt -- Something I've Never Understood by hardburn (Abbot) on Feb 05, 2004 at 17:09 UTC
But I doubt this is much of an issue these days, thanks to Moore's law and distributed computing. This is true for `crypt()` because it doesn't use a long enough salt value. However, a properly-sized salt can make all dictionary attacks impractical unless there are some fundamental changes in understanding computers (Moore's "law" is more like an observation, and will stop working someday). With a 32-bit salt, and a 160-bit hashing algorithm (like SHA1), the minimum size of the password database (not the attacker's dictionary) is 32 + 160 = 192 bits / user (ignoring the space to store the username and whatever overhead is needed by the database itself). To generate a dictionary, an attacker must create a hash value for every possible password and all salt values for each password. There are 2³² possible salt values, so it takes 160 * 2³² = 640 GB to store all possibilities for one password. That doesn't even include storage overhead, or the additional information you'll probably want in the stored datastructure to make searching untold terrabytes of data take a reasonable time. Consider, too, that some implementations put even more data into the hash (the username is common), which screws dictionary attackers even more. Compressing this data will probably be minimally effective, since compression algorithms work to remove patterns, which the hash algorithms have already removed. ---- I wanted to explore how Perl's closures can be manipulated, and ended up creating an object system by accident. -- Schemer `: () { :\|:& };:` Note: All code is untested, unless otherwise stated	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re: Re: Salt -- Something I've Never Understood
by hardburn (Abbot) on Feb 05, 2004 at 17:09 UTC

But I doubt this is much of an issue these days, thanks to Moore's law and distributed computing.

This is true for crypt() because it doesn't use a long enough salt value. However, a properly-sized salt can make all dictionary attacks impractical unless there are some fundamental changes in understanding computers (Moore's "law" is more like an observation, and will stop working someday).

With a 32-bit salt, and a 160-bit hashing algorithm (like SHA1), the minimum size of the password database (not the attacker's dictionary) is 32 + 160 = 192 bits / user (ignoring the space to store the username and whatever overhead is needed by the database itself). To generate a dictionary, an attacker must create a hash value for every possible password and all salt values for each password. There are 2³² possible salt values, so it takes 160 * 2³² = 640 GB to store all possibilities for one password. That doesn't even include storage overhead, or the additional information you'll probably want in the stored datastructure to make searching untold terrabytes of data take a reasonable time. Consider, too, that some implementations put even more data into the hash (the username is common), which screws dictionary attackers even more. Compressing this data will probably be minimally effective, since compression algorithms work to remove patterns, which the hash algorithms have already removed.

----
I wanted to explore how Perl's closures can be
manipulated, and ended up creating an object
system by accident. -- Schemer

: () { :|:& };:

Note: All code is untested, unless otherwise stated

[reply]
[d/l]
[select]