Re: [Cfrg] misuse-resistant AEAD (was: Re: CFRG and thwarting pervasive montoring)

Watson Ladd <> Thu, 02 January 2014 15:31 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id B93191AE237 for <>; Thu, 2 Jan 2014 07:31:31 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Status: No, score=-1.999 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, SPF_PASS=-0.001] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id zgfyIJMLx7lu for <>; Thu, 2 Jan 2014 07:31:28 -0800 (PST)
Received: from ( [IPv6:2a00:1450:400c:c00::234]) by (Postfix) with ESMTP id 0435A1AC497 for <>; Thu, 2 Jan 2014 07:31:27 -0800 (PST)
Received: by with SMTP id x13so12380915wgg.31 for <>; Thu, 02 Jan 2014 07:31:20 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=mhsudrfK0yFJRMcxRM4RaMElf7dyBBbXvw+BpXohtmA=; b=RpFGQ3PTWs/Ov3JU10eNmuX9WQaesEVYe5DFvR/+XeaUtycIK8yfrDWBYyW03i6G3I tsurbOdnF48UBI79pV+C8lrypxXT044NA1e7wf57OdwZm5iBuUuc0cfAWZOkUFWiHKm1 0TN8BJvIyxfMW5pcWyD+egVoI5+QVyYHhYur0aKRPVuFktr4mXN7DXqpq5yJ1w6R4lio 1zbmhXFwzN8fR0BLOOe+o/mngtLn4PGQvSS+nE1EDtSlc2xLuYsk4/OJOwaV3zaE2/FU kyWqMBu9OPwLXohvuWwDCdnUGm5vBr5JM74bcEFRav5AKNtl7mkw6Nkl4IbWIkkYNc26 Wr6g==
MIME-Version: 1.0
X-Received: by with SMTP id k18mr54983819wic.44.1388676680486; Thu, 02 Jan 2014 07:31:20 -0800 (PST)
Received: by with HTTP; Thu, 2 Jan 2014 07:31:20 -0800 (PST)
Received: by with HTTP; Thu, 2 Jan 2014 07:31:20 -0800 (PST)
In-Reply-To: <>
References: <> <> <> <> <>
Date: Thu, 02 Jan 2014 10:31:20 -0500
Message-ID: <>
From: Watson Ladd <>
To: David McGrew <>
Content-Type: multipart/alternative; boundary="001a11c229a23f941704eefe7cb4"
Cc: "" <>, Paul Hoffman <>
Subject: Re: [Cfrg] misuse-resistant AEAD (was: Re: CFRG and thwarting pervasive montoring)
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Thu, 02 Jan 2014 15:31:31 -0000

On Jan 2, 2014 10:03 AM, "David McGrew" <> wrote:
> Hi Paul,
> On 12/30/2013 02:06 PM, Paul Lambert wrote:
>> On 12/29/13, 1:12 PM, "Paul Hoffman" <> wrote:
>>> On Dec 29, 2013, at 11:12 AM, Stephen Farrell <
>>> wrote:
>>>> . . .
>>>> I would love to see ongoing detailed work within
>>>> CFRG as to how to counter pervasive monitoring.
>>> Wearing your perpass hat, how can CFRG help? I ask this because I have
>>> seen little on the perpass mailing list that indicated that an even
>>> problem has been lack of crypto, or the use of crypto that is thought to
>>> be breakable. What type of crypto research or assessment would help
>>> perpass?
>> In the past I¹ve never considered CFRG a viable discussion forum for
>> making an impact by creating or approving new algorithms Š but if it is:
>>         We need an Œapproved' nonce-insensitive AEAD algorithm.
>> I¹m designing multicast communications in a mesh topology and CCM and GCM
>> suffer from N^2 complexity (since they require unique nonce/key).  Yes Š
>> there are ways that some link proposals like 802.1ae mitigate the issue
>> using device addresses as part of the key setup.  The best solution is a
>> nonce-insensitive AEAD.
> I agree.   The best solution would be an authenticated encryption
algorithm that did not require a nonce as input.   An alternative which is
not quite as good would be an algorithm that requires a nonce as input, but
which has security that suffers only a minimal degradation if nonces are

Already exists: it's called CBC mode with HMAC. IVs are random and can
>> We already have an RFC for SIV which is deterministic and a decent
>> solution, but it is not ŒNIST¹ approved, so I have problems introducing
>> into consumer equipment.  It¹s also a little slow Š but I¹m not sure that
>> efficiency should be the primary evaluation criteria.
> All valid points.   SIV shows that it is possible to have a
misuse-resistant algorithm.  It may not have all of the properties that one
might want in an algorithm (for instance: more amenable to parallel
processing), but it shows that we can achieve more robust security than
nonce-based AEAD.

Deterministic encryption leaks considerable information when used on low
entropy messages. Nonce reuse resistant nonce based MAC and encryption
algorithms exist today, namely CBC initialized with the encryption of a
counter and HMAC.

>> I¹ve asked NIST in the past and they have expressed no interest in the
>> problem.  It used to be very important for algorithms to be NIST
>>   Do we need to find/create a new review and approval process for
>> algorithms that can be referenced by commercial products?
> NIST is responsive when the industry and standards organizations adopt
new mechanisms that have some clear advantage over previous mechanisms.
The problem is that NIST and the industry have gotten into a deadlock (or
deadly embrace) situation: the industry now hesitates to adopt algorithms
that are not NIST approved, and NIST hesitates to approve algorithms that
have not seen any adoption by industry or standards.    We can not just
blame NIST for being overly conservative here; there are many more
algorithm proposals than they could reasonably incorporate into their
processes.   To break the deadlock, we (CFRG and the industry) need to be
willing to adopt a new algorithm, or at least we need to be willing to take
further steps towards adoption than we have shown in the past. Some things
that CFRG could do: write a requirements document that demonstrates the
need for a new algorithm, publish a document specifying the new algorithm,
document the fact that there is a set of adopters or potential adopters
that are interested, and lastly, reach out to NIST (for instance, with a
question like "do you have any particular concerns about this algorithm
that would prevent you from approving it?").

CAESAR is going on right now with regards to AE. If you have requirements
that haven't been in the call, tell us about them.

> Going further, it might facilitate adoption if all of the information
needed to validate an implementation of an algorithm were provided.   That
is, a complete set of test cases in a format suitable for automated
validation (as done in the NIST Crypto Module Validation Program, or CMVP)
would make it easier to incorporate the algorithm in an
implementation-validation process.
> The CMVP is run jointly by the U.S. and Canada.   It would be good to
hear from the rest of the world on this topic.  I suspect that many vendors
outside of Northa America want to sell into the NA market, and thus also
would favor NIST approval of new algorithms. What is less clear is the role
of nation-specific block ciphers (or other algorithms), which is a topic
unto itself.
> David

>> Paul
>>> Note that deprecating the use of crypto that is widely known to be
>>> is the purview of IETF WGs, not the CFRG. The relevant WGs (particularly
>>> TLS) seem to already be doing that.
>>> --Paul Hoffman
>>> _______________________________________________
>>> Cfrg mailing list
>> _______________________________________________
>> Cfrg mailing list
> _______________________________________________
> Cfrg mailing list