Crypto Forum Shay Gueron
Internet Draft
University of Haifa and Meta
Intended status: Informational April 15, 2024
Expires: October 15, 2024
Double Nonce Derive Key AESGCM (DNDKGCM)
draftgueroncfrgdndkgcm00
Abstract
This document specifies an authenticated encryption algorithm called
Double Nonce Derive Key AESGCM (DNDKGCM) that operates with a 32
byte root key and encrypts with a 24byte random nonce, and
optionally provides for key commitment.
Encryption takes the root key and a random nonce, derives a fresh
encryption key and a key commitment value, invokes AESGCM with the
derived key and a 12byte zero nonce, and outputs the ciphertext,
authentication tag and the key commitment value.
The low collision probability with 24byte random nonces extends the
lifetime of the root key and this supports processing up to 2^64
bytes under one root key. DNDKGCM involves a small overhead compared
to using AESGCM directly, and its security relies only on the
standard assumption on AES as a pseudorandom permutation.
Status of this Memo
This InternetDraft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
InternetDrafts 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 InternetDrafts is at
http://datatracker.ietf.org/drafts/current/.
InternetDrafts are draft documents valid for a maximum of six months
Gueron Expires October 15, 2024 [Page 1]
InternetDraft DNDKGCM April 2024
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use InternetDrafts as reference
material or to cite them other than as "work in progress."
The list of current InternetDrafts can be accessed at
https://www.ietf.org/1idabstracts.html.
The list of InternetDraft Shadow Directories can be accessed at
https://www.ietf.org/shadow.html
This InternetDraft will expire on October 15, 2024.
Copyright Notice
Copyright (c) 2024 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(https://trustee.ietf.org/licenseinfo) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Revised BSD License text as described in Section 4.e of the
Trust Legal Provisions and are provided without warranty as described
in the Revised BSD License.
Table of Contents
1. Introduction...................................................3
1.1. Limitation 1: Short Nonces Enforce Frequent Key Rotation..3
1.2. Limitation 2: Lack of Key Commitment......................4
1.3. DNDKGCM Design Goals.....................................5
2. Requirements Language..........................................5
Gueron Expires October 15, 2024 [Page 2]
InternetDraft DNDKGCM April 2024
3. Preliminaries and Notation.....................................5
4. DNDKGCM Definition............................................7
4.1. Input and Output Ranges...................................7
4.2. The Preamble: DeriveL12vL2L3..........................8
4.3. Encryption...............................................12
4.4. Decryption...............................................13
4.5. No Key Commit Value Option...............................14
5. AEAD..........................................................14
6. Security Considerations.......................................15
7. Design Rationale..............................................15
7.1. Security Bounds..........................................17
8. IANA Considerations...........................................17
9. References....................................................18
9.1. Normative References.....................................18
9.2. Informative References...................................18
Appendix A. The Preamble Procedure Flow With Explicit Indexes....20
Appendix B. A WorkedOut Example.................................25
10. Acknowledgments..............................................28
11. Authors' Addresses...........................................28
1. Introduction
Authenticated Encryption with Additional Data (AEAD) [RFC5116] is a
fundamental cryptographic tool that provides confidentiality and
integrity in a single scheme. AESGCM [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, AESGCM has limitations that motivate seeking some variants.
1.1. Limitation 1: Short Nonces Enforce Frequent Key Rotation
AESGCM is a noncerespecting AEAD: a nonce must not be used for
Gueron Expires October 15, 2024 [Page 3]
InternetDraft DNDKGCM April 2024
encrypting more than one message under a given key. In fact, reusing
a nonce for two distinct messages leads to catastrophic failure of
confidentiality and integrity.
Applications can enforce nonce uniqueness by using a counter to
construct nonces. However, in many realworld scenarios, maintaining
a state is cumbersome, expensive, or even unsafe. Therefore, in
practice, systems often generate a nonce uniformly at random for
every message, hoping that a nonce collision does not occur over the
lifetime of the key. In this context, NIST's Special Publication 800
38D [GCM] states (Section 8) that:
The probability that the authenticated encryption function ever
will be invoked with the same IV and the same key on two (or more)
distinct sets of input data shall be no greater than 2^.32.
For AESGCM in a 12byte random setting, nonce collision probability
in Q calls is at most Q^2/2^97, and this bound is also essentially
tight. Upper bounding this probability by 2^32 limits the lifetime
of a key to at most 2^32.5 encryptions. In many scenarios, e.g., for
processing data at the cloud scale, this imposes a toofrequent key
rotation rate. Note that AESGCM can consume nonces of arbitrary
lengths, but the key rotation limitation is not fully alleviated by
using longer than 12 bytes nonces even with a stateful counter. The
reason is that GHASH is called over any nonce whose length is not 12
bytes, and the result is the initial 16byte counter for the
remaining AES computations [GCM]. This leads to a similar collision
probability issue: the probability is lower than with random 12byte
nonces, but still much higher than the security goal of DNDKGCM.
1.2. Limitation 2: Lack of Key Commitment
AESGCM has the following property: it is possible to find two (or
more) keys K1, K2, and two (or more) messages M1, M2, such that
encrypting M1 under K1 and encrypting M2 under K2 give the same
Gueron Expires October 15, 2024 [Page 4]
InternetDraft DNDKGCM April 2024
ciphertexttag pair. Thus, a receiver that decrypts a ciphertext blob
with a key that is not verifiably trustworthy might accept the
resulting plaintext as a valid message although it was generated by a
malicious untrusted actor. This lack of key commitment property is
not unique to AESGCM. It applies to other AEADs where authentication
uses universal hashing rather than e.g., (less efficient) collision
resistant hashing. In some scenarios, lack of key commitment can be a
problem [DGRW18], [LGR21], [ADG+22] and adding some mitigation would
be useful. Several approaches to add key commitment are shown in
[ADG+22] and some methods have already been deployed in real cloud
systems (e.g., AWS Encryption SDK [Gue20]).
1.3. DNDKGCM Design Goals
DNDKGCM is designed to address the two AESGCM limitations with:
a) A small performance overhead compared to using AESGCM directly.
b) A simple construction that can reuse vetted and optimized AESGCM
implementations and leverage ubiquitous processor instructions on
popular architectures (e.g., AESNI [Gue10] and PCLMULQDQ [GK08]).
c) Security that relies only on the universally accepted assumption
that AES is a good pseudorandom permutation. This is already the
assumption that establishes the security of AESGCM.
2. Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in BCP
14 [RFC2119] [RFC8174] when, and only when, they appear in all
capitals, as shown here.
3. Preliminaries and Notation
Gueron Expires October 15, 2024 [Page 5]
InternetDraft DNDKGCM April 2024
A byte is an integer between 0 and 255. It is represented here by two
hexadecimal digits. For example, the integers 5 and 135 are denoted
by 0x05 and 0x87, respectively.
Let U be an array of bytes ("array" for short) of length u (bytes),
written as U = U [u1] U [u2] ... U [0], where U [j] is the jth
byte, j = 0, ..., u1. By convention, the bytes are listed here in an
ordering such that U [u1] is in the leftmost position and U [0] is
in the rightmost position.
For integers a, b such that 0 <= b <= a <=(u1), T = U [a: b] denotes
the subarray U [a] U [a1] ...U [b] of length (ab+1) where T [j] =
U [j + b], j = 0, 1, ..., (a  b). To avoid confusion, note that in
this document, the two boundary indices are included in the range
(contrary to conventions used in some (not all) programming
languages). For completeness, in the case where
0 <= b = a+1 <=(u1)the subarray U [a: b] is understood to be empty.
Concatenation of byte arrays is denoted by "". If U1 = U1 [u11] U
[u12] ... U [0] and U0 = U0 [u01] U [u02] ... U [0] then U1  U2
is the array W = W [u1+u01: 0] of u1+u2 bytes such that W [u1+u0 1
: u0] = U1 and W [u01: 0] = U0.
For an integer s, (0x00)^s denotes an array of s zero bytes. An array
of 16 bytes is also called a "block".
The symbol FAIL is used here to indicate a failed integrity check.
Here, AES refers to the Advanced Encryption Standard [AES],
specifically, to the version with a 256bit key (equivalently 32byte
key) AES256. If K (key) is an array of 32 bytes and P (plaintext) is
an array of 16 bytes, then (ciphertext) C = AES (K, P) is the 16byte
array that results from encrypting P with AES under the key K.
Here, AESGCM refers to the Authenticated Encryption with Additional
Gueron Expires October 15, 2024 [Page 6]
InternetDraft DNDKGCM April 2024
Data (AEAD) scheme standardized in [GCM]. AESGCM encryption and
decryption are denoted AESGCM.Enc and AESGCM.Dec, respectively.
They take the tuples (N, A, M) and (N, A, C, T), respectively, where
N is a nonce, A is the Additional Authenticated Data (AAD), M is the
message, C is the ciphertext, and T is the authentication tag. Here,
the inputs and outputs are assumed to be arrays of bytes, K is an
array of 32 bytes, N is an array of 12 bytes, T is an array of 16
bytes, A is an array of at most 2^61  1 bytes and M (and C) is an
array of at most 2^36  32 bytes.
4. DNDKGCM Definition
DNDKGCM is an AEAD scheme that encrypts and authenticates a message,
along with additional authenticated data (AAD), using a 24byte nonce
that is selected uniformly at random for every message.
4.1. Input and Output Ranges
DNDKGCM is defined with the length and range parameters K_LEN,
N_LEN, A_MAX, P_MAX, C_MAX, T_LEN, and KC_LEN. Encryption is denoted
by DNDKGCM.Enc and decryption is denoted by DNDKGCM.Dec. These
procedures are defined for inputs that are arrays of bytes.
DNDKGCM.Enc takes a tuple (K, N, A, M) where K is the root key, N is
the nonce, A is the AAD, and M is the message. It outputs ciphertext
C, an authentication tag T and a commitment value KC. DNDKGCM.Dec
takes a tuple (K, N, A, C, T, KC), where K is the root key, N is the
nonce, A is the AAD, C is the ciphertext, T is the authentication tag
and KC is the commitment value. It outputs a message M with the same
bytelength as C, or a failure indication (FAIL).
The root key (K) MUST consist of K_LEN bytes. It MUST be selected
uniformly at random and be known only to the parties (sender and
recipient) that use the scheme. The nonce (N) MUST consist of N_LEN
bytes and MUST be selected uniformly at random for every encryption.
Gueron Expires October 15, 2024 [Page 7]
InternetDraft DNDKGCM April 2024
The AAD (A) MUST consist of at most A_MAX bytes, the message (M) MUST
consist of at most P_MAX bytes, the ciphertext (C) MUST consist of at
most C_MAX bytes, the authentication tag (T) MUST consist of T_LEN
bytes, and the key commitment value (KC) MUST consist of KC_LEN
bytes. The arrays A, M, C may be empty.
DNDKGCM is defined with the following parameter values: K_LEN = 32,
N_LEN = 24, A_MAX = 2^61  1, P_MAX = 2^36  32, C_MAX = 2^36  32,
T_LEN = 16, and KC_LEN = 32.
Tag truncation: AESGCM specification [GCM] (section 5.2.1.2) allows
16byte tags to be truncated down to 12 bytes (or even to shorter
tags of 8 or 4 bytes, where these lengths are accepted subject to
some usage constraints explained in appendix C of [GCM]). For
simplicity and brevity, this document defines DNDKGCM only with a
16byte tag and implicitly ignores a tag truncation option (even to
the seemingly innocuous truncation to 12 bytes). However, DNDKGCM
usages that require (and settle with) a shorter tag of d < 16 bytes,
MAY truncate the tag T [15: 0] to T [d1, d2, ..., 0] for d = 12, 8,
or 4 as indicated in [GCM]. The agreement on such truncation is left
for the communicating parties or protocol.
4.2. The Preamble: DeriveL12vL2L3
This section defines the two algorithms "SplitArray" and "DeriveL1
2vL2L3". SplitArray takes an array N of 2v bytes and outputs two
arrays N1 and N0 of v bytes. DeriveL12vL2L3 takes a root key (K)
of L1 bytes and a nonce (N) of 2v bytes (1 <= v <= 15). It outputs a
derived key (DerivedKey) of L2 bytes and a key commitment value
(KeyCommit) of L3 bytes.
This document fixes the parameter values to L1 = L2 = L3 = 32 and v =
12 (i.e., N (nonce) has 24 bytes). For short, Derive32243232 is
referred to as "Derive".
Gueron Expires October 15, 2024 [Page 8]
InternetDraft DNDKGCM April 2024
Algorithms 1 and 2 define SplitArray and Derive.
++
 
 Algorithm 1. SplitArray (v, N) 
 Input: Integer v (v <= 15), array N = N [2v  1: 0] 
 N1 = N1 [v1: 0] = N [2v1: v] 
 N0 = N0 [v1: 0] = N [v1: 0] 
 Output: N1, N0 
 
