Publications

Here is a full list of my publications:

Bibliographical data is also available from DBLP and from my Google Scholar profile.

Conference papers

[article] [slides]

On the Practical (In-)Security of 64-bit Block Ciphers: Collision Attacks on HTTP over TLS and OpenVPN

Download:

paper slides

Keywords:

OpenVPN, TLS, HTTPS, CBC, collision attack

See also:

SWEET32 attack

Abstract:

While modern block ciphers, such as AES, have a block size of at least 128 bits, there are many 64-bit block ciphers, such as 3DES and Blowfish, that are still widely supported in Internet security protocols such as TLS, SSH, and IPsec. When used in CBC mode, these ciphers are known to be susceptible to collision attacks when they are used to encrypt around 232 blocks of data (the so-called birthday bound). This threat has traditionally been dismissed as impractical since it requires some prior knowledge of the plaintext and even then, it only leaks a few secret bits per gigabyte. Indeed, practical collision attacks have never been demonstrated against any mainstream security protocol, leading to the continued use of 64-bit ciphers on the Internet. In this work, we demonstrate two concrete attacks that exploit collisions on short block ciphers. First, we present an attack on the use of 3DES in HTTPS that can be used to recover a secret session cookie. Second, we show how a similar attack on Blowfish can be used to recover HTTP BasicAuth credentials sent over OpenVPN connections. In our proof-of-concept demos, the attacker needs to capture about 785GB of data, which takes between 19-38 hours in our setting. This complexity is comparable to the recent RC4 attacks on TLS: the only fully implemented attack takes 75 hours. We evaluate the impact of our attacks by measuring the use of 64-bit block ciphers in real-world protocols. We discuss mitigations, such as disabling all 64-bit block ciphers, and report on the response of various software vendors to our responsible disclosure of these attacks.

[article] [slides]

Breaking Symmetric Cryptosystems using Quantum Period Finding

Download:

paper slides

Keywords:

Post-quantum cryptography, symmetric cryptography, quantum attacks, block ciphers, modes of operation, slide attack

Abstract:

Due to Shor's algorithm, quantum computers are a severe threat for public key cryptography. This motivated the cryptographic community to search for quantum-safe solutions. On the other hand, the impact of quantum computing on secret key cryptography is much less understood. In this paper, we consider attacks where an adversary can query an oracle implementing a cryptographic primitive in a quantum superposition of different states. This model gives a lot of power to the adversary, but recent results show that it is nonetheless possible to build secure cryptosystems in it.
We study applications of a quantum procedure called Simon's algorithm (the simplest quantum period finding algorithm) in order to attack symmetric cryptosystems in this model. Following previous works in this direction, we show that several classical attacks based on finding collisions can be dramatically sped up using Simon’s algorithm: finding a collision requires Ω(2n/2) queries in the classical setting, but when collisions happen with some hidden periodicity, they can be found with only O(n) queries in the quantum model.
We obtain attacks with very strong implications. First, we show that the most widely used modes of operation for authentication and authenti- cated encryption (e.g. CBC-MAC, PMAC, GMAC, GCM, and OCB) are completely broken in this security model. Our attacks are also applicable to many CAESAR candidates: CLOC, AEZ, COPA, OTR, POET, OMD, and Minalpher. This is quite surprising compared to the situation with encryption modes: Anand et al. show that standard modes are secure with a quantum-secure PRF.
Second, we show that Simon’s algorithm can also be applied to slide attacks, leading to an exponential speed-up of a classical symmetric cryptanalysis technique in the quantum model.

[article]

Key Recovery Attack against 2.5-round pi-Cipher

Download:

paper

Keywords:

Authenticated encryption, π-Cipher, CAESAR competition, guess and determine, cryptanalysis

Abstract:

In this paper, we propose a guess and determine attack against some variants of the π-Cipher family of authenticated ciphers. This family of ciphers is a second-round candidate of the CAESAR competition. More precisely, we show a key recovery attack with time complexity little higher than 2, and low data complexity, against variants of the cipher with ω-bit words, when the internal permutation is reduced to 2.5 rounds. In particular, this gives an attack with time complexity 272 against the variant π16-Cipher096 (using 16-bit words) reduced to 2.5 rounds, while the authors claim 96 bits of security with 3 rounds in their second-round submission. Therefore, the security margin for this variant of π-Cipher is very limited. The attack can also be applied to lightweight variants that are not included in the CAESAR proposal, and use only two rounds. The lightweight variants π16-Cipher096 and π16-Cipher128 claim 96 bits and 128 bits of security respectively, but our attack can break the full 2 rounds with complexity 272. Finally, the attack can be applied to reduced versions of two more variants of π-Cipher that were proposed in the first-round submission with 4 rounds: π16-Cipher128 (using 16-bit words) and π32-Cipher256 (using 32-bit words). The attack on 2.5 rounds has complexity 272 and 2137 respectively, while the security claim for 4 rounds are 128 bits and 256 bits of security.

