CryptoDB
Christina Boura
Publications
Year
Venue
Title
2024
TOSC
Cryptanalysis of Full-Round BipBip
Abstract
BipBip is a low-latency tweakable block cipher proposed by Belkheyar et al. in 2023. It was designed for pointer encryption inside a new memory safety mechanism called Cryptographic Capability Computing (C3). BipBip encrypts blocks of 24 bits using a 40-bit tweak and a 256-bit master key and is composed of 11 rounds. n this article, we provide a Demirci-Selçuk Meet-in-the-Middle (DS-MITM) attack against the 11-round (full) variant that breaks the security claim of the designers.
2024
EUROCRYPT
A generic algorithm for efficient key recovery in differential attacks – and its associated tool
Abstract
Differential cryptanalysis is an old and powerful attack against block ciphers. While different techniques have been introduced throughout the years to improve the complexity of this attack, the key recovery phase remains a tedious and error-prone procedure. In this work, we propose a new algorithm and its associated tool that permits, given a distinguisher, to output an efficient key guessing strategy. Our tool can be applied to SPN ciphers whose linear layer consists of a bit-permutation and whose key schedule is linear or almost linear. It can be used not only to help cryptanalysts find the best differential attack on a given cipher but also to assist designers in their security analysis. We applied our tool
to four targets: RECTANGLE, PRESENT-80, SPEEDY-7-192 and GIFT-64. We extend the previous best attack on RECTANGLE-128 by one round and the previous best differential attack against PRESENT-80 by 2 rounds. We
improve a previous key recovery step in an attack against SPEEDY and present more efficient key recovery strategies for RECTANGLE-80 and GIFT. Our tool outputs the results in only a second for most targets
2024
ASIACRYPT
Multiple-Tweak Differential Attack Against SCARF
Abstract
In this paper, we present the first third-party cryptanalysis of SCARF, a tweakable low-latency block cipher designed to thwart contention-based cache attacks through cache randomization. We focus on multiple-tweak differential attacks, exploiting biases across multiple tweaks. We establish a theoretical framework explaining biases for any number of rounds and verify this framework experimentally. Then, we use these properties to develop a key recovery attack on 7-round SCARF with a time complexity of 2^76, achieving a 98.9% success rate in recovering the 240-bit secret key. Additionally, we introduce a distinguishing attack on the full 8-round SCARF in a multi-key setting, with a complexity of c x 2^67.55, demonstrating that SCARF does not provide 80-bit security under these conditions. We also explore whether our approach could be extended to the single-key model and discuss the implications of different S-box choices on the attack success.
2023
EUROCRYPT
Better Steady than Speedy: Full break of SPEEDY-7-192
Abstract
Differential attacks are among the most important families of cryptanalysis against symmetric primitives. Since their introduction in 1990, several improvements to the basic technique as well as many dedicated attacks against symmetric primitives have been proposed. Most of the proposed improvements concern the key-recovery part. However, when designing a new primitive, the security analysis regarding differential attacks is often limited to finding the best trails over a limited number of rounds with branch and bound techniques, and a poor heuristic is then applied to deduce the total number of rounds a differential attack could reach. In this work we analyze the security of the SPEEDY family of block ciphers against differential cryptanalysis and show how to optimize many of the steps of the key-recovery procedure for this type of attacks. For this, we implemented a search for finding optimal trails for this cipher and their associated multiple probabilities under some constraints and applied non-trivial techniques to obtain optimal data and key-sieving. This permitted us to fully break SPEEDY-7-192, the 7-round variant of SPEEDY supposed to provide 192-bit security.
Our work demonstrates among others the need to better understand the subtleties of differential cryptanalysis in order to get meaningful estimates on the security offered by a cipher against these attacks.
2023
CRYPTO
Differential Meet-In-The-Middle Cryptanalysis
Abstract
In this paper we introduce the differential meet-in-the-middle framework, a new cryptanalysis technique for symmetric primitives. Our new cryptanalysis method combines techniques from both meet-in-the-middle and differential cryptanalysis. As such, the introduced technique can be seen as a way of extending meet-in-the-middle attacks and their variants but also as a new way to perform the key recovery part in differential attacks. We apply our approach to SKINNY-128-384 in the single key model and to AES-256 in the related-key model. Our attack on SKINNY-128-384 permits to break 25 out of the 56 rounds of this variant and improves by two rounds the previous best known attacks. For AES-256 we attack 12 rounds by considering two related keys, thus outperforming the previous best related-key attack on AES-256 with only two related keys by 2 rounds.
2023
TOSC
Related-Key Differential Analysis of the AES
Abstract
The Advanced Encryption Standard (AES) is considered to be the most important and widely deployed symmetric primitive. While the cipher was designed to be immune against differential and other classical attacks, this immunity does not hold in the related-key setting, and various related-key attacks have appeared over time. This work presents tools and algorithms to search for related-key distinguishers and attacks of differential nature against the AES. First, we propose two entirely different approaches to find optimal truncated differential characteristics and bounds on the minimum number of active S-boxes for all variants of the AES. In the first approach, we propose a simple MILP model that handles better linear inconsistencies with respect to the AES system of equations and that compares particularly well to previous tool-based approaches to solve this problem. The main advantage of this tool is that it can easily be used as the core algorithm to search for any attack on AES exploiting related-key differentials. Then, we design a fast and low-memory algorithm based on dynamic programming that has a very simple to understand complexity analysis and does not depend on any generic solver. This second algorithm provides us useful insight on the related-key differential search problem for AES and shows that the search space is not as big as one would expect. Finally, we build on the top of our MILP model a fully automated tool to search for the best differential MITM attacks against the AES. We apply our tool on AES-256 and find an attack on 13 rounds with only two related keys. This attack can be seen as the best known cryptanalysis against this variant if only 2 related keys are permitted.
2020
TOSC
Efficient MILP Modelings for Sboxes and Linear Layers of SPN ciphers
📺
Abstract
Mixed Integer Linear Programming (MILP) solvers are regularly used
by designers for providing security arguments and by cryptanalysts
for searching for new distinguishers. For both applications, bitwise
models are more refined and permit to analyze properties of
primitives more accurately than word-oriented models. Yet, they are
much heavier than these last ones. In this work, we first propose
many new algorithms for efficiently modeling differential
propagation through Sboxes. We manage notably to represent the
AES Sbox with three times less inequalities than before. Then, we
present two new algorithms inspired from coding theory to model
complex linear layers without dummy variables. This permits us to
represent many diffusion matrices, notably the ones of
Skinny-128 and AES in a much more compact way. To
demonstrate the impact of our new models on the solving time we ran
experiments for both Skinny-128 and AES. Finally, our
new models allowed us to computationally prove that there are no
impossible differentials for 5-round AES and 13-round
Skinny-128 with exactly one input and one output active byte,
even if the details of both the Sbox and the linear layer are taken
into account.
2019
TOSC
A General Proof Framework for Recent AES Distinguishers
📺
Abstract
In this paper, a new framework is developed for proving and adapting the recently proposed multiple-of-8 property and mixture-differential distinguishers. The above properties are formulated as immediate consequences of an equivalence relation on the input pairs, under which the difference at the output of the round function is invariant. This approach provides a further understanding of these newly developed distinguishers. For example, it clearly shows that the branch number of the linear layer does not influence the validity of the property, on the contrary of what was previously believed. We further provide an extension of the mixture-differential distinguishers and multiple-of-8 property to any SPN and to a larger class of subspaces. These adapted properties can then be exhibited in a systematic way for other ciphers than the AES. We illustrate this with the examples of Midori, Klein, LED and Skinny.
2018
TOSC
On the Boomerang Uniformity of Cryptographic Sboxes
📺
Abstract
The boomerang attack is a cryptanalysis technique against block ciphers which combines two differentials for the upper part and the lower part of the cipher. The dependency between these two differentials then highly affects the complexity of the attack and all its variants. Recently, Cid et al. introduced at Eurocrypt’18 a new tool, called the Boomerang Connectivity Table (BCT) that permits to simplify this complexity analysis, by storing and unifying the different switching probabilities of the cipher’s Sbox in one table. In this seminal paper a brief analysis of the properties of these tables is provided and some open questions are raised. It is being asked in particular whether Sboxes with optimal BCTs exist for even dimensions, where optimal means that the maximal value in the BCT equals the lowest known differential uniformity. When the dimension is even and differs from 6, such optimal Sboxes correspond to permutations such that the maximal value in their DDT and in their BCT equals 4 (unless APN permutations for such dimensions exist). We provide in this work a more in-depth analysis of boomerang connectivity tables, by studying more closely differentially 4-uniform Sboxes. We first completely characterize the BCT of all differentially 4-uniform permutations of 4 bits and then study these objects for some cryptographically relevant families of Sboxes, as the inverse function and quadratic permutations. These two families provide us with the first examples of differentially 4-uniform Sboxes optimal against boomerang attacks for an even number of variables, answering the above open question.
2014
ASIACRYPT
Program Committees
- Crypto 2024
- FSE 2022
- Asiacrypt 2022
- Eurocrypt 2021
- FSE 2020
- FSE 2019
- Eurocrypt 2019
- FSE 2018
- FSE 2017
- FSE 2016
Coauthors
- Andrey Bogdanov (1)
- Christina Boura (19)
- Christophe De Cannière (1)
- Anne Canteaut (5)
- Avik Chakraborti (1)
- Daniel Coggia (2)
- Nicolas David (3)
- Patrick Derbez (4)
- Margot Funk (1)
- Rachelle Heim Boissier (2)
- Kai Hu (1)
- Virginie Lallemand (1)
- Gregor Leander (1)
- Gaëtan Leurent (1)
- Muzhou Li (1)
- Bart Mennink (1)
- Kazuhiko Minematsu (1)
- María Naya-Plasencia (5)
- Goutam Paul (1)
- Shahram Rasoolzadeh (1)
- Vincent Rijmen (1)
- Dhiman Saha (2)
- Hadi Soleimany (1)
- Valentin Suder (3)
- Yosuke Todo (1)
- Jinliang Wang (1)
- Meiqin Wang (2)
- Long Wen (1)
- Jingyuan Zhao (1)