Publications

Download:

paper

Keywords:

GCM-RUP, partial key recovery, universal forgery, birthday bound

To appear

Abstract:

Authenticated encryption (AE) schemes are widely used to secure communications because they can guarantee both confidentiality and authenticity of a message. In addition to the standard AE security notion, some recent schemes offer extra robustness, i.e. they maintain security in some misuse scenarios. In particular, Ashur, Dunkelman and Luykx proposed a generic AE construction at CRYPTO’17 that is secure even when releasing unverified plaintext (the RUP setting), and a concrete instantiation, GCM-RUP. The designers proved that GCM-RUP is secure up to the birthday bound in the nonce-respecting model. In this paper, we perform a birthday-bound universal forgery attack against GCM-RUP, matching the bound of the proof. While there are simple distinguishing attacks with birthday complexity on GCM-RUP, our attack is much stronger: we have a partial key recovery leading to universal forgeries. For reference, the best known universal forgery attack against GCM requires 2^2n/3 operations, and many schemes do not have any known universal forgery attacks faster than 2ⁿ. This suggests that GCM-RUP offers a different security trade-off than GCM: stronger protection in the RUP setting, but more fragile when the data complexity reaches the birthday bound. In order to avoid this attack, we suggest a minor modification of GCM-RUP that seems to offer better robustness at the birthday bound.

Download:

paper

Keywords:

Lightweight cryptography, Micro-controller, MAC, Almost Universal hash functions, Beyond-birthday-bound security

To appear

Abstract:

Lightweight cryptography is a topic of growing importance, with the goal to secure the communication of low-end devices that are not powerful enough to use conventional cryptography. There have been many recent proposals of lightweight block ciphers, but comparatively few results on lightweight Message Authentication Codes (MACs).
Therefore, this paper focuses on lightweight MACs. We review some existing constructions, and revisit the choices made in mainstream MACs with a focus on lightweight cryptography. We consider MACs based on universal hash functions, because they offer information theoretic security, can be implemented efficiently and are widely used in conventional cryptography. However, many constructions used in practice (such as GMAC or Poly1305-AES) follow the Wegman-Carter-Shoup construction, which is only secure up to 2⁶⁴ queries with a 128-bit state.
We point out that there are simple solutions to reach security beyond the birthday bound, and we propose a concrete instantiation, MAC611, reaching 61-bit security with a 61-bit universal hash function. We wrote an optimized implementation on two ARM micro-controllers, and we obtain very good performances on the Cortex-M4, at only 3.7 c/B for long messages, and less than one thousand cycles for short messages.

Download:

paper

Keywords:

Even-Mansour, Cryptanalysis, 3-XOR

DOI:

10.1007/978-3-030-26951-7_8

Abstract:

The iterated Even-Mansour construction is an elegant construction that idealizes block cipher designs such as the AES. In this work we focus on the simplest variant, the 2-round Even-Mansour construction with a single key. This is the most minimal construction that offers security beyond the birthday bound: there is a security proof up to 2^2n/3 evaluations of the underlying permutations and encryption, and the best known attacks have a complexity of roughly 2ⁿ/n operations. We show that attacking this scheme with block size n is related to the 3-XOR problem with element size ℓ=2n, an important algorithmic problem that has been studied since the nineties. In particular the 3-XOR problem is known to require at least 2^ℓ/3 queries, and the best known algorithms require around 2^ℓ/2/ℓ operations: this roughly matches the known bounds for the 2-round Even-Mansour scheme.
Using this link we describe new attacks against the 2-round Even-Mansour scheme. In particular, we obtain the first algorithms where both the data and the memory complexity are significantly lower than 2ⁿ. From a practical standpoint, previous works with a data and/or memory complexity close to 2ⁿ are unlikely to be more efficient than a simple brute-force search over the key. Our best algorithm requires just λn known plaintext/ciphertext pairs, for some constant 0<λ<1, 2ⁿ/λn time, and 2^λn memory. For instance, with n=64 and λ=1/2, the memory requirement is practical, and we gain a factor 32 over brute-force search. We also describe an algorithm with asymptotic complexity O(2ⁿln²n/n²), improving the previous asymptotic complexity of O(2ⁿ/n), using a variant of the 3-SUM algorithm of Baran, Demaine, and Patrascu.

