## CryptoDB

### Alexander Maximov

#### Affiliation: Ericsson AB

#### Publications

**Year**

**Venue**

**Title**

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.

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 (1)
- Henri Gilbert (1)
- Martin Hell (1)
- Thomas Johansson (1)
- Christine Jost (1)
- Dmitry Khovratovich (2)
- Ha Lam (1)
- Subhamoy Maitra (1)
- Ben J. M. Smeets (1)