[MoonObserver]

> Never use random IVs with GCM; this breaks the authentication [2] [3]. Given the pitfalls of AES-GCM with respect to random nonces, you might prefer switching to XSalsa20+Poly1305. The advantage of XSalsa is it has an extended nonce length, so you can use random nonces without fear.

Those papers are a bit over my head. Could you please explain what's wrong with using random IVs here? What should we do instead (assuming we can only use GCM, and not switch to chacha)

[conradludgate]

There's two issues.

Background: the key+IV define a keystream which is xor-ed against the message. The same key+IV generate the same keystream. Thus you can XOR two cipher texts and reveal information from the two plaintext.

AES-GCM is authenticated encryption. To combat known-ciphertext-attacks, you want to have authenticated cipher texts. AES-GCM specifically is vulnerable to an attack with a reused IV to recover the authentication key. Allowing you to forge authentication tags and employ a KCA.

The solution, if you're stuck with aes, is to switch to XAES-GCM or better AES-GCM-SIV. Alternatively you must use a counter or checkes system to not reuse IV. Since this is in the context of 1fps, you could use unix timestamp + random bytes to reduce the chance of collisions.

[hatsunearu]

Is the statement just that if you use a random value for a nonce rather than some guaranteed never-used-once value, it's possible to get a collision faster than the "natural" block collision complexity (half block size or something like that)?

[conradludgate]

It's a birthday attack principle. With only 96bits after roughly a billion messages with the key and random IVs, you start reaching realistic probabilities that you will reuse an IV

[irundebian]

And how you will get a billion messages with 1 frame per second?

[jszymborski]

Not an expert, but this is my understanding.

1. It is necessary for nonces to never be re-used for a given key lest you open yourself to a certain class of attacks that can decode all messages using that key. This is specific to AES-GCM due to how it internally reuses nonces.

2. AES-GCM uses very small nonces, making the probability of randomly using the same nonce unacceptably as the number of messages encoded with a given key increases (as it would with each frame sent on 1fps).

You can avoid all this by using a different primitive with a longer nonce such as XSalsa (a version of Salsa with a 192-bit nonce)

[Vegenoid]

In AES-GCM (simplified explanation), an encrypted message takes 3 inputs: plaintext, a symmetric encryption key (generally unique per-session, as in this program), and a 12-byte nonce (a.k.a. IV).

If an attacker intercepts 2 messages that were encrypted with the same key and the same nonce, they can reveal the authentication key used for the generation of authentication tags (auth tags), and they can then forge auth tags for any message. These auth tags are how a recipient verifies that the message was created by someone who knows the symmetric key that was used to encrypt the plaintext, and that it was not altered in transit.

More simply, it allows an attacker to alter the ciphertext of an encrypted message, and then forge an authentication tag so that the modification of the ciphertext could not be detected. It does not reveal the symmetric key that allows decryption of the ciphertext, or encryption of arbitrary plaintext.

If a random nonce is generated, there is a chance that it is the same as a random nonce that was generated earlier in the session. Since the nonce is 12 bytes, this chance is very small for any 2 random nonces (1 in 2^96), but the chance of a collision increases rapidly with the number of encrypted messages sent in a session (see the birthday problem). It still requires a large number of messages to be sent before the chance of a collision becomes significant: "after 2^28 encryptions the probability of a nonce collision will be around 0,2 % ... After 2^33 [encryptions] the probability will be more than 80 %"[0]

If this program is sending 1 message per second (1 FPS), it would take 8 years for 2^28 messages to be sent. I haven't looked at the code, it may well be sending many more messages than that.

The alternative to a random nonce is a "counter" nonce, which starts at 1 and increments with each message. The potential pitfall of counter nonces is that they can be harder to implement, as they require tracking and updating state. If the program ever fails to track or update this state correctly, nonce reuse will occur. A different counter must be used for each symmetric key (which should be randomly generated for each session).

EXTRA CREDIT: There is also information revealed about the plaintext of the 2 messages that used the same key and nonce - specifically, the XOR of the 2 plaintexts. While this doesn't directly reveal the plaintexts, if some information about one of the plaintexts is known, that can be used to reveal information about the other plaintext.

I learned most of this information from David Wong's Real-World Cryptography.

[0]: https://eprint.iacr.org/2016/475.pdf, section 3.3