References of "Biryukov, Alex 50000799"
     in
Bookmark and Share    
Peer Reviewed
See detailTriathlon of Lightweight Block Ciphers for the Internet of Things
Dinu, Dumitru-Daniel UL; Le Corre, Yann UL; Khovratovich, Dmitry UL et al

Scientific Conference (2015, July)

In this paper we introduce an open framework for the benchmarking of lightweight block ciphers on a multitude of embedded platforms. Our framework is able to evaluate execution time, RAM footprint, as ... [more ▼]

In this paper we introduce an open framework for the benchmarking of lightweight block ciphers on a multitude of embedded platforms. Our framework is able to evaluate execution time, RAM footprint, as well as (binary) code size, and allows a user to define a custom "figure of merit" according to which all evaluated candidates can be ranked. We used the framework to benchmark various implementations of 13 lightweight ciphers, namely AES, Fantomas, HIGHT, LBlock, LED, Piccolo, PRESENT, PRINCE, RC5, Robin, Simon, Speck, and TWINE, on three different platforms: 8-bit ATmega, 16-bit MSP430, and 32-bit ARM. Our results give new insights to the question of how well these ciphers are suited to secure the Internet of Things (IoT). The benchmarking framework provides cipher designers with a tool to compare new algorithms with the state-of-the-art and allows standardization bodies to conduct a fair and comprehensive evaluation of a large number of candidates. [less ▲]

Detailed reference viewed: 458 (30 UL)
Full Text
Peer Reviewed
See detailDifferential Analysis and Meet-in-the-Middle Attack against Round-Reduced TWINE
Biryukov, Alex UL; Derbez, Patrick UL; Perrin, Léo Paul UL

in Leander, Gregor (Ed.) Fast Software Encryption - 22nd International Workshop, FSE 2015, Istanbul, March 8-11, 2015 (2015, March)

TWINE is a recent lightweight block cipher based on a Feistel structure. We first present two new attacks on TWINE-128 reduced to 25 rounds that have a slightly higher overall complexity than the 25-round ... [more ▼]

TWINE is a recent lightweight block cipher based on a Feistel structure. We first present two new attacks on TWINE-128 reduced to 25 rounds that have a slightly higher overall complexity than the 25-round attack presented by Wang and Wu at ACISP 2014, but a lower data complexity. Then, we introduce alternative representations of both the round function of this block cipher and of a sequence of 4 rounds. LBlock, another lightweight block cipher, turns out to exhibit the same behaviour. Then, we illustrate how this alternative representation can shed new light on the security of TWINE by deriving high probability iterated truncated differential trails covering 4 rounds with probability $2^{-16}$. The importance of these is shown by combining different truncated differential trails to attack 23-rounds TWINE-128 and by giving a tighter lower bound on the high probability of some differentials by clustering differential characteristics following one of these truncated trails. A comparison between these high probability differentials and those recently found in a variant of LBlock by Leurent highlights the importance of considering the whole distribution of the coefficients in the difference distribution table of a S-Box and not only their maximum value. [less ▲]

Detailed reference viewed: 262 (12 UL)
Full Text
Peer Reviewed
See detailProof-of-Work as Anonymous Micropayment: Rewarding a Tor Relay
Biryukov, Alex UL; Pustogarov, Ivan UL

in Financial Cryptography and Data Security - 19th International Conference (2015, January)

In this paper we propose a new micropayments scheme which can be used to reward Tor relay operators. Tor clients do not pay Tor relays with electronic cash directly but submit proof of work shares which ... [more ▼]

In this paper we propose a new micropayments scheme which can be used to reward Tor relay operators. Tor clients do not pay Tor relays with electronic cash directly but submit proof of work shares which the relays can resubmit to a crypto-currency mining pool. Relays credit users who submit shares with tickets that can later be used to purchase improved service. Both shares and tickets when sent over Tor circuits are anonymous. The analysis of the crypto-currencies market prices shows that the proposed scheme can compensate significant part of Tor relay operator's expenses. [less ▲]

