A protocol to authenticate users without login/password

Question

A casual message exchange on reddit yesterday got me thinking whether it might be possible to design a protocol that removes the need for users to remember a unique password for every service (s)he connects to.

The idea is that essentially each user supplies identifying credentials (name, date of birth, city of birth) and a secret pass-phrase. Based on this information, and the service being accessed (optional, in case the user does not want to be tracked across services), the client software can deterministically generate a RSA keypair (using a secure hashing scheme, SHA-512 maybe).

The public component of this keypair is passed to the service, and serves both as an authentication token and an encryption key. User need only remember one pass-phrase, and credentials to access any service from any client, with the public key being her secure identification. Ephemeral session-specific keys can still be used be used for forward secrecy.

I'm wondering what the drawbacks to this scheme are? It is not susceptible to spoofing unless the imposter gets hold of the private key, lack of multiple passwords make it more secure and reliable for users. It is susceptible to MITM and a compromised client (because it sees the pass-phrase), but that is the same as SSL today, and the threat of key-loggers.

So, I'm just wondering if there are any serious drawbacks I have missed, and also if someone wanted to experiment with this, would it make sense to build this on top of TLS (an extension to http, maybe), or to replace it?

Thank you!

Edit:
Thanks Thomas Pornin for the well-reasoned answer. I wonder if the following are valid rebuttals to the (well-founded objections) you raised:

1.Since there is only one password in this scheme, it is not unreasonable for there to be stringent complexity requirements (e.g. at least 128 bytes etc), so it is not susceptible to dictionary attacks. Dictionary attacks are really the same as saying if the attacker has infinite resources at his disposal, he can brute force any scheme. As long as the scheme is such that no information can be obtained by guessing portions of password, then it is surely possible to make dictionary attacks impractical?

1. Regarding need for changing the password: this would not be possible within the limitied protocol described in the question. Maybe when registering the users' public identity, the server can send a secret encoded with users' key that should be used only to invalidate the identity when required? As long as there is a public key per service (i.e. generated deterministically based on an unentangleable combination of user password and service identity, then an attacker can only compromise the access on a particular service).

Btw, do you know of any well known algorithms to generate the key pair based only on a (for instance) 512 bit number? I suppose this is same as asking if there is a way to find the closest safe prime given a number. Thanks!

Answer 1

Your idea is twofold:

1. Use an asymmetric key pair client-side for authentication.
2. Generate the private key deterministically from a password.

First part is standard issue in SSL; see the standard. Web browsers support it (but their GUI has long been ugly, confusing, or both).

Second part is not supported by widely deployed software, but it is not new, and it works, with the following caveat: it allows for offline dictionary attacks. Indeed, the client public key is public and is sent "as is" (within the client certificate) to any SSL server who asks for it. Also, by nature, the server must see it at some point. Since the private key is generated deterministically from the password, an attacker can then "try" passwords on his own machine, looking for a match with the observed public key.

---

This is actually very generic. Consider a system and protocol, where both client and server are "open": none of them stores any secret value, in the eyes of the attacker -- if the server can store secrets, then the proverbial list of (hashed) passwords in the server's database is enough. The only secret in the whole system is the user's password, which is stored in the user's head, and is unknown to the attacker. The attacker wants to recover that password.

Under these conditions, for any protocol you may come up with, offline dictionary attacks are possible. That's consubstantial to the openness of the systems: since the attacker is assumed to know everything about the whole setup except for the user's password, then he can emulate the whole thing on his own machines, for each potential password: the attacker runs both client and server in a virtual environment on his own cluster.

Throwing in RSA and hashing and whatsnot won't change anything to that. Once offline dictionary attacks are possible, you are back to the robustness of the password itself. There are ways to try to cope with offline dictionary attacks, but the situation is still, on the whole, uncomfortable.

To resist offline dictionary attacks, you must have a secret on either the client or the server. On the server, this is the usual model of hashed passwords in a database which the server tries to protect (with more or less success); the passwords are not stored "as is" but hashed, as a second line of defence. On the client, just store an asymmetric private key; possibly, encrypt it locally with a password, as a second line of defence. This is supported out-of-the-box by existing browsers (well, at least Firefox and its "master password").

---

Apart from the security concerns about dictionary attacks, there are practical issues with deterministic private key generation from the user password. In particular, what happens when the user changes his password ? His key pair mutates. Thus, all servers with which the private key is used must be contacted to acknowledge the new public key to accept. This brings to the dance the usual problem of public key distribution, then PKI, certificates and their ilk. This has long range ramifications.

Answer 2

This is called two way certificate authentication or client certificate authentication and has already been supported by SSL for quite some time. It simply isn't used that much in the wild because it causes problems with certificate management when dealing with multiple computers which make it harder on users than a simple username and password.

If you want to see how it operates, you can check out either StartSSL.com, which is a certificate authority that uses two way certificate authentication, or outside of a web context, TeamSpeak 3 also uses client certificates for authentication. That's how it keeps track of your user, but never asks for a username and password. They call it an identity and provide means to move it around, but it is simply a client certificate.

Since you asked specifically for drawbacks, the main one is using multiple devices and the key management issues that entails. One way around that is to provide one time use passwords that allow linking another computer and keeping track of multiple client keys that correspond to the user. Without associating some user description to each, it is also hard to remove access from a lost device.

An ideal implementation might store a public cert along with a description of the computer being used for each login and then allow generation of a one time key for the user to use on another computer to link it to their overall account. This would allow for a lost device to be removed by logging in on another device to remove the account. A password (or some other means of authentication) could also be used for doing the removal to prevent the lost device from removing the legit devices.

This is also often used in combination with passwords in higher security environments since it requires something you know (password) and something you have (client cert). This is broadly referred to as two factor authentication since it requires two of the three basic factors, who you are (biometrics), what you know (password) and what you have (tokens, certificates, cards, etc).