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

David McGrew <mcgrew@cisco.com> Thu, 02 January 2014 15:03 UTC

Return-Path: <mcgrew@cisco.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com []) by ietfa.amsl.com (Postfix) with ESMTP id 00B2E1AE329 for <cfrg@ietfa.amsl.com>; Thu, 2 Jan 2014 07:03:27 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -15.039
X-Spam-Status: No, score=-15.039 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_HI=-5, RP_MATCHES_RCVD=-0.538, SPF_PASS=-0.001, USER_IN_DEF_DKIM_WL=-7.5] autolearn=ham
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id VbELgxx0MEYd for <cfrg@ietfa.amsl.com>; Thu, 2 Jan 2014 07:03:25 -0800 (PST)
Received: from rcdn-iport-6.cisco.com (rcdn-iport-6.cisco.com []) by ietfa.amsl.com (Postfix) with ESMTP id 01A651AE59E for <cfrg@irtf.org>; Thu, 2 Jan 2014 07:03:24 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=4959; q=dns/txt; s=iport; t=1388674998; x=1389884598; h=message-id:date:from:mime-version:to:cc:subject: references:in-reply-to:content-transfer-encoding; bh=U2xJqY0BJUGLELDvF/6QIBLGzQad+vM0ayNRo6wXiLA=; b=Fvw7QHQrMTFon7LXrM1VleAD8+SrLy6RJ++5I38qesY5Au4i9DgCV2jq tnnUQ0ziPPVme7Q/iyghu9Vv6Rio4HkoHWBCLLnV0+lGtlyT71H17u6tA BhJ+7gsQb1zNhIYYzqhhXFEoBkFGrMFXLWC1lCO3R9gt8H7Ffno4LjCBK k=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-AV: E=Sophos;i="4.95,591,1384300800"; d="scan'208";a="294907612"
Received: from rcdn-core-6.cisco.com ([]) by rcdn-iport-6.cisco.com with ESMTP; 02 Jan 2014 15:03:17 +0000
Received: from [] (rtp-mcgrew-8913.cisco.com []) by rcdn-core-6.cisco.com (8.14.5/8.14.5) with ESMTP id s02F3GVi014870; Thu, 2 Jan 2014 15:03:17 GMT
Message-ID: <52C57FB4.2050102@cisco.com>
Date: Thu, 02 Jan 2014 10:03:16 -0500
From: David McGrew <mcgrew@cisco.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130922 Icedove/17.0.9
MIME-Version: 1.0
To: Paul Lambert <paul@marvell.com>
References: <CAGZ8ZG2f9QHX40RcB8aajWvEfG0Gh_uewu2Rq7bQGHYNx6cOmw@mail.gmail.com> <52C07436.2040709@cs.tcd.ie> <04C32948-02A2-44F4-B4C1-CF29D4146715@vpnc.org> <CEE6FEE3.2B330%paul@marvell.com>
In-Reply-To: <CEE6FEE3.2B330%paul@marvell.com>
Content-Type: text/plain; charset="windows-1252"; format="flowed"
Content-Transfer-Encoding: 8bit
Cc: "cfrg@irtf.org" <cfrg@irtf.org>, Paul Hoffman <paul.hoffman@vpnc.org>
Subject: [Cfrg] misuse-resistant AEAD (was: Re: CFRG and thwarting pervasive montoring)
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Thu, 02 Jan 2014 15:03:27 -0000

Hi Paul,

On 12/30/2013 02:06 PM, Paul Lambert wrote:
> On 12/29/13, 1:12 PM, "Paul Hoffman" <paul.hoffman@vpnc.org> wrote:
>> On Dec 29, 2013, at 11:12 AM, Stephen Farrell <stephen.farrell@cs.tcd.ie>
>> 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 minor
>> 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 repeated.

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

> 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 approved.
>   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?").

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.


> Paul
>> Note that deprecating the use of crypto that is widely known to be broken
>> 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@irtf.org
>> http://www.irtf.org/mailman/listinfo/cfrg
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg