The Big-3 of Password Authentication

No matter how complex or simple a password authentication system is, it almost always has to contend with a number of long-standing issues that consistently recur in the design of such systems. What follows is a brief summary of three of the most difficult-to-solve problems that have bedeviled password protocols for years. Research material on these subjects is extensive, and references will be provided on a separate page.

Dictionary Attacks

A dictionary attack is in essence a password-guessing attack. It is effective because users often choose easy-to-remember passwords, which are generally easy to guess as well. For example, under UNIX, the hashed password entry in the /etc/passwd file is 64 bits long and is generated from a key that is 56 bits long. To search all the possibilities for the key, one would need to make 2**56 attempts - quite a large number even by today's standards. However, since the key is a simple function of a password, a smarter attacker could create a dictionary of common passwords and try those first. Even if the dictionary is a million words long, searching the entire dictionary would take less than one trillionth the amount of time compared a so-called brute-force attack that looked at all possible keys. This can mean the difference between hours and years of CPU time. On typical multiuser systems, a dictionary of that size might allow an attacker to guess a significant fraction of user passwords.

Network-based Dictionary Attacks

A password database file is not the only potential target of a dictionary attack. With the assumption of insecure networks comes the possibility of a dictionary attack based on network traffic. To illustrate, we analyze a simple challenge-response protocol, in which a user, Alice, needs to convice another party, Bob, that she knows a password P.

Alice identifies herself to Bob.
Bob sends Alice a challenge R.
Alice computes H(R,P) and sends it to Bob, where P is the shared password and H() is a secure one-way hash function.
Bob compares this value against H(R,P) computed with his copy of P.

While Alice and Bob are having this conversation, a third party named Eve has been watching and recording all the messages. After snooping a successful authentication attempt, Eve can verify a guess P' by computing H(R,P') using the captured value of R and comparing the result against the captured value of H(R,P). If they match, Eve has found the correct password and can now impersonate Alice.

Even if the server keeps the password database completely secure to guard against an attack there, network traffic is nearly impossible to secure in many cases. Examples include cellular phone networks, set-top boxes for cable access, and public Internet access points. The problem of a dictionary attack is exacerbated by the need for small passwords, e.g. PINs or access codes that must be chosen from a relatively small keyspace. In these situations an attacker may be able to search the entire valid keyspace with a dictionary in a fairly short time.

It is obvious that immunity to network-based dictionary attacks would be a highly desirable property in any password-authentication mechanism. Unfortunately, nearly all password-only challenge-response protocols are vulnerable to such attacks. Protocols that defend successfully against dictionary attacks only started appearing in the early 90s, with the discovery of EKE and related protocols.

Plaintext-equivalence

A piece of data is said to plaintext-equivalent to a password if that piece of data can be used to obtain the same level of access that can be gotten with the password itself. Consider this naive attempt at improving on a remote login protocol:

Alice enters her password directly to her client software.
Instead of sending the password itself over the network, Alice's client software hashes her password with the standard UNIX password hash function and sends that over the network.
Bob, the server, directly compares the string received over the network against Alice's hashed password. If they match, authentication succeeds.

Although the cleartext password is neither sent over the network nor stored on the host system's password database, this protocol opens up the following attack: An intruder finds out Alice's hashed password either from monitoring the network or by reading the host's password database, initiates a connection with Bob, and sends over the hashed password when asked for it. Without knowing the password itself, our intruder has nevertheless fooled Bob and gained access to Alice's account.

This problem persists in more complex protocols. Consider a challenge-response system that uses a one-way function f() to hash passwords for storage. Alice and Bob authenticate as follows:

Alice identifies herself to Bob.
Bob sends Alice a challenge string R.
Alice computes H(R,f(P)) and sends it to Bob.
Bob computes H(R,f(P)) based on his stored value of f(P) and compares it against Alice's message. If they match, authentication succeeds.

The plaintext password P is never stored on the host system, but now an attacker can exploit plaintext-equivalence, look up f(P) from the password database, and impersonate Alice. This is because the client-side computation always uses the value of f(P) and never depends on P alone.

Plaintext-equivalence is actually a very difficult issue to resolve in password-authentication systems. In general, it is fairly easy to design protocols if one can assume that both parties possess an identical shared secret of some kind. This is mainly because both parties can perform fairly complex but symmetric operations based on the shared secret and exchanged messages, and a protocol designer can add operations and messages to strengthen a protocol without worrying much about "breaking" the protocol, i.e. causing the protocol to cease to function correctly. On the other hand, avoiding plaintext-equivalence requires the careful selection of mathematical operations that will in most cases operate asymmetrically on the client and server sides yet still authenticate properly when the correct password is used. This is analagous to the relative abundance of symmetric encryption algorithms as compared to the relatively few public-key cryptosystems currently available.

