International Association
for Cryptologic Research

This talk will propose a new approach for building the next generation of AEAD. In the last few years, researchers and practitioners have discovered that widely deployed AEAD schemes, designed almost two decades ago, have many limitations. These range from uncomfortably small security margins to outright security vulnerabilities. We will discuss foundational theory and concrete designs for the next generation of AEAD schemes. Our designs better support real-world workloads while retaining performance.

Recent attacks and applications have led to the need for symmetric encryption schemes that, in addition to providing the usual authenticity and privacy, are also committing. In response, many committing authenticated encryption schemes have been proposed. However, all known schemes, in order to provide s bits of committing security, suffer an expansion---this is the length of the ciphertext minus the length of the plaintext---of 2s bits. This incurs a cost in bandwidth or storage. (We typically want s=128, leading to 256-bit expansion.) However, it has been considered unavoidable due to birthday attacks. We show how to bypass this limitation. We give authenticated encryption (AE) schemes that provide s bits of committing security, yet suffer expansion only around s as long as messages are long enough, namely more than s bits. We call such schemes succinct. We do this via a generic, ciphertext-shortening transform called SC: given an AE scheme with 2s-bit expansion, SC returns an AE scheme with s-bit expansion while preserving committing security. SC is very efficient; an AES-based instantiation has overhead just two AES calls. As a tool, SC uses a collision-resistant invertible PRF called HtM, that we design, and whose analysis is technically difficult. To add the committing security that SC assumes to a base scheme, we also give a transform CTY that improves Chan and Rogaway's CTX. Our results hold in a general framework for authenticated encryption that includes both classical AEAD and AE2 (also called nonce-hiding AE) as special cases, so that we in particular obtain succinctly-committing AE schemes for both these settings.

There has been a recent interest to develop and standardize Robust Authenticated Encryption schemes. NIST, for example, is considering an Accordion mode for (wideblock) tweakable blockcipher, with Robust AE as a primary application. At the same time, recent attacks and applications suggest that encryption context needs to be committed. Indeed, committing security is also a design consideration in Accordion mode. In this work, we give a modular solution for this problem. We first show how to transform any wideblock tweakable blockcipher TE to a Robust AE scheme SE that commits just the key. The overhead is cheap, just a few finite-field multiplications and blockcipher calls. If one wants to commit the entire encryption context, one can simply hash the context to derive a 256-bit subkey, and uses SE on that subkey. The use of 256-bit key on SE only means that it has to rely on AES-256 but doesn't require TE to have 256-bit key. Our approach frees the Accordion designs from consideration of committing security. Moreover, it gives a big saving for several key-committing applications that don't want to pay the inherent hashing cost of full committing.

This talk will make the case, on behalf of a group of authors of many of the recent results on commitment in AEAD, that the community should prioritize and standardize AEAD designs that achieve commitment to the key, associated data, and nonce. We call this context commitment. The main benefit of such schemes is that they preclude practitioners from having to make choices about what parts of the context should be committing. While context commitment has not yet seen the same kind of attacks in practice as key commitment, we expect them to be discovered and, to get ahead of attackers, standardization efforts should therefore target context commitment. We will start our presentation by defining context commitment [BH22], highlighting in particular how it is not formally implied by key commitment. We next discuss new attacks that exploit this gap, including showing context-commitment attacks on recently proposed key commitment-secure schemes [Kra19, §3.1.1], [ADG+22, §5.3], and [D+22]. These hint at a rich landscape of possible attacks, and we briefly discuss frameworks that explore this landscape [BH22,CR22,MLGR22]. Finally, we provide an overview of recent proposals for new AEAD schemes that achieve context commitment, and discuss avenues for future work.

This paper provides efficient authenticated-encryption (AE) schemes in which a ciphertext is a commitment to the key. These are extended, at minimal additional cost, to schemes where the ciphertext is a commitment to all encryption inputs, meaning key, nonce, associated data and message. Our primary schemes are modifications of GCM (for basic, unique-nonce AE security) and AES-GCM-SIV (for misuse-resistant AE security) and add both forms of commitment without any increase in ciphertext size. We also give more generic, but somewhat more costly, solutions.

We study the security of CTR-DRBG, one of NIST’s recommended Pseudorandom Number Generator (PRNG) designs. Recently, Woodage and Shumow (Eurocrypt’ 19), and then Cohney et al. (S&P’ 20) point out some potential vulnerabilities in both NIST specification and common implementations of CTR-DRBG. While these researchers do suggest counter-measures, the security of the patched CTR-DRBG is still questionable. Our work fills this gap, proving that CTR-DRBG satisfies the robustness notion of Dodis et al. (CCS’13), the standard security goal for PRNGs.

We improve the attack of Durak and Vaudenay (CRYPTO’17) on NIST Format-Preserving Encryption standard FF3, reducing the running time from $$O(N^5)$$O(N5) to $$O(N^{17/6})$$O(N17/6) for domain $$\mathbb {Z}_N \times \mathbb {Z}_N$$ZN×ZN. Concretely, DV’s attack needs about $$2^{50}$$250 operations to recover encrypted 6-digit PINs, whereas ours only spends about $$2^{30}$$230 operations. In realizing this goal, we provide a pedagogical example of how to use distinguishing attacks to speed up slide attacks. In addition, we improve the running time of DV’s known-plaintext attack on 4-round Feistel of domain $$\mathbb {Z}_N \times \mathbb {Z}_N$$ZN×ZN from $$O(N^3)$$O(N3) time to just $$O(N^{5/3})$$O(N5/3) time. We also generalize our attacks to a general domain $$\mathbb {Z}_M \times \mathbb {Z}_N$$ZM×ZN, allowing one to recover encrypted SSNs using about $$2^{50}$$250 operations. Finally, we provide some proof-of-concept implementations to empirically validate our results.

Format-preserving encryption (FPE) produces ciphertexts which have the same format as the plaintexts. Building secure FPE is very challenging, and recent attacks (Bellare, Hoang, Tessaro, CCS ’16; Durak and Vaudenay, CRYPTO ’17) have highlighted security deficiencies in the recent NIST SP800-38G standard. This has left the question open of whether practical schemes with high security exist.In this paper, we continue the investigation of attacks against FPE schemes. Our first contribution are new known-plaintext message recovery attacks against Feistel-based FPEs (such as FF1/FF3 from the NIST SP800-38G standard) which improve upon previous work in terms of amortized complexity in multi-target scenarios, where multiple ciphertexts are to be decrypted. Our attacks are also qualitatively better in that they make no assumptions on the correlation between the targets to be decrypted and the known plaintexts. We also surface a new vulnerability specific to FF3 and how it handles odd length domains, which leads to a substantial speedup in our attacks.We also show the first attacks against non-Feistel based FPEs. Specifically, we show a strong message-recovery attack for FNR, a construction proposed by Cisco which replaces two rounds in the Feistel construction with a pairwise-independent permutation, following the paradigm by Naor and Reingold (JoC, ’99). We also provide a strong ciphertext-only attack against a variant of the DTP construction by Brightwell and Smith, which is deployed by Protegrity within commercial applications. All of our attacks show that existing constructions fall short of achieving desirable security levels. For Feistel and the FNR schemes, our attacks become feasible on small domains, e.g., 8 bits, for suggested round numbers. Our attack against the DTP construction is practical even for large domains. We provide proof-of-concept implementations of our attacks that verify our theoretical findings.