Publications

The counter mode (CTR) is a simple, efficient and widely used encryption mode using a block cipher. It comes with a security proof that guarantees no attacks up to the birthday bound (i.e. as long as the number of encrypted blocks \(\sigma\) satisfies \(\sigma \ll 2^{n/2}\)), and a matching attack that can distinguish plaintext/ciphertext pairs from random using about \(2^{n/2}\) blocks of data. The main goal of this paper is to study attacks against the counter mode beyond this simple distinguisher. We focus on message recovery attacks, with realistic assumptions about the capabilities of an adversary, and evaluate the full time complexity of the attacks rather than just the query complexity. Our main result is an attack to recover a block of message with complexity \(\tilde{\mathcal{O}}(2^{n/2})\). This shows that the actual security of CTR is similar to that of CBC, where collision attacks are well known to reveal information about the message. To achieve this result, we study a simple algorithmic problem related to the security of the CTR mode: the missing difference problem. We give efficient algorithms for this problem in two practically relevant cases: where the missing difference is known to be in some linear subspace, and when the amount of data is higher than strictly required. As a further application, we show that the second algorithm can also be used to break some polynomial MACs such as GMAC and Poly1305, with a universal forgery attack with complexity \(\tilde{\mathcal{O}}(2^{2n/3})\).

In this work, we study the security of several recent MAC constructions with provable security beyond the birthday bound. We consider block-cipher based constructions with a double-block internal state, such as SUM-ECBC, PMAC+, 3kf9, GCM-SIV2, and some variants (LightMAC+, 1kPMAC+). All these MACs have a security proof up to \(2^{2n/3}\) queries, but there are no known attacks with less than \(2^{n}\) queries. We describe a new cryptanalysis technique for double-block MACs based on finding quadruples of messages with four pairwise collisions in halves of the state. We show how to detect such quadruples in SUM-ECBC, PMAC+, 3kf9, GCM-SIV2 and their variants with \(\mathcal{O}(2^{3n/4})\) queries, and how to build a forgery attack with the same query complexity. The time complexity of these attacks is above \(2^n\), but it shows that the schemes do not reach full security in the information theoretic model. Surprisingly, our attack on LightMAC+ also invalidates a recent security proof by Naito. Moreover, we give a variant of the attack against SUM-ECBC and GCM-SIV2 with time and data complexity \(\tilde{\mathcal{O}}(2^{6n/7})\). As far as we know, this is the first attack with complexity below \(2^n\) against a deterministic beyond-birthday-bound secure MAC. As a side result, we also give a birthday attack against 1kf9, a single-key variant of 3kf9 that was withdrawn due to issues with the proof.

The iterated Even-Mansour construction is an elegant construction that idealizes block cipher designs such as the AES. In this work we focus on the simplest variant, the 2-round Even-Mansour construction with a single key. This is the most minimal construction that offers security beyond the birthday bound: there is a security proof up to \(2^{2n/3}\) evaluations of the underlying permutations and encryption, and the best known attacks have a complexity of roughly \(2^n/n\) operations. We show that attacking this scheme with block size \(n\) is related to the 3-XOR problem with element size \(\ell = 2n\), an important algorithmic problem that has been studied since the nineties. In particular the 3-XOR problem is known to require at least \(2^{\ell/3}\) queries, and the best known algorithms require around \(2^{\ell/2}/\ell\) operations: this roughly matches the known bounds for the 2-round Even-Mansour scheme. Using this link we describe new attacks against the 2-round Even-Mansour scheme. In particular, we obtain the first algorithms where both the data and the memory complexity are significantly lower than \(2^{n}\). From a practical standpoint, previous works with a data and/or memory complexity close to \(2^n\) are unlikely to be more efficient than a simple brute-force search over the key. Our best algorithm requires just \((\lambda n)\) known plaintext/ciphertext pairs, for some constant \(0 < \lambda < 1\), \(2^n/\lambda n\) time, and \(2^{\lambda n}\) memory. For instance, with \(n=64\) and \(\lambda=1/2\), the memory requirement is practical, and we gain a factor \(32\) over brute-force search. We also describe an algorithm with asymptotic complexity \(\mathcal{O}(2^{n} \ln^2 n / n^2)\), improving the previous asymptotic complexity of \(\mathcal{O}(2^n / n)\), using a variant of the 3-SUM algorithm of Baran, Demaine, and Pǎtraşcu.

