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) |
| 245 | 210 | 216 |
| 232 | 215 | 216 |
| 225 | 26 | 230 |
| 232 | 1 | 230 |
| 1 | 231 | 216 |
| 242 | 28 | 216 |
| 264 | 210 | 23 |
| 264 | 215 | 1 |
| 264 | 28 | 28 |
| 248 | 210 | 214 |
| 248 | 28 | 216 |
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 (with adversarial advantage of at most 2-32):
| 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:
- Gueron, A. Langley and Y. Lindell. AES-GCM-SIV: Specification and Analysis. Cryptology ePrint Archive, Report 2017/168, 2017.
The scientific justification behind the AES-GCM-SIV mode of operation appeared in the following papers:
- Gueron and Y. Lindell. GCM-SIV: Full Nonce Misuse-Resistant Authenticated Encryption at Under One Cycle per Byte. In the 22nd ACM CCS, pages 109-119, 2015.
- Gueron and Y. Lindell. Better Bounds for Block Cipher Modes of Operation via Nonce-Based Key Derivation. In the 24th ACM CCS, pages 1019-1036, 2017.
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 in Question 7. We remark that the software implementations tested here were written to be constant-time.
FAQ
- 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.
- 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.
- 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.
- 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.
- How does AES-GCM-SIV compare to AES-SIV in security?
The (distinguishing) advantage in AES-SIV is bounded by B2/2n;where B is the overall number of blocks encrypted, and n 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 248 blocks can be encrypted while maintaining an adversarial advantage of at most 2-32. 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 248 blocks can be encrypted with adversarial advantage of at most 2-32 (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.
- 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.
- 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.
- 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.