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