Subject: Re: Forgery limits in QUIC

From: Dirkjan Ochtman <[email-masked]>
Date: Fri, 1 May 2020 21:47:07 +0200

On Fri, May 1, 2020 at 8:15 AM Martin Thomson <[email-masked]> wrote:

> I realize that this is a fairly dramatic change, but I think we need to
> hold our ciphers to a high standard.  I will attempt to find an analysis
> myself, as I would expect it to exist, but I have a poor history of success
> finding the right cryptographic paper.  If anyone is able to provide
> pointers, that would be appreciated.
>

FWIW, Quinn already doesn't support CCM, so this would be a no-op for us.
Might be interesting to poll if other implementations even support CCM
today?

Thanks for working on this,

Dirkjan

---

From: Florentin Rochet <[email-masked]>
Date: Fri, 1 May 2020 21:51:00 +0200

Hi Martin,

On 01.05.20 08:14, Martin Thomson wrote:
> OK, I thought this would be easy.  I was wrong.  But it still might be easy.
>
> The draft currently defines four AEAD functions.  We have a good analysis for three of those functions.  We lack an analysis of the last.  That is AEAD_AES_128_CCM.
>
> It turns out that we never really had a good analysis of CCM.  TLS 1.3 conveniently fails to say anything about it.
>
> My suggestion is that we remove CCM from QUIC until we have an understanding of its robustness against confidentiality attacks with multiple successful applications of protection AND integrity attacks with multiple forgery attempts.  We need to base our recommendations about limits on something more than what we have now.
>
> I realize that this is a fairly dramatic change, but I think we need to hold our ciphers to a high standard.  I will attempt to find an analysis myself, as I would expect it to exist, but I have a poor history of success finding the right cryptographic paper.

Maybe this formal analysis of CCM helps: 
https://link.springer.com/content/pdf/10.1007/3-540-36492-7_7.pdf

It is dated from 2002, so you might also want to dive within the papers 
that cite this one. The security bound on integrity is a birthday bound 
(AES might be called max 2^64 times).

Best,

Florentin

>    If anyone is able to provide pointers, that would be appreciated.
>
> On Fri, May 1, 2020, at 14:45, Martin Thomson wrote:
>> I have just opened https://github.com/quicwg/base-drafts/issues/3619
>>
>> tl;dr We need to recommend limits on the number of failed decryptions.
>>
>> I am now working on a pull request to add this to the spec.
>>
>> I realize that we're nearing the end, but this is an important security
>> improvement and the result of some good work by cryptography
>> researchers, who have done a lot to improve our confidence that QUIC
>> can deliver on its promises of providing confidentiality and integrity..
>>
>> A big thanks to Felix Günther, Marc Fischlin, Christian Janson, and
>> Kenny Paterson for their work on this.
>>
>>

---

From: Matt Joras <[email-masked]>
Date: Fri, 1 May 2020 13:10:32 -0700

On Thu, Apr 30, 2020 at 11:15 PM Martin Thomson <[email-masked]> wrote:

> The draft currently defines four AEAD functions.  We have a good analysis
> for three of those functions.  We lack an analysis of the last.  That is
> AEAD_AES_128_CCM.
>
> It turns out that we never really had a good analysis of CCM.  TLS 1.3
> conveniently fails to say anything about it.
>
> My suggestion is that we remove CCM from QUIC until we have an
> understanding of its robustness against confidentiality attacks with
> multiple successful applications of protection AND integrity attacks with
> multiple forgery attempts.  We need to base our recommendations about
> limits on something more than what we have now.
>
Is it actually a fairly dramatic change? The supported cipher suite is not
a huge consideration for us, and I would guess this is generally true.
We've only implemented AEAD_AES_128_GCM and AEAD_AES_256_GCM. Perhaps this
is more of a concern for those wishing to ship embedded stacks, since AFAIK
CCM is nominally simpler to implement?

Removing it seems straightforward unless someone was has a good reason to
want to ship CCM specifically.

---

From: Ian Swett <[email-masked]>
Date: Fri, 1 May 2020 17:48:20 -0400

Dropping AEAD_AES_128_CCM is fine for us, since we don't use it.

On Fri, May 1, 2020 at 4:11 PM Matt Joras <[email-masked]> wrote:

>> > can deliver on its promises of providing confidentiality and
>> integrity...
>> >

---

From: Ted Hardie <[email-masked]>
Date: Sat, 2 May 2020 09:48:01 -0700

> conveniently fails to say anything about it.
I asked a few colleagues at Google about this, and one of them provided the
following two references, along with some notes:

A security analysis of AES-CCM is this paper:

J. Jonsson. On the security of CTR + CBC-MAC.
Selected Areas of Cryptography (SAC) 2002.
Available from csrc.nist.gov/encryption/modes/proposedmodes/ or
https://link.springer.com/content/pdf/10.1007%2F3-540-36492-7_7.pdf

Theorem 1 gives a result for the authenticity: Essentially it says that the
probability of a successful forgery with a tag of t bits is about 2^{-t}
for each attempt as long as significantly less than 2^64 blocks are
encrypted or decrypted. The author argues that the actual security might be
stronger than the proven bound in the next section, but it is unclear by
how much.

Theorem 2 gives a result for the privacy:   Essentially this says that the
birthday bound is an upper bound on the number of blocks that can be
encrypted. NIST fixes this number at 2^61. I haven't found an explanation
for this choice. It is quite close to the birthday bound. Maybe NIST
considers a distinguishing attack to be rather harmless.

Both theorems assume that there is no nonce reuse. Thes security bounds are
comparable with the bounds for AES-EAX. They are significantly better than
the bound for AES-GCM, especially when shorter tags are used.

A criticism of AES-CCM is this paper:

A Critique of CCM
P. Rogaway and D. Wagner
https://eprint.iacr.org/2003/070

The main points made in this paper are  that AES-CCM is inefficient and
that users have to juggle between nonce size and message size. I.e. if one
wants to encrypt long messages then the nonce has to be short. Since
shorter nonces have a higher probability to repeat when they are generated
randomly, most of the recommendations I've seen generate nonces by
including a counter value.

This is not my area of expertise, obviously, but I thought forwarding this
along might be useful.  I note that others have said down-thread that they
aren't implementing CCM, which may mean that removing it is the right thing
to do, whatever the analysis may be.

regards,

Ted

---

From: "Martin Thomson" <[email-masked]>
Date: Thu, 07 May 2020 19:46:24 +1000

Good news. We saved CCM.

I consider the pull to be ready for review.  Felix has validated - and corrected - the analysis. Antoine has promised to double check the numbers.  More eyes would be good.

On Fri, May 1, 2020, at 16:14, Martin Thomson wrote:
> The draft currently defines four AEAD functions.  We have a good 
> analysis for three of those functions.  We lack an analysis of the 
> last.  That is AEAD_AES_128_CCM.
> 
> multiple successful applications of protection AND integrity attacks 
> with multiple forgery attempts.  We need to base our recommendations 
> about limits on something more than what we have now.
> 
> hold our ciphers to a high standard.  I will attempt to find an 
> analysis myself, as I would expect it to exist, but I have a poor 
> history of success finding the right cryptographic paper.  If anyone is 
> able to provide pointers, that would be appreciated.
>