Re: [Cfrg] Question about the order of hashing

David McGrew <mcgrew@cisco.com> Thu, 05 January 2012 18:22 UTC

Return-Path: <mcgrew@cisco.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id EAF9C21F86E5 for <cfrg@ietfa.amsl.com>; Thu, 5 Jan 2012 10:22:43 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -105.248
X-Spam-Level:
X-Spam-Status: No, score=-105.248 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, J_CHICKENPOX_41=0.6, RCVD_IN_DNSWL_MED=-4, SARE_OBFU_ALL=0.751, USER_IN_WHITELIST=-100]
Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id y-f7obbGuHP4 for <cfrg@ietfa.amsl.com>; Thu, 5 Jan 2012 10:22:39 -0800 (PST)
Received: from mtv-iport-1.cisco.com (mtv-iport-1.cisco.com [173.36.130.12]) by ietfa.amsl.com (Postfix) with ESMTP id 5F1F021F85A0 for <cfrg@irtf.org>; Thu, 5 Jan 2012 10:22:34 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=mcgrew@cisco.com; l=4283; q=dns/txt; s=iport; t=1325787754; x=1326997354; h=cc:message-id:from:to:in-reply-to: content-transfer-encoding:mime-version:subject:date: references; bh=MkTpIvkGCoYXZRN4I7lZ2DpQQHjJA0gwqvPwukS7jVw=; b=kvxurmMGfIrxe65vHlMvLkpLNCw9u4FoxDR1JvaudcKfCn6inUkZdvGW CIrRxPJFkHGe52ol3xd7JehIAlzdcJ4J+xTgVnHNAXc54jo6vV+NGn4PL 3eZHDiyaI6qiut0oZRoESIiJ/DFYVmrJqDodJVFpQ1y2xklpotZDLFoJ8 8=;
X-IronPort-AV: E=Sophos;i="4.71,463,1320624000"; d="scan'208";a="22281168"
Received: from mtv-core-4.cisco.com ([171.68.58.9]) by mtv-iport-1.cisco.com with ESMTP; 05 Jan 2012 18:22:34 +0000
Received: from [10.32.254.210] ([10.32.254.210]) by mtv-core-4.cisco.com (8.14.3/8.14.3) with ESMTP id q05IMXMr019871; Thu, 5 Jan 2012 18:22:33 GMT
Message-Id: <F4E279C1-705D-4F8F-A9A3-7C844039DE30@cisco.com>
From: David McGrew <mcgrew@cisco.com>
To: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>, Yoav Nir <ynir@checkpoint.com>
In-Reply-To: <EE0C2F9E065E634B84FC3BE36CF8A4B2087DE600@xmb-sjc-23e.amer.cisco.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, 5 Jan 2012 10:22:32 -0800
References: <5E6BDD30-3EB8-4FBA-826E-4A44DED36283@checkpoint.com><49D24499-1C16-44C4-84C2-36F94F95235C@cs.columbia.edu> <5C0E5BE9-FE11-46BD-9D91-08FBE0299F10@checkpoint.com> <EE0C2F9E065E634B84FC3BE36CF8A4B2087DE600@xmb-sjc-23e.amer.cisco.com>
X-Mailer: Apple Mail (2.936)
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] Question about the order of hashing
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, 05 Jan 2012 18:22:44 -0000

Thanks Scott for pointing out that the use of the "incremental"  
property can be used here.  Yoav, there are more details on that  
property in <http://www.mindspring.com/~dmcgrew/gmac-incr-c-00.pdf>  
from IEEE SIS 2005, if you are interested.   As far as I know, there  
are no intellectual property considerations that are specific to  
incremental MACs or the use of GCM/GMAC in that manner.

David

On Jan 5, 2012, at 8:26 AM, Scott Fluhrer (sfluhrer) wrote:

>
>
>> -----Original Message-----
>> From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] On Behalf
> Of
>> Yoav Nir
>> Sent: Thursday, January 05, 2012 4:19 AM
>> To: Steven Bellovin
>> Cc: cfrg@irtf.org
>> Subject: Re: [Cfrg] Question about the order of hashing
>>
>>
>> On Jan 5, 2012, at 11:10 AM, Steven Bellovin wrote:
>>
>>>
>>> On Jan 5, 2012, at 2:29 35AM, Yoav Nir wrote:
>>>
>>>> Hi.
>>>>
>>>> When using keyed hash functions such as HMAC, GHash, and CBC-MAC,
>> does the order of the items being concatenated and hashed make any
>> difference to the security properties of the keyed hash?
>>>>
>>>> IOW, does changing HMAC(k, a||b) into HMAC(k, b||a) change the
>> security properties.
>>>>
>>>> My motivation for this question is that I would like to propose a
>> variant for IPsec where the sequence numbers are hashed after the
>> payload rather than before it. Different size packets take different
>> times to hash, so if we try to parallelize IPsec processing,
>> arbitrarily many packets may finish processing before a large single
>> packet has finished processing.
>>>>
>>>> IPsec emitters are required to emit the packets in order of the
>> sequence numbers, but since the sequence numbers (which are sent in
> the
>> clear) are hashed first, they have to be allocated before hashing
>> begins. By moving them to the end of the hash, I can allocate the
>> sequence number after having hashed most of the packet, and have
> nearly
>> constant-time processing after allocating the sequence number.
>>>>
>>>> So is this scheme I'm proposing save, or would it introduce some
>> major vulnerability.
>>>>
>>> What is your traffic model?  If it's a single TCP stream, I think
>> you'll introduce
>>> performance problems at that layer if you're sending packets out of
>> TCP order.
>>
>> With a single TCP stream that is transferring a lot of data, all
>> packets tend to be the same size - that of the MSS. My model is a lot
>> of packets, some UDP, some TCP, belonging to multiple streams.
>>
>> My implementation would place every TCP stream on a single processor,
>> but that's because my implementation is also a firewall. This won't
>> help cases where all (or most) traffic is a single TCP stream, but
>> parallelizing can help where you have multiple streams or packets
> under
>> the same SA.
>
> Yoav, might I point out that with ESP-GCM (and GMAC), you can actually
> compute things out of order.  That is, you can compute the entire
> encrypted data and ICV field assuming a sequence number of 0, and
> afterwards figure out how to adjust the ICV for the actual sequence
> number.
>
> This adjustment does involve computing H**n (where H is an internal  
> GCM
> value derived from the key, and n is the packet length in 16 byte
> increments, and the multiplications are GF(2**128) field
> multiplications).  Computing this is logarithmic time, not constant
> (unless you precompute all the possible H**n values; there's about 100
> of them for standard MTU sizes), but is certainly closer to constant
> what you're originally looking at with the standard HMAC  
> authentication.
>
> So, what's the benefit of putting up with this complexity?  Well, you
> can basically get what you want with standard (RFC-compliant)  
> protocols.
> So, you can implement what you want without asking anyone else to do
> anything (well, other than implement the GCM RFC, I suppose).  I share
> Steve's concerns about sending packets out of order (my personal worry
> would be video), but you can implement it yourself, and see in  
> practice
> if it works well.
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg