Is there a PAKE algorithm that is fully resistant to a server data leak?

Question

I'm looking to build an authorization system with a completely "public" server which involves two assumptions:

• The server's data is public
• The server is incorruptible and uncrackable i.e. nobody can pose as or hijack the server.

I've found SRP which is a pretty nifty concept, but even that one relies on the privacy of the server to be effective. By obtaining the verifier and salt, brute force attacks can be mounted offline without any additional input from the server. My goal is to have a system that requires interaction with the server to check for the correctness of the password, with all server-side data assumed to be visible.

I understand that may be very difficult if not outright impossible. Perhaps leveraging its other features (the server is verifiably legit, client can hold secrets) could be key? Or perhaps there is a way of securely encrypting the verifier.

Answer 1

The server's data is public

That assumption makes the idea of a PAKE undoable.

If the attacker has access to all the server's data, here's what he can do: clone the server, place the clone in his lab, and then have his client perform attempted negotiations based on all the passwords in his dictionary. Because the clone works exactly like the original server, the clone would access the correct entry in his dictionary, and so the attacker now knows the password.

What this means is that you need to change an assumption somewhere.

People have attempted to solve this problem; attempted solutions include having an uncopiable HSM hold a piece that the server needs to perform the authentication, and having multiple servers jointly perform the authentication (so that no one server knows enough, so that the adversary would need to break into all of them). Since I don't know what your limitations are, I don't know if these ideas would work for you (I suspect not).

As for your idea:

client can hold secrets

That feels like it's in the right direction; if the client can hold a private key (and the server would hold the corresponding public key), well, you still need to address MITM attacks (how does the client know he's actually directly talking to the real server), but you have solved the 'cloning the server allows someone to test passwords' problem. Of course, this direction is getting pretty far from the concept of a PAKE (which assumes that the client's knowledge of the password is the only thing it can use to authenticate).