Salt in encrypted password in pg_shadow

[Tom Lane]

Re: Salt in encrypted password in pg_shadow

Steve Atkins <steve@blighty. com> writes:[color=blue]
> If we need to tweak the authentication protocol _anyway_ at some
> point it'd be great to improve things. But until then... not worth
> the pain.[/color]

I've been hearing rumblings that MD5 and all other known crypto
protocols are known vulnerable since the latest crypto symposiums.
(Not that we didn't all suspect the NSA et al could break 'em, but
now they've told us exactly how they do it.)

So as soon as someone wheels up a new crypto hash method that looks
trustworthy, we can invent a new auth protocol and maybe throw in
another level of random salting while we're at it. But right now
I doubt it's worth the effort :-(

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 3: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to majordomo@postg resql.org so that your
message can get through to the mailing list cleanly

[Mike Nolan]

Re: Salt in encrypted password in pg_shadow

> So as soon as someone wheels up a new crypto hash method that looks[color=blue]
> trustworthy, we can invent a new auth protocol and maybe throw in
> another level of random salting while we're at it. But right now
> I doubt it's worth the effort :-([/color]

A relatively simple enhancement would be to use some or all of the user
name as the salt. That makes reverse engineering the passwords a bit
harder because there are multiple salts being used.

I suspect that with the speed of modern microprocessors that nearly any
crypto scheme is breakable using a few thousand dollars worth of hardware
and a few hours of time. If the NSA has built in shortcuts to their
sanctioned algorithms, that just makes the cracking process faster.

I know of an ecryption technique developed by a friend of mine, a retired
mathematician, that would probably be sufficiently robust. It uses group
theory to permutate the bit field and has both reversible and
non-reversible forms.

It would probably be subject to export restrictions. As I recall, he
couldn't even send a copy of the program to his son in Greece without
State Department approval.

But as long as people use vulnerable passwords, there is no password
encryption scheme that isn't vulnerable to attack, with or without
salt.

Challenge/response and one-time password schemes are more secure but
a lot more hassle for users.
--
Mike Nolan

---------------------------(end of broadcast)---------------------------
TIP 6: Have you searched our list archives?

http://archives.postgresql.org

[David Garamond]

Re: Salt in encrypted password in pg_shadow

Tom Lane wrote:[color=blue][color=green]
>>Hm, I thought the purpose of salt is generally well understood?[/color]
>
> Apparently not.
>
> The purpose of salting the encrypted passwords in pg_shadow is *not* to
> protect them against attackers who have somehow managed to
> illegitimately read pg_shadow. (As I explained before, such attackers
> are effectively superuser already, and so protecting the superuser
> password from them is not nearly as interesting as all that.) The
> purpose is to prevent unscrupulous DBAs from deducing the cleartext
> passwords being used by their users. Since the users presumably are not
> all named "postgres", the argument you are advancing is not relevant.[/color]

Then I'd say the purpose is wrong. There is not much hope in protecting
unscrupulous DBAs from getting their users' password anyway (they can
most probably sniff traffic, trap/log queries, or shut down postmaster
and replace it with a trojan binary).

The purpose of a salt, by most definition, should be to discourage
dictionary attack.

Anyway, I think we've agreed that the current protocol need not be
changed, on the basis of too much pain caused. But there's no reason not
to use random salt in future protocol. It offers the benefit you
mentioned plus protects against dictionary attack.

--
dave

---------------------------(end of broadcast)---------------------------
TIP 5: Have you checked our extensive FAQ?

http://www.postgresql.org/docs/faqs/FAQ.html

[Greg Stark]

Re: Salt in encrypted password in pg_shadow

Tom Lane <tgl@sss.pgh.pa .us> writes:
[color=blue]
> Greg Stark <gsstark@mit.ed u> writes:[color=green]
> > However with a known salt you only have to store the 1,000 hashes with the
> > known salt. You could instead store a dictionary of 64 million password
> > guesses in the same gigabyte.[/color]
>
> This is still not responding to my original point though: if you know
> the salt that was used, you can try brute-force scan of a few thousand
> probable passwords in less CPU time than it will take to read a gigabyte
> of precomputed hashes. The fact that common passwords are much shorter
> than the fixed-size MD5 hashes works against you in a big way.[/color]

We must be talking past each other. The threat model salts are meant to defend
against is someone who has access to the data in pg_shadow for many users.
Without the salts or with salts you can predict beforehand you look up the
hash value in your precomputed dictionary using an index and instantaneously
get a working password.

Postgres's current method is in fact doing it wrong. Because the salt is
predictable for the "postgres" users it doesn't protect against the attack
above. If I knew I could get access to lots of pg_shadow's, say I work at an
off-site backup storage company, I could check each of them instantaneously
against a precomputed index of hundreds of thousands of guessable passwords.
The same attack against a well salted hash would require running the entire
battery of hashes against each client's password individually.

The reason I say the threat model doesn't apply is only because it's unlikely
that someone would have access to many postgres installs's pg_shadow. That's
the only situation where that attack would arise. (Or if a given install had
hundreds of users with the same initial letters I guess, but that also seems
rare)

But if you're not going to worry about that threat then salting is buying you
nothing anyways. If you're going to use a salt you may as well use one that
accomplishes what it's there for.

--
greg


---------------------------(end of broadcast)---------------------------
TIP 7: don't forget to increase your free space map settings

[Bruno Wolff III]

Re: Salt in encrypted password in pg_shadow

On Wed, Sep 08, 2004 at 00:33:39 -0400,
Tom Lane <tgl@sss.pgh.pa .us> wrote:[color=blue]
>
> I've been hearing rumblings that MD5 and all other known crypto
> protocols are known vulnerable since the latest crypto symposiums.
> (Not that we didn't all suspect the NSA et al could break 'em, but
> now they've told us exactly how they do it.)[/color]

Things aren't currently that bad. So far people have found a way to find
two strings that give the same hash using MD5. They haven't yet found a way
to find a string which hashes to a given hash. SHA-0 was also shown to
have some weakness. From comments I have read, I don't think SHA-1 was
shown to have any weaknesses. One comment specifically mentioned that
the change made between SHA-0 and SHA-1 seems to have been made to address
the weakness found in SHA-0. I haven't read the source papers, so take this
all with a grain of salt.

---------------------------(end of broadcast)---------------------------
TIP 8: explain analyze is your friend

[Gaetano Mendola]

Re: Salt in encrypted password in pg_shadow

Bruno Wolff III wrote:
[color=blue]
> On Wed, Sep 08, 2004 at 00:33:39 -0400,
> Tom Lane <tgl@sss.pgh.pa .us> wrote:
>[color=green]
>>I've been hearing rumblings that MD5 and all other known crypto
>>protocols are known vulnerable since the latest crypto symposiums.
>>(Not that we didn't all suspect the NSA et al could break 'em, but
>>now they've told us exactly how they do it.)[/color]
>
>
> Things aren't currently that bad. So far people have found a way to find
> two strings that give the same hash using MD5. They haven't yet found a way
> to find a string which hashes to a given hash. SHA-0 was also shown to
> have some weakness. From comments I have read, I don't think SHA-1 was
> shown to have any weaknesses. One comment specifically mentioned that
> the change made between SHA-0 and SHA-1 seems to have been made to address
> the weakness found in SHA-0. I haven't read the source papers, so take this
> all with a grain of salt.[/color]

Well, when SHA-0 was ready NSA suggested to apply some changes in order to
correct some flaw discovered and SHA-1 comes out, interesting NSA never wrote
which flaw was corrected!
May be SHA-1 is trasparent water to NSA eyes :-)

I'm sure this entire thread will be stored somewhere else then archives...

Regards
Gaetano Mendola

[Greg Stark]

Re: Salt in encrypted password in pg_shadow

Gaetano Mendola <mendola@bigfoo t.com> writes:
[color=blue]
> Well, when SHA-0 was ready NSA suggested to apply some changes in order to
> correct some flaw discovered and SHA-1 comes out, interesting NSA never wrote
> which flaw was corrected!
> May be SHA-1 is trasparent water to NSA eyes :-)[/color]

This is awfully similar to the story that's told about DES:

When DES was under development the NSA told people to try a few specific
constants for the "sboxes" stage of the cipher. As far as anyone at the time
could tell they were completely random values and nearly any value would have
been just as good.

Then 30 years later when differential cryptanalysis was invented people found
the values the NSA told them to use are particularly resistant to differential
cryptanalysis attacks. Almost any other values and DES would have fallen right
then.

This means it's quite possible the NSA had differential cryptanalysis 30 years
before anyone else. Quite a remarkable achievement. However it's unlikely that
the same situation holds today. 30 years ago nobody outside the government was
doing serious cryptanalysis. If you were a mathematician interested in the
field you worked for the NSA or you changed fields. These days there's tons of
research in universities and in the private sector in serious cryptanalysis.
The NSA still employs plenty of good cryptanalysts but they no longer have the
monopoly they did back then.

--
greg


---------------------------(end of broadcast)---------------------------
TIP 9: the planner will ignore your desire to choose an index scan if your
joining column's datatypes do not match

[Gaetano Mendola]

Re: Salt in encrypted password in pg_shadow

Greg Stark wrote:
[color=blue]
> Gaetano Mendola <mendola@bigfoo t.com> writes:
>
>[color=green]
>>Well, when SHA-0 was ready NSA suggested to apply some changes in order to
>>correct some flaw discovered and SHA-1 comes out, interesting NSA never wrote
>>which flaw was corrected!
>>May be SHA-1 is trasparent water to NSA eyes :-)[/color]
>
>
> This is awfully similar to the story that's told about DES:
>
> When DES was under development the NSA told people to try a few specific
> constants for the "sboxes" stage of the cipher. As far as anyone at the time
> could tell they were completely random values and nearly any value would have
> been just as good.
>
> Then 30 years later when differential cryptanalysis was invented people found
> the values the NSA told them to use are particularly resistant to differential
> cryptanalysis attacks. Almost any other values and DES would have fallen right
> then.
>
> This means it's quite possible the NSA had differential cryptanalysis 30 years
> before anyone else. Quite a remarkable achievement. However it's unlikely that
> the same situation holds today. 30 years ago nobody outside the government was
> doing serious cryptanalysis. If you were a mathematician interested in the
> field you worked for the NSA or you changed fields. These days there's tons of
> research in universities and in the private sector in serious cryptanalysis.
> The NSA still employs plenty of good cryptanalysts but they no longer have the
> monopoly they did back then.[/color]

I will invite you to repeat the same sentence in 2034 ... :-)



Regards
Gaetano Mendola

[Greg Stark]

Re: Salt in encrypted password in pg_shadow


Chris Travers <chris@metatron tech.com> writes:
[color=blue]
> This only works because you have a theoretical delay between incorrect
> password attempts, so dictionary attacks directly are supposed to be
> difficult to impliment. I say theoretically because a smart attacker will
> use a program to open multiple telnet connections simultaneously to try a
> large number of passwords at once.[/color]

No, this is irrelevant to salts. People actually trying to log in is not the
threat model that salts are there to protect. This is not what is meant by
"dictionary attack".

What is meant by dictionary attack in the context of hashed passwords is
someone generating a "dictionary " of hashes for every guessable password. Then
they can take any hash they find in a password database and look up in their
"dictionary " a valid password it.

Salts prevent this by forcing someone to generate 2^16 possible hashes for
every possible guessable password. Essentially making them hash every
guessable password again anew for each user attacked.

They're only relevant for attackers who have access to the password database.
Not for attackers who are just knocking on the door over and over.

The weakness described would apply to someone who had access to many
pg_shadows from many installations. They could check every "postgres" user
against their dictionary quickly. Or an unscrupulous dba could assign
usernames starting with the same two letters for everyone and then guess
people's passwords by looking up the hashes in a dictionary.

--
greg


---------------------------(end of broadcast)---------------------------
TIP 1: subscribe and unsubscribe commands go to majordomo@postg resql.org

[Chris Travers]

Re: Salt in encrypted password in pg_shadow

Hi all;

With all due respect I generally side with Tom here.

Random salt values make sense in a few environments, for example, local
logins. They are designed to prevent someone from, say, copying the old
/etc/passwd or new /etc/shadow and then running an attack against the
passwords on it so that these passwords can be used to attack the
machine. This only works because you have a theoretical delay between
incorrect password attempts, so dictionary attacks directly are supposed
to be difficult to impliment. I say theoretically because a smart
attacker will use a program to open multiple telnet connections
simultaneously to try a large number of passwords at once.

Iirc, if PostgreSQL recieves a bad authentication attempt, it returns an
error and drops the connection. This is a double-edged sword
security-wise (allows for rapid dictionary attacks, but makes DoS a bit
less of a problem) and is a benefit performance-wise. So for the real
question: why would random salt values provide any security when it
would be less costly just to use a dictionary attack against account
itself? Given this model, it seems the only security benefit would be
that the attack Greg describes would be less likely to show up in the
logs. However, it could only work if the PostgreSQL instance is already
compromised, so this argument is somewhat moot. His argument seems to
be along the lines that the random salt in the /etc/shadow prevents root
from masquerading as any other user, which doesn't really work since
root can do this anyway. If an attacker can read pg_shadow, the fact
that the salt is not random is the least of your concerns.....

