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

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.

• Have you seen the AES-GCM-SIV spec? Aug 19, 2019 at 15:55
• I've looked at it a bit. It looks nice but as I said you can't get AES-GCM-SIV FIPS certified. I don't personally care about FIPS but we have some customers that would like to have a FIPS build that uses certified cryptographic modules. Yes I know FIPS often mandates crappier crypto, but corporate/government bureaucracy. I'm trying to think of a way to offer superior security while still being FIPS-compliant-able. Aug 19, 2019 at 15:56
• What matters for security is not whether you can't see how to break it. What matters for security is whether you have confidence that nobody can break it, not even people who are a lot smarter than you are. That's why it's important to show that if someone had a way to break it, then they would have a way to break AES or HMAC-SHA256 or anything else that has had enough decades of serious cryptanalysis put into it that we're pretty sure nobody can break it. Aug 23, 2019 at 15:23
• Yes, I agree, which is why I'm soliciting input as to whether there is any way to break the above without breaking AES. To get a you must break AES. To get c (inner ciphertext) you must break AES. XORing AES-ECB blocks doesn't do anything (not an XOR OTP). If you do manage to strip this off, you're left with AES-GCM which requires you to break AES. But I am not a Real Cryptographer, so I'm soliciting comments. I think my skill is wizard's apprentice, not wizard. Aug 23, 2019 at 15:24
• That's not usually a good question to ask to get serious attention from cryptanalysts. It's much cheaper and safer to start with designs that are easy to prove theorems about, than to ask cryptanalysts to find new theorems about novel designs. That's why I started from two well-established theorems in the literature—PRF security of a cascade $F_{G_k(i)}(j)$, and DAE security of SIV $H_k(m) \mathbin\| E_k(H_k(m), m)$—and picked the most obvious components available to you that would confidently provide security. (I didn't worry about the cost because you didn't specify a budget.) Aug 23, 2019 at 15:29

• 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!

• I haven't decided whether to go ahead and use this scheme because re-keying makes the probability low, but I am definitely going to do more research and debate the merits of enlarging my packets by at least 64 bits. You get the bounty for a good detailed series of responses. Thank you!!! Aug 23, 2019 at 16:29
• BTW... what happens if I do AES-ECB on the ciphertext and use a counter XORed with each ECB plaintext block? It seems like this would block the chosen plaintext distinguisher attack you describe above. Anyway I'll award the bounty once Stack Exchange lets me... there's some kind of time delay. Aug 23, 2019 at 16:31
• Hmm... what about a faster MAC with your scheme above, like CMAC / OMAC1? en.wikipedia.org/wiki/One-key_MAC Aug 23, 2019 at 20:40
• @AdamIerymenko I don't understand the question. What are you asking? Aug 23, 2019 at 20:46
• I'm just wondering if this would work just as well with CMAC, which can be constructed using AES with hardware acceleration and may be significantly faster. It seems as if it would. I am referring to your HMAC based scheme... made a mistake when I said "above." It's in another response. Aug 23, 2019 at 20:47

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.

• The reason for the original hare brained scheme is that in the possibly stateless system they are using, there is no way to keep track of $i$, and thus they are using random nonces, but they are only 64-bits long, so the chance of nonce collision of around 1 in a million after ONLY 4300 messages Aug 23, 2019 at 0:12
• This mistake of "more crypto is better crypto" is very common. It's like saying you want two engines in your dream car and three steering wheels for maneuverability. Aug 23, 2019 at 0:48
• @RichieFrame This scheme reduces from AE security to DAE security if you set $i = 0$ (or otherwise let $i$ repeat)—that is, the worst that will happen if you set $i = 0$ is that the adversary can identify repeated messages. Aug 23, 2019 at 4:16
• Unfortunately I benchmarked just HMAC-SHA256 and HMAC-SHA384 and both are far too slow. I do like your idea though for its simplicity. I'd go with it if HMAC wasn't a dog. I added an "edit #2" to my original post clarifying my approach just in case it's not clear for your benefit and the benefit of others. I feel like maybe some readers have missed the fact that the second encryption pass over the ciphertext uses an ephemeral per-message key. Aug 23, 2019 at 15:04
• One way to think of it is that I'm using AES-GCM in place of HMAC to generate a per-message ephemeral random key and then using that key to encrypt the message again. I'm also encrypting this key with the session key as a single AES-ECB block. I don't think I'm just blindly adding more cowbell. The goal isn't just "MoAR encryption!" but specifically to close the nonce reuse vulnerability in GCM. I use ECB to encrypt the inner ciphertext because it's crazy fast, is not an XOR OTP, and can't reveal structure since the key is ephemeral and the input is ciphertext. Aug 23, 2019 at 15:20

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.

• Sounds like the method I have in mind is generally okay. You're slightly off in a few places but it's not your fault -- you don't understand my exact application. (1) is not an issue since it's encrypting packet by packet and whole packets are always handled, and (2) is not either because you never lose part of a packet only whole packets. I've already done some experiments and found that the performance hit from a second AES (ECB) is minimal, only about 20%. A single x64 core can still push 10gbps traffic. I'll solicit more feedback just to be sure. Might do a blog post with the exact design. Aug 20, 2019 at 14:21
• Last thing I'm unclear about is how strong that second cipher really needs to be. Seems to me that overall difficulty is 2^(2N) where N is its strength in bits for the reason I explained, so a cipher whose strength is only about 64-80 bits would be okay... but I'm not positive about that. I want it to be extremely fast. I'm considering reduced round AES for the mitigation cipher since all it really has to do is make XORing of messages totally useless and make search generally as costly as other methods of breaking crypto. Aug 20, 2019 at 18:01
• @AdamIerymenko using AEC-ECB as the 2nd layer allows you to drop in another FIPS certified module, and have all components of encryption be FIPS compliant. Packet vs stream is irrelevant, you can use a packet counter instead of a message counter. Be very wary about intentionally kneecapping a system component, it creates a weak link that may be exploited in ways you cannot imagine (see Spectre/Meltdown for examples) Aug 20, 2019 at 18:34
• If I understand your suggested scheme right, the way you use ECB in the second layer means that, if two messages differing in some but not all cipher blocks are encrypted with the same nonce, your scheme leaks information about which blocks are the same in both messages and which are not. One way to avoid this would be to derive the AES-ECB key from the GCM tag+nonce; another would be to use CTR mode in the second layer instead, with the initial counter value derived from the encrypted tag + nonce. That might be DAE secure, although I can't prove that off the top of my head. Aug 21, 2019 at 21:00
• @AdamIerymenko The sceme I designed to meet the security requirement has 2 GCM layers, that plus ECB is what makes it XEX, which has provable security properties, and high performance (sequential and parallel encryption and decryption), while being able to use FIPS modules for each layer Aug 22, 2019 at 17:55