Password hashing

A proposal for a new password hashing based on SHA-256 or
SHA-512 has  
been proposed by RedHat but to my knowledge has not had any
rigorous  
analysis. The motivation for this is to replace MD-5 based
password  
hashing at banks where MD-5 is on the list of "do not
use" algorithms.  
I would prefer not to have the discussion "MD-5 is good
enough for  
this algorithm" since it is not an argument that the
customers  
requesting these changes are going to accept.

Jim

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography"
to majordomometzdowd.com

This might work, although 90% of the steps seem to
unnecessarily (and  
perilously) complicate the algorithm.  What's wrong with
starting  
with input SALT || PASSWORD and iterating N times, where N
is chosen  
(but variable) to make brute-force attacks take longer?  It
seems  
like the designers are trying to specify a cryptographic
hash  
algorithm...where they make black box calls to SHA-256 or
SHA-512.   
It's much simpler to just let SHA-256 and SHA-512 do the
work.

Adding a requirement that the salt be 128 bits (or more)
would  
improve the security against brute-force attacks more than
any of the  
other (convoluted) parts of the algorithm.  I suppose one
could argue  
that 8 ASCII characters for the salt is relatively secure
today, but  
what about in 20 years?

Martin

On Oct 11, 2007, at 11:49 PM, james hughes wrote:

> I forgot to add the links...
> 	http:
//people.redhat.com/drepper/sha-crypt.html
> 	http:/
/people.redhat.com/drepper/SHA-crypt.txt
>
> On Oct 11, 2007, at 10:19 PM, james hughes wrote:
>
>> A proposal for a new password hashing based on
SHA-256 or SHA-512  
>> has been proposed by RedHat but to my knowledge has
not had any  
>> rigorous analysis. The motivation for this is to
replace MD-5  
>> based password hashing at banks where MD-5 is on
the list of "do  
>> not use" algorithms. I would prefer not to
have the discussion  
>> "MD-5 is good enough for this algorithm"
since it is not an  
>> argument that the customers requesting these
changes are going to  
>> accept.
>>
>> Jim
>>
>


------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography"
to majordomometzdowd.com

On Thu, 11 Oct 2007 22:19:18 -0700
james hughes <hughejpmac.com> wrote:

> A proposal for a new password hashing based on SHA-256
or SHA-512 has
> been proposed by RedHat but to my knowledge has not had
any rigorous
> analysis. The motivation for this is to replace MD-5
based password
> hashing at banks where MD-5 is on the list of "do
not use"
> algorithms. I would prefer not to have the discussion
"MD-5 is good
> enough for this algorithm" since it is not an
argument that the
> customers requesting these changes are going to
accept.
> 
NetBSD uses iterated HMAC-SHA1, where the password is the
key and the
salt is the initial plaintext.  (This is my design but not
my
implementation.)


		--Steve Bellovin, http://www.cs.columbi
a.edu/~smb

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography"
to majordomometzdowd.com

