## CryptoDB

### Adi Shamir

#### Affiliation: The Weizmann Institute

#### Publications

**Year**

**Venue**

**Title**

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

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 .

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.

2014

CRYPTO

2014

EPRINT

2014

JOFC

2012

CRYPTO

2011

ASIACRYPT

2010

EPRINT

A Practical-Time Attack on the A5/3 Cryptosystem Used in Third Generation GSM Telephony
Abstract

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

Fast Exhaustive Search for Polynomial Systems in $F_2$
Abstract

We analyze how fast we can solve general systems of multivariate
equations of various low degrees over \GF{2}; this is
a well known hard problem which is important both in itself and
as part of many types of algebraic cryptanalysis. Compared to the standard
exhaustive-search technique, our improved approach is more
efficient both asymptotically and practically.
We implemented several optimized versions of our techniques on CPUs and GPUs. Modern graphic cards allows our technique to run more than 10 times faster than the most powerful CPU available. Today, we can solve 48+ quadratic equations in 48 binary variables on a NVIDIA GTX 295 video card (USD 500) in 21 minutes.
With this level of performance, solving systems of equations supposed to ensure a security level of 64 bits turns out to be feasible in practice with a modest budget. This is a clear demonstration of the power of GPUs in solving many types of combinatorial and cryptanalytic problems.

2010

EPRINT

Improved Single-Key Attacks on 8-round AES
Abstract

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

CRYPTO

2010

EUROCRYPT

2009

EPRINT

Un-Trusted-HB: Security Vulnerabilities of Trusted-HB
Abstract

With increased use of passive RFID tags, the need for secure lightweight identification protocols arose. HB+ is one such protocol, which was proven secure in the detection-based model, but shown breakable by man-in-the-middle attacks.
Trusted-HB is a variant of HB+, specifically designed to resist man-in-the-middle attacks. In this paper, we discuss several weaknesses of Trusted-HB, show that the formal security proof provided by its designers is incorrect, and demonstrate how to break it in realistic scenarios.

2008

EPRINT

On the Strength of the Concatenated Hash Combiner when All the Hash Functions are Weak
Abstract

At Crypto 2004 Joux showed a novel attack against the concatenated hash combiner instantiated with \md iterated hash functions. His method of producing multicollisions in the \md design was the first in a recent line of generic attacks against the \md construction. In the same paper, Joux raised an open question concerning the strength of the concatenated hash combiner and asked whether his attack can be improved when the attacker can efficiently find collisions in both underlying compression functions. We solve this open problem by showing that even in the powerful adversarial scenario first introduced by Liskov (SAC 2006) in which the underlying compression functions can be fully inverted (which implies that collisions can be easily generated), collisions in the concatenated hash cannot be created using fewer than $2^{n/2}$ queries. We then expand this result to include the double pipe hash construction of Lucks from Asiacrypt 2005. One of the intermediate results is of interest on its own and provides the first streamable construction provably indifferentiable from a random oracle in this model.

2008

EPRINT

Cube Attacks on Tweakable Black Box Polynomials
Abstract

Almost any cryptographic scheme can be described by
\emph{tweakable polynomials} over $GF(2)$, which contain both
secret variables (e.g., key bits) and public variables (e.g.,
plaintext bits or IV bits). The cryptanalyst is allowed to tweak
the polynomials by choosing arbitrary values for the public
variables, and his goal is to solve the resultant system of
polynomial equations in terms of their common secret variables. In
this paper we develop a new technique (called a \emph{cube
attack}) for solving such tweakable polynomials, which is a major
improvement over several previously published attacks of the same
type. For example, on the stream cipher Trivium with a reduced
number of initialization rounds, the best previous attack (due to
Fischer, Khazaei, and Meier) requires a barely practical
complexity of $2^{55}$ to attack $672$ initialization rounds,
whereas a cube attack can find the complete key of the same
variant in $2^{19}$ bit operations (which take less than a second
on a single PC). Trivium with $735$ initialization rounds (which
could not be attacked by any previous technique) can now be broken
with $2^{30}$ bit operations. Trivium with $767$ initialization
rounds can now be broken with $2^{45}$ bit operations, and the
complexity of the attack can almost certainly be further reduced to about
$2^{36}$ bit operations. Whereas previous attacks were heuristic,
had to be adapted to each cryptosystem, had no general complexity
bounds, and were not expected to succeed on random looking
polynomials, cube attacks are provably successful when applied to
random polynomials of degree $d$ over $n$ secret variables
whenever the number $m$ of public variables exceeds $d+log_dn$.
Their complexity is $2^{d-1}n+n^2$ bit operations, which is
polynomial in $n$ and amazingly low when $d$ is small. Cube
attacks can be applied to any block cipher, stream cipher, or MAC
which is provided as a black box (even when nothing is known about
its internal structure) as long as at least one output bit can be
represented by (an unknown) polynomial of relatively low degree in
the secret and public variables.

2007

EPRINT

Practical Cryptanalysis of SFLASH
Abstract

In this paper, we present a practical attack on the signature scheme
SFLASH proposed by Patarin, Goubin and Courtois in 2001 following a
design they had introduced in 1998.
The attack only needs the public key and requires about one second
to forge a signature for any message, after a one-time computation of
several minutes. It can be applied to both SFLASHv2 which was
accepted by NESSIE, as well as to SFLASHv3 which is a higher
security version.

2007

EPRINT

Second Preimage Attacks on Dithered Hash Functions
Abstract

