Publications

Abstract: Hover to see the abstract. In this work we consider generic algorithms to find near-collisions for a hash function. If we consider only hash computations, it is easy to compute a lower-bound for the complexity of near-collision algorithms, and to build a matching algorithm. However, this algorithm needs a lot of memory, and makes than 2^n/2 memory accesses. Recently, several algorithms have been proposed without this memory requirement; they require more hash evaluations, but the attack is actually more practical. They can be divided in two main categories: some are based on truncation, and some are based on covering codes. In this paper, we give a new insight to the generic complexity of a near-collision attack. First, we consider time-memory trade-offs for truncation-based algorithms. For a practical implementation, it seems reasonable to assume that \emph{some} memory is available and we show that taking advantage of this memory can significantly reduce the complexity. Second, we show a new method combining truncation and covering codes. The new algorithm is always at least as good as the previous works, and often gives a significant improvement. We illustrate our results by giving a 10-near collision for MD5: our algorithm has a complexity of 2^45.4 using 1TB of memory while the best previous algorithm required 2^52.5 computations.

Time-memory Trade-offs for Near-collisions

Conference:

FSE 2013 (©IACR)

Authors:

Gaëtan Leurent

Keywords:

Hash function, near-collision, generic attacks, time-memory trade-off

Download:

Abstract: In this paper, we study differential attacks against ARX schemes. We build upon the generalized characteristics of de Cannière and Rechberger; we introduce new multi-bit constraints to describe differential characteristics in ARX designs more accurately, and quartet constraints to analyze boomerang attacks. We also describe how to propagate those constraints; this can be used either to assist manual construction of a differential characteristic, or to extract more information from an already built characteristic. We show that our new constraints are more precise than what was used in previous works, and can detect more cases of incompatibility.
We have developed a set of tools for this analysis of ARX primitives based on this set of constraints. In the hope that this will be useful to other cryptanalysts, our tools are publicly available.
As a first application, we show that several published attacks are in fact invalid because the differential characteristics cannot be satisfied. This highlights the importance of verifying differential attacks more thoroughly. Hover to see the abstract.

Analysis of Differential Attacks in ARX Constructions

Conference:

Asiacrypt 2012 (©IACR)

Authors:

Gaëtan Leurent

Keywords:

Symmetric ciphers, hash functions, ARX, generalized characteristics, differential attacks, boomerang attacks

Download:

paper (full version), slides

Cryptanalysis of the “Kindle” Cipher

Conference:

SAC 2012

Authors:

Alex Biryukov, Gaëtan Leurent, Arnab Roy

Keywords:

Cryptanalysis, stream cipher, hash function, Pukall Cipher, PC1, PSCHF, MobiPocket, Amazon Kindle, e-book

Abstract: 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. Hover to see the abstract.

Download:

Abstract: In this paper we study boomerang attacks in the chosen-key setting. This is particularly relevant to hash function analysis, since many boomerang attacks have been described against ARX-based designs.
We present a new way to combine message modifications, or auxiliary differentials, with the boomerang attack. We show that under some conditions, we can combine three independent paths instead of two for the classical boomerang attack. Our main result is obtained by applying this technique to round-reduced Skein-256, for which we show a distinguisher on the keyed permutation with complexity only 2⁵⁷, and a distinguisher on the compression function with complexity 2¹¹⁴. We also discuss application of the technique to Skein-512 and show some problems with the paths used in previous boomerang analysis of Skein-512. Hover to see the abstract.

Boomerang Attacks on Hash Function using Auxiliary Differentials

Conference:

CT-RSA 2012

Authors:

Gaëtan Leurent, Arnab Roy

Keywords:

Hash function, SHA-3 competition, chosen-key, Skein, Threefish, boomerang attack, higher order differential, zero-sum

Download:

Abstract: Blue Midnight Wish (BMW) is one of the fastest SHA-3 candidates in the second round of the competition. In this paper we study the compression function of BMW and we obtain practical partial collisions in the case of BMW-256: we show a pair of inputs so that 300 pre-specified bits of the outputs collide (out of 512 bits). Our attack requires about 2³² evaluations of the compression function. The attack can also be considered as a near-collision attack: we give an input pair with only 122 active bits in the output, while generic algorithm would require 2⁵⁵ operations for the same result.
A similar attack can be developed for BMW-512, which will gives message pairs with around 600 colliding bits for a cost of 2⁶⁴. This analysis does not affect the security of the iterated hash function, but it shows that the compression function is far from ideal.
We also describe some tools for the analysis of systems of additions and xors, which are used in our attack, and which can be useful for the analysis of other systems. Hover to see the abstract.

Practical Near-Collisions on the Compression Function of BMW

Conference:

FSE 2011 (©IACR)

Authors:

Gaëtan Leurent, Søren S. Thomsen

Keywords:

Hash function, SHA-3, BMW, ARX, cryptanalysis, partial-collision, near-collision

Download:

Abstract: This paper provides three important contributions to the security analysis of SIMD.
First, we show a new free-start distinguisher based on symmetry relations. It allows to distinguish the compression function of SIMD from a random function with a single evaluation. However, we also show that this property is very hard to exploit to mount any attack on the hash function because of the mode of operation of the compression function. Essentially, if one can build a pair of symmetric states, the symmetry property can only be triggered once.
Then, we show that a class of free-start distinguishers is not a threat to wide-pipe hash functions. In particular, this means that our distinguisher has a minimal impact on the security of the SIMD hash function, and we still have a security proof for the iterated hash function. Intuitively, the reason why this distinguisher does not weaken the function is that getting into a symmetric state is about as hard as finding a preimage.
Finally, we study differential path in SIMD, and give an upper bound on the probability of related key differential paths. Our bound is in the order of 2^-n/2 using very weak assumptions. Resistance to related key attacks is often overlooked, but it is very important for hash function designs. Hover to see the abstract.

Security Analysis of SIMD

Conference:

SAC 2010

Authors:

Charles Bouillaguet, Gaëtan Leurent, Pierre-Alain Fouque

Keywords:

Hash function, SHA-3, SIMD, Distinguisher, Security proof

Download:

Abstract: In this paper we study the strength of two hash functions which are based on Generalized Feistels. We describe a new kind of attack based on a cancellation property in the round function. This new technique allows to efficiently use the degrees of freedom available to attack a hash function. Using the cancellation property, we can avoid the non-linear parts of the round function, at the expense of some freedom degrees.
Our attacks are mostly independent of the round function in use, and can be applied to similar hash functions which share the same structure but have different round functions. We start with a 22-round generic attack on the structure of Lesamnta, and adapt it to the actual round function to attack 24-round Lesamnta (the full function has 32 rounds). We follow with an attack on 9-round SHAvite-3₅₁₂ which also works for the tweaked version of SHAvite-3₅₁₂. Hover to see the abstract.

Attacks on Hash Functions based on Generalized Feistel: Application to Reduced-Round Lesamnta and SHAvite-3₅₁₂

Conference:

SAC 2010

Authors:

Charles Bouillaguet, Orr Dunkelman, Gaëtan Leurent, Pierre-Alain Fouque

Keywords:

Cryptanalysis, Hash function, Generalized Feistel, Cancellation property, SHA-3, Lesamnta, SHAvite-3

Download:

Abstract: In this paper, we analyze the SHAvite-3₅₁₂ hash function, as proposed and tweaked for round 2 of the SHA-3 competition. We present cryptanalytic results on 10 out of 14 rounds of the hash function SHAvite-3₅₁₂, and on the full 14 round compression function of SHAvite-3₅₁₂. We show a second preimage attack on the hash function reduced to 10 rounds with a complexity of 2⁴⁹⁷ compression function evaluations and 2¹⁶ memory. For the full 14-round compression function, we give a chosen counter, chosen salt preimage attack with 2³⁸⁴ compression function evaluations and 2¹²⁸ memory (or complexity 2⁴⁴⁸ without memory), and a collision attack with 2¹⁹² compression function evaluations and 2¹²⁸ memory. Hover to see the abstract.

Cryptanalysis of the 10-Round Hash and Full Compression Function of SHAvite-3₅₁₂

Conference:

Africacrypt 2010

Authors:

Praveen Gauravaram, Gaëtan Leurent, Florian Mendel, María Naya-Plasencia, Thomas Peyrin, Christian Rechberger, Martin Schläffer

Keywords:

Cryptanalysis, Hash function, SHA-3, SHAvite-3

Download:

Abstract: ESSENCE is a hash function submitted to the NIST Hash Competition that stands out as a hardware-friendly and highly parallelizable design. Previous analysis showed some non-randomness in the compression function which could not be extended to an attack on the hash function and ESSENCE remained unbroken. Preliminary analysis in its documentation argues that it resists standard differential cryptanalysis. This paper disproves this claim, showing that advanced techniques can be used to significantly reduce the cost of such attacks: using a manually found differential characteristic and an advanced search algorithm, we obtain collision attacks on the full ESSENCE-256 and ESSENCE-512, with respective complexities 2⁶⁸ and 2¹³⁵. In addition, we show how to use these attacks to forge valid (message, MAC) pairs for HMAC-ESSENCE-256 and HMAC-ESSENCE-512, essentially at the same cost as a collision. Hover to see the abstract.

