[Cfrg] two-pass modes of operation

David McGrew <mcgrew@cisco.com> Thu, 04 August 2011 13:13 UTC

Return-Path: <mcgrew@cisco.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id ABCFF21F8557 for <cfrg@ietfa.amsl.com>; Thu, 4 Aug 2011 06:13:57 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -102.705
X-Spam-Status: No, score=-102.705 tagged_above=-999 required=5 tests=[AWL=-0.106, BAYES_00=-2.599, USER_IN_WHITELIST=-100]
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id h7zJFxgm4xaU for <cfrg@ietfa.amsl.com>; Thu, 4 Aug 2011 06:13:56 -0700 (PDT)
Received: from rcdn-iport-8.cisco.com (rcdn-iport-8.cisco.com []) by ietfa.amsl.com (Postfix) with ESMTP id B844621F854E for <cfrg@irtf.org>; Thu, 4 Aug 2011 06:13:56 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=mcgrew@cisco.com; l=4039; q=dns/txt; s=iport; t=1312463651; x=1313673251; h=cc:message-id:from:to:in-reply-to: content-transfer-encoding:mime-version:subject:date: references; bh=3aulq5aQhMZ/pZ4DN5jlPhe1Q9c2ULbJrN8bVrwgXnk=; b=ZwJe8T56g8O32fZsISOv3YocxP8FbmvajmZdi2j8RtXkNcR40oQanlum H3DPJvjDgNYn08XLeQJYOy0L+149bqqiYQ4SRPxykpg5I1E/aPkCCaKuE qC1YYSeCdd/8NY9ciPB6cJgBi2ZCxkL1hQGsSKgHEH52BRAloFFZRd5qm U=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AvgAAAKbOk6rRDoH/2dsb2JhbABCDpd8j1x3gUABAQEBAgEBAQEPASUCNAsFBwQZAwQBASgHJx8JCAYBEgkZh0oEonsBnwSFY18Eh1qLIZAtVw
X-IronPort-AV: E=Sophos;i="4.67,316,1309737600"; d="scan'208";a="9629332"
Received: from mtv-core-2.cisco.com ([]) by rcdn-iport-8.cisco.com with ESMTP; 04 Aug 2011 13:14:08 +0000
Received: from stealth-10-32-254-211.cisco.com (stealth-10-32-254-211.cisco.com []) by mtv-core-2.cisco.com (8.14.3/8.14.3) with ESMTP id p74DE6lK008879; Thu, 4 Aug 2011 13:14:07 GMT
Message-Id: <2022F90C-089D-44B1-AB63-198FA402A76B@cisco.com>
From: David McGrew <mcgrew@cisco.com>
To: Jim Schaad <ietf@augustcellars.com>, Peter Gutmann <pgut001@cs.auckland.ac.nz>, Dan Harkins <dharkins@lounge.org>
In-Reply-To: <005f01cc46fe$2a89e760$7f9db620$@augustcellars.com>
Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes
Content-Transfer-Encoding: 7bit
Mime-Version: 1.0 (Apple Message framework v936)
Date: Thu, 4 Aug 2011 06:14:06 -0700
References: <49fd928bf94d1d1920df676bb61fa198.squirrel@www.trepanning.net> <E1QjRXj-0002HE-HM@login01.fos.auckland.ac.nz> <005f01cc46fe$2a89e760$7f9db620$@augustcellars.com>
X-Mailer: Apple Mail (2.936)
Cc: cfrg@irtf.org
Subject: [Cfrg] two-pass modes of operation
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.12
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, 04 Aug 2011 13:13:57 -0000

Agreed.  There is a question that always struck me as important, but  
one which I've never heard discussed: how do SIV and similar modes  
compare with Encryption with Associated Data (EAD) modes, like those  
defined in IEEE 1619.2 (EME2-AES and XCB-AES)?   These modes are the  
state of the art in "wide block encryption" as used for disk block  
encryption and suchlike; they are tweakable pseudorandom permutations  
with arbitrary-length inputs.

Both EAD modes require two serialized passes over the plaintext for  
both the sender and the recipient, in contrast to SIV, which  
inconveniences the sender more than the recipient; the EAD modes  
inconvenience the recipient as well.  So, if the sender can afford two  
passes, perhaps it would be reasonable to expect the receiver to  
perform two passes as well?

The IEEE EAD modes are not directly comparable to SIV, since the  
latter provides authentication.  But authentication could be added via  
a post-decryption redundancy check, as done in RFC 5649, so it is  
reasonable to compare them.

I believe that SIV and the EAD modes have roughly comparable  
computational cost.  Both EAD modes require two passes over the  
plaintext, but can perform all of the needed computations using  
paralellism, or a full pipeline.  This is in contrast to SIV, which  
uses CBC-MAC as an internal component and thus can't utilize  
paralellism or pipelining.

To my mind, the interesting questions here are:

1.  Where would misuse resistant crypto be valuable?

2.  Where can we tolerate the performance hit of two serialized passes  
over the plaintext?   How much advantage is it to have the receiver do  
one pass while the sender does two?

3.  How does performance compare between the EAD modes and SIV,  
especially in the scenarios identified in #1?


Full disclosure: my employer holds IPR on XCB.  Sorry, I know that IPR  
is cholesterol in the bloodstream of standards.

On Jul 20, 2011, at 9:57 AM, Jim Schaad wrote:

> That is completely correct.  SIV requires two passes for the sender  
> - but
> only one pass for the recipient.
>> -----Original Message-----
>> From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] On  
>> Behalf Of
>> Peter Gutmann
>> Sent: Wednesday, July 20, 2011 12:50 AM
>> To: dharkins@lounge.org; pgut001@cs.auckland.ac.nz
>> Cc: mcgrew@cisco.com; cfrg@irtf.org
>> Subject: Re: [Cfrg] request for comments on "Generation of  
>> Deterministic
>> Initialization Vectors (IVs) and Nonces"
>> "Dan Harkins" <dharkins@lounge.org> writes:
>>> Let me remind everyone of SIV mode*. It's a CTR mode derivative  
>>> but is
>>> resistant to nonce misuse. Unlike CBC, the nonce doesn't need to be
>>> unguessable. And it even provides a strong assurance of security  
>>> if the
>>> nonce is reused.
>> Doesn't SIV require the entire message to be buffered, which makes it
>> unusable in streaming implementations?
>> [Checks]
>> Unless I've misinterpreted some part of Fig.3 and Fig.8 of RFC  
>> 5297, this
> can't
>> be used in a streaming implementation because the CMAC operation to
>> create the IV has to make a complete pass over the message before  
>> you can
>> start encrypting (this is also similar to a key-wrap mechanism that  
>> Colin
> Plumb
>> and I came up with for RFC 3211, although it'd need a tweak to use a
> proper
>> MAC for full integrity-protection, it was designed for non- 
>> expanding 512-
>> byte disk sector encryption and dates from the early 1990s, so it  
>> predates
>> pretty much all of the work that newer modes and mechanisms are  
>> built on).
>> SIV is quite nice for something like 802.11, SRTP, DTLS, and  
>> others, but
>> unfortunately won't work as a general-purpose mechanism.
>> Are there any IP issues around SIV?
>> Peter.
>> _______________________________________________
>> Cfrg mailing list
>> Cfrg@irtf.org
>> http://www.irtf.org/mailman/listinfo/cfrg