Best Wishes,
Chris Travers
Metatron Technology Consulting


Greg Stark wrote:
[color=blue]
>Tom Lane <tgl@sss.pgh.pa .us> writes:
>
>
>[color=green]
>>Greg Stark <gsstark@mit.ed u> writes:
>>
>>[color=darkred]
>>>However with a known salt you only have to store the 1,000 hashes with the
>>>known salt. You could instead store a dictionary of 64 million password
>>>guesses in the same gigabyte.
>>>
>>>[/color]
>>This is still not responding to my original point though: if you know
>>the salt that was used, you can try brute-force scan of a few thousand
>>probable passwords in less CPU time than it will take to read a gigabyte
>>of precomputed hashes. The fact that common passwords are much shorter
>>than the fixed-size MD5 hashes works against you in a big way.
>>
>>[/color]
>
>We must be talking past each other. The threat model salts are meant to defend
>against is someone who has access to the data in pg_shadow for many users.
>Without the salts or with salts you can predict beforehand you look up the
>hash value in your precomputed dictionary using an index and instantaneously
>get a working password.
>
>Postgres's current method is in fact doing it wrong. Because the salt is
>predictable for the "postgres" users it doesn't protect against the attack
>above. If I knew I could get access to lots of pg_shadow's, say I work at an
>off-site backup storage company, I could check each of them instantaneously
>against a precomputed index of hundreds of thousands of guessable passwords.
>The same attack against a well salted hash would require running the entire
>battery of hashes against each client's password individually.
>
>The reason I say the threat model doesn't apply is only because it's unlikely
>that someone would have access to many postgres installs's pg_shadow. That's
>the only situation where that attack would arise. (Or if a given install had
>hundreds of users with the same initial letters I guess, but that also seems
>rare)
>
>But if you're not going to worry about that threat then salting is buying you
>nothing anyways. If you're going to use a salt you may as well use one that
>accomplishes what it's there for.
>
>
>[/color]



---------------------------(end of broadcast)---------------------------
TIP 4: Don't 'kill -9' the postmaster

[Greg Stark]

Re: Salt in encrypted password in pg_shadow

Tom Lane <tgl@sss.pgh.pa .us> writes:
[color=blue][color=green]
> > it's unlikely that the same situation holds today.[/color]
>
> Why would you think that? The US government may not have too many
> clues, but they certainly understand the importance of crypto. I cannot
> think of any reason to suppose that NSA et al would have stopped
> spending serious effort in this area.[/color]

Certainly the NSA hasn't stopped spending serious effort. What's changed is
that now there is serious effort outside the NSA as well. In academia and the
private sector, not to mention other national governments.

That wasn't the case 30 years ago partially because the money just wasn't
there outside the NSA, and partially because the NSA was extremely persuasive
in hiring away anyone doing research. It's hard to do get ahead in
publish-or-perish academia when everything you're working on suddenly becomes
classified...
[color=blue]
> (Where "serious effort" is measured by the standard of "a billion here, a
> billion there, pretty soon you're talking about real money".)[/color]

Well there's a limit to how much you can spend on researcher salaries. There
are only so many researchers available to hire. Of course we don't know what
their full budget is but if it's in the billions (which it may well be) it's
probably mostly spent on operational costs, not research.
[color=blue]
> Quite honestly, as a US taxpayer I would not be happy if the NSA were
> not far ahead of public research in this field ...[/color]

It's presumably ahead. But not like the situation 30 years ago when they were
the only group doing this kind of research.

--
greg


---------------------------(end of broadcast)---------------------------
TIP 4: Don't 'kill -9' the postmaster

[Tom Lane]

Re: Salt in encrypted password in pg_shadow

Greg Stark <gsstark@mit.ed u> writes:[color=blue]
> This means it's quite possible the NSA had differential cryptanalysis
> 30 years before anyone else.[/color]

s/quite possible/known fact/
[color=blue]
> Quite a remarkable achievement. However
> it's unlikely that the same situation holds today.[/color]

Why would you think that? The US government may not have too many
clues, but they certainly understand the importance of crypto. I cannot
think of any reason to suppose that NSA et al would have stopped
spending serious effort in this area. (Where "serious effort" is
measured by the standard of "a billion here, a billion there, pretty
soon you're talking about real money".)

Quite honestly, as a US taxpayer I would not be happy if the NSA were
not far ahead of public research in this field ...

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 4: Don't 'kill -9' the postmaster