3

Could I replace password hashing with the following strategy:

  • Generate a public/private key pair, store the public key as the "salt" and destroy the private key. Maybe we could even not generate the private key in the first place (we only need to know it mathematically exists).
  • To store a password: encrypt the password using the public key. That is practically irreversible as nobody has the private key.
  • To authenticate: encrypt the potential password with the same public key then compare it to the stored encrypted password. This assume the asymmetric cryptographic algorithm always produce the same encrypted text for a given clear text. (i.e. that encryption is a function)

This would provide the following advantages:

  1. Asymmetric cryptography is usually more expensive than hashing and should therefore require less stretching for the same benefits.
  2. Stronger guarantee on the entered password: there is one and only one password which can be accepted. That is, no collision can be accepted (contrary to hashing functions) as else the decrypted password would not be unique.

The main disadvantage I see is that the stored password length is correlated to actual password length, giving a clue on password strength. This can be mitigated by introducing a "lengthy" salt to the password, which will ensure that short password only look as short as the salt. Long password remain mostly unaffected but that is fine as they are long but might take space in the database.

Are there any other disadvantages to this technique?

I am guessing this has already been studied but I didn't find the name of such strategy.

Nonyme
  • 133
  • 4

2 Answers2

3

TL;DR

  1. The disadvantage you mention is less relevant than you think.

  2. The bigger disadvantage to Asymmetric Encryption is that it's quite a bit cheaper than a properly configured Slow Password Hash.

So, you should use a Slow Password Hash. (i.e. BCrypt)

Theoretically, using an Asymmetric encryption routine (where the Private Key is permanently forgotten) is a reasonably secure one-way hash function, but this is not suitable for low-entropy input data (i.e. passwords)

Asymmetric cryptography is usually more expensive than hashing and should therefore require less stretching for the same benefits.

I see that you understand the importance of an expensive hash routine to prevent Brute Force. While Asymmetric Encryption is slower than General Purpose Hash functions (i.e. SHA-2), what you should be using is a Slow Hash function (i.e. BCrypt) which is more expensive than either of the two aforementioned options.

Stronger guarantee on the entered password: there is one and only one password which can be accepted. That is, no collision can be accepted (contrary to hashing functions) as else the decrypted password would not be unique.

Modern hash functions have a large enough name-space that collision is not likely to occur in the application's lifetime. Trying to find something even more collision-resistant is pointless.

The main disadvantage I see is that the stored password length is correlated to actual password length, giving a clue on password strength. This can be mitigated by introducing a "lengthy" salt to the password, which will ensure that short password only look as short as the salt. Long password remain mostly unaffected but that is fine as they are long but might take space in the database.

The attacker would be able to see how many blocks long the encrypted password may be, but they would not be able to tell any more specifically than that. The vast majority of passwords can be stored in a single block (assuming a strong key size like RSA 1024 or RSA 2048) so this clue would be of limited use to an attacker.

Are there any other disadvantages to this technique?

  1. Asymmetric Cryptography is less expensive than a Slow Password Hash routine such as BCrypt.

  2. Disk space requirements are higher.

  3. "Don't roll your own."

There you have it, you should be using a Slow Password Hash such as

  • BCrypt, but be sure to run a quick SHA-2 hash on the input data, so super-long passwords will not be truncated by BCrypt
  • PBKDF2 but that is less GPU-resistant
  • SCrypt is better than BCrypt if you have a high enough work factor. Otherwise it is worse against GPUs.
  • The winner of the Password Hashing Competition may be even better than the aforementioned, but has not yet stood the test of time, so don't use it just yet. It's called Argon2, and has separate Work Factor settings for CPU time and Memory load. (nice!)

Most of these options generate random Salt by default, but do verify whether this is the case!

It is best to include some Pepper (~72 bits of entropy) before the Password prior to hashing. The Pepper can be the same for all your users, but should be stored in a file outside of the database so that component cannot be found via SQL Injection.

Make sure your Work Factor requires about 100ms (with appropriate DoS protection) on your target hardware (knowing that attackers will use faster hardware for Brute force)

700 Software
  • 13,897
  • 3
  • 53
  • 82
  • Also, let's say, the public key is 512-bit long and the password is 1024-bit long, you can brute-force the public key instead of the password, to find the password. Which would limit password security in the same way as a 512-bit hash... Meaning this scheme has virtually no benefit indeed. – Nonyme Sep 30 '16 at 14:20
  • Yes, folks would be able to brute-force the first 'block' of the password independently from the second 'block'. With a hash, you brute-force the whole password at once but you do get collision if the password is longer than the hash. But with such a large namespace (512 bits) such details [have no relevance](http://security.stackexchange.com/questions/138121/asymmetric-cryptography-as-hashing-function#comment257817_138123). – 700 Software Sep 30 '16 at 14:45
  • 1
    I mean, brute-forcing the key itself will give you the whole password. The fact that the blocks can be brute-forced independently is not necessary (but also a good argument). – Nonyme Sep 30 '16 at 16:22
  • Ah, brute-forcing the Private Key. I see what you are saying. – 700 Software Sep 30 '16 at 16:26
1

I can't understand why you think this would be any better than using one of the standard key derivation functions:

Your first argument makes no sense: during stretching, the type of work you're doing is only important in the sense that you want it to be designed to be slow on all type of hardware (which is definitely NOT one of the design goals of a typical encryption function).

Your second argument would only be valid if you're using unsalted passwords with a weak hash function. Otherwise, it wouldn't be pre-image resistant.

Stephane
  • 18,607
  • 3
  • 62
  • 70
  • Hashing functions are not designed to be slow on all type of hardware either. At least, SHA-2 and SHA-3 are designed to be really fast to compute. The second argument stand on a theoretical point of view. If you use a 1024 bit long password and a 512 bit hash, your password will not provide more security than 512 bit as there is "probably" a 512 bit pre-image. The asymmetric encryption scheme guarantee to have only a 1024 bit pre-image. – Nonyme Sep 28 '16 at 14:42
  • You're apparently under the misconception that stretching is done through hashing alone. It isn't. For reference, take a look at the design of scrypt. – Stephane Sep 28 '16 at 14:50
  • 1024 bit long passwords are rare. And it is unlikely you'll find a matching pre-image for an arbitrary 512-bit hash because it would take [1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 years](https://www.google.com/search?q=2^512+nanoseconds+in+millenia) to generate such a database, not to mention storage space requirements. Generally if the password has 72 bits of entropy then that is enough to be sure there will not be a pre-image until the password is stolen. (even if you are using a Fast hash like SHA-2) – 700 Software Sep 28 '16 at 17:12