Re: [Cfrg] TLS PRF security proof?

Watson Ladd <watsonbladd@gmail.com> Fri, 11 July 2014 14:48 UTC

Return-Path: <watsonbladd@gmail.com>
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 0D2C61B2B58 for <cfrg@ietfa.amsl.com>; Fri, 11 Jul 2014 07:48:24 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, 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 L3qONXUZFFcm for <cfrg@ietfa.amsl.com>; Fri, 11 Jul 2014 07:48:18 -0700 (PDT)
Received: from mail-we0-x234.google.com (mail-we0-x234.google.com [IPv6:2a00:1450:400c:c03::234]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 3755A1B2908 for <cfrg@irtf.org>; Fri, 11 Jul 2014 07:48:14 -0700 (PDT)
Received: by mail-we0-f180.google.com with SMTP id k48so279425wev.11 for <cfrg@irtf.org>; Fri, 11 Jul 2014 07:48:10 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=TrS3rYMr9FyziYrG9oF8G6HWJHMwrim6gw+uVvSgsEE=; b=H9h5FH284Arfe/Fh4+rA2a8LY2oZiD9dpUXs5nMuMTPzCcwljVJpi88hApKvj0a8w2 keViC66pdtR9FQJSFkc2QDfLBCsg49rVLJvEde+6c8pfBomIzLHTFFhmagrd1tN01CyM gH06XmM+qa5KGKRkijK7HfFe6F3BzFXsSi8nwRF+KJh/AsPMSNEcwKB24H/NsVsV/o4K q3s5BIkzRqzkgSYxKHc0jKVcAD8DJmDJKs5qxyCTP7MTmzPzkXE/rEbEEZGXWZ7lM3+q YEGksaMu1gfNyU2O46OtMf5UNcM6VqMTxgjjEcqJxk79p7fHSDZQc/D3XNhh9g89oxiT LcGQ==
MIME-Version: 1.0
X-Received: by 10.180.198.244 with SMTP id jf20mr5716291wic.40.1405090090047; Fri, 11 Jul 2014 07:48:10 -0700 (PDT)
Received: by 10.194.21.69 with HTTP; Fri, 11 Jul 2014 07:48:09 -0700 (PDT)
In-Reply-To: <53BE761A.9000709@rwth-aachen.de>
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> <CALCETrWo+gvVkL8P4Lw-ZtuTfu=L_q5+h9zcdpPyZvB5-FE0vg@mail.gmail.com> <CACsn0cmL6DcbynZkDOZST7-Voq+n217awx737dv7oy5VYWFDyg@mail.gmail.com> <CALCETrX5gJdQZATrzOrXtw_M4hc320yUi_HJPuexJORUuUw07g@mail.gmail.com> <53BE761A.9000709@rwth-aachen.de>
Date: Fri, 11 Jul 2014 07:48:09 -0700
Message-ID: <CACsn0ckL1UXivgaMh3JLMzh9oX8RjouUVyTKyx_Oq3iUy-p2bA@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Jakob Breier <Jakob.Breier@rwth-aachen.de>
Content-Type: text/plain; charset="UTF-8"
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/ay4nvBDwKwAmcEszDhj9_czvPfU
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: Fri, 11 Jul 2014 14:48:24 -0000

On Thu, Jul 10, 2014 at 4:16 AM, Jakob Breier
<Jakob.Breier@rwth-aachen.de> wrote:
> Hi,
>
>
> On 10.07.2014 05:16, Andy Lutomirski wrote:
>>
>> On Wed, Jul 9, 2014 at 8:05 PM, Watson Ladd <watsonbladd@gmail.com> wrote:
>>>
>>> On Wed, Jul 9, 2014 at 7:50 PM, Andy Lutomirski <luto@amacapital.net>
>>> wrote:
>>>>
>>>> On Wed, Jul 9, 2014 at 6:52 PM, Watson Ladd <watsonbladd@gmail.com>
>>>> wrote:
>>>>
>>>>> 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.
>>
>> Suppose that party A is malicious and they can find "party A data 1"
>> and "party A data 2" that collide.  I can imagine protocols in which
>> this violates one of the assumptions of the protocol.
>>
>> If you allow party A to spend an extremely long time precomputing
>> something *before starting the protocol*, I'd like the protocol to
>> remain reasonably secure.  Hashes with unnecessarily small internal
>> state violate this.
>
>
> If internal state size is your problem you can always use Sha512 or Sha3-512
> for an intended collision resistance of 256bit.
>
> But I find your argument much more compelling in the context of
> deteriorating hash functions, like MD5. Of course you wouldn't use MD5 for
> new protocols, nonetheless it provides a nice case study for how the Sha2
> and Sha3 family might break down with future cryptanalysis. Specifically
> while MD5 is no longer collision resistant, it is still preimage resistant
> and target collision resistant / UOWHF (in the sense that the random value
> is prefixed to the message).
>
>
> On 09.07.2014 17:28, Paul Hoffman wrote:
>>
>> On Jul 9, 2014, at 8:18 AM, Andy Lutomirski<luto@amacapital.net>  wrote:
>>
>>
>>> >I can't speak for the TLS WG, but from my own perspective, I have
>>> >three problems with HDKF:
>>> >
>>> >1. HKDF is parametrized by a hash.  What hash should people use?
>>
>> Any one that has no known weakening of preimage resistance. That is:
>> nearly any of them.
>
>
> Which brings me back to RFC 5869 in the use case of PRFs for protocols like
> TLS. If you want to assure your handshake was not tampered with, for example
> in a downgrade attack, and then put the whole handshake into the PRF/KDF (in
> addition to the Diffi-Hellman result or some other secret) you will at least
> need collision resistance of the KDF. HKDF was not analyzed under this
> setting (as far as I can tell from Definition 7 of the accompanying paper)
> and the explanations in the RFC do not help you decide with which hash
> functions it is secure then.

See "Dr. Strangelove, or how I learned to stop worrying and love the ROM".

The extract-hash-expand composition works. but it requires a source of
randomness (possibly public)
independent from  the data exchanged if you want it to work with
assumptions that aren't extremely hard.
Getting such data is impossible: you need to do a subtle calculation
of the gap between independence and
non-independence induced by the source in the security proof. It's a
very tricky thing to get right.

However, the protocol failures we've seen in the past were easily
discoverable in the ROM: they don't rely
on subtleties of hash functions. Furthermore, signatures == collision
independent hash functions. (I know the
<-, but maybe -> is more complicated: it might be just conjectural. At
least with ECDSA this is ==).

Real-world hash functions are stronger than most of our assumptions
about them, and weaker than the assumptions
that we can get away with in practice.

>
> It would be nice to only rely on target collision resistance and preimage
> resistance instead of full collision resistance of the hash function, and
> for right choices of the salt this would be possible for HKDF, too. For
> example if after the handshake an additional random from each of the parties
> is exchanged and the concatenation is used as the salt. I don't see how it
> would be feasible without at least one further message transfer, though, so
> it it's likely not worth the additional costs.

That one isn't independent of the rest of the protocol... Independance
is really hard.

The problem is that in the standard model life is very complicated:
it's not clear to me that just using HKDF is enough.
(In fact it isn't: you need additional analysis). We can't even make
secure protocols in the ROM in the IETF: while it would
be amusing to watch the TLS WG try to make a secure key agreement
protocol, it's probably a waste of time compared to
getting things right in the ROM.

Sincerely,
Watson Ladd
>
> Regards,
> Jakob Breier