Detailed reference viewed: 1252 (126 UL)
Full Text
See detailArgon and Argon2
Biryukov, Alex UL; Dinu, Dumitru-Daniel UL; Khovratovich, Dmitry UL

Report (2015)

This is a design specification for the functions Argon and Argon2 for the international password hashing competition (PHC), 2013-2015. Argon is our original submission to PHC. It is a multipurpose hash ... [more ▼]

This is a design specification for the functions Argon and Argon2 for the international password hashing competition (PHC), 2013-2015. Argon is our original submission to PHC. It is a multipurpose hash function, that is optimized for highest resilience against tradeoff attacks, so that any, even small memory reduction would lead to significant time and computational penalties. Argon can be used for password hashing, key derivation, or any other memory-hard computation (e.g., for cryptocurrencies). Argon2 summarizes the state of the art in the design of memory-hard functions. It is a streamlined and simple design. It aims at the highest memoryfilling rate and effective use of multiple computing units, while still providing defense against tradeoff attacks. Argon2 is optimized for the x86 architecture and exploits the cache and memory organization of the recent Intel and AMD processors. Argon2 has two variants: Argon2d and Argon2i. Argon2d is faster and uses data-depending memory access, which makes it suitable for cryptocurrencies and applications with no threats from side-channel timing attacks. Argon2i uses data-independent memory access, which is preferred for password hashing and password based key derivation. Argon2i is slower as it makes more passes over the memory to protect from tradeoff attacks. We recommend Argon for the applications that aim for the highest tradeoff resilience and want to guarantee prohibitive time and computational penalties on any memory-reducing implementation. According to our cryptanalytic algorithms, an attempt to use half of the requested memory (for instance, 64 MB instead of 128 MB) results in the speed penalty factor of 140 and in the penalty 218. The penalty grows exponentially as the available memory decreases, which effectively prohibits the adversary to use any smaller amount of memory. Such high computational penalties are a unique feature of Argon. We recommend Argon2 for the applications that aim for high performance. Both versions of Argon2 allow to fill 1 GB of RAM in a fraction of second, and smaller amounts even faster. It scales easily to the arbitrary number of parallel computing units. Its design is also optimized for clarity to ease analysis and implementation. [less ▲]

Detailed reference viewed: 415 (14 UL)
See detailProgress in Cryptology - INDOCRYPT 2015 - 16th International Conference on Cryptology in India
Biryukov, Alex UL; Vipul, Goyal

Book published by Springer (2015)

Detailed reference viewed: 119 (8 UL)
Full Text
Peer Reviewed
See detailCryptographic Schemes Based on the ASASA Structure: Black-box, White-box, and Public-key
Biryukov, Alex UL; Bouillaguet, Charles; Khovratovich, Dmitry UL

in 20th International Conference on the Theory and Application of Cryptology and Information Security (2014, December)

In this paper we pick up an old challenge to design public key or white-box constructions from symmetric cipher components. We design several encryption schemes based on the ASASA structure ranging from ... [more ▼]

In this paper we pick up an old challenge to design public key or white-box constructions from symmetric cipher components. We design several encryption schemes based on the ASASA structure ranging from fast and generic symmetric ciphers to compact public key and white-box constructions based on generic affine transformations combined with specially designed low degree non-linear layers. While explaining our design process we show several instructive attacks on the weaker variants of our schemes. [less ▲]

Detailed reference viewed: 370 (11 UL)
Full Text
Peer Reviewed
See detailBitcoin over Tor isn't a good idea
Biryukov, Alex UL; Pustogarov, Ivan UL

in 2015 IEEE Symposium on Security and Privacy (2014, November)

Bitcoin is a decentralized P2P digital currency in which coins are generated by a distributed set of miners and transaction are broadcasted via a peer-to-peer network. While Bitcoin provides some level of ... [more ▼]

Bitcoin is a decentralized P2P digital currency in which coins are generated by a distributed set of miners and transaction are broadcasted via a peer-to-peer network. While Bitcoin provides some level of anonymity (or rather pseudonymity) by encouraging the users to have any number of random-looking Bitcoin addresses, recent research shows that this level of anonymity is rather low. This encourages users to connect to the Bitcoin network through anonymizers like Tor and motivates development of default Tor functionality for popular mobile SPV clients. In this paper we show that combining Tor and Bitcoin creates an attack vector for the deterministic and stealthy man-in-the-middle attacks. A low-resource attacker can gain full control of information flows between all users who chose to use Bitcoin over Tor. In particular the attacker can link together user’s transactions regardless of pseudonyms used, control which Bitcoin blocks and transactions are relayed to the user and can delay or discard user’s transactions and blocks. In collusion with a powerful miner double-spending attacks become possible and a totally virtual Bitcoin reality can be created for such set of users. [less ▲]

Detailed reference viewed: 392 (25 UL)
Full Text
Peer Reviewed
See detailDeanonymisation of clients in Bitcoin P2P network
Biryukov, Alex UL; Khovratovich, Dmitry UL; Pustogarov, Ivan UL

in ACM Conference on Computer and Communications Security (CCS) (2014, November)

Bitcoin is a digital currency which relies on a distributed set of miners to mint coins and on a peer-to-peer network to broadcast transactions. The identities of Bitcoin users are hidden behind ... [more ▼]

Bitcoin is a digital currency which relies on a distributed set of miners to mint coins and on a peer-to-peer network to broadcast transactions. The identities of Bitcoin users are hidden behind pseudonyms (public keys) which are recommended to be changed frequently in order to increase transaction unlinkability. We present an efficient method to deanonymize Bitcoin users, which allows to link user pseudonyms to the IP addresses where the transactions are generated. Our techniques work for the most common and the most challenging scenario when users are behind NATs or firewalls of their ISPs. They allow to link transactions of a user behind a NAT and to distinguish connections and transactions of different users behind the same NAT. We also show that a natural countermeasure of using Tor or other anonymity services can be cut-off by abusing anti-DoS countermeasures of the bitcoin network. Our attacks require only a few machines and have been experimentally verified. We propose several countermeasures to mitigate these new attacks. [less ▲]

Detailed reference viewed: 15588 (140 UL)
Full Text
Peer Reviewed
See detailPAEQ: Parallelizable Permutation-Based Authenticated Encryption
Biryukov, Alex UL; Khovratovich, Dmitry UL

in 17th Information Security Conference (2014, November)

We propose a new authenticated encryption scheme PAEQ, which employs a fixed public permutation. In contrast to the recent sponge-based proposals, our scheme is fully parallelizable. It also allows ... [more ▼]

We propose a new authenticated encryption scheme PAEQ, which employs a fixed public permutation. In contrast to the recent sponge-based proposals, our scheme is fully parallelizable. It also allows flexible key and nonce length, and is one of the few which achieves 128-bit security for both confidentiality and data authenticity with the same key length. The permutation within PAEQ is a new design called AESQ, which is based on AES and is 512 bits wide. In contrast to similar constructions used in the SHA-3 competition, our permutation fully benefits from the newest Intel AES instructions and runs at 2.5 cycles per byte if used as the counter-mode PRF. [less ▲]

Detailed reference viewed: 548 (3 UL)
Full Text
Peer Reviewed
See detailContent and popularity analysis of Tor hidden services
Biryukov, Alex UL; Pustogarov, Ivan UL; Thill, Fabrice et al

in proceedings of the 2014 IEEE 34th International Conference on Distributed Computing Systems Workshops (2014, June)

Tor hidden services allow running Internet services while protecting the location of the servers. Their main purpose is to enable freedom of speech even in situations in which powerful adversaries try to ... [more ▼]

Tor hidden services allow running Internet services while protecting the location of the servers. Their main purpose is to enable freedom of speech even in situations in which powerful adversaries try to suppress it. However, providing location privacy and client anonymity also makes Tor hidden services an attractive platform for every kind of imaginable shady service. The ease with which Tor hidden services can be set up has spurred a huge growth of anonymously provided Internet services of both types. In this paper we analyse the landscape of Tor hidden services. We have studied 39824 hidden service descriptors collected on 4th of Feb 2013: we scanned them for open ports; in the case of 3050 HTTP services, we analysed and classified their content. We also estimated the popularity of hidden services by looking at the request rate for hidden service descriptors by clients. We found that while the content of Tor hidden services is rather varied, the most popular hidden services are related to botnets.We also propose a method for opportunistic deanonymisation of Tor Hidden Service clients. In addtiton, we identify past attempts to track “Silkroad” by consensus history analysis. [less ▲]