[article] [slides]

Improved Differential-Linear Cryptanalysis of 7-round Chaskey with Partitioning

Download:

paper slides

Keywords:

Differential cryptanalysis, linear cryptanalysis, ARX, addition, partitioning, Chaskey, FEAL

Abstract:

In this work we study the security of Chaskey, a recent lightweight MAC designed by Mouha et al., currently being considered for standardisation by ISO/IEC and ITU-T. Chaskey uses an ARX structure very similar to SipHash. We present the first cryptanalysis of Chaskey in the single user setting, with a differential-linear attack against 6 and 7 rounds, hinting that the full version of Chaskey with 8 rounds has a rather small security margin. In response to these attacks, a 12-round version has been proposed by the designers.
To improve the complexity of the differential-linear cryptanalysis, we refine a partitioning technique recently proposed by Biham and Carmeli to improve the linear cryptanalysis of addition operations. We also propose an analogue improvement of differential cryptanalysis of addition operations. Roughly speaking, these techniques reduce the data complexity of linear and differential attacks, at the cost of more processing time per data. It can be seen as the analogue for ARX ciphers of partial key guess and partial decryption for SBox-based ciphers.
When applied to the differential-linear attack against Chaskey, this partitioning technique greatly reduces the data complexity, and this also results in a reduced time complexity. While a basic differential-linear attack on 7 round takes 278 data and time (respectively 235 for 6 rounds), the improved attack requires only 248 data and 267 time (respectively 225 data and 229 time for 6 rounds).
We also show an application of the partitioning technique to FEAL-8X, and we hope that this technique will lead to a better understanding of the security of ARX designs.

[article]

Transcript Collision Attacks: Breaking Authentication in TLS, IKE, and SSH

Download:

paper

Keywords:

TLS, IKE, SSH, transcript collision

Abstract:

In response to high-profile attacks that exploit hash function collisions, software vendors have started to phase out the use of MD5 and SHA-1 in third-party digital signature applications such as X.509 certificates. However, weak hash constructions continue to be used in various cryptographic constructions within mainstream protocols such as TLS, IKE, and SSH, because practitioners argue that their use in these protocols relies only on second preimage resistance, and hence is unaffected by collisions. This paper systematically investigates and debunks this argument.
We identify a new class of transcript collision attacks on key exchange protocols that rely on efficient collision-finding algorithms on the underlying hash constructions. We implement and demonstrate concrete credential-forwarding attacks on TLS 1.2 client authentication, TLS 1.3 server authentication, and TLS channel bindings. We describe almost-practical impersonation and downgrade attacks in TLS 1.1, IKEv2 and SSH-2. As far as we know, these are the first collision-based attacks on the cryptographic constructions used in these popular protocols.
Our practical attacks on TLS were responsibly disclosed (under the name SLOTH) and have resulted in security updates to several TLS libraries. Our analysis demonstrates the urgent need for disabling all uses of weak hash functions in mainstream protocols, and our recommendations have been incorporated in the upcoming Token Binding and TLS 1.3 protocols.

[article]

Collision Attacks against CAESAR Candidates -- Forgery and Key-Recovery against AEZ and Marble

Download:

paper

Keywords:

CAESAR competition, authenticated encryption, cryptanalysis, Marble, AEZ, PMAC, forgery, key-recovery

Abstract:

In this paper we study authenticated encryption algorithms inspired by the OCB mode (Offset Codebook). These algorithms use secret offsets (masks derived from a whitening key) to turn a block cipher into a tweakable block cipher, following the XE or XEX construction.
OCB has a security proof up to 2n/2 queries, and a matching forgery attack was described by Ferguson, where the main step of the attack recovers the whitening key. In this work we study recent authenticated encryption algorithms inspired by OCB, such as Marble, AEZ, and COPA. While Ferguson’s attack is not applicable to those algorithms, we show that it is still possible to recover the secret mask with birthday complexity. Recovering the secret mask easily leads to a forgery attack, but it also leads to more devastating attacks, with a key-recovery attack against Marble and AEZ v2 and v3 with birthday complexity.
For Marble, this clearly violates the security claims of full n-bit security. For AEZ, this matches the security proof, but we believe it is nonetheless a quite undesirable property that collision attacks allow to recover the master key, and more robust designs would be desirable.
Our attack against AEZ is generic and independent of the internal permutation (in particular, it still works with the full AES), but the key-recovery is specific to the key derivation used in AEZ v2 and v3. Against Marble, the forgery attack is generic, but the key-recovery exploits the structure of the E permutation (4 AES rounds). In particular, we introduce a novel cryptanalytic method to attack 3 AES rounds followed by 3 inverse AES rounds, which can be of independent interest.

