Re: Forgery limits in QUIC

[Ted Hardie <[e-mail]>]

On Thu, Apr 30, 2020 at 11:15 PM Martin Thomson <[e-mail]> 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.
>
>
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

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