3
$\begingroup$

I am planning to use AES-GCM or AES-CTR for encryption. However, I have read from several sources that the IVs must be unique for every piece of information encrypted. I have a doubt though, what if I choose different IVs for the two encrypt calls, but the counter addition makes the IV+counter value the same for some of the blocks. Would this be a security risk?

counter = 1, 2, 3, 4, 5, ...
iv1 = 100
iv2 = 102

// blocks of text1
b11 => (101 = 100 + 1), b12 (102 = 100 + 2), b13 (103 = 100 + 3), ...

// blocks of text2, notice that iv+counter is same as the block b13
b21 => (103 = 102 + 1), ...
```
$\endgroup$
1
  • 2
    $\begingroup$ There are three parts to this question: 1) if there is an overlap in blocks, what's the security risk ? 2) how likely is it that there is such overlap ? 3) can this probability be reduced, perhaps to zero ? $\endgroup$
    – fgrieu
    Jul 8, 2022 at 6:27

1 Answer 1

3
$\begingroup$

However, I have read from several sources that the IVs must be unique for every piece of information encrypted.

Yes, that is basically correct. The terminology is a bit wrong though: the counter blocks must be unique, as the counter block is used as input to the encryption primitive (such as the AES block cipher, which will be assumed in the rest of this answer). This in turn creates a key stream, and the key stream blocks should be independent of each other. The key stream is then XORed with the plaintext to form the ciphertext.

I have a doubt though, what if I choose different IVs for the two encrypt calls, but the counter addition makes the IV+counter value the same for some of the blocks.

Generally the counter blocks are created by concatenating a nonce and an actual counter, increased for each block. The counter is generally initialized to zero. The counter part is then increased using modular addition of 1. It depends per implementation, but usually the implementations require you to specify the full 128 bit counter block (the "IV") at the start, and then perform modulo $2^{128}$ addition.

The problem happens when enough blocks have been encrypted so that the counter in the counter block overflows into the nonce. If the counter in the construction is 32 bits then this happens after $2^{32}$ blocks, i.e. 64 GiB of plaintext / ciphertext, assuming you started at zero for the counter.

Here is an example using hexadecimals, assuming a big endian counter. Option 1 is using modulo $2^{128}$ addition over all the bits / bytes and Option 2 is using modulo $2^{32}$ addition over the last 32 bits / bytes. All values in the block are displayed using hexadecimals. This is for one single message, so the nonce is displayed as a (randomized) static value.

Counter block 0
--------------------------|---------
          Nonce           | Counter
8A73A31F2A33C13B5AE5234A  | 00000000

Counter block 1
--------------------------|---------
          Nonce           | Counter
8A73A31F2A33C13B5AE5234A  | 00000001

Counter block 2^32 - 1
--------------------------|---------
          Nonce           | Counter
8A73A31F2A33C13B5AE5234A  | FFFFFFFF

Option 1: Overflow into nonce (possible collision)

Counter block 2^32 
--------------------------|---------
          Nonce           | Counter
8A73A31F2A33C13B5AE5234B  | 00000000

Option 2: Wrap around of counter (collision with counter block zero of the same message)

Counter block 2^32
--------------------------|---------
          Nonce           | Counter
8A73A31F2A33C13B5AE5234A  | 00000000

So generally the encryption should stop after a certain amount of blocks have been encrypted. How much can be encrypted depends on the size of the counter within the counter block. This is why most implementations will use addition of 1 using modulo $2^{128}$ as this means that the user can control the size of the nonce and thus the counter; the nonce size determines the amount of messages that can be encrypted, and the counter size determines the size of those messages.

Would this be a security risk?

Yes, because you can now XOR the ciphertext blocks that had the same counter block and key. This means that the key stream is identical. If you XOR the ciphertext blocks together then the key streams are nullified, and you end up with a XOR of the two plaintext blocks. If you have information about one of the plaintext blocks then this immediately means that you also have information about the other block.

If you want to know how to attack such a construction then look at examples or practices around a many-time pad.


Now for GCM: GCM doesn't accept a counter block as "IV". Instead it assumes that the IV is the nonce of 96 bits. If the IV is any other size then it will use that value to calculate the nonce instead (or it will fail if this functionality is not implemented). It has a static size of the counter in the counter block of 32 bits. However, it skips counter value 0 and uses counter value 1 for the calculation of the authentication tag. This means that it overflows after $2^{32} - 2$ blocks, so 64 GiB - 32 bytes.


Notes:

  • in principle the configuration of the counter block is completely up to the user for CTR mode;
  • the same goes for how the counter is increased by the implementation, big endian addition modulo $2^{128}$ is extremely common, but there are even little endian implementations out there;
  • a small nonce inside the counter block can quickly become an issue if the nonce itself is randomized, due to the birthday problem;
  • it is highly recommended to simply use a 96 bit / 12 byte nonce for GCM;
  • we can generally assume that an adversary knows the contents of the counter block, so they should be able to easily find identical key stream blocks to XOR them together;
  • some users randomize the entire IV / counter block for CTR, which basically means that it isn't known when the counter overflows - I would not recommend this.
$\endgroup$
1
  • $\begingroup$ Hey Maarten, I understood everything except this bit "This is why most implementations will use addition of 1 using modulo 2^128 as this means that the user can control the size of the nonce and thus the counter". Can you please elaborate more or share a link where I can specifically read more on this? $\endgroup$
    – Atul Vani
    Jul 11, 2022 at 1:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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