Password hashing
Joseph Ashwood
ashwood at msn.com
Mon Oct 15 22:12:53 EDT 2007
----- 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
More information about the cryptography
mailing list