## CryptoDB

### Nathan Keller

#### Affiliation: Bar-Ilan University, Israel

#### Publications

**Year**

**Venue**

**Title**

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.

2018

CRYPTO

An Optimal Distributed Discrete Log Protocol with Applications to Homomorphic Secret Sharing
📺
Abstract

The distributed discrete logarithm (DDL) problem was introduced by Boyle et al. at CRYPTO 2016. A protocol solving this problem was the main tool used in the share conversion procedure of their homomorphic secret sharing (HSS) scheme which allows non-interactive evaluation of branching programs among two parties over shares of secret inputs.Let g be a generator of a multiplicative group $$\mathbb {G}$$G. Given a random group element $$g^{x}$$gx and an unknown integer $$b \in [-M,M]$$b∈[-M,M] for a small M, two parties A and B (that cannot communicate) successfully solve DDL if $$A(g^{x}) - B(g^{x+b}) = b$$A(gx)-B(gx+b)=b. Otherwise, the parties err. In the DDL protocol of Boyle et al., A and B run in time T and have error probability that is roughly linear in M/T. Since it has a significant impact on the HSS scheme’s performance, a major open problem raised by Boyle et al. was to reduce the error probability as a function of T.In this paper we devise a new DDL protocol that substantially reduces the error probability to $$O(M \cdot T^{-2})$$O(M·T-2). Our new protocol improves the asymptotic evaluation time complexity of the HSS scheme by Boyle et al. on branching programs of size S from $$O(S^2)$$O(S2) to $$O(S^{3/2})$$O(S3/2). We further show that our protocol is optimal up to a constant factor for all relevant cryptographic group families, unless one can solve the discrete logarithm problem in a short interval of length R in time $$o(\sqrt{R})$$o(R).Our DDL protocol is based on a new type of random walk that is composed of several iterations in which the expected step length gradually increases. We believe that this random walk is of independent interest and will find additional applications.

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

JOFC

2012

CRYPTO

2010

CRYPTO

2010

EUROCRYPT

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

Related-Key Boomerang and Rectangle Attacks
Abstract

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
Abstract

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
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.

2008

EPRINT

Treatment of the Initial Value in Time-Memory-Data Tradeoff Attacks on Stream Ciphers
Abstract

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
Abstract

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.

2006

EPRINT

Linear Cryptanalysis of CTC
Abstract

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.

2006

EPRINT

MV3: A new word based stream cipher using rapid mixing and revolving buffers
Abstract

MV3 is a new word based stream cipher for encrypting long streams of data. A direct adaptation of a byte based cipher such as RC4 into a 32- or 64-bit word version will obviously need vast amounts of memory. This scaling issue necessitates a look for new components and principles, as well as mathematical analysis to justify their use. Our approach, like RC4's, is based on rapidly mixing random walks on directed graphs (that is, walks which reach a random state quickly, from any starting point). We begin with some well understood walks, and then introduce nonlinearity in their steps in order to improve security and show long term statistical correlations are negligible. To minimize the short term correlations, as well as to deter attacks using equations involving successive outputs, we provide a method for sequencing the outputs derived from the walk using three revolving buffers. The cipher is fast --- it runs at a speed of less than 5 cycles per byte on a Pentium IV processor. A word based cipher needs to output more bits per step, which exposes more correlations for attacks. Moreover we seek simplicity of construction and transparent analysis. To meet these requirements, we use a larger state and claim security corresponding to only a fraction of it. Our design is for an adequately secure word-based cipher; our very preliminary estimate puts the security close to exhaustive search for keys of size < 256 bits.

2002

EPRINT

New Results on Boomerang and Rectangle Attack
Abstract

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

EPRINT

The Rectangle Attack - Rectangling the Serpent
Abstract

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

- Eurocrypt 2020
- FSE 2019
- Eurocrypt 2018
- FSE 2018
- Eurocrypt 2017
- Asiacrypt 2015
- Eurocrypt 2013
- FSE 2009

#### Coauthors

- Achiya Bar-On (5)
- Elad Barkan (2)
- Eli Biham (21)
- Alex Biryukov (1)
- Itai Dinur (10)
- Orr Dunkelman (45)
- Seokhie Hong (1)
- Sebastiaan Indesteege (1)
- Dmitry Khovratovich (1)
- Jongsung Kim (2)
- Ohad Klein (1)
- Virginie Lallemand (1)
- Jiqiang Lu (1)
- Stephen D. Miller (1)
- Ilya Mironov (1)
- Bart Preneel (2)
- Eyal Ronen (1)
- Adi Shamir (19)
- Boaz Tsaban (1)
- Ramarathnam Venkatesan (1)
- Ariel Weizman (1)