Cryptanalysis of ESSENCE

Conference:

FSE 2010 (©IACR)

Authors:

María Naya-Plasencia, Andrea Röck, Jean-Philippe Aumasson, Yann Laigle-Chapuy, Gaëtan Leurent, Willi Meier, Thomas Peyrin

Keywords:

Cryptanalysis, Hash function, SHA-3, ESSENCE

Download:

Abstract: In this paper we present a collection of attacks based on generalisations of the complementation property of DES. We find symmetry relations in the key schedule and in the actual rounds, and we use these symmetries to build distinguishers for any number of rounds when the relation is deterministic. This can be seen as a generalisation of the complementation property of DES or of slide/related-key attacks, using different kinds of relations. We further explore these properties, and show that if the relations have easily found fixed points, a new kind of attacks can be applied.
Our main result is a self-similarity property on the SHA-3 candidate Lesamnta, which gives a very surprising result on its compression function. Despite the use of round constants which were designed to thwart any such attack, we show a distinguisher on the full compression function which needs only one query, and works for any number of rounds. We also show how to use this self-similarity property to find collisions on the full compression function of Lesamnta much faster than generic attacks. The main reason for this is the structure found in these round constants, which introduce an interesting and unexpected symmetry relation. This casts some doubt on the use of highly structured constants, as it is the case in many designs, including the AES and several SHA-3 candidates. Our second main contribution is a new related-key differential attack on round-reduced versions of the XTEA block-cipher. We exploit the weakness of the key-schedule to suggest an iterative related-key differential. It can be used to recover the secret key faster than exhaustive search using two related keys on 37 rounds. We then isolate a big class of weak keys for which we can attack 51 rounds out of the cipher’s 64 rounds. We also apply our techniques to ESSENCE and PURE. Hover to see the abstract.

Another Look at the Complementation Property

Conference:

FSE 2010 (© IACR)

Authors:

Charles Bouillaguet, Orr Dunkelman, Pierre-Alain Fouque, Gaëtan Leurent

Keywords:

Cryptanalysis, DES complementation property, Self-similarity, Hash function, SHA-3, Lesamnta, ESSENCE, Block cipher, XTEA, PURE

Download:

Abstract: The SHA-3 competition has been organized by NIST to select a new hashing standard. Edon-R was one of the fastest candidates in the first round of the competition. In this paper we study the security of Edon-R, and we show that using Edon-R as a MAC with the secret- IV or secret-prefix construction is unsafe. We present a practical attack in the case of Edon-R256, which requires 32 queries, 230 computations, negligible memory, and a precomputation of 252 . The main part of our attack can also be adapted to the tweaked Edon-R in the same settings: it does not yield a key-recovery attack, but it allows a selective forgery attack.
This does not directly contradict the security claims of Edon-R or the NIST requirements for SHA-3, since the recommended mode to build a MAC is HMAC. However, we believe that it shows a major weakness in the design. Hover to see the abstract.

Practical Key Recovery Attack against Secret-IV Edon-R

Conference:

CT-RSA 2010

Authors:

Gaëtan Leurent

Keywords:

Cryptanalysis, Hash function, Edon-R, MAC

Download:

Abstract: In this paper, we show a very efficient side channel attack against HMAC. Our attack assumes the presence of a side channel that reveals the Hamming distance of some registers. After a profiling phase in which the adversary has access to a device and can configure it, the attack recovers the secret key by monitoring a single execution of HMAC-SHA1. The secret key can be recovered using a "template attack" with a computation of about 2³² 3^κ compression functions, where κ is the number of 32-bit words of the key. Finally, we show that our attack can also be used to break the secrecy of network protocols usually implemented on embedded devices.
We have performed experiments using a NIOS processor executed on a Field Programmable Gate Array (FPGA) to confirm the leakage model. We hope that our results shed some light on the requirements in term of side channel attack for the future SHA-3 function. Hover to see the abstract.

Practical Electromagnetic Template Attack on HMAC

Conference:

CHESS 2009 (©IACR)

Authors:

Pierre-Alain Fouque, Gaëtan Leurent, Denis Réal, Frédéric Valette

Keywords:

Side-channel cryptanalysis, HMAC, SHA-1

Download:

Abstract: RSA-FDH and many other schemes secure in the Random- Oracle Model (ROM) require a hash function with output size larger than standard sizes. We show that the random-oracle instantiations proposed in the literature for such cases are weaker than a random oracle, including the proposals by Bellare and Rogaway from 1993 and 1996, and the ones implicit in IEEE P1363 and PKCS standards: for instance, we obtain a practical preimage attack on BR93 for 1024-bit digests (with complexity less than 2³⁰). Next, we study the security impact of hash function defects for ROM signatures. As an extreme case, we note that any hash collision would suffice to disclose the master key in the ID-based cryptosystem by Boneh et al. from FOCS ’07, and the secret key in the Rabin-Williams signature for which Bernstein proved tight security at EUROCRYPT ’08. We also remark that collisions can be found as a precomputation for any instantiation of the ROM, and this violates the security definition of the scheme in the standard model. Hence, this gives an example of a natural scheme that is proven secure in the ROM but that in insecure for any instantiation by a single function. Interestingly, for both of these schemes, a slight modification can prevent these attacks, while preserving the ROM security result. We give evidence that in the case of RSA and Rabin/Rabin-Williams, an appropriate PSS padding is more robust than all other paddings known. Hover to see the abstract.

How Risky is the Random Oracle Model?

Conference:

Crypto 2009 (©IACR)

Authors:

Gaëtan Leurent, Phong Nguyen

Keywords:

Random Oracle Model (ROM), instantiation, hash function

Download:

Abstract: MD4 is a hash function introduced by Rivest in 1990. It is still used in some contexts, and the most commonly used hash functions (MD5, SHA-1, SHA-2) are based on the design principles of MD4. MD4 has been extensively studied and very efficient collision attacks are known, but it is still believed to be a one-way function.
In this paper we show a partial pseudo-preimage attack on the compression function of MD4, using some ideas from previous cryptanalysis of MD4. We can choose 64 bits of the output for the cost of 2³² compression function computations (the remaining bits are randomly chosen by the preimage algorithm).
This gives a preimage attack on the compression function of MD4 with complexity 2⁹⁶, and we extend it to an attack on the full MD4 with complexity 2¹⁰². As far as we know this is the first preimage attack on a member of the MD4 family. Hover to see the abstract.

MD4 is not One-Way

Conference:

FSE 2008 (©IACR)

Authors:

Gaëtan Leurent

Keywords:

Cryptanalysis, Hash function, MD4, preimage

Download:

Abstract: At the ECRYPT Hash Workshop 2007, Finiasz, Gaborit, and Sendrier pro- posed an improved version of a previous provably secure syndrome-based hash function. The main innovation of the new design is the use of a quasi-cyclic code in order to have a shorter description and to lower the memory usage.
In this paper, we look at the security implications of using a quasi-cyclic code. We show that this very rich structure can be used to build a highly efficient attack: with most parameters, our collision attack is faster than the compression function! Hover to see the abstract.

Cryptanalysis of a Hash Function Based on Quasi-Cyclic Codes

Conference:

CT-RSA 2008

Authors:

Pierre-Alain Fouque, Gaëtan Leurent

Keywords:

Cryptanalysis, Hash function, Fast Syndrome Based (FSB), IFSB

Download:

paper, slides

Full Key-Recovery Attacks on HMAC/NMAC-MD4 and NMAC-MD5

Conference:

Crypto 2007 (©IACR)

Authors:

Pierre-Alain Fouque, Gaëtan Leurent, Phong Nguyen

Keywords:

Cryptanalysis, Hash function, HMAC, MAC, MD4, MD5

Abstract: At Crypto ’06, Bellare presented new security proofs for HMAC and NMAC, under the assumption that the underlying compression function is a pseudo-random function family. Conversely, at Asiacrypt ’06, Contini and Yin used collision techniques to obtain forgery and partial key-recovery attacks on HMAC and NMAC instantiated with MD4, MD5, SHA-0 and reduced SHA-1. In this paper, we present the first full key-recovery attacks on NMAC and HMAC instantiated with a real-life hash function, namely MD4. Our main result is an attack on HMAC/NMAC-MD4 which recovers the full MAC secret key after roughly 2⁸⁸ MAC queries and 2⁹⁵ MD4 computations. We also extend the partial key-recovery Contini-Yin attack on NMAC-MD5 (in the related- key setting) to a full key-recovery attack. The attacks are based on generalizations of collision attacks to recover a secret IV, using new differential paths for MD4. Hover to see the abstract.

