fetchmail-devel

[fetchmail-devel] Security vulnerability in APOP authentication

[<gae...@en...>]

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 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, I think fetchmail 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

Re: [fetchmail-devel] Security vulnerability in APOP authentication

[Matthias A. <mat...@gm...>]

Gaëtan LEURENT schrieb am 2007-03-14:

> 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.

Thanks for the heads-up.

The problem with APOP is that it specifies MD5, and that isn't going to
change, and with some clueless upstreams, APOP is the best you can
get...

> 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 fetchmail, and
> it does work.

How does this work in detail? Recover character by character? Are
specially-crafted challenges required to provoke weak messages in MD5,
if there are any?

What's the state of the MD5 cracking art WRT unknown plaintext, how big
is the effort to brute force the 85^5 space from the 1,000 hashes thus
collected?

I don't know details beyond that someone has a way to produce two
messages with colliding hash with reasonably little effort.

> 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.

How long until these colliding messages ASCII and RFC-822 message-id format

> In particular, they
> will contain non-ASCII characters.  Therefore, as a security
> countermeasure, I think fetchmail should reject msg-ids that does not
> conform to the RFC.

That is certainly feasible to implement, I wonder though if that helps
us out for long.

> 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.

That would certainly be interesting - who will present the attack at the
conference? Is the paper available for download or will it be after the
conference?

> 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.

I think I'll be easy on this one until after I've seen the details.

Best regards,

-- 
Matthias Andree

Re: [fetchmail-devel] Security vulnerability in APOP authentication

[<gae...@en...>]

Matthias Andree wrote on 18 Mar 2007 00:03:55 +0100:

> How does this work in detail? Recover character by character? Are
> specially-crafted challenges required to provoke weak messages in MD5,
> if there are any?

Yes, it uses specially-crafted challenges to recover the password
character by character.  It is not really a matter of weak messages, but
of pair of colliding messages.

The idea of this attack is to create a collision, and replace a part of
the collision with an unknown password character; therefore, if it still
collides the chances are that the password character is the same than
the one in the original collision.

> What's the state of the MD5 cracking art WRT unknown plaintext, how big
> is the effort to brute force the 85^5 space from the 1,000 hashes thus
> collected?

Well OpenSSL does something like 2^31 MD5 per hour, and 85^5 is about
2^32.  So you should be able to bruteforce 5 characters in 2
hours...

>> 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.
>
> How long until these colliding messages ASCII and RFC-822 message-id format

I have no idea...  I think APOP should already be considered insecure,
but as you said it is sometimes the best authentication available, so
it's better to try to make it as resistant as possible...  Anyway,
restricting the space of possible message-ids will at least make the
attack somewhat harder if it becomes possible.

>> In particular, they
>> will contain non-ASCII characters.  Therefore, as a security
>> countermeasure, I think fetchmail should reject msg-ids that does not
>> conform to the RFC.
>
> That is certainly feasible to implement, I wonder though if that helps
> us out for long.

Well I don't know.  That's up to you to choose if it's worth...

>> 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.
>
> That would certainly be interesting - who will present the attack at the
> conference? Is the paper available for download or will it be after the
> conference?

I will present it :-)  I send you a copy of the paper.

-- 
Gaëtan LEURENT

Re: [fetchmail-devel] Security vulnerability in APOP authentication

[Matthias A. <mat...@gm...>]

Gaëtan LEURENT schrieb:

> The idea of this attack is to create a collision, and replace a part of
> the collision with an unknown password character; therefore, if it still
> collides the chances are that the password character is the same than
> the one in the original collision.

> Well OpenSSL does something like 2^31 MD5 per hour, and 85^5 is about
> 2^32.  So you should be able to bruteforce 5 characters in 2
> hours...

Gee. I can then be friendly and use USER/PASS instead to spoil the
challenge at least :-)

>> That is certainly feasible to implement, I wonder though if that helps
>> us out for long.
> 
> Well I don't know.  That's up to you to choose if it's worth...

Let's just try it. I'm attaching a patch against 6.3.8-rc1 that
validates the timestamp according to the RFC-822 ABNF stuff and refuses
to authenticate if the timestamp isn't a valid RFC-822 msd-id token.

Yes, I hand-hacked a full(!) msg-id parser, and a few more eyeballing is
desired - let me know if you have any concerns about the new rfc822valid.c.

Thanks.

Best regards
Matthias Andree

Re: [fetchmail-devel] Security vulnerability in APOP authentication

[Matthias A. <mat...@gm...>]

(Mince alors, que je n'utilise pas Thunderbird pour des pièces
jointes en text. Dommage.)

"8-bit us-ascii" MIME encoding, what kind of TB brainfart is that?

*This* message should get the character encoding of the attachment
right.  Sorry for the mess.

-- 
Matthias 'mutt simply works' Andree

Re: [fetchmail-devel] Security vulnerability in APOP authentication

[Matthias A. <mat...@gm...>]

Gaëtan LEURENT schrieb:
> Matthias Andree wrote on 18 Mar 2007 00:03:55 +0100:
> 
>> How does this work in detail? Recover character by character? Are
>> specially-crafted challenges required to provoke weak messages in MD5,
>> if there are any?
> 
> Yes, it uses specially-crafted challenges to recover the password
> character by character.  It is not really a matter of weak messages, but
> of pair of colliding messages.

BTW, do you have or are you aware of a MITRE CVE Id to track this
protocol weakness?

Thanks,
Matthias

Re: [fetchmail-devel] Security vulnerability in APOP authentication

[<gae...@en...>]

Matthias Andree wrote on 19 Mar 2007 23:38:58 +0100:

> BTW, do you have or are you aware of a MITRE CVE Id to track this
> protocol weakness?

No.  Actually, I had never head about MITRE CVE until I read you
mail...

If I understood correctly how it works, the best thing to do is to post
to bugtrack, which I plan to do in a few days (just giving some time for
patches to come out...  or do you think I should rather do it right
now?)

-- 
Gaëtan LEURENT