References of "Biryukov, Alex 50000799"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailTorScan: Deanonymizing Connections Using Topology Leaks
Biryukov, Alex UL; Pustogarov, Ivan UL; Weinmann, Ralf-Philipp UL

in ERCIM News (2012), (90), 29-29

Tor is one of the most widely used tools for providing anonymity on the Internet. We have devised novel attacks against the Tor network that can compromise the anonymity of users accessing services that ... [more ▼]

Tor is one of the most widely used tools for providing anonymity on the Internet. We have devised novel attacks against the Tor network that can compromise the anonymity of users accessing services that exhibit frequent and predictable communication patterns and users establishing long-lived connections. [less ▲]

Detailed reference viewed: 201 (8 UL)
Full Text
Peer Reviewed
See detailTorScan: Tracing Long-Lived Connections and Differential Scanning Attacks
Biryukov, Alex UL; Pustogarov, Ivan UL; Weinmann, Ralf-Philipp UL

in Computer Security - ESORICS 2012 - 17th European Symposium on Research in Computer Security (2012)

Tor is a widely used anonymity network providing low-latency communication capabilities. The anonymity provided by Tor heavily relies on the hardness of linking a user’s entry and exit nodes. If an ... [more ▼]

Tor is a widely used anonymity network providing low-latency communication capabilities. The anonymity provided by Tor heavily relies on the hardness of linking a user’s entry and exit nodes. If an attacker gains access to the topological information about the Tor network instead of having to consider the network as a fully connected graph, this anonymity may be reduced. In fact, we have found ways to probe the connectivity of a Tor relay. We demonstrate how the resulting leakage of the Tor network topology can be used in attacks which trace back a user from an exit relay to a small set of potential entry nodes. [less ▲]

Detailed reference viewed: 163 (4 UL)
Full Text
See detailSelected Areas in Cryptography 7th International Workshop, SAC 2010, Revised Selected Papers
Gong, Guang; Stinson, Douglas; Biryukov, Alex UL

Book published by Springer (2011)

Detailed reference viewed: 80 (1 UL)
Full Text
Peer Reviewed
See detailSecond-Order Differential Collisions for Reduced SHA-256.
Biryukov, Alex UL; Lamberger, Mario; Mendel, Florian et al

in 17th International Conference on the Theory and Application of Cryptology and Information Security (2011)

In this work, we introduce a new non-random property for hash/compression functions using the theory of higher order differentials. Based on this, we show a second-order differential collision for the ... [more ▼]

In this work, we introduce a new non-random property for hash/compression functions using the theory of higher order differentials. Based on this, we show a second-order differential collision for the compression function of SHA-256 reduced to 47 out of 64 steps with practical complexity. We have implemented the attack and provide an example. Our results suggest that the security margin of SHA-256 is much lower than the security margin of most of the SHA-3 finalists in this setting. The techniques employed in this attack are based on a rectangle/boomerang approach and cover advanced search algorithms for good characteristics and message modification techniques. Our analysis also exposes flaws in all of the previously published related-key rectangle attacks on the SHACAL-2 block cipher, which is based on SHA-256. We provide valid rectangles for 48 steps of SHACAL-2. [less ▲]

Detailed reference viewed: 145 (1 UL)
Full Text
See detailLinear Cryptanalysis for Block Ciphers
Biryukov, Alex UL; De Cannière, Christophe

in Henk C. A. van Tilborg, Sushil Jajodia (Ed.) Encyclopedia of Cryptography and Security (2011)

Detailed reference viewed: 141 (0 UL)
Full Text
Peer Reviewed
See detailSearch for Related-Key Differential Characteristics in DES-Like Ciphers.
Biryukov, Alex UL; Nikolic, Ivica UL

in Fast Software Encryption - 18th International Workshop (2011)

We present the first automatic search algorithms for the best related-key differential characteristics in DES-like ciphers. We show that instead of brute-forcing the space of all possible differences in ... [more ▼]

We present the first automatic search algorithms for the best related-key differential characteristics in DES-like ciphers. We show that instead of brute-forcing the space of all possible differences in the master key and the plaintext, it is computationally more efficient to try only a reduced set of input-output differences of three consecutive S-box layers. Based on this observation, we propose two search algorithms – the first explores Matsui’s approach, while the second is divide-and-conquer technique. Using our algorithms, we find the probabilities (or the upper bounds on the probabilities) of the best related-key characteristics in DES, DESL, and s^2DES. [less ▲]