[article]

Cryptanalysis of Feistel Networks with Secret Round Functions

Download:

paper

Keywords:

Cryptanalysis, Feistel network, yoyo, generic attack, guess-and-determine

Abstract:

Generic distinguishers against Feistel Network with up to 5 rounds exist in the regular setting and up to 6 rounds in a multi-key setting. We present new cryptanalyses against Feistel Networks with 5, 6 and 7 rounds which are not simply distinguishers but actually recover completely the unknown Feistel functions.
When an exclusive-or is used to combine the output of the round function with the other branch, we use the so-called yoyo game which we improved using a heuristic based on particular cycle structures. The complexity of a complete recovery is equivalent to O(22n) encryptions where n is the branch size. This attack can be used against 6- and 7-round Feistel Networks in time respectively O(2n2n-1+2n) and O(2n2n+2n). However when modular addition is used, this attack does not work. In this case, we use an optimized guess-and-determine strategy to attack 5 rounds with complexity O(2n23n/4). Our results are, to the best of our knowledge, the first recovery attacks against generic 5-, 6- and 7-round Feistel Networks.

[article] [slides]

Differential Forgery Attack against LAC

Download:

paper slides

Keywords:

Differential cryptanalysis, differentials, characteristics, forgery attack, truncated differential, LBlock, LAC

Abstract:

LAC is one of the candidates to the CAESAR competition. In this paper we present a differential forgery attack on LAC. We study the collection of characteristics following a fixed truncated characteristic, in order to obtain a lower bound on the probability of a differential. We show that some differentials have a probability higher than 2-64, which allows a forgery attack on the full LAC. This work illustrates the difference between the probability of differentials and characteristics, and we describe tools to evaluate the probability of some characteristics.

[article] [slides]

Construction of Lightweight S-Boxes using Feistel and MISTY Structures

Download:

paper slides

Keywords:

S-Box, Feistel network, MISTY network, lightweight block-cipher

Abstract:

The aim of this work is to find large S-Boxes, typically operating on 8 bits, having both good cryptographic properties and a low implementation cost. Such S-Boxes are suitable building-blocks in many lightweight block ciphers since they may achieve a better security level than designs based directly on smaller S-Boxes. We focus on S-Boxes corresponding to three rounds of a balanced Feistel and of a balanced MISTY structure, and generalize the recent results by Li and Wang on the best differential uniformity and linearity offered by such a construction. Most notably, we prove that Feistel networks supersede MISTY networks for the construction of 8-bit permutations. Based on these results, we also provide a particular instantiation of an 8-bit permutation with better properties than the S-Boxes used in several ciphers, including Robin, Fantomas or CRYPTON.

[article] [slides]

The Sum can be Weaker than Each Part

Download:

paper slides

Keywords:

Hash functions, combiners, XOR combiner, preimage attack

Abstract:

In this paper we study the security of summing the outputs of two independent hash functions, in an effort to increase the security of the resulting design, or to hedge against the failure of one of the hash functions. The exclusive-or (XOR) combiner H1(M) ⊕ H2(M) is one of the two most classical combiners, together with the concatenation combiner H1(M) ‖ H2(M). While the security of the concatenation of two hash functions is well understood since Joux's seminal work on multicollisions, the security of the sum of two hash functions has been much less studied.
The XOR combiner is well known as a good PRF and MAC combiner, and is used in practice in TLS versions 1.0 and 1.1. In a hash function setting, Hoch and Shamir have shown that if the compression functions are modeled as random oracles, or even weak random oracles (i.e. they can easily be inverted -- in particular H1 and H2 offer no security), H1 ⊕ H2 is indifferentiable from a random oracle up to the birthday bound.
In this work, we focus on the preimage resistance of the sum of two narrow-pipe n-bit hash functions, following the Merkle-Damgård or HAIFA structure (the internal state size and the output size are both n bits). We show a rather surprising result: the sum of two such hash functions, e.g. SHA-512 ⊕ Whirlpool, can never provide n-bit security for preimage resistance. More precisely, we present a generic preimage attack with a complexity of Õ(25n/6). While it is already known that the XOR combiner is not preserving for preimage resistance (i.e. there might be some instantiations where the hash functions are secure but the sum is not), our result is much stronger: for any narrow-pipe functions, the sum is not preimage resistant.
Besides, we also provide concrete preimage attacks on the XOR combiner (and the concatenation combiner) when one or both of the compression functions are weak; this complements Hoch and Shamir's proof by showing its tightness for preimage resistance.
Of independent interests, one of our main technical contributions is a novel structure to control simultaneously the behavior of independent hash computations which share the same input message. We hope that breaking the pairwise relationship between their internal states will have applications in related settings.

