Christoph Dobraunig, Intel Labs
Krystian Matusiewicz, INT31
Alexander Tereschenko, INT31
Bart Mennink, Radboud University
This post discusses our recent research project on novel symmetric cryptography constructions. We will discuss modern go-to ciphers and where they fall short with modern-day data volumes. Then, we will discuss a new construction—cryptographic accordion—that aims to fix that and why NIST is interested in standardizing it. Finally, we will also present our proposed implementations of that construction, the ddd-aes family of ciphers.
Ciphers, Modes, and Why They are Failing Us
One of the fundamental classes of cryptographic algorithms are block ciphers. A block cipher takes as input a key and then transforms a fixed-width bit string of plaintext into a corresponding ciphertext of the same length. One can think of a block cipher as a family of random-looking permutations indexed by the key, and setting the key picks one permutation from the set. The most common block cipher – Advanced Encryption Standard (AES) - has blocks of size 128 bits.
In practical applications, one wants to encrypt data with an arbitrary length, not only 128 bits. To achieve this, we need a block cipher's mode of operation—a way of using the block cipher to process arbitrary-length data (and potentially provide additional properties like integrity).
Over the years, many modes of operation were developed and standardized. For example, the US National Institute of Standards and Technology (NIST), one of the worldwide standards-setting bodies in cryptography, has a series of publications defining those in standards SP 800-38 A through G.
One of the classical modes is the so-called Counter Mode (CTR), defined in NIST SP 800-38A, that only provides data confidentiality. Combine this with message authentication (highly desirable in this day and age!) based on polynomial evaluation over Galois fields, and you get a modern go-to cipher mode called Galois Counter Mode (GCM), defined in SP 800-38D.
All ciphers and modes have accompanying security proofs (or, more precisely, security reductions), which in modern cryptography typically rely on certain assumptions about the attacker's computational and storage limitations. Those proofs are valid up to certain limits, typically measured in units of data volume processed.
Let us dive deeper into how Counter Mode works and its intrinsic limitations. The basic idea is to use block cipher calls to transform a sequence of known values into a pseudorandom sequence of output bits that can be simply XORed with the plaintext. This effectively constructs a stream cipher with the keystream generated from the outputs of block cipher encryption calls.
The crucial observation is that the input values to the blocks need to be distinct, since in that case we have the guarantee that the outputs are also distinct.
This requirement is realized in practice by logically splitting the input to each block cipher call into two parts: a block counter and a so-called nonce (“number used once”). The block counter is simply incremented by one with each successive block cipher call. The nonce is a bit string that needs to be unique across all the usages of the same encryption key.
If the nonce repeats, keystream outputs also repeat, and the attacker can recover the XOR of the two plaintexts by XORing the two ciphertexts, thus completely breaking the encryption scheme. In a sense, ensuring the uniqueness of nonces is as important as ensuring the confidentiality of the encryption key.
This makes the selection of nonces of utmost importance for the system's overall security. One could, of course, use a monotonic counter that would guarantee no nonce repeats until all values are exhausted, but this requires maintaining and synchronizing the counter state—pretty inconvenient in parallel, often distributed systems.
The only other viable option is to generate nonces uniformly at random and rely on a probabilistic argument that the probability that any two nonces happen to be the same is negligible. However, this probability is larger than expected due to the “birthday paradox”. For n-bit nonces, the probability of a collision between generated values is almost one half when only 2^(n/2) nonces have been generated.
For nonces that are 96-bit long (a common value standardized in NIST SP800-38A/D), we need to stay way below 2^48 values. To achieve the probability of collision not exceeding 2^(-32) mandated by the NIST specification, we cannot use more than 2^32 nonces with one key.
Another issue with GCM mode is that its security degrades with the amount of encrypted data (because, over time, we get more encrypted blocks overall). This imposes another, even stricter limit on mode usability.
To put these limits into perspective, modern cloud-scale data volumes measure in zettabytes: in 2024, the worldwide cloud generated data volume was about 38ZB and total installed storage was approximately 5ZB (sources: IDC’s Global DataSphere and Global StorageSphere, 2024), growing at around 40% and 25% CAGR (Compound Annual Growth Rate), respectively. Traditional data center and AI/ML-serving networks use high-speed links up to 800Gbps, with 1600Gbps on the horizon. At those scales, the limits we discussed could be exhausted by a modern network in seconds and are orders of magnitude smaller than cloud-scale datasets.
That necessitates frequent rekeying, since we need to update the encryption key to a new one once we exhaust the allowable nonce space, and rekeying is costly in large-scale deployments since we need to synchronize rekeying on both ends of the encrypted channel.
In addition to the above woes, there are other issues with the traditional modes, such as non-ideal diffusion properties for the XTS mode due to it building upon the relatively “narrow-block” AES (of 128 bits), or the 128-bit block becoming a bottleneck for modern data volumes due to the associated generic birthday bound of 2^64 blocks (this property underlies the Sweet32 attack, for example, though for a smaller-block DES). For those interested in learning more, NIST has published a comprehensive overview and analysis of those traditional modes with some recommendations in its IR 8459 document.
Having looked at the aforementioned limitations and difficulties, can we do better than that?
The Cryptographic Accordion to the Rescue
With the challenges mounting, the cryptographic community is looking for ways to fix that. In that vein, NIST has initiated a project to develop a new construct called “cryptographic accordion”. That construct aims to solve many traditional cipher mode shortcomings, utilizing decades of cryptologic research and practical application of those original 800-38-family standards. Starting in 2023, so far, the NIST has held several workshops discussing potential approaches and requirements for that construct (see the latest one here: NIST Workshop on the Requirements for an Accordion Cipher Mode 2024) and published a final document outlining general definitions, approaches, and requirements for accordions – NIST IR 8552.
We refer you to the latter document for all the details, but what is the cryptographic accordion at the high level? In NIST’s own words, the term cryptographic accordion – or simply accordion – describes "a technique constructed from an underlying block cipher that acts like a cipher on inputs of varying sizes. Thus, an accordion is simultaneously a cipher and a mode of the underlying block cipher. An accordion is defined as a tweakable, variable-input-length-strong pseudorandom permutation (VIL-SPRP) constructed from an underlying block cipher."
Figure 2 illustrates the main properties of the accordion. It can shrink and expand to accommodate variable input lengths (the “accordion”!), and it is also a strong pseudorandom permutation, so any change in the input changes the whole output.
As you can see, several layers of abstraction are at play here. The lowest layer is the block cipher, out of which one builds the accordion, which, in a nutshell, forms a virtual tweakable flexible-size wide-block cipher. Based on that foundation, NIST envisions building the so-called derived functions, providing higher-level functionality like AEAD, deterministic authenticated encryption, and so on. Here is a helpful diagram from IR 8552 illustrating those layers:
There are various requirements, including security ones, formulated for accordions and derived functions, and among them are those fixing the problems of traditional modes we outlined earlier. There are things like bigger block sizes (256 bits) for the underlying block cipher, to provide the fundamental security beyond the current 128-bit AES for huge modern data volumes; beyond-birthday-bound security for accordions built upon the AES, to provide better security while still benefitting from all the investments into AES accelerators; multi-user security and key- and context-commitment – properties the cryptographic community learned to value over the years of using traditional modes that don’t necessarily provide them.
As one practical example, the accordion itself would immediately be more flexible and secure than the traditional XTS mode due to its wider and flexible block size. This would provide better diffusion that would cover the whole disk sector instead of only the 128-bit portions of it, and for any disk sector size, without changing the construct.
Thanks to accordion’s properties, implementing authenticated encryption with additional data (AEAD) derived function on top of it can be as simple as using the well-studied encode-then-encipher approach, while passing the nonce and the additional authenticated data (AAD) as the tweak. Figure 4 illustrates this approach.
To summarize, the accordion is almost “the one to rule them all” approach that incorporates the best cryptologic knowledge has to offer and aims to replace at least some, if not all, traditional modes while providing better practical flexibility and security for the cryptographic constructs utilizing them.
Process-wise, NIST plans to develop accordion(s) and derived functions independently, publishing draft specifications and inviting feedback from the wider community as they go along.
ddd-aes Family of Ciphers as a Practical Accordion Implementation
We have come to the core question—how to design an efficient and secure accordion mode, using a classical block cipher and potentially other simple constructs like universal hashing. The following will describe our approach in our proposal, which is described in the EUROCRYPT 2025 paper (full version on ePrint), together with the necessary background.
Since our task is constructing a strong pseudorandom permutation with a variable input length, we may recall how fixed-size SPRPs are built from smaller primitives.
The most natural starting point is the Feistel structure, which uses a smaller “round function” Fk to build a larger keyed permutation.
The first observation is that the left and right parts of the Feistel structure do not need to be equal in length. If one side is larger than the other, we get the so-called unbalanced Feistel network. This idea lets us make the size of the input and output flexible.
The second useful observation is the result of Luby and Rackoff, showing that four rounds of the Feistel structure are enough to build a secure SPRP, provided that the round function has appropriate properties.
A lot of research has been dedicated to the topic of secure constructions of that type, and one of them is the so-called docked double decker (ddd). The construction is presented in Figure 6.
The construction uses two types of functions: HL, which is a universal hash function with key L (polynomial evaluated at point L) and a fixed-input, variable-output pseudorandom function FK keyed by key K.
The input is split into three parts: T and V are fixed-size bitstrings of size equal to the size of the underlying block cipher and output of the universal hash. The middle part U is variable-size since it’s an input to the universal hashing (that can accept arbitrary lengths) and it is XORed with the output of the pseudorandom function that can also stretch arbitrarily.
Looking at the picture, one can see the “accordion” structure: values T and V serve as accordion’s handles while the middle part shrinks and stretches to accommodate the desired total input length.
ddd-aes Construction
To get a fully functional docked double decker-based accordion mode, we need to instantiate two functions: the universal hash HL and the pseudo-random function PRF FK. The performance and security level of the overall construction depends on the choice of those two functions.
Universal Hashing
Universal hashing is the simpler element of the design. A widely used function is GHASH used, e.g., in GCM authentication. In our design we opted for a very similar function, POLYVAL. Functionally, it works exactly like GHASH but is better-suited for ubiquitous little-endian platforms due to its native little-endianness.
Pseudo-Random Function
Designing a secure and efficient pseudo-random function is a more demanding challenge. We focused on designs that reuse AES block cipher due to its ubiquity and widespread hardware support, but it is of course also possible to have docked double decker constructions based on other PRF designs.
There are two variants of our design: a simpler one with its security limited by the classical birthday bound on the block cipher and a more advanced one that stays secure beyond the birthday bound limit of the queries.
PRF for ddd-aes
The first version is based on the XE (XOR – encrypt) construction by Rogaway where the tweak and block index are mixed with the input to the block cipher call, as shown in Figure 7. The tweak concatenated with flags get encrypted by the first call to AES and this value becomes one of the arguments to the finite field multiplication while the other argument is 2i where i is the block index. After XORing it with the input to the PRF, we obtain the inputs to the encryption calls. Encrypting those values gives us a sequence of pseudorandom blocks of bits that cannot be distinguished from random until we see enough to approach the birthday bound. This variant is very efficient as it requires essentially only one block cipher call per the output block (with just one extra call for tweak processing) making it comparable with counter mode encryption but the security is limited by the birthday bound, just like in other classical modes.
PRF for bbb-ddd-aes
The other, more secure version that goes beyond the birthday bound is based on a XORP construction by Iwata, but with the modification that adds the processing of the tweak.
The base XORP construction looks similar to the counter mode but adds one extra output of the encryption to the outputs of all blocks as illustrated in Figure 8. PRF input padded with counter values is encrypted by the block cipher calls. The key difference is that the first block is not output but is used to XOR its value to the subsequent outputs of the encrypted blocks. This method produces the output that is indistinguishable from random significantly beyond the birthday bound of 2^(n/2) calls for n-bit block cipher E.
However, for the docked double decker construction we need a PRF that also accepts a tweak value and we want to make it maintain its beyond birthday bound behavior even for limited tweak reuse scenarios. We do this by modifying the input to the XORP block cipher calls by feeding there encrypted values of the tweak and counter XORed with the input to the PRF as illustrated in Figure 9.
This way we get a PRF construction that stays secure beyond the birthday bound of the underlying block cipher and can provide security for much larger data volumes without the need to go for larger block cipher sizes.
What’s Next
This blog post is just a highlight of the work on our accordion design. If you want to dive deeper into this topic, we can recommend the following resources:
- A good starting point are the videos of the NIST Workshop on the Requirements for an Accordion Cipher Mode 2024
- An in-depth treatment of the construction is our paper published at EUROCRYPT 2025 [paper , slides , video]
- Our reference implementation is available at https://github.com/intel/ddd-aes
On June 6th 2025 NIST announced the intent to standardize an accordion mode, so we are sure we will hear much more about this new design direction in the coming months.
Share Your Feedback
We want to hear from you. Send comments, questions, and feedback to the INT31 team.
About the Authors
Alexander Tereschenko is a senior security architect, researcher, and cryptographer in INT31 with research interests in post-quantum crypto, cryptographic randomness, security protocols, cryptographic implementation security, and formal methods. He enjoys working with complex heterogeneous systems, connecting the dots, and has a passion for enhancing accessibility (a11y) of computer programs and documentation. Outside of work, he's a Free and Open Source software contributor and maintainer, and serves as a volunteer reviewer for The National Center for Women & Information Technology.
Christoph Dobraunig is a cryptographer in Intel Labs. He has done research in cryptography (analysis and design of symmetric cryptography) and implementation security (side-channel and fault attacks). However, his interests are not limited to these topics. He is a co-designer of the winner of the NIST lightweight cryptography standardization process and the first choice for lightweight applications in CAESAR, Ascon. Furthermore, he is a co-designer of Elephant and ISAP, two finalists of the NIST lightweight cryptography standardization process. Moreover, he is part of the SPHINCS+ Team. Currently, he has the honor of serving as Co-Editor-in-Chief for the IACR Transactions on Symmetric Cryptology (ToSC).
Krystian Matusiewicz is a cryptographer and a technical lead of the INT31 Cryptography Team that is tasked with making sure that the best possible cryptographic solutions are used in Intel products. Krystian has 20 years of experience in both academic cryptography research and industrial security engineering. He likes breaking things and building things that are hard to break.
In collaboration with Bart Mennink, Radboud University