International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Alex Biryukov

Affiliation: University of Luxembourg

Publications

Year
Venue
Title
2018
ASIACRYPT
Attacks and Countermeasures for White-box Designs
Alex Biryukov Aleksei Udovenko
In traditional symmetric cryptography, the adversary has access only to the inputs and outputs of a cryptographic primitive. In the white-box model the adversary is given full access to the implementation. He can use both static and dynamic analysis as well as fault analysis in order to break the cryptosystem, e.g. to extract the embedded secret key. Implementations secure in such model have many applications in industry. However, creating such implementations turns out to be a very challenging if not an impossible task.Recently, Bos et al. [7] proposed a generic attack on white-box primitives called differential computation analysis (DCA). This attack was applied to many white-box implementations both from academia and industry. The attack comes from the area of side-channel analysis and the most common method protecting against such attacks is masking, which in turn is a form of secret sharing. In this paper we present multiple generic attacks against masked white-box implementations. We use the term “masking” in a very broad sense. As a result, we deduce new constraints that any secure white-box implementation must satisfy.Based on the new constraints, we develop a general method for protecting white-box implementations. We split the protection into two independent components: value hiding and structure hiding. Value hiding must provide protection against passive DCA-style attacks that rely on analysis of computation traces. Structure hiding must provide protection against circuit analysis attacks. In this paper we focus on developing the value hiding component. It includes protection against the DCA attack by Bos et al. and protection against a new attack called algebraic attack.We present a provably secure first-order protection against the new algebraic attack. The protection is based on small gadgets implementing secure masked XOR and AND operations. Furthermore, we give a proof of compositional security allowing to freely combine secure gadgets. We derive concrete security bounds for circuits built using our construction.
2017
ASIACRYPT
2016
EUROCRYPT
2016
CRYPTO
2016
FSE
2016
ASIACRYPT
2016
TOSC
Multiset-Algebraic Cryptanalysis of Reduced Kuznyechik, Khazad, and secret SPNs
We devise the first closed formula for the number of rounds of a blockcipher with secret components so that these components can be revealed using multiset, algebraic-degree, or division-integral properties, which in this case are equivalent. Using the new result, we attack 7 (out of 9) rounds of Kuznyechik, the recent Russian blockcipher standard, thus halving its security margin. With the same technique we attack 6 (out of 8) rounds of Khazad, the legacy 64-bit blockcipher. Finally, we show how to cryptanalyze and find a decomposition of generic SPN construction for which the inner-components are secret. All the attacks are the best to date.
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
FSE
2015
CRYPTO
2015
ASIACRYPT
2014
EPRINT
2014
ASIACRYPT
2014
FSE
2013
FSE
2011
FSE
2011
FSE
2011
ASIACRYPT
2010
EPRINT
Feasible Attack on the 13-round AES-256
Alex Biryukov Dmitry Khovratovich
In this note we present the first attack with feasible complexity on the 13-round AES-256. The attack runs in the related-subkey scenario with four related keys, in 2^{76} time, data, and memory.
2010
JOFC
2010
EUROCRYPT
2010
EUROCRYPT
2010
EPRINT
Automatic Search for Related-Key Diff erential Characteristics in Byte-Oriented Block Ciphers: Application to AES, Camellia, Khazad and Others
Alex Biryukov Ivica Nikolić
While di fferential behavior of modern ciphers in a single secret key scenario is relatively well understood, and simple techniques for computation of security lower bounds are readily available, the security of modern block ciphers against related-key attacks is still very ad hoc. In this paper we make a first step towards provable security of block ciphers against related-key attacks by presenting an efficient search tool for finding diff erential characteristics both in the state and in the key (note that due to similarities between block ciphers and hash functions such tool will be useful in analysis of hash functions as well). We use this tool to search for the best possible (in terms of the number of rounds) related-key diff erential characteristics in AES, byte-Camellia, Khazad, FOX, and Anubis. We show the best related-key diff erential characteristics for 5, 11, and 14 rounds of AES-128, AES-192, and AES-256 respectively. We use the optimal diff erential characteristics to design the best related-key and chosen key attacks on AES-128 (7 out of 10 rounds), AES-192 (full 12 rounds), byte-Camellia (full 18 rounds) and Khazad (7 and 8 out of 8 rounds). We also show that ciphers FOX and Anubis have no related-key attacks on more than 4-5 rounds.
2009
ASIACRYPT
2009
CRYPTO
2009
FSE
2008
FSE
2008
EPRINT
Slid Pairs in Salsa20 and Trivium
Deike Priemuth-Schmid Alex Biryukov
The stream ciphers Salsa20 and Trivium are two of the finalists of the eSTREAM project which are in the final portfolio of new promising stream ciphers. In this paper we show that initialization and key-stream generation of these ciphers is {\em slidable}, i.e. one can find distinct (Key, IV) pairs that produce identical (or closely related) key-streams. There are $2^{256}$ and more then $2^{39}$ such pairs in Salsa20 and Trivium respectively. We write out and solve the non-linear equations which describe such related (Key, IV) pairs. This allows us to sample the space of such related pairs efficiently as well as detect such pairs in large portions of key-stream very efficiently. We show that Salsa20 does not have 256-bit security if one considers general birthday and related key distinguishing and key-recovery attacks.
2007
CHES
2007
CHES
2007
EPRINT
Two Trivial Attacks on Trivium
Alexander Maximov Alex Biryukov
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.
2006
EPRINT
On the Security of HMAC and NMAC Based on HAVAL, MD4, MD5, SHA-0 and SHA-1
HMAC is a widely used message authentication code and a pseudorandom function generator based on cryptographic hash functions such as MD5 and SHA-1. It has been standardized by ANSI, IETF, ISO and NIST. HMAC is proved to be secure as long as the compression function of the underlying hash function is a pseudorandom function. In this paper we devise two new distinguishers of the structure of HMAC, called {\em differential} and {\em rectangle distinguishers}, and use them to discuss the security of HMAC based on HAVAL, MD4, MD5, SHA-0 and SHA-1. We show how to distinguish HMAC with reduced or full versions of these cryptographic hash functions from a random function or from HMAC with a random function. We also show how to use our differential distinguisher to devise a forgery attack on HMAC. Our distinguishing and forgery attacks can also be mounted on NMAC based on HAVAL, MD4, MD5, SHA-0 and SHA-1. Furthermore, we show that our differential and rectangle distinguishers can lead to second-preimage attacks on HMAC and NMAC.
2005
FSE
2005
EPRINT
Some Thoughts on Time-Memory-Data Tradeoffs
Alex Biryukov
In this paper we show that Time-Memory tradeoff by Hellman may be extended to Time-Memory-Key tradeoff thus allowing attacks much faster than exhaustive search for ciphers for which typically it is stated that no such attack exists. For example, as a result AES with 128-bit key has only 85-bit security if $2^{43}$ encryptions of an arbitrary fixed text under different keys are available to the attacker. Such attacks are generic and are more practical than some recent high complexity chosen related-key attacks on round-reduced versions of AES. They constitute a practical threat for any cipher with 80-bit or shorter keys and are marginally practical for 128-bit key ciphers. We also show that UNIX password scheme even with carefully generated passwords is vulnerable to practical tradeoff attacks. Finally we also demonstrate a combination of rainbow tables with the time-memory-data tradeoff which results in a new tradeoff curve.
2005
EPRINT
On the Security of Encryption Modes of MD4, MD5 and HAVAL
MD4 is a cryptographic hash function introduced in 1990 by Rivest. After MD4 was proposed, several hash functions such as MD5, HAVAL, RIPEMD, RIPEMD-160, SHA-1 and SHA-256 were designed based on the MD4 structure. In this paper, we cryptanalyze the compression functions of MD4, MD5 and 4-, 5-pass HAVAL in encryption modes. We exploit the recently proposed related-key rectangle and boomerang techniques to show non-randomness of MD4, MD5 and 4-, 5-pass HAVAL and to distinguish them from a randomly chosen cipher. The attacks are highly practical and have been confirmed by our experiments.
2005
JOFC
2004
CRYPTO
2004
EPRINT
On Multiple Linear Approximations
In this paper we study the long standing problem of information extraction from multiple linear approximations. We develop a formal statistical framework for block cipher attacks based on this technique and derive explicit and compact gain formulas for generalized versions of Matsui's Algorithm 1 and Algorithm 2. The theoretical framework allows both approaches to be treated in a unified way, and predicts significantly improved attack complexities compared to current linear attacks using a single approximation. In order to substantiate the theoretical claims, we benchmarked the attacks against reduced-round versions of DES and observed a clear reduction of the data and time complexities, in almost perfect correspondence with the predictions. The complexities are reduced by several orders of magnitude for Algorithm 1, and the significant improvement in the case of Algorithm 2 suggests that this approach may outperform the currently best attacks on the full DES algorithm.
2004
EPRINT
Block Ciphers and Stream Ciphers: The State of the Art
Alex Biryukov
In these lecture notes we survey the state of the art in symmetric key encryption, in particular in the block ciphers and stream ciphers area. The area of symmetric key encryption has been very active in the last five years due to growing interest from academic and industry research, standardization efforts like AES, NESSIE and CRYPTREC, as well as due to ease of government control over export of cryptography.
2003
ASIACRYPT
2003
CRYPTO
2003
EUROCRYPT
2003
FSE
2003
FSE
2003
EPRINT
Crytanalysis of SAFER++
This paper presents several multiset and boomerang attacks on SAFER++ up to 5.5 out of its 7 rounds. These are the best known attacks for this cipher and significantly improve the previously known results. The attacks in the paper are practical up to 4 rounds. The methods developed to attack SAFER++ can be applied to other substitution-permutation networks with incomplete diffusion.
2003
EPRINT
Cryptanalysis of the Alleged SecurID Hash Function
Alex Biryukov Joseph Lano Bart Preneel
The SecurID hash function is used for authenticating users to a corporate computer infrastructure. We analyse an alleged implementation of this hash function. The block cipher at the heart of the function can be broken in few milliseconds on a PC with 70 adaptively chosen plaintexts. The 64-bit secret key of 10$\%$ of the cards can be discovered given two months of token outputs and $2^{48}$ analysis steps. A larger fraction of cards can be covered given more observation time.
2001
EUROCRYPT
2000
ASIACRYPT
2000
EUROCRYPT
2000
FSE
1999
EUROCRYPT
1999
FSE
1999
FSE
Slide Attacks
Alex Biryukov David Wagner
1998
CRYPTO
1998
EUROCRYPT
1997
JOFC
1994
ASIACRYPT
1994
EUROCRYPT

Program Committees

Eurocrypt 2019
FSE 2019
Crypto 2018
FSE 2018
Crypto 2016
FSE 2016
Eurocrypt 2015
CHES 2013
FSE 2013
FSE 2012
Asiacrypt 2012
Crypto 2011
FSE 2010
FSE 2009
FSE 2008
Asiacrypt 2007
FSE 2007 (Program chair)
Crypto 2007
Eurocrypt 2006
Crypto 2005
Asiacrypt 2005
Eurocrypt 2004
Crypto 2000