Download:

paper slides

Keywords:

Hash function, Cryptanalysis, Chosen-prefix collision, SHA1, MD5

DOI:

10.1007/978-3-030-17659-4_18

Abstract:

A chosen-prefix collision attack is a stronger variant of a collision attack, where an arbitrary pair of challenge prefixes are turned into a collision. Chosen-prefix collisions are usually significantly harder to produce than (identical-prefix) collisions, but the practical impact of such an attack is much larger. While many cryptographic constructions rely on collision-resistance for their security proofs, collision attacks are hard to turn into a break of concrete protocols, because the adversary has limited control over the colliding messages. On the other hand, chosen-prefix collisions have been shown to threaten certificates (by creating a rogue CA) and many internet protocols (TLS, SSH, IKE).
In this article, we propose new techniques to turn collision attacks into chosen-prefix collision attacks. Our strategy is composed of two phases: first, a birthday search that aims at taking the random chaining variable difference (due to the chosen-prefix model) to a set of pre-defined target differences. Then, using a multi-block approach, carefully analysing the clustering effect, we map this new chaining variable difference to a colliding pair of states using techniques developed for collision attacks.
We apply those techniques to MD5 and SHA1, and obtain improved attacks. In particular, we have a chosen-prefix collision attack against SHA1 with complexity between 2^66.9 and 2^69.4 (depending on assumptions about the cost of finding near-collision blocks), while the best-known attack has complexity 2^77.1. This is within a small factor of the complexity of the classical collision attack on SHA1 (estimated as 2^64.7). This represents yet another warning that industries and users have to move away from using SHA1 as soon as possible.

Download:

paper

Keywords:

MORUS, CAESAR, Authenticated Encryption, Nonce Respecting, Linear Cryptanalysis, Confidentiality

DOI:

10.1007/978-3-030-03329-3_2

Abstract:

MORUS is a high-performance authenticated encryption algorithm submitted to the CAESAR competition, and recently selected as a finalist. There are three versions of MORUS: MORUS-640 with a 128-bit key, and MORUS-1280 with 128-bit or 256-bit keys. For all versions the security claim for confidentiality matches the key size. In this paper, we analyze the components of this algorithm (initialization, state update and tag generation), and report several results.
As our main result, we present a linear correlation in the keystream of full MORUS, which can be used to distinguish its output from random and to recover some plaintext bits in the broadcast setting. For MORUS-1280, the correlation is 2^-76 , which can be exploited after around 2¹⁵² encryptions, less than what would be expected for a 256-bit secure cipher. For MORUS-640, the same attack results in a correlation of 2^-73 , which does not violate the security claims of the cipher.
To identify this correlation, we make use of rotational invariants in MORUS using linear masks that are invariant by word-rotations of the state. This motivates us to introduce single-word versions of MORUS called MiniMORUS, which simplifies the analysis. The attack has been implemented and verified on MiniMORUS, where it yields a correlation of 2^-16.
We also study reduced versions of the initialization and finalization of MORUS, aiming to evaluate the security margin of these components. We show a forgery attack when finalization is reduced from 10 steps to 3, and a key-recovery attack in the nonce-misuse setting when initialization is reduced from 16 steps to 10. These additional results do not threaten the full MORUS, but studying all aspects of the design is useful to understand its strengths and weaknesses.

Download:

paper

Keywords:

Modes of operation, Cryptanalysis, Message Authentication Codes, Beyond-Birthday-Bound security

DOI:

10.1007/978-3-319-96884-1_11

Abstract:

