Is there a password based challenge response authentication scheme with public key cryptography?

Question

I was thinking about an authentication where

• the user only has to know a password
• but no salt, everything else the client retrieves from the server
• yet a user's password can't be retrieved from the data on the server
• nor from the communication, meaning not even the server ever gets the password

I thought something like this could be close to the solution:

Set up:

1. the client calculates e=hash(password), p, q primes and n=p*q
2. uses this hash to calculate an RSA decryption key d=(e^(-1) mod phi(n))
3. passes on d and n to the server a way avoiding any man in the middle

Authentication:

1. the server sends a c=random() challenge and the stored n to the client
2. the client encrypts it and sends r=(c^(hash(password)) mod n) as response
3. the server decrypts a=(r^d mod n) answer and if a==c then the user has been authenticated

Is there a proven authentication scheme similar to this one? If not, would the above be safe with a proper RSA implementation, like OAEP, even though the encryption exponent is not the traditional 65537 but it is actually an intermediate key of the protocol?

Answer 1

What you're talking about is a zero-knowledge proof (or more specifically a ZKPP) similar to RSA-PAKE.

If we ignore the general problems of implementing RSA safely, there are a few problems with the scheme you suggested:

1. Since an attacker viewing the key-exchange knows c, if the value of c^h is ever less than n then r = c^h mod n = c^h. From this the attacker would recover c^h, and could compute log_c(c^h) to recover h and crack it offline.
2. The server is never authenticated, so an attacker could presumably select a value of c that is advantageous for the above attack, or other attacks.
3. You can't just use the raw result of a hash function to select e, because e must be relatively prime to φ(n). So you'd need to do some manipulation to ensure that e is a safe value. You'd need to ensure that this manipulation doesn't weaken the safety of the hash excessively.
4. The server must validate the initial setup values sent by the client, otherwise the whole scheme may be broken due to incorrect key generation or manipulation. This is difficult to do while maintaining zero-knowledge.
5. There are some potential attacks around schemes where an attacker can select the value of e interactively, such as e-residue attacks.
6. You'd need to be careful about error side-channels and timing side-channels on some of these operations.

What you probably want to look at is a protocol like SRP, which handles ZKPP authentication while avoiding most of these problems.