CCM/GCM implementation defect

CCM/GCM implementation defect

[Herbert Xu]

Hi:

It looks like our IPsec implementations of CCM and GCM are buggy
in that they don't include the IV in the authentication calculation.

This definitely breaks interoperability with anyone who implements
them correctly.  The fact that there have been no reports on this
probably means that nobody has run into this in the field yet.

On the security side, this is probably not a big deal for CCM
because it always verifies the authentication tag after decryption.
But for GCM this may be a DoS issue as an attacker could modify
the IV without triggering the authentication check and thus cause
an unnecessary decryption.  For both CCM and GCM this will result
in random data injected as a packet into the network stack which
hopefully will be dropped.

In order to fix this without breaking backwards compatibility,
my plan is to introduce new templates such as rfc4106v2 which
implement the RFC correctly.  The existing templates will be
retained so that current users aren't broken by the fix.

Once the kernel side is complete we could then get the user-space
implementors to update their tools to request for the new v2
templates.

Comments?

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: CCM/GCM implementation defect

[David Miller]

From: Herbert Xu <herbert@gondor.apana.org.au>
Date: Thu, 23 Apr 2015 11:26:20 +0800

> In order to fix this without breaking backwards compatibility,
> my plan is to introduce new templates such as rfc4106v2 which
> implement the RFC correctly.  The existing templates will be
> retained so that current users aren't broken by the fix.
> 
> Once the kernel side is complete we could then get the user-space
> implementors to update their tools to request for the new v2
> templates.
> 
> Comments?

At first glance this seems like a very reasonable approach.

Re: CCM/GCM implementation defect

[Horia Geantă]

On 4/23/2015 6:26 AM, Herbert Xu wrote:
> Hi:
>
> It looks like our IPsec implementations of CCM and GCM are buggy
This applies also to GMAC (rfc4543), right?

> in that they don't include the IV in the authentication calculation.
>
> This definitely breaks interoperability with anyone who implements
> them correctly.  The fact that there have been no reports on this
> probably means that nobody has run into this in the field yet.
Does this mean that even the test vectors (crypto/testmgr.h) are broken?

Thanks,
Horia

Re: CCM/GCM implementation defect

[Herbert Xu]

On Thu, Apr 23, 2015 at 12:03:38PM +0300, Horia Geantă wrote:
> This applies also to GMAC (rfc4543), right?

No RFC4543 appears to be correctly implemented.

> Does this mean that even the test vectors (crypto/testmgr.h) are broken?

Indeed.  The test vectors appear to be generated either through
our implementation or by one that is identical to us.

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: CCM/GCM implementation defect

[Martin Willi]

Hi Herbert,

> > Does this mean that even the test vectors (crypto/testmgr.h) are broken?
> 
> Indeed.  The test vectors appear to be generated either through
> our implementation or by one that is identical to us.

I'm not sure about that. RFC4106 refers to [1] for test vectors, which
is still available at web.archive.org [2].

When looking for example at Test Case 3, this is the same as in a newer
revision of the document [3]. That looks exactly the same as
aes_gcm_enc_tv_template[2] from testmgr.h.

We by the way use test vectors in userland from the same document to
verify our own GCM backend, our OpenSSL backend and an AESNI/PCLMULQD
backend. And I've never heard of any incompatibilities.

Regards
Martin

[1]http://csrc.nist.gov/CryptoToolkit/modes/proposedmodes/gcm/gcm-spec.pdf
[2]http://web.archive.org/web/20070712195408/http://csrc.nist.gov/CryptoToolkit/modes/proposedmodes/gcm/gcm-spec.pdf
[3]http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/gcm/gcm-revised-spec.pdf

Re: CCM/GCM implementation defect

[Herbert Xu]

On Thu, Apr 23, 2015 at 11:58:52AM +0200, Martin Willi wrote:
>
> I'm not sure about that. RFC4106 refers to [1] for test vectors, which
> is still available at web.archive.org [2].
> 
> When looking for example at Test Case 3, this is the same as in a newer
> revision of the document [3]. That looks exactly the same as
> aes_gcm_enc_tv_template[2] from testmgr.h.

These are GCM test vectors, not RFC4106 test vectors so they are
of no use when you're testing whether the IPsec IV (which is not
the same thing as the GCM IV) is included in the authentication
or not.

AFAIK GCM itself is implemented correctly.  It's only the IPsec
wrapper around it (rfc4106 in particular) that's broken.

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: CCM/GCM implementation defect

[Steffen Klassert]

On Thu, Apr 23, 2015 at 11:26:20AM +0800, Herbert Xu wrote:
> Hi:
> 
> It looks like our IPsec implementations of CCM and GCM are buggy
> in that they don't include the IV in the authentication calculation.

Seems like crypto_rfc4106_crypt() passes the associated data it
got from ESP directly to gcm, without chaining with the IV.

