Research Notes: AES-GMAC-CTR (SIV)

This post is for cryptography geeks who are interested in what we’re doing to improve ZeroTier’s security and performance in version 2.0.

Disclaimer: these are research notes, not a final design, and you shouldn’t copy this design into a production cryptosystem as it has not yet received sufficient review.

In our previous post on ZeroTier 2.0 cryptography we discussed ephemeral keys for forward secrecy and hardening the standard AES-GCM authenticated encryption mode against nonce re-use. In the latter case we proposed a design and solicited comments. We received a few, and this post describes an updated design informed by their feedback.

A Bit of Review

AES-GCM is what’s known as an authenticated encryption mode. It combines a cipher (AES in CTR mode) with a message authentication code generated by an algorithm called GMAC. AES-GCM is fast, secure (if used properly), and standard. Authenticated means it protects both the privacy and the integrity of messages. If a message’s encrypted data is modified in transit, AES-GCM will detect this on decryption so the altered message can be discarded.

Authentication is really important. It prevents a whole host of attacks including chosen ciphertext and “oracle” attacks that are beyond the scope of this post. In ZeroTier authenticated encryption is how your node verifies the identities of its peers. Without it someone could forge bogus messages from devices on your network. Even with encryption they could probe or launch denial of service attacks.

Using GCM Correctly

Each invocation of AES-GCM must be supplied with two things: a message to encrypt and an initialization vector or “nonce.” A nonce is cryptography jargon for a “number used once.”

Invoking AES-GCM for two different messages but with the same key and nonce is very bad. Since AES-GCM encrypts the message by XORing it with the output of AES-CTR, a duplicate nonce will result in identical AES-CTR output. This allows the two messages to be decrypted by XORing their ciphertext (since XOR is commutative). Duplication of a nonce also allows GCM itself to be attacked.

Using AES-GCM properly therefore requires that steps be taken to make sure a nonce is never repeated. There are three strategies, none of which is mutually exclusive: use a large nonce, change the key frequently, or negotiate a starting point for the nonce between both sides and increment it for each message to minimize the probability of duplication.

Unfortunately ZeroTier’s fundamental nature makes this harder than it would be in other types of systems that use reliable transport modes like TCP or maintain a lot of state.

ZeroTier is a mostly stateless distributed system. That makes the third strategy of persisted and negotiated nonces tough to implement securely and reliably. Version 2.0 will indeed change encryption keys often, but this will be done in a “lazy” fashion that could in theory fail. Permanent keys will still be used for control traffic as well as for reliability and quick-start reasons. Using a large nonce is possible but would add protocol overhead, and we intend ZeroTier to be a very low-overhead high performance protocol.

SIV Modes

We are by no means the first people to identify this “sudden death” aspect of AES-GCM (and many other authenticated cipher modes) as a weak point that should be strengthened. Since AES-GCM was standardized a number of alternatives have been proposed. The most promising are known as SIV modes for Synthetic Initialization Vector.

SIV modes work by using a message IV and the message plaintext to compute a “synthetic” IV that is both IV and message dependent. This content dependent synthetic IV is then used as the nonce for encryption. AES-SIV and AES-GCM-SIV are two SIV variants built from AES.

Since SIV modes make the encryption IV/nonce content dependent, two different messages with the same message IV will still result in different AES-CTR XOR streams. XORing their ciphertexts no longer accomplishes anything.

These modes do have one unavoidable but in most applications minor weakness: if you encrypt two identical messages with the same IV the result will be two absolutely identical encrypted messages. This will reveal to an observer the fact that a message was duplicated, but otherwise nothing bad happens.

Our Proposed SIV Mode: AES-GMAC-CTR

So use AES-GCM-SIV and we’re done, right?

Unfortunately we have clients with big pockets that want ZeroTier to eventually be able to pass FIPS and/or NSA certification.