Detailed reference viewed: 178 (1 UL)
Full Text
See detailData Encryption Standard (DES)
Biryukov, Alex UL; De Cannière, Christophe

in Henk C. A. van Tilborg, Sushil Jajodia (Ed.) Encyclopedia of Cryptography and Security (2011)

Detailed reference viewed: 149 (3 UL)
Full Text
Peer Reviewed
See detailBoomerang Attacks on BLAKE-32
Biryukov, Alex UL; Nikolic, Ivica UL; Roy, Arnab UL

in Fast Software Encryption - 18th International Workshop (2011)

We present high probability differential trails on 2 and 3 rounds of BLAKE-32. Using the trails we are able to launch boomerang attacks on up to 8 round-reduced keyed permutation of BLAKE-32. Also, we ... [more ▼]

We present high probability differential trails on 2 and 3 rounds of BLAKE-32. Using the trails we are able to launch boomerang attacks on up to 8 round-reduced keyed permutation of BLAKE-32. Also, we show that boomerangs can be used as distinguishers for hash/compression functions and present such distinguishers for the compression function of BLAKE-32 reduced to 7 rounds. Since our distinguishers on up to 6 round-reduced keyed permutation of BLAKE-32 are practical (complexity of only 212 encryptions), we are able to find boomerang quartets on a PC. [less ▲]

Detailed reference viewed: 78 (0 UL)
Full Text
Peer Reviewed
See detailCryptanalysis of the Atmel Cipher in SecureMemory, CryptoMemory and CryptoRF
Biryukov, Alex UL; Kizhvatov, Ilya UL; Zhang, Bin UL

in Applied Cryptography and Network Security - 9th International Conference (2011)

SecureMemory (SM), CryptoMemory (CM) and CryptoRF (CR) are the Atmel chip families with wide applications in practice. They implement a proprietary stream cipher, which we call the Atmel cipher, to ... [more ▼]

SecureMemory (SM), CryptoMemory (CM) and CryptoRF (CR) are the Atmel chip families with wide applications in practice. They implement a proprietary stream cipher, which we call the Atmel cipher, to provide authenticity, confidentiality and integrity. At CCS’2010, it was shown that given 1 keystream frame, the secret key in SM protected by the simple version of the cipher can be recovered in 2^39.4 cipher ticks and if 2640 keystream frames are available, the secret key in CM guarded by the more complex version of the cipher can be restored in 2^58 cipher ticks. In this paper, we show much more efficient and practical attacks on both versions of the Atmel cipher. The idea is to dynamically reconstruct the internal state of the underlying register by exploiting the different diffusion speeds of the different cells. For SM, we can recover the secret key in 2^29.8 cipher ticks given 1 keystream frame; for CM, we can recover the secret key in 2^50 cipher ticks with around 24 frames. Practical implementation of the full attack confirms our results. [less ▲]

Detailed reference viewed: 152 (2 UL)
Full Text
Peer Reviewed
See detailKey Recovery Attacks of Practical Complexity on AES-256 Variants with up to 10 Rounds
Biryukov, Alex UL; Dunkelman, Orr; Keller, Nathan et al

in EUROCRYPT 2010 (2010)