> 
> This definitely breaks interoperability with anyone who implements
> them correctly.  The fact that there have been no reports on this
> probably means that nobody has run into this in the field yet.
> 
> On the security side, this is probably not a big deal for CCM
> because it always verifies the authentication tag after decryption.
> But for GCM this may be a DoS issue as an attacker could modify
> the IV without triggering the authentication check and thus cause
> an unnecessary decryption.  For both CCM and GCM this will result
> in random data injected as a packet into the network stack which
> hopefully will be dropped.
> 
> In order to fix this without breaking backwards compatibility,
> my plan is to introduce new templates such as rfc4106v2 which
> implement the RFC correctly.  The existing templates will be
> retained so that current users aren't broken by the fix.

Adding a second template for the correct implementation is
probaply the only thing that we can do if we don't want to
break backwards compatibility. But maybe we can add a warning
to the old implementation, such that users notice that they
use a broken version.

Re: CCM/GCM implementation defect

[Martin Willi]

Hi Steffen,

> > It looks like our IPsec implementations of CCM and GCM are buggy
> > in that they don't include the IV in the authentication calculation.
> 
> Seems like crypto_rfc4106_crypt() passes the associated data it
> got from ESP directly to gcm, without chaining with the IV.

Do you have any pointer for me where this is defined? Why is it needed,
given that GCM implicitly authenticates the IV by using it in Y0?

Also, I've just verified that a tunnel between the Windows Filtering
Platform and Linux 3.13 using AES128GCM16 works just fine. So if we do
something wrong, the problem does not only affect Linux.

Regards
Martin

Re: CCM/GCM implementation defect

[Paul Wouters]

On 04/23/2015 07:45 AM, Steffen Klassert wrote:
> On Thu, Apr 23, 2015 at 11:26:20AM +0800, Herbert Xu wrote:
>> Hi:
>>
>> It looks like our IPsec implementations of CCM and GCM are buggy
>> in that they don't include the IV in the authentication calculation.
> 
> Seems like crypto_rfc4106_crypt() passes the associated data it
> got from ESP directly to gcm, without chaining with the IV.
> 
>>
>> This definitely breaks interoperability with anyone who implements
>> them correctly.  The fact that there have been no reports on this
>> probably means that nobody has run into this in the field yet.
>>
>> On the security side, this is probably not a big deal for CCM
>> because it always verifies the authentication tag after decryption.
>> But for GCM this may be a DoS issue as an attacker could modify
>> the IV without triggering the authentication check and thus cause
>> an unnecessary decryption.  For both CCM and GCM this will result
>> in random data injected as a packet into the network stack which
>> hopefully will be dropped.
>>
>> In order to fix this without breaking backwards compatibility,
>> my plan is to introduce new templates such as rfc4106v2 which
>> implement the RFC correctly.  The existing templates will be
>> retained so that current users aren't broken by the fix.
> 
> Adding a second template for the correct implementation is
> probaply the only thing that we can do if we don't want to
> break backwards compatibility. But maybe we can add a warning
> to the old implementation, such that users notice that they
> use a broken version.

Unless we have a cryptographer indicate to us how that this mistake does not significantly reduce or break the confidentiality and authentication, I do not
think we should keep a known broken implementation around. Lets say this brings GCM security down to ROT13, then it just needs to die without keeping
interoperability.

Additionally, looking at how long we suffered and still suffer from defaulting to something broken (sha2_256 truncation) I'm really not in favour of keeping
broken crypto implementations around.

Paul

Re: CCM/GCM implementation defect

[Herbert Xu]

On Thu, Apr 23, 2015 at 03:24:59PM +0200, Martin Willi wrote:
>
> Do you have any pointer for me where this is defined? Why is it needed,
> given that GCM implicitly authenticates the IV by using it in Y0?

The IV if present must be covered by the ICV.  This is required
by RFC4303 (section 2).  But really it's quite obvious.  If you
don't authenticate the IV, then I can easily inject random crap
into your network by changing the IV.

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: CCM/GCM implementation defect

[Herbert Xu]

On Thu, Apr 23, 2015 at 01:45:34PM +0200, Steffen Klassert wrote:
>
> Adding a second template for the correct implementation is
> probaply the only thing that we can do if we don't want to
> break backwards compatibility. But maybe we can add a warning
> to the old implementation, such that users notice that they
> use a broken version.

If we are going to do a warning I think the place to do it would
be in xfrm_algo.c.  We could add an insecure/warning flag and if
then print a warning if said algorithm is used.

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: CCM/GCM implementation defect

[Herbert Xu]

On Thu, Apr 23, 2015 at 03:24:59PM +0200, Martin Willi wrote:
>
> Do you have any pointer for me where this is defined? Why is it needed,
> given that GCM implicitly authenticates the IV by using it in Y0?

Actually you're quite right.  Both GCM and CCM implicitly includes
the IV in the authentication tag.

In fact after reviewing the two relevant RFCs (4106/4309) it seems
that we are correct after all since they explicitly exclude the IV
from the AAD.

Now we just need to figre out whether we're still OK with RFC4543.

Sorry for the false alarm.

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: CCM/GCM implementation defect

[Herbert Xu]

On Fri, Apr 24, 2015 at 01:30:00PM +0800, Herbert Xu wrote:
> Now we just need to figre out whether we're still OK with RFC4543.

Looks like we're OK here too as the diagram in section 3.5 says
that the IV should be included in the AAD.

So we're all good!

Thanks,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt