virtue of salted passwords
 

I'm a little confussed as to what the point of a salt is. If someone
could get a password hash, couldn't they get the salt, as well? Once
they have the salt, it kinda becomes pointless...

Re: virtue of salted passwords
 

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

In alt.computer.security, yawnmoth dared to utter,
> I'm a little confussed as to what the point of a salt is.

Salt is just a small bit of (hopefully) completely random data that is
to be dropped in place wherever you need randomness. Encryption is
obviously one of those areas. The idea is that a salt should be
created from completely random actions[0] so that it becomes more
difficult for an attacker to crack the encryption by introducing
irregularity into the equation.

http://www.catb.org/~esr/jargon/html/S/salt.html

[0] Generally speaking, gibberish entered at the keyboard. Other ways
of generating a salt include analyzing mouse gestures and even
analyzing the state of a lava lamp! The lava lamp idea is actually
patented in the US, IIRC.

- --
It is better to hear the rebuke of the wise,
Than for a man to hear the song of fools.
Ecclesiastes 7:5
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.7 (GNU/Linux)

iD8DBQFDggL6zLTO1iU1uO4RAq0aAJ9rqtSDezhf5AuUxBZnow m26JV+zgCgvXl2
BuMfpcedzYhPd3cub+XZxhA=
=0l1r
-----END PGP SIGNATURE-----

Re: virtue of salted passwords
 

+Alan Hicks+ wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> In alt.computer.security, yawnmoth dared to utter,
> > I'm a little confussed as to what the point of a salt is.
>
> Salt is just a small bit of (hopefully) completely random data that is
> to be dropped in place wherever you need randomness. Encryption is
> obviously one of those areas. The idea is that a salt should be
> created from completely random actions[0] so that it becomes more
> difficult for an attacker to crack the encryption by introducing
> irregularity into the equation.
>
> http://www.catb.org/~esr/jargon/html/S/salt.html
>
> [0] Generally speaking, gibberish entered at the keyboard. Other ways
> of generating a salt include analyzing mouse gestures and even
> analyzing the state of a lava lamp! The lava lamp idea is actually
> patented in the US, IIRC.

Correct me if I'm wrong, but if an attacker has the salt, it becomes
useless, doesn't it? If so, then why can't a would-be attacker get the
salt at the same time that he's getting the password hash?

Re: virtue of salted passwords
 

In the Usenet newsgroup alt.computer.security, in article
<1132550886.235721.210200@g43g2000cwa.googlegroups .com>, yawnmoth wrote:

>I'm a little confussed as to what the point of a salt is.

To make the raw password become one of a great many possible answers.
On the original UNIX 'crypt(3)' style passwords, the two character salt
would take the password "AAAAAAAA" and hash it to one of 4096 possible
answers. This makes dictionary attacks (where the attacker has every
possible hashed password, and what 'raw' password would make that hash)
difficult.

>If someone could get a password hash, couldn't they get the salt, as
>well?

No - because you still have to figure out what raw password, when hashed
with this salt would result in that hash. Remember, you can't go in the
opposite direction - starting with the chopped up meat and potatoes and
salt, and get back to the original shape of the potato or the piece of
cow (or what-ever) the chef stated with. They're called a one-way hash
for a reason.

>Once they have the salt, it kinda becomes pointless...

Got a really fast computer, huh? Maybe a search on google for the words
'password hash salt' would be enlightening.

Remember, the original UNIX password algorithm took the first eight
characters of the user's raw password, and two characters of salt, and
the result was a bit longer than 10 characters - care to think why?
Also be aware that modern systems use a different algorithm, such as
a modified MD5 hash, or blowfish to accept more character in, and a
longer hash out.

Old guy

Re: virtue of salted passwords
 

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

In alt.computer.security, yawnmoth dared to utter,
> Correct me if I'm wrong, but if an attacker has the salt, it becomes
> useless, doesn't it?

Well the purpose of a salt is to reduce regularity, so if an attacker
knows the salt, the salt is pretty much useless, IIUC.

> If so, then why can't a would-be attacker get the
> salt at the same time that he's getting the password hash?

Not necessarily. Password hashes can be retrieved in any number of
ways. There are no garauntees that an attacker who can find a password
hash would also retrieve the salt at the same time.

- --
It is better to hear the rebuke of the wise,
Than for a man to hear the song of fools.
Ecclesiastes 7:5
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.7 (GNU/Linux)

