Can I throw away a private key and use the public key like a hash function?

Question

Yes yes I know "don't invent your own protocols unless you're an expert". No need to yell at me I just want to know if there's a flaw in this idea and if not has anyone done it before.

The motivation here is I want to be able to authenticate users. I know that the standard solution is to salt and hash passwords. But I don't like the fact that the password itself must be sent to the server to check it. What if someone listens in? The client side can encrypt and send the password, but I don't like that either because maybe my decryption key leaks and someone who recorded previous web traffic can deduce all the passwords. Authentication is not a novel problem so I won't dwell any further on the pros and cons of the usual solutions.

My idea

For each user (a) the server stores a public key (g^x_a) and the password encrypted with that public key (g^{x_a} * p_a). The associated private key was either promptly destroyed or (better still) never calculated. The group generator g is held on to for future key generation. The usual relation applies g^a * g^b = g^{a+b}. The authentication process is as follows

1. The user Alice asks to be authenticated

2. The server Bob generates a new temporary public key g^t (again without an associated private key). Bob multiplies this temporary public key on his Alice data. This results in g^t * g^{x_a} = g^{t + x_a} = g^{x_a}' and g^t * g^{x_a} * p_a = g^{t + x_a} * p_a = g^{x_a}' * p_a. Bob disposes of the temporary public key leaving him only with a new public key (g^{x_a}') and Alice's password encrypted with this key. He sends the new key to Alice.

3. Alice takes the key given by Bob uses it to encrypt her password. She sends the encrypted value to Bob.

4. Bob authenticates Alice if the value given matches with the encrypted data calculated in step 2.

To recap

1. At no point in time can the server (or a database hacker) decrypt the password. With the private keys gone the public key encryption effectively works like a hash.

2. Since each user is encrypted with a different key, the passwords are effectively salted. A rainbow table would not work here.

3. A hacker with a previous image of the database cannot deduce future values of g^x_a * p_a by listening in on web traffic since that would require deducing the temporary key (which requires solving discrete log). Thus a leaked database image does not allow an attacker to impersonate users.

4. Neither the server nor the client has any private keys to manage. Only the client needs to keep secret information and the secret information can be human readable.

5. (drawback) an attacker has a small window of time between steps 2 and 4 where he can penetrate the server and impersonate a user using the data he found.

Answer 1

A very "easy" problem about (any) transport encryption of passwords:

• Sending it in plaintext over HTTP, of course any sniffer can read it, and use it to login.
• Sending plaintext over HTTPS (where all data is encrypted, not just the password alone) is already ok.
• Sending encrypted password within HTTPS offers no benefit.
• And encrypted passwords over HTTP (and the server expects it encrypted): There you still have the problem that a sniffer can read the encrypted password, send it to the server himself, and successfully log in.

So, tell me, why are you encrypting passwords during transfer?

About your combination of public keys, with RSA-OAEP etc. this just won't work (if you have never heard of OAEP, you should just know that plain RSA is not secure).

There are other problems, but these two alone make your scheme useless already.

Answer 2

@deviantfan gives a good answer; I want to expand.

Interesting idea and it may work (after careful analysis by people more cryptographer-y than me), but why not just use a regular salted hash function? For one thing, RSA is slow. Really slow. (for any message longer than about 256 bits, it's more efficient to RSA-encrypt an AES key and then AES-encrypt the message).

Oddly, people don't seem to publish benchmarking times for RSA keygen, but it seems like creating a new temporary RSA key takes about 1 second for RSA 2048, and about 20 seconds for RSA 4096. That's a lot of load on the server, and latency to the user.

As @Ben points out, slow is good for password-storage hash functions, but not this slow. Moreover, with slow password hashing, the server needs to do the slow hash operation once per legitimate login, while the attacker needs to do it per guess, slowing down their number of guesses per second. Here, the server needs to do the slow keygen once per legitimate login, but the attacker never needs to do it at all because they get the public key and can then guess against it. You're actually tilting the amount of work on the server vs the amount of work the attacker needs to do substantially in favour of the attacker.