Security vulnerability in APOP authentication

[gaetan.leurent@…]

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-idpasswd) 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 mutt, 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 mutt 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.

Fix:

Check more carefully for RFC compliance of the msg-id

[Brendan Cully]

Added by email2trac

[Brendan Cully]

On Sunday, 18 March 2007 at 17:36, Rocco Rutte wrote:
>  I was looking at some mutt code for this issue and other issues that 
>  report broken threading upon invalid message-ids. It seems that mutt 
>  happily accepts the following syntax: '<.*>' which is just plain wrong.
> 
>  I looked at rfc822.c to try to reuse address parsing for parsing 
>  message-ids but failed since I didn't have much time and the quote is 
>  quite complex.
> 
>  Even though adopting your code for mutt would be quite easy, I'm not 
>  yet sure what to do in case of validation errors.
> 
>  Say we get '<foobar>' during APOP authentication; should be really 
>  reject that and report failed authentication? If a message has 
>  '<foobar>' as message-id and others have it in their References: 
>  header, should we really ignore it and break threading?

Here's a patch that does a really minimal check that the message ID is
of the form <x@y> where x and y are between ASCII 0 and 127. I hope
that it's enough to thwart the MD5 collision attack, but liberal
enough to tolerate the range of broken POP servers out there. The @y
test could be easily removed if necessary.

Comments?

[Rocco Rutte]

Hi,

* Brendan Cully [07-04-02 15:31:14 -0700] wrote:
>On Sunday, 18 March 2007 at 17:36, Rocco Rutte wrote:

>>  I was looking at some mutt code for this issue and other issues that 
>>  report broken threading upon invalid message-ids. It seems that mutt 
>>  happily accepts the following syntax: '<.*>' which is just plain wrong.

>>  I looked at rfc822.c to try to reuse address parsing for parsing 
>>  message-ids but failed since I didn't have much time and the quote is 
>>  quite complex.

>>  Even though adopting your code for mutt would be quite easy, I'm not 
>>  yet sure what to do in case of validation errors.

>>  Say we get '<foobar>' during APOP authentication; should be really 
>>  reject that and report failed authentication? If a message has 
>>  '<foobar>' as message-id and others have it in their References: 
>>  header, should we really ignore it and break threading?

>Here's a patch that does a really minimal check that the message ID is
>of the form <x@y> where x and y are between ASCII 0 and 127. I hope
>that it's enough to thwart the MD5 collision attack, but liberal
>enough to tolerate the range of broken POP servers out there. The @y
>test could be easily removed if necessary.

>Comments?

Adding a new method is one way, I hoped to find some way to reuse the 
address parser. But as that's quote complex, I think it's okay for now. 
The only thing I saw was that checking for 'l>127' is probably not 
enough as you also want to check for 'l<32'.

   bye, Rocco

[brendan]

From the BNR, 0-31 appears to be legal when quoted in the local part. As long as the current MD5 collision generators need characters above 127, I think this is OK.

[Brendan Cully]

On Saturday, 07 April 2007 at 21:22, Matthias Andree wrote:
> Brendan Cully <brendan@kublai.com> writes:
> 
> > On Sunday, 18 March 2007 at 17:36, Rocco Rutte wrote:
> >>  I was looking at some mutt code for this issue and other issues that 
> >>  report broken threading upon invalid message-ids. It seems that mutt 
> >>  happily accepts the following syntax: '<.*>' which is just plain wrong.
> >> 
> >>  I looked at rfc822.c to try to reuse address parsing for parsing 
> >>  message-ids but failed since I didn't have much time and the quote is 
> >>  quite complex.
> >> 
> >>  Even though adopting your code for mutt would be quite easy, I'm not 
> >>  yet sure what to do in case of validation errors.
> >> 
> >>  Say we get '<foobar>' during APOP authentication; should be really 
> >>  reject that and report failed authentication? If a message has 
> >>  '<foobar>' as message-id and others have it in their References: 
> >>  header, should we really ignore it and break threading?
> >
> > Here's a patch that does a really minimal check that the message ID is
> > of the form <x@y> where x and y are between ASCII 0 and 127. I hope
> > that it's enough to thwart the MD5 collision attack, but liberal
> > enough to tolerate the range of broken POP servers out there. The @y
> > test could be easily removed if necessary.
> 
> May I again offer to use my code here which I deem a *COMPLETE*
> RFC822-validation:
> <http://mknod.org/svn/fetchmail/branches/BRANCH_6-3/rfc822valid.c>

I'm afraid that doing heavy validation may introduce interoperability
problems with some buggy POP servers. Since odd timestamps are
generally harmless in this context, I'd rather do the minimum needed
to suppress this vulnerability than enforce strict compliance with the
RFC.

[Matthias Andree]

Brendan Cully <brendan@kublai.com> writes:

>> May I again offer to use my code here which I deem a *COMPLETE*
>> RFC822-validation:
>> <http://mknod.org/svn/fetchmail/branches/BRANCH_6-3/rfc822valid.c>
>
> I'm afraid that doing heavy validation may introduce interoperability
> problems with some buggy POP servers. Since odd timestamps are
> generally harmless in this context, I'd rather do the minimum needed
> to suppress this vulnerability than enforce strict compliance with the
> RFC.

I have yet to see a server that sends a broken APOP challenge
(timestamp). Those I checked were all very conservative.

And making users complain to their ISPs about broken servers is also a
good thing.

APOP is "for lack of a stronger authenticator" anyways, and since my
upstreams all have at least proper SSL certificates that I can validate
to fend off MITM attacks, I couldn't care less about
interoperability.

The code as shown works on the servers I have access to - that's about
as much as matters to me.

I'm well aware that this isn't representative, yet I think that the more
you accept, the more susceptible you are to Leurent's CVE-2007-1558
attack - and that's avoidable.

[brendan]

(In [3d1d7f6cf693]) Validate msgid in APOP authentication. Closes #2846