Re: [Cfrg] Question about the order of hashing

Yoav Nir <ynir@checkpoint.com> Thu, 05 January 2012 09:19 UTC

Return-Path: <ynir@checkpoint.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 C5CCC21F8643 for <cfrg@ietfa.amsl.com>; Thu, 5 Jan 2012 01:19:22 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -9.802
X-Spam-Level:
X-Spam-Status: No, score=-9.802 tagged_above=-999 required=5 tests=[AWL=-0.554, BAYES_00=-2.599, J_CHICKENPOX_41=0.6, RCVD_IN_DNSWL_HI=-8, SARE_OBFU_ALL=0.751]
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 WNlm42iYTtKS for <cfrg@ietfa.amsl.com>; Thu, 5 Jan 2012 01:19:22 -0800 (PST)
Received: from michael.checkpoint.com (smtp.checkpoint.com [194.29.34.68]) by ietfa.amsl.com (Postfix) with ESMTP id B951221F860B for <cfrg@irtf.org>; Thu, 5 Jan 2012 01:19:21 -0800 (PST)
X-CheckPoint: {4F0568D5-1-1B221DC2-1FFFF}
Received: from il-ex01.ad.checkpoint.com (il-ex01.ad.checkpoint.com [194.29.34.26]) by michael.checkpoint.com (8.13.8/8.13.8) with ESMTP id q059JC1c001079; Thu, 5 Jan 2012 11:19:12 +0200
Received: from il-ex01.ad.checkpoint.com ([126.0.0.2]) by il-ex01.ad.checkpoint.com ([126.0.0.2]) with mapi; Thu, 5 Jan 2012 11:19:12 +0200
From: Yoav Nir <ynir@checkpoint.com>
To: Steven Bellovin <smb@cs.columbia.edu>
Date: Thu, 5 Jan 2012 11:19:15 +0200
Thread-Topic: [Cfrg] Question about the order of hashing
Thread-Index: AczLixWdboFGgb0mTuaGb+2KYIDM+A==
Message-ID: <5C0E5BE9-FE11-46BD-9D91-08FBE0299F10@checkpoint.com>
References: <5E6BDD30-3EB8-4FBA-826E-4A44DED36283@checkpoint.com> <49D24499-1C16-44C4-84C2-36F94F95235C@cs.columbia.edu>
In-Reply-To: <49D24499-1C16-44C4-84C2-36F94F95235C@cs.columbia.edu>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
acceptlanguage: en-US
x-kse-antivirus-interceptor-info: scan successful
x-kse-antivirus-info: Clean
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Cc: "cfrg@irtf.org" <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 09:19:22 -0000

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.