[Cfrg] TLS PRF security proof?

[Dan Brown <[e-mail]>]

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