[Evolution-hackers] Security vulnerability in APOP authentication

[gaetan leurent ens fr (Gaëtan LEURENT)]

Hello,

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.  I tested it against Evolution, 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, I think Evolution should reject msg-ids that does not
conform to the RFC.

The details of the attack and the new results against MD5 needed to
build it will be presented in the Fast Software Encryption conference on
March 28.  I can send you some more details if needed.

Meanwhile, feel free to alert any one that you believe is concerned.
I am already sending this mail to the maintainers of Thunderbird,
Evolution, fetchmail, and mutt.  KMail already seems to do enough checks
on the msg-id to avoid the attack.

Please CC me in any reply.

-- 
Gaëtan LEURENT