# 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, 2015 at 17:25

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 ? Aug 29, 2015 at 16:11
• A PRG is a pseudorandom generator. This is a completely different "creature" from a PRF. Aug 29, 2015 at 19:39
• Considering the question currently has a construction close to your point 2. isn't the correct answer "yes".
– otus
Aug 30, 2015 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. Aug 30, 2015 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. Sep 1, 2015 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. Aug 26, 2015 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, 2015 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 Aug 26, 2015 at 23:41
• Thanks for the answer and the comments. I've updated the post. The idea looks like the one proposed by Richie. Aug 29, 2015 at 16:04