RE: Authentication Methods for LDAP - last call (mandatory CRAM-M D5)

[Paul Leach <paulle@microsoft.com>]

Summary: CRAM-MD5 is seriously weak in at least three respects: as a result,
I believe that it is too weak to adopt. (I've appended a more complete
analysis after the ----- below).

1. It permits a server to totally choose the challenge. This permits a whole
class of attacks known as chosen plaintext attacks. Among the most serious
of these attacks is the precomputed dictionary attack -- the responses for
millions of common passwords to a fixed challenge are precomputed, and any
actual clients response can be matched to a password almost instantly.

2. The password isn't salted so as to be specific to the server. It is very
common for users to use the same password for multiple servers. This means
their password is only as secure as the least secure server.

3. CRAM-MD5 by itself has no method to integrity check LDAP requests; this
leaves it open to connection hijacking attacks and man-in-the-middle attacks
that enable the attacker to access potentially any server on which the user
has an account.

In addition, it requires either that the plaintext of the password be kept
on the server, or the MD5 "context". The latter is clearly more secure than
the plaintext password, _but_ I know of no analysis of the security of
contexts -- however, I do know that the MD5 code is careful to erase the
context after each use, implying that one should be very cautious in
believing that the context couldn't be used to recover the password.

Paul

----------------------------------------------------------

Attacks on CRAM-MD5 authentication

The following sections analyze the vulnerability of this protocol to attack
using the following techniques: eavesdropping/ brute force attacks; chosen
plaintext attack; and dictionary attacks.
 These attacks, if successful, compromise the client's password, and allow
the attacker access to the client's files even after the client's session
has ended.
 
Eavesdropping/ brute force attacks

 With the CRAM-MD5 protocol, an eavesdropper can acquire challenge/response
pairs. It can then test a password by using it to generate a key, encrypting
the challenge, and comparing it to the corresponding response; by
exhaustively trying all possible passwords, the correct one will eventually
be found. The total number of possible passwords is unbounded, so this
attack is not feasible.

CRAM-MD5 provides no protection against eavesdropping; if the CRAM-MD5
challenge/response exhange were protected by an encrypted TLS session it
would.

Online dictionary attacks

 If the attacker can eavesdrop, then it can test any overheard
challenge/response pairs against a list of common words. Such a list is
usually much smaller than the total number of possible passwords. The cost
of computing the response for each password on the list is paid once for
each challenge.

 This attack can be mitigated by checking passwords against a dictionary
when a user tries to change it, and disallowing passwords that are in the
dictionary.

Weak passwords

 Even when passwords are not allowed to be common words, the usual user
practice of choosing passwords that are short and have only lower cases
letters and perhaps digits means that the key space is smaller than the
theoretical maximum.

 This attack can be mitigated by requiring passwords to have a minimum
length and to include a minimum number of upper and lower case letters,
digits, and punctuation.

Chosen plaintext attacks

 With the CRAM-MD5 protocol, a "man-in-the-middle" or a malicious server can
choose the challenge from which the client will compute a response using a
secret of the client's password. The ability to choose the challenge is
known to make breaking many ciphers much easier, and it is possible that it
also may help break functions such as the one used to compute the response.
(See B. Kaliski, M.Robshaw,  "Message Authentication with MD5",
CryptoBytes, Sping 1995, RSA Inc,
(http://www.rsa.com/rsalabs/pubs/cryptobytes/spring95/md5.htm)

There is no known way to do this at present. However, the ability to choose
plaintext does have other consequences, outlined below.

Precomputed dictionary attacks

 If the attacker can execute a chosen plaintext attack, the attacker can
precompute the response for many common words to a challenge of its choice,
and store a dictionary of (response, password) pairs. Such precomputation
can often be done in parallel on many machines. It can then use the chosen
plaintext attack to acquire a response corresponding to that challenge, and
just look up the password in the dictionary. Even if most passwords are not
in the dictionary, experience shows that some will be unless very strict
control over users' choice of passwords is exercised. Since the attacker
gets to pick the challenge, the cost of computing the response for each
password on the list can be amortized over many passwords.

Other attacks

Connection hijacking

Any attacker that can inject packets into the network that appear to the
server to be coming from a particular client can hijack that client's
connection. Once a connection is set up and the client has authenticated, if
subsequent packets are not authenticated the attacker can inject requests to
read, write, or delete files to which the client has access.

Doing so requires that the injected packets have the right transport level
sequence numbers. If the attacker can not eavesdrop, this will have very low
probability of success, since the 32 bit initial sequence numbers may be
randomly chosen. Even if it can eavesdrop, then it needs to "gag" the
client, otherwise the client will start getting packets with bad sequence
numbers and reset the connection. This requires that the attacker is on a
host on the same LAN segment as the client or server and has modified the
host's OS to get direct access to its network card, or has taken over a
router between the client and the server. It is significantly more difficult
to hijack a connection than to eavesdrop, and doing so only permits the
attacker to access files as the client for the duration of the session. (See
RFC 1948.)

CRAM-MD5 by itself does not protect against connection hijacking; CRAM-MD5
in a TLS session with integrity protection would.

Rogue servers and spoofing by counterfeit servers

A counterfeit server is one that spoofs the DNS name resolution process so
that the client gets the counterfeit's IP address instead of the genuine
server's IP address, thus fooling the client into connecting to the
counterfeit while believing it is connecting to the genuine server.
 
A rogue server is a server that entices a client into accessing it, and uses
some aspect of the interaction to try to mount an attack.

Counterfeit and rogue servers are not detectable by the CRAM-MD5 mechanism,
which only authenticates clients to servers.

CRAM-MD5 provides no protection against rogue or counterfeit servers.

Man-in-the-middle attacks

A rogue or counterfeit server can authenticate to a real server as any
client that attempts to log in to it, by accessing the real server,
obtaining a challenge, and getting the client to respond to the challenge
from the real server.

CRAM-MD5 provides no protection against such attacks; CRAM-MD5 in a TLS
session with integrity protection would.

Active message modification attacks

If a client or server is not appropriately configured a router or a host on
a LAN segment between the client and server may be able mount an "active
message modification attack": it may be able to modify messages sent between
the client and server.

CRAM-MD5 by itself does not protect against message modification attacks;
CRAM-MD5 in a TLS session with integrity protection would.

Batch brute force attacks

Because the attacker can choose the challenge, it can gather many responses
to the same challenge, and find all the passwords matching the
challenge/response pairs in a single pass over the password space or any
subset thereof. This lowers the cost of finding at least one password by a
factor of N if N challenge/response pairs are captured.

CRAM-MD5 provides no protection against such attacks; if the CRAM-MD5
challenge/response exhange were protected by an encrypted TLS session it
would.