International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Orr Dunkelman

Publications

Year
Venue
Title
2021
EUROCRYPT
Three Third Generation Attacks on the Format Preserving Encryption Scheme FF3
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 📺
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 📺
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
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 📺
Orr Dunkelman Senyang Huang
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
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
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
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
JOFC
2018
CRYPTO
Improved Key Recovery Attacks on Reduced-Round AES with Practical Data and Memory Complexities
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
Tomer Ashur Achiya Bar-On Orr Dunkelman
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.
2017
CRYPTO
2016
CRYPTO
2016
JOFC
2016
JOFC
2015
JOFC
2015
JOFC
2015
JOFC
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EUROCRYPT
2015
CRYPTO
2014
EPRINT
2014
JOFC
2014
JOFC
2014
ASIACRYPT
2014
FSE
2013
ASIACRYPT
2013
FSE
2012
EUROCRYPT
2012
CRYPTO
2012
FSE
2012
FSE
2010
EPRINT
A Practical-Time Attack on the A5/3 Cryptosystem Used in Third Generation GSM Telephony
Orr Dunkelman Nathan Keller Adi Shamir
The privacy of most GSM phone conversations is currently protected by the 20+ years old A5/1 and A5/2 stream ciphers, which were repeatedly shown to be cryptographically weak. They will soon be replaced in third generation networks by a new A5/3 block cipher called KASUMI, which is a modified version of the MISTY cryptosystem. In this paper we describe a new type of attack called a sandwich attack, and use it to construct a simple distinguisher for 7 of the 8 rounds of KASUMI with an amazingly high probability of $2^{ -14}$. By using this distinguisher and analyzing the single remaining round, we can derive the complete 128 bit key of the full KASUMI by using only 4 related keys, $2^{26}$ data, $2^{30}$ bytes of memory, and $2^{32}$ time. These complexities are so small that we have actually simulated the attack in less than two hours on a single PC, and experimentally verified its correctness and complexity. Interestingly, neither our technique nor any other published attack can break MISTY in less than the $2^{128}$ complexity of exhaustive search, which indicates that the changes made by the GSM Association in moving from MISTY to KASUMI resulted in a much weaker cryptosystem.
2010
EPRINT
Related-Key Boomerang and Rectangle Attacks
This paper introduces the related-key boomerang and the related-key rectangle attacks. These new attacks can expand the cryptanalytic toolbox, and can be applied to many block ciphers. The main advantage of these new attacks, is the ability to exploit the related-key model twice. Hence, even ciphers which were considered resistant to either boomerang or related-key differential attacks may be broken using the new techniques. In this paper we present a rigorous treatment of the related-key boomerang and the related-key rectangle distinguishers. Following this treatment, we devise optimal distinguishing algorithms using the LLR (Logarithmic Likelihood Ratio) statistics. We then analyze the success probability under reasonable independence assumptions, and verify the computation experimentally by implementing an actual attack on a 6-round variant of KASUMI. The paper ends with a demonstration of the strength of our new proposed techniques with attacks on 10-round AES-192 and the full KASUMI.
2010
EPRINT
The Effects of the Omission of Last Round's MixColumns on AES
Orr Dunkelman Nathan Keller
The Advanced Encryption Standard (AES) is the most widely deployed block cipher. It follows the modern iterated block cipher approach, iterating a simple round function multiple times. The last round of AES slightly differs from the others, as a linear mixing operation (called MixColumns) is omitted from it. Following a statement of the designers, it is widely believed that the omission of the last round MixColumns has no security implications. As a result, the majority of attacks on reduced-round variants of AES assume that the last round of the reduced-round version is free of the MixColumns operation. In this note we refute this belief, showing that the omission of MixColumns does affect the security of (reduced-round) AES. First, we consider a simple example of 1-round AES, where we show that the omission reduces the time complexity of an attack with a single known plaintext from 2^{48} to 2^{16}. Then, we examine several previously known attacks on 7-round AES-192 and show that the omission reduces their time complexities by a factor of 2^{16}.
2010
EPRINT
Improved Single-Key Attacks on 8-round AES
Orr Dunkelman Nathan Keller Adi Shamir
AES is the most widely used block cipher today, and its security is one of the most important issues in cryptanalysis. After 13 years of analysis, related-key attacks were recently found against two of its flavors (AES-192 and AES-256). However, such a strong type of attack is not universally accepted as a valid attack model, and in the more standard single-key attack model at most 8 rounds of these two versions can be currently attacked. In the case of 8-round AES-192, the only known attack (found 10 years ago) is extremely marginal, requiring the evaluation of essentially all the 2^{128} possible plaintext/ciphertext pairs in order to speed up exhaustive key search by a factor of 16. In this paper we introduce three new cryptanalytic techniques, and use them to get the first non-marginal attack on 8-round AES-192 (making its time complexity about a million times faster than exhaustive search, and reducing its data complexity to about 1/32,000 of the full codebook). In addition, our new techniques can reduce the best known time complexities for all the other combinations of 7-round and 8-round AES-192 and AES-256.
2010
ASIACRYPT
2010
CRYPTO
2010
EUROCRYPT
2010
FSE
2009
CHES
2009
EPRINT
On the Security of Iterated Hashing based on Forgery-resistant Compression Functions
In this paper we re-examine the security notions suggested for hash functions, with an emphasis on the delicate notion of second preimage resistance. We start by showing that, in the random oracle model, both Merkle-Damgaard and HAIFA achieve second preimage resistance beyond the birthday bound, and actually up to the level of known generic attacks, hence demonstrating the optimality of HAIFA in this respect. We then try to distill a more elementary requirement out of the compression function to get some insight on the properties it should have to guarantee the second preimage resistance of its iteration. We show that if the (keyed) compression function is a secure FIL-MAC then the Merkle-Damgaard mode of iteration (or HAIFA) still maintains the same level of second preimage resistance. We conclude by showing that this ``new'' assumption (or security notion) implies the recently introduced Preimage-Awareness while ensuring all other classical security notions for hash functions.
2009
FSE
2008
EUROCRYPT
2008
FSE
2008
EPRINT
Treatment of the Initial Value in Time-Memory-Data Tradeoff Attacks on Stream Ciphers
Orr Dunkelman Nathan Keller
Time-Memory Tradeoff (TMTO) attacks on stream ciphers are a serious security threat and the resistance to this class of attacks is an important criterion in the design of a modern stream cipher. TMTO attacks are especially effective against stream ciphers where a variant of the TMTO attack can make use of multiple data to reduce the off-line and the on-line time complexities of the attack (given a fixed amount of memory). In this paper we present a new approach to TMTO attacks against stream ciphers using a publicly known initial value (IV): We suggest not to treat the IV as part of the secret key material (as done in current attacks), but rather to choose in advance some IVs and apply a TMTO attack to streams produced using these IVs. We show that while the obtained tradeoff curve is identical to the curve obtained by the current approach, the new technique allows to mount the TMTO attack in a larger variety of settings. For example, if both the secret key and the IV are of length n, it is possible to mount an attack with data, time, and memory complexities of 2^{4n/5}, while in the current approach, either the time complexity or the memory complexity is not less than 2^n. We conclude that if the IV length of a stream cipher is less than 1.5 times the key length, there exists an attack on the cipher with data, time, and memory complexities less than the complexity of exhaustive key search.
2008
EPRINT
New Impossible Differential Attacks on AES
In this paper we apply impossible differential attacks to reduced round AES. Using various techniques, including the early abort approach and key schedule considerations, we significantly improve previously known attacks due to Bahrak-Aref and Phan. The improvement of these attacks leads to the best known impossible differential attacks on 7-round AES-128 and AES-192, as well as to the best known impossible differential attacks on 8-round AES-256.
2008
ASIACRYPT
2008
ASIACRYPT
2007
FSE
2007
FSE
2007
EPRINT
Differential Cryptanalysis in Stream Ciphers
Eli Biham Orr Dunkelman
In this paper we present a general framework for the application of the ideas of differential cryptanalysis to stream ciphers. We demonstrate that some differences in the key (or the initial state or the plaintext) are likely to cause predicted differences in the key stream or in the internal state. These stream differences can then be used to analyze the internal state of the cipher and retrieve it efficiently. We apply our proposed ideas to stream ciphers of various designs, e.g., regularly clocked LFSRs, irregularly clocked LFSRs such as A5/1, and permutation-based stream ciphers such as RC4.
2007
EPRINT
A Framework for Iterative Hash Functions - HAIFA
Eli Biham Orr Dunkelman
Since the seminal works of Merkle and Damgard on the iteration of compression functions, hash functions were built from compression functions using the Merkle-Damgard construction. Recently, several flaws in this construction were identified, allowing for pre-image attacks and second pre-image attacks on such hash functions even when the underlying compression functions are secure. In this paper we propose the HAsh Iterative FrAmework (HAIFA). Our framework can fix many of the flaws while supporting several additional properties such as defining families of hash functions and supporting variable hash size. HAIFA allows for an online computation of the hash function in one pass with a fixed amount of memory independently of the size of the message. Besides our proposal, the recent attacks initiated research on the way compression functions are to be iterated. We show that most recent proposals such as randomized hashing, the enveloped Merkle-Damgard, and the RMC and ROX modes can be all be instantiated as part of the HAsh Iterative FrAmework (HAIFA).
2006
ASIACRYPT
2006
EPRINT
Linear Cryptanalysis of CTC
Orr Dunkelman Nathan Keller
CTC is a toy cipher designed by Courtois in order to prove the strength of algebraic attacks. In this paper we study the differential and the linear behavior of the 85 S-boxes version, which is attacked using algebraic techniques faster than exhaustive key search. We show that an $n$-round variant of the cipher can be attacked by a linear attack using only $2^{2n+2}$ known plaintexts, with a negligible time complexity. We conclude that CTC is insecure, even for quite a large number of rounds. We note that our observations can be probably used to devise other attacks that exploit the relatively slow diffusion of CTC.
2005
ASIACRYPT
2005
EUROCRYPT
2005
FSE
2003
FSE
2003
FSE
2002
ASIACRYPT
2002
FSE
2002
FSE
2002
EPRINT
New Results on Boomerang and Rectangle Attack
Eli Biham Orr Dunkelman Nathan Keller
The boomerang attack is a new and very powerful cryptanalytic technique. However, due to the adaptive chosen plaintext and ciphertext nature of the attack, boomerang key recovery attacks that retrieve key material on both sides of the boomerang distinguisher are hard to mount. We also present a method for using a boomerang distinguisher, which enables retrieving subkey bits on both sides of the boomerang distinguisher. The rectangle attack evolved from the boomerang attack.In this paper we present a new algorithm which improves the results of the rectangle attack. Using these improvements we can attack 3.5-round SC2000 with $2^{67}$ adaptive chosen plaintexts and ciphertexts, and 10-round Serpent with time complexity of $2^{173.8}$ memory accesses (which are equivalent to $2^{165.3}$ Serpent encryptions) with data complexity of $2^{126.3}$ chosen plaintexts.
2001
EUROCRYPT
2001
FSE
2001
EPRINT
The Rectangle Attack - Rectangling the Serpent
Biham Eli Orr Dunkelman Nathan Keller
Serpent is one of the 5 AES finalists. The best attack published so far analyzes up to 9 rounds. In this paper we present attacks on 7-round, 8-round, and 10-round variants of Serpent. We attack 7-round variant of Serpent with all key lengths, and 8- and 10-round variants wih 256-bit keys. The 10-roun attack on the 256-bit keys variants is the best published attack on the cipher. The attack enhances the amplified boomerang attack and uses better differentials. We also present the best 3-round, 4-round, 5-round and 6-round differential characteristics of Serpent.

Program Committees

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