++
Gueron Expires October 15, 2024 [Page 9]
InternetDraft DNDKGCM April 2024
++
 
 Algorithm 2. Derive (K, N) 
 Input: root key K, array of 2v bytes N = N [2v  1: 0] 
 Context: nonce length 2v 
 (N1, N0) = SplitArray (v, N) 
 For j in {1, 3, 5, 7, 9} 
 Bj [15: (16v)] = N1 [v1: 0] 
 Bj [(15v): 1] = (0x00)^(15v) 
 Bj [0] = j 
 For j in {0, 2, 4, 6, 8} 
 Bj [15: (16v)] = N0 [v1: 0] 
 Bj [(15v): 1] = (0x00)^(15v) 
 Bj [0] = j 
 For j = 0, ..., 9 
 itijbucgcinnvullehcrjdiheicn Xj = AES (K, Bj)

 For j = 2, 3, ..., 9
cdbd 
 Yj = Xj XOR X [j mod 2] 
 KeyCommit [31: 16] = Y8 XOR Y9 
 KeyCommit [15: 0] = Y6 XOR Y7 
 DerivedKey [31: 16] = Y4 XOR Y5 
 DerivedKey [15: 0] = Y2 XOR Y3 
 Output: (KeyCommit [31: 0], DerivedKey [31: 0]) 
 
++
Gueron Expires October 15, 2024 [Page 10]
InternetDraft DNDKGCM April 2024
Figure 1 illustrates the flows of Algorithms 1 and 2 from the "double
nonce" N to DerivedKey and KeyCommit. For convenience, Appendix A
shows these flows with explicit indexes.
++
 
N = N23 N22 N21 N20 N19 N18 N17 N16 N15 N14 N13 N12 \\ 
 N11 N10 N09 N08 N07 N06 N05 N04 N03 N02 N01 N00 
N1 = N23 N22 N21 N20 N19 N18 N17 N16 N15 N14 N13 N12 
N0 = N11 N10 N09 N08 N07 N06 N05 N04 N03 N02 N01 N00 

  = N1  0x000000 
[  0x01] [  0x03] [  0x05] [  0x07] [  0x09] 
      
 V V V V V 
 AES (K,*) AES (K,*) AES (K,*) AES (K,*) AES (K,*) 
      
 V V V V V 
 >> + > + > + > + 
 Y3 Y5 Y7 Y9 

  = N0  0x000000 
[  0x00] [  0x02] [  0x04] [  0x06] [  0x08] 
      
 V V V V V 
 AES (K,*) AES (K,*) AES (K,*) AES (K,*) AES (K,*) 
      
 V V V V V 
 >> + > + > + > + 
 Y2 Y4 Y6 Y8 

 Y3 Y5 Y7 Y9 
 + + + + 
Gueron Expires October 15, 2024 [Page 11]
InternetDraft DNDKGCM April 2024
 Y2 Y4 Y6 Y8 
     
 V V V V 
 DK [31: 16] DK [15: 0] KC [31: 16] KC [15: 0] 
 
++
Figure 1. The flows of Algorithms 1 and 2 from the double
nonce N to the derived key (DK) and key commit value (KC).
4.3. Encryption
DNDKGCM.Enc receives the tuple (K, N, A, M) as input. It is assumed
that the caller has generated N, uniformly at random prior to
invoking DNDKGCM.Enc (or that DNDKGCM.Enc starts with such
generation) and this step is not shown here. DNDKGCM.Enc runs the
preamble Derive over K and N and computes a derived key DK and a key
commitment value KC. Subsequently, DNDKGCM.Enc invokes AESGCM.Enc
with DK as the encryption key, a nonce NZ12 of 12 zero bytes, A and
M. This produces the ciphertext C with the same length as M and the
authentication tag T. The output is (C, T, KC). DNDKGCM.Enc is
defined by Algorithm 3.
Gueron Expires October 15, 2024 [Page 12]
InternetDraft DNDKGCM April 2024
++
 
 Algorithm 3. DNDKGCM.Enc 
 Input: K, N, A, M 
 NZ12 = (0x00)^12 
 (KC, DK) = Derive (K, N) 
 (C, T) = AESGCM.Enc (DK, NZ12, A, M) 
 Output: C, T, KC 
 
++
4.4. Decryption
DNDKGCM.Dec receives the tuple (K, N, A, C, T, KC) as input.
It runs the preamble Derive over K and N and computes a derived key
DK and a key commitment value contender KC'. If KC' is not equal to
KC, the decryption aborts and outputs the failure indication FAIL.
Otherwise, the procedure runs AESGCM.Dec with DK as the decryption
key, a nonce NZ12 of 12 zero bytes, A, C and T. This either retrieves
a message M with the same length as C, or an authentication failure
indication FAIL. The output of DNDKGCM.Dec is, accordingly, either M
or FAIL. The decryption does not release (any part of) M before it is
fully authenticated. DNDKGCM.Dec is defined by Algorithm 4.
Gueron Expires October 15, 2024 [Page 13]
InternetDraft DNDKGCM April 2024
++
 
 Algorithm 4. DNDKGCM.Dec 
 Input: K, N, A, C, T, KC 
 NZ12 = (0x00)^12 
 (KC', DK) = Derive (K, N) 
 If KC' \ne KC output FAIL and abort 
 M / FAIL = AESGCM.Dec (DK, NZ12, A, C, T) 
 Output: M or FAIL 
 
++
Appendix A provides a stepbystep detailed example.
4.5. No Key Commit Value Option
It is possible to use DNDKGCM without the key commit value (KC) for
usages where the standard properties of AEAD suffice. For example, in
the case where a party decrypting a ciphertext blob has means to
confirm that its root key was also the key used for encrypting the
blob. When KC is not required for decryption, it does not need to be
generated during encryption nor sent with the ciphertext blob. In
such cases, the Derive function can skip the AES calls that produce
KC, reducing the number of AES invocations from 10 to 6.
5. AEAD
Gueron Expires October 15, 2024 [Page 14]
InternetDraft DNDKGCM April 2024
We define an AEAD, in the format of [RFC5116], that uses DNDKGCM,
namely AEAD_DNDK_GCM.
The key input to this AEAD becomes the root key. Thus, AEAD_DNDK_GCM
takes a 32byte key.
6. Security Considerations
An invocation of DNDKGCM.Enc MUST use a (24byte) nonce that is
selected uniformly at random from the nonce space (in particular, the
selection of a nonce value for encryption should be unpredictable by
an outside observer).
Note that nonrepeating but nonrandom nonces (e.g., implemented as a
counter) are not acceptable for DNDKGCM. Such nonce selection could
lead to linear dependence in (N1, N0) values (at least without taking
steps to avoid it e.g., by fixing N1 = (0xFF)^12 and a running a
counter for N0). This is not a real limitation because scenarios that
can use a counter nonce can also use the standard AESGCM. In such
cases, using the doublelength of DNDKGCM is pointless.
DNDKGCM decryption involves two verifications: an optional match on
the key commitment value, and a match on the authentication tag in
the AESGCM.Dec invocation. An implementation MUST NOT release the
plaintext or any part of it before it is (doubly) authenticated
because otherwise parts of a system may process malicious data as if
it were authentic.
7. Design Rationale
The first goal of the DNDKGCM design is to overcome the short nonce
limitation of AESGCM, in the random nonce (stateless) setting. To
this end, DNDKGCM encryption (and decryption) consumes a double
Gueron Expires October 15, 2024 [Page 15]
InternetDraft DNDKGCM April 2024
length (random) nonce of 24 bytes, such that nonce collision
probability after Q samples is upper bounded by Q^2/2^193.
DNDKGCM.Enc invokes the pseudorandom function Derive (Algorithm 2)
to produce the fresh encryption key and a key commitment value. This
preamble step generalizes the DeriveKey design of [GL17] (which is
used for AESGCMSIV [RFC8452]). The difference is that the (double)
nonce is used only for the derivation and not for the AESGCM
encryption. However, the distinguishing advantage of Derive with Q
samples, and the collision probability of Q 32byte (truly) random
derived keys is kept negligible (at most Q^2/2^257) for the target
Q = 2^64 encryptions.
With this design, the random nonce setting is converted to a
multipleonetimekeys setting for AESGCM. Here, every key is used
for encrypting exactly one message, and it is therefore possible to
use a fixed AESGCM nonce (0x00^12 here).
The pseudorandom function Derive is a "double XORP": a variant of the
XORP construction [Iwa06] over two halves of the nonce. The Beyond
BirthdayBound indistinguishability is deduced from [BGK99]. The
security relies only on one cryptographic primitive, namely AES, and
on its pseudorandom permutation (PRP) advantage when used with
uniform random keys:
If Q keys K1, K2, ..., KQ are selected uniformly at random from the
AES key space, then AES outputs from chosen blocks and any choice
of a key from the list K1, K2, ..., KQ, are indistinguishable from
the outputs of Q corresponding preselected random permutations of
the space of 128bit strings, even after a very large number of
queries (Q). The case Q=1 is the standard assumption in the single
key setting.
Derive requires only 10 calls to AES256 with the root key, computed
and over independent blocks, where these computations can therefore
Gueron Expires October 15, 2024 [Page 16]
InternetDraft DNDKGCM April 2024
be parallelized. In addition, every encryption requires also an
AES256 key expansion with the fresh derived key (and other
initialization steps for AESGCM). The total overhead, however, is
relatively small (see [Gue24] for a full account).
7.1. Security Bounds
The privacy bounds of DNDKGCM rely on the designated parameters.
Assume that DNDKGCM is used for encrypting Q <= 2^64 messages with
lengths L1, L2, ..., LQ blocks. Assume that the PRP advantage of AES
(in this multikey setting) is negligible for such Q. Then, the
following holds: a) The distinguishing advantage of Derive is
negligible; b) The probability to encounter a collision in the Q
randomly generated 24byte nonces, and the probability to encounter a
collision in the Q derived 32byte encryption keys are negligible.
Under these conditions, the distinguishing advantage of passively
viewed ciphertexttag pairs from chosen inputs, and uniform random
strings of the matching lengths, is either less than 2^32 or
dominated by the sum
Sum ((L_i+2)^2/2^129, i=1, ..., Q)
For example, under the PRP assumption on AES, processing 2^64
messages of L_i = 2^16  2 blocks (2^20  32 bytes) would lead to
indistinguishability margins of ~2^32.
To find two (adversarial) keys K1, K2, and two NAM triples such
that DNDKGCM.Enc (K1, N1, A1, M1) = DNDKGCM.Enc (K2, N2, A2, M2),
an adversary needs to find 32byte keys K1, K2 such that the 32byte
key commitment values (KeyCommit)agree.
A detailed analysis is available in [Gue24].
8. IANA Considerations
Gueron Expires October 15, 2024 [Page 17]
InternetDraft DNDKGCM April 2024
IANA needs to add one entry to the "AEAD Algorithms" registry:
AEAD_DNDK_AES_256_GCM (Numeric ID TBD) referencing this document as
its specification.
9. References
9.1. Normative References
[AES] National Institute of Standards and Technology, "Advanced
Encryption Standard (AES)", FIPS 197,November 2001.
The original reference (FIPS 197 standard), dated 2001 was
superseded in May 2023; the new DOI is
https://doi.org/10.6028/NIST.FIPS.197upd1
[GCM] Dworkin, M., "Recommendation for Block Cipher Modes of
Operation: Galois/Counter Mode (GCM) and GMAC", NIST SP
80038D, DOI 10.6028/NIST.SP.80038D, November 2007,
https://csrc.nist.gov/publications/detail/sp/80038d/final.
Note: the GCM specification (NIST SP 80038D) is planned to
be revised in the near future.
https://csrc.nist.gov/News/2024/nisttorevisesp80038d
gcmandgmacmodes
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, DOI
10.17487/RFC2119, March 1997, .
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119
Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May
2017, .
9.2. Informative References
Gueron Expires October 15, 2024 [Page 18]
InternetDraft DNDKGCM April 2024
[RFC5116] McGrew, D., "An Interface and Algorithms for Authenticated
Encryption", RFC 5116, DOI 10.17487/RFC5116, January 2008,
.
[ADG+22] Albertini, A., Duong, T., Gueron, S., Kolbl, S., Luykx, A.,
Schmieg, S., "How to Abuse and Fix Authenticated Encryption
Without Key Commitment", in Proceedings of the 31st USENIX
Security Symposium (USENIX Security 22), pp. 32913308,
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/3540484051_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. 155186,
Springer, 2018. [Online]. Available:
https://doi.org/10.1007/9783319968841_6
[Gue10] Gueron, S., "Intel Advanced Encryption Standard (AES)
Instructions Set", Intel White Paper, Rev. 3, 194, 2010.
[Online]. Available:
https://www.intel.com/content/dam/doc/whitepaper/advanced
encryptionstandardnewinstructionssetpaper.pdf
[Gue20] Gueron, S., "Key Committing AEADs", Cryptology ePrint
Archive, Paper 2020/1153, 2020. [Online]. Available:
https://eprint.iacr.org/2020/1153
Gueron Expires October 15, 2024 [Page 19]
InternetDraft DNDKGCM April 2024
[Gue24] Gueron, S., "Double Nonce Derive Key AESGCM", Cryptology
ePrint Archive, Paper 2024/TBD, 2024. [Online]. To be
available on https://eprint.iacr.org/2024/
[GK08] Gueron, S., Kounavis, M., "CarryLess Multiplication and
Its Usage for Computing the GCM Mode", Intel White Paper,
Rev. 2.02, 184, 2014. [Online]. Available:
https://www.intel.com/content/dam/develop/external/us/en/do
cuments/clmulwprev20220140420.pdf
[RFC8452] Gueron, S. Langley, A, and Lindell, Y., "AESGCMSIV: Nonce
MisuseResistant 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 NonceBased 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 1113, 2021, pp. 195212. [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. 310327, Springer, 2006. [Online].
Available: https://doi.org/10.1007/11799313_20
Appendix A. The Preamble Procedure Flow With Explicit Indexes
Gueron Expires October 15, 2024 [Page 20]
InternetDraft DNDKGCM April 2024
Figures 2a, 2b, 2c illustrate the preamble procedure flow with
explicit indexes, starting from N to DerivedKey and KeyCommit.
++
 
 Long Nonce 
  
 N = 
 N[23] N[22] N[21] N[20] N[19] N[18] N[17] N[16] N[15] 
 N[14] N[13] N[12] N[11] N[10] N[9] N[8] N[7] N[6] N[5] 
 N[3] N[2] N[1] N[0] 
 
 Split Nonce 
  
 N1 = 
 N[23] N[22] N[21] N[20] N[19] N[18] 
 N[17] N[16] N[15] N[14] N[13] N[12] 
 N0 = 
 N[11] N[10] N[9] N[8] N[7] N[6] 
 N[5] N[4] N[3] N[2] N[1] N[0] 
 
++
Figure 2a.
Gueron Expires October 15, 2024 [Page 21]
InternetDraft DNDKGCM April 2024
++
 
 The 10 blocks for Derive 
  
 B1 = N[23] N[22] N[21] N[20] N[19] N[18] N[17] N[16] 
 N[15] N[14] N[13] N[12] 0 0 0 1 
 B3 = N[23] N[22] N[21] N[20] N[19] N[18] N[17] N[16] 
 N[15] N[14] N[13] N[12] 0 0 0 3 
 B5 = N[23] N[22] N[21] N[20] N[19] N[18] N[17] N[16] 
 N[15] N[14] N[13] N[12] 0 0 0 5 
 B7 = N[23] N[22] N[21] N[20] N[19] N[18] N[17] N[16] 
 N[15] N[14] N[13] N[12] 0 0 0 7 
 B9 = N[23] N[22] N[21] N[20] N[19] N[18] N[17] N[16] 
 N[15] N[14] N[13] N[12] 0 0 0 9 
  
 B0 = N[11] N[10] N[9] N[8] N[7] N[6] N[5] N[4] 
 N[3] N[2] N[1] N[0] 0 0 0 0 
 B2 = N[11] N[10] N[9] N[8] N[7] N[6] N[5] N[4] 
 N[3] N[2] N[1] N[0] 0 0 0 2 
 B4 = N[11] N[10] N[9] N[8] N[7] N[6] N[5] N[4] 
 N[3] N[2] N[1] N[0] 0 0 0 4 
 B6 = N[11] N[10] N[9] N[8] N[7] N[6] N[5] N[4] 
 N[3] N[2] N[1] N[0] 0 0 0 6 
 B8 = N[11] N[10] N[9] N[8] N[7] N[6] N[5] N[4] 
 N[3] N[2] N[1] N[0] 0 0 0 8 
 
Gueron Expires October 15, 2024 [Page 22]
InternetDraft DNDKGCM April 2024
++
Figure 2b.
Gueron Expires October 15, 2024 [Page 23]
InternetDraft DNDKGCM April 2024
++
 
 Double XORP XORs (here, "^" is XOR 
  
 Y[2]  Y[3]  Y[4]  Y[5]  
 X[2] ^ X[0]  X[3] ^ X[1]  X[4] ^ X[0]  X[5] ^ X[1]  
  
 Y[6]  Y[7]  Y[8]  Y[9] 
 X[6] ^ X[0]  X[7] ^ X[1]  X[8] ^ X[0]  X[9] ^ X[1] 
 
 The 10 encryption calls 
  
 X0 = E (K, B0) X1 = E (K, B1) X2 = E (K, B2) 
 X3 = E (K, B3) X4 = E (K, B4) X5 = E (K, B5) 
 X6 = E (K, B6) X7 = E (K, B7) X8 = E (K, B8) 
 X9 = E (K, B9) 
 
 The doubleXORP XORs 
  
 Y2 = X2 ^ X0  Y3 = X3 ^ X1  Y4 = X4 ^ X0  Y5 = X5 ^ X1  
 Y2 = X2 ^ X0  Y3 = X3 ^ X1  Y4 = X4 ^ X0  Y5 = X5 ^ X1  
 
 The key commitment value 
  
 KeyCommit [31: 16]  KeyCommit [15: 0]  
   
Gueron Expires October 15, 2024 [Page 24]
InternetDraft DNDKGCM April 2024
 Y8 ^ Y9  Y6 ^ Y7 
 
 The derived messagekey 
  
 DerivedKey [31: 16]  DerivedKey [15: 0]  
   
 Y4 ^ Y5  Y2 ^ Y3 
++
Figure 2c.
Appendix B. A WorkedOut Example
Following is a DNDKGCM encryption example. Arrays of bytes are typed
in increasing order of byte positions from left (byte 0) to right.
++
 Bytes Position 
 0001020304050607080910111213141516171819202121232425262728293031 
 000102030405060708091011121314151617181920212123 
 00010203040506070809101112131415 
  
 Root key: 
 0100000000000000000000000000000000000000000000000000000000000000 
 
 Input: 
 Nonce: 
 000102030405060708090a0b0c0d0e0f1011121314151617 
 aad: 0100000011 
 plaintext: 11000001 
 
Gueron Expires October 15, 2024 [Page 25]
InternetDraft DNDKGCM April 2024
 Derived key: 
 18c272b0158afa71ed99b64e5e39daaaaae37e70fa1b46407256c0b6f8531a64 
 
 Output: 
 Key Commit Value (KC) 
 1fd1839805fce095052919629ca8947766d08eeee135cdf261228bfd4a796bbb 
 ciphertext: e6de36f2 
 tag: e5973b407bafcd39a20f92ac8d1f5629 
 
 Intermediate Values: 
 
 Split Nonce: 
 Nonce [0]: 000102030405060708090a0b 
 Nonce [1]: 0c0d0e0f1011121314151617 
 
 B0: 00000000000102030405060708090a0b 
 B1: 010000000c0d0e0f1011121314151617 
 B2: 02000000000102030405060708090a0b 
 B3: 030000000c0d0e0f1011121314151617 
 B4: 04000000000102030405060708090a0b 
 B5: 050000000c0d0e0f1011121314151617 
 B6: 06000000000102030405060708090a0b 
 B7: 070000000c0d0e0f1011121314151617 
 B8: 08000000000102030405060708090a0b 
 B9: 090000000c0d0e0f1011121314151617 
 
 X0: b0fbcb02c071f4a25de23297e13d7066 
 X1: 19d1e1933ad4334fd02cc82d5c4a72f1 
 X2: d33a0c752571ba59daaf250dbf59ef56 
 X3: 62d25454ca5e87c5baf869f95c17376b 
Gueron Expires October 15, 2024 [Page 26]
InternetDraft DNDKGCM April 2024
 X4: 1910758c06e22831fd772c93eb731d55 
 X5: 1ad9216d065ca99c02ef169fae5705a6 
 X6: e5025a0563681bbfa686600e3ebed7a6 
 X7: 53f9f30c9c313cc72e6183d61f614146 
 X8: ebd781624db0d882664f49b4f38d61b4 
 X9: 242d251d5620d29d8aa338f304830898 
 
 Y2: 63c1c777e5004efb874d179a5e649f30 
 Y3: 7b03b5c7f08ab48a6ad4a1d4005d459a 
 Y4: a9ebbe8ec693dc93a0951e040a4e6d33 
 Y5: 0308c0fe3c889ad3d2c3deb2f21d7757 
 Y6: 55f99107a319ef1dfb645299df83a7c0 
 Y7: 4a28129fa6e50f88fe4d4bfb432b33b7 
 Y8: 5b2c4a608dc12c203bad7b2312b011d2 
 Y9: 3dfcc48e6cf4e1d25a8ff0de58c97a69 
 
 Derived Key (DK): 
 18c272b0158afa71ed99b64e5e39daaaaae37e70fa1b46407256c0b6f8531a64 
 
 DK [0]: 18c272b0158afa71ed99b64e5e39daaa 
 DK [1]: aae37e70fa1b46407256c0b6f8531a64 
 
 Key commit value (KC): 
 1fd1839805fce095052919629ca8947766d08eeee135cdf261228bfd4a796bbb 
 KC [0]: 1fd1839805fce095052919629ca89477 
 KC [1]: 66d08eeee135cdf261228bfd4a796bbb 
 
 Bytes Position 
 0001020304050607080910111213141516171819202121232425262728293031 
 000102030405060708091011121314151617181920212123 
Gueron Expires October 15, 2024 [Page 27]
InternetDraft DNDKGCM April 2024
 00010203040506070809101112131415 
  
++
10. Acknowledgments
The author would like to thank Gerald Doussot, Isaac Elbaz, Sasha
Frolov, Ed Knapp, Thomas Pornin, Eric Schorn for their comments and
suggestions.
11. Authors' Addresses
Shay Gueron
University of Haifa
Abba Khoushy Ave 199
Haifa 3498838, Israel
Email: shay.gueron@gmail.com
Gueron Expires October 15, 2024 [Page 28]