References of "Nikolic, Ivica 30000497"
     in
Bookmark and Share    
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: 95 (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: 96 (1 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: 52 (0 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: 131 (1 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: 96 (0 UL)
See detailRebound Attack on the Full Lane Compression Function
Matusiewicz, Krystian; Naya-Plasencia, Maria; Nikolic, Ivica UL et al

in Advances in Cryptology - ASIACRYPT 2009 (2009)

In this work, we apply the rebound attack to the AES based SHA-3 candidate Lane. The hash function Lane uses a permutation based compression function, consisting of a linear message expansion and 6 ... [more ▼]

In this work, we apply the rebound attack to the AES based SHA-3 candidate Lane. The hash function Lane uses a permutation based compression function, consisting of a linear message expansion and 6 parallel lanes. In the rebound attack on Lane, we apply several new techniques to construct a collision for the full compression function of Lane-256 and Lane-512. Using a relatively sparse truncated differential path, we are able to solve for a valid message expansion and colliding lanes independently. Additionally, we are able to apply the inbound phase more than once by exploiting the degrees of freedom in the parallel AES states. This allows us to construct semi-free-start collisions for full Lane-256 with 296 compression function evaluations and 2^{88} memory, and for full Lane-512 with 2^{224} compression function evaluations and 2^{128} memory. [less ▲]

Detailed reference viewed: 52 (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: 130 (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: 84 (0 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: 63 (0 UL)