Tech-invite3GPPspaceIETF RFCsSIP
929190898887868584838281807978777675747372717069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232221201918171615141312111009080706050403020100
in Index   Prev   Next

RFC 8452

AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption

Pages: 42
Informational
Errata
Part 1 of 2 – Pages 1 to 19
None   None   Next

Top   ToC   RFC8452 - Page 1
Internet Research Task Force (IRTF)                            S. Gueron
Request for Comments: 8452                University of Haifa and Amazon
Category: Informational                                       A. Langley
ISSN: 2070-1721                                               Google LLC
                                                              Y. Lindell
                                    Bar-Ilan University and Unbound Tech
                                                              April 2019


      AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption

Abstract

This memo specifies two authenticated encryption algorithms that are nonce misuse resistant -- that is, they do not fail catastrophically if a nonce is repeated. This document is the product of the Crypto Forum Research Group. Status of This Memo This document is not an Internet Standards Track specification; it is published for informational purposes. This document is a product of the Internet Research Task Force (IRTF). The IRTF publishes the results of Internet-related research and development activities. These results might not be suitable for deployment. This RFC represents the consensus of the Crypto Forum Research Group of the Internet Research Task Force (IRTF). Documents approved for publication by the IRSG are not candidates for any level of Internet Standard; see Section 2 of RFC 7841. Information about the current status of this document, any errata, and how to provide feedback on it may be obtained at https://www.rfc-editor.org/info/rfc8452. Copyright Notice Copyright (c) 2019 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document.
Top   ToC   RFC8452 - Page 2

Table of Contents

1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 2. Requirements Language . . . . . . . . . . . . . . . . . . . . 3 3. POLYVAL . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 4. Encryption . . . . . . . . . . . . . . . . . . . . . . . . . 4 5. Decryption . . . . . . . . . . . . . . . . . . . . . . . . . 7 6. AEADs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 7. Field Operation Examples . . . . . . . . . . . . . . . . . . 10 8. Worked Example . . . . . . . . . . . . . . . . . . . . . . . 10 9. Security Considerations . . . . . . . . . . . . . . . . . . . 11 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 14 11.1. Normative References . . . . . . . . . . . . . . . . . . 14 11.2. Informative References . . . . . . . . . . . . . . . . . 15 Appendix A. The Relationship between POLYVAL and GHASH . . . . . 17 Appendix B. Additional Comparisons with AES-GCM . . . . . . . . 19 Appendix C. Test Vectors . . . . . . . . . . . . . . . . . . . . 20 C.1. AEAD_AES_128_GCM_SIV . . . . . . . . . . . . . . . . . . 20 C.2. AEAD_AES_256_GCM_SIV . . . . . . . . . . . . . . . . . . 30 C.3. Counter Wrap Tests . . . . . . . . . . . . . . . . . . . 41 Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . 42 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 42

1. Introduction

The concept of Authenticated Encryption with Additional Data (AEAD) [RFC5116] couples confidentiality and integrity in a single operation, avoiding the risks of the previously common practice of using ad hoc constructions of block-cipher and hash primitives. The most popular AEAD, AES-GCM [GCM], is seeing widespread use due to its attractive performance. However, some AEADs (including AES-GCM) suffer catastrophic failures of confidentiality and/or integrity when two distinct messages are encrypted with the same key and nonce. While the requirements for AEADs specify that the pair of (key, nonce) shall only ever be used once, and thus prohibit this, this is a worry in practice. Nonce misuse-resistant AEADs do not suffer from this problem. For this class of AEADs, encrypting two messages with the same nonce only discloses whether the messages were equal or not. This is the minimum amount of information that a deterministic algorithm can leak in this situation. This memo specifies two nonce misuse-resistant AEADs: AEAD_AES_128_GCM_SIV and AEAD_AES_256_GCM_SIV. These AEADs are designed to be able to take advantage of existing hardware support
Top   ToC   RFC8452 - Page 3
   for AES-GCM and can decrypt within 5% of the speed of AES-GCM (for
   multikilobyte messages).  Encryption is, perforce, slower than
   AES-GCM, because two passes are required in order to achieve that
   nonce misuse-resistance property.  However, measurements suggest that
   it can still run at two-thirds of the speed of AES-GCM.

   We suggest that these AEADs be considered in any situation where
   nonce uniqueness cannot be guaranteed.  This includes situations
   where there is no stateful counter or where such state cannot be
   guaranteed, as when multiple encryptors use the same key.  As
   discussed in Section 9, it is RECOMMENDED to use this scheme with
   randomly chosen nonces.

   This document represents the consensus of the Crypto Forum Research
   Group (CFRG).