FIPS (specifically the FIPS-140 stuff) is a bunch of standards and requirements for (USA) federally certifiable data encryption systems. Many private companies require FIPS certification too since “nobody ever got fired” for using FIPS certified encryption.

The SIV modes are not NIST, FIPS, or NSA certified.

This led us to ask whether we might be able to build something with the nonce reuse resistance characteristics of AES-SIV out of entirely FIPS compliant cryptographic primitives. Our previous post proposed one method, but a crypto.stackexchange user calling themselves Squeamish Ossifrage pointed out that our mode was hard to prove secure. Instead he suggested something almost identical to AES-SIV but using GMAC instead of CMAC for performance reasons.

We took his idea and made minor modifications to fit it into the field sizes and other constraints of the existing ZeroTier protocol and packet format. We call our mode AES-GMAC-CTR as it uses GMAC (a FIPS certified mode) to construct a synthetic IV in a manner similar to AES-GCM-SIV and then uses AES-CTR (also FIPS) to encrypt messages. GMAC is also used for authentication.

Encryption in our ZeroTier-tuned AES-GMAC-CTR looks like this (NOTE: see the bottom of this post for an updated version, but this will be kept as it was in the original post):

Inputs:

IV byte[8]  : 64-bit message IV, sent with message
D byte      : 1 if destination address > source, 0 otherwise
M byte[]    : message plaintext
K1 byte[32] : AES-256 key for authentication
K2 byte[32] : AES-256 key for encryption

Outputs:

IV byte[8]  : 64-bit message IV, same as input
TAG byte[8] : 64-bit authentication tag
C byte[]    : message ciphertext

Algorithm:

(1) Extend the 64-bit message IV to 96 bits by adding the direction byte and a 24-bit unsigned message length.

MIV byte[12] = IV | D | len(M) as 24-bit unsigned int

(2) Compute 128-bit GMAC of message plaintext using MIV and the first of two AES keys, then encrypt it (ECB mode, one block) to prevent GMAC from being attacked if the IV is duplicated. Only the first 8 bytes of this final result are used.

TAG byte[8] = AES[K1](GMAC[K1](MIV,M))[0..8]

(3) Construct synthetic IV for AES-CTR from 64-bit TAG and 96-bit MIV and then encrypt (ECB mode, one block) with both AES keys.

SIV byte[16] =
  AES[K2](AES[K1](
    TAG[0..4] | (TAG[4..8] XOR MIV[0..4]) | MIV[4..12]
  ))

(4) Perform AES-CTR encryption

C byte[] = AES-CTR[K2](SIV,M)

Decryption is basically 1, 3, 4, 2, and then compare TAG with the authentication tag contained in the message and drop the message if they are not equal.

The output of GMAC is subsequently encrypted as a single AES block because as our pseudonymous crypto.stackexchange contributor pointed out GMAC alone is not an opaque cryptographic pseudorandom function. A duplicated nonce can allow GMAC itself to be attacked. This step mitigates this vulnerability. (We’re a bit puzzled as to why GMAC wasn’t designed that way. Performance?)

The use of a different AES key for encryption than for authentication is a precautionary measure to make sure an attacker can’t collect message IVs and authentication tags and somehow use these to say something about AES-CTR’s IV or key stream.

The synthetic IV for AES-CTR is encrypted with both AES keys to mix bits and also make the CTR IV itself secret. This is a paranoia / defense in depth addition that may not strictly be necessary, but it’s almost free so why not?

Lastly note that MAC-then-encrypt, while sometimes discouraged, is only really an issue if padding oracle attacks are possible such as in the CBC mode. This is not an issue with CTR which requires no padding. We also store the authentication tag in a specific field and authenticate the length as well as the message data, preventing the MAC from being altered by appending data to the message.

Discussion

Ignoring the SIV aspect of this construction, its security should be no worse than AES-GCM(MIV,M) with 64-bit authentication tags. GCM is just GMAC and AES-CTR performed in one pass.

