Deterministic Counter Mode with a PRF. What does evaluate at a point mean?

Question

This is from Dan Boneh's Lecture where he talks about operating a PRF (AES, DES) in Deterministic Counter Mode.

Dan Boneh says

What we could do is we could use what's called a deterministic counter mode. So in a deterministic counter mode, basically we build a stream cipher out of the block cipher. So suppose we have a PRF, F. So again you should think of AES when I say that. So AES is also a secure PRF. And what we'll do is, basically, we'll evaluate AES at the point zero, at the point one, at the point two, up to the point L. This will generate a pseudo random pad. And I will XOR that with all the message blocks and recover the ciphertext as a result. Okay, so really this is just a stream cipher that's built out of a PRF, like AES and triple DES, and it's a simple way to do encryption.

What exactly does he mean by "Evaluating at point 0, point 1" etc?

Does he mean encrypting the numbers 0, 1, 2, etc using AES?

i.e. something like

for (i = 0; i < messagelen; ++i)
    plaintext = PadToBlockLength(i);
    Output(AES-PRF(key, plaintext));

where the Output function generates one unit of the PRG with each call.

Answer 1

Let $E(k,b)$ be the AES encryption of message $b$ with the key $k$ where size of $b$ is 128-bit, the key size can be 128,192,and 256 bits.

What exactly does he mean by "Evaluating at point 0, point 1" etc

• Evaluating at point 0 : $c_0 = E(k,0)$
• Evaluating at point 1 : $c_1 =E(k,1)$
• Evaluating at point 2 : $c_2 = E(k,2)$
• and soo on
• Evaluating at point $\ell$ : $c_\ell= E(k,\ell)$

$$c_i = E(k,i)$$ and the encryption is performed as

$$C_i = c_i \oplus m[i]$$

i.e. something like

There is no padding there like the PKCS#5 etc; the input $i$ is considered as a 128-bit binary encoded representation of integer $i$, or one can think of it as a 128-bit counter. We can see it more clearly if we consider the below as hex

00000000000000000000000000000001
00000000000000000000000000000002
00000000000000000000000000000003
00000000000000000000000000000004
..
000000000000000000000000000000FF
..

What is defined here is the CTR mode of operation that is first defined for PRFs and introduced by Whitfield Diffie and Martin Hellman in 1979

• Privacy and Authentication: An Introduction to Cryptography as an invited paper on Proceedings of the IEEE, 67 (1979), pp. 397–427.

CTR turns a PRF into a stream cipher, as Snuffle turned into Salsa20 and AES into AES-CTR. Note that although not proved the AES is a candidate for a $PRP \subset PRF$. The CTR mode doesn't require the decryption of AES ( or any block cipher) and this is useful to reduce the area of the software/hardware implementations.