Subject: [Cfrg] TLS PRF security proof?

From: Dan Brown <[email-masked]>
Date: Tue, 8 Jul 2014 19:19:34 +0000

Dear CFRG list,

Is there a published security proof for the current TLS PRF in the draft TLS
1.3?  

Specifically, I refer to the current TLS PRF, which I try to paraphrase here
as:

PRF_k ( m ) = HMAC_k( HMAC_k(m) | m) | HMAC_k ( HMAC_k^2(m) | m) | HMAC_k (
HMAC_k^3(m) | m) | .

where the underscores are used to indicate a secret key input to a function,
and the caret indicates repeated application of a function, and | indicates
string concatenation, and the ellipsis (.) indicates to repeat (in the
obvious manner by more iterations) and to truncate as needed.  So, my
question is if the security of PRF_k has been proved assuming some security
property of HMAC_k.  So far, I've scanned:

http://eprint.iacr.org/2014/182

http://eprint.iacr.org/2013/339

http://eprint.iacr.org/2013/367

These three reports all seem to prove some security for TLS assuming the PRF
has some security property, rather than prove the security of the TLS PRF
(but apologies if I am mistaken).

The 3 reports indicate the kind of security that PRF_k ought to have for its
role in TLS.  Naively, I'd note that the input m is public, and in some
early stages of the handshake, m is subject to the modification by the
adversary, but the output is usually kept secret, and needs to be kept
secret, so it looks as though TLS PRF benefits from at least the standard
PRF security properties.  

Regardless of provable security, I wonder why the TLS PRF applies a MAC to
an iterated MAC tag, rather than say a counter.  Anyway, it reminds me of
some kind of chaining feedback mode, like CBC where blocks encrypted depend
on the key, so key-dependent input is not a real concern. Even so, oughtn't
there be there some simpler design, more like a counter mode, that avoids
any key-dependent inputs?  

I would imagine that the PRF security of TLS PRF could be proved secure in
the random oracle model, and perhaps if HMAC_k is some kind of secure PRF.
I do not see how one could prove the PRF security of PRF_k using only the
assumption that HMAC_k is a secure MAC, just because a secure MAC might be
biased.

If I had to whip up a PRF security proof, it would go something like this:
suppose adversary A can distinguish oracle access to function PRF_k from a
random function BIGRAND (with similar domain and range).  Then build an
adversary B that can distinguish between oracle access to function HMAC_k
and a random function SMALLRAND (with same domain and range) as follows.  B
simulates the PRF_k oracle for A by calling her oracle for HMAC_k, per the
definition of PRF_k.  To finish the proof, we just need to be sure that
using SMALLRAND instead of HMAC_k in the PRF_k construction yields something
indistinguishable from BIGRAND.  To make proving that easier, we could note
that m is almost a fixed length, and the output of F is fairly short.
(Under arbitrary length outputs, PRF_k built from SMALLRAND would likely
start enter a periodic cycle at around block 2^128, unlike BIGRAND, but we
can still have computational indistinguishability because it would take
2^128 steps just to scan the output of arbitrarily long PRF_k to detect the
cycling pattern.)

Best regards,

Daniel Brown

Research In Motion Limited

---

From: Andy Lutomirski <[email-masked]>
Date: Tue, 8 Jul 2014 12:24:05 -0700

On Tue, Jul 8, 2014 at 12:19 PM, Dan Brown <[email-masked]> wrote:
>
> Dear CFRG list,
>
>
>
> Is there a published security proof for the current TLS PRF in the draft TLS 1.3?
>

Would it be useful if CFRG were to publish a recommended PRF?  Perhaps
something using a modern hash function combiner using (HMAC-)SHA-512
and either SHA-3 or something from the Salsa/ChaCha family as the
base?

--Andy

---

From: "Igoe, Kevin M." <[email-masked]>
Date: Tue, 8 Jul 2014 19:56:37 +0000

Definitely useful in the long run, but in the short run no one is
going to modify more than a small fraction of the existing TLS
deployments.  Perhaps in TLS 1.3.

Any chance of cooking up a security proof for the existing PRF? I'm
not optimistic since HMAC_k is a coalescent function => the HMAC_k^t(m) 
eventually starts to cycle. Typically the time to fall onto the cycle
and the length of the cycle are both about sqrt(N), but the usual random
map model gives a quantifiable probability of falling onto a far shorter
is a far shorter time.  A low enough probability to be of little practical
concern, but still a possible source of problems.

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Andy Lutomirski
> Sent: Tuesday, July 08, 2014 3:24 PM
> To: Dan Brown
> Cc: [email-masked]
> Subject: Re: [Cfrg] TLS PRF security proof?
> 
> and either SHA-3 or something from the Salsa/ChaCha family as the base?
> 
> --Andy
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: "Dan Harkins" <[email-masked]>
Date: Tue, 8 Jul 2014 15:12:22 -0700 (PDT)

> and either SHA-3 or something from the Salsa/ChaCha family as the

  What about RFC 5869? http://eprint.iacr.org/2010/264 describes the
design rationale which is more than what TLS PRF has (which, to me,
seems a bit ad hoc).

  regards,

  Dan.

---

From: "Paterson, Kenny" <[email-masked]>
Date: Wed, 9 Jul 2014 09:03:39 +0000

Andy,

>and either SHA-3 or something from the Salsa/ChaCha family as the

I think this could be a useful activity for CFRG to take on, given the
widespread use of PRFs in IETF protocols - having a reference algorithm
for future protocol designers to use would be a good thing.

So I think the CFRG chairs would want to consider sponsoring any serious
effort in this direction.

On the other hand, CFRG is not really in the business of developing new
crypto from scratch (at least, that's my reading of the CFRG charter).

My first question, then, would be: are there any volunteers on the list
who are willing to dedicate some cycles to assessing the current state of
the art, as represented by existing RFCs and standards?

What is already out there that we could conveniently borrow from? Does
HMAC with a strong hash function already do the job, for example?

Cheers

Kenny

---

From: Dan Brown <[email-masked]>
Date: Wed, 9 Jul 2014 15:27:26 +0000

Oops, I see now that the the TLS PRF is based on the key expansion phase of
HKDF!  This is called PRF* in the Krawczyk's eprint.  Maybe the TLS draft
should cite the HKDF paper.

Anyway, Section 7 of the HKDF eprint says the "feedback mode" design of PRF*
is heuristic, and is more conservative than a simpler counter mode.

So, despite my mix-up, my questions still stand: Is PRF* proven secure? How
failsafe is it?

> From: Dan Harkins [mailto:[email-masked]]
> Sent: Tuesday, July 08, 2014 6:12 PM
> To: Andy Lutomirski
> Cc: Dan Brown; [email-masked]
design
> rationale which is more than what TLS PRF has (which, to me, seems a bit
ad
> hoc).