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

Watson Ladd <> Thu, 02 January 2014 22:26 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 8E9131AC85E for <>; Thu, 2 Jan 2014 14:26:31 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Status: No, score=-2 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, SPF_PASS=-0.001] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id c1GsXCUO6DPb for <>; Thu, 2 Jan 2014 14:26:29 -0800 (PST)
Received: from ( [IPv6:2a00:1450:400c:c05::230]) by (Postfix) with ESMTP id BEDCE1AC4C1 for <>; Thu, 2 Jan 2014 14:26:28 -0800 (PST)
Received: by with SMTP id hq4so19235928wib.9 for <>; Thu, 02 Jan 2014 14:26:21 -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:content-transfer-encoding; bh=+Oj3AYarZwK0d5u+e6OEclNiW8tJgCAr1wg+Iy2EOVM=; b=lJt2mukzck/Ddnb1CtOnAcmEu29PrEZDZRU8tR3MhNJsZ+VEvIh0Yry/YGCydVcsdN PHCunOpqbg3qtamC1++sARodzt5IASbRkbt8H8WMXJDUV0ciMDvX88YwTCvAsAQyErTc MzHPYj0OnS96N0vsA/YMFtLvYAwNBNStysL1+qRZBqrLxHTouViCoPYgtuB5vcd613Pu O8xq1a+KCc5C3mkGhTE9YQXj6Mj9cDtiMbD/fRag47xR2sNokoL6EnPsU3hiSVCeUSKu z4LvRfy5Iq76hb61LYedgujptNp+GVHptcs7vaTMdbE4b79vcB3KEnP6gEvvdpnAn86X thIg==
MIME-Version: 1.0
X-Received: by with SMTP id dd4mr56580070wib.20.1388701581210; Thu, 02 Jan 2014 14:26:21 -0800 (PST)
Received: by with HTTP; Thu, 2 Jan 2014 14:26:21 -0800 (PST)
In-Reply-To: <>
References: <> <> <> <> <> <> <>
Date: Thu, 02 Jan 2014 17:26:21 -0500
Message-ID: <>
From: Watson Ladd <>
To: Dan Harkins <>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Cc: David McGrew <>, "" <>, 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 22:26:31 -0000

On Thu, Jan 2, 2014 at 5:06 PM, Dan Harkins <> wrote:
> On Thu, January 2, 2014 7:31 am, Watson Ladd wrote:
>> On Jan 2, 2014 10:03 AM, "David McGrew" <> wrote:
>>> Hi Paul,
>>> On 12/30/2013 02:06 PM, Paul Lambert wrote:
>>>> 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
>> repeated.
>> Already exists: it's called CBC mode with HMAC. IVs are random and can
>> repeat.
>   There are still security sensitive requirements on IVs in CBC mode.
> Namely, they have to be unpredictable to the attacker. That problem does
> not exist with SIV. The nonce is completely arbitrary, it can be a counter,
> pseudo-random material, it can be partially derived, it can repeat or not.
>   And as a formal AEAD construction SIV avoids the ad hoc nature in which
> CBC plus HMAC has been put together in the past. It also has a nice and
> fixed API for things like passing AAD as a vector of inputs.

CBC+HMAC is an instance of generic composition. So is GCM and
What sort of device can encrypt, but not use a PRNG or count?

>>>> 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
>> it
>>>> 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.
>   With SIV, authenticity remains and the leakage is limited to knowledge
> that the plaintext equals a prior plaintext, and that is further constrained
> by the fact that it's the same plaintext plus the same AAD, if the AAD
> changes (due to a message header that encapsulates the encrypted blob
> being different) then there is no leakage.
>   It really is the "swiss army knife" of crypto tools-- it slices, it dices,
> it provides misuse-resistant AEAD, it does key wrapping with AAD!
> (And it has a security proof behind it too).

It's wonderful, but slow as molasses. 2 AES passes, only 1 of which
can be parallelized.
For the example of mesh networking it certainly has a place, but I
don't know if the security
is really that great for that application.

For example, imagine a simple message format with (sender, dest) as
header and a temperature as
the message. A mesh network passing around temperature measurements
will reveal a lot to a passive attacker:
remember temperatures are continuous, so all you need is the direction
change the same or different as before to
see just about everything.

Add a counter and everything is golden. But you need that counter. And
if you have a counter, nonce-based misuse-resistant
is just fine, and moreover can be done faster than SIV at the cost of
leaking common prefixes.

Authenticity doesn't make sense with repeated nonces. All you get is
the attacker cannot introduce new messages, but
they can still repeat old ones. This can be enough to have some fun.

>   regards,
>   Dan.
Watson Ladd

"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin