----- Original Message ----- From: "Tero Kivinen" <[EMAIL PROTECTED]>
Sent: Monday, October 15, 2007 5:47 AM
Subject: Re: Password hashing

Joseph Ashwood writes:
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.


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 [EMAIL PROTECTED]

Reply via email to