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