Download:

conference paper, full version, slides

Automatic Search of Differential Path in MD4

Conference:

ECRYPT Hash Workshop 2007

Authors:

Pierre-Alain Fouque, Gaëtan Leurent, Phong Nguyen

Keywords:

Cryptanalysis, Hash function, MD4, Differential paths

Abstract: In 2004, Wang et al. obtained breakthrough collision attacks on the main hash functions from the MD4 family. The attacks are differential attacks in which one closely follows the inner steps of the underlying compression function, based on a so-called differential path. It is generally assumed that such differential paths were found “by hand”. In this paper, we present an algorithm which automatically finds suitable differential paths, in the case of MD4. As a first application, we obtain new differential paths for MD4, which improve upon previously known MD4 differential paths. This algorithm could be used to find new differential paths, and to build new attacks against MD4. Hover to see the abstract.

Download:

Abstract: In Wang’s attack, message modifications allow to deterministically satisfy certain sufficient conditions to find collisions efficiently. Unfortunately, message modifications significantly change the messages and one has little control over the colliding blocks. In this paper, we show how to choose some part of the messages which collide. Consequently, we break a security countermeasure proposed by Szydlo and Yin at CT-RSA ’06, where they added a fixed padding at the end of each block.
Furthermore, we also apply this technique to partially recover the passwords in the Authentication Protocol of the Post Office Protocol (POP). This shows that collision attacks can be used to attack real protocols, which means that finding collisions is a real threat. Hover to see the abstract.

Message Freedom in MD4 and MD5 Collisions: Application to APOP

Conference:

FSE 2007 (©IACR)

Authors:

Gaëtan Leurent

Keywords:

Cryptanalysis, Hash function, message modifications, APOP authentication, POP3

Download:

Abstract: The XSL “algorithm” is a method for solving systems of multivariate polynomial equations based on the linearization method. It was proposed in 2002 as a dedicated method for exploiting the structure of some types of block ciphers, for example the AES and Serpent. Since its proposal, the potential for algebraic attacks against the AES has been the source of much speculation. Although it has attracted a lot of attention from the cryptographic community, currently very little is known about the effectiveness of the XSL algorithm. In this paper we present an analysis of the XSL algorithm, by giving a more concise description of the method and studying it from a more systematic point of view. We present strong evidence that, in its current form, the XSL algorithm does not provide an efficient method for solving the AES system of equations. Hover to see the abstract.

An Analysis of the XSL Algorithm

Conference:

Authors:

Carlos Cid, Gaëtan Leurent

Keywords:

Cryptanalysis, AES, Algebraic attacks, XL, XSL, Linearization

Download:

Abstract: Hash functions are used in many cryptographic constructions under various assumptions, and the practical impact of collision attacks is often unclear. In this paper, we show how collisions can be used to recover part of the password used in the APOP authentication protocol.
Since we actually need a little more than mere collisions, we look into the details of MD5 collisions. In Wang’s attack, message modifications allow to deterministically satisfy certain sufficient conditions to find collisions efficiently. Unfortunately, message modifications significantly change the messages and one has little control over the colliding blocks. In this paper, we show how to choose small parts of the colliding messages, which will allow to build the APOP attack.
This shows that collision attacks can be used to attack real protocols, which means that finding collisions is a real threat. Hover to see the abstract.

Journal papers

Practical key-recovery attack against APOP, an MD5 based challenge-response authentication

Journal:

International Journal of Applied Cryptography (IJACT)

Authors:

Gaëtan Leurent

Keywords:

Cryptanalysis, Hash function, message modifications, APOP authentication, POP3

Download:

Abstract: Hover to see the abstract. In this paper, we study differential attacks against ARX schemes. We build upon the generalized characteristics of de Cannière and Rechberger and the multi-bit constraints of Leurent. We describe a more efficient way to propagate multi-bit constraints, that allows us to use the complete set of 2³² 2.5-bit constraints, instead of the reduced sets used by Leurent.
As a result, we are able to build complex non-linear differential characteristics for reduced versions of the hash function Skein. We present several characteristics for use in various attack scenarios; this results in attacks with a relatively low complexity, in relatively strong settings. In particular, we show practical free-start and semi-free-start collision attacks for 20 rounds and 12 rounds of Skein-256, respectively.
To the best of our knowledge, these are the first examples of complex differential trails built for pure ARX designs. We believe this is an important work to assess the security of ARX designs against differential cryptanalysis.

Preprints

Construction of Differential Characteristics in ARX Designs — Application to Skein

