# Does CTR mode yield a PRF?

Can the keystream generated by CTR mode be considered a pseudo-random function?

I give more information. Assume $f$ is a PRF. We define a function which takes 2 inputs, the desired length, and an arbirtrary value:

$F_l(r):=f(r\cdot l \cdot 1) \cdot f(r \cdot l \cdot 2) \cdot \cdots\cdot f(r\cdot l\cdot l-1)\cdot f(r \cdot l \cdot l)$ where $\cdot$ denotes the concatenate operation.

Is $F_l$ a PRF ?

• You should really have the key in there as well. – otus Aug 29 '15 at 17:25

## 2 Answers

It is not accurate to say that the keystream from AES-CTR is a pseudorandom function. However, it is a pseudorandom generator. Furthermore, the construction that you gave is close to working but it's unclear where the key fits in. I will therefore elaborate on what we can exactly say.

Let $F$ be a pseudorandom function, and for simplicity assume that the key length, input length and output length are all the same (and of length denoted $n$). We denote by $F_k(x)$ the output of the PRF on input $x$, with key $k$. Then, we have the following two facts:

1. $G(k) = F_k(0)\cdot F_k(1) \cdot F_k(2)\cdots$ constitutes a pseudorandom generator.
2. $F'_k(x) = F_k(0 \cdot x) \cdot F_k(1 \cdot x) \cdot F_k(2 \cdot x) \cdots$ constitutes a pseudorandom function. Note that in this construction, $x$ has to be shorter than $n$ to provide "space" for the counter.

You want the first case when you want a PRG using AES. Especially when you have AES-NI this is a very fast option.

You want the second case when you want a PRF with input length $n$ and a larger output length. There are a number of ways of doing this. Another way is $F'_k(x) = G(F_k(x))$ where $G$ is any PRG.

• A PRG is not a PRF ? – Dingo13 Aug 29 '15 at 16:11
• A PRG is a pseudorandom generator. This is a completely different "creature" from a PRF. – Yehuda Lindell Aug 29 '15 at 19:39
• Considering the question currently has a construction close to your point 2. isn't the correct answer "yes". – otus Aug 30 '15 at 8:20
• @otus Hmm; changed the question. The construction there is not accurate, so there's some hesitation but I guess I can make this clear. – Yehuda Lindell Aug 30 '15 at 13:16
• It seems to me that when $k$ is random $G(k)$ is pseudo-random. For what reason $G$ is not a prf ? Thank you in advance. – Dingo13 Sep 1 '15 at 7:40

If $f$ is a block cipher, it is meant to be a PRP, not a PRF. However, the two are indistinguishable until about half the bit length, i.e. $2^{64}$ blocks for a 128-bit cipher like AES. (That's hundreds of exabytes.)

Since you consider the CTR mode as mapping a nonce to a keystream generated with that nonce, that is a pseudorandom function.

The concatenate operation you have in there is required. With addition or most other ways of combining $r$ and the block index you would get colliding inputs into the block cipher and it would no longer be PRF.

• This is incorrect. AES itself can be used as a PRF even though it's a permutation. However, with CTR mode, it no longer has input, or if you consider it with input then two applications with the same input give different output and so this isn't valid. – Yehuda Lindell Aug 26 '15 at 13:49
• @YehudaLindell, depends on what mapping you consider. I figured it was nonce -> keystream, but looking at it more closely, that's not necessarily what was meant. – otus Aug 26 '15 at 13:54
• if the CTR implementation is a black box where the input is the length of the requested output, and the box does not repeat nonces, then it could be considered a PRF up to the distinguishability limit of AES – Richie Frame Aug 26 '15 at 23:41
• Thanks for the answer and the comments. I've updated the post. The idea looks like the one proposed by Richie. – Dingo13 Aug 29 '15 at 16:04