Re: Forgery limits in QUIC

Ted Hardie <ted.ietf@gmail.com> Sat, 02 May 2020 16:48 UTC

Return-Path: <ted.ietf@gmail.com>
X-Original-To: quic@ietfa.amsl.com
Delivered-To: quic@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id BD52B3A15CB for <quic@ietfa.amsl.com>; Sat, 2 May 2020 09:48:36 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.097
X-Spam-Level:
X-Spam-Status: No, score=-2.097 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id OLzwjsLJZZYa for <quic@ietfa.amsl.com>; Sat, 2 May 2020 09:48:33 -0700 (PDT)
Received: from mail-ot1-x32c.google.com (mail-ot1-x32c.google.com [IPv6:2607:f8b0:4864:20::32c]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id CBC543A156D for <quic@ietf.org>; Sat, 2 May 2020 09:48:28 -0700 (PDT)
Received: by mail-ot1-x32c.google.com with SMTP id i27so5133247ota.7 for <quic@ietf.org>; Sat, 02 May 2020 09:48:28 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=cjrpxCBpgCUZqSAsO74Yz+V4y5bUwjGmnq0km4EC764=; b=YdTStSz3W5cuTMv/fc/TnggWA7B0JTj1zJYaqWKhJV01b/mc+2at2t8VkOOJPrfIm2 bKjG8zfk2CimM5c1GOnWM2+PHO07NyfKb/JHPoDO72aXvGhH/ttm5C13M0233oMlVeOR cyHZhkk5364MrKejF+tqMZp0fSFUe72cJrQFu6GNByGGy76FuQ/q3Ige9OzSsgongQEW qSgkk1Qd4AkmxX/TTuY43qzMFFV8uso27dpyBzqoM1tBIUrjO9wWAx90TauVLhGWk8rb LDXSxQKo6BvjK5x8TPleZziqbrmqzhiJVwZPBJMjNhfh5RRI7tG3Wp+JhA1v20r9PyK5 Kdjg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=cjrpxCBpgCUZqSAsO74Yz+V4y5bUwjGmnq0km4EC764=; b=Gp7cjp7wURXMjqu5BEtLLbqq/d97K5e0LjB/PgUUBBwg5TSn72MU5esxHtIY/OBacP pigm/3KB8OEExyqiIl/alBbLeEa47XQbuZeG4IpiJRSJezU07zFZGJ6qmPg8ikyuX1as iL/UTcpPutJk2H1u52z5LgDMhX1sZIt5ynjd1uniwxCikCz7XaK/Q1fjqe6kR/v1gxzr 5nKYBsN+zjJeLXWFp0n2tQNUiw1f7gdPd6XfXRxlwEJ6uoQDyDrzA2tDDDO0DE1MpMau 76EDvHBW81052oO3CnSShqbN98S+uLH4Rx7pJ/I3DPVY/0l7XdQEaO+fpeeEj0pn32cf skVw==
X-Gm-Message-State: AGi0PuYrg0/5+di0uOEgedyXBUlpKq5KbnQyl6bKpeXxHw9l5/VQ6wkW U4cn1nXqvRrV8U4Pl6oOR4sSe1bKlLSd3IAQTChu0lFBHeQ=
X-Google-Smtp-Source: APiQypKwmGPyCNBrk+J9Zx5M3gt54pWzPCRs9W4m20G0heF4NMYjKdz2qxevqUhPFbCc1TNAswYfCVtOKGfwL8ut9Tk=
X-Received: by 2002:a05:6830:1687:: with SMTP id k7mr8159498otr.49.1588438108059; Sat, 02 May 2020 09:48:28 -0700 (PDT)
MIME-Version: 1.0
References: <c32379cb-43c1-4db8-9f0a-b7294085dd6d@www.fastmail.com> <d7f385d4-b6cb-4565-ba35-4c096239fd34@www.fastmail.com>
In-Reply-To: <d7f385d4-b6cb-4565-ba35-4c096239fd34@www.fastmail.com>
From: Ted Hardie <ted.ietf@gmail.com>
Date: Sat, 2 May 2020 09:48:01 -0700
Message-ID: <CA+9kkMDDW-b4B=Ct52BBgS2s7SOiwODQkEZ=POc-_ykkUQmuzQ@mail.gmail.com>
Subject: Re: Forgery limits in QUIC
To: Martin Thomson <mt@lowentropy.net>
Cc: IETF QUIC WG <quic@ietf.org>
Content-Type: multipart/alternative; boundary="0000000000002dbeef05a4ad1195"
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/P9wSSyBdD7TUOk_A9Z5pUhvCVSM>
X-BeenThere: quic@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Main mailing list of the IETF QUIC working group <quic.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/quic>, <mailto:quic-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/quic/>
List-Post: <mailto:quic@ietf.org>
List-Help: <mailto:quic-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/quic>, <mailto:quic-request@ietf.org?subject=subscribe>
X-List-Received-Date: Sat, 02 May 2020 16:48:38 -0000

On Thu, Apr 30, 2020 at 11:15 PM Martin Thomson <mt@lowentropy.net> 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.
> >
> >
>
>