Crypto Forum Shay Gueron Internet Draft University of Haifa and Meta Intended status: Informational March 21, 2025 Expires: September 21, 2025 Double Nonce Derive Key AES-GCM (DNDK-GCM) draft-gueron-cfrg-dndkgcm-02 Abstract This document specifies an authenticated encryption algorithm called Double Nonce Derive Key AES-GCM (DNDK-GCM). It operates with a 32- byte root key and is designed to encrypt with a 24-byte random nonce and optionally to provide for key commitment. Encryption takes the root key and a 15-byte portion of the random nonce, and derives a fresh 32-byte encryption key and (optionally) a key commitment value. Then, it invokes AES-GCM with the derived key and the remaining bytes of the nonce, and outputs the ciphertext, authentication tag and the key commitment value. Although this is not the primary use case, it is also possible to use DNDK-GCM with a non-repeating but non-random nonce (i.e., a "counter- based nonce"). The low collision probability in a collection of 24-byte random nonces and the per-nonce derivation of an encryption key extend the lifetime of the root key, and the scheme can support processing up to 2^64 bytes under a given root key. DNDK-GCM introduces a relatively small overhead compared to using AES-GCM directly, and its security relies only on the standard assumption that AES acts 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. Gueron Expires September 21, 2025 [Page 1] Internet-Draft DNDK-GCM March 2025 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 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 September 21, 2025. Copyright Notice Copyright (c) 2025 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. Gueron Expires September 21, 2025 [Page 2] Internet-Draft DNDK-GCM March 2025 Table of Contents 1. Introduction...................................................4 1.1. Limitation 1: Short Nonces Enforce Frequent Key Rotation..4 1.2. Limitation 2: Lack of Key Commitment......................5 1.3. DNDK-GCM Design Goals.....................................5 2. Requirements Language..........................................6 3. Preliminaries and Notation.....................................6 4. DNDK-GCM Definition............................................9 4.1. Input and Output Ranges...................................9 4.2. DNDK-GCM Context and Options.............................11 4.3. The Preamble: Derive-L1-LN-L2-L3.........................12 4.4. Encryption...............................................14 4.5. Decryption...............................................15 4.6. DNDK-GCM Parameters......................................16 4.7. Using a Random Nonce and a Counter Nonce.................17 4.8. Usage Limits.............................................17 5. AEAD..........................................................18 6. Security Considerations.......................................19 6.1. Performing The Checks During Decryption..................19 6.1. The Key Commitment.......................................19 6.2. Security Bounds for DNDK-GCM.............................19 7. Design Rationale..............................................21 7.1. The DNDK-GCM overheads...................................23 8. IANA Considerations...........................................24 9. References....................................................24 9.1. Normative References.....................................24 9.2. Informative References...................................25 Appendix A. DNDK-GCM Encryption Worked-Out Examples..............27 A1. A Worked-Out Example (LN = 24; With Key Commitment).......27 A2. A Worked-Out Example (LN = 24; No Key Commitment).........29 A4. A Worked-Out Example (LN = 12; No Key Commitment).........34 Appendix B. A Python Script Reference Implementation Example.....37 10. Acknowledgments..............................................40 Gueron Expires September 21, 2025 [Page 3] Internet-Draft DNDK-GCM March 2025 11. Authors' Addresses...........................................40 1. Introduction Authenticated Encryption with Additional Data (AEAD) [RFC5116] is a fundamental cryptographic tool providing both confidentiality and integrity in a single scheme. AES-GCM [GCM] is one of the most widely used AEAD schemes, owing to its high performance on modern platforms with native instructions to accelerate AES computations and polynomial multiplications used for authentication. However, AES-GCM has notable limitations, including nonce length requirements and the absence of key commitment, which have led to the development of alternative approaches. 1.1. Limitation 1: Short Nonces Enforce Frequent Key Rotation AES-GCM is a nonce-respecting AEAD, meaning that a unique nonce must be used for each message encrypted under the same key. Reusing a nonce for different messages can lead to a severe compromise of both confidentiality and integrity. Applications can enforce nonce uniqueness by constructing nonces with a counter. However, in many real-world scenarios, maintaining state to track counters is costly or vulnerable to errors. In practice, systems often generate a random nonce for each message under the assumption that the probability of nonce collisions during the key's lifetime is sufficiently small. In this context, NIST's Special Publication 800-38D [GCM] states (Section 8) that: The probability that the authenticated encryption function will ever be invoked with the same IV and the 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 Gueron Expires September 21, 2025 [Page 4] Internet-Draft DNDK-GCM March 2025 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, and independently, the birthday bound limits the amount data that can be encrypted under a single key. 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 ciphertext-tag pair. As a result, a receiver decrypting a ciphertext with an unverifiable key might mistakenly accept a plaintext as valid, even if it was crafted by a malicious 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 for adding key commitment are detailed in [ADG+22], and some methods have already been deployed in cloud systems (e.g., AWS Encryption SDK [Gue20]). 1.3. DNDK-GCM Design Goals DNDK-GCM is designed to address the limitations of AES-GCM by: a) Minimizing performance overhead compared to AES-GCM. b) Reusing vetted and optimized AES-GCM implementations to leverage existing hardware instructions (e.g., AES-NI [Gue10] and PCLMULQDQ Gueron Expires September 21, 2025 [Page 5] Internet-Draft DNDK-GCM March 2025 [GK08]). c) Relying on widely accepted cryptographic assumptions for security. Namely, that the output of AES (with a uniform random key) is indistinguishable from the output of a uniform random 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 A byte is an integer between 0 and 255, commonly represented by two hexadecimal digits. For example, the decimal value 5 is represented as 0x05 in hexadecimal, and 135 is represented as 0x87. Let U be an array of bytes of length u. The bytes of U are indexed from 0 to u-1 and denoted as U[j], where j=0, 1, ..., u-1. Let T = U [a: b] denote the sub-array of U containing bytes from index a to b (inclusive), where 0 <= a <= b <= (u-1). The length of T is (b-a+1). For example, if U = [0x01, 0x02, 0x03, 0x04], then U[1:3] = [0x02, 0x03, 0x04]. For a = b, T = U [a: a] is U [a] and T = U [0: u-1] implies T = U. If a = b+1, the sub-array U[a:b] is defined as empty. Note: In this document, the two boundary indices in T [a: b] are inclusive, which differs from conventions in some (not all) programming languages, such as Python, where the upper boundary is Gueron Expires September 21, 2025 [Page 6] Internet-Draft DNDK-GCM March 2025 exclusive. Let U0 be an array of u0 bytes and U1 an array of u1 bytes. Suppose that 0 <= a1 <= b1 <=(u1-1), 0 <= a0 <= b0 <= (u0-1), and that b0 - a0 = b1 - a1 = s. Then, the notation U1 [a1: b1] = U0 [a0: b0] is an assignment that sets U1 [a1 + j] = U0 [a0 + j], j = 0, ..., s. Concatenation of arrays is denoted by "||". If U1 is an array of u1 bytes and U0 is an array of u0 bytes then U0 || U1 is the array W of u0+u1 bytes whose bytes are W [j] = U0 [j], j = 0, ... u0-1 and W [j] = U1 [j-u0], j = u0, ..., u0+u1-1. For example, if U0 = [0x01, 0x02] and U1 = [0x03, 0x04], then U0 || U1 = [0x01, 0x02, 0x03, 0x04. For an integer s, (0x00)^s denotes an array of s zero bytes. If s = 0, (0x00)^0 is defined as the empty string. An array of 16 bytes is also called a "block". Note that the bytewise specification of an array is agnostic to the way that the array is listed as a sequence (of bytes), i.e., whether byte 0 is in the rightmost or the leftmost position. The bytes positions in the sequence need to be specified unambiguously. Example. Let U0 be an array of length u0 = 16 (block), listed as follows: byte index (position) 00010203040506070809101112131415 U0 = 3dfcc48e6cf4e1d25a8ff0de58c97a69 (i.e., U0 [00] = 0x3d, U0 [07] = 0xd2, U0 [15] = 0x69). Then, byte index (position) 00010203040506070809101112131415 U0 [00: 15] = 3dfcc48e6cf4e1d25a8ff0de58c97a69 U0 [00: 07] = 3dfcc48e6cf4e1d2 Gueron Expires September 21, 2025 [Page 7] Internet-Draft DNDK-GCM March 2025 U0 [08: 15] = 5a8ff0de58c97a69 U0 [12: 14] = 58c973 U0 [13: 13] = c9 U0 [01: 00] = Let U1 be an array of 16 bytes. The assignment U1 [4: 6] = U0 [12: 14] determines 3 bytes of U1 as follows: byte index (position) 00010203040506070809101112131415 U1 = ********58c97a****************** (the unspecified bytes are denoted by "**") The symbol FAIL is used here to indicate a failed integrity check. The symbol != is the "not-equal" operator. 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 Z is an array of 16 bytes, then C = AES (K, Z) is the 16-byte array that results from encrypting Z with AES under the key K. Here, AES-GCM refers to the Authenticated Encryption with Additional 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, P) and (N, A, C, T), respectively, where N is a nonce, A is the Additional Authenticated Data (AAD), P is the plaintext 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 P (and C) is an array of at most 2^36 - 32 bytes. AES-GCM.Enc outputs the pair (C, T), which explicitly identifies the ciphertext and the tag. Equivalently, it is possible to view the concatenation of C, T (i.e., Gueron Expires September 21, 2025 [Page 8] Internet-Draft DNDK-GCM March 2025 (C || T || KC) as a single array that is called "ciphertext-blob" (and parsed accordingly). From this perspective, AES-GCM.Enc produces a single output (ciphertext-blob), while AES-GCM.Dec takes three inputs (N, A, ciphertext-blob). 4. DNDK-GCM Definition 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. - K_LEN: Length of the root key (in bytes). - N_LEN: Length of the nonce (in bytes). - A_MAX: Maximum length of Additional Authenticated Data (AAD). - P_MAX: Maximum length of plaintext. - C_MAX: Maximum length of ciphertext. - T_LEN: Length of the authentication tag (in bytes). - KC_LEN: Length of the key commitment value (in bytes). 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 as input a tuple (K, N, A, P) where K is the secret (root) key, N is the (randomly selected) nonce, A is the AAD, and P is the plaintext message. It outputs ciphertext C, an Gueron Expires September 21, 2025 [Page 9] Internet-Draft DNDK-GCM March 2025 authentication tag T and a commitment value KC (that may optionally be an empty array). In this notation, C, T, KC are explicitly identified and named, and the length of C is the same as the length of P. Equivalently, it is possible to view the concatenation of C, T, KC as a single array of bytes (parsed accordingly with the matching offsets for C, T, and KC) called "ciphertext-blob". Under this view, DNDK- GCM.Enc has a single output (namely ciphertext-blob) and the byte- length of ciphertext-blob equals to the length of P plus 48 when KC is not empty, and equals to the length of P plus 16 when KC is empty. 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 plaintext message P with the same byte-length as C, or a failure indication (FAIL). Equivalently, if the concatenation of C, T, KC is viewed as a single array "ciphertext-blob", DNDK-GCM.Dec has four inputs (namely K, N, A, ciphertext-blob). The root key (K) MUST consist of K_LEN bytes. It MUST be generated in a uniformly random (or pseudorandom) way and known only to the parties (sender and recipient) using the scheme. The nonce (N) MUST consist of N_LEN bytes preferably selected uniformly at random for every encryption. 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, P, C may be empty. Inputs to DNDK-GCM.Enc and to DNDK-GCM.Dec are assumed to be valid Gueron Expires September 21, 2025 [Page 10] Internet-Draft DNDK-GCM March 2025 and within the defined range of lengths (i.e., DNDK-GCM.Enc and DNDK- GCM.Dec check the inputs and abort if they are invalid). Tag truncation: The AES-GCM specification [GCM] (Section 5.2.1.2) permits 16-byte tags to be truncated to 12 bytes or even shorter tags of 8 or 4 bytes, where these lengths are accepted subject to the usage constraints outlined 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 innocuous truncation to 12 bytes). However, DNDK-GCM usages that require (and settle with) a shorter tag of d < 16 bytes, MAY truncate it to d = 12, 8, or 4 bytes as specified in [GCM]. The formatting and agreement of such truncation is left for the communicating parties or protocol. 4.2. DNDK-GCM Context and Options The DNDK-GCM context is KC_Choice (either 0 or 1) and LN (12 <= LN <= 27). These parameters determine the scheme's configuration as follows: The choice KC_Choice = 0 indicates that a commitment value (KC) is neither computed nor output by DNDK-GCM.Enc and is not required as input to DNDK-GCM.Dec. Equivalently, KC is an empty byte array. The choice KC_Choice = 1 indicates that a KC value is computed, KC is part of the DNDK-GCM.Enc output and KC is a required input for DNDK-GCM.Dec. LN is the byte-length of the nonce. A DNDK-GCM root key MUST be used with only one configuration that is pre-agreed by the communicating parties that use the scheme. Gueron Expires September 21, 2025 [Page 11] Internet-Draft DNDK-GCM March 2025 4.3. The Preamble: Derive-L1-LN-L2-L3 The algorithm "Derive-L1-LN-L2-L3" that takes a root key (K) of L1 bytes and a nonce (N) of LN bytes (12 <= LN <= 27). It outputs a derived key (DerivedKey) of L2 bytes and (optionally, depending on KC_Choice) a key commitment value (KeyCommit) of L3 bytes. This document sets the parameter values to L1 = L2 = L3 = 32. For brevity, Derive-32-24-32-32 is referred to as "Derive". If LN < 27, Derive appends (27-LN) zero bytes to N to define a 27- byte array named NPadded. If LN = 27, NPadded = N. The sub-array of the first 15 bytes of NPadded is called NHead, and the sub-array of the remaining 12 bytes is called NTail. Derive uses the 15 bytes of NHead and "ConfigByte", a byte that encodes KC_Choice and LN. It applies the XORP pseudorandom function (defined in [Iwa06], section 3, under the name 'F') with the root key K and the block NHead || ConfigByte and produces a 32-byte DerivedKey and (optionally) a 32-byte KeyCommit. ConfigByte is defined by ConfigByte = 128 * KC_Choice + 8 * (LN - 12) ConfigByte is divisible by 8 so its three least significant bits are zero. Thus, for all 0 <= w <= 7, the bytes ConfigByte and (ConfigByte + w) have the same five most significant bits. For example, with KC_Choice = 1 and LN = 24, ConfigByte = 0xe0 (=224) and (ConfigByte + 4) = 0xe4 (=228). With KC_Choice = 0 and LN = 24, ConfigByte = 0x60 (=96) and (ConfigByte + 3) = 0x63 (=99). Gueron Expires September 21, 2025 [Page 12] Internet-Draft DNDK-GCM March 2025 Derive also produces NTail as the 12-byte value GCM_IV that is subsequently used for the AES-GCM call. Algorithm1 1 defines Derive. +-----------------------------------------------------------------+ Algorithm 1. Derive (K, N) Input: K (root key), N (array of LN bytes) Context: KC_Choice, LN LN = len (N) NPadded = N || (0x00)^(27-LN) NHead = NPadded [0: 14] NTail = NPadded [15: 26] GCM_IV = NTail ConfigByte = 128 * KC_Choice + 8 * (LN - 12) B0 = NHead || (ConfigByte + 0) B1 = NHead || (ConfigByte + 1) B2 = NHead || (ConfigByte + 2) if KC_Choice = 1: B3 = NHead || (ConfigByte + 3) B4 = NHead || (ConfigByte + 4) X0 = AES (K, B0) X1 = AES (K, B1) Gueron Expires September 21, 2025 [Page 13] Internet-Draft DNDK-GCM March 2025 X2 = AES (K, B2) if KC_Choice = 1: X3 = AES (K, B3) X4 = AES (K, B4) Y1 = X1 XOR X0 Y2 = X2 XOR X0 DerivedKey = Y1 || Y2 KeyCommit = (0x00)^0 if KC_Choice = 1: Y3 = X3 XOR X0 Y4 = X4 XOR X0 KeyCommit = Y3 || Y4 Output: (GCM_IV, DerivedKey, KeyCommit) +-----------------------------------------------------------------+ 4.4. Encryption DNDK-GCM.Enc receives the tuple (K, N, A, P) as input. It first runs the preamble Derive over K and N to compute GCM_IV, a derived key (DK) and if KC_Choice = 1, a 32-byte key commitment value (KC). It then invokes AES-GCM.Enc using DK as the encryption key, the 12-byte nonce CCM_IV, A, and P. This produces the ciphertext C with the same length as P and the authentication tag T. The output is C, T, KC (or, equivalently, C || T || KC) if viewed as a single array called ciphertext-blob. Recall that if KC_Choice = 0 KC is the empty array. This allows for writing the output of DNDK-GCM.Enc as C, T, KC (equivalently C || T || KC) for both values of KC_Choice. Gueron Expires September 21, 2025 [Page 14] Internet-Draft DNDK-GCM March 2025 DNDK-GCM.Enc is defined by Algorithm 2. +-----------------------------------------------------------------+ Algorithm 2. DNDK-GCM.Enc Input: K, N, A, P Context: KC_Choice, LN (GCM_IV, DK, KC) = Derive (K, N) (C, T) = AES-GCM.Enc (DK, GCM_IV, A, P) Output: C, T, KC +-----------------------------------------------------------------+ 4.5. Decryption DNDK-GCM.Dec receives the tuple (K, N, A, C, T, KC) as input (or equivalently, C || T || KC as a ciphertext blob). It first runs the preamble "Derive" on K and N to compute GCM_IV, a derived key (DK), and, if KC_Choice = 1, a 32-byte key commitment value candidate (KC'). If KC != KC', decryption fails. In this case, DNDK-GCM.Dec terminates immediately without executing AES-GCM.Dec and outputs FAIL. Alternatively, to avoid an early exit, DNDK-GCM.Dec can proceed with AES-GCM.Dec but force a failure indication FAIL, regardless of the decryption result. In both cases, DNDK-GCM.Dec outputs FAIL if KC != KC'. AES-GCM.Dec is then invoked using DK as the decryption key, GCM_IV (a 12-byte nonce), A, C, and T. This process either retrieves a message P (with the same length as C) or returns an authentication failure indication. The final output of DNDK-GCM.Dec is P (only if KC = KC' and AES-GCM authentication succeeds) or FAIL. Gueron Expires September 21, 2025 [Page 15] Internet-Draft DNDK-GCM March 2025 Notably, AES-GCM.Dec does not release any part of P until full authentication is complete. The early-exit variant of DNDK-GCM.Dec is defined in Algorithm 3. +-----------------------------------------------------------------+ Algorithm 3. DNDK-GCM.Dec Input: K, N, A, C, T, KC Context: KC_Choice, LN (GCM_IV, DK, KC') = Derive (K, N) If KC' != KC output FAIL and abort P / FAIL = AES-GCM.Dec (DK, GCM_IV, A, C, T) Output: P or FAIL +-----------------------------------------------------------------+ Appendix A provides step-by-step detailed examples with the intermediate values. Appendix B provides a reference Python script implementation (that produces the values shown in Appendix A1). Note about comparison and side channels: The comparison of the received key commitment value (KC) with the recomputed value (KC') MUST be performed in a manner that is free from side-channel leaks, especially timing attacks. For example, if an implementation compares KC and KC' byte by byte and exits at the first mismatch, an adversary could guess the correct value of KC one byte at a time. To prevent this, the comparison should be performed in constant time. 4.6. DNDK-GCM Parameters DNDK-GCM is defined with the following parameter values: K_LEN = 32, Gueron Expires September 21, 2025 [Page 16] Internet-Draft DNDK-GCM March 2025 A_MAX = 2^61 - 1, P_MAX = 2^36 - 32, C_MAX = 2^36 - 32, T_LEN = 16, and KC_LEN = 32. Although Algorithms 1, 2, 3 are defined for any N_LEN = LN such that 12 <= LN <= 27, DNDK-GCM is constrained here only to the two options, N_LEN = LN = 24 and N_LEN = LN = 12. 4.7. Using a Random Nonce and a Counter Nonce DNDK-GCM is a nonce respecting AEAD and therefore, for a given root key, DNDK-GCM.Enc must use unique nonces. The main goal of the DNDK-GCM design is to support the random nonce scenario where the LN-byte nonce N is chosen uniformly at random. The use of sufficiently long random nonces (e.g., LN = 24) makes the nonce collision probability below the maximum acceptable threshold (e.g., 2^-32) during the allowed lifetime of the root key. When LN = 12, the nonce collision probability is the same as the nonce collision probability of AES-GCM (with a 12-byte nonce). DNDK-GCM can be used in the non-repeating but non-random nonce selection ("counter nonce") scenario. For such usage, it is RECOMMENDED to construct the nonce N such that the values of NHead = NPadded [0: 14] never repeat. Such a nonce selection is called "unique NHead nonce". Since the usage of a counter nonce requires maintaining a state, there should be no difficulty with using unique NHead nonces. A possible example, for the case of LN = 24, is to set the nonce for the i-th invocation of DNDK-GCM.Enc, to Ni = encode (i, 12) || (0x00)^(LN-12) 4.8. Usage Limits Gueron Expires September 21, 2025 [Page 17] Internet-Draft DNDK-GCM March 2025 This section describes the limits on the DNDK-GCM usage with a given root key. In the random nonce settings: for LN = 24, a given root key can be used for encrypting as many as 2^64 messages while processing up to 2^64 plaintext blocks. For LN = 12, a given root key can be used for encrypting at most 2^32.5 messages. In the unique NHead counter nonce settings: for LN = 24 and LN = 12, a given root key can be used for encrypting as many as 2^64 messages while processing up to 2^64 plaintext blocks. 5. AEAD We define four AEADs, in the format of [RFC5116], that use DNDK-GCM, namely AEAD_DNDK_GCM_LN_24_KC_1, AEAD_DNDK_GCM_LN_24_KC_0, AEAD_DNDK_GCM_LN_12_KC_1, and AEAD_DNDK_GCM_LN_12_KC_0. The common parameters for these fourAEADs are as follows: K_LEN = 32, A_MAX = 2^61 - 1, P_MAX = 2^36 - 32, C_MAX = 2^36 - 32, T_LEN = 16. They differ in the parameters N_LEN and KC_LEN as follows: For AEAD_DNDK_GCM_LN_24_KC_1, N_LEN = 24, and KC_LEN = 32. For AEAD_DNDK_GCM_LN_24_KC_0, N_LEN = 24, and KC_LEN = 0. For AEAD_DNDK_GCM_LN_12_KC_1, N_LEN = 12, and KC_LEN = 32. For AEAD_DNDK_GCM_LN_12_KC_0, N_LEN = 12, and KC_LEN = 0. Gueron Expires September 21, 2025 [Page 18] Internet-Draft DNDK-GCM March 2025 6. Security Considerations 6.1. Performing The Checks During Decryption DNDK-GCM decryption involves two checks: Check 1. matching the input key commitment value with the computed key commitment value. Check 2. matching the input authentication tag when AES-GCM.Dec is invoked. Both checks must be performed, and no part of the plaintext should be released until they both pass. An implementation of AES-GCM.Dec MAY continue the computations even if the first check fails, to release the failure indication only after executing AES-GCM. Note that the first check is bypassed if KC_Choice = 0 (i.e., the most significant bit of ConfigByte equals 0), indicating no key commitment is required. 6.1. The Key Commitment To find two (adversarial) root keys K1, K2, and two nonce-AAD- plaintext triples N1, A1, P1, N2, A2, P2, such that DNDK-GCM.Enc (K1, N1, A1, P1) = DNDK-GCM.Enc (K2, N2, A2, P2), an adversary needs to match the 32-byte key commitment values as defined by Derive. 6.2. Security Bounds for DNDK-GCM Suppose that DNDK-GCM is used for encrypting Q <= 2^64 messages (Nj, Aj, Mj) where Mj consists of Lj <= Lm blocks and Aj consists of at most La blocks, j = 1, ... , Q. Assume that the PRP advantage of AES (in this multikey setting) is negligible for such Q and Lm. Gueron Expires September 21, 2025 [Page 19] Internet-Draft DNDK-GCM March 2025 Derive is an instantiation of the XORP construction [Iwa06] with parameter w <= 4, which is run over NHeadj = NPaddedj [0: 14] || ConfigByte where NPaddedj = Nj || (0x00)^(27-LN) The distinguishing advantage of an adversary observing XORP samples over at most Q distinct NHeadj values is at most w^2 Q/2^(128), which, for w <= 4 is at most Q/2^(124) and is negligible for Q <= 2^64 (see [IMC16]). Up to this advantage, the sequence of (at most Q) derived keys from (at most Q) distinct NHeadj values is indistinguishable from a sequence of (at most Q) uniform random 32-byte values. The probability to encounter a collision in a uniform random 32-byte sequence is at most Q^2/2^(257) <= 2^(-129). In the unique NHead nonce setting, all the values of NHeadj are, by definition, distinct. Thus, up to the probability of 2^(-129) plus the XORP distinguishing advantage, the derived keys are distinct. Hence, in this scenario every derived key is used for encrypting exactly one message. In the random nonce scenario with LN = 24, the probability of a nonce collision is at most Q^2/2^(193) <= 2^(-65). Here, the NHeadj values are not necessarily distinct when Q <= 2^(64) is large, but the probability to encounter a 3-way collision across the NHeadj values (i.e., 0 <= i < j < k <= Q such that NHeadi = NHeadj = NHeadk) is at most Q^3/(6 * 2^(240)) <= 2^(-50). Therefore, with a probability of at most 2^(-65) + 2^(-50) (in addition to the XORP distinguishing advantage), every derived key is used to encrypt at most two messages. In fact, for large Q, the vast majority of the derived keys Gueron Expires September 21, 2025 [Page 20] Internet-Draft DNDK-GCM March 2025 are used for encrypting only one message. It follows that (up to some small probability), DNDK-GCM can be viewed as AES-GCM in a multi-key scenario, where every key is used for encrypting at most two messages (of length <= Lmax blocks). Note that if Nj != Nk for some 1 <= j < k <= Q and NHeadj = NHeadk, then NTailj != NTailk. This implies that AES-GCM is invoked with the same derived key, but with distinct GCM_IV values. Under these conditions, the distinguishing advantage of passively viewed ciphertext-tag(-Commitment) tuples from chosen inputs, and uniform random strings of the matching lengths, is dominated by Q (Lm + 2)^2 / 2^128 This upper bound can be further refined. For integrity, an adversary that views Q <= 2^(64) encryption results and tries a total of Q' <= 2^(64) forgery attempts has a forgery success probability of at most Q' * (Lm + La + 1) / 2^(127) A detailed analysis is available in [Gue25]. 7. Design Rationale The main goal of the DNDK-GCM design is to address the short nonce limitation of AES-GCM in the random nonce setting. To this end, DNDK- GCM supports a double-length nonce of 24 bytes, where the probability to encounter a nonce collision in Q uniform random samples is upper bounded by Q^2/2^193, which is negligible for Q <= 2^(64). Gueron Expires September 21, 2025 [Page 21] Internet-Draft DNDK-GCM March 2025 The DNDK-GCM design extends the Derive-Key approach of [GL17], where the Derive function and the underlying AEAD share the same nonce, as seen in AES-GCM-SIV [RFC8452], which utilizes a 12-byte nonce. To enable using a 16-bytes permutation (AES) as a primitive, Derive operates over a sub-array of NPadded, namely NHead, that is strictly shorter than a single block. The DNDK-GCM design chooses the longest possible such subarray, i.e. a 15-byte NHead. It populates a block with NHead and uses the remaining byte for encoding KC_Choice, LN, and while leaving 3 bits for a counter (counting from 0 to 2 or 4). The remaining nine bytes of NPadded (NTail) are used as the AES-GCM IV that is invoked with the derived key. In the random nonce setting, splitting NPadded into a 15-byte NHead and a 12-byte NTail minimizes the key collision and the 3-way key collision probabilities. This lowers the upper bounds on the distinguishing advantage of DNDK-GCM outputs from uniform random strings and allows for processing a very large number of messages and a very large amount of data under a given root key. In the counter nonce setting, DNDK-GCM is a nonce respecting AEAD. Note that invocations of DNDK-GCM.Enc can choose to fix the 15-byte NHead and place a counter in NTail. This would fix the derived key and yield security bounds that are similar to those of AES-GCM (with a counter nonce). However, this is a non-optimal way to construct counter nonces and much better bounds are achieved in the unique NHead nonce settings where all the NHead values are, by definition, distinct. With the choice LN = 12 and the counter nonce setting, DNDK-GCM reduces the upper bounds on the ciphertext indistinguishability compared to plain AES-GCM. This may justify the Derive overhead while using only 12-byte nonces. In the random nonce setting, both AEADs have the same limitations on the amounts of processed data and number of messages. In this case, DNDK-GCM is defined only for completeness. Gueron Expires September 21, 2025 [Page 22] Internet-Draft DNDK-GCM March 2025 DNDK-GCM employs the Beyond-Birthday-Bound (BBB) pseudorandom function XORP [Iwa06], which requires only 5 (or 3 without key commitment) AES calls to output the required 64 bytes (or 32 bytes without key commitment). It can be argued that a non-BBB Derive that is based on a counter mode (using only 4 (or 2) AES calls) also suffices. However, in this case, the derived keys are sampled from only a subset of the key space (all 32-byte arrays), and a justification would require some non-standard assumption on AES. Incorporating KC_Choice and the key commitment into the configuration byte ConfigByte = 128 * KC_Choice + 8 * (LN - 12) creates a domain separation that leads to different derived keys per configuration. Domain separation: The scheme as specified in a way that whether (or not) a key commitment (KC) is computed, is supposed to be part of the agreed configuration between sender and recipient. Nevertheless, this choice it is also encoded in the ConfigByte, and thus impacts the derived AES-GCM key. To argue why such a domain separation is desirable, we note that this feature provides a sort of cryptographic verification that the sender and recipient have actually agreed on the configuration. This may help detect mismatches, for example if encryption is computed with KC_Choice = 1 but KC is omitted from the blob that is submitted for decryption. 7.1. The DNDK-GCM overheads This section describes the overheads of DNDK-GCM compared to AES-GCM (with a 32-byte key). The function Derive requires 5 calls to AES256 with the root key if KC_Choice = 1, and 3 calls if KC_Choice = 0. These AES256 computations are executed over independent blocks and can be parallelized for better performance. In addition, every encryption (and decryption) requires an AES256 key Gueron Expires September 21, 2025 [Page 23] Internet-Draft DNDK-GCM March 2025 expansion with the fresh derived key (and other initialization steps for AES-GCM). This computational overhead is independent of the nonce length (LN). The total overhead is relatively small (see [Gue25] for a full account). 8. IANA Considerations 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 FIPS 197 standard (2001) was superseded in May 2023; the updated 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 [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 [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: Gueron Expires September 21, 2025 [Page 25] Internet-Draft DNDK-GCM March 2025 https://eprint.iacr.org/2020/1153 [Gue25] Gueron, S., "Generalized Nonce-Based Key Derivation AEAD Constructions and Double Nonce Derive Key AES-GCM", Cryptology ePrint Archive, Paper 2025/TBD, 2025. [Online]. To be available on https://eprint.iacr.org/2025/ [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 Gueron Expires September 21, 2025 [Page 26] Internet-Draft DNDK-GCM March 2025 [IMC16] Iwata, T., Mennink, B., and Vizar, D., "CENC is Optimally Secure," Cryptology ePrint Archive, Paper 2016/1087, 2016. [Online]. Available: https://eprint.iacr.org/2016/1087 Appendix A. DNDK-GCM Encryption Worked-Out Examples This appendix provides DNDK-GCM encryption examples. Arrays of bytes are typed in increasing order of byte positions from left (byte 0) to right. A1. A Worked-Out Example (LN = 24; With Key Commitment) =================================================================== DNDK-GCM example =================================================================== Nonce length (LN) = 24 KC_Choice = 1 =================================================================== ---------Bytes Position--------- 00010203040506070809101112131415 ...16171819202121232425262728293031 -------------------------------- -------------------------------- Root key = 01000000000000000000000000000000 00000000000000000000000000000000 ------------------------------------------------------------------- Input ------------------------------------------------------------------- Nonce = 000102030405060708090a0b0c0d0e0f 1011121314151617 Gueron Expires September 21, 2025 [Page 27] Internet-Draft DNDK-GCM March 2025 aad (5 bytes) = 0100000011 plaintext (4 bytes) = 11000001 ------------------------------------------------------------------- Output ------------------------------------------------------------------- cipher (4 bytes) = 8eee8a4b tag = 8a1c8d0ceb7e07e3c834cafe75aa001f Key commitment value = 2baf00efd298de13055c9a6c39e05aee 571583384357635e144fa21444239968 ------------------------------------------------------------------- ciphertext tag (20 bytes) = 8eee8a4b8a1c8d0ceb7e07e3c834cafe 75aa001f ------------------------------------------------------------------- ciphertext tag commit (52 bytes) = 8eee8a4b8a1c8d0ceb7e07e3c834cafe 75aa001f2baf00efd298de13055c9a6c 39e05aee571583384357635e144fa214 44239968 ------------------------------------------------------------------- Intermediate values ------------------------------------------------------------------- DerivedKey = 3d1480ee39a968d581d16a578bdaf0e6 719dcfff6e127b40bbdd844accea7e1c AES-GCM nonce = 0f1011121314151617000000 Nonce PAD length (bytes) = 3 Padded nonce (NPadded) = 000102030405060708090a0b0c0d0e0f 1011121314151617000000 ConfigByte 128 * KC_Choice + 8 * (LN - 12) as int = 224 Gueron Expires September 21, 2025 [Page 28] Internet-Draft DNDK-GCM March 2025 in hex = e0 =================================================================== B0 = 000102030405060708090a0b0c0d0ee0 X0 = cd8a6170df972d556ae1eaf9ea9bd799 ConfigBytePlus0 = e0 B1 = 000102030405060708090a0b0c0d0ee1 X1 = f09ee19ee63e4580eb3080ae6141277f ConfigBytePlus1 = e1 B2 = 000102030405060708090a0b0c0d0ee2 X2 = bc17ae8fb1855615d13c6eb32671a985 ConfigBytePlus2 = e2 B3 = 000102030405060708090a0b0c0d0ee3 X3 = e625619f0d0ff3466fbd7095d37b8d77 ConfigBytePlus3 = e3 B4 = 000102030405060708090a0b0c0d0ee4 X4 = 9a9fe2489cc04e0b7eae48edaeb84ef1 ConfigBytePlus4 = e4 Y1 = 3d1480ee39a968d581d16a578bdaf0e6 Y2 = 719dcfff6e127b40bbdd844accea7e1c DerivedKey (= Y1 || Y2) = 3d1480ee39a968d581d16a578bdaf0e6 719dcfff6e127b40bbdd844accea7e1c Y3 = 2baf00efd298de13055c9a6c39e05aee Y4 = 571583384357635e144fa21444239968 KeyCommit (= Y3 || Y4) = 2baf00efd298de13055c9a6c39e05aee 571583384357635e144fa21444239968 ------------------------------------------------------------------- A2. A Worked-Out Example (LN = 24; No Key Commitment) Gueron Expires September 21, 2025 [Page 29] Internet-Draft DNDK-GCM March 2025 =================================================================== DNDK-GCM example =================================================================== Nonce length (LN) = 24 KC_Choice = 0 =================================================================== ---------Bytes Position--------- 00010203040506070809101112131415 ...16171819202121232425262728293031 -------------------------------- -------------------------------- Root key = 01000000000000000000000000000000 00000000000000000000000000000000 ------------------------------------------------------------------- Input ------------------------------------------------------------------- Nonce = 000102030405060708090a0b0c0d0e0f 1011121314151617 aad (5 bytes) = 0100000011 plaintext (4 bytes) = 11000001 ------------------------------------------------------------------- Output ------------------------------------------------------------------- cipher (4 bytes) = 7f6e39cc tag = b61df0a502c167164e99fa23b7d12b9d Key commitment value = ------------------------------------------------------------------- ciphertext tag (20 bytes) = 7f6e39ccb61df0a502c167164e99fa23 Gueron Expires September 21, 2025 [Page 30] Internet-Draft DNDK-GCM March 2025 b7d12b9d ------------------------------------------------------------------- ciphertext tag commit (20 bytes) = 7f6e39ccb61df0a502c167164e99fa23 b7d12b9d ------------------------------------------------------------------- Intermediate values ------------------------------------------------------------------- DerivedKey = d974a46fbbeb3dec953ce088ef6b6085 73248947acf51606de5a1e5b72629197 AES-GCM nonce = 0f1011121314151617000000 Nonce PAD length (bytes) = 3 Padded nonce (NPadded) = 000102030405060708090a0b0c0d0e0f 1011121314151617000000 ConfigByte 128 * KC_Choice + 8 * (LN - 12) as int = 96 in hex = 60 =================================================================== B0 = 000102030405060708090a0b0c0d0e60 X0 = d3a8349b7cd72d37e061b49c3c5d2c12 ConfigBytePlus0 = 60 B1 = 000102030405060708090a0b0c0d0e61 X1 = 0adc90f4c73c10db755d5414d3364c97 ConfigBytePlus1 = 61 B2 = 000102030405060708090a0b0c0d0e62 X2 = a08cbddcd0223b313e3baac74e3fbd85 ConfigBytePlus2 = 62 Gueron Expires September 21, 2025 [Page 31] Internet-Draft DNDK-GCM March 2025 Y1 = d974a46fbbeb3dec953ce088ef6b6085 Y2 = 73248947acf51606de5a1e5b72629197 DerivedKey (= Y1 || Y2) = d974a46fbbeb3dec953ce088ef6b6085 73248947acf51606de5a1e5b72629197 KeyCommit (= Y3 || Y4) = ------------------------------------------------------------------- A3. A Worked-Out Example (LN = 12; With Key Commitment) =================================================================== DNDK-GCM example =================================================================== Nonce length (LN) = 12 KC_Choice = 1 =================================================================== ---------Bytes Position--------- 00010203040506070809101112131415 ...16171819202121232425262728293031 -------------------------------- -------------------------------- Root key = 01000000000000000000000000000000 00000000000000000000000000000000 ------------------------------------------------------------------- Input ------------------------------------------------------------------- Nonce = 000102030405060708090a0b aad (5 bytes) = 0100000011 plaintext (4 bytes) = 11000001 Gueron Expires September 21, 2025 [Page 32] Internet-Draft DNDK-GCM March 2025 ------------------------------------------------------------------- Output ------------------------------------------------------------------- cipher (4 bytes) = 1915d0bd tag = 187b392eeb9b231a57a852db20e02201 Key commitment value = 675fb3ec6d0e56002333c2504d1b70db 47c3713775999c9600bedcfda76f8d8c ------------------------------------------------------------------- ciphertext tag (20 bytes) = 1915d0bd187b392eeb9b231a57a852db 20e02201 ------------------------------------------------------------------- ciphertext tag commit (52 bytes) = 1915d0bd187b392eeb9b231a57a852db 20e02201675fb3ec6d0e56002333c250 4d1b70db47c3713775999c9600bedcfd a76f8d8c ------------------------------------------------------------------- Intermediate values ------------------------------------------------------------------- DerivedKey = dfde3c721be6e0b0369770788941a293 96c4e50dd81725d3832221fa47d564e1 AES-GCM nonce = 000000000000000000000000 Nonce PAD length (bytes) = 15 Padded nonce (NPadded) = 000102030405060708090a0b00000000 0000000000000000000000 ConfigByte 128 * KC_Choice + 8 * (LN - 12) as int = 128 in hex = 80 =================================================================== Gueron Expires September 21, 2025 [Page 33] Internet-Draft DNDK-GCM March 2025 B0 = 000102030405060708090a0b00000080 X0 = 78d5b87c1bf1f2ee7de63d4899309b82 ConfigBytePlus0 = 80 B1 = 000102030405060708090a0b00000081 X1 = a70b840e0017125e4b714d3010713911 ConfigBytePlus1 = 81 B2 = 000102030405060708090a0b00000082 X2 = ee115d71c3e6d73dfec41cb2dee5ff63 ConfigBytePlus2 = 82 B3 = 000102030405060708090a0b00000083 X3 = 1f8a0b9076ffa4ee5ed5ff18d42beb59 ConfigBytePlus3 = 83 B4 = 000102030405060708090a0b00000084 X4 = 3f16c94b6e686e787d58e1b53e5f160e ConfigBytePlus4 = 84 Y1 = dfde3c721be6e0b0369770788941a293 Y2 = 96c4e50dd81725d3832221fa47d564e1 DerivedKey (= Y1 || Y2) = dfde3c721be6e0b0369770788941a293 96c4e50dd81725d3832221fa47d564e1 Y3 = 675fb3ec6d0e56002333c2504d1b70db Y4 = 47c3713775999c9600bedcfda76f8d8c KeyCommit (= Y3 || Y4) = 675fb3ec6d0e56002333c2504d1b70db 47c3713775999c9600bedcfda76f8d8c ------------------------------------------------------------------- A4. A Worked-Out Example (LN = 12; No Key Commitment) =================================================================== DNDK-GCM example Gueron Expires September 21, 2025 [Page 34] Internet-Draft DNDK-GCM March 2025 =================================================================== Nonce length (LN) = 12 KC_Choice = 0 =================================================================== ---------Bytes Position--------- 00010203040506070809101112131415 ...16171819202121232425262728293031 -------------------------------- -------------------------------- Root key = 01000000000000000000000000000000 00000000000000000000000000000000 ------------------------------------------------------------------- Input ------------------------------------------------------------------- Nonce = 000102030405060708090a0b aad (5 bytes) = 0100000011 plaintext (4 bytes) = 11000001 ------------------------------------------------------------------- Output ------------------------------------------------------------------- cipher (4 bytes) = b95cf258 tag = 39e74511d997eaafd0f567d13758305b Key commitment value = ------------------------------------------------------------------- ciphertext tag (20 bytes) = b95cf25839e74511d997eaafd0f567d1 3758305b ------------------------------------------------------------------- ciphertext tag commit Gueron Expires September 21, 2025 [Page 35] Internet-Draft DNDK-GCM March 2025 (20 bytes) = b95cf25839e74511d997eaafd0f567d1 3758305b ------------------------------------------------------------------- Intermediate values ------------------------------------------------------------------- DerivedKey = 13c31bcaf1f11785e1dcb29d5d65541a 4b371b1142bb60f39cea823f189e0a17 AES-GCM nonce = 000000000000000000000000 Nonce PAD length (bytes) = 15 Padded nonce (NPadded) = 000102030405060708090a0b00000000 0000000000000000000000 ConfigByte 128 * KC_Choice + 8 * (LN - 12) as int = 0 in hex = 00 =================================================================== B0 = 000102030405060708090a0b00000000 X0 = e794aa3c8558d394f822920ae2a9d6e5 ConfigBytePlus0 = 00 B1 = 000102030405060708090a0b00000001 X1 = f457b1f674a9c41119fe2097bfcc82ff ConfigBytePlus1 = 01 B2 = 000102030405060708090a0b00000002 X2 = aca3b12dc7e3b36764c81035fa37dcf2 ConfigBytePlus2 = 02 Y1 = 13c31bcaf1f11785e1dcb29d5d65541a Y2 = 4b371b1142bb60f39cea823f189e0a17 DerivedKey (= Y1 || Y2) = Gueron Expires September 21, 2025 [Page 36] Internet-Draft DNDK-GCM March 2025 13c31bcaf1f11785e1dcb29d5d65541a 4b371b1142bb60f39cea823f189e0a17 KeyCommit (= Y3 || Y4) = ------------------------------------------------------------------- Appendix B. A Python Script Reference Implementation Example This Appendix provides a Python script implementation of DNDK-GCM (the variant with the key commitment). The inputs that produce the values reported in Appendix A (LN = 24 and KC_Choice = 1) # DNDK-GCM encryption example from Cryptodome.Cipher import AES # Root key RootKey = \ 0x0100000000000000000000000000000000000000000000000000000000000000.\ to_bytes(32,'big') # Nonce (24 bytes) N =\ 0x000102030405060708090a0b0c0d0e0f1011121314151617.\ to_bytes(24,'big') ''' # The 12-byte case ################## # Nonce (12 bytes) N =\ 0x000102030405060708090a0b.\ to_bytes(12,'big') ################## ''' Gueron Expires September 21, 2025 [Page 37] Internet-Draft DNDK-GCM March 2025 # aad and plaintext aad = 0x0100000011.to_bytes(5,'big') plaintext = 0x11000001.to_bytes(4,'big') # # Configuration # LN = len (N) KC_Choice = 0 # 1/0 with/without key commitment PADLEN = 27-LN NPadded = N + (0x00).to_bytes (PADLEN, 'big') NHead = NPadded [0: 15] # The first 15 bytes of the nonce NTail = NPadded [15: 27] ###GCM_IV = NTail + (0x00).to_bytes (3, 'big') GCM_IV = NTail # Preparing blocks B0, B1, B2, B3, B4 for XORP Configurenum = 128 * KC_Choice + 8*(LN-12) ConfigBytePlus0 = (Configurenum + 0).to_bytes (1, 'big') B0 = NHead + ConfigBytePlus0 ConfigBytePlus1 = (Configurenum + 1).to_bytes (1, 'big') B1 = NHead + ConfigBytePlus1 ConfigBytePlus2 = (Configurenum + 2).to_bytes (1, 'big') B2 = NHead + ConfigBytePlus2 if KC_Choice == 1: ConfigBytePlus3 = (Configurenum + 3).to_bytes (1, 'big') B3 = NHead + ConfigBytePlus3 ConfigBytePlus4 = (Configurenum + 4).to_bytes (1, 'big') B4 = NHead + ConfigBytePlus4 # # X values Gueron Expires September 21, 2025 [Page 38] Internet-Draft DNDK-GCM March 2025 rootcipher = AES.new(key=RootKey, mode=AES.MODE_ECB) X0 = rootcipher.encrypt(B0) X1 = rootcipher.encrypt(B1) X2 = rootcipher.encrypt(B2) if KC_Choice == 1: X3 = rootcipher.encrypt(B3) X4 = rootcipher.encrypt(B4) # Y values Y1 = bytes(a ^ b for (a,b) in zip (X1, X0)) Y2 = bytes(a ^ b for (a,b) in zip (X2, X0)) DerivedKey = Y1 + Y2 # Set KeyCommit to be empty # if KC_Choice = 0, KC, is empty KeyCommit = 0x00.to_bytes (0, 'big') # Otherwise, compute KeyCommit if KC_Choice == 1: Y3 = bytes(a ^ b for (a,b) in zip (X3, X0)) Y4 = bytes(a ^ b for (a,b) in zip (X4, X0)) KeyCommit = Y3 + Y4 # # Encrypt (A, M) with AES-GCM under DerivedKey, key # and the 12-byte nonce GCM_IV aesgcmkey = DerivedKey cipher = AES.new(aesgcmkey, AES.MODE_GCM, nonce=GCM_IV) cipher.update(aad) ciphertext, tag = cipher.encrypt_and_digest(plaintext) # Combined cipher, tag, KeyCommit ciphertext_tag = ciphertext + tag ciphertext_tag_commit = ciphertext + tag + KeyCommit # Gueron Expires September 21, 2025 [Page 39] Internet-Draft DNDK-GCM March 2025 # Printing the values can be done by e.g., the following lines: # print ("N = ", N.hex()[0: 32]) # print (" ", N.hex()[32: 54]) # print ("B0 = ", B0.hex()) # print (" ", KeyCommit.hex()[0: 32], sep='') # print (" ", KeyCommit.hex()[32: 64], sep='') 10. Acknowledgments The author would like to thank Jean Paul Degabriele, Gerald Doussot, Isaac Elbaz, Sasha Frolov, Ed Knapp, Maximilian Lorlacks, Thomas Pornin, Eric Schorn and Falko Strenzke 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 September 21, 2025 [Page 40]