## CryptoDB

### Alexander Maximov

#### Publications

**Year**

**Venue**

**Title**

2021

TOSC

Improved guess-and-determine and distinguishing attacks on SNOW-V
Abstract

In this paper, we investigate the security of SNOW-V, demonstrating two guess-and-determine (GnD) attacks against the full version with complexities 2384 and 2378, respectively, and one distinguishing attack against a reduced variant with complexity 2303. Our GnD attacks use enumeration with recursion to explore valid guessing paths, and try to truncate as many invalid guessing paths as possible at early stages of the recursion by carefully designing the order of guessing. In our first GnD attack, we guess three 128-bit state variables, determine the remaining four according to four consecutive keystream words. We finally use the next three keystream words to verify the correct guess. The second GnD attack is similar but exploits one more keystream word as side information helping to truncate more guessing paths. Our distinguishing attack targets a reduced variant where 32-bit adders are replaced with exclusive-OR operations. The samples can be collected from short keystream sequences under different (key, IV) pairs. These attacks do not threaten SNOW-V, but provide more in-depth details for understanding its security and give new ideas for cryptanalysis of other ciphers.

2020

TOSC

Spectral analysis of ZUC-256
📺
Abstract

In this paper we develop a number of generic techniques and algorithms in spectral analysis of large linear approximations for use in cryptanalysis. We apply the developed tools for cryptanalysis of ZUC-256 and give a distinguishing attack with complexity around 2236. Although the attack is only 220 times faster than exhaustive key search, the result indicates that ZUC-256 does not provide a source with full 256-bit entropy in the generated keystream, which would be expected from a 256-bit key. To the best of our knowledge, this is the first known academic attack on full ZUC-256 with a computational complexity that is below exhaustive key search.

2020

TOSC

Vectorized linear approximations for attacks on SNOW 3G
📺
Abstract

SNOW 3G is a stream cipher designed in 2006 by ETSI/SAGE, serving in 3GPP as one of the standard algorithms for data confidentiality and integrity protection. It is also included in the 4G LTE standard. In this paper we derive vectorized linear approximations of the finite state machine in SNOW3G. In particular,we show one 24-bit approximation with a bias around 2−37 and one byte-oriented approximation with a bias around 2−40. We then use the approximations to launch attacks on SNOW 3G. The first approximation is used in a distinguishing attack resulting in an expected complexity of 2172 and the second one can be used in a standard fast correlation attack resulting in key recovery in an expected complexity of 2177. If the key length in SNOW 3G would be increased to 256 bits, the results show that there are then academic attacks on such a version faster than the exhaustive key search.

2019

TCHES

New Circuit Minimization Techniques for Smaller and Faster AES SBoxes
📺
Abstract

In this paper we consider various methods and techniques to find the smallest circuit realizing a given linear transformation on n input signals and m output signals, with a constraint of a maximum depth, maxD, of the circuit. Additional requirements may include that input signals can arrive to the circuit with different delays, and output signals may be requested to be ready at a different depth. We apply these methods and also improve previous results in order to find hardware circuits for forward, inverse, and combined AES SBoxes, and for each of them we provide the fastest and smallest combinatorial circuits. Additionally, we propose a novel technique with “floating multiplexers” to minimize the circuit for the combined SBox, where we have two different linear matrices (forward and inverse) combined with multiplexers. The resulting AES SBox solutions are the fastest and smallest to our knowledge.

2019

TOSC

A new SNOW stream cipher called SNOW-V
📺
Abstract

In this paper we are proposing a new member in the SNOW family of stream ciphers, called SNOW-V. The motivation is to meet an industry demand of very high speed encryption in a virtualized environment, something that can be expected to be relevant in a future 5G mobile communication system. We are revising the SNOW 3G architecture to be competitive in such a pure software environment, making use of both existing acceleration instructions for the AES encryption round function as well as the ability of modern CPUs to handle large vectors of integers (e.g. SIMD instructions). We have kept the general design from SNOW 3G, in terms of linear feedback shift register (LFSR) and Finite State Machine (FSM), but both entities are updated to better align with vectorized implementations. The LFSR part is new and operates 8 times the speed of the FSM. We have furthermore increased the total state size by using 128-bit registers in the FSM, we use the full AES encryption round function in the FSM update, and, finally, the initialization phase includes a masking with key bits at its end. The result is an algorithm generally much faster than AES-256 and with expected security not worse than AES-256.

2008

EPRINT

New State Recovery Attack on RC4
Abstract

The stream cipher RC4 was designed by R.~Rivest
in 1987, and it has a very simple and elegant structure. It is
probably the most deployed cipher on the Earth.
~~~~In this paper we analyse the class RC4-$N$ of RC4-like stream ciphers,
where $N$ is the modulus of operations, as well as the length of internal
arrays. Our new attack is a state recovery attack which accepts
the keystream of a certain length, and recovers the internal state.
For the original RC4-256, our attack has total complexity of
around $2^{241}$ operations,
whereas the best previous attack needs $2^{779}$ of time.
Moreover, we show that if the secret key is of length $N$ bits or longer,
the new attack works faster than an exhaustive search. The algorithm of
the attack was implemented and verified on small cases.

