## CryptoDB

### Orr Dunkelman

#### Publications

**Year**

**Venue**

**Title**

2022

TOSC

Finding Collisions against 4-Round SHA-3-384 in Practical Time
Abstract

The Keccak sponge function family, designed by Bertoni et al. in 2007, was selected by the U.S. National Institute of Standards and Technology (NIST) in 2012 as the next generation of Secure Hash Algorithm (SHA-3). Due to its theoretical and practical importance, cryptanalysis of SHA-3 has attracted a lot of attention. Currently, the most powerful collision attack on SHA-3 is Jian Guo et al.’s linearisation technique. However, this technique is infeasible for variants with asmaller input space, such as SHA-3-384.In this work we improve upon previous results by utilising three ideas which were not used in previous works on collision attacks against SHA-3. First, we use 2-block messages instead of 1-block messages, to reduce constraints and increase flexibility in our solutions. Second, we reduce the connectivity problem into a satisfiability (SAT) problem, instead of applying the linearisation technique. Finally, we propose an efficient deduce-and-sieve algorithm on the basis of two new non-random propertiesof the Keccak non-linear layer.The resulting collision-finding algorithm on 4-round SHA-3-384 has a practical time complexity of 259.64 (and a memory complexity of 245.94). This greatly improves upon the best known collision attack so far: Dinur et al. achieved an impractical 2147 time complexity. Our attack does not threaten the security margin of the SHA-3 hash function. However, the tools developed in this paper could be used to analyse other cryptographic primitives as well as to develop new and faster SAT solvers.

2021

EUROCRYPT

Three Third Generation Attacks on the Format Preserving Encryption Scheme FF3
📺
Abstract

Format-Preserving Encryption (FPE) schemes accept plaintexts from any finite set of values (such as social security numbers or birth dates) and produce ciphertexts that belong to the same set. They are extremely useful in practice since they make it possible to encrypt existing databases or communication packets without changing their format. Due to industry demand, NIST had standardized in 2016 two such encryption schemes called FF1 and FF3. They immediately attracted considerable cryptanalytic attention with decreasing attack complexities. The best currently known attack on the Feistel construction FF3 has data and memory complexity of ${O}(N^{11/6})$ and time complexity of ${O}(N^{17/6})$, where the input belongs to a domain of size $N \times N$.
In this paper, we present and experimentally verify three improved attacks on FF3. Our best attack achieves the tradeoff curve $D=M=\tilde{O}(N^{2-t})$, $T=\tilde{O}(N^{2+t})$ for all $t \leq 0.5$.
In particular, we can reduce the data and memory complexities to the more practical $\tilde{O}(N^{1.5})$, and at the same time, reduce the time complexity to $\tilde{O}(N^{2.5})$.
We also identify another attack vector against FPE schemes, the {\em related-domain} attack. We show how one can mount powerful attacks when the adversary is given access to the encryption under the same key in different domains, and show how to apply it to efficiently distinguish FF3 and FF3-1 instances.

2020

EUROCRYPT

The Retracing Boomerang Attack
📺
Abstract

Boomerang attacks are extensions of differential attacks, that make it
possible to combine
two unrelated differential properties of the first and second part of a
cryptosystem with probabilities $p$ and $q$ into a new differential-like
property
of the whole cryptosystem with probability $p^2q^2$ (since each one of the
properties has to be satisfied twice). In this paper we describe a new
version of
boomerang attacks which uses the counterintuitive idea of throwing out most
of the data in order to force equalities between certain values
on the ciphertext side. In certain cases,
this creates a correlation between the four probabilistic events,
which increases the probability of the combined property to $p^2q$
and increases the signal to noise ratio of the resultant distinguisher.
We call this variant a {\it retracing boomerang attack} since we make
sure that the boomerang we throw follows the same path
on its forward and backward directions.
To demonstrate the power of the new
technique, we apply it to the case of 5-round AES. This version of AES was
repeatedly
attacked by a large variety of techniques, but for twenty years its
complexity had remained
stuck at $2^{32}$. At Crypto'18 it was finally reduced to $2^{24}$ (for full key recovery), and with
our
new technique we can further reduce the complexity of full key recovery to
the surprisingly low value of $2^{16.5}$
(i.e., only $90,000$ encryption/decryption operations are required for a full
key recovery on half the rounds of AES).
In addition to improving previous
attacks, our new technique unveils a hidden relationship between
boomerang attacks and two other cryptanalytic techniques, the yoyo game and
the recently introduced mixture differentials.

