APOP vulnerability
CVE-Id:
CVE-2007-1558
Short description:
Security vulnerability in the APOP protocol, related to recent
collision attacks by Wang and al. against MD5. Using the man in the
middle setting, one can recover the first characters of the password
with a few hundred authentications from the client.
Affects:
Most mail user agent that support APOP. I tested Mozilla Thunderbird,
Evolution, KMail, mutt, fetchmail, and only KMail is not vulnerable.
Microsoft Outlook and Apple Mail does not support APOP.
Long Description:
I found a security vulnerability in the APOP authentication. It is
related to recent collision attacks by Wang and al. against MD5. The
basic idea is to craft a pair of message-ids that will collide in the
APOP hash if the password begins in a specified way. So the attacker
would impersonate a POP server, and send these msg-id; the client will
return the hash, and the attacker can learn some password characters.
The msg-ids will be generated from a MD5 collision: if you have two
colliding messages for MD5 "<????@????>x" and "<¿¿¿¿@¿¿¿¿>x", and the
message are of length two blocks, then you will use "<????@????>" and
"<¿¿¿¿@¿¿¿¿>" as msg-ids. When the client computes
MD5(msg-id||passwd) with these two, it will collide if the first
password character if 'x', no matter what is next (since we are at a
block boundary, and the end of the password will be the same in the
two hashs). Therefore you can learn the password characters one by
one (actually you can only recover three of them, due to the way MD5
collisions are computed).
This attack is really a practical one: it needs about an hour of
computation and a few hundred authentications from the client, and can
recover three password characters (brute-forcing 5 characters is a
matter of hours). I tested it against Thunderbird, Evolution, mutt,
and fetchmail, and it does work.
However, using the current techniques available to attack MD5, the
msg-ids sent by the server can easily be distinguished from genuine
ones as they will not respect the RFC specification. In particular,
they will contain non-ASCII characters. Therefore, as a security
countermeasure, mail user agents should reject msg-ids that does not
conform to the RFC.
This was presented in the Fast Software Encryption conference. The
paper is available on my web page. This attack was independently
discovered by Sasaki, Yamamoto and Aoki, and they wrote a paper
available on eprint.
Sasaki also presented an extension of this attack at the Rump Session
of FSE 2007: he is able to recover the first 31 passwords of the
password. He did not give many details, but I guess he still uses
non-RFC compliant message-ids. However, it is theoretically possible
to use his idea with RFC-compliant message-id if one does a
precomputation of 2^64 MD5, using the birthday paradox (it has to be
done only once to break as many password as wanted). This is very
expensive, but not completely unrealistic...
Recommendations:
APOP should be considered broken in the man-in-the-middle setting.
User should be encouraged to switch to another authentication
mechanism, such as CRAM-MD5 (or use TLS...).
Mail user agent should check carefully the RFC-compliance of the
message-id. Mozilla and fetchmail development team have written such
code that will be present in the next version of their software. This
will prevent the attack for now, but it might not last long...
Mail user agent should also be careful when autodetecting the
authentication mode: in the man-in-the middle setting, the attacker
will claim to support only what he can break, and the user should be
warned if the usual authentication mode is no longer present.
References:
http://www.eleves.ens.fr/home/leurent/files/APOP_FSE07.pdf
http://eprint.iacr.org/2007/101
--
Gaëtan LEURENT