What is the proper way to implement AES CTR with 128 bit nonce and 64 bit counter?

Question

While encrypting AES in CTR mode, the input to the AES encryption function is the either a combination of IV + $m$ bit counter or is either $0$ IV bits with an $m$ bit counter. It is however rare to see the full usage of the input block ($128$ bits) as just a counter. Since CTR mode essentially converts a block cipher to a stream cipher, the implementer must be careful that the XOR of ciphertexts should not reveal XOR of plaintexts. For this requirement, the $(nonce, key)$ pair should be unique for each invocation. I'm particularly interested in file encryption, or a large (in size) session of encrypted communication over a network , (say file download > 64 GB).

My encryption scheme: Use a 128 bit IV to populate the initial block. For every requirement of a 16 byte keystream increment the counter and add it with the initial block populated with the IV. (EDITED)

This will be the protocol: $C_{i} = AES_{k}(IV + i) \oplus P_{i}$ where $i$ is 64 bit counter, $IV$ is $128$ bit nonce and $+$ is arithmetic addition modulo $2^{128} -1$.

• Is this secure (confidential sense)?
• Will there be collisions in the input block to the AES function since we have already populated the initial block, with random IV (Can modular addition of counter cause collision) ?
• Is this a standard way of doing AES CTR ?
• What is the proper way to check for overflow? Should I check whether initial block (treated as a big endian integer) equals to $2^{128} -1$ or only whether $i$ equals $2^{64} -1$ and then raise an exception?

Answer 1

This will be the protocol: $C_{i} = AES_{k}(IV + i) \oplus P_{i}$ where $i$ is 64 bit counter, $IV$ is $128$ bit nonce and $+$ is arithmetic addition modulo $2^{128} -1$.

Is this secure (confidential sense)?

Well, you didn't really specify the nonce to be random. If it is a serial number then it is obviously not secure at the next file uses the same block as what the other one started with.

Will there be collisions in the input block to the AES function since we have already populated the initial block, with random IV (Can modular addition of counter cause collision)?

If it is random then you don't really know what the distance is towards the next IV. If you are (rather) unlucky then it is less than $2^{64}$ and then the really big files could be in trouble as the last part of one file and the first part of another may use the same counter and thus key stream. So serial number: clearly not secure

Is this a standard way of doing AES CTR?

Generally the counter value and the nonce would use separate bits. You'd round up the number of required bits for the counter and use as many as possible for the nonce. Sometimes domain separation could also be encoded in one or more bits.

What is the proper way to check for overflow? Should I check whether initial block (treated as a big endian integer) equals to $2^{128} -1$ or only whether $i$ equals $2^{64} -1$ and then raise an exception?

In your scheme you'd not really know when the overflow happens. In the general sense you could simply test if the counter returns to zero, or calculate the amount of bytes and make sure that you keep below that value.

---

You could also derive a different key per file, then you can use all 128 bits for the counter.

Let's describe such a system. $K_F = {KDF}(K_M, \mathbb{nonce}_F)$ where each value is 256 bits. Then start the ${IV}$ / counter at all zero so you can just perform $C = E_{CTR}(K_F, {IV}=0, P)$ and $C_{total} = ({nonce}_F, C)$ where $P$ is the original file and $C$ is the encrypted file.

Answer 2

You will be able to encrypt messages of size $2^{64}*16$ bytes before your keystream is reused within a message. This should suit your needs.

If your IV is randomly generated each time, you will need to consider the birthday attack for $H=2^{64}$ (64 bits). According to the table, if you encrypt 6,100 downloads, the probability of random collision is $10^{-12}$. This is still the case if the IV has lower 64 bits set, because that is equivalent to the scenario when IV is null in lower 64 bits and the initial counter $i$ is increased by the value of those bits mod $2^{64}$

Implementation is up to you but you can keep your IV and counter as separate ints then combine them. Counter will then roll over automatically. IV is an int128 and counter is an int64.

EDIT: There is no need to increment the higher 64 bits of the IV. This is not your counter. Don't change it. You have plenty of keyspace to use by only changing the 64-bit counter, as described above.