This is a follow-up to a previous question about encrypting IV/MAC results from AEAD ciphers.
I have a system I'm working on that needs to use standard (NIST/FIPS) cryptography, at least for its primary security layer. This is going to be AES-256/GCM used exactly as directed. I am also going to have periodic re-keying with a re-key interval around two minutes.
Random nonces in this system are only 64 bits though. (Internally they'll be padded to 96 bits for GCM by adding the message size and other bits, but only 64 random bits are used in the protocol.) Re-keying every two minutes makes nonce reuse with the same key very unlikely, but I still wouldn't mind adding some mitigation for additional margin and defense in depth.
This is a minimal-state system, so stateful nonce reuse resistance schemes are problematic. (Stateful nonce generation is a footgun anyway.) This is also a packet based system rather than a stream protocol so reliable message delivery can't be guaranteed, making stateful ratcheting schemes hard to implement and clunky. Its packet-based nature also means that in theory re-keying could fail multiple times, potentially extending the key lifetime... which is part of why I'd like to add some extra margin here.
So I'm researching whether there's any way to apply a nonce-reuse/misuse resistance mitigation after the fact. (I'm aware of SIV modes but they're not standard so I can't use them.)
Here's the idea I have:
- Encrypt with AES256/GCM in the boring standard way: Nonce + Plaintext -> Auth Tag, Ciphertext.
- Concatenate 64-bit nonce with 64-bit auth tag and encrypt with AES256 in ECB mode (it's only one block). (This is the first of two ECB encryptions.)
- Initialize another cipher using this encrypted nonce+auth tag.
- Encrypt the encrypted nonce+auth tag again and include this final AES(AES(Nonce+Auth Tag)) in the message.
- Encrypt the ciphertext output of AES256/GCM with the other cipher we initialized in step 3.
(Decryption basically goes 4, 3, 5, 2, 1.)
Encrypting the nonce and auth tag together (step 2) mixes them and yields a 128-bit combined tag that's dependent on both the nonce and the message content. This makes it impossible to detect a duplicate nonce by just observing the nonce field.
BUT as others pointed out in my previous post, a duplicate nonce will still result in an identical GCM (CTR) key stream. This means an attacker can XOR messages together and look for duplicated nonces by looking for cases where the result matches a known plaintext or has low entropy.
The mitigation against this is in step 5. A secret key that depends on both the auth tag and the nonce is used to encrypt the ciphertext again, making it impossible to just XOR messages to look for duplicated nonces.
(Note that a message with a duplicate nonce and plaintext will result in an exactly identical encrypted final message, but that's not a big deal. It only reveals that an identical message was sent. It doesn't allow anything to be decrypted. It's also extremely unlikely.)
My final question is about this secondary cipher's strength requirements for this mitigation to matter. For performance reasons this cipher that is used for this mitigation step should be incredibly fast and it doesn't seem like it needs to be all that strong. The only goal here is to make it impractical for an attacker to store a ton of messages and XOR them together to look for nonce collisions (with the same key). Let's say our secondary cipher has a strength of 2^64 bits. Every key is random and plaintext is ciphertext, so the only way I can attack it is to look for collisions. This means doing 2^128 operations per message pair because for each iteration in my attack I must do 2^64 corresponding iterations on another message to check for attack success. Something very weak and very fast like 4-round AES-128 or 8-round Speck might be good enough...?
So the time complexity of searching for collisions seems to be 2^(2N) where N is the relative strength of the secondary cipher and the space complexity seems to be M*(2^32) where M is the average size of a message and 2^32 due to 64-bit nonces and the birthday bound. For a 2^64 difficulty secondary cipher and 1400 byte averages messages that's 2^128 time and about 6TB space. This of course ignores periodic re-keying. As soon as re-keying happens you must start over.
Going back to the certification topic: since AES256/GCM provides the "real security" in this system, it can be the thing considered in certification. This defense in depth bolt-on could be ignored as an additional protocol detail with no "official" security role.
I guess my question is whether my scheme is strong enough to be worth spending a few CPU cycles to apply. Would this really mitigate accidental nonce reuse? If I were an attacker I can't think of a way I'd detect nonce reuse in this scheme (other than the scenario of duplicated plaintext and nonce), but anyone can design an encryption scheme they themselves can't break right?
In response to Squeamish Ossifrage's more standard and conceptually clear but unfortunately too slow construct they posted below, I've thought of a simpler way to explain mine and possibly relate the two.
To encrypt the message, I do:
t, c = AES-GCM(i, k, m) a = AES-ECB(k, i | t) (one block) C = AES-ECB(a, c) (multiple blocks) T = AES-ECB(k, a) (one block) i = 64-bit nonce/IV k = 256-bit AES-256 session key m = plaintext t = 64 bits of AES-GCM authentication tag c = AES-GCM ciphertext (inner ciphertext) a = outer key for final ECB step C = final ciphertext T = final "combined tag"
Decryption is left as an exercise to the reader. It's pretty obvious.
This is very fast (1.3-1.4GiB/sec per core). I can also see that:
- AES-ECB encrypting (i | t) yields an encrypted 128-bit result that will be different for every message even if i repeats. It's also opaque unless you can break AES.
- AES-ECB encrypting the GCM ciphertext with an ephemeral key dependent on the original message does not weaken GCM at all, and is not amenable to XORing messages together because AES-ECB is not an XOR OTP.
- AES-ECB encrypting (i | t) a second time to conceal the inner ephemeral key does indeed conceal this key unless you can break AES.
Maybe that's more clear. Unless I am totally missing something this does protect against IV reuse and I can't see how it weakens standard AES-GCM encryption in any way... again unless you can break AES. If you can break AES you can basically attack the entire world economy. Have fun.
This is not standard, but the use of AES256-GCM with a 64-bit nonce and tag is okay for short messages with frequent re-keying. This system will re-key about every minute or two. I'm thinking that FIPS/NSA could look only at the way GCM is used and ignore this as a "protocol detail." The goal here is to harden this beyond FIPS by completely eliminating the risk of IV use (in a stateless system, where it is possible) while still being able to link against FIPS-compliant libraries and pass muster by being able to say the main security of our system is based on standard primitives.