AES 128 bits with 12 bytes IV vector composed of a 4 bytes counter : safe?

I have a 128 bits AES cypher (GCM, Galois/Counter Mode) using a 12-byte initialization vector (IV) composed of:

• 8 constant bytes:
• 6 bytes (device ID)
• 2 bytes (zero)
• 4 bytes (incrementing frame counter)

Is this really safe? Assuming the frame counter may overflow in the long run.

• If you don't rotate the keys, then you're screwed as soon as you re-use an IV / key pair. (e.g. after $2^{32}+1$ messages) – SEJPM May 16 '16 at 10:27
• safe is relative, it may be safe for others but not for you – Richie Frame May 16 '16 at 11:13
• One more possible issue: What kind of storage frame counter uses? If it is volatile storage, then you may have problem of IV reuse after device power is reset. After power reset the device needs to either start using fresh key or if it uses the same key, then the device needs to remember what frame counter values (may) have been previously used. – user4982 May 16 '16 at 14:24
• In fact I do not know if the frame counter is volatile or not, but I'm assuming it's not (there is some kind of non volatile storage). One angle of attack in that case could be to force the reset of the frame counter? (for example submitting the device to a strong magnetic field to force a reset). – Laurent Grégoire May 16 '16 at 17:52

As SEJPM notes in the comments, the IVs will repeat after $2^{32}$ frames. This is bad (unless the key is changed more often than that).

In particular, if you can temporarily capture the device and make it encrypt $2^{32}$ known messages of sufficient length, you will learn the keystreams corresponding to all the $2^{32}$ possible IVs for that device. This allows you to trivially decrypt any past or future messages sent by the device just as easily as if you had the key.

Depending on the nature of the device, convincing it to encrypt $2^{32}$ known messages may be anything from impossible to trivially easy. Since you yourself mention that "the frame counter may overflow in the long run," it seems that it's at least within the realm of possibility.

In any case, even if this particular attack turns out to be infeasible, any situation where two different messages are encrypted in CTR mode with the same key and IV violates the basic assumptions of the security proof for CTR mode, and makes it potentially vulnerable to attacks.

To prevent such attacks, you'd need to either:

• ensure that the frame counter can never overflow (under normal or abnormal operating conditions), or
• ensure that the key is changed (at least) every time the frame counter overflows.

To prevent counter overflow, you can either widen the counter (e.g. adding the two unused bytes in the IV to the frame counter to make it 48 bits wide) or add an explicit overflow check (which might mean bricking your device instead of compromising security if the maximum number of message frames is exceeded, unless you have some kind of a key update mechanism in place), or, better yet, both.

Addendum: As user4982 notes above, a similar attack is also possible even without wraparound, if the frame counter can be forced (or accidentally made) to reset to zero (or to any previously used value) e.g. by cutting power to the device.

One way to defeat this attack is to store the frame counter in non-volatile (e.g. flash) memory. Since such memory can often be slow to write to, and may not tolerate an unlimited number of write-erase cycles, one commonly used trick is to write a value that is, say, 1000 frames higher than the actual current counter value, and then wait until the actual counter catches up to the stored value before the next write. This allows you to reduce the number of writes to non-volatile memory by a factor of 1000, at the cost of potentially skipping up to 1000 counter values every time the device is reset.

(There are other, more sophisticated methods of minimizing non-volatile memory wear as well, but they tend to depend on the specific characteristics of the non-volatile storage you're using.)

Of course, if the device already has some way of changing the encryption key, another option could be to simply change the key every time the device is reset, eliminating the need to store the counter entirely.

• It's probably worthwhile to address @user4982's point in the comments above. If the frame counter can be reset (for instance, by power cycling the device), then it will be trivially easy to get the device to replay keystreams. – Stephen Touset May 16 '16 at 19:16
• I guess the frame counter is stored in volatile storage. In that case, given the low speed of the network (1200 bps), frame counter wraparound is a far fetched scenario. – Laurent Grégoire May 16 '16 at 20:13