Crypto Forum Shay Gueron Internet Draft University of Haifa and Meta Intended status: Informational April 15, 2024 Expires: October 15, 2024 Double Nonce Derive Key AES-GCM (DNDK-GCM) draft-gueron-cfrg-dndkgcm-00 Abstract This document specifies an authenticated encryption algorithm called Double Nonce Derive Key AES-GCM (DNDK-GCM) that operates with a 32- byte root key and encrypts with a 24-byte random nonce, and optionally provides for key commitment. Encryption takes the root key and a random nonce, derives a fresh encryption key and a key commitment value, invokes AES-GCM with the derived key and a 12-byte zero nonce, and outputs the ciphertext, authentication tag and the key commitment value. The low collision probability with 24-byte random nonces extends the lifetime of the root key and this supports processing up to 2^64 bytes under one root key. DNDK-GCM involves a small overhead compared to using AES-GCM directly, and its security relies only on the standard assumption on AES as a pseudorandom permutation. Status of this Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. The list of current Internet-Drafts is at http://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months Gueron Expires October 15, 2024 [Page 1] Internet-Draft DNDK-GCM April 2024 and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at https://www.ietf.org/1id-abstracts.html. The list of Internet-Draft Shadow Directories can be accessed at https://www.ietf.org/shadow.html This Internet-Draft will expire on October 15, 2024. Copyright Notice Copyright (c) 2024 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. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License. Table of Contents 1. Introduction...................................................3 1.1. Limitation 1: Short Nonces Enforce Frequent Key Rotation..3 1.2. Limitation 2: Lack of Key Commitment......................4 1.3. DNDK-GCM Design Goals.....................................5 2. Requirements Language..........................................5 Gueron Expires October 15, 2024 [Page 2] Internet-Draft DNDK-GCM April 2024 3. Preliminaries and Notation.....................................5 4. DNDK-GCM Definition............................................7 4.1. Input and Output Ranges...................................7 4.2. The Preamble: Derive-L1-2v-L2-L3..........................8 4.3. Encryption...............................................12 4.4. Decryption...............................................13 4.5. No Key Commit Value Option...............................14 5. AEAD..........................................................14 6. Security Considerations.......................................15 7. Design Rationale..............................................15 7.1. Security Bounds..........................................17 8. IANA Considerations...........................................17 9. References....................................................18 9.1. Normative References.....................................18 9.2. Informative References...................................18 Appendix A. The Preamble Procedure Flow With Explicit Indexes....20 Appendix B. A Worked-Out Example.................................25 10. Acknowledgments..............................................28 11. Authors' Addresses...........................................28 1. Introduction Authenticated Encryption with Additional Data (AEAD) [RFC5116] is a fundamental cryptographic tool that provides confidentiality and integrity in a single scheme. AES-GCM [GCM] is currently the most frequently used AEAD scheme. It draws popularity due to its attractive performance especially on modern platforms that nowadays have native instructions to accelerate AES computations and polynomial multiplications that are used for authentication. However, AES-GCM has limitations that motivate seeking some variants. 1.1. Limitation 1: Short Nonces Enforce Frequent Key Rotation AES-GCM is a nonce-respecting AEAD: a nonce must not be used for Gueron Expires October 15, 2024 [Page 3] Internet-Draft DNDK-GCM April 2024 encrypting more than one message under a given key. In fact, reusing a nonce for two distinct messages leads to catastrophic failure of confidentiality and integrity. Applications can enforce nonce uniqueness by using a counter to construct nonces. However, in many real-world scenarios, maintaining a state is cumbersome, expensive, or even unsafe. Therefore, in practice, systems often generate a nonce uniformly at random for every message, hoping that a nonce collision does not occur over the lifetime of the key. In this context, NIST's Special Publication 800- 38D [GCM] states (Section 8) that: The probability that the authenticated encryption function ever will be invoked with the same IV and the same key on two (or more) distinct sets of input data shall be no greater than 2^.32. For AES-GCM in a 12-byte random setting, nonce collision probability in Q calls is at most Q^2/2^97, and this bound is also essentially tight. Upper bounding this probability by 2^-32 limits the lifetime of a key to at most 2^32.5 encryptions. In many scenarios, e.g., for processing data at the cloud scale, this imposes a too-frequent key rotation rate. Note that AES-GCM can consume nonces of arbitrary lengths, but the key rotation limitation is not fully alleviated by using longer than 12 bytes nonces even with a stateful counter. The reason is that GHASH is called over any nonce whose length is not 12 bytes, and the result is the initial 16-byte counter for the remaining AES computations [GCM]. This leads to a similar collision probability issue: the probability is lower than with random 12-byte nonces, but still much higher than the security goal of DNDK-GCM. 1.2. Limitation 2: Lack of Key Commitment AES-GCM has the following property: it is possible to find two (or more) keys K1, K2, and two (or more) messages M1, M2, such that encrypting M1 under K1 and encrypting M2 under K2 give the same Gueron Expires October 15, 2024 [Page 4] Internet-Draft DNDK-GCM April 2024 ciphertext-tag pair. Thus, a receiver that decrypts a ciphertext blob with a key that is not verifiably trustworthy might accept the resulting plaintext as a valid message although it was generated by a malicious untrusted actor. This lack of key commitment property is not unique to AES-GCM. It applies to other AEADs where authentication uses universal hashing rather than e.g., (less efficient) collision resistant hashing. In some scenarios, lack of key commitment can be a problem [DGRW18], [LGR21], [ADG+22] and adding some mitigation would be useful. Several approaches to add key commitment are shown in [ADG+22] and some methods have already been deployed in real cloud systems (e.g., AWS Encryption SDK [Gue20]). 1.3. DNDK-GCM Design Goals DNDK-GCM is designed to address the two AES-GCM limitations with: a) A small performance overhead compared to using AES-GCM directly. b) A simple construction that can reuse vetted and optimized AES-GCM implementations and leverage ubiquitous processor instructions on popular architectures (e.g., AES-NI [Gue10] and PCLMULQDQ [GK08]). c) Security that relies only on the universally accepted assumption that AES is a good pseudorandom permutation. This is already the assumption that establishes the security of AES-GCM. 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. Preliminaries and Notation Gueron Expires October 15, 2024 [Page 5] Internet-Draft DNDK-GCM April 2024 A byte is an integer between 0 and 255. It is represented here by two hexadecimal digits. For example, the integers 5 and 135 are denoted by 0x05 and 0x87, respectively. Let U be an array of bytes ("array" for short) of length u (bytes), written as U = U [u-1] U [u-2] ... U [0], where U [j] is the j-th byte, j = 0, ..., u-1. By convention, the bytes are listed here in an ordering such that U [u-1] is in the leftmost position and U [0] is in the rightmost position. For integers a, b such that 0 <= b <= a <=(u-1), T = U [a: b] denotes the sub-array U [a] U [a-1] ...U [b] of length (a-b+1) where T [j] = U [j + b], j = 0, 1, ..., (a - b). To avoid confusion, note that in this document, the two boundary indices are included in the range (contrary to conventions used in some (not all) programming languages). For completeness, in the case where 0 <= b = a+1 <=(u-1)the sub-array U [a: b] is understood to be empty. Concatenation of byte arrays is denoted by "||". If U1 = U1 [u1-1] U [u1-2] ... U [0] and U0 = U0 [u0-1] U [u0-2] ... U [0] then U1 || U2 is the array W = W [u1+u0-1: 0] of u1+u2 bytes such that W [u1+u0 -1 : u0] = U1 and W [u0-1: 0] = U0. For an integer s, (0x00)^s denotes an array of s zero bytes. An array of 16 bytes is also called a "block". The symbol FAIL is used here to indicate a failed integrity check. Here, AES refers to the Advanced Encryption Standard [AES], specifically, to the version with a 256-bit key (equivalently 32-byte key) AES256. If K (key) is an array of 32 bytes and P (plaintext) is an array of 16 bytes, then (ciphertext) C = AES (K, P) is the 16-byte array that results from encrypting P with AES under the key K. Here, AES-GCM refers to the Authenticated Encryption with Additional Gueron Expires October 15, 2024 [Page 6] Internet-Draft DNDK-GCM April 2024 Data (AEAD) scheme standardized in [GCM]. AES-GCM encryption and decryption are denoted AES-GCM.Enc and AES-GCM.Dec, respectively. They take the tuples (N, A, M) and (N, A, C, T), respectively, where N is a nonce, A is the Additional Authenticated Data (AAD), M is the message, C is the ciphertext, and T is the authentication tag. Here, the inputs and outputs are assumed to be arrays of bytes, K is an array of 32 bytes, N is an array of 12 bytes, T is an array of 16 bytes, A is an array of at most 2^61 - 1 bytes and M (and C) is an array of at most 2^36 - 32 bytes. 4. DNDK-GCM Definition DNDK-GCM is an AEAD scheme that encrypts and authenticates a message, along with additional authenticated data (AAD), using a 24-byte nonce that is selected uniformly at random for every message. 4.1. Input and Output Ranges DNDK-GCM is defined with the length and range parameters K_LEN, N_LEN, A_MAX, P_MAX, C_MAX, T_LEN, and KC_LEN. Encryption is denoted by DNDK-GCM.Enc and decryption is denoted by DNDK-GCM.Dec. These procedures are defined for inputs that are arrays of bytes. DNDK-GCM.Enc takes a tuple (K, N, A, M) where K is the root key, N is the nonce, A is the AAD, and M is the message. It outputs ciphertext C, an authentication tag T and a commitment value KC. DNDK-GCM.Dec takes a tuple (K, N, A, C, T, KC), where K is the root key, N is the nonce, A is the AAD, C is the ciphertext, T is the authentication tag and KC is the commitment value. It outputs a message M with the same byte-length as C, or a failure indication (FAIL). The root key (K) MUST consist of K_LEN bytes. It MUST be selected uniformly at random and be known only to the parties (sender and recipient) that use the scheme. The nonce (N) MUST consist of N_LEN bytes and MUST be selected uniformly at random for every encryption. Gueron Expires October 15, 2024 [Page 7] Internet-Draft DNDK-GCM April 2024 The AAD (A) MUST consist of at most A_MAX bytes, the message (M) MUST consist of at most P_MAX bytes, the ciphertext (C) MUST consist of at most C_MAX bytes, the authentication tag (T) MUST consist of T_LEN bytes, and the key commitment value (KC) MUST consist of KC_LEN bytes. The arrays A, M, C may be empty. DNDK-GCM is defined with the following parameter values: K_LEN = 32, N_LEN = 24, A_MAX = 2^61 - 1, P_MAX = 2^36 - 32, C_MAX = 2^36 - 32, T_LEN = 16, and KC_LEN = 32. Tag truncation: AES-GCM specification [GCM] (section 5.2.1.2) allows 16-byte tags to be truncated down to 12 bytes (or even to shorter tags of 8 or 4 bytes, where these lengths are accepted subject to some usage constraints explained in appendix C of [GCM]). For simplicity and brevity, this document defines DNDK-GCM only with a 16-byte tag and implicitly ignores a tag truncation option (even to the seemingly innocuous truncation to 12 bytes). However, DNDK-GCM usages that require (and settle with) a shorter tag of d < 16 bytes, MAY truncate the tag T [15: 0] to T [d-1, d-2, ..., 0] for d = 12, 8, or 4 as indicated in [GCM]. The agreement on such truncation is left for the communicating parties or protocol. 4.2. The Preamble: Derive-L1-2v-L2-L3 This section defines the two algorithms "SplitArray" and "Derive-L1- 2v-L2-L3". SplitArray takes an array N of 2v bytes and outputs two arrays N1 and N0 of v bytes. Derive-L1-2v-L2-L3 takes a root key (K) of L1 bytes and a nonce (N) of 2v bytes (1 <= v <= 15). It outputs a derived key (DerivedKey) of L2 bytes and a key commitment value (KeyCommit) of L3 bytes. This document fixes the parameter values to L1 = L2 = L3 = 32 and v = 12 (i.e., N (nonce) has 24 bytes). For short, Derive-32-24-32-32 is referred to as "Derive". Gueron Expires October 15, 2024 [Page 8] Internet-Draft DNDK-GCM April 2024 Algorithms 1 and 2 define SplitArray and Derive. +-------------------------------------------------------------------+ | | | Algorithm 1. SplitArray (v, N) | | Input: Integer v (v <= 15), array N = N [2v - 1: 0] | | N1 = N1 [v-1: 0] = N [2v-1: v] | | N0 = N0 [v-1: 0] = N [v-1: 0] | | Output: N1, N0 | | | +-------------------------------------------------------------------+ Gueron Expires October 15, 2024 [Page 9] Internet-Draft DNDK-GCM April 2024 +-------------------------------------------------------------------+ | | | Algorithm 2. Derive (K, N) | | Input: root key K, array of 2v bytes N = N [2v - 1: 0] | | Context: nonce length 2v | | (N1, N0) = SplitArray (v, N) | | For j in {1, 3, 5, 7, 9} | | Bj [15: (16-v)] = N1 [v-1: 0] | | Bj [(15-v): 1] = (0x00)^(15-v) | | Bj [0] = j | | For j in {0, 2, 4, 6, 8} | | Bj [15: (16-v)] = N0 [v-1: 0] | | Bj [(15-v): 1] = (0x00)^(15-v) | | Bj [0] = j | | For j = 0, ..., 9 | | itijbucgcinnvullehcrjdiheicn Xj = AES (K, Bj) | | For j = 2, 3, ..., 9 cdbd | | Yj = Xj XOR X [j mod 2] | | KeyCommit [31: 16] = Y8 XOR Y9 | | KeyCommit [15: 0] = Y6 XOR Y7 | | DerivedKey [31: 16] = Y4 XOR Y5 | | DerivedKey [15: 0] = Y2 XOR Y3 | | Output: (KeyCommit [31: 0], DerivedKey [31: 0]) | | | +-------------------------------------------------------------------+ Gueron Expires October 15, 2024 [Page 10] Internet-Draft DNDK-GCM April 2024 Figure 1 illustrates the flows of Algorithms 1 and 2 from the "double nonce" N to DerivedKey and KeyCommit. For convenience, Appendix A shows these flows with explicit indexes. +-------------------------------------------------------------+ | | |N = N23 N22 N21 N20 N19 N18 N17 N16 N15 N14 N13 N12 \\ | | N11 N10 N09 N08 N07 N06 N05 N04 N03 N02 N01 N00 | |N1 = N23 N22 N21 N20 N19 N18 N17 N16 N15 N14 N13 N12 | |N0 = N11 N10 N09 N08 N07 N06 N05 N04 N03 N02 N01 N00 | |-------------------------------------------------------------| | - = N1 || 0x000000 | |[- || 0x01] [- || 0x03] [- || 0x05] [- || 0x07] [- || 0x09] | | | | | | | | | V V V V V | | AES (K,*) AES (K,*) AES (K,*) AES (K,*) AES (K,*) | | | | | | | | | V V V V V | | >-------> + -------> + -------> + -------> + | | Y3 Y5 Y7 Y9 | |-------------------------------------------------------------| | - = N0 || 0x000000 | |[- || 0x00] [- || 0x02] [- || 0x04] [- || 0x06] [- || 0x08] | | | | | | | | | V V V V V | | AES (K,*) AES (K,*) AES (K,*) AES (K,*) AES (K,*) | | | | | | | | | V V V V V | | >-------> + -------> + -------> + -------> + | | Y2 Y4 Y6 Y8 | |-------------------------------------------------------------| | Y3 Y5 Y7 Y9 | | + + + + | Gueron Expires October 15, 2024 [Page 11] Internet-Draft DNDK-GCM April 2024 | Y2 Y4 Y6 Y8 | | | | | | | | V V V V | | DK [31: 16] DK [15: 0] KC [31: 16] KC [15: 0] | | | +-------------------------------------------------------------+ Figure 1. The flows of Algorithms 1 and 2 from the double nonce N to the derived key (DK) and key commit value (KC). 4.3. Encryption DNDK-GCM.Enc receives the tuple (K, N, A, M) as input. It is assumed that the caller has generated N, uniformly at random prior to invoking DNDK-GCM.Enc (or that DNDK-GCM.Enc starts with such generation) and this step is not shown here. DNDK-GCM.Enc runs the preamble Derive over K and N and computes a derived key DK and a key commitment value KC. Subsequently, DNDK-GCM.Enc invokes AES-GCM.Enc with DK as the encryption key, a nonce NZ12 of 12 zero bytes, A and M. This produces the ciphertext C with the same length as M and the authentication tag T. The output is (C, T, KC). DNDK-GCM.Enc is defined by Algorithm 3. Gueron Expires October 15, 2024 [Page 12] Internet-Draft DNDK-GCM April 2024 +-----------------------------------------------------------------+ | | | Algorithm 3. DNDK-GCM.Enc | | Input: K, N, A, M | | NZ12 = (0x00)^12 | | (KC, DK) = Derive (K, N) | | (C, T) = AES-GCM.Enc (DK, NZ12, A, M) | | Output: C, T, KC | | | +-----------------------------------------------------------------+ 4.4. Decryption DNDK-GCM.Dec receives the tuple (K, N, A, C, T, KC) as input. It runs the preamble Derive over K and N and computes a derived key DK and a key commitment value contender KC'. If KC' is not equal to KC, the decryption aborts and outputs the failure indication FAIL. Otherwise, the procedure runs AES-GCM.Dec with DK as the decryption key, a nonce NZ12 of 12 zero bytes, A, C and T. This either retrieves a message M with the same length as C, or an authentication failure indication FAIL. The output of DNDK-GCM.Dec is, accordingly, either M or FAIL. The decryption does not release (any part of) M before it is fully authenticated. DNDK-GCM.Dec is defined by Algorithm 4. Gueron Expires October 15, 2024 [Page 13] Internet-Draft DNDK-GCM April 2024 +-----------------------------------------------------------------+ | | | Algorithm 4. DNDK-GCM.Dec | | Input: K, N, A, C, T, KC | | NZ12 = (0x00)^12 | | (KC', DK) = Derive (K, N) | | If KC' \ne KC output FAIL and abort | | M / FAIL = AES-GCM.Dec (DK, NZ12, A, C, T) | | Output: M or FAIL | | | +-----------------------------------------------------------------+ Appendix A provides a step-by-step detailed example. 4.5. No Key Commit Value Option It is possible to use DNDK-GCM without the key commit value (KC) for usages where the standard properties of AEAD suffice. For example, in the case where a party decrypting a ciphertext blob has means to confirm that its root key was also the key used for encrypting the blob. When KC is not required for decryption, it does not need to be generated during encryption nor sent with the ciphertext blob. In such cases, the Derive function can skip the AES calls that produce KC, reducing the number of AES invocations from 10 to 6. 5. AEAD Gueron Expires October 15, 2024 [Page 14] Internet-Draft DNDK-GCM April 2024 We define an AEAD, in the format of [RFC5116], that uses DNDK-GCM, namely AEAD_DNDK_GCM. The key input to this AEAD becomes the root key. Thus, AEAD_DNDK_GCM takes a 32-byte key. 6. Security Considerations An invocation of DNDK-GCM.Enc MUST use a (24-byte) nonce that is selected uniformly at random from the nonce space (in particular, the selection of a nonce value for encryption should be unpredictable by an outside observer). Note that non-repeating but nonrandom nonces (e.g., implemented as a counter) are not acceptable for DNDK-GCM. Such nonce selection could lead to linear dependence in (N1, N0) values (at least without taking steps to avoid it e.g., by fixing N1 = (0xFF)^12 and a running a counter for N0). This is not a real limitation because scenarios that can use a counter nonce can also use the standard AES-GCM. In such cases, using the double-length of DNDK-GCM is pointless. DNDK-GCM decryption involves two verifications: an optional match on the key commitment value, and a match on the authentication tag in the AES-GCM.Dec invocation. An implementation MUST NOT release the plaintext or any part of it before it is (doubly) authenticated because otherwise parts of a system may process malicious data as if it were authentic. 7. Design Rationale The first goal of the DNDK-GCM design is to overcome the short nonce limitation of AES-GCM, in the random nonce (stateless) setting. To this end, DNDK-GCM encryption (and decryption) consumes a double- Gueron Expires October 15, 2024 [Page 15] Internet-Draft DNDK-GCM April 2024 length (random) nonce of 24 bytes, such that nonce collision probability after Q samples is upper bounded by Q^2/2^193. DNDK-GCM.Enc invokes the pseudorandom function Derive (Algorithm 2) to produce the fresh encryption key and a key commitment value. This preamble step generalizes the Derive-Key design of [GL17] (which is used for AES-GCM-SIV [RFC8452]). The difference is that the (double) nonce is used only for the derivation and not for the AES-GCM encryption. However, the distinguishing advantage of Derive with Q samples, and the collision probability of Q 32-byte (truly) random derived keys is kept negligible (at most Q^2/2^257) for the target Q = 2^64 encryptions. With this design, the random nonce setting is converted to a multiple-one-time-keys setting for AES-GCM. Here, every key is used for encrypting exactly one message, and it is therefore possible to use a fixed AES-GCM nonce (0x00^12 here). The pseudorandom function Derive is a "double XORP": a variant of the XORP construction [Iwa06] over two halves of the nonce. The Beyond- Birthday-Bound indistinguishability is deduced from [BGK99]. The security relies only on one cryptographic primitive, namely AES, and on its pseudorandom permutation (PRP) advantage when used with uniform random keys: If Q keys K1, K2, ..., KQ are selected uniformly at random from the AES key space, then AES outputs from chosen blocks and any choice of a key from the list K1, K2, ..., KQ, are indistinguishable from the outputs of Q corresponding preselected random permutations of the space of 128-bit strings, even after a very large number of queries (Q). The case Q=1 is the standard assumption in the single- key setting. Derive requires only 10 calls to AES256 with the root key, computed and over independent blocks, where these computations can therefore Gueron Expires October 15, 2024 [Page 16] Internet-Draft DNDK-GCM April 2024 be parallelized. In addition, every encryption requires also an AES256 key expansion with the fresh derived key (and other initialization steps for AES-GCM). The total overhead, however, is relatively small (see [Gue24] for a full account). 7.1. Security Bounds The privacy bounds of DNDK-GCM rely on the designated parameters. Assume that DNDK-GCM is used for encrypting Q <= 2^64 messages with lengths L1, L2, ..., LQ blocks. Assume that the PRP advantage of AES (in this multikey setting) is negligible for such Q. Then, the following holds: a) The distinguishing advantage of Derive is negligible; b) The probability to encounter a collision in the Q randomly generated 24-byte nonces, and the probability to encounter a collision in the Q derived 32-byte encryption keys are negligible. Under these conditions, the distinguishing advantage of passively viewed ciphertext-tag pairs from chosen inputs, and uniform random strings of the matching lengths, is either less than 2^-32 or dominated by the sum Sum ((L_i+2)^2/2^129, i=1, ..., Q) For example, under the PRP assumption on AES, processing 2^64 messages of L_i = 2^16 - 2 blocks (2^20 - 32 bytes) would lead to indistinguishability margins of ~2^-32. To find two (adversarial) keys K1, K2, and two N-A-M triples such that DNDK-GCM.Enc (K1, N1, A1, M1) = DNDK-GCM.Enc (K2, N2, A2, M2), an adversary needs to find 32-byte keys K1, K2 such that the 32-byte key commitment values (KeyCommit)agree. A detailed analysis is available in [Gue24]. 8. IANA Considerations Gueron Expires October 15, 2024 [Page 17] Internet-Draft DNDK-GCM April 2024 IANA needs to add one entry to the "AEAD Algorithms" registry: AEAD_DNDK_AES_256_GCM (Numeric ID TBD) referencing this document as its specification. 9. References 9.1. Normative References [AES] National Institute of Standards and Technology, "Advanced Encryption Standard (AES)", FIPS 197,November 2001. The original reference (FIPS 197 standard), dated 2001 was superseded in May 2023; the new DOI is https://doi.org/10.6028/NIST.FIPS.197-upd1 [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. Note: the GCM specification (NIST SP 800-38D) is planned to be revised in the near future. https://csrc.nist.gov/News/2024/nist-to-revise-sp-80038d- gcm-and-gmac-modes [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, . 9.2. Informative References Gueron Expires October 15, 2024 [Page 18] Internet-Draft DNDK-GCM April 2024 [RFC5116] McGrew, D., "An Interface and Algorithms for Authenticated Encryption", RFC 5116, DOI 10.17487/RFC5116, January 2008, . [ADG+22] Albertini, A., Duong, T., Gueron, S., Kolbl, S., Luykx, A., Schmieg, S., "How to Abuse and Fix Authenticated Encryption Without Key Commitment", in Proceedings of the 31st USENIX Security Symposium (USENIX Security 22), pp. 3291-3308, 2022. [Online]. Available: https://www.usenix.org/system/files/usenixsecurity22- albertini.pdf [BGK99] Bellare, M., Goldreich, O., Krawczyk, H. (1999), "Stateless Evaluation of Pseudorandom Functions: Security Beyond the Birthday Barrier", In: Wiener, M. (eds) Advances in Cryptology - CRYPTO' 99. CRYPTO 1999. Lecture Notes in Computer Science, vol 1666. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48405-1_17 [DGRW18] Dodis, J., Grubbs, P., Ristenpart, T., Woodage, J., "Fast Message Franking: From Invisible Salamanders to Encryptment", CRYPTO 2018, Proceedings, Part I, Lecture Notes in Computer Science, vol. 10991, pp. 155-186, Springer, 2018. [Online]. Available: https://doi.org/10.1007/978-3-319-96884-1_6 [Gue10] Gueron, S., "Intel Advanced Encryption Standard (AES) Instructions Set", Intel White Paper, Rev. 3, 1-94, 2010. [Online]. Available: https://www.intel.com/content/dam/doc/white-paper/advanced- encryption-standard-new-instructions-set-paper.pdf [Gue20] Gueron, S., "Key Committing AEADs", Cryptology ePrint Archive, Paper 2020/1153, 2020. [Online]. Available: https://eprint.iacr.org/2020/1153 Gueron Expires October 15, 2024 [Page 19] Internet-Draft DNDK-GCM April 2024 [Gue24] Gueron, S., "Double Nonce Derive Key AES-GCM", Cryptology ePrint Archive, Paper 2024/TBD, 2024. [Online]. To be available on https://eprint.iacr.org/2024/ [GK08] Gueron, S., Kounavis, M., "Carry-Less Multiplication and Its Usage for Computing the GCM Mode", Intel White Paper, Rev. 2.02, 1-84, 2014. [Online]. Available: https://www.intel.com/content/dam/develop/external/us/en/do cuments/clmul-wp-rev-2-02-2014-04-20.pdf [RFC8452] Gueron, S. Langley, A, and Lindell, Y., "AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption," RFC 8452, RFC Editor, April 2019. [Online]. Available: https://www.rfc- editor.org/info/rfc8452 [GL17] 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, 2017. [Online]. Available: https://doi.org/10.1145/3133956.3133992 [LGR21] J. Len, P. Grubbs, T. Ristenpart, "Partitioning Oracle Attacks," 30th USENIX Security Symposium, USENIX Security 2021, August 11-13, 2021, pp. 195-212. [Online]. Available: https://www.usenix.org/system/files/sec21summer_len.pdf [Iwa06] Iwata, T., "New Blockcipher Modes of Operation with Beyond the Birthday Bound Security", Fast Software Encryption, FSE 2006, Revised Selected Papers, Lecture Notes in Computer Science, vol. 4047, pp. 310-327, Springer, 2006. [Online]. Available: https://doi.org/10.1007/11799313_20 Appendix A. The Preamble Procedure Flow With Explicit Indexes Gueron Expires October 15, 2024 [Page 20] Internet-Draft DNDK-GCM April 2024 Figures 2a, 2b, 2c illustrate the preamble procedure flow with explicit indexes, starting from N to DerivedKey and KeyCommit. +-------------------------------------------------------------------+ | | | Long Nonce | | ---------- | | N = | | N[23] N[22] N[21] N[20] N[19] N[18] N[17] N[16] N[15] | | N[14] N[13] N[12] N[11] N[10] N[9] N[8] N[7] N[6] N[5] | | N[3] N[2] N[1] N[0] | | | | Split Nonce | | ----------- | | N1 = | | N[23] N[22] N[21] N[20] N[19] N[18] | | N[17] N[16] N[15] N[14] N[13] N[12] | | N0 = | | N[11] N[10] N[9] N[8] N[7] N[6] | | N[5] N[4] N[3] N[2] N[1] N[0] | | | +-------------------------------------------------------------------+ Figure 2a. Gueron Expires October 15, 2024 [Page 21] Internet-Draft DNDK-GCM April 2024 +-------------------------------------------------------------------+ | | | The 10 blocks for Derive | | ------------------------ | | B1 = N[23] N[22] N[21] N[20] N[19] N[18] N[17] N[16] | | N[15] N[14] N[13] N[12] 0 0 0 1 | | B3 = N[23] N[22] N[21] N[20] N[19] N[18] N[17] N[16] | | N[15] N[14] N[13] N[12] 0 0 0 3 | | B5 = N[23] N[22] N[21] N[20] N[19] N[18] N[17] N[16] | | N[15] N[14] N[13] N[12] 0 0 0 5 | | B7 = N[23] N[22] N[21] N[20] N[19] N[18] N[17] N[16] | | N[15] N[14] N[13] N[12] 0 0 0 7 | | B9 = N[23] N[22] N[21] N[20] N[19] N[18] N[17] N[16] | | N[15] N[14] N[13] N[12] 0 0 0 9 | | ---------------------------------------------------- | | B0 = N[11] N[10] N[9] N[8] N[7] N[6] N[5] N[4] | | N[3] N[2] N[1] N[0] 0 0 0 0 | | B2 = N[11] N[10] N[9] N[8] N[7] N[6] N[5] N[4] | | N[3] N[2] N[1] N[0] 0 0 0 2 | | B4 = N[11] N[10] N[9] N[8] N[7] N[6] N[5] N[4] | | N[3] N[2] N[1] N[0] 0 0 0 4 | | B6 = N[11] N[10] N[9] N[8] N[7] N[6] N[5] N[4] | | N[3] N[2] N[1] N[0] 0 0 0 6 | | B8 = N[11] N[10] N[9] N[8] N[7] N[6] N[5] N[4] | | N[3] N[2] N[1] N[0] 0 0 0 8 | | | Gueron Expires October 15, 2024 [Page 22] Internet-Draft DNDK-GCM April 2024 +-------------------------------------------------------------------+ Figure 2b. Gueron Expires October 15, 2024 [Page 23] Internet-Draft DNDK-GCM April 2024 +-------------------------------------------------------------------+ | | | Double XORP XORs (here, "^" is XOR | | ---------------- | | Y[2] | Y[3] | Y[4] | Y[5] | | | X[2] ^ X[0] | X[3] ^ X[1] | X[4] ^ X[0] | X[5] ^ X[1] | | | ---------------------------------------------------------- | | Y[6] | Y[7] | Y[8] | Y[9] | | X[6] ^ X[0] | X[7] ^ X[1] | X[8] ^ X[0] | X[9] ^ X[1] | | | | The 10 encryption calls | | ----------------------- | | X0 = E (K, B0)| X1 = E (K, B1)| X2 = E (K, B2)| | | X3 = E (K, B3)| X4 = E (K, B4)| X5 = E (K, B5)| | | X6 = E (K, B6)| X7 = E (K, B7)| X8 = E (K, B8)| | | X9 = E (K, B9)| | | | | The double-XORP XORs | | -------------------- | | Y2 = X2 ^ X0 | Y3 = X3 ^ X1 | Y4 = X4 ^ X0 | Y5 = X5 ^ X1 | | | Y2 = X2 ^ X0 | Y3 = X3 ^ X1 | Y4 = X4 ^ X0 | Y5 = X5 ^ X1 | | | | | The key commitment value | | ------------------------ | | KeyCommit [31: 16] | KeyCommit [15: 0] | | | --------------------------------------- | | Gueron Expires October 15, 2024 [Page 24] Internet-Draft DNDK-GCM April 2024 | Y8 ^ Y9 | Y6 ^ Y7 | | | | The derived message-key | | ----------------------- | | DerivedKey [31: 16] | DerivedKey [15: 0] | | | ---------------------------------------- | | | Y4 ^ Y5 | Y2 ^ Y3 | +-------------------------------------------------------------------+ Figure 2c. Appendix B. A Worked-Out Example Following is a DNDK-GCM encryption example. Arrays of bytes are typed in increasing order of byte positions from left (byte 0) to right. +------------------------------------------------------------------+ | -------------------------Bytes Position------------------------- | | 0001020304050607080910111213141516171819202121232425262728293031 | | 000102030405060708091011121314151617181920212123 | | 00010203040506070809101112131415 | | --------------------------------||------------------------------ | | Root key: | | 0100000000000000000000000000000000000000000000000000000000000000 | | | | Input: | | Nonce: | | 000102030405060708090a0b0c0d0e0f1011121314151617 | | aad: 0100000011 | | plaintext: 11000001 | | | Gueron Expires October 15, 2024 [Page 25] Internet-Draft DNDK-GCM April 2024 | Derived key: | | 18c272b0158afa71ed99b64e5e39daaaaae37e70fa1b46407256c0b6f8531a64 | | | | Output: | | Key Commit Value (KC) | | 1fd1839805fce095052919629ca8947766d08eeee135cdf261228bfd4a796bbb | | ciphertext: e6de36f2 | | tag: e5973b407bafcd39a20f92ac8d1f5629 | | | | Intermediate Values: | | | | Split Nonce: | | Nonce [0]: 000102030405060708090a0b | | Nonce [1]: 0c0d0e0f1011121314151617 | | | | B0: 00000000000102030405060708090a0b | | B1: 010000000c0d0e0f1011121314151617 | | B2: 02000000000102030405060708090a0b | | B3: 030000000c0d0e0f1011121314151617 | | B4: 04000000000102030405060708090a0b | | B5: 050000000c0d0e0f1011121314151617 | | B6: 06000000000102030405060708090a0b | | B7: 070000000c0d0e0f1011121314151617 | | B8: 08000000000102030405060708090a0b | | B9: 090000000c0d0e0f1011121314151617 | | | | X0: b0fbcb02c071f4a25de23297e13d7066 | | X1: 19d1e1933ad4334fd02cc82d5c4a72f1 | | X2: d33a0c752571ba59daaf250dbf59ef56 | | X3: 62d25454ca5e87c5baf869f95c17376b | Gueron Expires October 15, 2024 [Page 26] Internet-Draft DNDK-GCM April 2024 | X4: 1910758c06e22831fd772c93eb731d55 | | X5: 1ad9216d065ca99c02ef169fae5705a6 | | X6: e5025a0563681bbfa686600e3ebed7a6 | | X7: 53f9f30c9c313cc72e6183d61f614146 | | X8: ebd781624db0d882664f49b4f38d61b4 | | X9: 242d251d5620d29d8aa338f304830898 | | | | Y2: 63c1c777e5004efb874d179a5e649f30 | | Y3: 7b03b5c7f08ab48a6ad4a1d4005d459a | | Y4: a9ebbe8ec693dc93a0951e040a4e6d33 | | Y5: 0308c0fe3c889ad3d2c3deb2f21d7757 | | Y6: 55f99107a319ef1dfb645299df83a7c0 | | Y7: 4a28129fa6e50f88fe4d4bfb432b33b7 | | Y8: 5b2c4a608dc12c203bad7b2312b011d2 | | Y9: 3dfcc48e6cf4e1d25a8ff0de58c97a69 | | | | Derived Key (DK): | | 18c272b0158afa71ed99b64e5e39daaaaae37e70fa1b46407256c0b6f8531a64 | | | | DK [0]: 18c272b0158afa71ed99b64e5e39daaa | | DK [1]: aae37e70fa1b46407256c0b6f8531a64 | | | | Key commit value (KC): | | 1fd1839805fce095052919629ca8947766d08eeee135cdf261228bfd4a796bbb | | KC [0]: 1fd1839805fce095052919629ca89477 | | KC [1]: 66d08eeee135cdf261228bfd4a796bbb | | | | -------------------------Bytes Position------------------------- | | 0001020304050607080910111213141516171819202121232425262728293031 | | 000102030405060708091011121314151617181920212123 | Gueron Expires October 15, 2024 [Page 27] Internet-Draft DNDK-GCM April 2024 | 00010203040506070809101112131415 | | --------------------------------||------------------------------ | +------------------------------------------------------------------+ 10. Acknowledgments The author would like to thank Gerald Doussot, Isaac Elbaz, Sasha Frolov, Ed Knapp, Thomas Pornin, Eric Schorn for their comments and suggestions. 11. Authors' Addresses Shay Gueron University of Haifa Abba Khoushy Ave 199 Haifa 3498838, Israel Email: shay.gueron@gmail.com Gueron Expires October 15, 2024 [Page 28]