2. Requirements Language

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.

3. POLYVAL

The GCM-SIV construction is similar to GCM: the block cipher is used in counter mode to encrypt the plaintext, and a polynomial authenticator is used to provide integrity. The authenticator in GCM-SIV is called POLYVAL. POLYVAL, like GHASH (the authenticator in AES-GCM; see [GCM], Section 6.4), operates in a binary field of size 2^128. The field is defined by the irreducible polynomial x^128 + x^127 + x^126 + x^121 + 1. The sum of any two elements in the field is the result of XORing them. The product of any two elements is calculated using standard (binary) polynomial multiplication followed by reduction modulo the irreducible polynomial. We define another binary operation on elements of the field: dot(a, b), where dot(a, b) = a * b * x^-128. The value of the field element x^-128 is equal to x^127 + x^124 + x^121 + x^114 + 1. The result of this multiplication, dot(a, b), is another field element.
Top   ToC   RFC8452 - Page 4
   Polynomials in this field are converted to and from 128-bit strings
   by taking the least significant bit of the first byte to be the
   coefficient of x^0, the most significant bit of the first byte to be
   the coefficient of x^7, and so on, until the most significant bit of
   the last byte is the coefficient of x^127.

   POLYVAL takes a field element, H, and a series of field elements
   X_1, ..., X_s.  Its result is S_s, where S is defined by the
   iteration S_0 = 0; S_j = dot(S_{j-1} + X_j, H), for j = 1..s.

   We note that POLYVAL(H, X_1, X_2, ...) is equal to
   ByteReverse(GHASH(ByteReverse(H) * x, ByteReverse(X_1),
   ByteReverse(X_2), ...)), where ByteReverse is a function that
   reverses the order of 16 bytes.  See Appendix A for a more detailed
   explanation.

4. Encryption

AES-GCM-SIV encryption takes a 16- or 32-byte key-generating key, a 96-bit nonce, and plaintext and additional data byte strings of variable length. It outputs an authenticated ciphertext that will be 16 bytes longer than the plaintext. Both encryption and decryption are only defined on inputs that are a whole number of bytes. If the key-generating key is 16 bytes long, then AES-128 is used throughout. Otherwise, AES-256 is used throughout. The first step of encryption is to generate per-nonce, message- authentication and message-encryption keys. The message- authentication key is 128 bit, and the message-encryption key is either 128 (for AES-128) or 256 bit (for AES-256). These keys are generated by encrypting a series of plaintext blocks that contain a 32-bit, little-endian counter followed by the nonce, and then discarding the second half of the resulting ciphertext. In the AES-128 case, 128 + 128 = 256 bits of key material need to be generated, and, since encrypting each block yields 64 bits after discarding half, four blocks need to be encrypted. The counter values for these blocks are 0, 1, 2, and 3. For AES-256, six blocks are needed in total, with counter values 0 through 5 (inclusive).
Top   ToC   RFC8452 - Page 5
   In pseudocode form, where "++" indicates concatenation and "x[:8]"
   indicates taking only the first eight bytes from x:

   func derive_keys(key_generating_key, nonce) {
     message_authentication_key =
         AES(key = key_generating_key,
             block = little_endian_uint32(0) ++ nonce)[:8] ++
         AES(key = key_generating_key,
             block = little_endian_uint32(1) ++ nonce)[:8]
     message_encryption_key =
         AES(key = key_generating_key,
             block = little_endian_uint32(2) ++ nonce)[:8] ++
         AES(key = key_generating_key,
             block = little_endian_uint32(3) ++ nonce)[:8]

     if bytelen(key_generating_key) == 32 {
       message_encryption_key ++=
           AES(key = key_generating_key,
               block = little_endian_uint32(4) ++ nonce)[:8] ++
           AES(key = key_generating_key,
               block = little_endian_uint32(5) ++ nonce)[:8]
     }

     return message_authentication_key, message_encryption_key
   }

   Define the "length block" as a 16-byte value that is the
   concatenation of the 64-bit, little-endian encodings of
   bytelen(additional_data) * 8 and bytelen(plaintext) * 8.  Pad the
   plaintext and additional data with zeros until they are each a
   multiple of 16 bytes, the AES block size.  Then X_1, X_2, ... (the
   series of field elements that are inputs to POLYVAL) are the
   concatenation of the padded additional data, the padded plaintext,
   and the length block.

   Calculate S_s = POLYVAL(message-authentication-key, X_1, X_2, ...).
   XOR the first twelve bytes of S_s with the nonce and clear the most
   significant bit of the last byte.  Encrypt the result with AES using
   the message-encryption key to produce the tag.

   (It's worth highlighting a contrast with AES-GCM here: AES-GCM
   authenticates the encoded additional data and ciphertext, while
   AES-GCM-SIV authenticates the encoded additional data and plaintext.)

   The encrypted plaintext is produced by using AES, with the message-
   encryption key, in counter mode (see [SP800-38A], Section 6.5) on the
   unpadded plaintext.  The initial counter block is the tag with the
   most significant bit of the last byte set to one.  The counter