The goal of this paper is to analyze the security of dithered variants of the Merkle-Damgard mode of operation that use a third input to indicate the position of a block in the message to be hashed. These modes of operation for hash functions have been proposed to avoid some structural weaknesses of the Merkle-Damgard paradigm, e.g. that second preimages can be constructed in much less than $2^n$ work, as pointed out by Kelsey and Schneier. Among the modes of operation that use such a third input are Rivest's dithered hashing and Biham and Dunkelman's HAIFA proposal.
We propose several new second preimage attacks on the Merkle-Damgard mode of operation, which can also attack Rivest's dithered hash with almost the same complexity. When applied to Shoup's UOWHF, these attacks can be shown to be optimal since their complexity matches Shoup's security bound.

2006

EPRINT

Length-based cryptanalysis: The case of Thompson's Group
Abstract

The length-based approach is a heuristic for solving randomly generated equations in groups which possess a reasonably behaved length function. We describe several improvements of the previously suggested length-based algorithms, that make them applicable to Thompson's group with significant success rates. In particular, this shows that the Shpilrain-Ushakov public key cryptosystem based on Thompson's group is insecure, and suggests that no practical public key cryptosystem based on this group can be secure.

2005

CHES

2005

EPRINT

Cache attacks and Countermeasures: the Case of AES
Abstract

We describe several software side-channel attacks based on inter-process leakage through the state of the CPU's memory cache. This leakage reveals memory access patterns, which can be used for cryptanalysis of cryptographic primitives that employ data-dependent table lookups. The attacks allow an unprivileged process to attack other processes running in parallel on the same processor, despite partitioning methods such as memory protection, sandboxing and virtualization. Some of our methods require only the ability to trigger services that perform encryption or MAC using the unknown key, such as encrypted disk partitions or secure network links. Moreover, we demonstrate an extremely strong type of attack, which requires knowledge of neither the specific plaintexts nor ciphertexts, and works by merely monitoring the effect of the cryptographic process on the cache. We discuss in detail several such attacks on AES, and experimentally demonstrate their applicability to real systems, such as OpenSSL and Linux's dm-crypt encrypted partitions (in the latter case, the full key can be recovered after just 800 writes to the partition, taking 65 milliseconds). Finally, we describe several countermeasures which can be used to mitigate such attacks.

2003

EPRINT

Guaranteeing the diversity of number generators
Abstract

A major problem in using iterative number generators of the
form $x_i=f(x_{i-1})$ is that they can enter unexpectedly short
cycles. This is hard to analyze when the generator is designed,
hard to detect in real time when the generator is used, and can
have devastating cryptanalytic implications. In this paper we
define a measure of security, called \emph{sequence diversity},
which generalizes the notion of cycle-length for non-iterative
generators. We then introduce the class of counter assisted
generators, and show how to turn any iterative generator (even a
bad one designed or seeded by an adversary) into a counter
assisted generator with a provably high diversity, without
reducing the quality of generators which are already
cryptographically strong.

2000

EUROCRYPT

1996

EPRINT

Visual Cryptography II: Improving the Contrast Via the Cover Base
Abstract

In Eurocrypt'94 we proposed a a new type of cryptographic scheme,
which can decode concealed images without any cryptographic computations,
by placing two transparencies on top of each other and using the decoder's
(human) visual systems.
One of the drawback of that proposal was a loss in contrast: a black pixel
is translated in the reconstruction into a black region, but a white
pixel is translated into a grey region (half black and half white).
In this paper we propose am alternative model for reconstruction with a
different set of operation (which we call the ``Cover" semi-group) is proposed.
In this model we are able to obtain a better contrast than
is possible in the previous one.
We prove tight bounds on the contrast
as a function of the complexity of the scheme. We also show
that for constructing k-out-n secret sharing schemes when
n and k are greater than 2 the new method is not applicable.

#### 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 (5)
- Yaniv Carmeli (2)
- Hsieh-Chung Chen (1)
- Chen-Mou Cheng (2)
- Tung Chou (2)
- Don Coppersmith (1)
- Nicolas Courtois (1)
- Itai Dinur (20)
- Yevgeniy Dodis (2)
- Bruce Dodson (1)
- Vivien Dubois (2)
- Orr Dunkelman (30)
- Shimon Even (1)
- Uriel Feige (3)
- Amos Fiat (2)
- Pierre-Alain Fouque (5)
- Dmitry Frumkin (1)
- Willi Geiselmann (1)
- Daniel Genkin (2)
- Oded Goldreich (1)
- Tim Güneysu (1)
- Masha Gutman (1)
- Dani Halevy (1)
- Jonathan J. Hoch (5)
- Naofumi Homma (1)
- James Hughes (1)
- Yael Tauman Kalai (2)
- Nathan Keller (24)
- 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 (2)
- Ruben Niederhagen (2)
- H. Ong (1)
- Dag Arne Osvik (2)
- Christof Paar (1)
- Jacques Patarin (1)
- Inna Polak (1)
- Ronald L. Rivest (2)
- Eyal Ronen (4)
- Dima Ruinskiy (2)
- Akashi Satoh (1)
- Claus-Peter Schnorr (1)
- A. W. Schrift (1)
- Rainer Steinwandt (1)
- Noah Stephens-Davidowitz (2)
- Julien P. Stern (1)
- Jacques Stern (2)
- Moshe Tennenholtz (1)
- Jim Tomlinson (1)
- Eran Tromer (8)
- Boaz Tsaban (3)
- David Wagner (1)
- Daniel Wichs (2)
- Bo-Yin Yang (2)
- Sébastien Zimmer (3)
- Ralf Zimmermann (1)