Publications
Here is a full list of my publications:
Bibliographical data is also available from DBLP and from my Google Scholar profile.
Conference papers
![download article [article]](article.png)
Universal Forgery Attack against GCM-RUP
Download:
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 22n/3 operations, and many schemes do not have any known universal forgery attacks faster than 2n. 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 article [article]](article.png)
Lightweight MACs from Universal Hash Functions
Download:
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 264 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 article [article]](article.png)
Low-Memory Attacks against Two-Round Even-Mansour using the 3-XOR Problem
Download:
Keywords:
Even-Mansour, Cryptanalysis, 3-XOR
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
22n/3 evaluations of the underlying permutations and
encryption, and the best known attacks have a complexity of roughly
2n/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
2n. From a practical standpoint, previous works with a
data and/or memory complexity close to 2n 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, 2n/λ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(2nln2n/n2),
improving the previous asymptotic complexity of
O(2n/n), using a variant of the 3-SUM algorithm
of Baran, Demaine, and Patrascu.
![download article [article]](article.png)
![download presentation [slides]](presentation.png)
From Collisions to Chosen-Prefix Collisions — Application to Full SHA-1
Keywords:
Hash function, Cryptanalysis, Chosen-prefix collision, SHA1, MD5
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 266.9 and 269.4 (depending on assumptions
about the cost of finding near-collision blocks), while the best-known
attack has complexity 277.1. This is within a small factor of the
complexity of the classical collision attack on SHA1 (estimated as
264.7). This represents yet another warning that industries and users
have to move away from using SHA1 as soon as possible.
![download article [article]](article.png)
Cryptanalysis of MORUS
Download:
Keywords:
MORUS, CAESAR, Authenticated Encryption, Nonce Respecting, Linear Cryptanalysis, Confidentiality
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 2152 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 article [article]](article.png)
Generic Attacks against Beyond-Birthday-Bound MACs
Download:
Keywords:
Modes of operation, Cryptanalysis, Message Authentication Codes, Beyond-Birthday-Bound security
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 22n/3 queries, but
there are no known attacks with less than 2n 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(23n/4) queries, and how to build a
forgery attack with the same query complexity. The time complexity of
these attacks is above 2n, 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
Õ(26n/7). As far as we know, this is the first
attack with complexity below 2n 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 article [article]](article.png)
The Missing Difference Problem, and its Applications to Counter Mode Encryption
Download:
Keywords:
Modes of operation, CTR, GCM, Poly1305, Cryptanalysis
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
σ≪2n/2, and a matching attack that can distinguish
plaintext/ciphertext pairs from random using about 2n/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
Õ(2n/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
Õ(22n/3).
![download article [article]](article.png)
![download presentation [slides]](presentation.png)
On the Practical (In-)Security of 64-bit Block Ciphers: Collision Attacks on HTTP over TLS and OpenVPN
Keywords:
OpenVPN, TLS, HTTPS, CBC, collision attack
See also:
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.
![download article [article]](article.png)
![download presentation [slides]](presentation.png)
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.
![download article [article]](article.png)
Key Recovery Attack against 2.5-round pi-Cipher
Download:
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 24ω, 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.
![download article [article]](article.png)
![download presentation [slides]](presentation.png)
Improved Differential-Linear Cryptanalysis of 7-round Chaskey with Partitioning
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.
![download article [article]](article.png)
Transcript Collision Attacks: Breaking Authentication in TLS, IKE, and SSH
Download:
Keywords:
TLS, IKE, SSH, transcript collision
See also:
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 article [article]](article.png)
Collision Attacks against CAESAR Candidates — Forgery and Key-Recovery against AEZ and Marble
Download:
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.
![download article [article]](article.png)
Cryptanalysis of Feistel Networks with Secret Round Functions
Download:
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.
![download article [article]](article.png)
![download presentation [slides]](presentation.png)
Differential Forgery Attack against LAC
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.
![download article [article]](article.png)
![download presentation [slides]](presentation.png)
Construction of Lightweight S-Boxes using Feistel and MISTY Structures
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.
![download article [article]](article.png)
![download presentation [slides]](presentation.png)
The Sum can be Weaker than Each Part
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.
![download article [article]](article.png)
FPGA implementations of SPRING
Download:
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.
![download article [article]](article.png)
![download presentation [slides]](presentation.png)
Improved Generic Attacks Against Hash-based MACs and HAIFA
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.
![download article [article]](article.png)
The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function
Download:
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.
![download article [article]](article.png)
Hardware Implementation and Side-Channel Analysis of Lapin
Download:
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.
![download article [article]](article.png)
![download presentation [slides]](presentation.png)
LS-Designs: Bitslice Encryption for Efficient Masked Software Implementations
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.
![download article [article]](article.png)
![download presentation [slides]](presentation.png)
SPRING: Fast Pseudorandom Functions from Rounded Ring Products
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.
![download article [article]](article.png)
![download presentation [slides]](presentation.png)
New Generic Attacks against Hash-based MACs
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.
![download article [article]](article.png)
![download presentation [slides]](presentation.png)
Construction of Differential Characteristics in ARX Designs — Application to Skein
Keywords:
Symmetric ciphers, hash functions, ARX, Skein, generalized characteristics, differential attacks
See also:
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.
![download article [article]](article.png)
![download presentation [slides]](presentation.png)
Cryptanalysis of WIDEA
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.
![download article [article]](article.png)
![download presentation [slides]](presentation.png)
Time-memory Trade-offs for Near-collisions
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.
![download article [article]](article.png)
![download presentation [slides]](presentation.png)
Analysis of Differential Attacks in ARX Constructions
Keywords:
Symmetric ciphers, hash functions, ARX, generalized characteristics, differential attacks, boomerang attacks
See also:
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 article [article]](article.png)
![download presentation [slides]](presentation.png)
Cryptanalysis of the “Kindle” Cipher
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.
![download article [article]](article.png)
Narrow-Bicliques: Cryptanalysis of Full IDEA
Download:
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.
![download article [article]](article.png)
![download presentation [slides]](presentation.png)
Boomerang Attacks on Hash Function using Auxiliary Differentials
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.
![download article [article]](article.png)
![download presentation [slides]](presentation.png)
Practical Near-Collisions on the Compression Function of BMW
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.
![download article [article]](article.png)
![download presentation [slides]](presentation.png)
Security Analysis of SIMD
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.
![download article [article]](article.png)
![download presentation [slides]](presentation.png)
Attacks on Hash Functions based on Generalized Feistel: Application to Reduced-Round Lesamnta and SHAvite-3₅₁₂
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₅₁₂.
![download article [article]](article.png)
Cryptanalysis of the 10-Round Hash and Full Compression Function of SHAvite-3₅₁₂
Download:
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.
![download article [article]](article.png)
Cryptanalysis of ESSENCE
Download:
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.
![download article [article]](article.png)
![download presentation [slides]](presentation.png)
Another Look at the Complementation Property
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.
![download article [article]](article.png)
![download presentation [slides]](presentation.png)
Practical Key Recovery Attack against Secret-IV Edon-R
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.
![download article [article]](article.png)
Practical Electromagnetic Template Attack on HMAC
Download:
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.
![download article [article]](article.png)
How Risky is the Random Oracle Model?
Download:
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.
![download article [article]](article.png)
![download presentation [slides]](presentation.png)
MD4 is not One-Way
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.
![download article [article]](article.png)
![download presentation [slides]](presentation.png)
Cryptanalysis of a Hash Function Based on Quasi-Cyclic Codes
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!
![download article [article]](article.png)
![download presentation [slides]](presentation.png)
Full Key-Recovery Attacks on HMAC/NMAC-MD4 and NMAC-MD5
Download:
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.
![download article [article]](article.png)
![download presentation [slides]](presentation.png)
Automatic Search of Differential Path in MD4
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 article [article]](article.png)
![download presentation [slides]](presentation.png)
Message Freedom in MD4 and MD5 Collisions: Application to APOP
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.
![download article [article]](article.png)
An Analysis of the XSL Algorithm
Download:
Keywords:
Cryptanalysis, AES, Algebraic attacks, XL, XSL, Linearization
DOI:
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
![download article [article]](article.png)
Cryptanalysis of Forkciphers
Download:
Keywords:
Forkciphers, TWEAKEY, ForkAES, ForkSkinny, Cryptanalysis, NIST Lightweight Standardisation
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 article [article]](article.png)
Generic Attacks on Hash Combiners
Download:
Keywords:
Hash function, Generic attack, Hash combiner, XOR combiner, Concatenation combiner, Zipper hash, Hash-Twice, (Second) Preimage attack
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 article [article]](article.png)
MDS Matrices with Lightweight Circuits
Download:
Keywords:
MDS matrix, Lightweight cryptography
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 article [article]](article.png)
![download presentation [slides]](presentation.png)
Quantum Differential and Linear Cryptanalysis
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.
![download article [article]](article.png)
Improved Generic Attacks Against Hash-based MACs and HAIFA (long version)
Download:
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.
![download article [article]](article.png)
Practical key-recovery attack against APOP, an MD5 based challenge-response authentication
Download:
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
See also:
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.
![download presentation [slides]](presentation.png)
![download abstract [abstract]](article.png)
Generic Attacks against MAC algorithms
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
See also:
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.
Seminars and Workshops
- 2018
- Lightweight Crypto Day 2018, Tel Aviv, Isreal
- Flexible Symmetric Cryptography Workshop, Lorentz Center, Leiden, Netherlands
- 2017
- Journées
nationales pre-GDR Sécurité Informatique, Paris,
France
- FOQUS Workshop, Paris, France
- La demi-heure de science, Inria Paris, France
- UVSQ, Versailles, France
- ESC 2017, Canach, Luxembourg
- 2016
- University of Oxford, Mathematical Institute Cryptography Seminar, Oxford, UK
- Dagstuhl Seminar 16021: Symmetric Cryptography, Dagstuhl, Germany
- 2015
- ASK 2015, Singapore
- ESC 2015, Clervaux, Luxembourg
- 2014
- Dagstuhl Seminar 14021: Symmetric Cryptography, Dagstuhl, Germany
- 2013
- Tsinghua University, Institute for Advanced Study Cryptology Seminar, Beijing, China
- ASK 2013, Weihai, China
- Séminaire CCA, Paris, France
- ESC 2013, Mondorf-les-Bains, Luxembourg
- 2012
- SKLOIS, Chinese Academy of Sciences, Beijing, China
- University Joseph Fourier, Grenoble, France
- Université Catholique de Louvain, Louvain-la-Neuve, Belgique
- IRMAR, Rennes, France
- 2011
- UVSQ, Versailles, France
- 2010
- ESC 2010, Remich, Luxembourg
PhD Thesis
![download thesis [thesis]](article.png)
![download presentation [slides]](presentation.png)
Design and Analysis of Hash Functions
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.