Webpage for the AES-GCM-SIV Mode of Operation

Shay Gueron – University of Haifa and AWS
Adam Langley – Google
Yehuda Lindell – Bar-Ilan University

Abstract

AES-GCM-SIV is a fully nonce-misuse resistant authenticated-encryption scheme. Such schemes have the property that both privacy and integrity are preserved, even if nonces are repeated. To be more exact, encryption is a function of a nonce, the plaintext message, and possibly additional authenticated data (typically denoted AAD). In a fully nonce-misuse resistant scheme, if a nonce is misused (i.e., used more than once) then nothing is revealed unless the same message is encrypted multiple times with the same nonce. In such a case, it is possible to see that the same message was encrypted (since encryption is a deterministic function of the nonce and message), but nothing beyond that is revealed. As such, it is highly recommended to use a nonce-misuse resistant scheme in cases that unique nonces cannot be guaranteed.

One may conclude that when using a nonce-misuse resistant scheme it is safe to always use the same nonce. This is not fully accurate, since this allows an adversary to detect repeating messages. Furthermore, AES-GCM-SIV has the property that the security bounds are considerably higher when different nonces are used (even going beyond the birthday bound). Thus, always reusing the same nonce means that the number of encryptions allowed using a single key for AES-GCM-SIV is comparable to that of AES-GCM (authenticated encryption) or AES-SIV (a different nonce-misuse resistant scheme). In contrast, when the nonce reuse is limited (e.g., occurs as a result of using imperfect randomness, or birthday collisions in the nonce when encrypting a very large number of messages), then the bounds on the number of encryptions are very high.

 

A Figure Description of AES-GCM-SIV

The following diagram provides a high-level overview of the construction. We point out that the formatting of the messages and intermediate values (not detailed in this diagram) are crucial to the security of the scheme.

Usage Bounds

We give some examples of usage bounds for AES-GCM-SIV; for all of these bounds the advantage of the adversary is bounded by 2-32.

Number of different nonces Maximum nonce repetition Maximum message length (in blocks)
232 High – 210 242
248 High – 210 226
264 High – 210 210
232 Medium – 26 250
248 Medium – 26 234
264 Medium – 26 218
232 Low – 23 256
248 Low – 23 240
264 Low – 23 224
1 (fixed nonce) 232 216
1 (fixed nonce) 238 210
1 (fixed nonce) 244 24

 

Note that the overall number of messages is the product of the number of different nonces and maximum nonce repetition. In particular, for a fixed nonce, the maximum nonce repetition is simply the number of different messages overall.

When using random nonces, we obtain the following bounds:

Number of messages Maximum message length (in blocks)
232 229
248 221
264 213

 

Detailed Information

The AES-GCM-SIV specification is available at AES-GCM-SIV spec. A detailed description and discussion of the security of AES-GCM-SIV can be found at:

The scientific justification behind the AES-GCM-SIV mode of operation appeared in the following papers:

Recently, it was shown that AES-GCM-SIV has excellent bounds also in the multi-user setting. This was analyzed in:

  • Bose, V.T. Hoang and S. Tessaro. Revisiting AES-GCM-SIV: Multi-user Security, Faster Key Derivation, and Better Bounds. Manuscript, 2017.

 

Software Implementations

 

Performance

AES-GCM-SIV has excellent performance, and is based on the same fast operations as AES-GCM. We compared AES-GCM-SIV with AES-GCM on the Intel micro-architecture codename Skylake. This architecture includes the AES-NI and CLMUL (technically, called “PCLMULQDQ”) instructions. The performance here is given in cycles per byte (C/B) or (for very short messages) in cycles. The AES-GCM numbers correspond to the highly optimized DecryptSSL (1.0.2k) implementations that includes interleaving of the authenticator hash computation with the AES operations. These numbers do not account for the “Init” step of DecryptSSL (which amounts to about 1,000 additional cycles).

Platform: Intel Skylake

Algorithm Message size Speed
AES-128-GCM encrypt 16 bytes 129 cycles
AES-128-GCM encrypt 1024 bytes 0.84 C/B
AES-128-GCM encrypt 8192 bytes 0.66 C/B
AES-128-GCM decrypt 16 bytes 141 cycles
AES-128-GCM decrypt 1024 bytes 0.79 C/B
AES-128-GCM decrypt 8192 bytes 0.65 C/B
AES-128-GCM-SIV encrypt 16 bytes 257 cycles
AES-128-GCM-SIV encrypt 1024 bytes 1.37 C/B
AES-128-GCM-SIV encrypt 8192 bytes 0.98 C/B
AES-128-GCM-SIV decrypt 16 bytes 358 cycles
AES-128-GCM-SIV decrypt 1024 bytes 1.17 C/B
AES-128-GCM-SIV decrypt 8192 bytes 0.69 C/B
AES-256-GCM encrypt 16 bytes 154 cycles
AES-256-GCM encrypt 1024 bytes 1.1 C/B
AES-256-GCM encrypt 8192 bytes 0.91 C/B
AES-256-GCM decrypt 16 bytes 201 cycles
AES-256-GCM decrypt 1024 bytes 1.05 C/B
AES-256-GCM decrypt 8192 bytes 0.9 C/B
AES-256-GCM-SIV encrypt 16 bytes 306 cycles
AES-256-GCM-SIV encrypt 1024 bytes 1.69 C/B
AES-256-GCM-SIV encrypt 8192 bytes 1.24 C/B
AES-256-GCM-SIV decrypt 16 bytes 445 cycles
AES-256-GCM-SIV decrypt 1024 bytes 1.48 C/B
AES-256-GCM-SIV decrypt 8192 bytes 0.95 C/B

 

Observe that for the encrypt operation for extremely short messages (a single block of 16 bytes) AES-GCM-SIV is about 2 times slower than AES-GCM, and for 1024 and 8192 byte messages AES-GCM-SIV is about 1.5 times slower than AES-GCM (not counting ~1000 cycles for “Init”). In contrast, observe that the decrypt operations cost about the same for AES-GCM and AES-GCM-SIV. The reason is that AES-GCM-SIV encryption must serialize the hash computation and the encryption, which is the inherent cost of achieving nonce misuse resistance.  However, AES-GCM-SIV decryption can interleave the CTR decryption and the computation of the hash (over the plaintext), exactly as can be done with AES-GCM.

The above results are on a platform with the AES-NI and CLMUL instructions. In order to demonstrate performance on older platforms without these instructions, we tested AES-GCM-SIV versus AES-GCM on the ARMv7. This architecture does not have the AES-NI and CLMUL instructions. The results appear in the table below.

Platform: ARMv7 (1.5GHz Krait 300)

Algorithm Message size Speed
AES-128-GCM encrypt 16 bytes 14 MB/s
AES-128-GCM encrypt 1350 bytes 52.3 MB/s
AES-128-GCM encrypt 8192 bytes 55.4 MB/s
AES-128-GCM-SIV encrypt 16 bytes 6.3 MB/s
AES-128-GCM-SIV encrypt 1350 bytes 38.1 MB/s
AES-128-GCM-SIV encrypt 8192 bytes 40.2 MB/s
AES-128-GCM-SIV decrypt 16 bytes 6.0 MB/s
AES-128-GCM-SIV decrypt 1350 bytes 37.7 MB/s
AES-128-GCM-SIV decrypt 8192 bytes 39.7 MB/s
AES-256-GCM encrypt 16 bytes 12.7 MB/s
AES-256-GCM encrypt 1350 bytes 42.2 MB/s
AES-256-GCM encrypt 8192 bytes 45.0 MB/s
AES-256-GCM-SIV encrypt 16 bytes 4.4 MB/s
AES-256-GCM-SIV encrypt 1350 bytes 30.9 MB/s
AES-256-GCM-SIV encrypt 8192 bytes 33.3 MB/s
AES-256-GCM-SIV decrypt 16 bytes 4.3 MB/s
AES-256-GCM-SIV decrypt 1350 bytes 30.9 MB/s
AES-256-GCM-SIV decrypt 8192 bytes 33.1 MB/s

 

Observe that for the encrypt operation for extremely short messages (a single block of 16 bytes) AES-GCM-SIV is 2.2 times slower than AES-GCM (x2.9  for AES-256), and for 1350 and 8192 byte messages AES-GCM-SIV is about 1.4 times slower than AES-GCM (x1.35 for AES-256). We remark that the implementation here, without AES-NI, does not use the interleaving optimization of the authenticator hash computation with the AES operations. For this reason, the AES-GCM-SIV decrypt operation costs more AES-GCM decrypt/encrypt, unlike the results shown for Intel Skylake. We remark that the software implementations tested here were written to be constant-time.

 

FAQ

  1. What are the security bounds for AES-GCM-SIV and why can’t I always use the same nonce?

As we showed in the table of usage bounds above, the security bounds for AES-GCM-SIV are very strong and it’s possible to encrypt a very large number of messages, even with repeating nonces. However, as can be seen in the table, the exact bounds do depend on the number of nonce repetitions.

  1. Does AES-GCM-SIV only guarantee a weaker variant of “fully nonce-misuse resistant”?

AES-GCM-SIV achieves the strongest level of nonce-misuse resistance. There are two standard notions: in the weaker notion, when the same nonce is repeated with messages with the same prefix then the fact of this repetition is revealed. However, in the stronger notion that is achieved by AES-GCM-SIV, nothing is revealed unless the exact same nonce is used to encrypt the exact same message twice. In this case, the only information that is revealed is that the same message was encrypted twice (and this is an inevitable property of a deterministic algorithm).

We stress that the dependence of the bound on the amount of nonce misuse is not a weakness of the scheme, but a strength. In fact, when using the same nonce always, the bounds achieved by AES-GCM-SIV are similar to previous nonce-misuse resistant schemes (like AES-SIV). However, AES-GCM-SIV has the feature that the bounds are far better than others when nonces don’t repeat too much. This is due to the nonce-based key-derivation at the beginning of every encryption.

  1. What is the difference between POLYVAL and GHASH and why did you make this change to AES-GCM?

When designing AES-GCM-SIV, we decided use POLYVAL instead of GHASH (which is the hash function use in AES-GCM). The reason for this change is consistency with the order of bits inside bytes, which is reversed in AES-GCM (it is not consistent with the bytes of AES as a cipher that operates, by definition, on a state of 16 bytes). After interpreting AES-GCM in an algebraic way, we saw that GHASH is defined by a sequence of operations of the type a*b*x^{-127}, in some finite field. For AES-GCM where a is fixed (it is the hash key) we can write this operation as (a*x)*(b*x)^{-128}. Since a*x is actually H*x, this means that an extra multiplication is needed. By contrast, POLYVAL is defined directly and naturally as a*b*x^{-128}, which is actually the operation that can be computed efficiently in the field.

  1. How can I implement GHASH using POLYVAL as a black-box?

A formula for carrying out this transition appears in the papers and in the AES-GCM-SIV specification. Also, this was the first implementation in BoringSSL and can be found here.

  1. How does AES-GCM-SIV compare to AES-SIV in security?

The (distinguishing) advantage in AES-SIV is bounded by  where  is the overall number of blocks encrypted, and  is the block length (See Section 5 of: P. Rogaway and T. Shrimpton. A Provable-Security Treatment of the Key-Wrap Problem. In EUROCRYPT 2006.) Thus, for AES, a total number of  blocks can be encrypted while maintaining an adversarial advantage of at most . Looking at the table for AES-GCM-SIV above, you can see that when the same nonce is always used, the bound is the same, and at most  blocks can be encrypted with adversarial advantage of at most  (the number of blocks is obtained by multiplying the number of messages with the message length). However, when different nonces are used, AES-SIV still has this bound, whereas AES-GCM-SIV has much greater bounds. This is due to the nonce-based key derivation method used in AES-GCM-SIV.

  1. How does AES-GCM-SIV compare to AES-SIV in performance when AES-NI and PCLMULQDQ are not available?

AES-GCM-SIV is targeted for platforms with AES-NI and CLMUL. In all such platforms, AES-GCM-SIV way outperforms AES-SIV since all operations are parallelizable (this is in contrast to CMAC used in AES-SIV that is inherently sequential).

When AES-NI and CLMUL are not available (e.g., on old platforms), then AES-GCM-SIV still outperforms AES-SIV (since each incremental POLYHASH computation is cheaper than a full AES computation). However, on such platforms, other alternatives (based on ChaCha20, for example) may perform better.

  1. Why wasn’t AES-GCM-SIV submitted to the CAESAR competition?

AES-GCM-SIV was developed after CAESAR was underway so we couldn’t send it.

  1. How did you choose the key derivation method and is this the best choice?

There are a number of options for good key derivation. Our aim in choosing the KDF was one that would enable 264 key derivations with maximum distinguishing advantage of 2-32. The key derivation is efficient, as it can be pipelined using our optimized method for pipelining the AES key schedule. Note that the KDF requires a key expansion followed by a few encryptions, and the overhead becomes relatively negligible for sufficiently long messages.

In principle, other KDFs with good bounds could also be used (like XORing different PRP outputs), and the results would be similar.