2020

EUROCRYPT

New Slide Attacks on Almost Self-Similar Ciphers
📺
Abstract

The slide attack is a powerful cryptanalytic tool which has the unusual property that it can break iterated block ciphers with a complexity that does not depend on their number of rounds. However, it requires complete self similarity in the sense that all the rounds must be identical. While this can be the case in Feistel structures, this rarely happens in SP networks since the last round must end with an additional post-whitening subkey. In addition, in many SP networks the final round has additional asymmetries - for example, in AES the last round omits the MixColumns operation. Such asymmetry in the last round can make it difficult to utilize most of the advanced tools which were developed for slide attacks, such as deriving from one slid pair additional slid pairs by repeatedly
re-encrypting their ciphertexts. Consequently, almost all the successful applications of slide attacks against real cryptosystems (e.g., FF3, GOST,
SHACAL-1, etc.) had targeted Feistel structures rather than SP networks.
In this paper we overcome this last round problem by developing four new types of slide attacks. We demonstrate their power by applying them to many types of AES-like structures (with and without linear mixing in the last round, with known or secret S-boxes, with periodicity of 1,2 and 3 in their subkeys, etc).
In most of these cases, the time complexity of our attack is close to $2^{n/2}$, the smallest possible complexity for most slide attacks. Our new slide attacks have several unique properties: The first uses slid sets in which each plaintext from the first set forms a slid pair with some plaintext from the second set, but without knowing the exact correspondence. The second makes it possible to create from several slid pairs an exponential number of new slid pairs which form a hypercube spanned by the given pairs. The third has the unusual property that it is always successful, and the fourth can use known messages instead of chosen messages, with only slightly higher time complexity.

2019

EUROCRYPT

DLCT: A New Tool for Differential-Linear Cryptanalysis
Abstract

Differential cryptanalysis and linear cryptanalysis are the two best-known techniques for cryptanalysis of block ciphers. In 1994, Langford and Hellman introduced the differential-linear (DL) attack based on dividing the attacked cipher E into two subciphers $$E_0$$E0 and $$E_1$$E1 and combining a differential characteristic for $$E_0$$E0 with a linear approximation for $$E_1$$E1 into an attack on the entire cipher E. The DL technique was used to mount the best known attacks against numerous ciphers, including the AES finalist Serpent, ICEPOLE, COCONUT98, Chaskey, CTC2, and 8-round DES.Several papers aimed at formalizing the DL attack, and formulating assumptions under which its complexity can be estimated accurately. These culminated in a recent work of Blondeau, Leander, and Nyberg (Journal of Cryptology, 2017) which obtained an accurate expression under the sole assumption that the two subciphers $$E_0$$E0 and $$E_1$$E1 are independent.In this paper we show that in many cases, dependency between the two subcipher s significantly affects the complexity of the DL attack, and in particular, can be exploited by the adversary to make the attack more efficient. We present the Differential-Linear Connectivity Table (DLCT) which allows us to take into account the dependency between the two subciphers, and to choose the differential characteristic in $$E_0$$E0 and the linear approximation in $$E_1$$E1 in a way that takes advantage of this dependency. We then show that the DLCT can be constructed efficiently using the Fast Fourier Transform. Finally, we demonstrate the strength of the DLCT by using it to improve differential-linear attacks on ICEPOLE and on 8-round DES, and to explain published experimental results on Serpent and on the CAESAR finalist Ascon which did not comply with the standard differential-linear framework.

2019

TOSC

Reconstructing an S-box from its Difference Distribution Table
📺
Abstract

In this paper we study the problem of recovering a secret S-box from its difference distribution table (DDT). While being an interesting theoretical problem on its own, the ability to recover the S-box from the DDT of a secret S-box can be used in cryptanalytic attacks where the attacker can obtain the DDT (e.g., in Bar-On et al.’s attack on GOST), in supporting theoretical analysis of the properties of difference distribution tables (e.g., in Boura et al.’s work), or in some analysis of S-boxes with unknown design criteria (e.g., in Biryukov and Perrin’s analysis).We show that using the well established relation between the DDT and the linear approximation table (LAT), one can devise an algorithm different from the straightforward guess-and-determine (GD) algorithm proposed by Boura et al. Moreover, we show how to exploit this relation, and embed the knowledge obtained from it in the GD algorithm. We tested our new algorithm on random S-boxes of different sizes, and for random 14-bit bijective S-boxes, our results outperform the GD attack by several orders of magnitude.

2019

JOFC

Efficient Dissection of Bicomposite Problems with Cryptanalytic Applications
Abstract

In this paper, we show that a large class of diverse problems have a bicomposite structure which makes it possible to solve them with a new type of algorithm called dissection , which has much better time/memory tradeoffs than previously known algorithms. A typical example is the problem of finding the key of multiple encryption schemes with r independent n -bit keys. All the previous error-free attacks required time T and memory M satisfying $$\textit{TM} = 2^{rn}$$ TM = 2 rn , and even if “false negatives” are allowed, no attack could achieve $$\textit{TM}<2^{3rn/4}$$ TM < 2 3 r n / 4 . Our new technique yields the first algorithm which never errs and finds all the possible keys with a smaller product of $$\textit{TM}$$ TM , such as $$T=2^{4n}$$ T = 2 4 n time and $$M=2^{n}$$ M = 2 n memory for breaking the sequential execution of $$\hbox {r}=7$$ r = 7 block ciphers. The improvement ratio we obtain increases in an unbounded way as r increases, and if we allow algorithms which can sometimes miss solutions, we can get even better tradeoffs by combining our dissection technique with parallel collision search. To demonstrate the generality of the new dissection technique, we show how to use it in a generic way in order to improve rebound attacks on hash functions and to solve with better time complexities (for small memory complexities) hard combinatorial search problems, such as the well-known knapsack problem.

2019

JOFC

Improved Key Recovery Attacks on Reduced-Round AES with Practical Data and Memory Complexities
Abstract

Determining the security of AES is a central problem in cryptanalysis, but progress in this area had been slow and only a handful of cryptanalytic techniques led to significant advancements. At Eurocrypt 2017 Grassi et al. presented a novel type of distinguisher for AES-like structures, but so far all the published attacks which were based on this distinguisher were inferior to previously known attacks in their complexity. In this paper we combine the technique of Grassi et al. with several other techniques in a novel way to obtain the best known key recovery attack on 5-round AES in the single-key model, reducing its overall complexity from about $$2^{32}$$ 2 32 to less than $$2^{22}$$ 2 22 . Extending our techniques to 7-round AES, we obtain the best known attacks on reduced-round AES-192 which use practical amounts of data and memory, breaking the record for such attacks which was obtained in 2000 by the classical Square attack. In addition, we use our techniques to improve the Gilbert–Minier attack (2000) on 7-round AES, reducing its memory complexity from $$2^{80}$$ 2 80 to $$2^{40}$$ 2 40 .

2019

JOFC

A Practical Forgery Attack on Lilliput-AE
Abstract

Lilliput-AE is a tweakable block cipher submitted as a candidate to the NIST lightweight cryptography standardization process. It is based upon the lightweight block cipher Lilliput, whose cryptanalysis so far suggests that it has a large security margin. In this note, we present an extremely efficient forgery attack on Lilliput-AE: Given a single arbitrary message of length about $$2^{36}$$ 2 36 bytes, we can instantly produce another valid message that leads to the same tag, along with the corresponding ciphertext. The attack uses a weakness in the tweakey schedule of Lilliput-AE which leads to the existence of a related-tweak differential characteristic with probability 1 in the underlying block cipher. The weakness we exploit, which does not exist in Lilliput, demonstrates the potential security risk in using a very simple tweakey schedule in which the same part of the key/tweak is reused in every round, even when round constants are employed to prevent slide attacks. Following this attack, the Lilliput-AE submission to NIST was tweaked.

