3
$\begingroup$

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 ?

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

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ A PRG is not a PRF ? $\endgroup$ – Dingo13 Aug 29 '15 at 16:11
  • $\begingroup$ A PRG is a pseudorandom generator. This is a completely different "creature" from a PRF. $\endgroup$ – Yehuda Lindell Aug 29 '15 at 19:39
  • $\begingroup$ Considering the question currently has a construction close to your point 2. isn't the correct answer "yes". $\endgroup$ – otus Aug 30 '15 at 8:20
  • $\begingroup$ @otus Hmm; changed the question. The construction there is not accurate, so there's some hesitation but I guess I can make this clear. $\endgroup$ – Yehuda Lindell Aug 30 '15 at 13:16
  • $\begingroup$ 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. $\endgroup$ – Dingo13 Sep 1 '15 at 7:40
-1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yehuda Lindell Aug 26 '15 at 13:49
  • $\begingroup$ @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. $\endgroup$ – otus Aug 26 '15 at 13:54
  • 1
    $\begingroup$ 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 $\endgroup$ – Richie Frame Aug 26 '15 at 23:41
  • $\begingroup$ Thanks for the answer and the comments. I've updated the post. The idea looks like the one proposed by Richie. $\endgroup$ – Dingo13 Aug 29 '15 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.