Re: [Cfrg] Hash function combiners for session key derivation?

[Andy Lutomirski <[e-mail]>]

On Wed, Sep 3, 2014 at 4:04 AM, Anja Lehmann <[e-mail]> wrote:
> Dear Andy,
>
>
>> 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.
>
> Maybe this is a stupid question from a theoretician ... but what is so
> impractical about pairwise independent functions? They can e.g. be realized
> as f(x) = ax + b for random a,b \in {0,1}^n.
>

For the keyed case, this may not be a problem.  For the unkeyed case,
where do the random numbers come from?  The TLS WG or CFRG or someone
could say "a = some digits of pi and b = some digits of e", but then
people will wonder whether that was an acceptable choice.

> I guess the more limiting factor might be that Comb_4P&OW and
> Comb_6P require a pairwise independent *permutation*, which in turn fixes
> the input length of the combiner. This does not hold for Comb_4P&IRO though.
>
>
>> 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_1.
>
>> 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.
>>
>> 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*.
>
> In fact, in the paper it is assumed that H_0 and H_1 are independent
> functions. The construction of Comb_4P is basically a Feistel-network using
> H_0(m) \xor H_1(m) as round function. So clearly, if one sets H_0 = H_1,
> this construction is not a PRF (even if both functions are secure PRFs)
>
> From a provable security point of view, it is actually quite cruial that the
> functions are keyed with independent keys, as otherwise the security
> reduction would not work. I would assume that this is a rather general
> problem for such combiners, as in the proof one usually reduces the security
> of the combiner to the security of *one* of the hash functions. (Which
> proves that the combiner is secure as long as at least one of the underlying
> functions is secure.) Thereby, the reduction has black-box access to the
> assumed secure hash function and simulates the other function. However,
> having only black-box access means that the reduction does not know the
> secret key and thus, it can not ensure that both functions are invoked with
> the same key. That is, if the construction actually uses the same key for
> both functions, we can not simulate that case in the proof. So, assuming
> independent keys might be an inherent constraint for those combiners.
>

Hmm.  I imagined a hash combiner that was secure in a somewhat
different model.  Fix H_0 as a secure hash (for whatever notion of
security you're checking).  Let the adversary choose H_1, where H_1
has oracle access to H_0.  Then let the adversary try to break the
result (without direct access to the queries made to H_0 or H_1).  For
this purpose, I'm treating the key, if any, as a parameter to H_0 and
H_1.  One could debate whether, for target collision resistance, the
adversary should be allowed to know the target when defining H_1.

In the independently keyed case, I *think* Comb_4P, etc are okay in
this model.  In the unkeyed case, they're not.  I don't know whether
combiners secure against this sort of adversary even exist.

> However, in the context of TLS and using a hash combiner for key-derivation
> ... aren't you in the nice setting that there is already a pre-master secret
> that is assumed to be random? So simply splitting that into two halves would
> work to get two independent keys, right?

Hmm, interesting.

In TLS (to a very rough approximation), a DH exchange generates a key.
Somehow, the final session key (master secret) needs to be a function
of both the DH key and the (variable-length) transcript of messages
sent.  The really critical property, which is, I think, worthy of
using a hash combiner, is that no one should be able to generate a
different transcript that results in the same session key, since, if
that can happen, then a MITM could possible trick people into using a
weak hash function by changing the part of the transcript that's
responsible for choosing the has function.

This could be made secure (I think) by doing two DH exchanges to get
two independent keys.  But maybe it could also work well enough by
splitting the DH key into two halves.  Hmm.

>
> Also (even though I of course like the concept of multi-property hash
> combiners) if the goal is to come up with a combiner that is secure for a
> particular and well-defined purpose (like being a good PRF), and the
> combiner isn't used anywhere else, one could of course also use a
> construction that is tailored for that purpose.
>
> The goal of the combiners in [1] was to preserve several properties
> simultaneously, such that the same construction can be used in various
> applications. So all combiners in that paper are robust e.g., for
> collision-resistance, pseudorandomness and being a secure MAC. But again, if
> only a single property is needed then a dedicated combiner for that property
> is usually more efficient.
>
> We actually provided a security proof for the key-derivation hash combiners
> used in TLS 1.0/1.1, and also made some suggestions how one can improve the
> combiners security (and efficiency) in [2]

I'll read that.  Thanks.

--Andy

>
> [1] Marc Fischlin, Anja Lehmann, and Krzysztof Pietrzak. "Robust
> multi-property combiners for hash functions revisited." ICALP 2008.
> pp.655-666.
>
> [2] Marc Fischlin, Anja Lehmann, Daniel Wagner: Hash Function Combiners in
> TLS and SSL. CT-RSA 2010: 268-283
>
> Best regards,
> Anja
>
> --
> Dr. Anja Lehmann
> IBM Research Zurich
>
> www.zurich.ibm.com/~anj
> tel: [phone]
> fax: [phone]
>



-- 
Andy Lutomirski
AMA Capital Management, LLC