In this work, we study the security of several recent MAC constructions with provable security beyond the birthday bound. We consider block-cipher based constructions with a double-block internal state, such as SUM-ECBC, PMAC+, 3kf9, GCM-SIV2, and some variants (LightMAC+, 1kPMAC+). All these MACs have a security proof up to 2^2n/3 queries, but there are no known attacks with less than 2ⁿ queries.
We describe a new cryptanalysis technique for double-block MACs based on finding quadruples of messages with four pairwise collisions in halves of the state. We show how to detect such quadruples in SUM-ECBC, PMAC+, 3kf9, GCM-SIV2 and their variants with O(2^3n/4) queries, and how to build a forgery attack with the same query complexity. The time complexity of these attacks is above 2ⁿ, but it shows that the schemes do not reach full security in the information theoretic model. Surprisingly, our attack on LightMAC+ also invalidates a recent security proof by Naito.
Moreover, we give a variant of the attack against SUM-ECBC and GCM-SIV2 with time and data complexity Õ(2^6n/7). As far as we know, this is the first attack with complexity below 2ⁿ against a deterministic beyond-birthday-bound secure MAC.
As a side result, we also give a birthday attack against 1kf9, a single-key variant of 3kf9 that was withdrawn due to issues with the proof.

Download:

paper

Keywords:

Modes of operation, CTR, GCM, Poly1305, Cryptanalysis

DOI:

10.1007/978-3-319-78375-8_24

Abstract:

The counter mode (CTR) is a simple, efficient and widely used encryption mode using a block cipher. It comes with a security proof that guarantees no attacks up to the birthday bound (i.e. as long as the number of encrypted blocks σ satisfies σ≪2^n/2, and a matching attack that can distinguish plaintext/ciphertext pairs from random using about 2^n/2 blocks of data.
The main goal of this paper is to study attacks against the counter mode beyond this simple distinguisher. We focus on message recovery attacks, with realistic assumptions about the capabilities of an adversary, and evaluate the full time complexity of the attacks rather than just the query complexity. Our main result is an attack to recover a block of message with complexity Õ(2^n/2). This shows that the actual security of CTR is similar to that of CBC, where collision attacks are well known to reveal information about the message.
To achieve this result, we study a simple algorithmic problem related to the security of the CTR mode: the missing difference problem. We give efficient algorithms for this problem in two practically relevant cases: where the missing difference is known to be in some linear subspace, and when the amount of data is higher than strictly required.
As a further application, we show that the second algorithm can also be used to break some polynomial MACs such as GMAC and Poly1305, with a universal forgery attack with complexity Õ(2^2n/3).

Download:

paper slides

Keywords:

OpenVPN, TLS, HTTPS, CBC, collision attack

See also:

SWEET32 attack

DOI:

10.1145/2976749.2978423

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 2³² 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.

Download:

paper slides

Keywords:

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

DOI:

10.1007/978-3-662-53008-5_8

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 Ω(2^n/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.

Download:

paper

Keywords:

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

DOI:

10.1007/978-3-662-52993-5_27

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^4ω, 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 2⁷² 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 2⁷². 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 2⁷² and 2¹³⁷ respectively, while the security claim for 4 rounds are 128 bits and 256 bits of security.

Download:

paper slides

Keywords:

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

DOI:

10.1007/978-3-662-49890-3_14

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 2⁷⁸ data and time (respectively 2³⁵ for 6 rounds), the improved attack requires only 2⁴⁸ data and 2⁶⁷ time (respectively 2²⁵ data and 2²⁹ 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.

Download:

paper

Keywords:

TLS, IKE, SSH, transcript collision

See also:

SLOTH attack, NDSS Distinguihed paper award

DOI:

10.14722/ndss.2016.23418

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.

Download:

paper

Keywords:

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

DOI:

10.1007/978-3-662-48800-3_21

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 2^n/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.

Download:

paper

Keywords:

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

DOI:

10.1007/978-3-319-31301-6_6

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(2²ⁿ) encryptions where n is the branch size. This attack can be used against 6- and 7-round Feistel Networks in time respectively O(2^n2n-1+2n) and O(2ⁿ²ⁿ⁺²ⁿ). 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(2^n23n/4). Our results are, to the best of our knowledge, the first recovery attacks against generic 5-, 6- and 7-round Feistel Networks.

Download:

paper slides

Keywords:

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

DOI:

10.1007/978-3-319-31301-6_13

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.

Download:

paper slides

Keywords:

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

DOI:

10.1007/978-3-319-31301-6_22

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.

Download:

paper slides

Keywords:

Hash functions, combiners, XOR combiner, preimage attack

DOI:

10.1007/978-3-662-46800-5_14

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 H₁(M) ⊕ H₂(M) is one of the two most classical combiners, together with the concatenation combiner H₁(M) ‖ H₂(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 H₁ and H₂ offer no security), H₁ ⊕ H₂ 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 Õ(2^5n/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.

Download:

paper

Keywords:

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

DOI:

10.1007/978-3-662-44709-3_23

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.

Download:

paper slides

Keywords:

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

DOI:

10.1007/978-3-662-44371-2_9

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 2^4ℓ/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.

Download:

paper

Keywords:

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

DOI:

10.1007/978-3-319-13051-4_12

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×2^n/2 (namely 2²⁶⁶) compression function evaluations for long messages. This complexity has to be compared with the expected 2⁵¹² 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.

Download:

paper

Keywords:

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

DOI:

10.1007/978-3-319-04852-9_11

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.

Download:

paper slides

Keywords:

Masking, Block cipher design, Robin, Fantomas

See also:

CAESAR candidate SCREAM

DOI:

10.1007/978-3-662-46706-0_2

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.

Download:

paper slides

Keywords:

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

DOI:

10.1007/978-3-662-46706-0_3

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.

Download:

paper slides

Keywords:

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

DOI:

10.1007/978-3-642-42045-0_1

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 2ⁿ computations and some distinguishing (e.g. distinguishing-H but not distinguishing-R) and state-recovery attacks should also require 2^ℓ computations (or 2^k 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 Õ(2^3ℓ/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.

Download:

paper slides

Keywords:

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

See also:

ARXtools

DOI:

10.1007/978-3-642-40041-4_14

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.

Download:

paper slides

Keywords:

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

DOI:

10.1007/978-3-662-43933-3_3

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 2⁶⁵, and we use the distinguisher in a key-recovery attack with complexity w·2⁶⁸. 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.

Download:

paper slides

Keywords:

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

DOI:

10.1007/978-3-662-43933-3_11

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

Download:

paper slides

Keywords:

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

See also:

ARXtools

DOI:

10.1007/978-3-642-34961-4_15

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.

Download:

paper slides

Keywords:

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

DOI:

10.1007/978-3-642-35999-6_7

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.

Download:

paper

Keywords:

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

DOI:

10.1007/978-3-642-29011-4_24

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.

Download:

paper slides

Keywords:

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

DOI:

10.1007/978-3-642-27954-6_14

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.

Download:

paper slides

Keywords:

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

DOI:

10.1007/978-3-642-21702-9_14

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.

Download:

paper slides

Keywords:

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

DOI:

10.1007/978-3-642-19574-7_24

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.

Download:

paper slides

Keywords:

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

DOI:

10.1007/978-3-642-19574-7_2

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

Download:

paper

Keywords:

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

DOI:

10.1007/978-3-642-12678-9_25

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.

Download:

paper

Keywords:

Cryptanalysis, Hash function, SHA-3, ESSENCE

DOI:

10.1007/978-3-642-13858-4_8

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.

Download:

paper slides

Keywords:

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

DOI:

10.1007/978-3-642-13858-4_20

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.

Download:

paper slides

Keywords:

Cryptanalysis, Hash function, Edon-R, MAC

DOI:

10.1007/978-3-642-11925-5_23

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.

Download:

paper

Keywords:

Side-channel cryptanalysis, HMAC, SHA-1

DOI:

10.1007/978-3-642-04138-9_6

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

Download:

paper

Keywords:

Random Oracle Model (ROM), instantiation, hash function

DOI:

10.1007/978-3-642-03356-8_26

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.

Download:

paper slides

Keywords:

Cryptanalysis, Hash function, MD4, preimage

DOI:

10.1007/978-3-540-71039-4_26

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.

Download:

paper slides

Keywords:

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

DOI:

10.1007/978-3-540-79263-5_2

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!

Download:

conference paper full paper slides

Keywords:

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

DOI:

10.1007/978-3-540-74143-5_2

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.

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.

Download:

paper slides

Keywords:

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

DOI:

10.1007/978-3-540-74619-5_20

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.

Download:

paper

Keywords:

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

DOI:

10.1007/11593447_18

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.

Download:

paper

Keywords:

Forkciphers, TWEAKEY, ForkAES, ForkSkinny, Cryptanalysis, NIST Lightweight Standardisation

DOI:

10.13154/tosc.v2020.i1.233-265

Abstract:

The forkcipher framework was designed in 2018 by Andreeva et al. for authenticated encryption of short messages. Two dedicated ciphers were proposed in this framework: ForkAES based on the AES (and its tweakable variant Kiasu-BC), and ForkSkinny based on Skinny. The main motivation is that the forked ciphers should keep the same security as the underlying ciphers, but offer better performances thanks to the larger output. Recent cryptanalysis results at ACNS’19 have shown that ForkAES actually offers a reduced security margin compared to the AES with an 8-round attack, and this was taken into account in the design of ForkSkinny.
In this paper, we present new cryptanalysis results on forkciphers. First we improve the previous attack on ForkAES in order to attack the full 10 rounds. This is the first attack challenging the security of full ForkAES. Then we present the first analysis of ForkSkinny, showing that the best attacks on Skinny can be extended to one round for most ForkSkinny variants, and up to three rounds for ForkSkinny-128-256. This allows to evaluate the security degradation between ForkSkinny and the underlying block cipher.
Our analysis shows that all components of a forkcipher must be carefully designed: the attack against ForkAES uses the weak diffusion of the middle rounds in reconstruction queries (going from one ciphertext to the other), but the attack against ForkSkinny uses a weakness of the tweakey schedule in encryption queries (when one branch of the tweakey schedule is skipped).

Download:

paper

Keywords:

Hash function, Generic attack, Hash combiner, XOR combiner, Concatenation combiner, Zipper hash, Hash-Twice, (Second) Preimage attack

DOI:

10.1007/s00145-019-09328-w

Abstract:

Hash combiners are a practical way to make cryptographic hash functions more tolerant to future attacks and compatible with existing infrastructure. A combiner combines two or more hash functions in a way that is hopefully more secure than each of the underlying hash functions, or at least remains secure as long as one of them is secure. Two classical hash combiners are the exclusive-or (XOR) com- biner H1(M)⊕H2(M) and the concatenation combiner H1(M)‖H2(M). Both of them process the same message using the two underlying hash functions in parallel. Apart from parallel combiners, there are also cascade constructions sequentially calling the underlying hash functions to process the message repeatedly, such as Hash-Twice H2(H1(IV,M,M) and the Zipper hash H2(H1(IV,M),M̄), where M̄ is the reverse of the message M. In this work, we study the security of these hash combiners by devising the best-known generic attacks. The results show that the security of most of the combiners is not as high as commonly believed.

Download:

paper

Keywords:

MDS matrix, Lightweight cryptography

DOI:

10.13154/tosc.v2018.i2.48-78

Abstract:

MDS matrices are an important element for the design of block ciphers such as the AES. In recent years, there has been a lot of work on the construction of MDS matrices with a low implementation cost, in the context of lightweight cryptography.
Most of the previous efforts focused on local optimization, constructing MDS matrices with coefficients that can be efficiently computed. In particular, this led to a matrix with a direct xor count of only 106, while a direct implementation of the MixColumn matrix of the AES requires 152 bitwise xors.
More recently, techniques based on global optimization have been introduced, were the implementation can reuse some intermediate variables. In particular, Kranz et al. used optimization tools to a find good implementation from the description of an MDS matrix. They have lowered the cost of implementing the MixColumn matrix to 97 bitwise xors, and proposed a new matrix with only 72 bitwise xors, the lowest cost known so far.
In this work we propose a different approach to global optimization. Instead of looking for an optimized circuit of a given matrix, we run a search through a space of circuits, to find optimal circuits yielding MDS matrices. This results in MDS matrices with an even lower cost, with only 67 bitwise xors.

Download:

paper slides

Keywords:

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

DOI:

10.13154/tosc.v2016.i1.71-94

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.

Download:

paper

Keywords:

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

DOI:

10.1007/s00453-016-0236-6

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 2^4ℓ/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.

Download:

paper

Keywords:

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

DOI:

10.1504/IJACT.2008.017049

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.

Keywords:

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

See also:

Conference program

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 Ω(2^n/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.

Download:

slides abstract

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.

Keywords:

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

See also:

Conference website

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.

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.