# What might be assumed about a PRF if the key has been chosen?

The defining feature of a PRF $f:\{0,1\}^k\times\{0,1\}^s\mapsto\{0,1\}^*$ is that, if the first parameter is selected at random, it should be indistinguishable from a function $g:\{0,1\}^s\mapsto\{0,1\}^*$ selected at random.

But what if the key parameter isn't selected at random? What, more exactly, might and might not be assumed about the function $f$ in such case?

The question is motivated by the use of a configurable PRF (for both the KDF and the finished verify messages) in protocols such as TLS 1.2, and of secure resumption attacks that exploit assumptions regarding the relation between the master key and the authenticity of resumed connections.

More precisely, is it safe to prevent such secure resumption attacks, by using a hash of all handshake messages when the master key is derived?

In TLS 1.2 the master key is calculated as

  master_secret = PRF(pre_master_secret, "master secret",
ClientHello.random + ServerHello.random)
[0..47];


One suggestion that has been discussed for TLS 1.3 is to replace the concatenation of the random values with a hash of all handshake messages up to this point. The question is, would this prevent an attacker who is able to select the pre_master_secret value, from also selecting the master_secret for the two connections?

(We might assume the adversary has been able to define the cipher suite itself, including the key agreement mechanism, the hash algorithm and the PRF algorithm, and that the only thing we might assume about these algorithms is that they meet the conventional minimum security requirements for such algorithms.)

The handshake messages to be hashed include a client_hello, server_hello, server_certificate and possibly server_key_exchange and client_key_exchange. The pre_master_secret depends on information present in server_key_exchange and client_key_exchange. I.e. once these messages have been fixed, the pre_master_secret is fixed.

Now, if, for simplicity, we assume that the server_key_exchange and client_key_exchange messages are not included in the handshake hash, the security against an adversary who is able to design the PRF and select the pre_master_secret ought to be reducible to this question:

Suppose you have a function $f$ and that this function is such that, given any pair $v,s$, you might find a value $k$ such that $f(k,s) = v$; could this necessarily be turned into a distinguisher for $f$?

-
securee $\mapsto$ secure $\;$ –  Ricky Demer Mar 28 '14 at 14:51
That could not necessarily be turned into a distinguisher for $\hspace{.04 in}f$, since such an $\hspace{.04 in}f$ could be created by modifying any PRF with a large-enough key space on an exponentially-small fraction of its key space. $\hspace{.36 in}$ –  Ricky Demer Mar 28 '14 at 15:19
@RickyDemer: So the answer is "no" and "no"? –  Henrick Hellström Mar 28 '14 at 15:29
The answers to your last and your first two questions are "no". $\hspace{2.64 in}$ I don't know the answer to your other question. $\;$ –  Ricky Demer Mar 28 '14 at 15:37
I'm confused by "what might be assumed about..." -- you can of course assume anything you want. Do you mean, assuming only that $f$ is a PRF, what can we say about security if the key parameter is not chosen randomly? If so, the answer is: there are no guarantees whatsoever. There are bad cases where the function $f$ is no good at all, if the key is predictable or has low entropy. In TLS, the spec calls the function a PRF, but actually the protocol implicitly requires stronger assumptions than just that it's a PRF; it also needs to have some hash-like properties as well. –  D.W. Mar 28 '14 at 20:20