Research Notes: AES-GMAC-CTR (SIV)

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):