International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Adi Shamir

Publications

Year
Venue
Title
2024
EUROCRYPT
Polynomial Time Cryptanalytic Extraction of Neural Network Models
Billions of dollars and countless GPU hours are currently spent on training Deep Neural Networks (DNNs) for a variety of tasks. Thus, it is essential to determine the difficulty of extracting all the parameters of such neural networks when given access to their black-box implementations. Many versions of this problem have been studied over the last 30 years, and the best current attack on ReLU-based deep neural networks was presented at Crypto'20 by Carlini, Jagielski, and Mironov. It resembles a differential chosen plaintext attack on a cryptosystem, which has a secret key embedded in its black-box implementation and requires a polynomial number of queries but an exponential amount of time (as a function of the number of neurons). In this paper, we improve this attack by developing several new techniques that enable us to extract with arbitrarily high precision all the real-valued parameters of a ReLU-based DNN using a polynomial number of queries \emph{and} a polynomial amount of time. We demonstrate its practical efficiency by applying it to a full-sized neural network for classifying the CIFAR10 dataset, which has 3072 inputs, 8 hidden layers with 256 neurons each, and about $1.2$ million neuronal parameters. An attack following the approach by Carlini et al.\ requires an exhaustive search over $2^{256}$ possibilities. Our attack replaces this with our new techniques, which require only 30 minutes on a 256-core computer.
2023
EUROCRYPT
Efficient Detection of High Probability Statistical Properties of Cryptosystems via Surrogate Differentiation
A central problem in cryptanalysis is to find all the significant deviations from randomness in a given $n$-bit cryptographic primitive. When $n$ is small (e.g., an $8$-bit S-box), this is easy to do, but for large $n$, the only practical way to find such statistical properties was to exploit the internal structure of the primitive and to speed up the search with a variety of heuristic rules of thumb. However, such bottom-up techniques can miss many properties, especially in cryptosystems which are designed to have hidden trapdoors. In this paper we consider the top-down version of the problem in which the cryptographic primitive is given as a structureless black box, and reduce the complexity of the best known techniques for finding all its significant differential and linear properties by a large factor of $2^{n/2}$. Our main new tool is the idea of using {\it surrogate differentiation}. In the context of finding differential properties, it enables us to simultaneously find information about all the differentials of the form $f(x) \oplus f(x \oplus \alpha)$ in all possible directions $\alpha$ by differentiating $f$ in a single arbitrarily chosen direction $\gamma$ (which is unrelated to the $\alpha$'s). In the context of finding linear properties, surrogate differentiation can be combined in a highly effective way with the Fast Fourier Transform. For $64$-bit cryptographic primitives, this technique makes it possible to automatically find in about $2^{64}$ time all their differentials with probability $p \geq 2^{-32}$ and all their linear approximations with bias $|p| \geq 2^{-16}$; previous algorithms for these problems required at least $2^{96}$ time. Similar techniques can be used to significantly improve the best known time complexities of finding related key differentials, second-order differentials, and boomerangs. In addition, we show how to run variants of these algorithms which require no memory, and how to detect such statistical properties even in trapdoored cryptosystems whose designers specifically try to evade our techniques.
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
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 .
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
JOFC
2016
CRYPTO
2016
JOFC
2016
JOFC
2016
JOFC
2015
JOFC
2015
JOFC
2015
JOFC
2015
CRYPTO
2014
CRYPTO
2014
CRYPTO
2014
JOFC
2014
JOFC
2014
ASIACRYPT
2014
FSE
2014
EUROCRYPT
2014
PKC
Post-Snowden Cryptography
Adi Shamir
2013
ASIACRYPT
2013
FSE
2012
EUROCRYPT
2012
CRYPTO
2012
FSE
2012
FSE
2011
FSE
2011
FSE
2011
ASIACRYPT
2010
JOFC
2010
JOFC
2010
ASIACRYPT
2010
CRYPTO
2010
CHES
2010
EUROCRYPT
2009
EUROCRYPT
2009
FSE
2008
EUROCRYPT
2008
FSE
2008
CHES
RSA-Past, Present, Future
Adi Shamir
2008
CHES
2008
CRYPTO
2008
CRYPTO
2007
CRYPTO
2007
PKC
2006
CRYPTO
2006
FSE
2006
ASIACRYPT
2005
CHES
2005
FSE
2005
FSE
2005
JOFC
2004
ASIACRYPT
2004
CHES
2004
FSE
2003
ASIACRYPT
2003
CRYPTO
2003
ASIACRYPT
2003
CHES
RSA Security Analysis
Adi Shamir
2002
ASIACRYPT
2002
ASIACRYPT
2002
CHES
2002
CRYPTO
2001
ASIACRYPT
2001
CHES
2001
CRYPTO
2001
EUROCRYPT
2001
FSE
2000
ASIACRYPT
2000
CHES
2000
EUROCRYPT
2000
EUROCRYPT
2000
FSE
1999
CHES
1999
CRYPTO
1999
EUROCRYPT
1999
FSE
1999
PKC
1998
CRYPTO
1998
EUROCRYPT
1997
CRYPTO
1997
EUROCRYPT
1994
EUROCRYPT
1994
EUROCRYPT
1993
CRYPTO
1993
JOFC
1992
CRYPTO
1991
CRYPTO
1991
CRYPTO
1991
EUROCRYPT
1991
JOFC
1990
CRYPTO
1990
CRYPTO
1989
CRYPTO
1989
CRYPTO
1988
CRYPTO
1988
CRYPTO
1988
JOFC
1987
CRYPTO
1986
CRYPTO
1985
CRYPTO
1985
CRYPTO
1985
EUROCRYPT
1984
CRYPTO
1984
CRYPTO
1982
CRYPTO
1981
CRYPTO

Coauthors

Ohad Amon (1)
Elena Andreeva (2)
Takafumi Aoki (1)
Jean-Philippe Aumasson (1)
Achiya Bar-On (2)
Elad Barkan (1)
Eli Biham (13)
Alex Biryukov (9)
Charles Bouillaguet (3)
Isaac Canales-Martínez (1)
Yaniv Carmeli (2)
Jorge Chavez-Saab (1)
Hsieh-Chung Chen (1)
Chen-Mou Cheng (1)
Tung Chou (1)
Don Coppersmith (1)
Nicolas Courtois (1)
Itai Dinur (18)
Yevgeniy Dodis (1)
Bruce Dodson (1)
Vivien Dubois (1)
Orr Dunkelman (27)
Shimon Even (1)
Uriel Feige (3)
Amos Fiat (2)
Pierre-Alain Fouque (3)
Willi Geiselmann (1)
Daniel Genkin (2)
Oded Goldreich (1)
Tim Güneysu (1)
Dani Halevy (1)
Anna Hambitzer (1)
Jonathan J. Hoch (4)
Naofumi Homma (1)
James Hughes (1)
Yael Tauman Kalai (2)
Nathan Keller (22)
John Kelsey (2)
Dmitry Khovratovich (1)
Aviad Kipnis (2)
Alexander Klimov (5)
Wil Kortsmit (1)
Dror Lapidot (2)
Noam Lasry (1)
Arjen K. Lenstra (3)
Paul C. Leyland (1)
Itsik Mantin (1)
Yossi Matias (1)
Willi Meier (1)
Silvio Micali (1)
Anton Mityagin (1)
Atsushi Miyamoto (1)
David Naccache (1)
Moni Naor (1)
Ruben Niederhagen (1)
H. Ong (1)
Dag Arne Osvik (1)
Christof Paar (1)
Jacques Patarin (1)
Ronald L. Rivest (2)
Francisco Rodriguez (1)
Eyal Ronen (5)
Dima Ruinskiy (1)
Akashi Satoh (1)
Nitin Satpute (1)
Claus-Peter Schnorr (1)
A. W. Schrift (1)
Rainer Steinwandt (1)
Noah Stephens-Davidowitz (1)
Julien P. Stern (1)
Jacques Stern (1)
Moshe Tennenholtz (1)
Jim Tomlinson (1)
Eran Tromer (7)
Boaz Tsaban (1)
David Wagner (1)
Daniel Wichs (1)
Bo-Yin Yang (1)
Sébastien Zimmer (2)
Ralf Zimmermann (1)