Re: [Cfrg] TLS PRF security proof?

Andy Lutomirski <luto@amacapital.net> Thu, 10 July 2014 02:51 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 [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id B67D51A0252 for <cfrg@ietfa.amsl.com>; Wed, 9 Jul 2014 19:51:02 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.979
X-Spam-Level:
X-Spam-Status: No, score=-1.979 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FM_FORGED_GMAIL=0.622, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id B6HGkEyhT00k for <cfrg@ietfa.amsl.com>; Wed, 9 Jul 2014 19:51:01 -0700 (PDT)
Received: from mail-la0-f42.google.com (mail-la0-f42.google.com [209.85.215.42]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id CE2D01A0242 for <cfrg@irtf.org>; Wed, 9 Jul 2014 19:51:00 -0700 (PDT)
Received: by mail-la0-f42.google.com with SMTP id pn19so5684714lab.1 for <cfrg@irtf.org>; Wed, 09 Jul 2014 19:50:58 -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:in-reply-to:references:from:date :message-id:subject:to:cc:content-type; bh=NWg9b+Qcqtc2UfUF7HgWgX30ejVGjUR24gcgHUfpLBA=; b=dd5UoB+Kzvms1MKXtEihQIIMm+DPIYVXMRwBUX8HDbsTr9YmWUi+dhryQRV0N5lFh/ +fS8oxIELxWHKFs5+0ohX6QXvGDYHzqm707H9fbuQU6+Z4XiWyABB6AWic6vaKQKIDy1 arGOP36EzkyoU/V4hI7FZr5wSJrFHIBK1U7qLMay4+sgTygRsWm2RIzeZiTB6wjHSw3j zsFGE8gal5qpWodmSaE0b/JS0ChBrLQPgSq7/P992xJHqFpBhAPlwJLduFw2IwIou7Qu 2V1RrknuaAWwKRe+Y3WP/qdug0wjb7GixpQmAczXDdrHeGZBI6kfvSD3Ls/mAemw0G0R d2aA==
X-Gm-Message-State: ALoCoQmQKfzGHuOsVZbhgQCuEb3hsQ9HrgABbbXH5RLR2on7rdLg44GCVP4+oqQVys2T1CK3QbDs
X-Received: by 10.112.147.233 with SMTP id tn9mr667165lbb.17.1404960658616; Wed, 09 Jul 2014 19:50:58 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.152.108.130 with HTTP; Wed, 9 Jul 2014 19:50:38 -0700 (PDT)
In-Reply-To: <CACsn0c=9PuGD8p0hM6LUJKFMN_eP=UtGQN38y6DW9rsQsy1PLQ@mail.gmail.com>
References: <20140709125829.22319253.16811.16396@certicom.com> <CALCETrVG9Ltf=9x64mOScorLCUPZNtr1XF6rkfpgzT2GDiwi+g@mail.gmail.com> <6A60ED12-70B4-4CBF-B31E-3D5DDA7DC7EA@vpnc.org> <CALCETrXMZZVbF3tzZm0PfuKQ0h8mUoj7XcWgcJMNMgTuEp1+dg@mail.gmail.com> <CALCETrW7JUbJTJAY3UWf6EpXWc5ij+xy3fzWXE8+-xtpsLG7CQ@mail.gmail.com> <CACsn0c=9PuGD8p0hM6LUJKFMN_eP=UtGQN38y6DW9rsQsy1PLQ@mail.gmail.com>
From: Andy Lutomirski <luto@amacapital.net>
Date: Wed, 09 Jul 2014 19:50:38 -0700
Message-ID: <CALCETrWo+gvVkL8P4Lw-ZtuTfu=L_q5+h9zcdpPyZvB5-FE0vg@mail.gmail.com>
To: Watson Ladd <watsonbladd@gmail.com>
Content-Type: text/plain; charset="UTF-8"
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/TutsGcj5t9wrw4rBMTuTjvLPS6A
Cc: "cfrg@irtf.org" <cfrg@irtf.org>, Paul Hoffman <paul.hoffman@vpnc.org>
Subject: Re: [Cfrg] TLS PRF security proof?
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: Thu, 10 Jul 2014 02:51:02 -0000

On Wed, Jul 9, 2014 at 6:52 PM, Watson Ladd <watsonbladd@gmail.com> wrote:
> On Wed, Jul 9, 2014 at 10:50 AM, Andy Lutomirski <luto@amacapital.net> wrote:
>> On Wed, Jul 9, 2014 at 8:33 AM, Andy Lutomirski <luto@amacapital.net> wrote:
>>> On Wed, Jul 9, 2014 at 8:28 AM, Paul Hoffman <paul.hoffman@vpnc.org> 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?

>
> 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?

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

--Andy