- 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
- 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$
- 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.
- 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.