[article]

FPGA implementations of SPRING

Download:

paper

Keywords:

SPRING, PRF, learning with rounding, lattices, PFGA implementation, side-channel security

Abstract:

SPRING is a family of pseudo-random functions that aims to combine the guarantees of security reductions with good performance on a variety of platforms. Preliminary software implementations for small-parameter instantiations of SPRING were proposed at FSE 2014, and have been demonstrated to reach throughputs within small factors of those of AES. In this paper, we complement these results and investigate the hardware design space of these types of primitives.
Our first (pragmatic) contribution is the first FPGA implementation of SPRING in a counter-like mode. We show that the "rounded product" operations in our design can be computed efficiently, reaching throughputs in the hundreds of megabits/second range within only 4% of the resources of a modern (Xilinx Virtex-6) reconfigurable device. Our second (more prospective) contribution is to discuss the properties of SPRING hardware implementations for side-channel resistance. We show that a part of the design can be very efficiently masked (with linear overhead), while another part implies quadratic overhead due to non-linear operations (similarly to what is usually observed, e.g., for block ciphers). Yet, we argue that for this second part of the design, resistance against simple power analysis may be sufficient to obtain concrete implementation security. We suggest ways to reach this goal very efficiently, via shuffling. We believe that such hybrid implementations, where each part of the design is protected with adequate solutions, is a promising topic for further investigation.

[article] [slides]

Improved Generic Attacks Against Hash-based MACs and HAIFA

Download:

paper slides

Keywords:

Hash functions, MAC, HMAC, Merkle-Damgård, HAIFA, state-recovery attack, universal forgery attack, GOST, Streebog, SHA family

Abstract:

The security of HMAC (and more general hash-based MACs) against state-recovery and universal forgery attacks was very recently shown to be suboptimal, following a series of surprising results by Leurent et al. and Peyrin et al. These results have shown that such powerful attacks require much less than 2 computations, contradicting the common belief (where ℓ denotes the internal state size). In this work, we revisit and extend these results, with a focus on properties of concrete hash functions such as a limited message length, and special iteration modes.
We begin by devising the first state-recovery attack on HMAC with a HAIFA hash function (using a block counter in every compression function call), with complexity 24ℓ/5. Then, we describe improved trade-offs between the message length and the complexity of a state-recovery attack on HMAC. Consequently, we obtain improved attacks on several HMAC constructions used in practice, in which the hash functions limit the maximal message length (e.g., SHA-1 and SHA-2). Finally, we present the first universal forgery attacks, which can be applied with short message queries to the MAC oracle. In particular, we devise the first universal forgery attacks applicable to SHA-1 and SHA-2.

[article]

The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function

Download:

paper

Keywords:

Streebog, cryptanalysis, second-preimage attack, diamond structure, expandable message, HAIFA

Abstract:

Abstract. Streebog is a new Russian hash function standard. It follows the HAIFA framework as domain extension algorithm and claims to resist recent generic second-preimage attacks with long messages. However, we demonstrate in this article that the specific instantiation of the HAIFA framework used in Streebog makes it weak against such attacks. More precisely, we observe that Streebog makes a rather poor usage of the HAIFA counter input in the compression function, which allows to construct second-preimages on the full Streebog-512 with a complexity as low as n×2n/2 (namely 2266) compression function evaluations for long messages. This complexity has to be compared with the expected 2512 computations bound that an ideal hash function should provide. Our work is a good example that one must be careful when using a design framework for which not all instances are secure. HAIFA helps designers to build a secure hash function, but one should pay attention to the way the counter is handled inside the compression function.

[article]