Top   ToC   RFC8452 - Page 6
   advances by incrementing the first 32 bits interpreted as an
   unsigned, little-endian integer, wrapping at 2^32.  The result of the
   encryption is the encrypted plaintext (truncated to the length of the
   plaintext), followed by the tag.

   In pseudocode form, the encryption process can be expressed as:

   func right_pad_to_multiple_of_16_bytes(input) {
     while (bytelen(input) % 16 != 0) {
       input = input ++ "\x00"
     }
     return input
   }

   func AES_CTR(key, initial_counter_block, in) {
     block = initial_counter_block

     output = ""
     while bytelen(in) > 0 {
       keystream_block = AES(key = key, block = block)
       block[0:4] = little_endian_uint32(
           read_little_endian_uint32(block[0:4]) + 1)

       todo = min(bytelen(in), bytelen(keystream_block)
       for j = 0; j < todo; j++ {
         output = output ++ (keystream_block[j] ^ in[j])
       }

       in = in[todo:]
     }

     return output
   }

   func encrypt(key_generating_key,
                nonce,
                plaintext,
                additional_data) {
     if bytelen(plaintext) > 2^36 {
       fail()
     }
     if bytelen(additional_data) > 2^36 {
       fail()
     }

     message_encryption_key, message_authentication_key =
         derive_keys(key_generating_key, nonce)
Top   ToC   RFC8452 - Page 7
     length_block =
         little_endian_uint64(bytelen(additional_data) * 8) ++
         little_endian_uint64(bytelen(plaintext) * 8)
     padded_plaintext = right_pad_to_multiple_of_16_bytes(plaintext)
     padded_ad = right_pad_to_multiple_of_16_bytes(additional_data)
     S_s = POLYVAL(key = message_authentication_key,
                   input = padded_ad ++ padded_plaintext ++
                           length_block)
     for i = 0; i < 12; i++ {
       S_s[i] ^= nonce[i]
     }
     S_s[15] &= 0x7f
     tag = AES(key = message_encryption_key, block = S_s)

     counter_block = tag
     counter_block[15] |= 0x80
     return AES_CTR(key = message_encryption_key,
                    initial_counter_block = counter_block,
                    in = plaintext) ++
            tag
   }

5. Decryption

Decryption takes a 16- or 32-byte key-generating key, a 96-bit nonce, and ciphertext and additional data byte strings of variable length. It either fails or outputs a plaintext that is 16 bytes shorter than the ciphertext. To decrypt an AES-GCM-SIV ciphertext, first derive the message- encryption and message-authentication keys in the same manner as when encrypting. If the ciphertext is less than 16 bytes or more than 2^36 + 16 bytes, then fail. Otherwise, split the input into the encrypted plaintext and a 16-byte tag. Decrypt the encrypted plaintext with the message- encryption key in counter mode, where the initial counter block is the tag with the most significant bit of the last byte set to one. Advance the counter for each block in the same way as when encrypting. At this point, the plaintext is unauthenticated and MUST NOT be output until the following tag confirmation is complete: Pad the additional data and plaintext with zeros until they are each a multiple of 16 bytes, the AES block size. Calculate the length block and X_1, X_2, ... as above and compute S_s = POLYVAL(message-authentication-key, X_1, X_2, ...)
Top   ToC   RFC8452 - Page 8
   Compute the expected tag by XORing S_s and the nonce, clearing the
   most significant bit of the last byte and encrypting with the
   message-encryption key.  Compare the provided and expected tag values
   in constant time.  Fail the decryption if they do not match (and do
   not release the plaintext); otherwise, return the plaintext.

   In pseudocode form, the decryption process can be expressed as:
Top   ToC   RFC8452 - Page 9
   func decrypt(key_generating_key,
                nonce,
                ciphertext,
                additional_data) {
     if bytelen(ciphertext) < 16 || bytelen(ciphertext) > 2^36 + 16 {
       fail()
     }
     if bytelen(additional_data) > 2^36 {
       fail()
     }

     message_encryption_key, message_authentication_key =
         derive_keys(key_generating_key, nonce)

     tag = ciphertext[bytelen(ciphertext)-16:]

     counter_block = tag
     counter_block[15] |= 0x80
     plaintext = AES_CTR(key = message_encryption_key,
                         initial_counter_block = counter_block,
                         in = ciphertext[:bytelen(ciphertext)-16])

     length_block =
         little_endian_uint64(bytelen(additional_data) * 8) ++
         little_endian_uint64(bytelen(plaintext) * 8)
     padded_plaintext = right_pad_to_multiple_of_16_bytes(plaintext)
     padded_ad = right_pad_to_multiple_of_16_bytes(additional_data)
     S_s = POLYVAL(key = message_authentication_key,
                   input = padded_ad ++ padded_plaintext ++
                           length_block)
     for i = 0; i < 12; i++ {
       S_s[i] ^= nonce[i]
     }
     S_s[15] &= 0x7f
     expected_tag = AES(key = message_encryption_key, block = S_s)

     xor_sum = 0
     for i := 0; i < bytelen(expected_tag); i++ {
       xor_sum |= expected_tag[i] ^ tag[i]
     }

     if xor_sum != 0 {
       fail()
     }

     return plaintext
   }
Top   ToC   RFC8452 - Page 10

6. AEADs

We define two AEADs, in the format of RFC 5116, that use AES-GCM-SIV: AEAD_AES_128_GCM_SIV and AEAD_AES_256_GCM_SIV. They differ only in the size of the AES key used. The key input to these AEADs becomes the key-generating key. Thus, AEAD_AES_128_GCM_SIV takes a 16-byte key and AEAD_AES_256_GCM_SIV takes a 32-byte key. The parameters for AEAD_AES_128_GCM_SIV are then as follows: K_LEN is 16, P_MAX is 2^36, A_MAX is 2^36, N_MIN and N_MAX are 12, and C_MAX is 2^36 + 16. The parameters for AEAD_AES_256_GCM_SIV differ only in the key size: K_LEN is 32, P_MAX is 2^36, A_MAX is 2^36, N_MIN and N_MAX are 12, and C_MAX is 2^36 + 16.

7. Field Operation Examples

Polynomials in this document will be written as 16-byte values. For example, the sixteen bytes 01000000000000000000000000000492 would represent the polynomial x^127 + x^124 + x^121 + x^114 + 1, which is also the value of x^-128 in this field. If a = 66e94bd4ef8a2c3b884cfa59ca342b2e and b = ff000000000000000000000000000000, then a + b = 99e94bd4ef8a2c3b884cfa59ca342b2e, a * b = 37856175e9dc9df26ebc6d6171aa0ae9, and dot(a, b) = ebe563401e7e91ea3ad6426b8140c394.

8. Worked Example

Consider the encryption of the plaintext "Hello world" with the additional data "example" under key ee8e1ed9ff2540ae8f2ba9f50bc2f27c using AEAD_AES_128_GCM_SIV. The random nonce that we'll use for this example is 752abad3e0afb5f434dc4310. In order to generate the message-authentication and message- encryption keys, a counter is combined with the nonce to form four blocks. These blocks are encrypted with the key given above: Counter | Nonce Ciphertext 00000000752abad3e0afb5f434dc4310 -> 310728d9911f1f38c40e952ca83d093e 01000000752abad3e0afb5f434dc4310 -> 37b24316c3fab9a046ae90952daa0450 02000000752abad3e0afb5f434dc4310 -> a4c5ae624996327947920b2d2412474b 03000000752abad3e0afb5f434dc4310 -> c100be4d7e2c6edd1efef004305ab1e7
Top   ToC   RFC8452 - Page 11
   The latter halves of the ciphertext blocks are discarded and the
   remaining bytes are concatenated to form the per-message keys.  Thus,
   the message-authentication key is 310728d9911f1f3837b24316c3fab9a0,
   and the message-encryption key is a4c5ae6249963279c100be4d7e2c6edd.

   The length block contains the encoding of the bit lengths of the
   additional data and plaintext, respectively.  The string "example" is
   seven characters, thus 56 bits (or 0x38 in hex).  The string "Hello
   world" is 11 characters, or 88 = 0x58 bits.  Thus, the length block
   is 38000000000000005800000000000000.

   The input to POLYVAL is the padded additional data, padded plaintext,
   and then the length block.  This is 6578616d706c650000000000000000004
   8656c6c6f20776f726c64000000000038000000000000005800000000000000,
   based on the ASCII encoding of "example" (6578616d706c65) and "Hello
   world" (48656c6c6f20776f726c64).

   Calling POLYVAL with the message-authentication key and the input
   above results in S_s = ad7fcf0b5169851662672f3c5f95138f.

   Before encrypting, the nonce is XORed in and the most significant bit
   of the last byte is cleared.  This gives
   d85575d8b1c630e256bb6c2c5f95130f, because that bit happened to be one
   previously.  Encrypting with the message-encryption key (using
   AES-128) gives the tag, which is 4fbcdeb7e4793f4a1d7e4faa70100af1.

   In order to form the initial counter block, the most significant bit
   of the last byte of the tag is set to one.  That doesn't result in a
   change in this example.  Encrypting this with the message key (using
   AES-128) gives the first block of the keystream:
   1551f2c1787e81deac9a99f139540ab5.

   The final ciphertext is the result of XORing the plaintext with the
   keystream and appending the tag.  That gives
   5d349ead175ef6b1def6fd4fbcdeb7e4793f4a1d7e4faa70100af1.

9. Security Considerations

AES-GCM-SIV decryption involves first producing an unauthenticated plaintext. This plaintext is vulnerable to manipulation by an attacker; thus, if an implementation released some or all of the plaintext before authenticating it, other parts of a system may process malicious data as if it were authentic. AES-GCM might be less likely to lead implementations to do this because there the ciphertext is generally authenticated before, or concurrently with, the plaintext calculation. Therefore, this text requires that implementations MUST NOT release unauthenticated plaintext. Thus, system designers should consider memory limitations when picking the
Top   ToC   RFC8452 - Page 12
   size of AES-GCM-SIV plaintexts: large plaintexts may not fit in the
   available memory of some machines, tempting implementations to
   release unverified plaintext.

   A detailed cryptographic analysis of AES-GCM-SIV appears in
   [AES-GCM-SIV], and the remainder of this section is a summary of that
   paper.

   The AEADs defined in this document calculate fresh AES keys for each
   nonce.  This allows a larger number of plaintexts to be encrypted
   under a given key.  Without this step, AES-GCM-SIV encryption would
   be limited by the birthday bound like other standard modes (e.g.,
   AES-GCM, AES-CCM [RFC3610], and AES-SIV [RFC5297]).  This means that
   when 2^64 blocks have been encrypted overall, a distinguishing
   adversary who is trying to break the confidentiality of the scheme
   has an advantage of 1/2.  Thus, in order to limit the adversary's
   advantage to 2^-32, at most 2^48 blocks can be encrypted overall.  In
   contrast, by deriving fresh keys from each nonce, it is possible to
   encrypt a far larger number of messages and blocks with AES-GCM-SIV.

   We stress that nonce misuse-resistant schemes guarantee that if a
   nonce repeats, then the only security loss is that identical
   plaintexts will produce identical ciphertexts.  Since this can also
   be a concern (as the fact that the same plaintext has been encrypted
   twice is revealed), we do not recommend using a fixed nonce as a
   policy.  In addition, as we show below, better-than-birthday bounds
   are achieved by AES-GCM-SIV when the nonce repetition rate is low.
   Finally, as shown in [BHT18], there is a great security benefit in
   the multiuser/multikey setting when each particular nonce is reused
   by a small number of users only.  We stress that the nonce misuse-
   resistance property is not intended to be coupled with intentional
   nonce reuse; rather, such schemes provide the best possible security
   in the event of nonce reuse.  Due to all of the above, it is
   RECOMMENDED that AES-GCM-SIV nonces be randomly generated.

   Some example usage bounds for AES-GCM-SIV are given below.  The
   adversary's advantage is the "AdvEnc" from [key-derive] and is
   colloquially the ability of an attacker to distinguish ciphertexts
   from random bit strings.  The bounds below limit this advantage to
   2^-32.  For up to 256 uses of the same nonce and key (i.e., where one
   can assume that nonce misuse is no more than this bound), the
   following message limits should be respected (this assumes a short
   additional authenticated data (AAD), i.e., less than 64 bytes):

      2^29 messages, where each plaintext is at most 1 GiB

      2^35 messages, where each plaintext is at most 128 MiB
Top   ToC   RFC8452 - Page 13
      2^49 messages, where each plaintext is at most 1 MiB

      2^61 messages, where each plaintext is at most 16 KiB

   Suzuki et al. [multi-birthday] show that even if nonces are selected
   uniformly at random, the probability that one or more values would be
   repeated 256 or more times is negligible until the number of nonces
   reaches 2^102.  (Specifically, the probability is 1/((2^96)^(255)) *
   Binomial(q, 256), where q is the number of nonces.)  Since 2^102 is
   vastly greater than the limit on the number of plaintexts per key
   given above, we don't feel that this limit on the number of repeated
   nonces will be a problem.  This also means that selecting nonces at
   random is a safe practice with AES-GCM-SIV.  The bounds obtained for
   random nonces are as follows (as above, for these bounds, the
   adversary's advantage is at most 2^-32):

      2^32 messages, where each plaintext is at most 8 GiB

      2^48 messages, where each plaintext is at most 32 MiB

      2^64 messages, where each plaintext is at most 128 KiB

   For situations where, for some reason, an even higher number of nonce
   repeats is possible (e.g., in devices with very poor randomness), the
   message limits need to be reconsidered.  Theorem 7 in [AES-GCM-SIV]
   contains more details, but for up to 1,024 repeats of each nonce, the
   limits would be (again assuming a short AAD, i.e., less than 64
   bytes):

      2^25 messages, where each plaintext is at most 1 GiB

      2^31 messages, where each plaintext is at most 128 MiB

      2^45 messages, where each plaintext is at most 1 MiB

      2^57 messages, where each plaintext is at most 16 KiB

   In addition to calculating fresh AES keys for each nonce, these AEADs
   also calculate fresh POLYVAL keys.  Previous versions of GCM-SIV did
   not do this and instead used part of the AEAD's key as the POLYVAL
   key.  Bleichenbacher pointed out [Bleichenbacher16] that this allowed
   an attacker who controlled the AEAD key to force the POLYVAL key to
   be zero.  If a user of this AEAD authenticated messages with a secret
   additional-data value, then this would be insecure as the attacker
   could calculate a valid authenticator without knowing the input.
   This does not violate the standard properties of an AEAD as the
Top   ToC   RFC8452 - Page 14
   additional data is not assumed to be confidential.  However, we want
   these AEADs to be robust against plausible misuse and also to be
   drop-in replacements for AES-GCM and so derive nonce-specific POLYVAL
   keys to avoid this issue.

   We also wish to note that the probability of successful forgery
   increases with the number of attempts that an attacker is permitted.
   The advantage defined in [key-derive] and used above is specified in
   terms of the ability of an attacker to distinguish ciphertexts from
   random bit strings.  It thus covers both confidentiality and
   integrity, and Theorem 6.2 in [key-derive] shows that the advantage
   increases with the number of decryption attempts, although much more
   slowly than with the number of encryptions; the dependence on the
   number of decryption queries for forgery is actually only linear, not
   quadratic.  The latter is an artifact of the bound in the paper not
   being tight.  If an attacker is permitted extremely large numbers of
   attempts, then the tiny probability that any given attempt succeeds
   may sum to a non-trivial chance.

   A security analysis of a similar scheme without nonce-based key
   derivation appears in [GCM-SIV], and a full analysis of the bounds
   when applying nonce-based key derivation appears in [key-derive].  A
   larger table of bounds and other information appears at
   [aes-gcm-siv-homepage].

   The multiuser/multikey security of AES-GCM-SIV was studied by
   [BHT18], which showed that security is almost the same as in the
   single-user setting, as long as nonces do not repeat many times
   across many users.  This is the case when nonces are chosen randomly.

10. IANA Considerations

IANA has added two entries to the "AEAD Algorithms" registry: AEAD_AES_128_GCM_SIV (Numeric ID 30) and AEAD_AES_256_GCM_SIV (Numeric ID 31), both referencing this document as their specification.

11. References

11.1. Normative References

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfc-editor.org/info/rfc2119>.
Top   ToC   RFC8452 - Page 15
   [RFC8174]  Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
              2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
              May 2017, <https://www.rfc-editor.org/info/rfc8174>.

   [SP800-38A]
              Dworkin, M., "Recommendation for Block Cipher Modes of
              Operation: Methods and Techniques", NIST SP 800-38A,
              DOI 10.6028/NIST.SP.800-38A, December 2001,
              <https://csrc.nist.gov/publications/detail/sp/800-38a/
              final>.

11.2. Informative References

[AES-GCM-SIV] Gueron, S., Langley, A., and Y. Lindell, "AES-GCM-SIV: Specification and Analysis", July 2017, <https://eprint.iacr.org/2017/168>. [aes-gcm-siv-homepage] Gueron, S., Langley, A., and Y. Lindell, "Webpage for the AES-GCM-SIV Mode of Operation", <https://cyber.biu.ac.il/aes-gcm-siv/>. [BHT18] Bose, P., Hoang, V., and S. Tessaro, "Revisiting AES-GCM- SIV: Multi-user Security, Faster Key Derivation, and Better Bounds", Advances in Cryptology - EUROCRYPT 2018, DOI 10.1007/978-3-319-78381-9_18, May 2018, <https://eprint.iacr.org/2018/136.pdf>. [Bleichenbacher16] Bleichenbacher, D., "Subject: AES-GCM-SIV security of the additional data", message to the cfrg mailing list, 24 June 2016, <https://mailarchive.ietf.org/arch/msg/cfrg/ qgh-Yxmj7CC7cq2YZLpmfGA3x-o>. [GCM] Dworkin, M., "Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC", NIST SP 800-38D, DOI 10.6028/NIST.SP.800-38D, November 2007, <https://csrc.nist.gov/publications/detail/sp/800-38d/ final>. [GCM-SIV] Gueron, S. and Y. Lindell, "GCM-SIV: Full Nonce Misuse- Resistant Authenticated Encryption at Under One Cycle Per Byte", Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, DOI 10.1145/2810103.2813613, October 2015, <http://doi.acm.org/10.1145/2810103.2813613>.
Top   ToC   RFC8452 - Page 16
   [key-derive]
              Gueron, S. and Y. Lindell, "Better Bounds for Block Cipher
              Modes of Operation via Nonce-Based Key Derivation",
              Proceedings of the 2017 ACM SIGSAC Conference on Computer
              and Communications Security, DOI 10.1145/3133956.3133992,
              2017, <https://doi.org/10.1145/3133956.3133992>.

   [multi-birthday]
              Suzuki, K., Tonien, D., Kurosawa, K., and K. Toyota,
              "Birthday Paradox for Multi-collisions", Information
              Security and Cryptology - ICISC 2006, Lecture Notes in
              Computer Science, Volume 4296, DOI 10.1007/11927587_5,
              2006, <http://dx.doi.org/10.1007/11927587_5>.

   [RFC3610]  Whiting, D., Housley, R., and N. Ferguson, "Counter with
              CBC-MAC (CCM)", RFC 3610, DOI 10.17487/RFC3610, September
              2003, <https://www.rfc-editor.org/info/rfc3610>.

   [RFC5116]  McGrew, D., "An Interface and Algorithms for Authenticated
              Encryption", RFC 5116, DOI 10.17487/RFC5116, January 2008,
              <https://www.rfc-editor.org/info/rfc5116>.

   [RFC5297]  Harkins, D., "Synthetic Initialization Vector (SIV)
              Authenticated Encryption Using the Advanced Encryption
              Standard (AES)", RFC 5297, DOI 10.17487/RFC5297, October
              2008, <https://www.rfc-editor.org/info/rfc5297>.
Top   ToC   RFC8452 - Page 17

Appendix A. The Relationship between POLYVAL and GHASH

GHASH and POLYVAL both operate in GF(2^128), although with different irreducible polynomials: POLYVAL works modulo x^128 + x^127 + x^126 + x^121 + 1 and GHASH works modulo x^128 + x^7 + x^2 + x + 1. Note that these irreducible polynomials are the "reverse" of each other. GHASH also has a different mapping between 128-bit strings and field elements. Whereas POLYVAL takes the least significant to most significant bits of the first byte to be the coefficients of x^0 to x^7, GHASH takes them to be the coefficients of x^7 to x^0. This continues until, for the last byte, POLYVAL takes the least significant to most significant bits to be the coefficients of x^120 to x^127, while GHASH takes them to be the coefficients of x^127 to x^120. The combination of these facts means that it's possible to "convert" values between the two by reversing the order of the bytes in a 16-byte string. The differing interpretations of bit order takes care of reversing the bits within each byte, and then reversing the bytes does the rest. This may have a practical benefit for implementations that wish to implement both GHASH and POLYVAL. In order to be clear which field a given operation is performed in, let mulX_GHASH be a function that takes a 16-byte string, converts it to an element of GHASH's field using GHASH's convention, multiplies it by x, and converts it back to a string. Likewise, let mulX_POLYVAL be a function that converts a 16-byte string to an element of POLYVAL's field using POLYVAL's convention, multiplies it by x, and converts it back. Given the 16-byte string 01000000000000000000000000000000, mulX_GHASH of that string is 00800000000000000000000000000000 and mulX_POLYVAL of that string is 02000000000000000000000000000000. As a more general example, given 9c98c04df9387ded828175a92ba652d8, mulX_GHASH of that string is 4e4c6026fc9c3ef6c140bad495d3296c and mulX_POLYVAL of it is 3931819bf271fada0503eb52574ca5f2. Lastly, let ByteReverse be the function that takes a 16-byte string and returns a copy where the order of the bytes has been reversed.
Top   ToC   RFC8452 - Page 18
   Now GHASH and POLYVAL can be defined in terms of one another:

   POLYVAL(H, X_1, ..., X_n) =
   ByteReverse(GHASH(mulX_GHASH(ByteReverse(H)), ByteReverse(X_1), ...,
   ByteReverse(X_n)))

   GHASH(H, X_1, ..., X_n) =
   ByteReverse(POLYVAL(mulX_POLYVAL(ByteReverse(H)), ByteReverse(X_1),
   ..., ByteReverse(X_n)))

   As a worked example:
      let H = 25629347589242761d31f826ba4b757b,
          X_1 = 4f4f95668c83dfb6401762bb2d01a262, and
          X_2 = d1a24ddd2721d006bbe45f20d3c9f362.
      POLYVAL(H, X_1, X_2) = f7a3b47b846119fae5b7866cf5e5b77e.

   If we wished to calculate this given only an implementation of GHASH,
   then the key for GHASH would be

   mulX_GHASH(ByteReverse(H)) = dcbaa5dd137c188ebb21492c23c9b112.

   Then ByteReverse(GHASH(dcba..., ByteReverse(X_1), ByteReverse(X_2)))
        = f7a3b47b846119fae5b7866cf5e5b77e, as required.

   In the other direction, GHASH(H, X_1, X_2) =
   bd9b3997046731fb96251b91f9c99d7a.  If we wished to calculate this
   given only an implementation of POLYVAL, then we would first
   calculate the key for POLYVAL:

  mulX_POLYVAL(ByteReverse(H)) = f6ea96744df0633aec8424b18e26c54a.

  Then ByteReverse(POLYVAL(f6ea..., ByteReverse(X_1), ByteReverse(X_2)))
       = bd9b3997046731fb96251b91f9c99d7a.
Top   ToC   RFC8452 - Page 19

Appendix B. Additional Comparisons with AES-GCM

Some functional properties that differ between AES-GCM and AES-GCM- SIV that are also worth noting: AES-GCM allows plaintexts to be encrypted in a streaming fashion -- i.e., the beginning of the plaintext can be encrypted and transmitted before the entire message has been processed. AES-GCM-SIV requires two passes for encryption and so cannot do this. AES-GCM allows a constant additional-data input to be precomputed in order to save per-message computation. AES-GCM-SIV varies the authenticator key based on the nonce and so does not permit this. The performance for AES-GCM versus AES-GCM-SIV on small machines can be roughly characterized by the number of AES operations and the number of GF(2^128) multiplications needed to process a message. Let a = (bytelen(additional-data) + 15) / 16 and p = (bytelen(plaintext) + 15) / 16. Then AES-GCM requires p + 1 AES operations and p + a + 1 field multiplications. Defined similarly, AES-GCM-SIV with AES-128 requires p + 5 AES operations and p + a + 1 field multiplications. With AES-256, that becomes p + 7 AES operations. With large machines, the available parallelism becomes far more important, and such simple performance analysis is no longer representative. For such machines, we find that decryption of AES- GCM-SIV is only about 5% slower than AES-GCM, as long as the message is at least a couple of kilobytes. Encryption tends to run about two-thirds the speed because of the additional pass required.


(next page on part 2)

Next Section