Nonce-misuse-resistance scheme applied after the fact to AES-GCM for defense in depth?

Question

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:

1. Encrypt with AES256/GCM in the boring standard way: Nonce + Plaintext -> Auth Tag, Ciphertext.
2. 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.)
3. Initialize another cipher using this encrypted nonce+auth tag.
4. Encrypt the encrypted nonce+auth tag again and include this final AES(AES(Nonce+Auth Tag)) in the message.
5. 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?

Edit: we blogged this and have a GitHub thread too.

Edit #2:

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.

Answer 1

• The AES-GCM forgery probability bounded by $qL/2^\tau$ where $q$ is the number of messages, $L$ is the maximum message length in 128-bit blocks, and $\tau$ is the length of the tag.

  Here you've truncated it to 64 bits, rather than 128 bits, so if you allow messages up to 16 megabytes long, the forgery probability after a single attempt is already around $1/2^{44}$ when you might hope it is closer to $1/2^{100}$. Maybe that's acceptable for your application if it saves a substantial transmission or storage cost—but you're still paying for a 128-bit tag, so it doesn't actually save any cost.

• The scheme you have described admits a chosen-plaintext distinguisher with advantage about $q^2\!/2^{64}$ where $q$ is the number of messages with the same nonce. Specifically, if the 64-bit truncation $t$ of the AES-GCM authentication tag collides between two messages, which by the birthday paradox happens with probability about $q^2\!/2^{64}$, then the derived key $a$ will collide too, and the adversary can tell when individual blocks in the two messages are the same.

  This is substantially worse security than one would expect from a deterministic authenticated cipher; e.g., AES-SIV bounds the advantage by about $q^2\!/2^{128}$ instead.

Better bounds cannot be proven for your scheme, so I wouldn't recommend using it!

Answer 2

What you are doing sounds like piling on complexity of dubious value without a clear understanding of what security the components actually provide, in the hope that enough complexity will render the question moot. I would advise you discard the hare-brained scheme you've cooked up and start from something much simpler that is easier to prove theorems about.

Here is a simple deterministic authenticated cipher with 256-bit key $k$ using only FIPS-approved components.^*

• To encrypt the $i^{\mathit{th}}$ message $m_i$, compute \begin{align*} a_i &= \operatorname{HMAC-SHA256}_k(i \mathbin\| 0 \mathbin\| m_i), \\ \kappa_i &= \operatorname{HMAC-SHA256}_k(i \mathbin\| 1 \mathbin\| a_i), \\ c_i &= \operatorname{AES256-CTR}_{\kappa_i}(m_i). \end{align*} The authenticated ciphertext is $(a_i, c_i)$.

• To decrypt the $i^{\mathit{th}}$ message $(\hat a_i, \hat c_i)$, which may be $(a_i, c_i)$ or may be a forgery, compute \begin{align*} \hat\kappa_i &= \operatorname{HMAC-SHA256}_k(i \mathbin\| 1 \mathbin\| \hat a_i), \\ \hat m_i &= \operatorname{AES256-CTR}_{\hat \kappa_i}^{-1}(\hat c_i), \end{align*} and drop it on the floor unless $\hat a_i \stackrel?= \operatorname{HMAC-SHA256}_k(i \mathbin\| 0 \mathbin\| \hat m_i)$.

(Here the nonce for AES-CTR is always zero, which is OK because we use an independent AES-CTR key $\kappa_i$ for each message.)

If you can't count to maintain $i$, it's safe to pick $i$ at random, or even to set $i = 0$ for all messages—with the usual caveat about any deterministic cipher that if you repeat $i$ then the adversary can tell whether a message is repeated or not.

