Paper 2025/785

DNDK: Combining Nonce and Key Derivation for Fast and Scalable AEAD

Abstract

Authenticated encryption with associated data (AEAD) schemes are responsible for securing increasingly critical digital infrastructures, worldwide. Unfortunately, current widely deployed schemes suffer from various limitations that make them difficult to use securely in practice. For example, schemes like AES-GCM limit the amount of data that can be encrypted with a single key, therefore limiting its secure scaling to modern workloads. At the same time, practitioners may not be able to move away from the use of AES-GCM due to mature and widely deployed implementations, legacy constraints, and compliance. In this paper, we provide approaches to improve the secure scaling of AEAD schemes via what we call derived-nonce, derived-key (DNDK) transforms. At a high level, such transforms use a root key to derive a nonce and key for use with an underlying scheme. The challenge is doing so in a way that introduces as little overhead as possible, and relying on a small number of assumptions on the used primitives. We provide some general results about secure scaling transforms and a concrete design for AES-GCM that is called DNDK-GCM. It requires as little as three additional AES calls to enable use of the same key to encrypt up to $2^{64}$ bytes of data, even when using random nonces. We also provide a detailed performance analysis. DNDK-GCM is now a draft IETF standard, and is already deployed at the cloud scale by companies including Meta.