International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Virginie Lallemand

Publications

Year
Venue
Title
2024
TOSC
On Impossible Boomerang Attacks: Application to Simon and SKINNYee
The impossible boomerang attack, introduced in 2008 by Jiqiang Lu, is an extension of the impossible differential attack that relies on a boomerang distinguisher of probability 0 for discarding incorrect key guesses. In Lu’s work, the considered impossible boomerang distinguishers were built from 4 (different) probability-1 differentials that lead to 4 differences that do not sum to 0 in the middle, in a miss-in-the-middle way.In this article, we study the possibility of extending this notion by looking at finerlevel contradictions that derive from boomerang switch constraints. We start by discussing the case of quadratic Feistel ciphers and in particular of the Simon ciphers. We exploit their very specific boomerang constraints to enforce a contradiction that creates a new type of impossible boomerang distinguisher that we search with an SMT solver. We next switch to word-oriented ciphers and study how to leverage the Boomerang Connectivity Table contradictions. We apply this idea to SKINNYee, a recent tweakable block cipher proposed at Crypto 2022 and obtain a 21-round distinguisher.After detailing the process and the complexities of an impossible boomerang attack in the single (twea)key and related (twea)key model, we extend our distinguishers into attacks and present a 23-round impossible boomerang attack on Simon-32/64 (out of 32 rounds) and a 29-round impossible boomerang attack on SKINNYee (out of 56 rounds). To the best of our knowledge our analysis covers two more rounds than the (so far, only) other third-party analysis of SKINNYee that has been published to date.
2023
TOSC
On Boomerang Attacks on Quadratic Feistel Ciphers: New results on KATAN and Simon
Xavier Bonnetain Virginie Lallemand
The recent introduction of the Boomerang Connectivity Table (BCT) at Eurocrypt 2018 revived interest in boomerang cryptanalysis and in the need to correctly build boomerang distinguishers. Several important advances have been made on this matter, with in particular the study of the extension of the BCT theory to multiple rounds and to different types of ciphers.In this paper, we pursue these investigations by studying the specific case of quadratic Feistel ciphers, motivated by the need to look at two particularly lightweight ciphers, KATAN and Simon. Our analysis shows that their light round function leads to an extreme case, as a one-round boomerang can only have a probability of 0 or 1. We identify six papers presenting boomerang analyses of KATAN or Simon and all use the naive approach to compute the distinguisher’s probability. We are able to prove that several results are theoretically incorrect and we run experiments to check the probability of the others. Many do not have the claimed probability: it fails distinguishing in some cases, but we also identify instances where the experimental probability turns out to be better than the claimed one.To address this shortfall, we propose an SMT model taking into account the boomerang constraints. We present several experimentally-verified related-key distinguishers obtained with our new technique: on KATAN32 a 151-round boomerang and on Simon-32/64 a 17-round boomerang, a 19-round rotational-xor boomerang and a 15-round rotational-xor-differential boomerang.Furthermore, we extend our 19-round distinguisher into a 25-round rotational-xor rectangle attack on Simon-32/64. To the best of our knowledge this attack reaches one more round than previously published results.
2022
TOSC
Automatic Search of Rectangle Attacks on Feistel Ciphers: Application to WARP
Virginie Lallemand Marine Minier Loïc Rouquette
In this paper we present a boomerang analysis of WARP, a recently proposed Generalized Feistel Network with extremely compact hardware implementations. We start by looking for boomerang characteristics that directly take into account the boomerang switch effects by showing how to adapt Delaune et al. automated tool to the case of Feistel ciphers, and discuss several improvements to keep the execution time reasonable. This technique returns a 23-round distinguisher of probability 2−124, which becomes the best distinguisher presented on WARP so far. We then look for an attack by adding the key recovery phase to our model and we obtain a 26-round rectangle attack with time and data complexities of 2115.9 and 2120.6 respectively, again resulting in the best result presented so far. Incidentally, our analysis discloses how an attacker can take advantage of the position of the key addition (put after the S-box application to avoid complementation properties), which in our case offers an improvement of a factor of 275 of the time complexity in comparison to a variant with the key addition positioned before. Note that our findings do not threaten the security of the cipher which iterates 41 rounds.
2021
TOSC
MOE: Multiplication Operated Encryption with Trojan Resilience 📺
In order to lower costs, the fabrication of Integrated Circuits (ICs) is increasingly delegated to offshore contract foundries, making them exposed to malicious modifications, known as hardware Trojans. Recent works have demonstrated that a strong form of Trojan-resilience can be obtained from untrusted chips by exploiting secret sharing and Multi-Party Computation (MPC), yet with significant cost overheads. In this paper, we study the possibility of building a symmetric cipher enabling similar guarantees in a more efficient manner. To reach this goal, we exploit a simple round structure mixing a modular multiplication and a multiplication with a binary matrix. Besides being motivated as a new block cipher design for Trojan resilience, our research also exposes the cryptographic properties of the modular multiplication, which is of independent interest.
2021
TOSC
CTET+: A Beyond-Birthday-Bound Secure Tweakable Enciphering Scheme Using a Single Pseudorandom Permutation 📺
In this work, we propose a construction of 2-round tweakable substitutionpermutation networks using a single secret S-box. This construction is based on non-linear permutation layers using independent round keys, and achieves security beyond the birthday bound in the random permutation model. When instantiated with an n-bit block cipher with ωn-bit keys, the resulting tweakable block cipher, dubbed CTET+, can be viewed as a tweakable enciphering scheme that encrypts ωκ-bit messages for any integer ω ≥ 2 using 5n + κ-bit keys and n-bit tweaks, providing 2n/3-bit security.Compared to the 2-round non-linear SPN analyzed in [CDK+18], we both minimize it by requiring a single permutation, and weaken the requirements on the middle linear layer, allowing better performance. As a result, CTET+ becomes the first tweakable enciphering scheme that provides beyond-birthday-bound security using a single permutation, while its efficiency is still comparable to existing schemes including AES-XTS, EME, XCB and TET. Furthermore, we propose a new tweakable enciphering scheme, dubbed AES6-CTET+, which is an actual instantiation of CTET+ using a reduced round AES block cipher as the underlying secret S-box. Extensivecryptanalysis of this algorithm allows us to claim 127 bits of security.Such tweakable enciphering schemes with huge block sizes become desirable in the context of disk encryption, since processing a whole sector as a single block significantly worsens the granularity for attackers when compared to, for example, AES-XTS, which treats every 16-byte block on the disk independently. Besides, as a huge amount of data is being stored and encrypted at rest under many different keys in clouds, beyond-birthday-bound security will most likely become necessary in the short term.
2020
TOSC
On the Feistel Counterpart of the Boomerang Connectivity Table: Introduction and Analysis of the FBCT 📺
At Eurocrypt 2018, Cid et al. introduced the Boomerang Connectivity Table (BCT), a tool to compute the probability of the middle round of a boomerang distinguisher from the description of the cipher’s Sbox(es). Their new table and the following works led to a refined understanding of boomerangs, and resulted in a series of improved attacks. Still, these works only addressed the case of Substitution Permutation Networks, and completely left out the case of ciphers following a Feistel construction. In this article, we address this lack by introducing the FBCT, the Feistel counterpart of the BCT. We show that the coefficient at row Δi, ∇o corresponds to the number of times the second order derivative at points Δi, ∇o) cancels out. We explore the properties of the FBCT and compare it to what is known on the BCT. Taking matters further, we show how to compute the probability of a boomerang switch over multiple rounds with a generic formula.
2020
CRYPTO
Cryptanalysis Results on Spook: Bringing Full-round Shadow-512 to the Light 📺
Spook is one of the 32 candidates that has made it to the second round of the NIST Lightweight Cryptography Standardization process, and is particularly interesting since it proposes differential side channel resistance. In this paper, we present practical distinguishers of the full 6-step version of the underlying permutations of Spook, namely Shadow-512 and Shadow-384, solving challenges proposed by the designers on the permutation. We also propose practical forgeries with 4-step Shadow for the S1P mode of operation in the nonce misuse scenario, which is allowed by the CIML2 security game considered by the authors. All the results presented in this paper have been implemented.
2019
EUROCRYPT
bison Instantiating the Whitened Swap-Or-Not Construction 📺
We give the first practical instance – bison – of the Whitened Swap-Or-Not construction. After clarifying inherent limitations of the construction, we point out that this way of building block ciphers allows easy and very strong arguments against differential attacks.
2019
ASIACRYPT
Forkcipher: A New Primitive for Authenticated Encryption of Very Short Messages
Highly efficient encryption and authentication of short messages is an essential requirement for enabling security in constrained scenarios such as the CAN FD in automotive systems (max. message size 64 bytes), massive IoT, critical communication domains of 5G, and Narrowband IoT, to mention a few. In addition, one of the NIST lightweight cryptography project requirements is that AEAD schemes shall be “optimized to be efficient for short messages (e.g., as short as 8 bytes)”.In this work we introduce and formalize a novel primitive in symmetric cryptography called forkcipher. A forkcipher is a keyed primitive expanding a fixed-lenght input to a fixed-length output. We define its security as indistinguishability under a chosen ciphertext attack (for n-bit inputs to 2n-bit outputs). We give a generic construction validation via the new iterate-fork-iterate design paradigm.We then propose $$ {\mathsf {ForkSkinny}} $$ as a concrete forkcipher instance with a public tweak and based on SKINNY: a tweakable lightweight cipher following the TWEAKEY framework. We conduct extensive cryptanalysis of $$ {\mathsf {ForkSkinny}} $$ against classical and structure-specific attacks.We demonstrate the applicability of forkciphers by designing three new provably-secure nonce-based AEAD modes which offer performance and security tradeoffs and are optimized for efficiency of very short messages. Considering a reference block size of 16 bytes, and ignoring possible hardware optimizations, our new AEAD schemes beat the best SKINNY-based AEAD modes. More generally, we show forkciphers are suited for lightweight applications dealing with predominantly short messages, while at the same time allowing handling arbitrary messages sizes.Furthermore, our hardware implementation results show that when we exploit the inherent parallelism of $$ {\mathsf {ForkSkinny}} $$ we achieve the best performance when directly compared with the most efficient mode instantiated with SKINNY.
2018
JOFC
2018
CRYPTO
Rasta: A Cipher with Low ANDdepth and Few ANDs per Bit 📺
Recent developments in multi party computation (MPC) and fully homomorphic encryption (FHE) promoted the design and analysis of symmetric cryptographic schemes that minimize multiplications in one way or another. In this paper, we propose with Rastaa design strategy for symmetric encryption that has ANDdepth d and at the same time only needs d ANDs per encrypted bit. Even for very low values of d between 2 and 6 we can give strong evidence that attacks may not exist. This contributes to a better understanding of the limits of what concrete symmetric-key constructions can theoretically achieve with respect to AND-related metrics, and is to the best of our knowledge the first attempt that minimizes both metrics simultaneously. Furthermore, we can give evidence that for choices of d between 4 and 6 the resulting implementation properties may well be competitive by testing our construction in the use-case of removing the large ciphertext-expansion when using the BGV scheme.
2016
CRYPTO
2015
EUROCRYPT
2015
CRYPTO
2014
FSE

Program Committees

FSE 2022
FSE 2020
FSE 2019
Asiacrypt 2019
FSE 2018
Asiacrypt 2018