RFC 8452
AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption
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 EncryptionAbstract
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.
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 . . . . . . . . . . . . . . . . . . . . . . . 421. 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
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.
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).
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
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)
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, ...)
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:
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
}
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
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
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
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
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>.
[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>.
[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>.
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.
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.
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)