2007

EPRINT

Two Trivial Attacks on Trivium
Abstract

Trivium is a stream cipher designed in 2005 by C. De Canni\`ere and B. Preneel for the European project eSTREAM. It has successfully passed the first phase of the project and has been selected for a special focus in the second phase for the hardware portfolio of the project. Trivium has an internal state of size 288 bits and the key of length 80 bits. Although the design has a simple and elegant structure, no attack on it has been found yet.
In this paper we study a class of Trivium-like designs. We propose a set of techniques that one can apply in cryptanalysis of such constructions. The first group of methods is for recovering the internal state and the secret key of the cipher, given a piece of a known keystream. Our attack is more than $2^{30}$ faster than the best known attack. Another group of techniques allows to gather statistics on the keystream, and to build a distinguisher.
We study two designs: the original design of Trivium and a truncated version Bivium, which follows the same design principles as the original. We show that the internal state of the full Trivium can be recovered in time around $c\cdot 2^{83.5}$, and for Bivium this complexity is $c\cdot 2^{36.1}$. These are the best known results for these ciphers. Moreover, a distinguisher for Bivium with working time $2^{32}$ is presented, the correctness of which has been verified by simulations.

2007

EPRINT

Two Linear Distinguishing Attacks on VMPC and RC4A and Weakness of RC4 Family of Stream Ciphers (Corrected)
Abstract

At FSE 2004 two new stream ciphers VMPC and RC4A have been proposed.
VMPC is a generalisation of the stream cipher RC4, whereas RC4A is an
attempt to increase the security of RC4 by introducing an additional
permuter in the design. This paper is the first work
presenting attacks on VMPC and RC4A. We propose two linear
distinguishing attacks, one on VMPC of complexity $2^{39.97}$, and
one on RC4A of complexity $2^{58}$. We investigate the RC4 family of
stream ciphers and show some theoretical weaknesses of such constructions.

2005

FSE

2004

EPRINT

Plateaued Rotation Symmetric Boolean Functions on Odd Number of Variables
Abstract

The class of Rotation Symmetric Boolean Functions (RSBFs) has received serious attention recently in searching functions of cryptographic significance. These functions are invariant under circular translation of indices. In this paper we study such functions on odd number of variables and interesting combinatorial properties related to Walsh spectra of such functions are revealed. In particular we concentrate on plateaued functions (functions with three valued Walsh spectra) in this class and derive necessary conditions for existence of balanced rotation symmetric plateaued functions. As application of our result we show the non existence of 9-variable, 3-resilient RSBF with nonlinearity 240 that has been posed as an open question in FSE 2004. Further we show how one can make efficient search in the space of RSBFs based on our theoretical results and as example we complete the search for unbalanced 9-variable, 3rd order correlation immune plateaued RSBFs with nonlinearity 240.

2004

EPRINT

Classes of Plateaued Rotation Symmetric Boolean Functions under Transformation of Walsh Spectra
Abstract

Construction methods of Boolean functions with cryptographically
significant properties is an important and difficult problem.
In this work we investigate the class of rotation symmetric
Boolean functions (RSBFs). These functions
are invariant under circular translation of indices and
were mainly introduced for efficient implementation purposes.
First, we derive general results on these functions. Afterwards,
we concentrate on plateaued RSBFs on odd number of variables,
which have three valued Walsh Spectra ($0, \pm \lambda$), and
can have maximum nonlinearity.
We consider both cases when the number of
variables $n$ is composite and prime.
%
When $n$ is odd and prime, we derive the constructive relation
between {\it balanced/unbalanced} plateaued RSBFs and show how
from one given such function the complete sub class can be generated.
As long as search for one plateaued RSBF is of high complexity,
our proposed manipulation technique with Walsh spectra imediately give us
the way to construct many such functions without time
consuming. Since the most important properties of a function are
determined via the values of Walsh spectra, then such transformation
technique is important to create new function with, possible, better
properties. The application of our transformation technique construct
a class of
$\left((2^{\frac{n-1}{2}}+1)/n\right)!\cdot
\left(2^{\frac{n-1}{2}}-1\right)$
balanced/unbalanced plateaued RSBFs.
%
In our practical implementation of this technique,
given one balanced PRSBF on $n=11$ variables we could
construct 185 new such functions. To find the
first function took us several days, whereas to construct new 185 functions
took us just a second. However, this technique can
be applied only when the Legendre symbol $(2/n)$ is $-1$, and
the first such $n$'s are $3, 5, 7, 11, 13, 19, 29, 37, 43, \ldots$.

#### Coauthors

- Côme Berbain (1)
- Alex Biryukov (1)
- Patrik Ekdahl (2)
- Henri Gilbert (1)
- Martin Hell (1)
- Thomas Johansson (5)
- Christine Jost (1)
- Dmitry Khovratovich (2)
- Ha Lam (1)
- Subhamoy Maitra (1)
- Ben J. M. Smeets (1)
- Jing Yang (4)