Re: [Cfrg] Do we need a selection contest for AEAD?

Mihir Bellare <> Wed, 24 June 2020 18:44 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 261A23A08CD for <>; Wed, 24 Jun 2020 11:44:32 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.998
X-Spam-Status: No, score=-1.998 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (1024-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id IetOiChsyYrU for <>; Wed, 24 Jun 2020 11:44:30 -0700 (PDT)
Received: from ( [IPv6:2a00:1450:4864:20::52c]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 2A7233A08CA for <>; Wed, 24 Jun 2020 11:44:30 -0700 (PDT)
Received: by with SMTP id z17so2253253edr.9 for <>; Wed, 24 Jun 2020 11:44:30 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=qRji2XTSHGKkpaZndL9q2txmYfpLcxAqkuhTphbxPy4=; b=gz80pqnAF2vIGfjXofnw1vo90LvyosyIcQUTADcXTI8zUhXJHAxz/rhHGZ7hIqRm/F q8MLICGX5AdORWJbTBEX4lPJMCLUJ+p0cLaYhRT+kMZMkLpcDMGDKut+4C0Tn21dgXRw AZzeApDoQ4GfhbhwOi8Y9wbx29yuK7usV22S4=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=qRji2XTSHGKkpaZndL9q2txmYfpLcxAqkuhTphbxPy4=; b=ZXBweuDx/oD43snkqsP4xVX9dR8mWXFfRWFTX70FF4qFvi5z/H6QAGgO/ch55/W2r2 Z2Y3S+uJ3NJ0ACxFVVPVJNcxJALG8XlT46EjRNdjvJz/gpKxVc1sHFNv/9oW/27QA1EZ 3YSYsfUWoYmFkAfZKfyIkMQv9sySxKNI5RoN23evqcPqujHBXQ+5fT1Tr1vofLjBhVqU 71NUku0ya99M5a+ydQsbZeLllRNtbbxZYNTtFP7FjQJstdpPlWANB94cO1Gn+UfIk/Ez Ok66mVUk6YK5k3oh+fL6SujBInX7l/DNEF9KnU09r9QvHIzkGdUtj+iAUwsVAHF+VZ7s q9ew==
X-Gm-Message-State: AOAM530kFfjyOlsW9TLAlgCQQ6/p5QUyQu2RlieZYfwiZbN6BHZypAnK Ti2+rWPN6MikZRnVO+JIZB2HbmoJADKyWxvxdbFz/A==
X-Google-Smtp-Source: ABdhPJx5fwOqAgVZD/8YGqxZw91LsnEyewWZJjzY8e1ZNqcxVngRp1PKka2F3Gglq9HMiUgmfEpsKsrpi64Uh+stfO0=
X-Received: by 2002:a05:6402:1153:: with SMTP id g19mr27441933edw.127.1593024268472; Wed, 24 Jun 2020 11:44:28 -0700 (PDT)
MIME-Version: 1.0
References: <> <>
In-Reply-To: <>
From: Mihir Bellare <>
Date: Wed, 24 Jun 2020 11:43:52 -0700
Message-ID: <>
To: Paul Grubbs <>
Cc: "Stanislav V. Smyshlyaev" <>, CFRG <>
Content-Type: multipart/alternative; boundary="000000000000a42c0905a8d8ddb7"
Archived-At: <>
Subject: Re: [Cfrg] Do we need a selection contest for AEAD?
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 24 Jun 2020 18:44:32 -0000

> it might be good to have the first round be more of a "meta-competition"
> for discussing and prioritizing requirements and use cases.

Responding here both to the above and to Thomas's post about Deoxys. I
think we need to step back to consider that what we call AEAD is not
providing the message privacy that we think it is, and how that affects

RFC 5116 <> says:  "there is no need to
coordinate the details of the nonce format between the encrypter and the
decrypter, as long the entire nonce is sent or stored with the ciphertext
and is thus available to the decrypter ... the nonce MAY be stored or
transported with the ciphertext ... "

What [BNT19] <> points out is that if
you send the nonce with the ciphertext, for certain choices of nonces, you
can compromise privacy of the message. This is kind of obvious in
retrospect; the nonce can be message dependent. The difficulty is that in
AEAD (which we call AE1), the nonce is assumed magically provided to the
decryptor; the AEAD model does not say it is safe to transmit it.  [BNT19]
<> defines a stronger AE2 goal which
does what AEAD seems to have been understood to do, namely provide message
privacy for any (non-repeating) choice of nonces, even if they are
transmitted. This is done via nonce hiding, so the latter is not just about
hiding the nonce itself (which is an added benefit) but, even before that,
about hiding the message when nonces are visible.

Message-dependent nonces are not a likely choice, but they are allowed
under RFC 5116. If one continues to use AEAD, I think in future standards,
language as used in RFC 5116 should be changed to say that it is only with
nonces that do not depend on the message (like random numbers or sequence
numbers) or nonces that are not transmitted. But it is a burden for
implementers to have to figure out if their nonces are conforming. With
AE2, they don't need to; any (non-repeating) nonce choices, even message
dependent, are fine.

On Tue, Jun 23, 2020 at 10:31 PM Thomas Peyrin <>
For nonce-hiding, I wonder if/how the constructions in could be applied on top of these modes

As above, it isn't just for nonce hiding that one would want to apply the
above; it is to have message privacy even for transmitted nonces, meaning
what AEAD was thought to provide. I think the goal for Deoxys and future AE
schemes should be AE2 for this reason.

 As to the methods, yes, one could use them to get AE2. But the bounds
mostly admit a birthday term. You seem to have worked to get good bounds
for Deoxys, so perhaps one could find a direct way to get AE2 for Deoxys
without sacrificing something in the bounds?