2018

CRYPTO

Improved Key Recovery Attacks on Reduced-Round AES with Practical Data and Memory Complexities
Abstract

Determining the security of AES is a central problem in cryptanalysis, but progress in this area had been slow and only a handful of cryptanalytic techniques led to significant advancements. At Eurocrypt 2017 Grassi et al. presented a novel type of distinguisher for AES-like structures, but so far all the published attacks which were based on this distinguisher were inferior to previously known attacks in their complexity. In this paper we combine the technique of Grassi et al. with several other techniques to obtain the best known key recovery attack on 5-round AES in the single-key model, reducing its overall complexity from about $$2^{32}$$ to about $$2^{22.5}$$. Extending our techniques to 7-round AES, we obtain the best known attacks on AES-192 which use practical amounts of data and memory, breaking the record for such attacks which was obtained 18 years ago by the classical Square attack.

2017

TOSC

Cryptanalysis of GOST2
Abstract

GOST 28147 is a 256-bit key 64-bit block cipher developed by the USSR, later adopted by the Russian government as a national standard. In 2010, GOST was suggested to be included in ISO/IEC 18033-3, but was rejected due to weaknesses found in its key schedule. In 2015, a new version of GOST was suggested with the purpose of mitigating such attacks. In this paper, we show that similar weaknesses exist in the new version as well. More specifically, we present a fixed-point attack on the full cipher with time complexity of 2237 encryptions. We also present a reflection attack with time complexity of 2192 for a key that is chosen from a class of 2224 weak keys. Finally, we discuss an impossible reflection attack which improves on exhaustive search by a factor of 2e, and several possible related-key attacks.

2014

JOFC

2012

CRYPTO

2010

CRYPTO

2010

EUROCRYPT

#### Program Committees

- FSE 2022
- Eurocrypt 2022 (Program chair)
- Eurocrypt 2021
- FSE 2020
- FSE 2019
- Crypto 2019
- Crypto 2017
- FSE 2016
- CHES 2016
- FSE 2015
- Crypto 2015
- Crypto 2014
- FSE 2014
- FSE 2013
- Asiacrypt 2013
- Asiacrypt 2012
- Eurocrypt 2012
- Eurocrypt 2011
- Crypto 2011
- FSE 2010
- FSE 2009 (Program chair)
- Eurocrypt 2008
- Crypto 2008
- FSE 2008
- FSE 2007
- Crypto 2007
- FSE 2006
- Asiacrypt 2005

#### Coauthors

- Ohad Amon (1)
- Elena Andreeva (1)
- Tomer Ashur (2)
- Achiya Bar-On (6)
- Orna Agmon Ben-Yehuda (1)
- Eli Biham (16)
- Alex Biryukov (1)
- Charles Bouillaguet (2)
- Christophe De Cannière (1)
- Itai Dinur (13)
- Pierre-Alain Fouque (2)
- Jonathan J. Hoch (1)
- Senyang Huang (2)
- Sebastiaan Indesteege (1)
- Nathan Keller (41)
- John Kelsey (1)
- Dmitry Khovratovich (1)
- Miroslav Knezevic (1)
- Virginie Lallemand (1)
- Eran Lambooij (1)
- Noam Lasry (1)
- Gaëtan Leurent (1)
- Atul Luykx (1)
- Alexander Maximov (1)
- Bart Preneel (1)
- Eyal Ronen (4)
- Yu Sasaki (1)
- Adi Shamir (26)
- Takeshi Shimoyama (1)
- Boaz Tsaban (1)
- Ariel Weizman (1)
- Hitoshi Yanami (1)
- Sébastien Zimmer (1)