If a nonce is repeated for two different messages, the actual CTR IV remains unique (within the 2^64 bounds of the authentication tag) and thus CTR mode is not compromised. Encryption of the GMAC tag also prevents GMAC itself from being attacked.

A duplicated nonce with an identical message results in identical output, revealing message duplication (like other SIV modes) but nothing more.

The only scenario where an attack is possible is if a nonce is duplicated for two different messages that also result in a 64-bit authentication tag collision when AES[K1](GMAC[K1](MIV,M))[0..8] is computed for both.

Using a bit of Python code to compute birthday attack probabilities and stipulating that we want a birthday attack probability of no more than 0.000001% (p=10^-8), we can send about 607,400 messages before an IV collision occurs with this probability (ignoring the use of packet size and direction to extend it to 96 bits) and the same number for authentication tags. Multiplying these we find that we need about 369 billion messages to reach this probability for both IV and authentication tag collision. Using ZeroTier’s default MTU of 2800 that would be around an exabyte of data transferred.

Remember that we will re-key every two minutes by default, so you’d have to be transferring data at over 10 terabytes per second to rack up an 0.000001% chance of a combined IV/tag collision for a given ephemeral key. 10 terabytes per second is about 8000gbps or 200 bonded 40gbps lines.

We hope this math is right. If it’s not, let us know!

Furthermore since we encrypt GMAC’s output we prevent GCM itself from being attacked, all the attacker would earn for all their effort is a lone pair of compromised packets.

The performance of this construction is excellent. Using AES-NI hardware acceleration our implementation clocks 2.1 gigabytes per second per core on a 2.9ghz Intel Core i7. That means a quad-core ~2.9ghz x64 desktop class chip with AES-NI should be able to easily handle ~40gbps of network traffic in one direction or ~20gbps full duplex.

This design is still not set in stone. If you see a problem or can think of a way to further harden it, please let us know. See threads on Reddit and Hacker News.

Update #1: User rosulek on Reddit points out that it’s good practice to avoid using the same key for different operations in a construction even if there is no obvious danger. Instead of using two keys, we might consider using four: K1 for GMAC-AES, K2 for AES-ECB(GMAC-AES), K3 for AES-ECB(CTR IV), K4 for AES-CTR. The performance impact is undetectable in a benchmark, so if it’s considered good practice why not?

Update #2: Based on a bit more feedback and research we’ve decided it’s best to use four keys. These could be derived from a master using a KDF (key derivation function). The overhead is not significant and this avoids the use of the same key for more than one purpose. We also got rid of the double ECB encrypt of the CTR IV in favor of using a role-specific key (K3).

Inputs:

IV byte[8]  : 64-bit message IV, sent with message
D byte      : 1 if destination address > source, 0 otherwise
M byte[]    : message plaintext
K1 byte[32] : AES-256 key for authentication
K2 byte[32] : AES-256 key for authentication keyed hashing
K3 byte[32] : AES-256 key for CTR IV keyed hashing
K4 byte[32] : AES-256 key for encryption

Outputs:

IV byte[8]  : 64-bit message IV, same as input
TAG byte[8] : 64-bit authentication tag
C byte[]    : message ciphertext

Algorithm:

(1) Extend the 64-bit message IV to 96 bits by adding the direction byte and a 24-bit unsigned message length.

MIV byte[12] = IV | D | len(M) as 24-bit unsigned int

(2) Compute 128-bit GMAC of message plaintext using MIV (96-bit extended IV) with one key for GMAC and another for AES-ECB keyed hashing. Only the first 8 bytes of this final result are used.

TAG byte[8] = AES[K2]( GMAC[K1](MIV,M) )[0..8]

(3) Construct synthetic IV for AES-CTR from 64-bit TAG and MIV and then encrypt with AES-ECB (keyed hash).

SIV byte[16] = AES[K3]( TAG | MIV[0..4] | (MIV[4..8] XOR MIV[8..12]) )

(4) Perform AES-CTR encryption

C byte[] = AES-CTR[K4](SIV,M)