I would have thought PBKDF2 would be the obvious,
standardized (PKCS
#5 / RFC 2898) and designed for purpose method to derive a
key from a
password.  PBKDF2 would typically be based on HMAC-SHA1.

Should be straight-forward to use PBKDF2 with HMAC-SHA-256
instead for
larger key sizes, or for avoidance of SHA1 since the partial
attacks
on it.

Adam

On Thu, Oct 11, 2007 at 10:19:18PM -0700, james hughes
wrote:
> A proposal for a new password hashing based on SHA-256
or SHA-512 has  
> been proposed by RedHat but to my knowledge has not had
any rigorous  
> analysis. The motivation for this is to replace MD-5
based password  
> hashing at banks where MD-5 is on the list of "do
not use" algorithms.  
> I would prefer not to have the discussion "MD-5 is
good enough for  
> this algorithm" since it is not an argument that
the customers  
> requesting these changes are going to accept.

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography"
to majordomometzdowd.com

On Thu, 11 Oct 2007, james hughes wrote:

> I forgot to add the links...
> 	http:
//people.redhat.com/drepper/sha-crypt.html
> 	http:/
/people.redhat.com/drepper/SHA-crypt.txt
> 
> On Oct 11, 2007, at 10:19 PM, james hughes wrote:
> 
> > A proposal for a new password hashing based on
SHA-256 or SHA-512 has been
> > proposed by RedHat but to my knowledge has not had
any rigorous analysis.
> > The motivation for this is to replace MD-5 based
password hashing at banks
> > where MD-5 is on the list of "do not
use" algorithms. I would prefer not to
> > have the discussion "MD-5 is good enough for
this algorithm" since it is not
> > an argument that the customers requesting these
changes are going to accept.

Some comments:

* Use of an off-the-shelf algorithm like SHA1 might be nice
for "tick here
  for FIPS certification", but they render the hashing
scheme more
  vulnerable to dictionary attacks assisted by
(near-)commodity hardware.
  Contrast with OpenBSD's blowfish scheme, which is
deliberately designed
  to not be implementable using off-the-shelf crypto
accelerator chips.

* Hideously obfuscated and overcomplicated. Comments like
those on step 11
  of the algorithm (some mumbo jumbo about a completely
deterministic step
  "adding randomness") and the absence of any
rationale for the complexity
  seem to indicate that they believe a complicated design
will somehow
  thwart attacks by itself.

* Why specify the number of rounds directly? Most password
and KDF schemes
  use an exponential scheme to match Moore's law.

-d

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography"
to majordomometzdowd.com

On 10/13/07, Martin James Cochran <Martin.Cochrancolorado.edu> wrote:

> ...  What's wrong with starting
> with input SALT || PASSWORD and iterating N times,
....

Shouldn't it be USERID || SALT || PASSWORD to guarantee that
if
two users choose the same password they get different
hashes?
It looks to me like this wold make dictionary attacks harder
too.

-- 
Sandy Harris,
Nanjing, China

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography"
to majordomometzdowd.com

On Oct 12, 2007, at 6:47 PM, Sandy Harris wrote:

> On 10/13/07, Martin James Cochran
<Martin.Cochrancolorado.edu> wrote:
>
>> ...  What's wrong with starting
>> with input SALT || PASSWORD and iterating N times,
....
>
> Shouldn't it be USERID || SALT || PASSWORD to guarantee
that if
> two users choose the same password they get different
hashes?
> It looks to me like this wold make dictionary attacks
harder too.

If the salt space is large enough ( > 128 bits, say) and
the salts  
are generated with a good source of randomness, then it's  
overwhelmingly likely that an attacker will have to do a
dictionary  
attack per user anyway, even across many different machines.
 Also,  
with such a large salt space it's extremely unlikely that
users who  
choose the same passwords will have the same salt.


------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography"
to majordomometzdowd.com

> A proposal for a new password hashing based on SHA-256
or SHA-512 has  
> been proposed by RedHat but to my knowledge has not had
any rigorous  
> analysis. The motivation for this is to replace MD-5
based password  
> hashing at banks where MD-5 is on the list of "do
not use" algorithms.  
> I would prefer not to have the discussion "MD-5 is
good enough for  
> this algorithm" since it is not an argument that
the customers  
> requesting these changes are going to accept.

	blowfish anyone?
	http://www.usenix.org/events/usenix99/provos/provos_htm
l/

itojun

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography"
to majordomometzdowd.com

Just combining several of my thoughts into a single email.

On the Red Hat proposal:
Why does every undereducated person believe that
complexity==security? It is 
far better to rely on little things called
"proofs." There are several 
proofs out there with significant impact on this. In
particular the really 
nice HMAC proof. The absurd complexity makes it highly
likely that there is 
at least some shortcut in it that hasn't been seen yet.

On SALT || PASSWORD:
In doing that you are assuming collision resistence, and no
shortcuts in 
computation. It is better than the RedHat proposal, but not
optimal.

On NetBSD HMAC-SHA1:
There is a shortcut in the design as listed, using the
non-changing password 
as the key allows for the optimization that a single HMAC
can be keyed, then 
copied and reused with each seed. this shortcut actually
speeds attack by a 
factor of 3. The fix is to use the salt as the HMAC key,
this assumes much 
less of the hash function.

On PDKDF2:
Also appears to suffer from the same precomputation flaw,
possibly more I 
haven't looked at it too closely for this purpose.

On USERID || SALT || PASSWORD:
Close, anything that is fixed (USERID and PASSWORD) should
be put at the 
end, so the there is round to round variation before it,
preventing 
precomputation. It also assumes the same collision
resistence and no 
shortcut.


The better solution, with aspects borrowed from the others:
IV[0] = Salt
IV[i] = HMAC(key=IV[i-1], data=USERID||PASSWORD)
PasswordHash=IV[k]

Of course nonambiguous formatting for USERID||PASSWORD is
necessary to avoid 
any shortcuts or precomputations, but any nonambiguous
method is sufficient, 
including a fixed length USERID.

By using an HMAC instead of just a hash function allows it
to make use of 
most of the HMAC proof, reducing the assumptions on the
underlying hash to 
the effective minimum. By ordering everything to place the
SALT and later 
prior result as the HMAC key this prevents any
precomputation under the 
assumption that there is no method of computing the hash
shorter than 3 hash 
compression iterations, a quite small window of opportunity,
and any result 
will likely benefit the rightful computation of the
PasswordHash resulting 
in a simple increase in the value of k.
                    Joe 

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography"
to majordomometzdowd.com