Re: [Cfrg] TLS PRF security proof?

[Hugo Krawczyk <[e-mail]>]

Having a source of independent public randomness (a.k.a. salt) it less rare
than you seem to believe and it has benefits even if you use a beloved
random oracle (see the Photuris real-world example in page 28 of
http://eprint.iacr.org/2010/264).

Some examples of applications where salt is readily available:

- Any KE with explicit authentication (via signatures or public key
encryption like IKE) can use as salt the nonces exchanged between the
parties  (and chosen independently of other randomness used in the
protocol). It requires explicit authentication since you need to
authenticate these nonces to ensure they are not chosen by an attacker.
Since nonces are part of most KE protocols you get the salt for free.

- A DH-based public-key encryption scheme (i.e ElGamal) can publish a salt
string (certified together with the public key) for extracting a strong
encryption key from DH values.

- A physical RNG can use fixed salt to whiten possible biases of the
generator.

On the subject of trusting analysis based on random oracle. A protocol with
a formal proof in the random oracle model is much better than one without a
proof at all. And one with a proof in the standard (non-RO) model is better
than one in the ROM. I would not suggest, in general, paying a significant
performance cost to avoid ROs but if you have two schemes with comparable
performance one with RO and one without, I would favor the latter.

The case of HKDF is even simpler: you don't need to choose between two
schemes. The *same* scheme supports non-ROM cases when possible, supports
salt when available, and supports ROM (with and without salt) when
necessary.





On Fri, Jul 11, 2014 at 10:48 AM, Watson Ladd <[e-mail]> wrote:

> On Thu, Jul 10, 2014 at 4:16 AM, Jakob Breier
> <[e-mail]> wrote:
> > Hi,
> >
> >
> > On 10.07.2014 05:16, Andy Lutomirski wrote:
> >>
> >> On Wed, Jul 9, 2014 at 8:05 PM, Watson Ladd <[e-mail]>
> wrote:
> >>>
> >>> 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:
> >>>>
> >>>>> 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<[e-mail]>
>  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
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg
>