Password hashing

[Joseph Ashwood]

----- Original Message ----- 
From: "Tero Kivinen" <kivinen at iki.fi>
Sent: Monday, October 15, 2007 5:47 AM
Subject: Re: Password hashing


> Joseph Ashwood writes:
>> 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.
>
> When you are trying to crack password, you do know the SALT and
> iteration count. You do not know the password. You need to try all
> possible passwords with different salts. As we use the password we are
> trying as an input to our test function we need to initialize
> hmac_sha1 again for each pasword we are guessing. Or did I understand
> something wrong.
>
> With your fix I could take the SALT from the passwd string and
> initialize first level of hmac with it and then feed different
> password to it.

It is true that the first two iterations of the compression function in my 
supplied solution are computationally irrelevant, while in the current 
design the first two are computationally relevant, but the second time 
through the HMAC the situation reverses, the password keyed HMAC has exactly 
the same pre-salt state as the in the first HMAC iteration, and so in the 
second and subsequent HMAC iteration the first two applications of the 
compression function are computationally irrelevant, but in my solution 
there is no prior knowledge of the key for the second and subsequent HMAC 
iteration and so the first two applications of the compression function are 
computationally relevant. So my given solution trades the computation in the 
first two compression function computations for the millions of subsequent 
compression function computations. Asymptotically this is a 3 fold 
improvement, and so it is a very good change.

It is also worth noting that most passwords, even so called "good" 
passwords, have only a small amoutn of entropy, and a 50,000 word list will 
contain a significant number of all passwords on a system, there are more 
salts, and so storing the precomputations of the passwords versus the 
precomputations of even a 32-bit salt is radically different.

>
>> On USERID || SALT || PASSWORD:
>
> Adding USERID to the calculations will firstly break API
> compatibility, as the crypt function do not know the userid.

There is a choice, do it right, or keep the API. I am firmly on the side of 
doing it right. While the USERID is irrelevant if the SALT can be made to 
never repeat, that is a very hard thing to truly accomplish, especially 
across multiple disconnected systems.

> It will
> also break the ability to copy the encrypted passwords from one
> machine to other,

So it prevents people from doing something that is poor security.

> even when you would need to change user id in the
> progress (If I need to set up account for someone on my machines, I
> usually either ask them to send me already encrypted password I can
> put in to my /etc/password, or ask them to send me ssh public key...

While the design is being changed (as you noted making this change would 
necessitate other changes) it is worthwhile to eliminate other security poor 
decisions as well.
                Joe 

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com