issues.html
40f4d899a5905e716559a669c820d7439beb0d3806c3fc33c0a32d7821536d04<html>
<head>
<title>SRP: Issues, Terms, and Definitions</title>
</head>
<body fgcolor="#000000" bgcolor="#FFFFFF">
<h1>The Big-3 of Password Authentication</h1>
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.
<p>
<hr>
<a name="dictionary"><h2>Dictionary Attacks</h2></a>
A <i>dictionary attack</i> 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
<code>/etc/passwd</code> 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 <i>dictionary</i> 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 <i>brute-force attack</i> 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.
<h3>Network-based Dictionary Attacks</h3>
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.
<ul>
<li>Alice identifies herself to Bob.
<li>Bob sends Alice a challenge R.
<li>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.
<li>Bob compares this value against H(R,P) computed with his copy of P.
</ul>
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.
<p>
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 <i>entire</i>
valid keyspace with a dictionary in a fairly short time.
<p>
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.
<p>
<hr>
<a name="plainequiv"><h2>Plaintext-equivalence</h2></a>
A piece of data is said to <i>plaintext-equivalent</i> 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:
<ul>
<li>Alice enters her password directly to her client software.
<li>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.
<li>Bob, the server, directly compares the string received over the
network against Alice's hashed password. If they match,
authentication succeeds.
</ul>
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.
<p>
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:
<ul>
<li>Alice identifies herself to Bob.
<li>Bob sends Alice a challenge string R.
<li>Alice computes H(R,f(P)) and sends it to Bob.
<li>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.
</ul>
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.
<p>
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.
<p>
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.
<p>
Vendors of modern operating systems are beginning to realize the
hazards of plaintext-equivalence.
As recent security woes plaguing both
<a href="http://www.techweb.com/se/directlink.cgi?EET19970331S0001">Microsoft Windows NT</a> and
<a href="novell.txt">Novell NetWare</a>
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.
<p>
<hr>
<a name="forwsecrecy"><h2>Forward Secrecy</h2></a>
<i>Forward secrecy</i>, 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 <i>session keys</i> 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.
<p>
To illustrate how lack of forward secrecy might be exploited, we start
with a modified challenge-response protocol that also performs a
key exchange:
<ul>
<li>Alice and Bob exchange random strings over the network;
Alice sends R to Bob and Bob sends S to Alice.
<li>Both parties compute K = H(R,S,P), where P is the shared password.
<li>Both parties verify that they have the same K and start encrypting
messages with it.
</ul>
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 <i>password chaining</i>.
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
<i>that</i> password changed, and continue until <i>all</i> of
Alice's session traffic had been decrypted.
<p>
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.
<h3>Denning-Sacco</h3>
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 <i>Denning-Sacco</i>
attack and has been shown to be successful against a surprisingly large
number of existing protocols.
More information is available from <a href="references.html#DS81">[DS81]</a>
<p>
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.
<p>
<hr>
<p>
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.
<p>
<hr>
<a href="index.html">Back</a>
</body>
</html>
© 2022 Packet Storm. All rights reserved.
%7Cutmcsr%3D(direct)%7Cutmcmd%3D(none)){kind=small}
Follow us on Twitter
Follow us on Facebook
Subscribe to an RSS Feed