Hardware Implementation and Side-Channel Analysis of Lapin

Download:

paper

Keywords:

LPN, Ring-LPN, masking, side-channel analysis

Abstract:

Lapin is a new authentication protocol that has been designed for low-cost implementations. In a work from RFIDsec 2012, Berstein and Lange argued that at similar (mathematical) security levels, Lapin's performances are below the ones of block cipher based authentication. In this paper, we suggest that as soon as physical security (e.g. against side-channel attacks) is taken into account, this criticism can be mitigated. For this purpose, we start by investigating masked hardware implementations of Lapin, and discuss the gains obtained over software ones. Next, we observe that the structure of our implementations significantly differs from block cipher ones (for which most results in side-channel analysis apply), hence raising questions regarding how to evaluate physical security in this case. We then provide first results of side-channel analyzes against unprotected and masked Lapin. Despite interesting properties of the masked implementations, our conclusions are still contrasted because of the on-chip randomness requirements of Lapin protocol. These results give strong incentive to design similar but deterministic protocols, e.g. based on the recently introduced Learning With Rounding assumption.

[article] [slides]

LS-Designs: Bitslice Encryption for Efficient Masked Software Implementations

Download:

paper slides

Keywords:

Masking, Block cipher design, Robin, Fantomas

See also:

CAESAR candidate SCREAM

Abstract:

Side-channel analysis is an important issue for the security of embedded cryptographic devices, and masking is one of the most in- vestigated solutions to mitigate such attacks. In this context, efficient masking has recently been considered as a possible criteria for new block cipher designs. Previous proposals in this direction were applicable to dif- ferent types of masking schemes (e.g. Boolean and polynomial). In this paper, we study possible optimizations when specializing the designs to Boolean masking. For this purpose, we first observe that bitslice ciphers have interesting properties for improving both the efficiency and the reg- ularity of masked software implementations. Next we specify a family of block ciphers (denoted as LS-designs) that can systematically take ad- vantage of bitslicing in a principled manner. Eventually, we evaluate both the security and performance of such designs and two of their instances, confirming excellent properties for physically secure applications.

[article] [slides]

SPRING: Fast Pseudorandom Functions from Rounded Ring Products

Download:

paper slides

Keywords:

Pseudorandom functions, noisy learning problems, learning with rounding, lattices

Abstract:

Recently, Banerjee, Peikert and Rosen (EUROCRYPT 2012) proposed new theoretical pseudorandom function candidates based on "rounded products" in certain polynomial rings, which have rigorously provable security based on worst-case lattice problems. The functions also enjoy algebraic properties that make them highly parallelizable and attractive for modern applications, such as evaluation under homomorphic encryption schemes. However, the parameters required by BPR's security proofs are too large for practical use, and many other practical aspects of the design were left unexplored in that work.
In this work we give two concrete and practically efficient instantiations of the BPR design, which we call SPRING, for "subset-product with rounding over a ring." One instantiation uses a generator matrix of a binary BCH error-correcting code to "determinstically extract" nearly random bits from a (biased) rounded subset-product. The second instantiation eliminates bias by working over suitable moduli and decomposing the computation into "Chinese remainder" components.
We analyze the concrete security of these instantiations, and provide initial software implementations whose throughputs are within small factors (as small as 4.5) of those of AES.

[article] [slides]

New Generic Attacks against Hash-based MACs

Download:

paper slides

Keywords:

NMAC, HMAC, hash function, distinguishing-H, key recovery, GOST

Abstract:

In this paper we study the security of hash-based MAC algorithms (such as HMAC and NMAC) above the birthday bound. Up to the birthday bound, HMAC and NMAC are proven to be secure under reasonable assumptions on the hash function. On the other hand, if an n-bit MAC is built from a hash function with a ℓ-bit state (ℓ ≥ n), there is a well-known existential forgery attack with complexity 2ℓ/2. However, the remaining security after 2ℓ/2 computations is not well understood. In particular it is widely assumed that if the underlying hash function is sound, then a generic universal forgery attack should require 2n computations and some distinguishing (e.g. distinguishing-H but not distinguishing-R) and state-recovery attacks should also require 2 computations (or 2k if k < ℓ).
In this work, we show that above the birthday bound, hash-based MACs offer significantly less security than previously believed. Our main result is a generic distinguishing-H and state-recovery attack against hash-based MACs with a complexity of only Õ(2ℓ/2). In addition, we show a key-recovery attack with complexity Õ(23ℓ/4) against HMAC used with a hash functions with an internal checksum, such as GOST. This surprising result shows that the use of a checksum might actually weaken a hash function when used in a MAC. We stress that our attacks are generic, and they are in fact more efficient than some previous attacks proposed on MACs instanciated with concrete hash functions. We use techniques similar to the cycle-detection technique proposed by Peyrin et al. at Asiacrypt 2012 to attack HMAC in the related-key model. However, our attacks works in the single-key model for both HMAC and NMAC, and without restriction on the key size.