Authors:

Gaëtan Leurent

Keywords:

Symmetric ciphers, hash functions, ARX, Skein, generalized characteristics, differential attacks

Download:

SKLOIS, Chinese Academy of Sciences

Seminar talks

Differential Attacks against ARX Designs

Places:

Date:

December 6, 2012

Keywords:

Symmetric ciphers, hash functions, ARX, Skein, generalized characteristics, differential attacks

Abstract: In this talk, we study differential attacks against ARX schemes. We build upon the generalized characteristics of de Cannière and Rechberger; we introduce new multi-bit constraints to describe differential characteristics in ARX designs more accurately, and quartet constraints to analyze boomerang attacks. We describe an efficient way to propagate multi-bit constraints, that allows us to use the complete set of 2^32 2.5-bit constraints.
We have developed a set of tools for this analysis of ARX primitives based on this set of constraints. We show that the new constraints are more precise than what was used in previous works, and can detect several cases of incompatibility. In particular, we show that several published attacks are in fact fact invalid because the differential characteristics cannot be satisfied. This highlights the importance of verifying differential attacks more thoroughly.
Moreover, we are able to build automatically complex non-linear differential characteristics for reduced versions of the hash function Skein. We describe several characteristics for use in various attack scenarios; this results in attacks with a relatively low complexity, in relatively strong settings. In particular, we show practical free-start and semi-free-start collision attacks for 20 rounds and 12 rounds of Skein-256, respectively. To the best of our knowledge, these are the first examples of complex differential trails built for pure ARX designs. Hover to see the abstract.

Download:

University Joseph Fourier, Université Catholique de Louvain, IRMAR

Boomerang Attacks against ARX Hash Functions

Places:

Date:

2012

Keywords:

Symmetric ciphers, hash functions, ARX, generalized characteristics, differential attacks, boomerang attacks

Abstract: In this work we study differential attacks — and in particular boomerang attacks — against ARX-based hash functions such as Blake and Skein. ARX designs are quite popular, but analysis of these schemes is hard because differentials path must be constructed and verified at the bit level.
The first part of the talk will describe an improvement to boomerang attacks when used in the context of hash functions. We present a new way to combine message modifications, or auxiliary differentials, with the boomerang attack. We show that under some conditions, we can combine three independent paths instead of two for the classical boomerang attack. This leads to a semi-practical distinguisher for the compression function of Skein-256 (reduced to 32 rounds), and for the inner permutation of Blake-256 (reduced to 8 rounds).
In the second part of the talk, we study the details of differential paths. We describe some techniques to compute constraints that must be satisfied by the messages and show that many previous results are based on paths that are not satisfiable. For our new attacks, the paths have been verified by building actual messages, since the complexity is low enough. Hover to see the abstract.

Download:

Université de Versailles Saint-Quentin

Analisys of some SHA-3 candidates

Place:

Date:

May 4, 2011

Keywords:

Hash functions, SHA-3, design, analysis

Abstract: Hash functions are essential primitives in modern cryptography, used in many protocols and standards. Due to attacks on most widely used hash functions, the SHA-3 competition was launched by NIST in 2008 to select a new hash function for standardisation. This ongoing effort is focusing the attention of many people in the symmetric crypto community, from designers to cryptanalysts.
In this talk we will describe two recent attacks on second-round SHA-3 candidates. The first attack is based on a cancellation property of some generalized Feistel schemes, and leads to a pseudo-preimage attack on the full compression function of SHAvite3-512. The same ideas can be used to attack reduced versions of Lesamnta, and also to target some generalized Feistel schemes in a block cipher setting. The second attack is a near-collision attack on the full compression function of Blue Midnight Wish (BMW). We describe some tools for the analysis of systems of additions and xors used in the attack, and which can be useful for the analysis of other ARX designs. Hover to see the abstract.

Download:

University of Luxembourg, SnT

A Look at the SHA-3 Competiton: Design and Analysis of Hash Functions

Place:

Date:

January 19, 2010

Keywords:

Hash functions, SHA-3, design, analysis

Abstract: Hash functions are a basic primitive used in many cryptographic protocols. Due to attacks on most widely used hash function, the SHA-3 competition was launched by NIST in 2008 to select a new hash function for standardisation. This ongoing effort is focusing the attention of many people in the symmetric crypto community, from designers to cryptanalysts.
In this talk we will give an overview of hash function design, and present new attack on two SHA-3 candidates, Lesamnta and SHAvite-3. Hover to see the abstract.

Download: