Paper 2026/2293

Nonce Misuse Resilience of GCM with Rijndael-256-256

Abstract

GCM is the leading authenticated encryption scheme. With its application in TLS alone, it finds millions of uses every day. However, in the last years, various shortcomings of GCM have been observed: mistakes in earlier proofs, non-optimal security degradation in case of shorter tags, the support for a $96$-bit nonce only (concatenated with a $32$-bit counter) for the most widely implemented variant, but most of all, the brittle resistance against nonce misuse. This latter shortcoming is particularly worrisome in applications where uniqueness of the nonce cannot be guaranteed (such as in distributed systems). In part to salvage this situation, the US National Institute of Standards and Technology (NIST) is contemplating the idea of standardizing Rijndael-256-256. Indeed, sticking to the concept of a $32$-bit counter, this would allow the support of $224$-bit nonces next to the $32$-bit counter. Nonetheless, it may be observed that nonces may still be accidentally reused due to other causes and the larger block size does not solve the fatal effects of nonce misuse, among which the possibility to perform a subkey recovery. To salvage this, we propose GCM-256. The fix is, as a matter of fact, rather simple and comes almost for free. In a nutshell: whereas a native generalization of GCM to $256$-bit blocks would mask the output of GHASH with only half of the output of the initial nonce based block cipher evaluation, we suggest to not discard the other half but use it as key to GHASH. As an effect, we demonstrate that GCM-256 does not only achieves classic confidentiality and authenticity, but as a bonus it achieves nonce misuse resilience, meaning that even if nonces are misused, the scheme still guarantees security for fresh nonces.