Re: [Cfrg] Question about the order of hashing

David McGrew <> Thu, 05 January 2012 18:22 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id EAF9C21F86E5 for <>; Thu, 5 Jan 2012 10:22:43 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -105.248
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 ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id y-f7obbGuHP4 for <>; Thu, 5 Jan 2012 10:22:39 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTP id 5F1F021F85A0 for <>; Thu, 5 Jan 2012 10:22:34 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple;;; 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 ([]) by with ESMTP; 05 Jan 2012 18:22:34 +0000
Received: from [] ([]) by (8.14.3/8.14.3) with ESMTP id q05IMXMr019871; Thu, 5 Jan 2012 18:22:33 GMT
Message-Id: <>
From: David McGrew <>
To: "Scott Fluhrer (sfluhrer)" <>, Yoav Nir <>
In-Reply-To: <>
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: <><> <> <>
X-Mailer: Apple Mail (2.936)
Subject: Re: [Cfrg] Question about the order of hashing
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-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 <>  
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.


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

>> -----Original Message-----
>> From: [] On Behalf
> Of
>> Yoav Nir
>> Sent: Thursday, January 05, 2012 4:19 AM
>> To: Steven Bellovin
>> Cc:
>> 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  
> 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