iD8DBQFDgipFzLTO1iU1uO4RAiWSAKCOU6CIjbuGDFaJPvDSNN 5UHi97BACdErA1
f0ktwGh1qkHQqXISlfk2Mtg=
=+dJY
-----END PGP SIGNATURE-----

Re: virtue of salted passwords
 

Moe Trin wrote:
> In the Usenet newsgroup alt.computer.security, in article
> <1132550886.235721.210200@g43g2000cwa.googlegroups .com>, yawnmoth wrote:
> <snip>
> >If someone could get a password hash, couldn't they get the salt, as
> >well?
>
> No - because you still have to figure out what raw password, when hashed
> with this salt would result in that hash. Remember, you can't go in the
> opposite direction - starting with the chopped up meat and potatoes and
> salt, and get back to the original shape of the potato or the piece of
> cow (or what-ever) the chef stated with. They're called a one-way hash
> for a reason.
>
> >Once they have the salt, it kinda becomes pointless...
>
> Got a really fast computer, huh? Maybe a search on google for the words
> 'password hash salt' would be enlightening.
I think you misunderstand the question. If you have the salt (although
salts may be randomly assigned, once they're assigned, they shouldn't
change) and the password hash, all you need to do to do a dictionary
search is to append the salt to every word. If the salt is '4d', don't
try passwords like 'aardvark', 'abascus', or whatever - try passwords
like 'aardvark4d' and 'abascus4d'. ie. append '4d' to every word.

Of course, you don't even need the salt to do this. If you login by
sending TCP packets that include the password to some computer, that
computer is going to have to append the salt to the password. If it
doesn't, then not even the original person who chose the password would
be able to login (unless he knew the salt, of course).

The recieving computer can't apply the salt only to the right password,
either, because it has no way of knowing whether or not the submitted
password even was the correct one until after the salts been applied.

So, if you're doing a dictionary attack the same way that a normal user
would log in, salting is equally useless.

Also, your suggestion of doing a google search for 'password hash salt'
doesn't really yield any hits that discuss the above.

Re: virtue of salted passwords
 

+Alan Hicks+ wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> <snip>
> Not necessarily. Password hashes can be retrieved in any number of
> ways. There are no garauntees that an attacker who can find a password
> hash would also retrieve the salt at the same time.

Any ideas as to how to make it harder to retrieve salts for web
applications? One idea would be to have two seperate databases with
different passwords. One database would contain the salt and the other
would contain the hash. Although this would make it that much harder
for both to be revealed via sql injection, it doesn't really seem all
that feasable a solution. Another idea would be to store salts using
text files and hashes in databases...

Re: virtue of salted passwords
 

In the Usenet newsgroup alt.computer.security, in article
<1132610312.778021.29070@g49g2000cwa.googlegroups. com>, yawnmoth wrote:

>I think you misunderstand the question. If you have the salt (although
>salts may be randomly assigned, once they're assigned, they shouldn't
>change) and the password hash, all you need to do to do a dictionary
>search is to append the salt to every word. If the salt is '4d', don't
>try passwords like 'aardvark', 'abascus', or whatever - try passwords
>like 'aardvark4d' and 'abascus4d'. ie. append '4d' to every word.

No, you don't understand how the password algorithms work. Salt does not
get attached to the password that you would be trying. It doesn't matter
which of the 4096 salts are used - the _user_ only has that initial
word. Note - I'm talking the old fashioned crypt(3) style passwords,
though the MD5 or Blowfish algorithms are similar in function. Which
algorithm should you be using? They result in quite different hashes.

When you try to connect, the login authentication takes the characters
you keyed in, grabs the salt from the password (or much more common now,
the shadow file), hammers them together, and hashes that. It then
compares the result of the hashing with the data in the {passwd|shadow}
file. If the hash just created matches - you're in. If it doesn't,
the user gets a "Login Incorrect" message (the same as if you also
supplied a bad username).

>Of course, you don't even need the salt to do this. If you login by
>sending TCP packets that include the password to some computer, that
>computer is going to have to append the salt to the password. If it
>doesn't, then not even the original person who chose the password would
>be able to login (unless he knew the salt, of course).

The user has no need to know (and may know only the most rare occasion)
the value of the salt.

The reason for the salt was that originally, the password file was
viewable by everyone (it still is), because everyone needed to know
data in certain fields (UID to username for directory listings being
one example). This exposed the hashed password. Modern systems use a
shadowed password file that is only readable by 'root' (the authentication
application runs with root access).

[compton ~]$ ls -l /etc/passwd /etc/shadow
-rw-r--r-- 1 root root 17444 Nov 13 09:40 /etc/passwd
-rw------- 1 root root 6693 Nov 19 19:15 /etc/shadow
[compton ~]$ grep root /etc/passwd /etc/shadow
root:x:0:0:root:/root:/bin/bash
grep: /etc/shadow: Permission denied
[compton ~]$

Thus, in the old days, you had the hashed password and the salt, but what
raw password did that mean? So, what you did was to start with 'A' and
work through the alphabet to 'zzzzzzzz' and try that. This is why I spoke
of having a fast computer. If you exclude a few of the control characters
that shouldn't be used, you've got something like 90 character and if you
use a six character string of those 90 characters, you get (are you ready?)
10804695562359870518299193703899148848724015728610 899282651377959960576
different passwords (that is 6^90, which my small calculator says is
1.0805 x 10^70), and that's before we start mucking with salt. The password
algorithm is intentionally convoluted to take extra time. However, if the
user uses the 'passwd' command to change to a new password, EVEN IF THEY
KEY IN THE SAME PASSWORD AS BEFORE, the mechanism will have only 1 chance
in 4096 in producing the same hash (the salt is chosen randomly). Now your
old password will work even though the salt has changed. The problem is
that your dictionary is now missing the new hash. You can't look at the
hash 'H50eMz5u9P1U4' and say "that is the hash of 'foo'", because there
are 4096 different hashes that are foo (even assuming someone used such
an easy password).

Also, there are password Nazi programs that monitor passwords, requiring
when you create (or change) the password that the new one has certain
characteristics - such as a minimum length (usually 6 or more characters),
2 digits and one punctuation character embedded, and mixed upper and lower
case. Some take it further that the raw password can't be a word that
appears in /usr/share/dict/words - on my system, that has over 200,000
words in English. Still others require that the password can't be one that
the user has used previously for some period, or some number of changes.

>Also, your suggestion of doing a google search for 'password hash salt'
>doesn't really yield any hits that discuss the above.