Detailed reference viewed: 385 (12 UL)
Full Text
Peer Reviewed
See detailDifferential entropy analysis of the IDEA block cipher
Biryukov, Alex UL; Nakahara, Jorge; Murat Yildirim, Hamdi

in Journal of Computational and Applied Mathematics (2014), 259(Part B), 561570

This paper describes a new cryptanalytic technique that combines differential cryptanalysis with Shannon entropy. We call it differential entropy (DE). The objective is to exploit the non-uniform ... [more ▼]

This paper describes a new cryptanalytic technique that combines differential cryptanalysis with Shannon entropy. We call it differential entropy (DE). The objective is to exploit the non-uniform distribution of output differences from a given mapping as a distinguishing tool in cryptanalysis. Our preferred target is the IDEA block cipher, since we detected significantly low entropy at the output of its multiplication operation. We looked to further extend this entropy analysis to larger components and for a number of rounds. We present key-recovery attacks on up to 2.5-round IDEA in the single-key model and without weak-key assumptions. [less ▲]

Detailed reference viewed: 149 (1 UL)
Full Text
Peer Reviewed
See detailAutomatic Search for Differential Trails in ARX Ciphers
Biryukov, Alex UL; Velichkov, Vesselin UL

in Topics in Cryptology – CT-RSA 2014 Lecture Notes in Computer Science (2014)

We propose a tool for automatic search for differential trails in ARX ciphers. By introducing the concept of a partial difference distribution table (pDDT) we extend Matsui's algorithm, originally ... [more ▼]

We propose a tool for automatic search for differential trails in ARX ciphers. By introducing the concept of a partial difference distribution table (pDDT) we extend Matsui's algorithm, originally proposed for DES-like ciphers, to the class of ARX ciphers. To the best of our knowledge this is the first application of Matsui's algorithm to ciphers that do not have S-boxes. The tool is applied to the block ciphers TEA, XTEA, SPECK and RAIDEN. For RAIDEN we find an iterative characteristic on all 32 rounds that can be used to break the full cipher using standard differential cryptanalysis. This is the first cryptanalysis of the cipher in a non-related key setting. Differential trails on 9, 10 and 13 rounds are found for SPECK32, SPECK48 and SPECK64 respectively. The 13 round trail covers half of the total number of rounds. These are the first public results on the security analysis of SPECK. For TEA multiple full (i.e. not truncated) differential trails are reported for the first time, while for XTEA we confirm the previous best known trail reported by Hong et al. We also show closed formulas for computing the exact additive differential probabilities of the left and right shift operations. The source code of the tool is publicly available as part of a larger toolkit for the analysis of ARX at the following address: https://github.com/vesselinux/yaarx . [less ▲]

Detailed reference viewed: 280 (13 UL)
Full Text
Peer Reviewed
See detailColliding Keys for SC2000-256
Biryukov, Alex UL; Nikolic, Ivica

in Selected Areas in Cryptography, Lecture Notes in Computer Science (2014)

In this work we present analysis for the block cipher SC2000, which is in the Japanese CRYPTREC portfolio for standardization. In spite of its very complex and non-linear key-schedule we have found a ... [more ▼]

In this work we present analysis for the block cipher SC2000, which is in the Japanese CRYPTREC portfolio for standardization. In spite of its very complex and non-linear key-schedule we have found a property of the full SC2000-256 (with 256-bit keys) which allows the attacker to find many pairs of keys which generate identical sets of subkeys. Such colliding keys result in identical encryptions. We designed an algorithm that efficiently produces colliding key pairs in 2^39 time, which takes a few hours on a PC. We show that there are around 2^68 colliding pairs, and the whole set can be enumerated in 2^58 time. This result shows that SC2000-256 cannot model an ideal cipher. Furthermore we explain how practical collisions can be produced for both Davies-Meyer and Hiroses hash function constructions instantiated with SC2000-256 . [less ▲]