Authenticated encryption schemes are usually expected to offer confidentiality and authenticity. In case of release of unverified plaintext (RUP), an adversary gets separated access to the decryption and verification functionality, and has more power in breaking the scheme. Andreeva et al. (ASIACRYPT 2014) formalized RUP security using plaintext awareness, informally meaning that the decryption functionality gives no extra power in breaking confidentiality, and INT-RUP security, covering authenticity in case of RUP. We describe a single, unified model, called AERUP security, that ties together these notions: we prove that an authenticated encryption scheme is AERUP secure if and only if it is conventionally secure, plaintext aware, and INT-RUP secure. We next present ANYDAE, a generalization of SUNDAE of Banik et al. (ToSC 2018/3). ANYDAE is a lightweight deterministic scheme that is based on a block cipher with block size \(n\) and arbitrary mixing functions that all operate on an \(n\)-bit state. It is particularly efficient for short messages, it does not rely on a nonce, and it provides maximal robustness to a lack of secure state. Whereas SUNDAE is not secure under release of unverified plaintext (a fairly simple attack can be mounted in constant time), ANYDAE is. We make handy use of the AERUP security model to prove that ANYDAE achieves both conventional security as RUP security, provided that certain modest conditions on the mixing functions are met. We describe two simple instances, called MONDAE and TUESDAE, that conform to these conditions and that are competitive with SUNDAE, in terms of efficiency and optimality.

Tweakable block ciphers are increasingly becoming a common primitive to build new resilient modes as well as a concept for multiple dedicated designs. While regular block ciphers define a family of permutations indexed by a secret key, tweakable ones define a family of permutations indexed by both a secret key and a public tweak. In this work we formalize and study a generic framework for building such a tweakable block cipher based on regular block ciphers, the iterated tweakable FX construction, which includes many such previous constructions of tweakable block ciphers. Then we describe a cryptanalysis from which we can derive a provable security upper-bound for all constructions following this tweakable iterated FX strategy. Concretely, the cryptanalysis of \(r\) rounds of our generic construction based on \(n\)-bit block ciphers with \(κ\)-bit keys requires \(\mathcal{O}(2^{\frac{r}{r+1}(n + κ)})\) online and offline queries. For \(r=2\) rounds this interestingly matches the proof of the particular case of XHX2 by Lee and Lee (ASIACRYPT 2018) thus proving for the first time its tightness. In turn, the XHX and XHX2 proofs show that our generic cryptanalysis is information theoretically optimal for 1 and 2 rounds.

This paper presents the first third-party security analysis of TinyJambu, which is one of 32 second-round candidates in NIST's lightweight cryptography standardization process. TinyJambu adopts an NLFSR based keyed-permutation that computes only a single NAND gate as a non-linear component per round. The designers evaluated the minimum number of active AND gates, however such a counting method neglects the dependency between multiple AND gates. There also exist previous works considering such dependencies with stricter models, however those are known to be too slow. In this paper, we present a new model that provides a good balance of efficiency and accuracy by only taking into account the first-order correlation of AND gates that frequently occurs in TinyJambu. With the refined model, we show a 338-round differential with probability \(2^{-62.68}\) that leads to a forgery attack breaking 64-bit security. This implies that the security margin of TinyJambu with respect to the number of unattacked rounds is approximately 12%. We also show a differential on full 384 rounds with probability \(2^{-70.64}\), thus the security margin of full rounds with respect to the data complexity, namely the gap between the claimed security bits and the attack complexity, is less than 8 bits. Our attacks also point out structural weaknesses of the mode that essentially come from the minimal state size to be lightweight.

Gimli is a family of cryptographic primitives (both a hash function and an AEAD scheme) that has been selected for the second round of the NIST competition for standardizing new lightweight designs. The candidate Gimli is based on the permutation Gimli, which was presented at CHES 2017. In this paper, we study the security of both the permutation and the constructions that are based on it. We exploit the slow diffusion in Gimli and its internal symmetries to build, for the first time, a distinguisher on the full permutation of complexity \(2^{64}\). We also provide a practical distinguisher on 23 out of the full 24 rounds of Gimli that has been implemented. Next, we give (full state) collision and semi-free-start collision attacks on Gimli-Hash, reaching respectively up to 12 and 18 rounds. On the practical side, we compute a collision on 8-round Gimli-Hash. In the quantum setting, these attacks reach 2 more rounds. Finally, we perform the first study of linear trails in the permutation, and we propose differential-linear cryptanalysis that reach up to 17 rounds of Gimli.