OK - try looking for 'Jack the Ripper' (or the more modern version called
'John the ripper', which are password cracking applications. There really
is a lot of documentation on this, as the implementation goes back over
35 years, and has been subject to literally hundreds of papers.

Old guy

Re: virtue of salted passwords
 

Moe Trin wrote:
> In the Usenet newsgroup alt.computer.security, in article
> <1132610312.778021.29070@g49g2000cwa.googlegroups. com>, yawnmoth wrote:
>
> <snip>
>
> The user has no need to know (and may know only the most rare occasion)
> the value of the salt.
>
> The reason for the salt was that originally, the password file was
> viewable by everyone (it still is), because everyone needed to know
> data in certain fields (UID to username for directory listings being
> one example). This exposed the hashed password. Modern systems use a
> shadowed password file that is only readable by 'root' (the authentication
> application runs with root access).
>
> [compton ~]$ ls -l /etc/passwd /etc/shadow
> -rw-r--r-- 1 root root 17444 Nov 13 09:40 /etc/passwd
> -rw------- 1 root root 6693 Nov 19 19:15 /etc/shadow
> [compton ~]$ grep root /etc/passwd /etc/shadow
> root:x:0:0:root:/root:/bin/bash
> grep: /etc/shadow: Permission denied
> [compton ~]$
>
> Thus, in the old days, you had the hashed password and the salt, but what
> raw password did that mean? So, what you did was to start with 'A' and
> work through the alphabet to 'zzzzzzzz' and try that. This is why I spoke
> of having a fast computer. If you exclude a few of the control characters
> that shouldn't be used, you've got something like 90 character and if you
> use a six character string of those 90 characters, you get (are you ready?)
> 10804695562359870518299193703899148848724015728610 899282651377959960576
> different passwords (that is 6^90, which my small calculator says is
> 1.0805 x 10^70), and that's before we start mucking with salt. The password
> algorithm is intentionally convoluted to take extra time. However, if the
> user uses the 'passwd' command to change to a new password, EVEN IF THEY
> KEY IN THE SAME PASSWORD AS BEFORE, the mechanism will have only 1 chance
> in 4096 in producing the same hash (the salt is chosen randomly). Now your
> old password will work even though the salt has changed. The problem is
> that your dictionary is now missing the new hash. You can't look at the
> hash 'H50eMz5u9P1U4' and say "that is the hash of 'foo'", because there
> are 4096 different hashes that are foo (even assuming someone used such
> an easy password).
>
> Also, there are password Nazi programs that monitor passwords, requiring
> when you create (or change) the password that the new one has certain
> characteristics - such as a minimum length (usually 6 or more characters),
> 2 digits and one punctuation character embedded, and mixed upper and lower
> case. Some take it further that the raw password can't be a word that
> appears in /usr/share/dict/words - on my system, that has over 200,000
> words in English. Still others require that the password can't be one that
> the user has used previously for some period, or some number of changes.

I'm not really sure what the vast majority of your points have to do
with my original post. I'm not saying that brute forcing passwords is
going to be easy if you have a salt. I'm saying that it will be easier
than it would have otherwise been. If there are 4096 possible salts
and 6^90 possible passwords (before salting), then, if you don't know
the salt, you have to try 4096*6^90 possible character combinations.
If you know the salt, you only have to try 6^90. 4096*6^90 is clearly
greater than 6^90, hence having a salt makes things easier.

Alternatively, if we assume that the user in question chose the
password from a 200,000 word dictionary (this isn't really all that
unreasonable an assumption), then there are going to be 200000*4096
possible character combinations, if you don't know the salt. If you do
know the salt, there will only be 200000. Since 200000*4096 is greater
than 200000, knowing the salt makes things easier.

You recommended that I look up Jack the Ripper and see how that works.
Will doing so make 200000*4096 less than 200000? If not, then I'm not
really sure what the point of your recommendation was, either.

Re: virtue of salted passwords
 

On 21 Nov 2005, in the Usenet newsgroup alt.computer.security, in article
<1132629459.063922.307670@z14g2000cwz.googlegroups .com>, yawnmoth wrote:

>I'm not really sure what the vast majority of your points have to do
>with my original post. I'm not saying that brute forcing passwords is
>going to be easy if you have a salt.

Based on your response to Alan, I suspect you are not referring to the
classic UNIX passwd mechanism, as you are referring to web pages. As
mentioned, in UNIX, if you have the hash, you also have the salt as
under the old crypt (3) style, the salt is the first two characters,
and the remaining 11 characters is the hash. MD5, Blowfish, et.al. are
similar.

>If there are 4096 possible salts and 6^90 possible passwords (before
>salting), then, if you don't know the salt, you have to try 4096*6^90
>possible character combinations. If you know the salt, you only have to
>try 6^90. 4096*6^90 is clearly greater than 6^90, hence having a salt
>makes things easier.

No - because you don't worry about the salt at all. User A has a password
of "password", and it's been encrypted to something - say "xSVPzKH9J8Sts".
You plug your English dictionary into the cracking program, which takes
the first two characters of that string (xS), and does the hashing. All
the system cares is if the resulting hash is "VPzKH9J8Sts". If it is,
then this is the correct password. If it's not, then try the next word.

The idea of the salt is that you don't have "current access" to the file,
but are going to create a dictionary of all possible hashed passwords, so
that _WHEN_ you gain access to the file, you can look at "CAARbkve6pHE3"
and say "that password is <Mumble>". If you have "current access" to
the file, you don't need that monstrous list of the gazillion different
13 character strings that you would find in that password field.

What is it that you are trying to do? Invent a password algorithm for
your web site that will be more secure (more secure than what?), or
understand how existing systems (which one[s]) work? Or what? The old
UNIX style passwords use salt, but not that many others do - depending
on a single hashing algorithm because if someone has gotten access to
the store of encrypted|hashed|what-ever passwords, they already own the
system, and don't need the password. Case in point - the UNIX root
user (as well as the Novell administrator) can use a command like 'su -'
and become any user without needing to know the user's password (knowing
their own root|administrator password is sufficient). Getting more
complicated than that (with Access Control Lists for example) can
prevent this, but at a cost of vastly more complexity and often much
less usefulness. You mention putting the salt in a separate file
from the hash - in a practical sense (people do change passwords), it's
not going to make a difference, because if you gain access to either
file, you already have access to the other. Thing it, as a user on the
system, you don't have access to where the passwords are stored. IF YOU
DO, then you're already root, and don't need it. And yes, we do try to
keep the backup tapes in a secure location, so you can't just stuff the
tape into your system and grab the file.

Old guy