3
$\begingroup$

I want to use AES CTR with a random IV, as this would be the easiest way for me. I have a cryptographic module, that supports true random number generation. Due to compatibility, I must use AES CTR. The module also supports a monolithic counter, but its max value is quite low and might be too low for my use-case.

RFC 3686 states the following:

enter image description here

I must ensure that the IV never repeats, which is not true for a random number, as it could repeat. My key does not change. I found this thread on so that states, that using a random number (128 bit in this case) is an easy way to do it, as collisions are very unlikely.

My counter block would consist of only 64 bits of random (IV), 32 bytes would be reserved for the block counter, and 32 bytes for a static device identifier (Nonce). The generation of a new random IV would only occur on device restart and block counter overflow, both events occur rather rarely. This minimizes the possibility of a collision drastically, however, a chance remains.

enter image description here

My questions are:

  1. Is there an official document that states, that using a random IV for a fixed key is a valid approach (not just a so answer :))
  2. If not, do you think, that this approach is valid?

Thanks in advance and best regards

$\endgroup$

1 Answer 1

5
$\begingroup$
  1. Is there an official document that states, that using a random IV for a fixed key is a valid approach (not just a so answer :))

The NIST 800-38a states what you need and remember the problem occurs when $(key,IV)$ pair is reused, or more precisely say under the same key any $(IV||counter)$ combination. The latter can happen if random IV is used then under the same key, two messages collide in different positions.

Two approaches are given in 800-38a

  1. Sequential generation

In the first approach, for a given key, all plaintext messages are encrypted sequentially. Within the messages, the same fixed set of $m$ bits of the counter block is incremented by the standard incrementing function. The initial counter block for the initial plaintext message may be any string of $b$ bits. The initial counter block for any subsequent message can be obtained by applying the standard incrementing function to the fixed set of $m$ bits of the final counter block of the previous message. In effect, all of the plaintext messages that are ever encrypted under the given key are concatenated into a single message; consequently, the total number of plaintext blocks must not exceed $2^m$. Procedures should be established to ensure the maintenance of the state of the final counter block of the latest encrypted message and to ensure the proper sequencing of the messages.

In short, one continues where the counter left+1 not counter exceeding the $2^m$

  1. With Nonce

A second approach to satisfying the uniqueness property across messages is to assign to each message a unique string of $b/2$ bits (rounding up, if $b$ is odd), in other words, a message nonce, and to incorporate the message nonce into every counter block for the message. The leading $b/2$ bits (rounding up, if $b$ is odd) of each counter block would be the message nonce, and the standard incrementing function would be applied to the remaining $m$ bits to provide an index to the counter blocks for the message. Thus, if $N$ is the message nonce for a given message, then the $j$th counter block is given by $T_j = N || [j]_m$ , for $j = 1…n$. The number of blocks, $n$, in any message must satisfy $n < 2^m$. A procedure should be established to ensure the uniqueness of the message nonces.

In short, this is the nonce is incremented per message.

There is no mention of random generation in this document it is an old document too. In AES-GCM NIST 800-38d, it is either random nonce or incremental nonce with counter/LFSR is advised, remember AES-GCM uses CTR mode with a combination of a 92-bit nonce 32-bit counter. 92-bit nonces are safer to use in random than 64 bit IVs since the collision probability is low.

We simply approximate the collision probability by the square root for 50%. Therefore we can say 64-bit random nonces have 50% collision probability after $2^{32}$ unifrom random nonce generation. Actually, in the adversary sense, this is not negligible one must stop way earlier. In the case of 96-bit, one needs to generate uniform random $2^{48}$ nonces to hit 50% and the same adversary approach should be taken. To see more detail about the collision see Birthday problem for cryptographic hashing, 101. by fgrieu.

  1. If not, do you think, that this approach is valid?

Since your key never changes there is a 50% collision probability after encrypting $2^{32}$ messages and you will hit the (key,IV) reuse problem, the more you encrypt the more you will have.

As I can see, your compatibility is CTR not how it is used. You can either use sequential IV as in GCM's suggestions that will enable you to encrypt up to $2^{64}$ messages under the key or remove the device identifier for the IV and use random generation under which you will get a collision with 50% probability after encrypting $2^{48}$ messages.

The first statement would only be true, if just the IV changes for every encrypted 16-byte block. However the IV only changes on reboot and block counter overflow. One more note: there is a 10s delay after a reboot, so generating new 64-bit IV this way, it would take (2^32 * 10s) / ( 60 * 60 * 24 * 365)s = 1360 years to reach the 2^32 messages. But it would indeed be an option to increase the IV by 2 bytes by reducing the block counter to 2 bytes.

you said I get a 50% collision after 2^32 messages. Did you consider the 32-bit block counter?

That is depending on how the counter is used there it is assumed that the nonce is used only once.

The first statement would only be true, if just the IV changes for every encrypted 16-byte block. However the IV only changes on reboot and block counter overflow. One more note: there is a 10s delay after a reboot, so generating new 64-bit IV this way, it would take (2^32 * 10s) / ( 60 * 60 * 24 * 365)s = 1360 years to reach the 2^32 messages. But it would indeed be an option to increase the IV by 2 bytes by reducing the block counter to 2 bytes.

The message size is 1 to 3 blocks (16 bytes), there are different messages, but a lot of them repeat over and over.

In this way, you can use the counter up to $2^{32}/3 \approx 2^{28}$ messages without changing the IV. One should note that to use this you need to store the last used position +1 on the system.

System failures

During the system failures, one may fail to store it correctly and this can cause reuse of the olf position. In this case, a new nonce generation is suggested and since this requires already a reboot then there is no problem here.

$\endgroup$
9
  • $\begingroup$ Note that an import ingredient is missing the number of the devices that I've skipped to consider. $\endgroup$
    – kelalaka
    Dec 21, 2020 at 10:19
  • $\begingroup$ Thanks for your input! Greatly appreciated. You said I get a 50% collision after 2^32 messages. Did you consider the 32-bit block counter? The first statement would only be true, if just the IV changes for every encrypted 16-byte block. However the IV only changes on reboot and block counter overflow. One more note: there is a 10s delay after a reboot, so generating new 64-bit IV this way, it would take (2^32 * 10s) / ( 60 * 60 * 24 * 365)s = 1360 years to reach the 2^32 messages. But it would indeed be an option to increase the IV by 2 bytes by reducing the block counter to 2 bytes. $\endgroup$
    – earthling
    Dec 21, 2020 at 10:42
  • $\begingroup$ Can you elaborate on the number of devices to consider? $\endgroup$
    – earthling
    Dec 21, 2020 at 10:43
  • 1
    $\begingroup$ If the 32-block counter starts from 0 for every message then there is no consideration of it on the collision computation on random IVs. Besides the max size of each message is also important to consider when you are working as the first case of the 800-38a. Let me wrote the other parts in an extension of the answer. Does the number of deceives is really $2^{32}$? You may consider using less space. $\endgroup$
    – kelalaka
    Dec 21, 2020 at 10:58
  • $\begingroup$ Starting from 0, the 2^32 consideration makes sense. However, please consider the 10s reboot time for generating a new IV. The message size is 1 to 3 blocks (16 bytes), there are different messages, but a lot of them repeat over and over. I can't reduce the size of the nonce due to downwards compatibility. $\endgroup$
    – earthling
    Dec 21, 2020 at 11:04

Your Answer

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

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