The counter mode turns a block cipher into a stream cipher. The counter mode uses a nonce and a counter. The nonce is unique for each message that is encrypted. When a block is encrypted the counter is incremented by one and the nonce and counter are encrypted. The output of the encryption is then XORed with the plaintext to get the ciphertext.

Typically a random 64 bit nonce and a 64 bit counter are used. For a plaintext \(P = P_1P_2P_3\dots\) the encryption works as follows:

\[C_i = P_i \oplus E(n | i-1)\]

where \(n\) denotes the 64 bit nonce, \(i\) the number of the plaintext block that is encrypted and the pipe “|” denotes the concatenation of the nonce and counter, i.e. the nonce is stored in the upper 64 bits and the counter in the lower 64 bits or the resulting 128 bit block.

It is essential to not reuse the nonce when encrypting two message with the same key.

Let’s assume the same nonce is used to encrypt two messages \(M\) and \(M'\). Then, both messages are XORed with the same stream. Let

\[S_i = E(n|i-1)\]

be the stream used to XOR the plaintexts. The ciphertext for the two messages would be

\[\begin{split} C_i = M_i \oplus S_i \\[2ex] C'_i = M'_i \oplus S_i \end{split}\]

Now, if you XOR the ciphertexts you get

\[C_i \oplus C'_i = M_i \oplus S_i \oplus M'_i \oplus S_i = M_i \oplus M'_i\]

If, for instance, the messages are natural lanuage, recovering the messages (e.g. via statistical analysis) would be an easy task.

How much data can be encrypted with the same key?

CTR limits the size of the data that can be encrypted under the same key. Let’s consider only the counter, first. For instance, if an \(n\) bit counter is used, not more than \(2^n\) plaintext blocks must be encrypted. Otherwise the stream \(S\) that is used to XOR the plaintext repeats and the attack described above would become possible.

For instance, if \(n=64\) not more than \(2^{64}\) blocks must be encrypted. If AES is used for which the block size is 128 bit (16 byte), it would be safe to encrypt up to \(2^{64} \cdot 2^4\) byte, or in other words, \(2^{28}\) TiB. However, in reality we should stop after much less data because collisions in random nonces are likely to be happen much earlier. If we use a 64 bit counter, the nonce is a 64 bit value as well. If we create them at random we know from the birthday attack that a collision (i.e. a particular random nonce was already created) is likely to happen after \(2^{n/2}\) nonces have been created.