[article] [slides]

Construction of Differential Characteristics in ARX Designs — Application to Skein

Download:

paper slides

Keywords:

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

See also:

ARXtools

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 232 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.

[article] [slides]

Cryptanalysis of WIDEA

Download:

paper slides

Keywords:

Cryptanalysis, block cipher, hash function, truncated differential, IDEA, WIDEA, HIDEA

Abstract:

WIDEA is a family of block ciphers designed by Junod and Macchetti in 2009 as an extension of IDEA to larger block sizes (256 and 512 bits for the main instances WIDEA-4 and WIDEA-8) and key sizes (512 and 1024 bits), with a focus on using them to design a hash function. WIDEA is based on the trusted IDEA design, and was expected to inherit its good security properties. WIDEA-w is composed of w parallel copies of the IDEA block cipher, with an MDS matrix to provide diffusion between them.
In this paper we present low complexity attacks on WIDEA based on truncated differentials. We show a distinguisher for the full WIDEA with complexity only 265, and we use the distinguisher in a key-recovery attack with complexity w·268. We also show a collision attack on WIDEA-8 if it is used to build a hash function using the Merkle-Damgård mode of operation.
The attacks exploit the parallel structure of WIDEA and the limited diffusion between the IDEA instances, using differential trails where the MDS diffusion layer is never active. In addition, we use structures of plaintext to reduce the data complexity.

[article] [slides]

Time-memory Trade-offs for Near-collisions

Download:

paper slides

Keywords:

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

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 2n/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 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 245.4 using 1TB of memory while the best previous algorithm required 252.5 computations.

[article] [slides]

Analysis of Differential Attacks in ARX Constructions

Download:

paper slides

Keywords:

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

See also:

ARXtools

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.

[article] [slides]

Cryptanalysis of the “Kindle” Cipher

Download:

paper slides

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.

[article]

Narrow-Bicliques: Cryptanalysis of Full IDEA

Download:

paper

Keywords:

block ciphers, bicliques, meet-in-the-middle, IDEA, key recovery

Abstract:

Compared to most other symmetric primitives, the block cipher IDEA proved to be resistant to any cryptanalysis attempt since its design more than 20 years ago. Out of its 8.5 rounds, only up to 5 initial rounds or 6 middle rounds could be attacked. In this paper we apply and extend the recently introduced biclique framework to IDEA and improve various key recovery attacks on reduced-round versions. Moreover, for the first time we describe an approach to noticeably speed-up key-recovery for the full 8.5 round IDEA.
On the conceptual side, for the first time we show that the biclique approach to block cipher cryptanalysis can not only be used to obtain results on more rounds, but can also improve time complexities and data complexities. For this we consider e.g. the first 5 rounds of IDEA, and show better time complexities than the many earlier cryptanalysis attempts. All this is achieved by the amplified independent-bicliques technique: the recently introduced independent-biclique approach amplified with ways to use available degrees of freedom as known from hash cryptanalysis. We do not need to assume to know or be able to chose relations between multiple keys. Our cryptanalysis is of high computational complexity, and does not threaten the practical use of IDEA in any way, yet the techniques are practically verified to a large extent.

[article] [slides]

Boomerang Attacks on Hash Function using Auxiliary Differentials

Download:

paper slides

Keywords:

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

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 257, and a distinguisher on the compression function with complexity 2114. 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.

[article] [slides]

Practical Near-Collisions on the Compression Function of BMW

Download:

paper slides

Keywords:

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

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 232 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 255 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 264. 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.

[article] [slides]

Security Analysis of SIMD

Download:

paper slides

Keywords:

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

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.

[article] [slides]

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

Download:

paper slides

Keywords:

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

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₅₁₂.

[article]

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

Download:

paper

Keywords:

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

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.

[article]

Cryptanalysis of ESSENCE

Download:

paper

Keywords:

Cryptanalysis, Hash function, SHA-3, ESSENCE

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.

[article] [slides]

Another Look at the Complementation Property

Download:

paper slides

Keywords:

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

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.

[article] [slides]

Practical Key Recovery Attack against Secret-IV Edon-R

Download:

paper slides

Keywords:

Cryptanalysis, Hash function, Edon-R, MAC

Abstract:

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.

[article]

Practical Electromagnetic Template Attack on HMAC

Download:

paper

Keywords:

Side-channel cryptanalysis, HMAC, SHA-1

Abstract:

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 232 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.

[article]

How Risky is the Random Oracle Model?

Download:

paper

Keywords:

Random Oracle Model (ROM), instantiation, hash function

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.

[article] [slides]

MD4 is not One-Way

Download:

paper slides

Keywords:

Cryptanalysis, Hash function, MD4, preimage

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.

[article] [slides]

Cryptanalysis of a Hash Function Based on Quasi-Cyclic Codes

Download:

paper slides

Keywords:

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

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!

[article] [slides]

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

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.

[article] [slides]

Automatic Search of Differential Path in MD4

Download:

paper slides

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.

[article] [slides]

Message Freedom in MD4 and MD5 Collisions: Application to APOP

Download:

paper slides

Keywords:

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

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.

[article]

An Analysis of the XSL Algorithm

Download:

paper

Keywords:

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

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.

Journal papers

[article] [slides]

Quantum Differential and Linear Cryptanalysis

Download:

paper slides

Keywords:

Symmetric cryptography, Differential cryptanalysis, Linear cryptanalysis, Post-quantum cryptography, Quantum attacks, Block ciphers

Abstract:

Quantum computers, that may become available one day, would impact many scientific fields, most notably cryptography since many asymmetric primitives are insecure against an adversary with quantum capabilities. Cryptographers are already anticipating this threat by proposing and studying a number of potentially quantum-safe alternatives for those primitives. On the other hand, symmetric primitives seem less vulnerable against quantum computing: the main known applicable result is Grover's algorithm that gives a quadratic speed-up for exhaustive search.
In this work, we examine more closely the security of symmetric ciphers against quantum attacks. Since our trust in symmetric ciphers relies mostly on their ability to resist cryptanalysis techniques, we investigate quantum cryptanalysis techniques. More specifically, we consider quantum versions of differential and linear cryptanalysis. We show that it is usually possible to use quantum computations to obtain a quadratic speed-up for these attack techniques, but the situation must be nuanced: we don't get a quadratic speed-up for all variants of the attacks. This allows us to demonstrate the following non-intuitive result: the best attack in the classical world does not necessarily lead to the best quantum one. We give some examples of application on ciphers LAC and KLEIN. We also discuss the important difference between an adversary that can only perform quantum computations, and an adversary that can also make quantum queries to a keyed primitive.

[article]

Improved Generic Attacks Against Hash-based MACs and HAIFA (long version)

Download:

paper

Keywords:

Keywords Hash functions, MAC, HMAC, Merkle-Damgård, HAIFA, state-recovery attack, universal forgery attack, GOST, Streebog, SHA family

Abstract:

The security of HMAC (and more general hash-based MACs) against state-recovery and universal forgery attacks was shown to be suboptimal, following a series of results by Leurent et al. and Peyrin et al. These results have shown that such powerful attacks require significantly less than 2 computations, contradicting the common belief (where ℓ denotes the internal state size). In this work, we revisit and extend these results, with a focus on concrete hash functions that limit the message length, and apply special iteration modes.
We begin by devising the first state-recovery attack on HMAC with a HAIFA hash function (using a block counter in every compression function call), with complexity 24ℓ/5. Then, we describe improved tradeoffs between the message length and the complexity of a state-recovery attack on HMAC with a Merkle-Damgård hash function. Consequently, we obtain improved attacks on several HMAC constructions used in practice, in which the hash functions limits the maximal message length (e.g., SHA-1 and SHA-2). Finally, we present the first universal forgery attacks, which can be applied with short message queries to the MAC oracle. In particular, we devise the first universal forgery attacks applicable to SHA-1 and SHA-2.
Despite their theoretical interest, our attacks do not seem to threaten the practical security of the analyzed concrete HMAC constructions.

[article]

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

Download:

paper

Keywords:

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

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.

Invited talks

Breaking Symmetric Cryptosystems using Quantum Period Finding

Keywords:

Post-quantum cryptography, symmetric cryptography, quantum attacks, block ciphers, modes of operation, slide attack

Abstract:

Due to Shor's algorithm, quantum computers are a severe threat for public key cryptography. This motivated the cryptographic community to search for quantum-safe solutions. On the other hand, the impact of quantum computing on secret key cryptography is much less understood. In this paper, we consider attacks where an adversary can query an oracle implementing a cryptographic primitive in a quantum superposition of different states. This model gives a lot of power to the adversary, but recent results show that it is nonetheless possible to build secure cryptosystems in it.
We study applications of a quantum procedure called Simon's algorithm (the simplest quantum period finding algorithm) in order to attack symmetric cryptosystems in this model. Following previous works in this direction, we show that several classical attacks based on finding collisions can be dramatically sped up using Simon’s algorithm: finding a collision requires Ω(2n/2) queries in the classical setting, but when collisions happen with some hidden periodicity, they can be found with only O(n) queries in the quantum model.
We obtain attacks with very strong implications. First, we show that the most widely used modes of operation for authentication and authenti- cated encryption (e.g. CBC-MAC, PMAC, GMAC, GCM, and OCB) are completely broken in this security model. Our attacks are also applicable to many CAESAR candidates: CLOC, AEZ, COPA, OTR, POET, OMD, and Minalpher. This is quite surprising compared to the situation with encryption modes: Anand et al. show that standard modes are secure with a quantum-secure PRF.
Second, we show that Simon’s algorithm can also be applied to slide attacks, leading to an exponential speed-up of a classical symmetric cryptanalysis technique in the quantum model.

[slides] [abstract]

Generic Attacks against MAC algorithms

Download:

slidesabstract

Keywords:

MAC, Generic Atacks, CBC-MAC, PMAC, HMAC

Abstract:

In this talk we discuss the security of some classical MAC constructions based on block ciphers or hash functions. These construction are widely deployed, and their security has been proven based on idealized behavior of the underlying primitive.
We focus on generic attacks and how the relate to the complexity bounds of the security proof. The two approaches are complementary: generic attacks yields upper bounds on the security of a mode, and security proofs yield a lower bound. While there is usually an attack matching the proof, we point out that this only the case for the strongest security notion, resistance against existential forgery. For weaker security notions, there is usually a gap between the best attacks and the complexity bound of the proof, and the security loss when the bounds are exceeded is not well understood. Actually, constructions with similar security proofs can have very different security levels beyond the bound.
In particular, we will discuss recent attacks against hash-based MACs, showing that state recovery and universal forgery attacks require less than $2^n$ work.

New Generic attacks on Hash-based MACs

Keywords:

NMAC, HMAC, hash function, distinguishing-H, key recovery, GOST

Abstract:

In this talk we study the security of hash-based MAC algorithms (such as HMAC and NMAC) above the birthday bound. Up to the birthday bound, HMAC and NMAC are proven to be secure under reasonable assumptions on the hash function. On the other hand, if an n-bit MAC is built from a hash function with a l-bit state (l > n), there is a well-known existential forgery attack with complexity 2^l/2. However, the remaining security after 2^l/2 computations is not well understood. In particular it is widely assumed that if the underlying hash function is sound, then a generic universal forgery attack should still require 2^n computations and some distinguishing (e.g. distinguishing-H but not distinguishing-R) and state-recovery attacks should still require 2^l computations. In this work, we show that above the birthday bound, hash-based MACs offer significantly less security than previously believed. Our main result is a generic distinguishing-H and state-recovery attack against hash-based MACs with a complexity of only 2^l/2. In addition, we show a key-recovery attack with complexity 2^3l/4 against HMAC used with a hash functions with an internal checksum, such as GOST. This surprising result shows that the use of a checksum might actually weaken a hash function when used in a MAC.

PhD Thesis

[thesis] [slides]

Design and Analysis of Hash Functions

Download:

thesis slides

Keywords:

Symmetric cryptography, Hash functions, design, cryptanalysis

Abstract:

Hash functions are essential primitives in modern cryptography, used in many protocols and standards.
My work has been organized around the SHA-3 competition, launched by NIST to select a new hash function standard. In the first part, I studied the new attacks of Wang et al. against MD4 and MD5. I describe some improvements of these attacks, and new applications to higher-level constructions. In the second part, I describe a new hash function, SIMD, which has been submitted to NIST for the SHA-3 competition. The design of SIMD follows ideas from the MD4 family, but I used my knowledge of this family to make it resistant to most attacks. Finally, in the third part, I describe new attacks against SHA-3 candidates. I give new attacks techniques which are general enough to apply to several hash functions or block ciphers. Thus, this thesis covers the two main realms of symmetric cryptography: design and analysis.