...And you will know me by the trail of bits
Announcing AES-GEM (AES with Galois Extended Mode)
By Scott Arciszewski
Today, AES-GCM is one of two cipher modes used by TLS 1.3 (the other being ChaCha20-Poly1305) and the preferred method for encrypting data in FIPS-validated modules. But despite its overwhelming success, AES-GCM has been the root cause of some catastrophic failures: for example, Hanno Böck and Sean Devlin exploited nonce misuse to inject their Black Hat USA slide deck into the MI5 website.
Security researchers have been sounding the alarm about AES-GCM’s weaknesses for years. Nineteen years ago, Niels Ferguson submitted a paper to a NIST project on block cipher modes outlining authentication weaknesses in AES-GCM (although NIST would ultimately standardize it). And earlier this year, Amazon published a paper that detailed practical challenges with AES-GCM and posited that AES’ 128-bit block size is no longer sufficient, preferring a 256-bit block cipher (i.e., Rijndael-256).
To address these issues, I propose a new block cipher mode called Galois Extended Mode (GEM for short), which I presented last month at the NIST workshop on the requirements for an accordion mode cipher. AES-GEM improves the security of GCM in every dimension with minimal performance overhead.
Important: The current design for AES-GEM is not ready for production use, as some details will likely change in the future. To understand the current design, let’s start by understanding where AES-GCM falls short, and then discuss how we can do better with GEM.
How AES works
Before we dive in, it may be helpful for some readers to explain some of the terms and concepts used throughout this blog post.
AES (Advanced Encryption Standard) is a block cipher widely used to encrypt information. It supports multiple key sizes (128-, 192-, and 256-bit keys) but always operates on 128-bit blocks. AES is the standardized form of the Rijndael family of block ciphers. Rijndael supports other block sizes than 128-bit, but only the 128-bit blocks were standardized by NIST. Modern processors provide dedicated hardware instructions for accelerating AES operations, but the AES key schedule can still negatively impact performance.
ECB (Electronic Code Book) mode is the absence of a block cipher mode of operation. It involves computing the block cipher directly on a block of data. ECB mode is not semantically secure, as many cryptographers have demonstrated. For improved security, block ciphers like AES are typically used with a mode of operation. (If not, they almost certainly should be. Get in touch with our cryptography team if you think you’re using ECB to encrypt sensitive data.)
CTR (Counter Mode) is a mode of operation for block ciphers wherein an increasing sequence of values is encrypted with the block cipher to produce a pseudorandom keystream. To encrypt data, simply calculate the XOR of each plaintext byte with each corresponding keystream byte.
GCM (Galois/Counter Mode) is a block cipher mode of operation that provides authenticated encryption. It is what cryptographers call an AEAD mode: Authenticated Encryption with Additional Data. GCM can provide confidentiality for sensitive data and integrity for both sensitive and public data.
AEAD modes are important for designing cryptosystems that are resilient to attackers who attempt to mutate encrypted data in order to study the system’s behavior in hopes of learning something useful for cryptanalysis.
GCM is a composite of Counter Mode (CTR) for encrypting the plaintext and a Galois field Message Authentication Code (GMAC), which authenticates the ciphertext (and, if provided, additional associated data). GMAC is defined with a function called GHASH, which is a polynomial evaluated over the authenticated data. The output of GHASH is XORed with an encrypted block to produce the final authentication tag. The authentication key, called H, is calculated by encrypting a sequence of 128 zeroed bits.
POLYVAL is an alternative to GHASH that is used in AES-GCM-SIV. The irreducible polynomial used by POLYVAL is the reverse of GHASH’s irreducible polynomial.
Many cipher modes (including GCM and CTR) require a number that is used only once for each message. This public number that should never be repeated is called a nonce.
Finally, the birthday bound is a concept from probability theory that indicates the likelihood of collisions in a set of random values. In cryptography, it implies that if nonces are selected randomly, the probability of two nonces colliding increases significantly as more nonces are used. For AES-GCM with 96-bit nonces, after about 232 messages, there’s a 1 in 232 chance of a nonce collision, which can lead to security vulnerabilities such as the ability to forge messages.
Practical challenges with AES-GCM today
The biggest challenge with AES-GCM, as others have pointed out, is that AES only has a 128-bit block size. This has two primary consequences:
- The size of the public nonce and internal counter is constrained to a total of 128 bits. In practice, the nonce size is usually 96 bits, and the counter is 32 bits. If a larger nonce is selected, it is hashed down to an appropriate size, which has little improvement on security. If you ever reuse a nonce, you leak the authentication subkey and can, therefore, forge messages indefinitely.
- Above a certain number of blocks encrypted under the same key, an attacker can distinguish between ciphertext and random bytes with significant probability.
- Key length: 128 bits
- Subkey length: 128 bits
- Nonce length: 192 bits
- Maximum plaintext length: 261 – 1 bytes
- Maximum AAD length: 261 – 1 bytes
- Tag length: 48 bytes (AEAD) or 16 bytes (without commitment)
- Key length: 256 bits
- Subkey length: 256 bits
- Nonce length: 256 bits
- Maximum plaintext length: 261 – 1 bytes
- Maximum AAD length: 261 – 1 bytes
- Tag length: 48 bytes (AEAD) or 16 bytes (without commitment)
- Derive an authentication subkey, H, by encrypting an all-cleared block with the key.
- Calculate GHASH() of the ciphertext, associated data, and a block containing the lengths of both segments (in bits).
- XOR the output of step 2 with the AES-CTR encryption of a counter block.
- Derive an authentication subkey, H, by encrypting an all-set block with the subkey.
- Calculate GHASH() of the ciphertext, associated data, and a block containing the lengths of both segments (in bits).
- Encrypt the output of step 2 with AES-ECB, using the input key.
- XOR the output of step 3 with the AES-CTR encryption of a counter block.
- Key derivation: four additional blocks of AES encryption, some XORs, one additional key schedule
- Authentication: one additional block of AES encryption
- Key commitment: two additional blocks of AES encryption
- Key derivation: two additional blocks of AES encryption, some XORs, one additional key schedule
- Authentication: one additional block of AES encryption
- Key commitment: two additional blocks of AES encryption
- For AES-256-GEM, encrypt 32 bytes derived from the reserved nonce space, and use these as the actual CTR key.
- For AES-128-GEM, encrypt 16 bytes derived from the reserved nonce space (but a distinct nonce space from what AES-256-GEM would select), and use it as the actual underlying CTR key.
- Key derivation: four additional blocks of AES encryption, some XORs, one additional key schedule
- Additional key derivation every 236 bytes of plaintext: two additional blocks of AES encryption, one additional key schedule
- Authentication: one additional block of AES encryption
- Key commitment: two additional blocks of AES encryption
- Key derivation: two additional blocks of AES encryption, some XORs, one additional key schedule
- Additional key derivation every 236 bytes of plaintext: one additional block of AES encryption, one additional key schedule
- Authentication: one additional block of AES encryption
- Key commitment: two additional blocks of AES encryption
Categories: Security Posts