# How can one parallelize tasks in CTR-AES for maximum performance?

From what I have read it seems like one of the purported benefits of using CTR mode AES, is that it can be parallelized to a greater degree, or maybe more easily than the other block cipher modes, leading to performance gains?

In NIST SP800-38A §6.5 , it says:

In both CTR encryption and CTR decryption, the forward cipher functions can be performed in parallel...

And this answer to “Decryption a chunk of file with AES”, if I understand correctly, suggests that basically you have one task do $$O_j=CIPH_K(T_j) \text{ for } j=1,2...\frac{n}{2}$$ with another task doing $$O_j=CIPH_K(T_j) \text{ for } j=\frac{n}{2},\frac{n}{2}+1...n$$ in parallel.

Is this what NIST SP800-38A, was referring to, something along these lines?
Or are there more or better ways to parallelize things?

-

Generally, it depends on the architecture.

If you have $n$ processors available, the obvious way to parallelize CTR mode encryption is to distribute each chunk of $n$ consecutive blocks among the processors, so that processor $0 \le i < n$ computes:

$$C_j = E_K(c_j) \oplus P_j, \quad j = i + kn, k = 0,1,2,\dotsc$$

where $c_j$ is the $j$-th counter value, $P_j$ and $C_j$ are the $j$-th plaintext and ciphertext blocks, $E_K(\cdot)$ denotes block cipher encryption with the key $K$, and $\oplus$ denotes XOR. Of course, as CTR decryption is identical to encryption, the same scheme can be used for both. When encrypting data in RAM, it is also generally most efficient to do the encryption in place, with the output overwriting the input.

This basic parallelization scheme makes most sense if the processors are accessing the memory via a shared cache, or if they're dedicated hardware units that access shared memory only via a controller unit. (In the latter case, it may also make sense for the processors to only handle the keystream generation, and leave the relatively trivial XOR operation to the controller.)

If the processors each have a local cache, it may be more efficient to split the ciphertext into longer chunks, of a suitable size to fit into this cache, and have each processor encrypt one chunk at a time. This can be particularly effective if the bus width / optimal transfer burst size between the cache and the main memory storing the plaintext / ciphertext is longer than one cipher block. Again, if the memory controller is smart enough to perform the XOR operation directly, without having to first transfer the plaintext to the processors and the ciphertext back, this is an optimization worth taking.

On general-purpose processors that support efficient SIMD operations, having each processor encrypt several blocks at can also enable the use of bit-slicing techniques in the block cipher encryption process. However, this does not necessarily require the blocks assigned to a single processor to be consecutive, merely that they're processed more than one at a time.

Also, CTR mode allows the keystream $E_K(c_j)$ to be computed in advance, even before the plaintext / ciphertext input is known. In some circumstances, such as when dealing with very bursty data transfers, buffering the keystream in advance may be useful.

Anyway, the nice thing about CTR mode is that the result of the encryption process is exactly the same regardless of what order it's done in, or how many processors it's distributed over. In particular, this means that the two ends of an encrypted channel can each select the parallelization scheme that is most suited to them, even if their computational capabilities are wildly different.

-

From the diagram on CTR mode

you can notice that there are no dependencies between any of the phases of the pipeline. If you have more than one block-size worth of data, you can process each block-size chunk completely independently of the others by calculating $\mathrm{ciphertext}_i = E(\mathrm{key}, \mathrm{nonce} \, || \, \mathrm{counter}_i) \oplus \mathrm{plaintext}_i$.

-
Okay i see. In $\mathrm{ciphertext}_i = E(\mathrm{nonce} \, || \, \mathrm{counter}_i) \oplus \mathrm{plaintext}_i$, does $||$ just mean concatenation or ? –  guydudebro May 31 at 0:47
$\vert\vert$ is concatenation, $\oplus$ is XOR. –  Stephen Touset May 31 at 19:42