No matter how hard or easy it is to avoid plaintext-equivalence, it has been and will continue to be a highly desirable property of almost any password-authentication mechanism. While it is always a good idea to protect a server's password database from intruders, this protection is usually limited to operating system mechanisms like file permissions and access control lists. At some point, the server itself needs to be able to read the file to perform authentication. Thus, the means for accessing the contents of the entire password database must reside somewhere on the server. In a sense, UNIX users have enjoyed the relative security of a non- plaintext-equivalent password mechanism for decades; on most older systems, the password database is world-readable! Users of UNIX and other multiuser operating systems would not be willing to give up such a system and trade off resistance against internal attacks for a little bit of network security.

Vendors of modern operating systems are beginning to realize the hazards of plaintext-equivalence. As recent security woes plaguing both Microsoft Windows NT and Novell NetWare have become widely reported in the media, it has become increasingly clear that existing protocols offer inadequate protection against password file attacks. As soon as a weak authentication mechanism becomes incorporated into a large number of products, a hacker or group of hackers who dislikes/distrusts the company writes and releases utilities to find and extract the contents of the password file, which promptly results in a full compromise of system security. Much bad publicity ensues. The only way around this problem is to use a system that makes the password file inherently useless to attackers, even if it were to be made world-readable. True security starts there.

Forward Secrecy

Forward secrecy, as applied to password-authentication protocols, indicates the degree to which a protocol resists compromising secret information if another part of the protocol is compromised. This issue arises in modern password-authentication systems because they are often used for exchanging session keys to encrypt traffic as well as for authentication. Even in the most secure of password-authentication systems, it is always possible for keys and passwords to be compromised. A user might write down a password or pick an very easily-guessed one. Session keys might be leaked or might be generated from poor random number generators or from easily-guessed seeds.

To illustrate how lack of forward secrecy might be exploited, we start with a modified challenge-response protocol that also performs a key exchange:

Alice and Bob exchange random strings over the network; Alice sends R to Bob and Bob sends S to Alice.
Both parties compute K = H(R,S,P), where P is the shared password.
Both parties verify that they have the same K and start encrypting messages with it.

If Alice ever lets her password P fall into the hands of an attacker like Eve, who regularly monitors traffic between Alice and Bob, it will allow Eve to decrypt all transmissions made while P was used as the password. Eve can simply gather the R and S values from any session, compute H(R,S,P) using the stolen password, and immediately obtain the session key for that session. This type of attack is particularly insidious because of a phenomenon known as password chaining. Since the most common way for Alice to change her password on Bob's system is to log in and run the appropriate command, anyone who decrypts that session will see Alice's new password. If Eve got her hands on one of Alice's old passwords, she could decrypt all sessions encrypted with the help of that password, until she saw Alice change her password. Eve could continue decrypting sessions using the new password until that password changed, and continue until all of Alice's session traffic had been decrypted.

This attack also works in reverse. In many instances, the session key can be compromised, either through negligence or the use of weak encryption. For example, to be exported legally from the U.S., encryption software must generally be limited to a key length of 40 bits or shorter. Such keys have been demonstrated to be easily compromised through brute-force attacks in a matter of hours. A number of currently-used systems tackle the authentication problem by establishing a secure connection in advance and then sending the password over this secure connection. Once the session key is compromised under this arrangement, the password is instantly revealed.

Denning-Sacco

The protocol that we just analyzed is also susceptible to an attack based on a compromised session key. If Eve discovered the value of K for a session, she could start a dictionary attack against P by testing candidate values P' and comparing H(R,S,P') against K. This version of a dictionary attack is known as the Denning-Sacco attack and has been shown to be successful against a surprisingly large number of existing protocols. More information is available from [DS81]

It is obvious why forward secrecy is a good requirement in password-authentication systems. Although exploiting a lack of forward secrecy generally involves a security breach elsewhere, containing the extent of the breach can often mean the difference between a localized, repairable intrusion and a complete compromise of an entire network.

This list is by no means a complete list of issues that arise in the design of strong password-authentication systems. I do believe, however, that these issues tend to be featured prominently in security analyses of proposed protocols. They are intriguing partially because they are inherently hard problems that have only begun to be solved recently, and because there exists a large body of work dealing with how to exploit weaker protocols that fail to address these issues properly.

Back