It is easy to prove that this scheme provides reasonable DAE security for essentially arbitrary data volumes assuming reasonable PRF security of HMAC-SHA256 and PRP security of AES-256: the structure is SIV with the PRF $m_i \mapsto \operatorname{HMAC-SHA256}_k(i \mathbin\| 0 \mathbin\| m_i)$ and the cascade cipher $(\mathit{iv}_i, m_i) \mapsto \operatorname{AES256-CTR}_{\kappa_i}(m_i)$ where $\kappa_i = \operatorname{HMAC-SHA256}_k(i \mathbin\| 1 \mathbin\| \mathit{iv}_i)$. The cascade cipher has reasonable IND-CPA security by Theorem 3.1 of the XSalsa20 paper and the usual $\text{PRP} \to \text{PRF} \to \text{IND-CPA}$ chain of reasoning. The domain separation in the two uses of HMAC obviates the need to use a double-length key. The keys and authentication tags are large enough—256 bits—that you need not worry about collisions.

This won't beat any speed records unless you're using hardware acceleration for SHA-256 and AES—changing AES keys for each message is expensive in software—and of course your use of AES will invite timing side channel attacks on software implementations. But you didn't specify a budget and you're already using AES—your primary constraint seems to be that you use FIPS-certified components. If you have a budget, measured in joules or cycles per byte, you need to specify it clearly.

---

If HMAC-SHA256 is too slow and you are guaranteed to have AES hardware acceleration, it may be fruitful to use an AES-based PRF instead. For example, you could substitute the following instead, at some cost to security that I haven't calculated but should be more or less reasonable with bounds on advantage around $q^2\!/2^{128}$ after processing $q$ blocks of data—in other words, limit the volume of data under a single key to well below (say) $2^{48}$ blocks of data if you want the adversary's advantage to be below $2^{-32}$:

\begin{align*} a_i &= \operatorname{AES256-CMAC}_k(i \mathbin\| 0 \mathbin\| m_i) \\ \kappa_i &= \operatorname{AES256-CMAC}_k(a_i \mathbin\| 1) \mathbin\| \operatorname{AES256-CMAC}_k(a_i \mathbin\| 2) \\ c_i &= \operatorname{AES256-CTR}_{\kappa_i}(m_i). \end{align*}

(The numbers $0$, $1$, and $2$ are there just to ensure that the inputs to AES256-CMAC are encoded uniquely; here $i$ must be padded to 128 bits for this to work. Otherwise you have to study the collisions in the inputs directly in any security analysis. Again, the AES-CTR nonce is always zero here, because we derive an independent key $\kappa_i$ per message.)

Alternatively, if you can use AES-GCM, you can probably use AES(AES-GMAC) under the same key^† instead of AES-CMAC—AES-GMAC is just AES-GCM with empty ciphertext, and is amenable to vectorization unlike AES-CMAC, and if fed through a PRP like AES it makes a good PRF. The result is very nearly AES-GCM-SIV.

---

_{^* I don't know that this would pass muster for a FIPS compliance cultural apparatchik, but it uses HMAC-SHA256 for message authentication and AES256-CTR for message encryption. You could, of course, substitute AES256-GCM for AES256-CTR if you must use AES-GCM, at the cost of 16 more bytes per message.}

_{^† Using a second key here doesn't hurt, but is not necessary; the collision probability of inputs grows by a small constant factor but remains quadratic in the number of blocks, so safe data volume limits are the same.}

Answer 3

If you cannot eliminate the weak points, you can indeed work around them. I will not specifically try to sound like a paranoid here and say outright that this is by design, but FIPS/NIST standards can sometimes be designed in such a way that they are difficult to implement securely, and the cost of doing it wrong can be catastrophic. Working around it by preprocessing or postprocessing when you are sure that implementation cannot be done according to best practices can indeed be a good idea.

There are several things to note in general here:

1. On modern systems with hardware acceleration, AES is VERY fast. You can push several GB per second through the CPU, this is generally faster than you can read the plaintext or transmit the ciphertext, so there is room to apply multiple layers of encryption.

2. Modes like CTR and ECB can be encrypted and decrypted in parallel, making use of multiple cores for high performance implementations.

3. The weak points of GCM are as follows. The probability of nonce reuse, the size of the authentication tag, and the potential for exposure of the hash key ($E_K(0)$)

There are also a few things to note from your ideas.

1. "Initialize another cipher using this encrypted nonce+auth tag" requires you to encrypt and store the entire message before you can start the next layer.

2. "reliable message delivery can't be guaranteed" is not good for GCM in any way, since you need every single bit to authenticate.

If you want to maintain performance in a stateless system with a good system PRNG, using parallel algorithms is the way to go. But what you will need is more key material. You are processing the information directly with FIPS compliant AES-GCM and a 256-bit key.. you will want to use the entire auth tag, do not truncate to 64-bits. Since you need the nonce to start decrypting the message, you will want that to be the first part of the ciphertext.

You are generating 64-bit random nonces, and padding them to 96-bits. If possible, a 32-bit message counter should be the padding, if you loose the state it is still a better option than just having 0s. With a 64-bit random nonce, the probability of a nonce reuse is already too high for comfort, even when encrypting only 2 messages per key. The message counter helps a lot, but if the state can be lost you MUST do something to compensate.

The output of your FIPS module is a nonce/ciphertext/tag space that is 96+$x$+128 bits long, and it is time to apply more layers. The next layer will first pad the nonce to 128-bits, and pad the ciphertext to a multiple of 128-bits, making your entire message a size multiple of 128-bits. Then you encrypt with ECB.

Because of the way the message was padded, the nonce and auth tag are independently encrypted blocks. The message is now no longer xor-able with a known plaintext, although nonce reuse is still detectable if plaintext blocks are identical. The key for the ECB layer does not need to be rekeyed as often.

Now you have a message that is encrypted with an XOR type cipher (CTR) and a block permutation (ECB), the final layer is the same as the first, GCM, you can reuse the FIPS module again for this, but the key should not be the same as for the first GCM layer or the ECB layer. When you rekey, you can simply generate more key material, and change both GCM ciphers at the same time. You will need a new random nonce as well.

Since you are generating 2 nonces, your nonce space is now 128-bits, which is much more comfortable. The chance of both nonces repeating together is quite low. The reason you want to reykey the outer GCM layer with the inner is because of the weak points inherent to GCM. The final step will be to encrypt the auth tag of the outer layer with ECB, and output the final ciphertext. Also, increasing the nonce space for the message does not increase it for the individual layers, so you will not be able to increase the rekey interval securely.

Compared to a standard GCM implementation, you will be adding 64-bits of padding to the first nonce, up to 128-bits of padding to the initial message... and also the 2nd 64 (or 96)-bit nonce and 128-bit tag, for a total of up to 3-4 blocks, or no more than 48 (or 52) bytes. You will also need to store more key material, a long term 128 to 256-bit key for the ECB layer, and a temporary 128 to 256 bit key for the outer GCM layer.

The entire system can encrypt plaintext in parallel, you need to send blocks in specific order to get the ciphertext correct for immediate parallel decryption:

Nonce3 | Enc_3(Enc_2(Nonce1-padded)) |

Enc_3(Enc_2(CT1)) | Enc_3(Enc_2(CT2)) | ... | Enc_3(Enc_2(CTN-padded)) |

Enc_3(Enc_2(TAG1)) | Enc_2(TAG3)

Because of the position of nonces, you can begin transmitting the message immediately, you do not need to wait for any future block to process a prior block in the stream. You can also start decryption immediately, since the nonce for the outer layer is the first part of the message. You must authenticate both layers for complete integrity, but you may be able to authenticate the inner layer first.

There are ways to accelerate the whole thing, but if you are using FIPS modules you cannot do that. You may however be able to use the inherent parallel decoding of the module to encrypt and decrypt as fast as possible, that depends on how modular your program is, and if you are locking to memory or disk, and how much resources you have. Even though GCM can be decrypted several blocks at a time, the module may not unlock the message until it completes authentication of the whole message, but if you can decrypt the outer layer in memory, then the middle, then the inner layer to disk, it will be quite fast. Keeping all keys 128-bits long will also make things faster, up to 40% faster than 256-bit keys, or 24% faster with just the first layer 256-bit.