[Cfrg] Hash function combiners for session key derivation?

[Andy Lutomirski <[e-mail]>]

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
adversary.

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
everything.

[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

-- 
Andy Lutomirski
AMA Capital Management, LLC