Protocols of the Past

Strong password authentication has remained a hard problem in cryptography despite advances in both symmetric (secret-key) and asymmetric (public-key) cryptosystems. Additional background information on the nature of the difficulty of this problem is available. The history of password authentication is littered with examples of weak, easily-compromised systems, most of which are still in use today. Here are the major categories of password authentication systems, along with some example implementations illustrating their flaws:

Weak Authentication

In general, "weak" authentication systems are characterized by protocols that either leak the password directly over the network or that leak sufficient information while performing authentication to allow intruders to deduce or guess at the password.

Cleartext Passwords

The most obvious (and insecure) method of authentication is to store the password in a database somewhere on the server. During authentication, the client sends the password directly to the server, and the server compares this with the stored value. The security problems with this are obvious.

Hashed Passwords

Several decades ago, it was discovered that a server did not have to store a user's password in cleartext form anywhere on the system in order to perform password authentication. Instead, the user's password could be run through a one-way hash function, which would convert it into a random-looking sequence of bytes. Such a function would be difficult to invert: given a password, it would be easy to compute its hash, but given a hash, it would be computationally infeasible to compute the password itself. Authentication consisted merely of running the hash function on a typed password and comparing it to the stored value. The password database itself could be made world-readable without fear of an intruder being able to lift passwords from it.

This system is still being used to this day, primarily for UNIX systems. Although the 56-bit DES cipher on which it is based is starting to show signs of age, the most glaring problem with this system in a networked environment is that it does not address the issue of how to transmit the password securely to the server for verification. Indeed, the vast majority of implementations today still send the password completely in the clear.

Challenge-Response

To avoid revealing passwords directly over an untrusted network, challenge-response systems were developed. At their simplest, the server sends the user some sort of challenge, which would typically be some sort of random string. The user would then compute a response, usually some function based on both the challenge and the password. This way, even if an intruder captures a valid challenge-response pair, it will not help him gain access to the system since future challenges are likely to be different and thus require different responses.

Unfortunately, challenge-response systems as a whole suffer from deficiencies that make them insecure for modern networked applications. The issues page discusses three major problems with these systems and gives some examples of how they have been and will continue to be exploited. There are a number of such protocols used in active systems today, and nearly all of them suffer from the insecurities described on the issues page.

Stronger Authentication

Although strong encryption has been with us for decades, the development of truly strong two-party (direct) authentication protocols really only started in 1990 with the publication of the EKE family of algorithms.

EKE

EKE describes a family of protocols that combine symmetric and public-key cryptosystems to perform password authentication. For the first time, protocols existed that could withstand dictionary attacks and possibly provide forward secrecy without involving trusted third parties or manual key-management.

EKE is discussed in [BM92].

DH-EKE, SPEKE

EKE can be implemented with different public-key systems, and each implementation has its set of quirks and idiosyncracies depending on the exact algorithms used. The most well-known and secure forms of EKE involve exponential key exchange, similar to the Diffie-Hellman key-exchange protocol. DH-EKE, for example, is EKE implemented using Diffie-Hellman itself. The only significant difference is that the messages exchanged under DH are now encrypted with the shared password.

Likewise, SPEKE is based on Diffie-Hellman, but the password is now used to influence the selection of the generator parameter in the session-key generation function. Technical details on all these protocols can be found at the Integrity Science Web site. These protocols have been subjected to some analysis, which indicates that they resist dictionary attacks and provide forward secrecy. However, the EKE family does not address the problem of plaintext- equivalence of passwords. They operate on the assumption that the server knows the same password as the client.

DH-EKE and SPEKE are described in [Jablon96].

A-EKE

The designers of EKE proposed a modification of the EKE protocol that they called "Augmented EKE", in which the server could store a quantity that was not plaintext-equivalent to the user's password. This protocol is the only other protocol known to this day that resists to dictionary attacks and does not have a plaintext-equivalent password database. Unfortunately, A-EKE sacrifices forward secrecy in its attempt to avoid plaintext-equivalence.

A-EKE is proposed in [BM94]. A vulnerability in A-EKE is covered in [STW95].

Inconvenient Authentication

In the absence of strong, simple password authentication technology, system designers in the 1980s turned to other techniques to ensure password security. Most of these systems were, of course, not entirely password-based, and often required extra overhead on the part of users, administrators, or both to operate smoothly.

