Re: [Cfrg] Question about the order of hashing

Hugo Krawczyk <hugo@ee.technion.ac.il> Thu, 05 January 2012 21:11 UTC

Return-Path: <hugokraw@gmail.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 9162121F88B1 for <cfrg@ietfa.amsl.com>; Thu, 5 Jan 2012 13:11:51 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.625
X-Spam-Level:
X-Spam-Status: No, score=-1.625 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, FM_FORGED_GMAIL=0.622, HTML_MESSAGE=0.001, J_CHICKENPOX_41=0.6, RCVD_IN_DNSWL_LOW=-1, 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 mOpCrDfhu19s for <cfrg@ietfa.amsl.com>; Thu, 5 Jan 2012 13:11:50 -0800 (PST)
Received: from mail-tul01m020-f182.google.com (mail-tul01m020-f182.google.com [209.85.214.182]) by ietfa.amsl.com (Postfix) with ESMTP id A127321F88A7 for <cfrg@irtf.org>; Thu, 5 Jan 2012 13:11:50 -0800 (PST)
Received: by obbwd18 with SMTP id wd18so1559367obb.13 for <cfrg@irtf.org>; Thu, 05 Jan 2012 13:11:50 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:sender:in-reply-to:references:from:date :x-google-sender-auth:message-id:subject:to:cc:content-type; bh=h05Yjy796ZQqo8iQqd2U73VBi/fwkcxv2lPaaN4d0og=; b=rOCGFWRG41eygaxnqA+r52DwTl9VsN5GIWtlZV+YcSfHRcWv9JshXGlR5S98eoZ51n C/KrlgDtdwfUKN7A0Dv40iT4LaQSZUwSuRqk9pAG2JYIeYtBMUaM9w3yfy8AvduZjPxp 6AILEk+9Y5DU9SBr4Xhjr0146XNWdckP7QRdk=
Received: by 10.182.159.70 with SMTP id xa6mr2839954obb.1.1325797910117; Thu, 05 Jan 2012 13:11:50 -0800 (PST)
MIME-Version: 1.0
Sender: hugokraw@gmail.com
Received: by 10.182.121.103 with HTTP; Thu, 5 Jan 2012 13:11:29 -0800 (PST)
In-Reply-To: <5E6BDD30-3EB8-4FBA-826E-4A44DED36283@checkpoint.com>
References: <5E6BDD30-3EB8-4FBA-826E-4A44DED36283@checkpoint.com>
From: Hugo Krawczyk <hugo@ee.technion.ac.il>
Date: Thu, 5 Jan 2012 16:11:29 -0500
X-Google-Sender-Auth: 3uPWevukPyt8n9Ll233KqgX_YZ4
Message-ID: <CADi0yUP4yjRa7ZxMyQasVdJpq0_+vjFtXZF+qfXwwfM45_ee1g@mail.gmail.com>
To: Yoav Nir <ynir@checkpoint.com>
Content-Type: multipart/alternative; boundary=14dae939977179fc7a04b5ce611e
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 21:11:51 -0000

The security properties of HMAC do not change by the order of the data
items. However, the change of order may affect the security of a
cryptographic protocol that uses HMAC. Particularly, ambiguous parsing as
in Thomas example can break a protocol. Or think of a DH key exchange that
is authenticated with a preshared key K by transmitting HMAC(K, g^a||g^b)
from A to B and HMAC(K, g^b||g^a) from B to A (and assume the parties check
that g^a \noteq g^b to prevent reflection attacks). Now, if you change the
order of arguments in the B to A flow, you create a reflection attack
opportunity that did not exist in the original protocol.

I would assume that if the only thing that you change is the position of
the sequence number and in the new ordering the position and length of this
number is uniquely determined (e.g., last 4 bytes of the message) then you
should be ok, but it is just an assumption. You should look more carefully
at your specific protocol/usage.

Hugo


On Thu, Jan 5, 2012 at 2:29 AM, Yoav Nir <ynir@checkpoint.com> 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.
>
> Thanks
>
> Yoav
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
>