Re: [Cfrg] Question about the order of hashing

Thomas Pornin <pornin@bolet.org> Thu, 05 January 2012 13:09 UTC

Return-Path: <pornin@bolet.org>
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 DE1E921F8815 for <cfrg@ietfa.amsl.com>; Thu, 5 Jan 2012 05:09:02 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.248
X-Spam-Level:
X-Spam-Status: No, score=-1.248 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, J_CHICKENPOX_41=0.6, 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 f2iTB1G1knX6 for <cfrg@ietfa.amsl.com>; Thu, 5 Jan 2012 05:09:02 -0800 (PST)
Received: from arges.bolet.org (arges.bolet.org [88.191.65.205]) by ietfa.amsl.com (Postfix) with ESMTP id D0F7C21F8679 for <cfrg@irtf.org>; Thu, 5 Jan 2012 05:09:01 -0800 (PST)
Received: from [10.0.1.101] (unknown [184.163.20.48]) by arges.bolet.org (Postfix) with ESMTPSA id 600B968C090; Thu, 5 Jan 2012 14:08:32 +0100 (CET)
Mime-Version: 1.0 (Apple Message framework v1251.1)
Content-Type: text/plain; charset=us-ascii
From: Thomas Pornin <pornin@bolet.org>
In-Reply-To: <5E6BDD30-3EB8-4FBA-826E-4A44DED36283@checkpoint.com>
Date: Thu, 5 Jan 2012 08:08:31 -0500
Content-Transfer-Encoding: quoted-printable
Message-Id: <84B1FEDA-5224-4E67-BF14-6B55A9769D56@bolet.org>
References: <5E6BDD30-3EB8-4FBA-826E-4A44DED36283@checkpoint.com>
To: Yoav Nir <ynir@checkpoint.com>
X-Mailer: Apple Mail (2.1251.1)
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 13:09:03 -0000

On 2012-01-05, at 2:29 AM, Yoav Nir wrote:
> IOW, does changing HMAC(k, a||b) into HMAC(k, b||a) change the security properties.

As long as the concatenation can be unambiguously undone, the security properties are maintained.

The trouble with concatenation is that, when done carelessly, it can introduce ambiguities. For instance, if you take a protocol which concatenates the user name and his password directly, then user 'steven' with password 'cipher', and user 'steve' with password 'ncipher', end up with the same concatenation result: 'stevencipher'. That can be a problem for the security properties. In the case of users and passwords, a common solution is to add a separator character, which is forbidden in user names (hence 'steven:cipher' and 'steve:ncipher').

By swapping your 'a' and 'b', you might introduce ambiguities. For instance, suppose that 'a' is a self-terminated structure (i.e. it begins with a header which defines its length, so the end of 'a' and the start of 'b' can be reliably located within 'a||b' by looking at the first bytes), but 'b' is not. Then 'a||b' can always be split back into a single, well-defined (a,b) pair. On the other hand, 'b||a' might not be unambiguously split, so you could have distinct pairs 'b1||a1' and 'b2||a2' which both match the 'b||a' string (and yield the same MAC).

As long as you take care of that point, i.e. do not introduce the possibility of a 'stevencipher', then you can choose whichever conventional order you like, it will not impact the security of HMAC (of course, sender and receiver must both agree on the same, single, well-defined order).


	--Thomas Pornin