Double Nonce Derive Key AES-GCM (DNDK-GCM)
draft-gueron-cfrg-dndkgcm-01
This document is an Internet-Draft (I-D).
Anyone may submit an I-D to the IETF.
This I-D is not endorsed by the IETF and has no formal standing in the
IETF standards process.
| Document | Type | Active Internet-Draft (individual) | |
|---|---|---|---|
| Author | Shay Gueron | ||
| Last updated | 2024-10-17 | ||
| RFC stream | (None) | ||
| Intended RFC status | (None) | ||
| Formats | |||
| Stream | Stream state | (No stream defined) | |
| Consensus boilerplate | Unknown | ||
| RFC Editor Note | (None) | ||
| IESG | IESG state | I-D Exists | |
| Telechat date | (None) | ||
| Responsible AD | (None) | ||
| Send notices to | (None) |
draft-gueron-cfrg-dndkgcm-01
Crypto Forum Shay Gueron
Internet Draft
University of Haifa and Meta
Intended status: Informational October 17, 2024
Expires: April 17, 2025
Double Nonce Derive Key AES-GCM (DNDK-GCM)
draft-gueron-cfrg-dndkgcm-01
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
(IV), and to provide for key commitment.
Encryption takes the root key and a random nonce (IV), 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.
Although this is not the primary targeted usage, it is also possible,
under some restrictions, to use DNDK-GCM with a non-repeating but
non-random nonce
The low collision probability in a collection of 24-byte random
nonces, together with 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 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 April 17, 2025 [Page 1]
Internet-Draft DNDK-GCM October 2024
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 April 17, 2025.
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.
Gueron Expires April 17, 2025 [Page 2]
Internet-Draft DNDK-GCM October 2024
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 Options...............................................8
5. DNDK-GCM With a Random Nonce and Key Commitment................9
5.1. DNDK-GCM..................................................9
5.2. Input and Output Ranges...................................9
5.3. Usage limits.............................................11
5.4. The Preamble: Derive-L1-2v-L2-L3.........................11
5.5. Encryption...............................................14
5.6. Decryption...............................................14
6. DNDK-GCM With a Counter Nonce.................................15
7. AEAD..........................................................17
8. Security Considerations.......................................17
9. Design Rationale..............................................18
9.1. The DNDK-GCM overheads...................................19
9.2. Security Bounds..........................................20
10. IANA Considerations..........................................21
11. References...................................................21
11.1. Normative References....................................21
11.2. Informative References..................................22
Appendix A. DNDK-GCM Encryption Worked-Out Examples..............24
A1. A Worked-Out Example (With Key Commitment)................24
A2. A Worked-Out Example (Couter Nonce With Key Commitment)...27
A3. A Worked-Out Example (Couter Nonce Without Key Commitment)30
Appendix B. A Python Script Reference Implementation Example.....33
12. Acknowledgments..............................................37
13. Authors' Addresses...........................................38
Gueron Expires April 17, 2025 [Page 3]
Internet-Draft DNDK-GCM October 2024
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
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
state is cumbersome, costly, or even unsafe. In practice, systems
often generate a nonce randomly for every message, with the hope that
nonce collisions do not occur during the key's lifetime. In this
context, NIST's Special Publication 800-38D [GCM] states (Section 8)
that:
The probability that the authenticated encryption function will 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
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
Gueron Expires April 17, 2025 [Page 4]
Internet-Draft DNDK-GCM October 2024
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. Thus, a receiver decrypting a ciphertext blob
with an unverifiable key might accept the resulting plaintext as
valid, even though it was generated 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).
1.3. DNDK-GCM Design Goals
DNDK-GCM is designed to address two main limitations of AES-GCM:
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
Gueron Expires April 17, 2025 [Page 5]
Internet-Draft DNDK-GCM October 2024
that AES (with a uniform random key) 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
A byte is an integer between 0 and 255, represented here by two
hexadecimal digits. For instance, 5 is 0x05, and 135 is 0x87.
Let U be an array of bytes ("array" for short) of length u (bytes).
The bytes of U are indexed from 0 to u-1 and denoted by U [j], j = 0,
..., u-1. Let a, b be two integers such that 0 <= a <= b <= (u-1).
Then, T = U [a: b] is the sub-array of U, of length (b-a+1), that
consists of bytes of U that are found in the index range between a
and b (inclusively). Specifically, T is defined, bytewise, by T [j] =
U [j + a], j = 0, 1, ..., (b - a). For a=b, T = U [a: a] is U [a] and
T = U [0: u-1] implies T = U. For completeness, in the case where 0
<= a = b+1 <=(u-1), the sub-array U [a: b] is understood to be empty.
Note that in this document, the two boundary indices in T [a: b] are
included in the range (contrary to conventions used in some (not all)
programming languages).
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-1.
Gueron Expires April 17, 2025 [Page 6]
Internet-Draft DNDK-GCM October 2024
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
u1+u2 bytes whose bytes are W [j] = U0 [j], j = 0, ... u0-1 and W [j]
= U1 [j-u0], j = u0, ..., u1+u0-1.
For an integer s, (0x00)^s denotes an array of s zero bytes. An array
of 16 bytes is also called a "block".
Note that the bytewise specification of an array is agnostic to way
that the array is listed as a sequence (of bytes), i.e., whether byte
0 is in the rightmost of the leftmost position. The bytes positions
in the sequence need to be specified unambiguously.
Example. Let U0 be an array of length u0 = 16, listed as follows:
byte index (position) 00010203040506070809101112131415
U0 = 3dfcc48e6cf4e1d25a8ff0de58c97a69
(i.e., U0 [00] = 3d, U0 [07] = d2, U0 [15] = 69). Then,
byte index (position) 00010203040506070809101112131415
U0 [00: 15] = 3dfcc48e6cf4e1d25a8ff0de58c97a69
U0 [00: 07] = 3dfcc48e6cf4e1d2
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******************
Gueron Expires April 17, 2025 [Page 7]
Internet-Draft DNDK-GCM October 2024
(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 as a
single array that is called "ciphertext-blob" (and parsed
accordingly). From this perspective, DNDK-GCM.Enc produces a single
output (the ciphertext-blob), while AES-GCM.Dec takes three inputs.
4. DNDK-GCM Options
The DNDK-GCM scheme includes three configurations, denoted by a
"Config" string as follows.
Config = 0x010000: Random nonce; With key commitment.
Config = 0x100000: Counter nonce; No key commitment.
Config = 0x110000: Counter nonce; With key commitment.
Gueron Expires April 17, 2025 [Page 8]
Internet-Draft DNDK-GCM October 2024
The Config value is incorporated in the DNDK-GCM key derivation step,
to achieve domain separation, as defined below. This ensures that
derived keys are uniquely associated with the configuration choice.
Whan Config = 0x100000, encryption does not include (nor needs to
compute) a key commitment value (KC), and decryption does not expect
to receive KC as input. For Config = 0x010000 and Config = 0x110000,
the encryption process computes a 32-byte key commitment value (KC)
and appends it to the authentication tag as part of the output.
Decryption expects to receive a KC value as input.
Every given DNDK-GCM key must be used with only one configuration and
the configuration must be pre-agreed by the communicating parties
that use DNDK-GCM.
5. DNDK-GCM With a Random Nonce and Key Commitment
This section describes the configuration associated with Config =
0x010000, i.e., using a random nonce (IV) and delivering key
commitment. This is the main usage format for DNDK-GCM.
5.1. DNDK-GCM
DNDK-GCM with Config = 0x010000 is a randomized AEAD scheme that
encrypts and authenticates a message, along with additional
authenticated data (AAD), using a 24-byte nonce (IV) that is selected
uniformly at random for each message.
5.2. 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
Gueron Expires April 17, 2025 [Page 9]
Internet-Draft DNDK-GCM October 2024
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
authentication tag T and a commitment value KC. 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) called "ciphertext-
blob". Under this view, DNDK-GCM.Enc has a single output (namely
ciphertext-blob) and the length of ciphertext-blob equals to the
length of P plus 48.
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 (and parsed
accordingly) 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. It SHOULD be 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
Gueron Expires April 17, 2025 [Page 10]
Internet-Draft DNDK-GCM October 2024
commitment value (KC) MUST consist of KC_LEN bytes. The arrays A, P,
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.
Inputs to DNDK-GCM.Enc and to DNDK-GCM.Dec are assumed to be valid
and within the defined range of lengths (i.e., DNDK-GCM.Enc and DNDK-
GCM.Dec implicitly check and reject invalid inputs).
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 the tag T to
d = 12, 8, or 4 bytes as indicated in [GCM]. The formatting and
agreement of such truncation is left for the communicating parties or
protocol.
5.3. Usage limits
A given DNDK-GCM key must be used for encrypting a maximum of 2^48
messages and processing up to 2^64 plaintext blocks.
5.4. 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 (randomly chosen) nonce (N) of 2v bytes (1 <= v <=
15). It outputs a derived key (DerivedKey) of L2 bytes and a key
Gueron Expires April 17, 2025 [Page 11]
Internet-Draft DNDK-GCM October 2024
commitment value (KeyCommit) of L3 bytes.
This document sets the parameter values to L1 = L2 = L3 = 32 and v =
12 (i.e., the nonce N has 24 bytes). For brevity, Derive-32-24-32-32
is referred to as "Derive".
Algorithms 1 and 2 define SplitArray and Derive.
+-------------------------------------------------------------------+
Algorithm 1. SplitArray (v, N)
Input: v (1 <= v <= 15), N (array of 2v bytes). Here, v=12.
// Explicitly:
N0 [ 0] = N [ 0]; N0 [ 1] = N [ 1]; N0 [ 2] = N [ 2];
N0 [ 3] = N [ 3]; N0 [ 4] = N [ 4]; N0 [ 5] = N [ 5];
N0 [ 6] = N [ 6]; N0 [ 7] = N [ 7]; N0 [ 8] = N [ 8];
N0 [ 9] = N [ 9]; N0 [10] = N [10]; N0 [11] = N [11];
N1 [ 0] = N [12]; N1 [ 1] = N [13]; N1 [ 2] = N [14];
N1 [ 3] = N [15]; N1 [ 4] = N [16]; N1 [ 5] = N [17];
N1 [ 6] = N [18]; N1 [ 7] = N [19]; N1 [ 8] = N [20];
N1 [ 9] = N [21]; N1 [10] = N [22]; N1 [11] = N [23];
// Shorthand:
// N0 [0: v-1] = N [0: v-1];
// N1 [0: v-1] = N [v: 2v-1];
Output: N1, N0
+-------------------------------------------------------------------+
Gueron Expires April 17, 2025 [Page 12]
Internet-Draft DNDK-GCM October 2024
+-------------------------------------------------------------------+
Algorithm 2. Derive (K, N)
Input: K (root key), N (array of 2v bytes). Here, v=12.
(N1, N0) = SplitArray (v, N)
Context: Config = 0x010000 (variant with key commitment)
For j in {1, 3, 5, 7, 9} // (odd indices)
Bj [0] = j
Bj [1: (15-v)] = Config
Bj [(16-v): 15] = N1 [0: v-1]
For j in {0, 2, 4, 6, 8}
Bj [0] = j
Bj [1: (15-v) = Config
Bj [(16-v): 15 = N0 [0: v-1]
For j in {0, 1, ..., 9}
Xj = AES (K, Bj)
For j in {2, 3, ..., 9}
Yj = Xj XOR X [j mod 2]
KeyCommit [0: 15] = Y6 XOR Y7
KeyCommit [16: 31] = Y8 XOR Y9
DerivedKey [0: 15] = Y2 XOR Y3
DerivedKey [16: 31] = Y4 XOR Y5
Output: (KeyCommit [0: 31], DerivedKey [0: 31])
+-------------------------------------------------------------------+
Gueron Expires April 17, 2025 [Page 13]
Internet-Draft DNDK-GCM October 2024
5.5. Encryption
DNDK-GCM.Enc receives the tuple (K, N, A, P) as input. It is assumed
that prior to invoking DNDK-GCM.Enc, the caller has generated N,
uniformly at random (or that DNDK-GCM.Enc starts with such
generation). This step is not shown explicitly. DNDK-GCM.Enc first
runs the preamble Derive on K and N to compute a derived key (DK) and
a key commitment value (KC). It then invokes AES-GCM.Enc using DK as
the encryption key, a nonce (NZ12) of 12 zero bytes, 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) is viewed as a single array called ciphertext-blob).
DNDK-GCM.Enc is defined by Algorithm 3.
+-----------------------------------------------------------------+
Algorithm 3. DNDK-GCM.Enc
Input: K, N, A, P
NZ12 = (0x00)^12
(KC, DK) = Derive (K, N)
(C, T) = AES-GCM.Enc (DK, NZ12, A, P)
Output: C, T, KC
+-----------------------------------------------------------------+
5.6. Decryption
DNDK-GCM.Dec receives the tuple (K, N, A, C, T, KC) as input (or,
equivalently C || T || KC is viewed as a single array called
ciphertext-blob). It runs the preamble Derive over K and N and
computes a derived key (DK) and a key commitment value contender
(KC'). If KC' does not match KC, the decryption is aborted and
outputs the failure indication FAIL. Otherwise, AES-GCM.Dec is
Gueron Expires April 17, 2025 [Page 14]
Internet-Draft DNDK-GCM October 2024
invoked using DK as the decryption key, a nonce (NZ12) of 12 zero
bytes, A, C and T. This either retrieves a message P with the same
length as C, or an authentication failure indication FAIL. The output
of DNDK-GCM.Dec is, accordingly, either P or FAIL. The decryption
does not release any part of P before it is fully authenticated.
DNDK-GCM.Dec is defined by Algorithm 4.
+-----------------------------------------------------------------+
Algorithm 4. DNDK-GCM.Dec
Input: K, N, A, C, T, KC
NZ12 = (0x00)^12
(KC', DK) = Derive (K, N)
If KC' != KC output FAIL and abort
P / FAIL = AES-GCM.Dec (DK, NZ12, A, C, T)
Output: M or FAIL
+-----------------------------------------------------------------+
Appendix A1 provides a step-by-step detailed example with the
intermediate values. Appendix B provides a reference Python script
implementation (that produces the values of Appendix A1).
6. DNDK-GCM With a Counter Nonce
The main goal of the DNDK-GCM design (The Config = 0x010000
configuration) is to support the use of sufficiently long random
nonces where the nonce collision probability remains negligible
during the allowed lifetime of the root key.
For completeness, this section defines a DNDK-GCM variant for using
distinct but not random nonces, called here "counter nonces" (with or
without key commitment). These variants use 12-bye nonces and are
associated with Config = 0x100000 or Config = 0x110000. The
Gueron Expires April 17, 2025 [Page 15]
Internet-Draft DNDK-GCM October 2024
differences (from the random nonce case) are in in details of
Algorithm 2, while the encryption and decryption flows are analogous
to the cases with Config = 0x010000. The modified version of
Algorithm 2 is the following.
+-------------------------------------------------------------------+
Algorithm 2' [Counter nonce setting]. Derive (K, N)
Input: K (root key), N (array of v bytes). Here, v=12.
Context: Config = 0x100000 (or 0x110000)
N0 = N
For j in {0, 2, 4, 6, 8}
Bj [0] = j
Bj [1: (15-v) = Config
Bj [(16-v): 15 = N0 [0: v-1]
For j in {0, 2, 4, 6, 8}
Xj = AES (K, Bj)
For j in {1, 3, 5, 7, 9}
Xj = 0x00000000000000000000000000000000
For j in {2, 3, ..., 9}
Yj = Xj XOR X [j mod 2]
KeyCommit [0: 15] = Y6 XOR Y7
KeyCommit [16: 31] = Y8 XOR Y9
DerivedKey [0: 15] = Y2 XOR Y3
DerivedKey [16: 31] = Y4 XOR Y5
Output: (KeyCommit [0: 31], DerivedKey [0: 31])
+-------------------------------------------------------------------+
Gueron Expires April 17, 2025 [Page 16]
Internet-Draft DNDK-GCM October 2024
Appendix A2 and Appendix A3 provide a step-by-step detailed example
with the intermediate values.
7. AEAD
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.
8. Security Considerations
DNDK-GCM (Config = 0x01000000) is a randomized AEAD where the nonce
serves as an initialization vector (IV): an invocation of DNDK-
GCM.Enc MUST use a nonce that is selected uniformly at random (or
pseudo-randomly) from the set of all 24-byte arrays. In particular,
the selection of a nonce value for encryption MUST NOT be under the
control of (nor be predictable by) any entity that does not own the
secret key. The generated nonce must be provided to the decryption
function.
It is unacceptable to use DNDK-GCM with just non-repeating but non-
random nonces, without placing additional constraints on their
selection. Such nonces (can be chosen to) could lead to linear
dependence (zero XOR sum) in the derived keys. For example, for every
root key, the XOR sum of the derived keys from the four (double)
nonces (0x11)^12 || (0x21)^12, (0x11)^12 || (0x22)^12, (0x12)^12 ||
(0x21)^12, (0x12)^12 || (0x22)^12 is zero.
It is possible to prevent such linear dependence and safely use a
Gueron Expires April 17, 2025 [Page 17]
Internet-Draft DNDK-GCM October 2024
counter to select the nonces. One way is to freeze half of the nonce
and populate the other half with a 12-byte running counter, e.g.,
select nonces of the form (0xff)^12 || counter. Then continue with
Algorithm 2.
This constrained nonce setting is not a significant limitation for
applications that can accommodate a stateful 12-byte counter (which
provides sufficient counter values). However, these usages do not
need (nor really leverage to advantage) a double-length nonce. They
and can simply use a 12-byte nonce and skip some of the (redundant)
steps of Algorithm 2, as shown in Algorithm 2' (as proposed for
Config = 0x100000 and Config = 0x110000). Here, the key derivation
allows for encrypting more data than the possible amount with the
standard AES-GCM.
Technically, these variants define a degenerate form of DNDK-GCM
where DerivedKey is derived from a single-length nonce. An
appropriate name would be Derive Key AES-GCM (DK-GCM).
DNDK-GCM decryption (for Config = 0x110000 and Config = 0x010000)
involves two verifications: a match on the key commitment value, and
a match on the authentication tag. An implementation of AES-GCM.Dec
MUST NOT release any part of the reproduced plaintext before it is
(doubly) authenticated because otherwise parts of a system may
process malicious data as if it were authentic.
For the case, Config = 0x100000, a key commitment value is not
computed nor communicated, and AES-GCM.Dec does not expect (nor use)
to receive it as input. Here, AES-GCM.Dec MUST NOT release any part
of the reproduced plaintext before it is authenticated.
9. Design Rationale
The first goal of the DNDK-GCM design (Config = 0x01000000) is to
overcome the short nonce limitation of AES-GCM, in the random nonce
Gueron Expires April 17, 2025 [Page 18]
Internet-Draft DNDK-GCM October 2024
(stateless) setting. To this end, DNDK-GCM encryption (and
decryption) consumes a double-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. The pseudorandom function Derive is a "double XORP": a
variant of the XORP construction [Iwa06] over two halves of the
(random) nonce. The (Beyond-Birthday-Bound) indistinguishability with
random inputs is deduced from [BGK99]. Within the prescribed limit on
the number of encrypted messages and the total amount of plaintext,
the ciphertext distinguishing advantage and the collision probability
derived of the derived keys are negligible. This random nonce setting
converts the DNDK-GCM encryption to a multi-key AES-GCM setting where
every key is used for encrypting exactly one message. This allows for
using a fixed AES-GCM nonce (0x00^12). The security of DNDK-GCM
relies on the security of AES in the multi-key setting.
Given the prescribed limit on the number of encrypted messages,
adversarial decryption queries with nonces that were not used with an
encryption query can be ignored without making special related-key
assumptions.
For the counter nonce setting (Config = 0x100000 or 0x110000) DNDK-
GCM uses a 12-byte nonce and Derive is simply "XORP" pseudorandom
function. The security follows from Derive-Key design of [GL17].
9.1. The DNDK-GCM overheads
For DNDK-GCM (Config = 0x01000000), Derive requires 10 calls to
AES256 with the root key. These computations are computed and over
Gueron Expires April 17, 2025 [Page 19]
Internet-Draft DNDK-GCM October 2024
independent blocks and can therefore 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).
For the counter nonce settings with Config = 0x110000, Derive
requires 5 AES calls, and for Config = 0x100000 it requires 3 AES
calls.
9.2. Security Bounds
Suppose that DNDK-GCM (Config = 0x01000000) is used for encrypting Q
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)
(these privacy bounds hold for Config = 0x10000000 and 0x110000)
To find two (adversarial) keys K1, K2, and two N-A-P triples such
that DNDK-GCM.Enc (K1, N1, A1, P1) = DNDK-GCM.Enc (K2, N2, A2, P2),
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].
Gueron Expires April 17, 2025 [Page 20]
Internet-Draft DNDK-GCM October 2024
10. 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.
11. References
11.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, <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://datatracker.ietf.org/doc/html/bcp14>.
Gueron Expires April 17, 2025 [Page 21]
Internet-Draft DNDK-GCM October 2024
11.2. Informative References
[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>.
[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
Gueron Expires April 17, 2025 [Page 22]
Internet-Draft DNDK-GCM October 2024
Archive, Paper 2020/1153, 2020. [Online]. Available:
https://eprint.iacr.org/2020/1153
[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
Gueron Expires April 17, 2025 [Page 23]
Internet-Draft DNDK-GCM October 2024
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 (With Key Commitment)
The configuration Config = 0x010000 selects the variant with key
commitment.
===================================================================
DNDK-GCM example
Config = 010000
===================================================================
Random nonce; With Key Commit
===================================================================
---------Bytes Position---------
00010203040506070809101112131415
...16171819202121232425262728293031
--------------------------------
Root key = 01000000000000000000000000000000
00000000000000000000000000000000
Nonce = 000102030405060708090a0b0c0d0e0f
1011121314151617
aad (5 bytes) = 0100000011
plaintext (4 bytes) = 11000001
-------------------------------------------------------------------
Key commitment value = 8bbe4d73fe5f89412c77ad3d3633e551
492bd29c83e796bd42e21feb13c27544
tag = 60b8ea8fef0fe4a299fad34a046895b7
cipher (4 bytes) = 64a5ec95
Gueron Expires April 17, 2025 [Page 24]
Internet-Draft DNDK-GCM October 2024
-------------------------------------------------------------------
ciphertext tag (20 bytes) = 64a5ec9560b8ea8fef0fe4a299fad34a
046895b7
-------------------------------------------------------------------
ciphertext tag commit
(52 bytes) = 64a5ec9560b8ea8fef0fe4a299fad34a
046895b78bbe4d73fe5f89412c77ad3d
3633e551492bd29c83e796bd42e21feb
13c27544
===================================================================
Intermediate values
===================================================================
Nonce
N = 000102030405060708090a0b0c0d0e0f
1011121314151617
Split Nonce
N1 = 0c0d0e0f1011121314151617
N0 = 000102030405060708090a0b
Config = 010000
Derive
B0 = 00010000000102030405060708090a0b
B1 = 010100000c0d0e0f1011121314151617
B2 = 02010000000102030405060708090a0b
B3 = 030100000c0d0e0f1011121314151617
B4 = 04010000000102030405060708090a0b
B5 = 050100000c0d0e0f1011121314151617
B6 = 06010000000102030405060708090a0b
B7 = 070100000c0d0e0f1011121314151617
B8 = 08010000000102030405060708090a0b
B9 = 090100000c0d0e0f1011121314151617
Gueron Expires April 17, 2025 [Page 25]
Internet-Draft DNDK-GCM October 2024
X0 = 4aa753bea7432390936bad728ef10edf
X1 = b40cc73539f699ecd07ecb5a5a4073bb
X2 = 434adcb757a3ce5632be2a001de4944c
X3 = e63e787d409f1bd96162c4d0d963d6b7
X4 = e149cfef6afb5e500fb4603119ea83ad
X5 = ef6c894641a9e73265ed17a179ab0f07
X6 = 61281d2ac2391f8d22ea0406a4674aa2
X7 = 143dc4d2a2d32cb04d88cf1346e5d297
X8 = a48d8620ed8e7e45db1671f038b3e94c
X9 = 130dc037f0dc5284dae10833ffc0e16c
Y2 = 09ed8f09f0e0edc6a1d5877293159a93
Y3 = 5232bf4879698235b11c0f8a8323a50c
Y4 = abee9c51cdb87dc09cdfcd43971b8d72
Y5 = 5b604e73785f7edeb593dcfb23eb7cbc
Y6 = 2b8f4e94657a3c1db181a9742a96447d
Y7 = a03103e79b25b55c9df604491ca5a12c
Y8 = ee2ad59e4acd5dd5487ddc82b642e793
Y9 = a7010702c92acb680a9fc369a58092d7
-------------------------------------------------------------------
Key commitment value
KeyCommit1 = Y8 XOR Y9; KeyCommit0 = Y6 XOR Y7
KeyCommit = KeyCommit0 + KeyCommit1
-------------------------------------------------------------------
KeyCommit0 = 8bbe4d73fe5f89412c77ad3d3633e551
KeyCommit1 = 492bd29c83e796bd42e21feb13c27544
KeyCommit = 8bbe4d73fe5f89412c77ad3d3633e551
492bd29c83e796bd42e21feb13c27544
-------------------------------------------------------------------
Derived key
DerivedKey1 = Y4 XOR Y5; DerivedKey0 = Y2 XOR Y3
Gueron Expires April 17, 2025 [Page 26]
Internet-Draft DNDK-GCM October 2024
DerivedKey = DerivedKey0 + DerivedKey1
-------------------------------------------------------------------
DerivedKey0 = 5bdf304189896ff310c988f810363f9f
DerivedKey1 = f08ed222b5e7031e294c11b8b4f0f1ce
DerivedKey = 5bdf304189896ff310c988f810363f9f
f08ed222b5e7031e294c11b8b4f0f1ce
-------------------------------------------------------------------
A2. A Worked-Out Example (Couter Nonce With Key Commitment)
The configuration Config = 0x110000 selects the variant with a
counter nonce and key commitment.
===================================================================
DNDK-GCM example
Config = 110000
===================================================================
Counter nonce; With Key Commit
===================================================================
---------Bytes Position---------
00010203040506070809101112131415
...16171819202121232425262728293031
--------------------------------
Root key = 01000000000000000000000000000000
00000000000000000000000000000000
Nonce = 000102030405060708090a0b
aad (5 bytes) = 0100000011
plaintext (4 bytes) = 11000001
-------------------------------------------------------------------
Key commitment value = f9f58a5823c3ded0d79a3e9c90035393
Gueron Expires April 17, 2025 [Page 27]
Internet-Draft DNDK-GCM October 2024
c328127f75ea0b0851a3681fb1ea092f
tag = c1cae687dc8c010156bf7ea28c5e1e61
cipher (4 bytes) = 17c09c47
-------------------------------------------------------------------
ciphertext tag (20 bytes) = 17c09c47c1cae687dc8c010156bf7ea2
8c5e1e61
-------------------------------------------------------------------
ciphertext tag commit
(52 bytes) = 17c09c47c1cae687dc8c010156bf7ea2
8c5e1e61f9f58a5823c3ded0d79a3e9c
90035393c328127f75ea0b0851a3681f
b1ea092f
===================================================================
Intermediate values
===================================================================
Nonce
N = 000102030405060708090a0b
Split Nonce
N1 =
N0 = 000102030405060708090a0b
Config = 110000
Derive
B0 = 00110000000102030405060708090a0b
B1 = 01110000ffffffffffffffffffffffff
B2 = 02110000000102030405060708090a0b
B3 = 03110000ffffffffffffffffffffffff
B4 = 04110000000102030405060708090a0b
B5 = 05110000ffffffffffffffffffffffff
B6 = 06110000000102030405060708090a0b
Gueron Expires April 17, 2025 [Page 28]
Internet-Draft DNDK-GCM October 2024
B7 = 07110000ffffffffffffffffffffffff
B8 = 08110000000102030405060708090a0b
B9 = 09110000ffffffffffffffffffffffff
X0 = 562442e1b081e557046708fdd9051bd6
X1 = 00000000000000000000000000000000
X2 = a2bbd80d8d40a8a03538ff51c0de51de
X3 = 00000000000000000000000000000000
X4 = 888313ef53ea71f2a42c53fa9089dcaa
X5 = 00000000000000000000000000000000
X6 = afd1c8b993423b87d3fd366149064845
X7 = 00000000000000000000000000000000
X8 = 950c509ec56bee5f55c460e268ef12f9
X9 = 00000000000000000000000000000000
Y2 = f49f9aec3dc14df7315ff7ac19db4a08
Y3 = 00000000000000000000000000000000
Y4 = dea7510ee36b94a5a04b5b07498cc77c
Y5 = 00000000000000000000000000000000
Y6 = f9f58a5823c3ded0d79a3e9c90035393
Y7 = 00000000000000000000000000000000
Y8 = c328127f75ea0b0851a3681fb1ea092f
Y9 = 00000000000000000000000000000000
-------------------------------------------------------------------
Key commitment value
KeyCommit1 = Y8 XOR Y9; KeyCommit0 = Y6 XOR Y7
KeyCommit = KeyCommit0 + KeyCommit1
-------------------------------------------------------------------
KeyCommit0 = f9f58a5823c3ded0d79a3e9c90035393
KeyCommit1 = c328127f75ea0b0851a3681fb1ea092f
KeyCommit = f9f58a5823c3ded0d79a3e9c90035393
c328127f75ea0b0851a3681fb1ea092f
Gueron Expires April 17, 2025 [Page 29]
Internet-Draft DNDK-GCM October 2024
-------------------------------------------------------------------
Derived key
DerivedKey1 = Y4 XOR Y5; DerivedKey0 = Y2 XOR Y3
DerivedKey = DerivedKey0 + DerivedKey1
-------------------------------------------------------------------
DerivedKey0 = f49f9aec3dc14df7315ff7ac19db4a08
DerivedKey1 = dea7510ee36b94a5a04b5b07498cc77c
DerivedKey = f49f9aec3dc14df7315ff7ac19db4a08
dea7510ee36b94a5a04b5b07498cc77c
-------------------------------------------------------------------
A3. A Worked-Out Example (Couter Nonce Without Key Commitment)
The configuration Config = 0x100000 selects the variant with a
counter nonce and no key commitment.
===================================================================
DNDK-GCM example
Config = 100000
===================================================================
Counter nonce; No Key Commit
===================================================================
---------Bytes Position---------
00010203040506070809101112131415
...16171819202121232425262728293031
--------------------------------
Root key = 01000000000000000000000000000000
00000000000000000000000000000000
Nonce = 000102030405060708090a0b
aad (5 bytes) = 0100000011
Gueron Expires April 17, 2025 [Page 30]
Internet-Draft DNDK-GCM October 2024
plaintext (4 bytes) = 11000001
-------------------------------------------------------------------
Key commitment value =
tag = ddd4a11ef1e7796476dbdde2b9a1b6b4
cipher (4 bytes) = 06d7ce9e
-------------------------------------------------------------------
ciphertext tag (20 bytes) = 06d7ce9eddd4a11ef1e7796476dbdde2
b9a1b6b4
-------------------------------------------------------------------
ciphertext tag commit
(20 bytes) = 06d7ce9eddd4a11ef1e7796476dbdde2
b9a1b6b4
===================================================================
Intermediate values
===================================================================
Nonce
N = 000102030405060708090a0b
Split Nonce
N1 =
N0 = 000102030405060708090a0b
Config = 100000
Derive
B0 = 00100000000102030405060708090a0b
B1 = 01100000ffffffffffffffffffffffff
B2 = 02100000000102030405060708090a0b
B3 = 03100000ffffffffffffffffffffffff
Gueron Expires April 17, 2025 [Page 31]
Internet-Draft DNDK-GCM October 2024
B4 = 04100000000102030405060708090a0b
B5 = 05100000ffffffffffffffffffffffff
B6 = 06100000000102030405060708090a0b
B7 = 07100000ffffffffffffffffffffffff
B8 = 08100000000102030405060708090a0b
B9 = 09100000ffffffffffffffffffffffff
X0 = 2e4a0bef515cefe8f635a6d34c80180e
X1 = 00000000000000000000000000000000
X2 = e283b79f020239e69eadedecbf5227bc
X3 = 00000000000000000000000000000000
X4 = 60f6e16726aef76c84684a8e19d7f21c
X5 = 00000000000000000000000000000000
X6 = 1641b80f40ef16d7fab0e883616c292d
X7 = 00000000000000000000000000000000
X8 = 523b3388354c6172245042abee1ec8d2
X9 = 00000000000000000000000000000000
Y2 = ccc9bc70535ed60e68984b3ff3d23fb2
Y3 = 00000000000000000000000000000000
Y4 = 4ebcea8877f21884725dec5d5557ea12
Y5 = 00000000000000000000000000000000
Y6 = 380bb3e011b3f93f0c854e502dec3123
Y7 = 00000000000000000000000000000000
Y8 = 7c71386764108e9ad265e478a29ed0dc
Y9 = 00000000000000000000000000000000
-------------------------------------------------------------------
Key commitment value
KeyCommit1 = Y8 XOR Y9; KeyCommit0 = Y6 XOR Y7
KeyCommit = KeyCommit0 + KeyCommit1
-------------------------------------------------------------------
KeyCommit0 =
Gueron Expires April 17, 2025 [Page 32]
Internet-Draft DNDK-GCM October 2024
KeyCommit1 =
KeyCommit =
-------------------------------------------------------------------
Derived key
DerivedKey1 = Y4 XOR Y5; DerivedKey0 = Y2 XOR Y3
DerivedKey = DerivedKey0 + DerivedKey1
-------------------------------------------------------------------
DerivedKey0 = ccc9bc70535ed60e68984b3ff3d23fb2
DerivedKey1 = 4ebcea8877f21884725dec5d5557ea12
DerivedKey = ccc9bc70535ed60e68984b3ff3d23fb2
4ebcea8877f21884725dec5d5557ea12
-------------------------------------------------------------------
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 (with Config = The script is already
hardcoded with.
# DNDK-GCM encryption example
#
from Cryptodome.Cipher import AES
#
# Hardcoded input to encryption
# (can be edited)
# Root key
RootKey = \
0x0100000000000000000000000000000000000000000000000000000000000000.\
Gueron Expires April 17, 2025 [Page 33]
Internet-Draft DNDK-GCM October 2024
to_bytes(32,'big')
# Nonce (24 bytes)
N =\
0x000102030405060708090a0b0c0d0e0f1011121314151617.\
to_bytes(24,'big')
# aad and plaintext
aad = 0x0100000011.to_bytes(5,'big')
plaintext = 0x11000001.to_bytes(4,'big')
# End of (hardcoded) input setting.
#
# Nonce Split
N0 = N [0:12]
N1 = N [12:24]
# Configuration options
# Config = 0x010000: Random nonce; With Key Commit.
# Config = 0x100000: Counter nonce; No Key Commit).
# Config = 0x110000: Counter nonce; With Key Commit.
# For counter nonces (Config = 0x100000 or 0x110000)
# the nonce length is 12 bytes
# Implicitly, N1 = 0xff^12
#
# The three options
Config = 0x010000.to_bytes(3, 'big')
# Config = 0x100000.to_bytes(3, 'big')
# Config = 0x110000.to_bytes(3, 'big')
#
# The case of counter nonce (Config = 0x010000 or 0x110000):
if Config == 0x110000.to_bytes(3, 'big') or \
Config == 0x100000.to_bytes(3, 'big'):
N1 = 0xffffffffffffffffffffffff.to_bytes(12, 'big')
Gueron Expires April 17, 2025 [Page 34]
Internet-Draft DNDK-GCM October 2024
# implicit 2nd half-nonce
N = N0 + 0x00.to_bytes(0, 'big') # The nonce has 12 bytes
#
# In the case of counter nonce (Config = 0x010000 or 0x110000),
# B1, B3, B5, B7, B9, and X1, X3, X5, X7, X9
# need not be computed because
# X1, X3, X5, X7, X9 are zeroed out
#(to ignore the contribution of the implicit N1).
#
# B values
B0 = 0x00.to_bytes(1, 'big') + Config + N0
B1 = 0x01.to_bytes(1, 'big') + Config + N1
B2 = 0x02.to_bytes(1, 'big') + Config + N0
B3 = 0x03.to_bytes(1, 'big') + Config + N1
B4 = 0x04.to_bytes(1, 'big') + Config + N0
B5 = 0x05.to_bytes(1, 'big') + Config + N1
B6 = 0x06.to_bytes(1, 'big') + Config + N0
B7 = 0x07.to_bytes(1, 'big') + Config + N1
B8 = 0x08.to_bytes(1, 'big') + Config + N0
B9 = 0x09.to_bytes(1, 'big') + Config + N1
# X values
X0 = AES.new(key=RootKey, mode=AES.MODE_ECB).encrypt(B0)
X1 = AES.new(key=RootKey, mode=AES.MODE_ECB).encrypt(B1)
X2 = AES.new(key=RootKey, mode=AES.MODE_ECB).encrypt(B2)
X3 = AES.new(key=RootKey, mode=AES.MODE_ECB).encrypt(B3)
X4 = AES.new(key=RootKey, mode=AES.MODE_ECB).encrypt(B4)
X5 = AES.new(key=RootKey, mode=AES.MODE_ECB).encrypt(B5)
X6 = AES.new(key=RootKey, mode=AES.MODE_ECB).encrypt(B6)
X7 = AES.new(key=RootKey, mode=AES.MODE_ECB).encrypt(B7)
X8 = AES.new(key=RootKey, mode=AES.MODE_ECB).encrypt(B8)
Gueron Expires April 17, 2025 [Page 35]
Internet-Draft DNDK-GCM October 2024
X9 = AES.new(key=RootKey, mode=AES.MODE_ECB).encrypt(B9)
# For the case of counter nonce (Config = 0x010000 or 0x110000),
# cancel the redundant contribution of X1, X3, X5, X7, X9
# by setting them to (0x00)^16,
if Config == 0x110000.to_bytes(3, 'big') or Config ==
0x100000.to_bytes(3, 'big'):
0x00000000000000000000000000000000.to_bytes(16, 'big')
X1 = 0x00000000000000000000000000000000.to_bytes(16, 'big')
X3 = 0x00000000000000000000000000000000.to_bytes(16, 'big')
X5 = 0x00000000000000000000000000000000.to_bytes(16, 'big')
X7 = 0x00000000000000000000000000000000.to_bytes(16, 'big')
X9 = 0x00000000000000000000000000000000.to_bytes(16, 'big')
#
# Y values
Y2 = bytes(a ^ b for (a,b) in zip (X2, X0))
Y3 = bytes(a ^ b for (a,b) in zip (X3, X1))
Y4 = bytes(a ^ b for (a,b) in zip (X4, X0))
Y5 = bytes(a ^ b for (a,b) in zip (X5, X1))
Y6 = bytes(a ^ b for (a,b) in zip (X6, X0))
Y7 = bytes(a ^ b for (a,b) in zip (X7, X1))
Y8 = bytes(a ^ b for (a,b) in zip (X8, X0))
Y9 = bytes(a ^ b for (a,b) in zip (X9, X1))
# Key Commitment value
KeyCommit1 = bytes(a ^ b for (a,b) in zip (Y8, Y9))
KeyCommit0 = bytes(a ^ b for (a,b) in zip (Y6, Y7))
# For the case of no Key Commitment value (Config == 0x100000)
if Config == 0x100000.to_bytes(3, 'big'):
KeyCommit1 = 0x00.to_bytes(0, 'big')
KeyCommit0 = 0x00.to_bytes(0, 'big')
KeyCommit = 0x00.to_bytes(0, 'big')
Gueron Expires April 17, 2025 [Page 36]
Internet-Draft DNDK-GCM October 2024
# Concatenation of the two halves gives the key commitment value
KeyCommit = KeyCommit0 + KeyCommit1
# Derived key
DerivedKey1 = bytes(a ^ b for (a,b) in zip (Y4, Y5))
DerivedKey0 = bytes(a ^ b for (a,b) in zip (Y2, Y3))
# Concatenation of the two halves gives the Derived Key
DerivedKey = DerivedKey0 + DerivedKey1
# Encrypt with AES-GCM using the derived key and a 12-byte zero nonce
aesgcmkey = DerivedKey
Zero_12B_Nonce = 0x000000000000000000000000.to_bytes(12,'big')
cipher = AES.new(aesgcmkey, AES.MODE_GCM, nonce=Zero_12B_Nonce)
cipher.update(aad)
ciphertext, tag = cipher.encrypt_and_digest(plaintext)
# Combined cipher, tag, commit
ciphertext_tag = ciphertext + tag
ciphertext_tag_commit = ciphertext + tag + KeyCommit
#
# Printing the values can be done by e.g., the following lines:
# print ("N = ", N.hex()[0: 32])
# print (" ", N.hex()[32: 48])
# print (" ", N.hex()[32: 48])
# print ("N1 = ", N1.hex() [0: 24])
# print ("B0 = ", B0.hex())
12. 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.
Gueron Expires April 17, 2025 [Page 37]
Internet-Draft DNDK-GCM October 2024
13. Authors' Addresses
Shay Gueron
University of Haifa
Abba Khoushy Ave 199
Haifa 3498838, Israel
Email: shay.gueron@gmail.com
Gueron Expires April 17, 2025 [Page 38]