Re: [Cfrg] TLS PRF security proof?

[Watson Ladd <[e-mail]>]

On Wed, Jul 9, 2014 at 7:50 PM, Andy Lutomirski <[e-mail]> wrote:
> On Wed, Jul 9, 2014 at 6:52 PM, Watson Ladd <[e-mail]> wrote:
>> On Wed, Jul 9, 2014 at 10:50 AM, Andy Lutomirski <[e-mail]> wrote:
>>> On Wed, Jul 9, 2014 at 8:33 AM, Andy Lutomirski <[e-mail]> wrote:
>>>> On Wed, Jul 9, 2014 at 8:28 AM, Paul Hoffman <[e-mail]> wrote:
>>>>>
>>>>>> 2. The RFC didn't make the security properties clear to me.  For
>>>>>> example, protocols should stick nonces into the salt.  Oh, wait, they
>>>>>> shouldn't stick nonces into the salt without care.
>>>>>
>>>>> Can you justify that second sentence with anything from RFC 5869? In fact, it says the opposite:
>>>>>
>>>>>    Ideally, the salt value is a random (or pseudorandom) string of the
>>>>>    length HashLen.  Yet, even a salt value of less quality (shorter in
>>>>>    size or with limited entropy) may still make a significant
>>>>>    contribution to the security of the output keying material; designers
>>>>>    of applications are therefore encouraged to provide salt values to
>>>>>    HKDF if such values can be obtained by the application.
>>>>
>>>> Quoting from RFC 5869, section 3.4:
>>>>
>>>>    Independence is also an important aspect of the salt value provided
>>>>    to a KDF.  While there is no need to keep the salt secret, and the
>>>>    same salt value can be used with multiple IKM values, it is assumed
>>>>    that salt values are independent of the input keying material.  In
>>>>    particular, an application needs to make sure that salt values are
>>>>    not chosen or manipulated by an attacker.  As an example, consider
>>>>    the case (as in IKE) where the salt is derived from nonces supplied
>>>>    by the parties in a key exchange protocol.  Before the protocol can
>>>>    use such salt to derive keys, it needs to make sure that these nonces
>>>>    are authenticated as coming from the legitimate parties rather than
>>>>    selected by the attacker (in IKE, for example this authentication is
>>>>    an integral part of the authenticated Diffie-Hellman exchange).
>>>>
>>>
>>> I should note that this text in 3.4 smells funny to me even taken
>>> alone.  Making sure that the nonces come from legitimate parties does
>>> *not* imply that they are independent of the IKM in any sense of the
>>> word "independent" that I understand.
>>>
>>> I, and presumably protocol designers everywhere, would much prefer
>>> language that tells me "this primitive provides this security
>>> guarantee if this condition is met" where the condition is clearly
>>> specified.
>>>
>>> This is not to say that HKDF is not a perfectly good KDF, but I find
>>> the RFC 5869 language unconvincing.
>>
>> The reason the salt argument exists is because of a technicality in
>> the existence of entropy extractors:
>> they don't exist. Therefore, you need to make a randomized definition,
>> which requires a random string
>> independent of the other arguments.
>>
>> The "obvious" way to get a salt is to do a coinflip protocol, then use
>> that as the salt. (That is, commit, commit, reveal,
>> reveal, and xor the revealed strings). This produces a random string,
>> independent (well, no... the attacker could abandon
>> the protocol round rather than continue it if they don't like it) of
>> other values. (To fix this you condition on successful protocol
>> runs, and do some math)
>
> Would it be good enough to do:
>
> A -> B: commit
> B -> A: nonce
> A -> B: reveal
>
> Not that any protocol designer is likely to do this, but it's less
> unpalatable than adding the extra round.
>
> And does using a salt as suggested in the RFC actually reduce provable security?

No, not using a salt forces stronger assumptions on the hash function.
In some cases these assumptions
are so strong they are not satisfied by any hash function: in that
case you prove the protocol secure in the ROM.

Doing anything in the standard model, with standard assumptions, is
hard. In practice the ROM is good enough for protocols.

Honestly, I would be shocked if HKDF turned out to not get the job
done in any reasonable protocol.

>
>>
>> In the ROM none of this matters, but interestingly the eprint paper
>> gives a natural protocol secure in the ROM, but insecure
>> because a natural choice of hash function admits a length extension attack.
>
> Does that mean that HKDF-SHA-bits is not secure in the ROM?

A protocol where H(stuff) is revealed, and H(stuff | junk) is used as
a key, falls apart for hashes admitting length extension,
(like every MD style hash) but is secure in the ROM. SHAxxx is not a
random oracle! No deterministic function ever can be
a random oracle, but SHAxxx is particularly easy to distinguish as it
has a length extension property.

>
>>
>> Without the salt argument the result is simply H(stuff), which is
>> supposed to be fine for any reasonable choice of H.
>
> If stuff is (party A data | party B data) and party A gets to choose
> all of its data offline, then this isn't so appealing for common
> choices of H.

Why not? Is there a weakness of SHA256 I'm unaware of? If you need
signatures, you need collision resistant hash functions.
All uses of SHA1 and MD5 need to be ended ASAP: Microsoft has already
begun this process.

Sincerely,
Watson Ladd
>
> --Andy



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin