[Cfrg] Hash function combiners for session key derivation?

Andy Lutomirski <luto@amacapital.net> Mon, 01 September 2014 05:45 UTC

Return-Path: <luto@amacapital.net>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com []) by ietfa.amsl.com (Postfix) with ESMTP id B037D1A002D for <cfrg@ietfa.amsl.com>; Sun, 31 Aug 2014 22:45:40 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.721
X-Spam-Status: No, score=0.721 tagged_above=-999 required=5 tests=[BAYES_50=0.8, FM_FORGED_GMAIL=0.622, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id wFtIU5goUuyd for <cfrg@ietfa.amsl.com>; Sun, 31 Aug 2014 22:45:39 -0700 (PDT)
Received: from mail-la0-f44.google.com (mail-la0-f44.google.com []) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id B77881A0025 for <cfrg@irtf.org>; Sun, 31 Aug 2014 22:45:38 -0700 (PDT)
Received: by mail-la0-f44.google.com with SMTP id hz20so5494624lab.31 for <cfrg@irtf.org>; Sun, 31 Aug 2014 22:45:37 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:from:date:message-id:subject:to :content-type:content-transfer-encoding; bh=6myqB7ab7cK9n7OolqisoC8rYTFzeUHMQQZhjZ5HJ58=; b=NDGJqnTPlVrSYSAPkBkpaqg2nZoL+ewfJBAfEwxltsjs+uUPLSZafmNa5S4B9MOcqM wIMRYq2gm6FYvvINlq5OA6LfLIAELdMIlyV5u30knyUVWnRQtXEAYVeBCcqbD4SpURh2 I9WSLkiE/DhuI9kZbzcZHeIcyDhrWqD4ERGi+p+n65Mv62LWOsq0bbj9WD7FmH49c9FC 7wGIwbmrArdeGJt3q9N+vyH85DzowSaifAdpDDgHe35j3vCiVYJgO36nZLV5EmQ7AXFc g1+I0OhKux58PUiefqtW+eHStS3UqYwyXUBAA/AX4Wzphe1VMGTVNRd4PhEK9+UE6iUw x0Vw==
X-Gm-Message-State: ALoCoQmlomV+mG641VhRmVpvdi0UtjfVPqVOkPVOWIa2k3jdREil60iZXze5rWAwQ3CJjpApQdhc
X-Received: by with SMTP id mu10mr5742462lbc.81.1409550336926; Sun, 31 Aug 2014 22:45:36 -0700 (PDT)
MIME-Version: 1.0
Received: by with HTTP; Sun, 31 Aug 2014 22:45:16 -0700 (PDT)
From: Andy Lutomirski <luto@amacapital.net>
Date: Sun, 31 Aug 2014 22:45:16 -0700
Message-ID: <CALCETrVzG3MMzeQ41T9+5G4AFUNCj+ROYuhoxN4mm93LngsZPA@mail.gmail.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>, ANJ@zurich.ibm.com, Zooko Wilcox-OHearn <zooko@leastauthority.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/59ECQbGjN7RaoWdPJCUgpQSP-Y4
Subject: [Cfrg] Hash function combiners for session key derivation?
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
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: Mon, 01 Sep 2014 05:45:40 -0000

I would like to see future protocols (in particular, TLS 1.3) use an
extremely robust hash function to derive session keys.  The reason is
straightforward: if, say, TLS 1.2's "PRF" were to fail badly enough,
then any TLS 1.2-compatible protocol would be broken because it could
no longer protect against downgrade attacks.

In other words, hash function diversity has very limited value for
hash functions used to protect cryptographic handshakes.

Unfortunately, I don't know of a good option for protocols like TLS.
The state of the art appears to be the "Robust Multi-Property
Combiners" in [1].

As far as I can tell, none of the combiners in that paper would be
suitable.  The more advanced combiners (Comb_4P&OW, Comb_4P&IRO, and
Comb_6P) are impractical, because they require the use of pairwise
independent functions on the input space.

Beyond that, I think that even the simple combiner Comb_4P is broken.
For background, Comb_4P is a combiner on hash functions H_0 and H_0.
I'll use slightly different notation that the paper:

Let m be a message.  Define:

A_left = H_0(0, m) ⊕ H_1(0, m)
A_right = H_1(0, m).

B_left = A_right ⊕ H_0(1, A_left) ⊕ H_1(1, A_left)
B_right = A_left

C_left = B_right ⊕ H_0(2, B_left) ⊕ H_2(1, B_left)
C_right = B_left

Comp_4P(m) = C_left || C_right

Let's instantiate this.  Let H_1 be a perfectly secure hash function
(imagine SHA-3, perhaps).  Define H_0 maliciously: H_0 = H_1.

Following the definitions through gives C_left = B_right = A_left =
all zeros.  Instantiated like this, Comb_4P is most certainly not a
PRF in any useful sense.

What went wrong?  The paper proves that Comb_4P is a PRF if H_0 or H_1
is a PRF, but, as far as I can tell, the paper's concept of a hash
combiner being a PRF assumes that H_0 and H_1 are *independently
keyed*.  At first glance, this isn't a problem -- protocols that key
their hash functions just need to be careful to supply two independent
keys to Comb_4P rather than assuming that Comb_4P(key, message) works
the way that SHA-3(key, message) does.  Except that the usual way to
generate independent keys is to use some key expansion algorithm,
which usually requires a hash function.  Oops.

Do any of you know of a construction that can be dropped in to
existing protocols and that doesn't have problems like this?  I think
that, to be widely useful, a hash function combiner should have
variable input length, and if the input to that hash function consists
of a bunch of fields, then then combiner should have all expected
security properties despite the fact that one of those fields might be
a key, possibly with structure that could be interesting to an

Am I missing something here?  Are there well-understood hash combiners
that would work better?

For what it's worth, I think that, at least for something like TLS,
some of the combiners in [1] might be salvageable.  The idea would be
to split the client and server random values into three pieces.  CR_0
and SR_0 go into the transcript as usual.  A key is derived as
something like H_0(CR_1 || SR_1) ⊕ H_1(CR_2 || SR_2), and that key is
used to instantiate Comb_6P.  Getting the proofs to work could be a
big mess, though: any adversary knows the key, which could break

[1] Fischlin, Marc, Anja Lehmann, and Krzysztof Pietrzak. "Robust
multi-property combiners for hash functions revisited." Automata,
Languages and Programming. Springer Berlin Heidelberg, 2008. 655-666.


Andy Lutomirski
AMA Capital Management, LLC