One-time passwords

A one-time password is exactly that - a password that is valid only once and then discarded. The most famous of these systems is known as S/Key.

The security advantages of one-time passwords is clear: An intercepted password is useless to an attacker. The inconvenience of one-time passwords is equally clear: Users need to manage either a list of passwords or client software that computes the one-time passwords on the fly. And then there is the problem of regenerating a list of passwords every time the user runs out.

Kerberos

Kerberos is a distributed authentication service developed at MIT Project Athena. Authentication is granted through tickets, which are generated by a central authentication server. Kerberos maintains a set of secret keys, one for every entity to be authenticated within a particular realm, or domain. This means that the server must be kept extremely secure, as it represents a single point of failure for the entire system and all the nodes and users within it.

Kerberos requires a great deal of administrative overhead, and it changes the fundamental authentication model for users, sacrificing some transparency in the process. It also does not handle authentication very well when the user and host are in different administrative domains. Kerberos is suited mostly for centrally-managed clustered networks, where the same authentication service is needed for all users. It is not well-suited for smaller clusters or standalone systems, where the overhead of a separate, secure authentication server is unacceptable.

In 1989, the Kerberos 4 TGT protocol was broken and a dictionary attack found against it by Bellovin and Merritt; see [BM89] for details. In a sense, this places Kerberos in the uncomfortable position of being both inconvenient and weak. Kerberos V5, however, addresses this problem nicely by allowing for preauthentication methods like SRP, which eliminate the threat of dictionary attack.

Ssh

Recently, a new product called ssh has made the rounds of the security community. Ssh is basically an implementation of RSA written by non-US citizens, so the version distributed from Finland escapes US export restrictions. It offers host-based security and session encryption based on host-generated RSA keys. It is designed to replace the Berkeley 'r' commands like rsh that use a system of trusted hosts.

Unlike Kerberos, ssh does not require a centralized authentication server to operate. Like Kerberos, however, ssh requires that users and administrators learn new sets of commands and new key management techniques to keep systems secure. To negotiate a partially secure file transfer, for example, a user must remember to do:

$ ssh -L 1234:remote-server.stanford.edu:21 remote-server
(in a different window)
$ ftp myhost 1234

instead of the customary

$ ftp remote-server

Although ssh also provides the scp command for copying files between systems, it does not provide the same functionality as full-blown FTP. Nevertheless, the SRP distribution will be adding an scp-style authenticated file copy command.

Ssh consists of a large amount of code, most of which runs either as root or set-uid root. This makes auditing and verification of code difficult and time- consuming. SRP, by contrast, uses a non-setuid client, and the server code is a small patch to existing daemons. By emphasizing design simplicity, SRP minimizes the potential damage that bugs can cause, and programs can be tested more easily for conformance to specifications.

The final "issue" with ssh, though, is that it runs afoul of export regulations and RSA patent issues once inside the US. While it is legal for a US citizen to download ssh, he could not write his own SSH-enabled application and re-export it from a Web site. In addition, a commercial user would require a BSAFE license from RSA. To be fair, export regulations also prevent the exportation of SRP with strong encryption. However, SRP can perform secure authentication without the benefit of any encryption, while SSH needs encryption to protect the cleartext passwords over the network. This was, in fact, one of the original design parameters of SRP; it was intended to offer as much security as possible in a configuration that coexisted with export regulations.

In equation form:

(SRP Telnet/FTP) - (strong encryption) = protected password + clear session
(SSH/SCP) - (strong encryption) = cleartext password + clear session = rlogin/rcp

It is somewhat disturbing to note that while the overall issue of system security is beginning to attract an increased amount of attention, most existing systems still do not employ strong forms of authentication. Since strong authentication had not been invented when the Telnet protocol and other remote access standards were being decided, the world was saddled with a huge installed base of weak authentication mechanisms and all the security problems associated with them. Only the truly security-conscious users and administrators have so far taken it upon themselves to install one of the forms of "inconvenient but safe" authentication mechanisms in the form of add-on software. It is hoped that authentication systems like SRP will be able to bring true security to a greater number of users and move beyond the obsolete protocols of the past.

Back