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. On USERID || SALT || PASSWORD: Adding USERID to the calculations will firstly break API compatibility, as the crypt function do not know the userid. It will also break the ability to copy the encrypted passwords from one machine to other, 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... -- [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Password hashing
Martin James Cochran [EMAIL PROTECTED] writes: 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? Or just use PBKDF2, RFC 2898. It does what's required, has been vetted by cryptographers, is an IETF standard, has free implementations available, ... Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Password hashing
| ... 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. As others have pointed out, with a large enough salt, dictionary attacks become impossible. But it's worth mentioning another issue: People's userid's do change and it's nice not to have the hashed passwords break as a result. (This is pretty counter-intuitive to users who change their names, and a disaster if a large organization needs to do a mass renaming and somehow has to coordinate a mass password update at the same time.) -- Jerry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Password hashing
- Original Message - From: Tero Kivinen [EMAIL PROTECTED] 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 [EMAIL PROTECTED]
Re: Password hashing
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 [EMAIL PROTECTED]
Re: Password hashing
Steven M. Bellovin wrote: On Thu, 11 Oct 2007 22:19:18 -0700 james hughes [EMAIL PROTECTED] 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.) +1 to iterated HMAC-xxx, where xxx is a cryptographic hash of your choosing. Easy to implement, hard to get wrong, somewhat understood security properties. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.links.org/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Password hashing
- Original Message - From: Jim Gellman [EMAIL PROTECTED] To: Joseph Ashwood [EMAIL PROTECTED] Cc: Cryptography cryptography@metzdowd.com Sent: Saturday, October 13, 2007 1:25 PM Subject: Re: Password hashing I'm not sure I follow your notation. Are you saying that IV[n] is the n'th application of the compression function? No, each application of the HMAC is seperate, this is to incur the finalization penalty in the computation. if you want it closer to implementation: IV = SALT for(n iterations) IV = HMAC(key=IV, data=USERID||PASSWORD) PasswordHash=IV Why put each field in it's own block? It really is to incur as many necessary performance penalties as possible. The HMAC keying requires 2 compressions, then the USERID||PASSWORD formatting can be created to make it consistently 2 more compressions, and a finalization per round. More inflation is of course possible, but I don't think it is reasonable, too much possibility of stretching too far, giving too much leverage for an attack on the compression function (i.e. the more times you use the compression function the more likely a shortcut exists, but by resetting the state such attacks become much less likely). Joe - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Password hashing
This does not extend the discussion at hand, but it might be useful to some here who may have to deal with FIPS 140-2. On 13 Oct 2007 09:32:44 +1000, Damien Miller wrote: 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. Although there are password hashing mechanisms built from FIPS-approved algorithms (e.g., SHA-1 HMAC), there are no FIPS-approved password hashing mechanisms specifically defined. Meaning, I think there is some room to move here. Now, assuming passwords are a critical security parameter (CSP) for a module, password hashing built from non-FIPS-approved algorithms automatically means the generated password hashes are considered to be CSPs in the clear for FIPS 140-2 purposes (i.e., the password hashes are just considered to an obfuscated form of the plaintext password), and so we have to deal with the requirements revolving around plaintext CSPs for those password hashes. Inside of the cryptographic boundary of a module, CSPs can be maintained in plaintext, as they are considered protected by the security mechanisms of the module, which gives us a foothold for using such password hashing mechanisms. However, while the passwords are considered in the clear, the fact they are undergoing password hashing is not ignored - the authentication mechanism must still meet the applicable authentication requirements of FIPS 140-2, so the password hashing must not cause the password-based authentication to fail to meet those FIPS 140-2 requirements. And, I think password hashing mechanisms built from non-FIPS-approved algorithms can still be used to help meet some FIPS 140-2 authentication requirements - e.g, I can envision bcrypt being configured such that, given a particular module's hardware, it slows does authentication attempts sufficiently to satisfy some strength of authentication requirements. -Andrew - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Password hashing
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
Re: Password hashing
On Thu, 11 Oct 2007 22:19:18 -0700 james hughes [EMAIL PROTECTED] 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.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Password hashing
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 [EMAIL PROTECTED]