AES is the best known and most widely used block cipher. Its three versions (AES-128, AES-192, and AES-256) differ in their key sizes (128 bits, 192 bits and 256 bits) and in their number of rounds (10 ... [more ▼]

AES is the best known and most widely used block cipher. Its three versions (AES-128, AES-192, and AES-256) differ in their key sizes (128 bits, 192 bits and 256 bits) and in their number of rounds (10, 12, and 14, respectively). While for AES-128, there are no known attacks faster than exhaustive search, AES-192 and AES-256 were recently shown to be breakable by attacks which require 2^176 and 2^99.5 time, respectively. While these complexities are much faster than exhaustive search, they are completely non-practical, and do not seem to pose any real threat to the security of AES-based systems. In this paper we aim to increase our understanding of AES security, and we concentrate on attacks with practical complexity, i.e., attacks that can be experimentally verified. We show attacks on reduced-round variants of AES-256 with up to 10 rounds with complexity which is feasible. One of our attacks uses only two related keys and 239 time to recover the complete 256-bit key of a 9-round version of AES-256 (the best previous attack on this variant required 4 related keys and 2^120 time). Another attack can break a 10-round version of AES-256 in 2^45 time, but it uses a stronger type of related subkey attack (the best previous attack on this variant required 64 related keys and 2^172 time). While the full AES-256 cannot be directly broken by these attacks, the fact that 10 rounds can be broken with such a low complexity raises serious concerns about the remaining safety margin offered by AES-256. [less ▲]

Detailed reference viewed: 215 (2 UL)
Full Text
Peer Reviewed
See detailAnalysis of SNOW 3G XOR Resynchronization Mechanism
Biryukov, Alex UL; Priemuth-Schmid, Deike UL; Zhang, Bin UL

in SECRYPT 2010 (2010)

The stream cipher SNOW 3G designed in 2006 by ETSI/SA-GE is a base algorithm for the second set of 3GPP confidentiality and integrity algorithms. In this paper, we investigate the resynchronization ... [more ▼]

The stream cipher SNOW 3G designed in 2006 by ETSI/SA-GE is a base algorithm for the second set of 3GPP confidentiality and integrity algorithms. In this paper, we investigate the resynchronization security of a close variant of SNOW 3G, in which two modular additions are replaced by xors and which is called SNOW 3G$^{\oplus}$. It is shown that the feedback from the FSM to the LFSR is crucial for security. Given a pair of \textit{known} IVs, the cipher without such a feedback is extremely vulnerable to differential known IV attacks with practical complexities ($2^{57}$ time and $2^{33}$ keystream). With such a feedback, it is shown that $16$ out of $33$ initialization rounds can be broken by a differential \textit{chosen} IV attack. This is the first public evaluation result for this algorithm. [less ▲]

Detailed reference viewed: 111 (2 UL)
Full Text
Peer Reviewed
See detailStructural Cryptanalysis of SASAS
Biryukov, Alex UL; Shamir, Adi

in Journal of Cryptology (2010), 23(4), 505-518

In this paper we consider the security of block ciphers which contain alternate layers of invertible S-boxes and affine mappings (there are many popular cryptosystems which use this structure, including ... [more ▼]

In this paper we consider the security of block ciphers which contain alternate layers of invertible S-boxes and affine mappings (there are many popular cryptosystems which use this structure, including the winner of the AES competition, Rijndael). We show that a five-layer scheme with 128-bit plaintexts and 8-bit S-boxes is surprisingly weak against what we call a multiset attack, even when all the S-boxes and affine mappings are key dependent (and thus completely unknown to the attacker). We tested the multiset attack with an actual implementation, which required just 2^16 chosen plaintexts and a few seconds on a single PC to find the 2^17 bits of information in all the unknown elements of the scheme. [less ▲]

Detailed reference viewed: 179 (3 UL)
Full Text
Peer Reviewed
See detailAutomatic Search for Related-Key Differential Characteristics in Byte-Oriented Block Ciphers: Application to AES, Camellia, Khazad and Others
Biryukov, Alex UL; Nikolic, Ivica UL

in EUROCRYPT (2010)

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 ... [more ▼]

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. [less ▲]

Detailed reference viewed: 221 (1 UL)
Full Text
Peer Reviewed
See detailMultiset Collision Attacks on Reduced-Round SNOW 3G and SNOW 3G (+)
Biryukov, Alex UL; Priemuth-Schmid, Deike UL; Zhang, Bin UL

in ACNS 2010 (2010)

The stream cipher SNOW 3G designed in 2006 by ETSI/SA-GE is a base algorithm for the second set of 3GPP confidentiality and integrity algorithms. In this paper we study the resynchronization mechanism of ... [more ▼]

The stream cipher SNOW 3G designed in 2006 by ETSI/SA-GE is a base algorithm for the second set of 3GPP confidentiality and integrity algorithms. In this paper we study the resynchronization mechanism of SNOW 3G and of a similar cipher SNOW 3G ⊕  using multiset collision attacks. For SNOW 3G we show a simple 13-round multiset distinguisher with complexity of 28 steps. We show full key recovery chosen IV resynchronization attacks for up to 18 out of 33 initialization rounds of SNOW3G ⊕  with a complexity of 257 to generate the data and 253 steps of analysis. [less ▲]

Detailed reference viewed: 151 (3 UL)
Full Text
Peer Reviewed
See detailSpeeding up Collision Search for Byte-Oriented Hash Functions
Khovratovich, Dmitry UL; Biryukov, Alex UL; Nikolic, Ivica UL

in CT-RSA (2009)

We describe a new tool for the search of collisions for hash functions. The tool is applicable when an attack is based on a differential trail, whose probability determines the complexity of the attack ... [more ▼]

We describe a new tool for the search of collisions for hash functions. The tool is applicable when an attack is based on a differential trail, whose probability determines the complexity of the attack. Using the linear algebra methods we show how to organize the search so that many (in some cases — all) trail conditions are always satisfied thus significantly reducing the number of trials and the overall complexity. The method is illustrated with the collision and second preimage attacks on the compression functions based on Rijndael. We show that slow diffusion in the Rijndael (and AES) key schedule allows to run an attack on a version with a 13-round compression function, and the S-boxes do not prevent the attack. We finally propose how to modify the key schedule to resist the attack and provide lower bounds on the complexity of the generic differential attacks for our modification. [less ▲]

Detailed reference viewed: 151 (0 UL)
Full Text
Peer Reviewed
See detailDistinguisher and Related-Key Attack on the Full AES-256
Biryukov, Alex UL; Khovratovich, Dmitry UL; Nikolic, Ivica UL

in Advances in Cryptology - CRYPTO (2009)

In this paper we construct a chosen-key distinguisher and a related-key attack on the full 256-bit key AES. We define a notion of differential q -multicollision and show that for AES-256 q-multicollisions ... [more ▼]

In this paper we construct a chosen-key distinguisher and a related-key attack on the full 256-bit key AES. We define a notion of differential q -multicollision and show that for AES-256 q-multicollisions can be constructed in time q·267 and with negligible memory, while we prove that the same task for an ideal cipher of the same block size would require at least $O(q\cdot 2^{\frac{q-1}{q+1}128})$ time. Using similar approach and with the same complexity we can also construct q-pseudo collisions for AES-256 in Davies-Meyer mode, a scheme which is provably secure in the ideal-cipher model. We have also computed partial q-multicollisions in time q·237 on a PC to verify our results. These results show that AES-256 can not model an ideal cipher in theoretical constructions. Finally we extend our results to find the first publicly known attack on the full 14-round AES-256: a related-key distinguisher which works for one out of every 2^{35} keys with 2^{120} data and time complexity and negligible memory. This distinguisher is translated into a key-recovery attack with total complexity of 2^{131} time and 2^{65} memory. [less ▲]

Detailed reference viewed: 183 (1 UL)
Full Text
Peer Reviewed
See detailCryptanalysis of the LAKE Hash Family
Biryukov, Alex UL; Gauravaram, Praveen; Guo, Jian et al

in Fast Software Encryption (2009)

We analyse the security of the cryptographic hash function LAKE-256 proposed at FSE 2008 by Aumasson, Meier and Phan. By exploiting non-injectivity of some of the building primitives of LAKE, we show ... [more ▼]

We analyse the security of the cryptographic hash function LAKE-256 proposed at FSE 2008 by Aumasson, Meier and Phan. By exploiting non-injectivity of some of the building primitives of LAKE, we show three different collision and near-collision attacks on the compression function. The first attack uses differences in the chaining values and the block counter and finds collisions with complexity 2^{33}. The second attack utilizes differences in the chaining values and salt and yields collisions with complexity 2^{42}. The final attack uses differences only in the chaining values to yield near-collisions with complexity 2^{99}. All our attacks are independent of the number of rounds in the compression function. We illustrate the first two attacks by showing examples of collisions and near-collisions. [less ▲]

Detailed reference viewed: 146 (0 UL)
Full Text
Peer Reviewed
See detailRelated-Key Cryptanalysis of the Full AES-192 and AES-256
Biryukov, Alex UL; Khovratovich, Dmitry UL

in ASIACRYPT 2009 (2009)

In this paper we present two related-key attacks on the full AES. For AES-256 we show the first key recovery attack that works for all the keys and has 2^99.5 time and data complexity, while the recent ... [more ▼]

In this paper we present two related-key attacks on the full AES. For AES-256 we show the first key recovery attack that works for all the keys and has 2^99.5 time and data complexity, while the recent attack by Biryukov-Khovratovich-Nikolic works for a weak key class and has much higher complexity. The second attack is the first cryptanalysis of the full AES-192. Both our attacks are boomerang attacks, which are based on the recent idea of finding local collisions in block ciphers and enhanced with the boomerang switching techniques to gain free rounds in the middle. [less ▲]

Detailed reference viewed: 171 (1 UL)
Peer Reviewed
See detailCollisions for Step-Reduced SHA-256
Nikolic, Ivica UL; Biryukov, Alex UL

in Fast Software Encryption - 15th International Workshop, Revised Selected Papers (2008)

Detailed reference viewed: 110 (0 UL)
Peer Reviewed
See detailSlid Pairs in Salsa20 and Trivium
Priemuth-Schmid, Deike UL; Biryukov, Alex UL

in INDOCRYPT (2008)

Detailed reference viewed: 110 (1 UL)