Detailed reference viewed: 79 (1 UL)
Full Text
Peer Reviewed
See detailDifferential Analysis of Block Ciphers SIMON and SPECK
Biryukov, Alex UL; Roy, Arnab; Velichkov, Vesselin UL

in Fast Software Encryption - 21st International Workshop (2014)

In this paper we continue the previous line of research on the analysis of the differential properties of the lightweight block ciphers Simon and Speck. We apply a recently proposed technique for ... [more ▼]

In this paper we continue the previous line of research on the analysis of the differential properties of the lightweight block ciphers Simon and Speck. We apply a recently proposed technique for automatic search for differential trails in ARX ciphers and improve the trails in Simon32 and Simon48 previously reported as best. We further extend the search technique for the case of differen- tials and improve the best previously reported differentials on Simon32, Simon48 and Simon64 by exploiting more effectively the strong differential effect of the cipher. We also present improved trails and differentials on Speck32, Speck48 and Speck64. Using these new results we improve the currently best known attacks on several versions of Simon and Speck. A second major contribution of the paper is a graph based algorithm (linear time) for the computation of the exact differential probability of the main building block of Simon: an AND operation preceded by two bitwise shift operations. This gives us a better insight into the differential property of the Simon round function and differential effect in the cipher. Our algorithm is general and works for any rotation constants. The presented techniques are generic and are therefore applicable to a broader class of ARX designs. [less ▲]

Detailed reference viewed: 282 (11 UL)
Full Text
Peer Reviewed
See detailTrawling for tor hidden services: Detection, measurement, deanonymization
Biryukov, Alex UL; Pustogarov, Ivan UL; Weinmann, Ralf-Philipp UL

in 2013 IEEE Symposium on Security and Privacy (SP) (2013, May 19)

Tor is the most popular volunteer-based anonymity network consisting of over 3000 volunteer-operated relays. Apart from making connections to servers hard to trace to their origin it can also provide ... [more ▼]

Tor is the most popular volunteer-based anonymity network consisting of over 3000 volunteer-operated relays. Apart from making connections to servers hard to trace to their origin it can also provide receiver privacy for Internet services through a feature called "hidden services". In this paper we expose flaws both in the design and implementation of Tor's hidden services that allow an attacker to measure the popularity of arbitrary hidden services, take down hidden services and deanonymize hidden services. We give a practical evaluation of our techniques by studying: (1) a recent case of a botnet using Tor hidden services for command and control channels; (2) Silk Road, a hidden service used to sell drugs and other contraband; (3) the hidden service of the DuckDuckGo search engine. [less ▲]

Detailed reference viewed: 518 (6 UL)
Full Text
Peer Reviewed
See detailComplementing Feistel Ciphers
Biryukov, Alex UL; Nikolic, Ivica

in Fast Software Encryption, 20th International Workshop, Lecture Notes in Computer Science (2013)

In this paper, we propose related-key differential distinguishers based on the complementation property of Feistel ciphers. We show that with relaxed requirements on the complementation, i.e. the property ... [more ▼]

In this paper, we propose related-key differential distinguishers based on the complementation property of Feistel ciphers. We show that with relaxed requirements on the complementation, i.e. the property does not have to hold for all keys and the complementation does not have to be on all bits, one can obtain a variety of distinguishers. We formulate criteria sufficient for attacks based on the complementation property. To stress the importance of our findings we provide analysis of the full-round primitives: Camelia-128 and GOST. [less ▲]

Detailed reference viewed: 167 (0 UL)
Full Text
See detailSecurity Analysis of the Block Cipher SC2000
Biryukov, Alex UL; Nikolic, Ivica

Report (2013)

Detailed reference viewed: 88 (2 UL)
Full Text
Peer Reviewed
See detailCryptanalysis of the Full AES Using GPU-Like Special-Purpose Hardware
Biryukov, Alex UL; Groszschädl, Johann UL

in Fundamenta Informaticae (2012), 114(3-4), 221-237

The block cipher Rijndael has undergone more than ten years of extensive cryptanalysis since its submission as a candidate for the Advanced Encryption Standard (AES) in April 1998. To date, most of the ... [more ▼]

The block cipher Rijndael has undergone more than ten years of extensive cryptanalysis since its submission as a candidate for the Advanced Encryption Standard (AES) in April 1998. To date, most of the publicly-known cryptanalytic results are based on reduced-round variants of the AES (respectively Rijndael) algorithm. Among the few exceptions that target the full AES are the Related-Key Cryptanalysis (RKC) introduced at ASIACRYPT 2009 and attacks exploiting Time-Memory-Key (TMK) trade-offs such as demonstrated at SAC 2005. However, all these attacks are generally considered infeasible in practice due to their high complexity (i.e. 2^99.5 AES operations for RKC, 2^80 for TMK). In this paper, we evaluate the cost of cryptanalytic attacks on the full AES when using special-purpose hardware in the form of multi-core AES processors that are designed in a similar way as modern Graphics Processing Units (GPUs) such as the NVIDIA GT200b. Using today's VLSI technology would allow for the implementation of a GPU-like processor reaching a throughput of up to 10^12 AES operations per second. An organization able to spend one trillion US$ for designing and building a supercomputer based on such processors could theoretically break the full AES in a time frame of as little as one year when using RKC, or in merely one month when performing a TMK attack. We also analyze different time-cost trade-offs and assess the implications of progress in VLSI technology under the assumption that Moore's law will continue to hold for the next ten years. These assessments raise some concerns about the long-term security of the AES. [less ▲]

Detailed reference viewed: 181 (6 UL)
Full Text
Peer Reviewed
See detailCryptanalysis of the "Kindle" Cipher
Biryukov, Alex UL; Leurent, Gaëtan UL; Roy, Arnab UL

in Selected Areas in Cryptography (2012)

In this paper we study a 128-bit-key cipher called PC1 which is used as part of the DRM system of the Amazon Kindle e-book reader. This is the first academic cryptanalysis of this cipher and it shows that ... [more ▼]

In this paper we study a 128-bit-key cipher called PC1 which is used as part of the DRM system of the Amazon Kindle e-book reader. This is the first academic cryptanalysis of this cipher and it shows that PC1 is a very weak stream cipher, and can be practically broken in a known-plaintext and even in a ciphertext-only scenario. A hash function based on this cipher has also been proposed and is implemented in the binary editor WinHex. We show that this hash function is also vulnerable to a practical attack, which can produce meaningful collisions or second pre-images. [less ▲]

Detailed reference viewed: 284 (8 UL)
Full Text
Peer Reviewed
See detailCryptanalysis of the Loiss Stream Cipher
Biryukov, Alex UL; Kircanski, Aleksandar; Youssef, Amr M.

in Selected Areas in Cryptography (2012)

Loiss is a byte-oriented stream cipher designed by Dengguo Feng et al. Its design builds upon the design of the SNOW family of ciphers. The algorithm consists of a linear feedback shift register (LFSR ... [more ▼]

Loiss is a byte-oriented stream cipher designed by Dengguo Feng et al. Its design builds upon the design of the SNOW family of ciphers. The algorithm consists of a linear feedback shift register (LFSR) and a non-linear finite state machine (FSM). Loiss utilizes a structure called Byte-Oriented Mixer with Memory (BOMM) in its filter generator, which aims to improve resistance against algebraic attacks, linear distinguishing attacks and fast correlation attacks. In this paper, by exploiting some differential properties of the BOMM structure during the cipher initialization phase, we provide an attack of a practical complexity on Loiss in the related-key model. As confirmed by our experimental results, our attack recovers 92 bits of the 128-bit key in less than one hour on a PC with 3 GHz Intel Pentium 4 processor. The possibility of extending the attack to a resynchronization attack in a single-key model is discussed. We also show that Loiss is not resistant to slide attacks. [less ▲]

Detailed reference viewed: 151 (1 UL)