What are the implications of allowing a zero-length GCM nonce?

Question

NIST SP800-38D section 5.2.1.1 is clear that empty nonces are not allowed with GCM, but without explaining the reasoning. My assumption was this is simply because the probability of error (encrypting multiple messages with an empty nonce) would be to high in any system that supported empty nonces at all. As NIST does not allow it, my GCM implementation does not support empty nonces.

However I was recently directed to Apple's CoreCrypto library which has a special function ccgcm_set_iv_legacy to enable empty nonces, and the documentation for this function includes the statement

"Zero-length IVs nullify the authenticity guarantees of GCM."

[https://opensource.apple.com/source/xnu/xnu-4570.41.2/EXTERNAL_HEADERS/corecrypto/ccmode.h.auto.html]

Can anyone explain what is meant by this? Of course if you encrypt multiple messages with GCM using a zero-length IV and the same key you have a serious problem. But is there something more to this warning? In particular can you safely encrypt a message with a zero-length IV as well as some number of messages with non-zero length IVs?

Answer 1

As documented in NIST SP800-38D, GCM works as follows, upon input of block cipher $E$, key $K$, initialization vector $IV$, and plaintext $P$:

1. Compute the GHASH key $H=E_K(0^{128})$
2. Compute the initial counter-mode value $J_0$ using some rules which amount to $J_0=0^{128}$ for an (illegal) empty IV.
3. Encrypt the plaintext using CTR-mode and IV $\operatorname{inc_{32}}(J_0)$, i.e. $C=\operatorname{GCTR}_K(\operatorname{inc_{32}}(J_0),P)$
4. Compute the polynomial hash (GHASH) over the ciphertext $C\|0^u\|\operatorname{len}(A)\|\operatorname{len}(C)$ using the key $H$ and call the resulting block $S$.
5. Compute the tag as $T=\operatorname{GCTR}_K(J_0,S)$

Now the key thing to note here is that $\operatorname{GCTR}_K(J_0,S)$ actually amounts to computing $E_K(J_0)\oplus S=E_K(0^n)\oplus S=H\oplus S$. Now we only need to realize that e.g. for a single-block message we have $T=H\oplus S=H\oplus H^2\cdot C\oplus H\cdot L$ where $L=\operatorname{len}(A)\|\operatorname{len}(C)$. As you can probably see the last equation $T=H^2\cdot C\oplus H\cdot L\oplus H$ is actually a quadratic equation where we know every value except $H$.

As we're working over a finite field in the above computation, we can just solve the equation using standard algebra and compute $H$ using the appropriate operators for the field. As you have now recovered $H$, you can change the ciphertext however you want and re-authenticate it at-will and even do that to messages with a different nonce but the same key.

This issue is avoided in "legal" versions of GCM by hashing in the length of the IV for variable-length IVs and for fixed-length IVs by setting the last bit to 1. This then yields a $J_0\neq 0^{n}$ which gets translated to a (pseudo-)random independent-looking value by $E_K(J_0)$.