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.

  • 2
    The "encode before sending password" is done by HTTPS connection. I don't get how you do 4. since server has only Alice's encrypted data with pk1, so if server generates pk2 and reencrypt it, it has Alice pk1&pk2 data. So Alice must enter her password, encrypt with pk1 that she must store and never loose (1st flaw), and re-encrypt with pk2 to have the server compare it. Then, server has to store the unhashed Alice-pk1 data to be able to encrypt it with pk2. That's a 2nd flaw: if I get the DB, I don't get Alice password but I get Alice-pk1 which is enough to login – Xenos Jul 20 '18 at 8:11
  • 1
    Where is the point in generating a public key and destroying the private key? It's just a random number that happens to be smaller than the product of two prime numbers which are also destroyed. It's just a random number without its corresponding private key. In addition, making changes to the password before sending it, effectively makes this changed string the new password. An attacker able to intercept it, can authenticate as the user. – GxTruth Jul 20 '18 at 11:44
  • I'm not following your math, could you expand on how you're planning to generate a public key from two other public keys? – AndrolGenhald Jul 20 '18 at 15:01
  • My understanding of public keys is that they are elements of a group. For the specific case of RSA the group is integers mod N. So long as I hold on to the group generator g I can generate keys g^x as much as I want and any two of my keys can be multiplied to make a third key since g^x * g^y = g^{x+y}. Furthermore the ciphertext g^x * p encrypted again with g^y gives g^y *g^x * p = g^{x+y} * p. – IIAOPSW Jul 20 '18 at 20:16
  • @IIAOPSW Using multiple keys with the same modulus is a really bad idea. – AndrolGenhald Jul 20 '18 at 20:47

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.

  • Who said anything about RSA? I just said public and private keys. Any group operation such that discrete log is a hard problem would suffice. On HTTP(S) who said anything about this being a web server? – IIAOPSW Jul 20 '18 at 20:29
  • @IIAOPSW RSA: Ok, maybe I assumed a bit much. ... HTTPS: The name here doesn't really matter - point is, encrypting only the password is useless. There has to be replay safety, which usually goes along fine with encrypting the whole transmission. – deviantfan Jul 20 '18 at 22:20
  • @deviatnfan the replay safety in my proposal comes from the temporary key in step 2. The data itself isn't really sensitive but certain calls are restricted by user. Encrypting the whole message feels overkill. – IIAOPSW Jul 22 '18 at 16:16
  • I think I understand your sniffer/replay criticism. What happens in my proposal is k2*k1 gets sent out and k2*k1*p is expected back. k1 sits on file and k2 was generated and disposed of just moments ago. Neither sent value can be used in a replay attack because on the next auth request the server sends k3*k1 and expects k3*k1*p. Even a hacker who stole k1 and k1*p from the server and sniffed k3*k1, k2*k1, k2*k1*p from traffic couldn't derive the value k3*k1*p. – IIAOPSW Jul 22 '18 at 16:25

@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.

  • I was going to comment that this scheme would be bad because you want to use a slow hash...but if RSA is already slow to generate a new key, isn't that a good thing? – Ben Jul 20 '18 at 14:08
  • 1
    I think (but may be wrong) that "pass the hash" won't work here because the "hash" changes every time. The server stores K1*P, sends K1*K2 to the user, and gets back K1*K2*P from the user, where K2 is generated "on the fly" with every login. If I understand correctly, at no point is there a value transferred over the network that an attacker could use on a subsequent login. – Ben Jul 20 '18 at 14:10
  • @ben good points, I didn't read carefully enough. Re-working answer. – Mike Ounsworth Jul 20 '18 at 14:18
  • Oh...RSA key generation is slow. But I'd guess using the key once you know it, is pretty fast? So you'd penalize legitimate users of the system during login, without getting that benefit in the case of a stolen password table. If using a known key to "hash" a given password attempt is faster than bcrypt or argon2, then that's a reason not to use this method. – Ben Jul 20 '18 at 15:52
  • 2
    @IIAOPSW Hmm, that's true, but then you're hardly creating a keypair and throwing away half;more like using modular exponentiation as a hash function. And probably not one with uniformly random outputs because of all the congruence structure. This might be a better fit for CryptoSE than SecuritySE. – Mike Ounsworth Jul 20 '18 at 21:18

Your Answer

