## CryptoDB

### Alexander Maximov

#### Publications

Year
Venue
Title
2020
TOSC
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
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
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
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.
2015
EPRINT
2008
CRYPTO
2008
EPRINT
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
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
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.
2006
FSE
2005
ASIACRYPT
2005
FSE
2004
FSE
2004
EPRINT
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
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$.