<figure><img src="image_1.png" /></figure>

HAL
open science

# Symmetric Cryptanalysis Beyond Primitives

Gaëtan Leurent

► To cite this version:

Gaëtan Leurent. Symmetric Cryptanalysis Beyond Primitives. Cryptography and Security [cs.CR]. Sorbonne Université, 2024. tel-04406617

HAL Id: tel-04406617

https://inria.hal.science/tel-04406617

Submitted on 19 Jan 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
HABILITATION THESIS

# Symmetric Cryptanalysis
Beyond Primitives

Gaëtan Leurent

Defended on January 18, 2024

## Reviewers:

Henri Gilbert ANSSI

Tetsu Iwata Nagoya University

Bart Preneel KU Leuven

## Jury:

Karthikeyan Bhargavan INRIA & Cryspen

Anne Canteaut INRIA

Orr Dunkelman University of Haifa

Henri Gilbert ANSSI

Tetsu Iwata Nagoya University

Antoine Joux CISPA

Gregor Leander Ruhr University Bochum

Bart Preneel KU Leuven

Vincent Rijmen KU Leuven
<figure><img src="image_3.png" /></figure>
À Loreto.
<figure><img src="image_4.png" /></figure>
Acknowledgments

First, I must specially thank Anne, María and Jean-Pierre who pushed me to finally write down this manuscript and defend this habilitation. Without their regular nagging, I wouldn't be writing this acknowledgment and you wouldn't be reading it.

I would like to thank all my coauthors, without whom I wouldn't have obtained all the results presented in this thesis. In particular, I would like to thank the PhD students that I have had the pleasure to supervise: Sébastien, Ferdinand, Clara and Augustin. Working with them has been motivating and encouraging.

I am grateful to Pierre-Alain who took me in as a PhD student, and to Alex and François-Xavier who hosted me as a postdoc, for giving me the taste of research in cryptography, a challenging and fun research topic. Since 2013, I have had the pleasure of working with the SECRET team at INRIA, which become known as COSMIQ in 2020. I would like to thank all past and present members of the team for welcoming me in the group, for the great interactions we've had, and for the wonderful working environment. The team owes a lot to Anne, who lead the group when it was known as SECRET, and to Jean-Pierre as the current leader, but also to all the researchers, post-docs, PhD students and visitors (I will not attempt to list them because I would certainly forget someone). I particularly enjoy the discussions at the coffee break, the daily crosswords and regular occasions to share a drink together. In recent years, the atmosphere at INRIA has become less welcoming to research than it used to be, but the COSMIQ team is still a great place to work, thanks to its members.

Research is a collaborative endeavor, and I'm glad we have a great community in symmetric cryptography, so that it's always fun to meet coauthors and colleagues at conferences, or to spend some time visiting their labs. Within France, we also have regular collaboration with several groups through collaborative projects (in particular the groups in Versailles, Rennes, and Nancy), and this often led to fruitful collaborations; more generally, the C2 community is full of amazing researchers.

Finally, I would like to warmly thank Bart, Henri and Tetsu for their work reviewing my manuscript, and all the members of the jury who make me the honor of being here today: Anne, Antoine, Bart, Gregor, Henri, Karthik, Orr, Tetsu, and Vincent.
<figure><img src="image_5.png" /></figure>
# Contents

<table><tr><td>0 Overview of my Results</td><td>ix</td></tr><tr><td>1 Introduction</td><td>1</td></tr><tr><td>1.1 Symmetric and asymmetric cryptography</td><td>1</td></tr><tr><td>1.2 Evaluating cryptographic schemes</td><td>3</td></tr><tr><td>1.3 Cryptography usage in practice</td><td>3</td></tr><tr><td>1.4 Cryptanalysis beyond primitives</td><td>6</td></tr><tr><td>1.5 Prelude: the birthday bound</td><td>9</td></tr><tr><td>2 Generic Attacks Against Hash Functions and Hash Combiners</td><td>12</td></tr><tr><td>2.1 Generic attacks on hash functions</td><td>13</td></tr><tr><td>2.2 Combiners</td><td>16</td></tr><tr><td>2.3 The interchange structure</td><td>17</td></tr><tr><td>2.4 Preimage attack against the XOR combiner</td><td>18</td></tr><tr><td>2.5 Preimage attack using cycles in the functional graph</td><td>20</td></tr><tr><td>2.6 Improved preimage attack using cycles in the functional graph</td><td>21</td></tr><tr><td>2.7 Conclusion</td><td>22</td></tr><tr><td>3 Chosen-Prefix Collision Attacks</td><td>23</td></tr><tr><td>3.1 From collisions to chosen-prefix collisions</td><td>24</td></tr><tr><td>3.2 Chosen-prefix collision attack against SHA-1</td><td>28</td></tr><tr><td>3.3 Impersonation attack against the PGP Web-of-trust</td><td>30</td></tr><tr><td>3.4 Transcript collision attacks</td><td>32</td></tr><tr><td>3.5 Conclusion</td><td>35</td></tr><tr><td>4 Generic Attacks Against Hash-Based MACs</td><td>37</td></tr><tr><td>4.1 Security of MAC algorithms</td><td>37</td></tr><tr><td>4.2 Hash-based MACs</td><td>38</td></tr><tr><td>4.3 State-recovery attack using cycles</td><td>39</td></tr><tr><td>4.4 State-recovery attack based on chains</td><td>41</td></tr><tr><td>4.5 Key-recovery attack against HMAC-GOST</td><td>43</td></tr><tr><td>4.6 Conclusion</td><td>44</td></tr><tr><td>5 Generic Attacks Against Encryption Modes</td><td>46</td></tr><tr><td>5.1 CBC and CTR</td><td>46</td></tr><tr><td>5.2 Birthday-bound security</td><td>48</td></tr><tr><td>5.3 Plaintext-recovery attack against CBC</td><td>49</td></tr><tr><td>5.4 The missing difference problem</td><td>52</td></tr><tr><td>5.5 Plaintext-recovery attack against CTR</td><td>55</td></tr><tr><td>5.6 Conclusion</td><td>56</td></tr><tr><td>6 Generic Attacks Against Beyond-Birthday-Bound MACs</td><td>57</td></tr></table>
<table><tbody><tr><td>6.1</td><td>Double-block hash-then-sum MACs</td><td>57</td></tr><tr><td>6.2</td><td>Attacking SUM-ECBC</td><td>58</td></tr><tr><td>6.3</td><td>Generalization to double-block hash-then-sum MACs</td><td>61</td></tr><tr><td><b>7</b></td><td><b>Generic Attacks Against MACs in the Quantum Setting</b></td><td><b>62</b></td></tr><tr><td>7.1</td><td>Quantum security models</td><td>62</td></tr><tr><td>7.2</td><td>Simon's algorithm</td><td>63</td></tr><tr><td>7.3</td><td>Breaking CBC-MAC</td><td>64</td></tr><tr><td>7.4</td><td>Breaking PMAC</td><td>65</td></tr><tr><td>7.5</td><td>Breaking GMAC</td><td>66</td></tr><tr><td>7.6</td><td>Breaking OCB3</td><td>67</td></tr><tr><td>7.7</td><td>Conclusion</td><td>68</td></tr><tr><td colspan="2"><b>Bibliography</b></td><td><b>70</b></td></tr><tr><td colspan="2"><b>Selected Publications</b></td><td><b>87</b></td></tr><tr><td>A</td><td>The Sum Can Be Weaker Than Each Part</td><td>88</td></tr><tr><td>B</td><td>Generic Attacks on Hash Combiners</td><td>111</td></tr><tr><td>C</td><td>From Collisions to Chosen-Prefix Collisions</td><td>195</td></tr><tr><td>D</td><td>SHA-1 is a Shambles</td><td>225</td></tr><tr><td>E</td><td>Transcript Collision Attacks</td><td>260</td></tr><tr><td>F</td><td>New Generic Attacks against Hash-Based MACs</td><td>277</td></tr><tr><td>G</td><td>Improved Generic Attacks Against Hash-Based MACs and HAIFA</td><td>297</td></tr><tr><td>H</td><td>On the Practical (In-)Security of 64-bit Block Ciphers</td><td>331</td></tr><tr><td>I</td><td>The Missing Difference Problem</td><td>343</td></tr><tr><td>J</td><td>Generic Attacks Against Beyond-Birthday-Bound MACs</td><td>370</td></tr><tr><td>K</td><td>Breaking Symmetric Cryptosystems Using Quantum Period Finding</td><td>400</td></tr><tr><td>L</td><td>Quantum Linearization Attacks</td><td>430</td></tr></tbody></table>
# 0. Overview of my Results

I study the construction and analysis of symmetric cryptography algorithms. Symmetric primitives are mostly standardized through open international competitions, where their security is assessed by public cryptanalysis. I have contributed to several competitions (SHA-3, CAESAR, NIST Lightweight) by designing new primitives, and analyzing the other candidates. I have also applied cryptanalysis techniques beyond primitives, to analyze the security of modes of operations, and to extend cryptanalysis results to practical settings.
I briefly mention my main results below.

**Design of primitives.** I have contributed to the design of several primitives; most of them have been submitted to standardization processes:

* SIMD, a hash function submitted to the SHA-3 competition [LBF08];

* SPRING, a PRF based on a lattice construction [BBL+15];

* SCREAM an authenticated encryption algorithm based on LS-designs submitted to the CAESAR competition [GLS+14];

* Spook an authenticated encryption algorithm based on LS-designs submitted to the NIST lightweight standardization [BBB+20];

* Saturnin [CDL+20] an authenticated encryption algorithm with post-quantum security submitted to the NIST lightweight standardization [BBB+20]; we later proposed a dedicated mode of operation, with post-quantum security: QCB [BBC+21].

I have also proposed constructions for components of symmetric primitives (used in some of the primitives above):

* the LS-design methodology for block ciphers [GLS+15];

* constructions for lightweight 8-bit S-Boxes based on 4-bit S-Boxes [CDL16];

* constructions of lightweight MDS matrices [DL18].

**Cryptanalysis of primitives.** I have obtained important cryptanalysis results on primitives, either in the context of standardization processes, or by evaluating the security of widely used primitives. Some of my main results are:

* the first preimage attack against the full MD4 [Leu08a];

* tools for the analysis of ARX primitives [Leu12; Leu13];

* a differential-linear attack against Chaskey [Leu16b]; the attack breaks 7 rounds and has motivated the authors to increase the number of rounds from 8 to 12;

* an analysis of differential and linear cryptanalysis in the quantum setting [KLL+16b];

* a chosen-prefix collision attack against the full SHA-1 [LP19; LP20];

* a new representation of the AES key-schedule [LP21] (Eurocrypt 2021 best paper award);
* attacks against the full permutation Gimli [FLN+20; FLN+21] (*Asiacrypt 2020 best paper award*);

* attacks against Simon and Simeck [LPS21];

* an analysis of GEA, the encryption algorithm used in GPRS showing an intentional weakness in GEA-1 [BDL+21];

* improvement of boomerang attacks against AES-based primitives [BL23];

* algebraic attacks against arithmetization-oriented primitives [BCD+20; BBL+22; LMP+23]; in particular we solved several challenges from the Ethereum Foundation.<fnref n="1" />

**Generic attacks.** I also use cryptanalysis techniques more originally, in order to devise generic attacks against modes of operations or ideal constructions. Some of the results obtained are quite surprising:

* generic attacks against hash-based MACs [LPW13; DL14; DL16]; surprisingly, we obtain a key-recovery attack when the hash function uses an internal checksum, showing that the checksum makes the hash function *weaker*;

* a preimage attack against the sum of two hash functions, showing that the sum is often *weaker* than the initial functions [LW15];

* generic attack against several MACs with security beyond the birthday bound [LNS18]; this contributed to closing the gap between proofs and attacks, and we have also invalidated a previous proof;

* a generic attack against the CTR mode, showing plaintext recovery with complexity $2^{n/2}$ [LS18];

* forgery attacks with polynomial complexity against MACs in the quantum setting [KLL+16a; BLN+21]; this shows that quantum computing has a strong impact on symmetric cryptography, in addition to asymmetric cryptography.

**Practical impact of cryptanalysis.** Finally, I’m also interested in the practical security impact of cryptanalysis, and I’ve demonstrated several attacks against concrete protocols, using weaknesses of cryptographic algorithms. In particular, I am proud that several of my works have contributed to the deprecation of obsolete standards:

* a password-recovery attack against APOP using MD5 collisions [Leu07] (CVE-2007-1558);

* a demonstration of the well-known collision attack with complexity $2^{n/2}$, showing that it is actually practical against block ciphers with 64-bit blocks, such as 3DES (Sweet32, CVE-2016-2183, CVE-2016-6329);

* the first chosen-prefix collision for SHA-1, using it for impersonation attack against the PGP web-of-trust [LP20] (Shambles, CVE-2019-14855);

* transcript-collision attacks against internet protocols TLS, SSH, and IPsec using chosen-prefix collisions for MD5 and SHA-1 [BL16b] (SLOTH, CVE-2015-7575 – NDSS 2016 distinguished paper award).

**Focus of this thesis.** In this thesis, I will explain cryptanalysis techniques that don’t target directly primitives; instead I will focus on application to modes of operations and ideal constructions, and on leveraging weaknesses of primitives to break concrete protocols.

<footnote n="1">¹https://crypto.ethereum.org/bounties/zk-hash</footnote>
## Journals papers

[Leu08b] G. Leurent. "Practical key-recovery attack against APOP, an MD5-based challenge-response authentication". In: *Int. J. Appl. Cryptogr.* 1.1 (2008), pp. 32–46. DOI: 10.1504/IJACT.2008.017049.

[DL16] I. Dinur and G. Leurent. "Improved Generic Attacks Against Hash-Based MACs and HAIFA". In: *Algorithmica* (2016), pp. 1–35. ISSN: 1432-0541. DOI: 10.1007/s00453-016-0236-6.

[BDG+20] Z. Bao, I. Dinur, J. Guo, G. Leurent, and L. Wang. "Generic Attacks on Hash Combiners". In: *Journal of Cryptology* 33.3 (July 2020), pp. 742–823. DOI: 10.1007/s00145-019-09328-w.

[FLN+21] A. Flórez-Gutiérrez, G. Leurent, M. Naya-Plasencia, L. Perrin, A. Schrottenloher, and F. Sibleyras. "Internal Symmetries and Linear Properties: Full-permutation Distinguishers and Improved Collisions on Gimli". In: *Journal of Cryptology* 34.4 (Oct. 2021), p. 45. DOI: 10.1007/s00145-021-09413-z.

[DEK+22] O. Dunkelman, M. Eichlseder, D. Kales, N. Keller, G. Leurent, and M. Schofnegger. "Practical key recovery attacks on FlexAEAD". In: *Designs, Codes and Cryptography* 90.4 (Apr. 2022), pp. 983–1007. ISSN: 1573-7586. DOI: 10.1007/s10623-022-01023-5.

## Peer-reviewed International Conferences

[CL05] C. Cid and G. Leurent. "An Analysis of the XSL Algorithm". In: *ASI-ACRYPT 2005*. Ed. by B. K. Roy. Vol. 3788. LNCS. Springer, Heidelberg, Dec. 2005, pp. 333–352. DOI: 10.1007/11593447_18.

[FLN07] P.-A. Fouque, G. Leurent, and P. Q. Nguyen. "Full Key-Recovery Attacks on HMAC/NMAC-MD4 and NMAC-MD5". In: *CRYPTO 2007*. Ed. by A. Menezes. Vol. 4622. LNCS. Springer, Heidelberg, Aug. 2007, pp. 13–30. DOI: 10.1007/978-3-540-74143-5_2.

[Leu07] G. Leurent. "Message Freedom in MD4 and MD5 Collisions: Application to APOP". In: *FSE 2007*. Ed. by A. Biryukov. Vol. 4593. LNCS. Springer, Heidelberg, Mar. 2007, pp. 309–328. DOI: 10.1007/978-3-540-74619-5_20.

[FL08] P.-A. Fouque and G. Leurent. "Cryptanalysis of a Hash Function Based on Quasi-cyclic Codes". In: *CT-RSA 2008*. Ed. by T. Malkin. Vol. 4964. LNCS. Springer, Heidelberg, Apr. 2008, pp. 19–35. DOI: 10.1007/978-3-540-79263-5_2.

[Leu08a] G. Leurent. "MD4 is Not One-Way". In: *FSE 2008*. Ed. by K. Nyberg. Vol. 5086. LNCS. Springer, Heidelberg, Feb. 2008, pp. 412–428. DOI: 10.1007/978-3-540-71039-4_26.

[FLR+09] P.-A. Fouque, G. Leurent, D. Réal, and F. Valette. "Practical Electromagnetic Template Attack on HMAC". In: *CHES 2009*. Ed. by C. Clavier and K. Gaj. Vol. 5747. LNCS. Springer, Heidelberg, Sept. 2009, pp. 66–80. DOI: 10.1007/978-3-642-04138-9_6.

[LN09] G. Leurent and P. Q. Nguyen. "How Risky Is the Random-Oracle Model?". In: *CRYPTO 2009*. Ed. by S. Halevi. Vol. 5677. LNCS. Springer, Heidelberg, Aug. 2009, pp. 445–464. DOI: 10.1007/978-3-642-03356-8_26.

[BDL+10] C. Bouillaguet, O. Dunkelman, G. Leurent, and P.-A. Fouque. "Another Look at Complementation Properties". In: *FSE 2010*. Ed. by S. Hong and T. Iwata. Vol. 6147. LNCS. Springer, Heidelberg, Feb. 2010, pp. 347–364. DOI: 10.1007/978-3-642-13858-4_20.
[GLM+10] P. Gauravaram, G. Leurent, F. Mendel, M. Naya-Plasencia, T. Peyrin, C. Rechberger, and M. Schläffer. "Cryptanalysis of the 10-Round Hash and Full Compression Function of SHAVite-3-512". In: *AFRICACRYPT 10*. Ed. by D. J. Bernstein and T. Lange. Vol. 6055. LNCS. Springer, Heidelberg, May 2010, pp. 419-436. DOI: 10.1007/978-3-642-12678-9_25.

[Leu10] G. Leurent. "Practical Key Recovery Attack against Secret-IV Edon-R". In: *CT-RSA 2010*. Ed. by J. Pieprzyk. Vol. 5985. LNCS. Springer, Heidelberg, Mar. 2010, pp. 334-349. DOI: 10.1007/978-3-642-11925-5_23.

[NRA+10] M. Naya-Plasencia, A. Röck, J.-P. Aumasson, Y. Laigle-Chapuy, G. Leurent, W. Meier, and T. Peyrin. "Cryptanalysis of ESSENCE". In: *FSE 2010*. Ed. by S. Hong and T. Iwata. Vol. 6147. LNCS. Springer, Heidelberg, Feb. 2010, pp. 134-152. DOI: 10.1007/978-3-642-13858-4_8.

[BDL+11] C. Bouillaguet, O. Dunkelman, G. Leurent, and P.-A. Fouque. "Attacks on Hash Functions Based on Generalized Feistel: Application to Reduced-Round Lesamnta and SHAVite-3512". In: *SAC 2010*. Ed. by A. Biryukov, G. Gong, and D. R. Stinson. Vol. 6544. LNCS. Springer, Heidelberg, Aug. 2011, pp. 18-35. DOI: 10.1007/978-3-642-19574-7_2.

[BFL11] C. Bouillaguet, P.-A. Fouque, and G. Leurent. "Security Analysis of SIMD". In: *SAC 2010*. Ed. by A. Biryukov, G. Gong, and D. R. Stinson. Vol. 6544. LNCS. Springer, Heidelberg, Aug. 2011, pp. 351-368. DOI: 10.1007/978-3-642-19574-7_24.

[LT11] G. Leurent and S. S. Thomsen. "Practical Near-Collisions on the Compression Function of BMW". In: *FSE 2011*. Ed. by A. Joux. Vol. 6733. LNCS. Springer, Heidelberg, Feb. 2011, pp. 238-251. DOI: 10.1007/978-3-642-21702-9_14.

[BDF+12] C. Bouillaguet, O. Dunkelman, P.-A. Fouque, and G. Leurent. "New Insights on Impossible Differential Cryptanalysis". In: *SAC 2011*. Ed. by A. Miri and S. Vaudenay. Vol. 7118. LNCS. Springer, Heidelberg, Aug. 2012, pp. 243-259. DOI: 10.1007/978-3-642-28496-0_15.

[KLR12] D. Khovratovich, G. Leurent, and C. Rechberger. "Narrow-Bicliques: Cryptanalysis of Full IDEA". In: *EUROCRYPT 2012*. Ed. by D. Pointcheval and T. Johansson. Vol. 7237. LNCS. Springer, Heidelberg, Apr. 2012, pp. 392-410. DOI: 10.1007/978-3-642-29011-4_24.

[Leu12] G. Leurent. "Analysis of Differential Attacks in ARX Constructions". In: *ASIACRYPT 2012*. Ed. by X. Wang and K. Sako. Vol. 7658. LNCS. Springer, Heidelberg, Dec. 2012, pp. 226-243. DOI: 10.1007/978-3-642-34961-4_15.

[LR12] G. Leurent and A. Roy. "Boomerang Attacks on Hash Function Using Auxiliary Differentials". In: *CT-RSA 2012*. Ed. by O. Dunkelman. Vol. 7178. LNCS. Springer, Heidelberg, Feb. 2012, pp. 215-230. DOI: 10.1007/978-3-642-27954-6_14.

[BLR13] A. Biryukov, G. Leurent, and A. Roy. "Cryptanalysis of the "Kindle" Cipher". In: *SAC 2012*. Ed. by L. R. Knudsen and H. Wu. Vol. 7707. LNCS. Springer, Heidelberg, Aug. 2013, pp. 86-103. DOI: 10.1007/978-3-642-35999-6_7.

[Leu13] G. Leurent. "Construction of Differential Characteristics in ARX Designs Application to Skein". In: *CRYPTO 2013, Part I*. Ed. by R. Canetti and J. A. Garay. Vol. 8042. LNCS. Springer, Heidelberg, Aug. 2013, pp. 241-258. DOI: 10.1007/978-3-642-40041-4_14.
[LPW13] G. Leurent, T. Peyrin, and L. Wang. "New Generic Attacks against Hash-Based MACs". In: *ASIACRYPT 2013, Part II*. Ed. by K. Sako and P. Sarkar. Vol. 8270. LNCS. Springer, Heidelberg, Dec. 2013, pp. 1–20. DOI: 10.1007/978-3-642-42045-0_1.

[BGL+14] H. Brenner, L. Gaspar, G. Leurent, A. Rosen, and F.-X. Standaert. "FPGA Implementations of SPRING - And Their Countermeasures against Side-Channel Attacks". In: *CHES 2014*. Ed. by L. Batina and M. Robshaw. Vol. 8731. LNCS. Springer, Heidelberg, Sept. 2014, pp. 414–432. DOI: 10.1007/978-3-662-44709-3_23.

[DL14] I. Dinur and G. Leurent. "Improved Generic Attacks against Hash-Based MACs and HAIFA". In: *CRYPTO 2014, Part I*. Ed. by J. A. Garay and R. Gennaro. Vol. 8616. LNCS. Springer, Heidelberg, Aug. 2014, pp. 149–168. DOI: 10.1007/978-3-662-44371-2_9.

[GLS14] L. Gaspar, G. Leurent, and F.-X. Standaert. "Hardware Implementation and Side-Channel Analysis of Lapin". In: *CT-RSA 2014*. Ed. by J. Benaloh. Vol. 8366. LNCS. Springer, Heidelberg, Feb. 2014, pp. 206–226. DOI: 10.1007/978-3-319-04852-9_11.

[GJL+14] J. Guo, J. Jean, G. Leurent, T. Peyrin, and L. Wang. "The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function". In: *SAC 2014*. Ed. by A. Joux and A. M. Youssef. Vol. 8781. LNCS. Springer, Heidelberg, Aug. 2014, pp. 195–211. DOI: 10.1007/978-3-319-13051-4_12.

[Leu14a] G. Leurent. "Cryptanalysis of WIDEA". In: *FSE 2013*. Ed. by S. Moriai. Vol. 8424. LNCS. Springer, Heidelberg, Mar. 2014, pp. 39–51. DOI: 10.1007/978-3-662-43933-3_3.

[Leu14b] G. Leurent. "Time-Memory Trade-Offs for Near-Collisions". In: *FSE 2013*. Ed. by S. Moriai. Vol. 8424. LNCS. Springer, Heidelberg, Mar. 2014, pp. 205–218. DOI: 10.1007/978-3-662-43933-3_11.

[BBL+15] A. Banerjee, H. Brenner, G. Leurent, C. Peikert, and A. Rosen. "SPRING: Fast Pseudorandom Functions from Rounded Ring Products". In: *FSE 2014*. Ed. by C. Cid and C. Rechberger. Vol. 8540. LNCS. Springer, Heidelberg, Mar. 2015, pp. 38–57. DOI: 10.1007/978-3-662-46706-0_3.

[FLS15] T. Fuhr, G. Leurent, and V. Suder. "Collision Attacks Against CAESAR Candidates - Forgery and Key-Recovery Against AEZ and Marble". In: *ASIACRYPT 2015, Part II*. Ed. by T. Iwata and J. H. Cheon. Vol. 9453. LNCS. Springer, Heidelberg, Nov. 2015, pp. 510–532. DOI: 10.1007/978-3-662-48800-3_21.

[GLS+15] V. Grosso, G. Leurent, F.-X. Standaert, and K. Varici. "LS-Designs: Bitslice Encryption for Efficient Masked Software Implementations". In: *FSE 2014*. Ed. by C. Cid and C. Rechberger. Vol. 8540. LNCS. Springer, Heidelberg, Mar. 2015, pp. 18–37. DOI: 10.1007/978-3-662-46706-0_2.

[LW15] G. Leurent and L. Wang. "The Sum Can Be Weaker Than Each Part". In: *EUROCRYPT 2015, Part I*. Ed. by E. Oswald and M. Fischlin. Vol. 9056. LNCS. Springer, Heidelberg, Apr. 2015, pp. 345–367. DOI: 10.1007/978-3-662-46800-5_14.

[BL16a] K. Bhargavan and G. Leurent. "On the Practical (In-)Security of 64-bit Block Ciphers: Collision Attacks on HTTP over TLS and OpenVPN". In: *ACM CCS 2016*. Ed. by E. R. Weippl, S. Katzenbeisser, C. Kruegel, A. C. Myers, and S. Halevi. ACM Press, Oct. 2016, pp. 456–467. DOI: 10.1145/2976749.2978423.
[BL16b] K. Bhargavan and G. Leurent. "Transcript Collision Attacks: Breaking Authentication in TLS, IKE and SSH". In: *NDSS 2016*. The Internet Society, Feb. 2016. DOI: 10.14722/ndss.2016.23418.

[BLP16] A. Biryukov, G. Leurent, and L. Perrin. "Cryptanalysis of Feistel Networks with Secret Round Functions". In: *SAC 2015*. Ed. by O. Dunkelman and L. Keliher. Vol. 9566. LNCS. Springer, Heidelberg, Aug. 2016, pp. 102-121. DOI: 10.1007/978-3-319-31301-6_6.

[BCL+16] C. Boura, A. Chakraborti, G. Leurent, G. Paul, D. Saha, H. Soleimany, and V. Suder. "Key Recovery Attack Against 2.5-Round $\pi$-Cipher". In: *FSE 2016*. Ed. by T. Peyrin. Vol. 9783. LNCS. Springer, Heidelberg, Mar. 2016, pp. 535-553. DOI: 10.1007/978-3-662-52993-5_27.

[CDL16] A. Canteaut, S. Duval, and G. Leurent. "Construction of Lightweight S-Boxes Using Feistel and MISTY Structures". In: *SAC 2015*. Ed. by O. Dunkelman and L. Keliher. Vol. 9566. LNCS. Springer, Heidelberg, Aug. 2016, pp. 373-393. DOI: 10.1007/978-3-319-31301-6_22.

[KLL+16a] M. Kaplan, G. Leurent, A. Leverrier, and M. Naya-Plasencia. "Breaking Symmetric Cryptosystems Using Quantum Period Finding". In: *CRYPTO 2016, Part II*. Ed. by M. Robshaw and J. Katz. Vol. 9815. LNCS. Springer, Heidelberg, Aug. 2016, pp. 207-237. DOI: 10.1007/978-3-662-53008-5_8.

[KLL+16b] M. Kaplan, G. Leurent, A. Leverrier, and M. Naya-Plasencia. "Quantum Differential and Linear Cryptanalysis". In: *IACR Trans. Symm. Cryptol.* 2016.1 (2016), pp. 71-94. ISSN: 2519-173X. DOI: 10.13154/tosc.v2016.i1.71-94.

[Leu16a] G. Leurent. "Differential Forgery Attack Against LAC". In: *SAC 2015*. Ed. by O. Dunkelman and L. Keliher. Vol. 9566. LNCS. Springer, Heidelberg, Aug. 2016, pp. 217-224. DOI: 10.1007/978-3-319-31301-6_13.

[Leu16b] G. Leurent. "Improved Differential-Linear Cryptanalysis of 7-Round Chaskey with Partitioning". In: *EUROCRYPT 2016, Part I*. Ed. by M. Fischlin and J.-S. Coron. Vol. 9665. LNCS. Springer, Heidelberg, May 2016, pp. 344-371. DOI: 10.1007/978-3-662-49890-3_14.

[AEL+18] T. Ashur, M. Eichlseder, M. M. Lauridsen, G. Leurent, B. Minaud, Y. Rotella, Y. Sasaki, and B. Viguier. "Cryptanalysis of MORUS". In: *ASI-ACRYPT 2018, Part II*. Ed. by T. Peyrin and S. Galbraith. Vol. 11273. LNCS. Springer, Heidelberg, Dec. 2018, pp. 35-64. DOI: 10.1007/978-3-030-03329-3_2.

[DL18] S. Duval and G. Leurent. "MDS Matrices with Lightweight Circuits". In: *IACR Trans. Symm. Cryptol.* 2018.2 (2018), pp. 48-78. ISSN: 2519-173X. DOI: 10.13154/tosc.v2018.i2.48-78.

[LNS18] G. Leurent, M. Nandi, and F. Sibleyras. "Generic Attacks Against Beyond-Birthday-Bound MACs". In: *CRYPTO 2018, Part I*. Ed. by H. Shacham and A. Boldyreva. Vol. 10991. LNCS. Springer, Heidelberg, Aug. 2018, pp. 306-336. DOI: 10.1007/978-3-319-96884-1_11.

[LS18] G. Leurent and F. Sibleyras. "The Missing Difference Problem, and Its Applications to Counter Mode Encryption". In: *EUROCRYPT 2018, Part II*. Ed. by J. B. Nielsen and V. Rijmen. Vol. 10821. LNCS. Springer, Heidelberg, Apr. 2018, pp. 745-770. DOI: 10.1007/978-3-319-78375-8_24.
[LP19] G. Leurent and T. Peyrin. "From Collisions to Chosen-Prefix Collisions Application to Full SHA-1". In: EUROCRYPT 2019, Part III. Ed. by Y. Ishai and V. Rijmen. Vol. 11478. LNCS. Springer, Heidelberg, May 2019, pp. 527-555. DOI: 10.1007/978-3-030-17659-4_18.

[LS19] G. Leurent and F. Sibleyras. "Low-Memory Attacks Against Two-Round Even-Mansour Using the 3-XOR Problem". In: CRYPTO 2019, Part II. Ed. by A. Boldyreva and D. Micciancio. Vol. 11693. LNCS. Springer, Heidelberg, Aug. 2019, pp. 210-235. DOI: 10.1007/978-3-030-26951-7_8.

[BDL20] A. Bariant, N. David, and G. Leurent. "Cryptanalysis of Forkciphers". In: IACR Trans. Symm. Cryptol. 2020.1 (2020), pp. 233-265. ISSN: 2519-173X. DOI: 10.13154/tosc.v2020.i1.233-265.

[BBB+20] D. Bellizia, F. Berti, O. Bronchain, G. Cassiers, S. Duval, C. Guo, G. Leander, G. Leurent, I. Levi, C. Momin, O. Pereira, T. Peters, F.-X. Standaert, B. Udvarhelyi, and F. Wiemer. "Spook: Sponge-Based Leakage-Resistant Authenticated Encryption with a Masked Tweakable Block Cipher". In: IACR Trans. Symm. Cryptol. 2020.S1 (2020), pp. 295-349. ISSN: 2519-173X. DOI: 10.13154/tosc.v2020.iS1.295-349.

[BCD+20] T. Beyne, A. Canteaut, I. Dinur, M. Eichlseder, G. Leander, G. Leurent, M. Naya-Plasencia, L. Perrin, Y. Sasaki, Y. Todo, and F. Wiemer. "Out of Oddity - New Cryptanalytic Techniques Against Symmetric Primitives Optimized for Integrity Proof Systems". In: CRYPTO 2020, Part III. Ed. by D. Micciancio and T. Ristenpart. Vol. 12172. LNCS. Springer, Heidelberg, Aug. 2020, pp. 299-328. DOI: 10.1007/978-3-030-56877-1_11.

[CDL+20] A. Canteaut, S. Duval, G. Leurent, M. Naya-Plasencia, L. Perrin, T. Pornin, and A. Schrottenloher. "Saturnin: a suite of lightweight symmetric algorithms for post-quantum security". In: IACR Trans. Symm. Cryptol. 2020.S1 (2020), pp. 160-207. ISSN: 2519-173X. DOI: 10.13154/tosc.v2020.iS1.160-207.

[DL20] I. Dinur and G. Leurent. "Preface to Volume 2020, Special Issue on Designs for the NIST Lightweight Standardisation Process". In: IACR Trans. Symm. Cryptol. 2020.S1 (2020), pp. 1-4. ISSN: 2519-173X. DOI: 10.13154/tosc.v2020.iS1.1-4.

[FLN+20] A. Flórez-Gutiérrez, G. Leurent, M. Naya-Plasencia, L. Perrin, A. Schrottenloher, and F. Sibleyras. "New Results on Gimli: Full-Permutation Distinguishers and Improved Collisions". In: ASIACRYPT 2020, Part I. Ed. by S. Moriai and H. Wang. Vol. 12491. LNCS. Springer, Heidelberg, Dec. 2020, pp. 33-63. DOI: 10.1007/978-3-030-64837-4_2.

[LP20] G. Leurent and T. Peyrin. "SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust". In: USENIX Security 2020. Ed. by S. Capkun and F. Roesner. USENIX Association, Aug. 2020, pp. 1839-1856. URL: https://www.usenix.org/system/files/sec20-leurent.pdf.

[LS20] G. Leurent and Y. Sasaki. "Preface to Volume 2020, Issue 1". In: IACR Trans. Symm. Cryptol. 2020.1 (2020), pp. 1-5. ISSN: 2519-173X. DOI: 10.13154/tosc.v2020.i1.1-5.

[LLW+20] Y. Li, G. Leurent, M. Wang, W. Wang, G. Zhang, and Y. Liu. "Universal Forgery Attack Against GCM-RUP". In: CT-RSA 2020. Ed. by S. Jarecki. Vol. 12006. LNCS. Springer, Heidelberg, Feb. 2020, pp. 15-34. DOI: 10.1007/978-3-030-40186-3_2.
[BDL+21] C. Beierle, P. Derbez, G. Leander, G. Leurent, H. Raddum, Y. Rotella, D. Rupprecht, and L. Stennes. "Cryptanalysis of the GPRS Encryption Algorithms GEA-1 and GEA-2". In: *EUROCRYPT 2021, Part II*. Ed. by A. Canteaut and F.-X. Standaert. Vol. 12697. LNCS. Springer, Heidelberg, Oct. 2021, pp. 155-183. DOI: 10.1007/978-3-030-77886-6_6.

[BBC+21] R. Bhaumik, X. Bonnetain, A. Chailloux, G. Leurent, M. Naya-Plasencia, A. Schrottenloher, and Y. Seurin. "QCB: Efficient Quantum-Secure Authenticated Encryption". In: *ASIACRYPT 2021, Part I*. Ed. by M. Tibouchi and H. Wang. Vol. 13090. LNCS. Springer, Heidelberg, Dec. 2021, pp. 668-698. DOI: 10.1007/978-3-030-92062-3_23.

[BLN+21] X. Bonnetain, G. Leurent, M. Naya-Plasencia, and A. Schrottenloher. "Quantum Linearization Attacks". In: *ASIACRYPT 2021, Part I*. Ed. by M. Tibouchi and H. Wang. Vol. 13090. LNCS. Springer, Heidelberg, Dec. 2021, pp. 422-452. DOI: 10.1007/978-3-030-92062-3_15.

[CKL+21] A. Chattopadhyay, M. Khairallah, G. Leurent, Z. Najm, T. Peyrin, and V. Velichkov. "On the Cost of ASIC Hardware Crackers: A SHA-1 Case Study". In: *CT-RSA 2021*. Ed. by K. G. Paterson. Vol. 12704. LNCS. Springer, Heidelberg, May 2021, pp. 657-681. DOI: 10.1007/978-3-030-75539-3_27.

[DL21] I. Dinur and G. Leurent. "Preface to Volume 2021, Issue 1". In: *IACR Trans. Symm. Cryptol.* 2021.1 (2021), pp. 1-4. ISSN: 2519-173X. DOI: 10.4658/tosc.v2021.i1.1-4.

[LP21] G. Leurent and C. Pernot. "New Representations of the AES Key Schedule". In: *EUROCRYPT 2021, Part I*. Ed. by A. Canteaut and F.-X. Standaert. Vol. 12696. LNCS. Springer, Heidelberg, Oct. 2021, pp. 54-84. DOI: 10.1007/978-3-030-77870-5_3.

[LPS21] G. Leurent, C. Pernot, and A. Schrottenloher. "Clustering Effect in Simon and Simeck". In: *ASIACRYPT 2021, Part I*. Ed. by M. Tibouchi and H. Wang. Vol. 13090. LNCS. Springer, Heidelberg, Dec. 2021, pp. 272-302. DOI: 10.1007/978-3-030-92062-3_10.

[BBL+22] A. Bariant, C. Bouvier, G. Leurent, and L. Perrin. "Algebraic Attacks against Some Arithmetization-Oriented Primitives". In: *IACR Trans. Symm. Cryptol.* 2022.3 (2022), pp. 73-101. DOI: 10.4658/tosc.v2022.i3.73-101.

[BL23] A. Bariant and G. Leurent. "Truncated Boomerang Attacks and Application to AES-Based Ciphers". In: *EUROCRYPT 2023, Part IV*. Ed. by C. Hazay and M. Stam. Vol. 14007. LNCS. Springer, Heidelberg, Apr. 2023, pp. 3-35. DOI: 10.1007/978-3-031-30634-1_1.

## Research Reports

[LBF08] G. Leurent, C. Bouillaguet, and P.-A. Fouque. *SIMD Is a Message Digest*. Submitted to the SHA-3 competition. 2008. URL: https://who.rocq.inria.fr/Gaetan.Leurent/simd.html.

[GLS+14] V. Grosso, G. Leurent, F.-X. Standaert, K. Varici, F. Durvaux, L. Gaspar, and S. Kerckhof. *SCREAM & iSCREAM: Side-Channel Resistant Authenticated Encryption with Masking*. Submitted to the CAESAR competition. Mar. 2014. URL: http://perso.uclouvain.be/fstandae/SCREAM/.
[BDD+17] X. Bonnetain, P. Derbez, S. Duval, G. L. Jérémy Jean, B. Minaud, and V. Suder. *AEZ forgeries*. Message on the crypto-competition mailing list. Presented at the FSE 2017 rump session: https://iacr.org/workshops/fse2017/slides/Rump-02.pdf. Mar. 2017. URL: https://groups.google.com/g/crypto-competitions/c/YWkEZkLKr9E/m/75LG5KmeBQAJ.

[LMP+23] G. Leurent, B. Mennink, K. Pietrzak, and V. Rijmen. *Analysis of MinRoot: Public report*. Tech. rep. Ethereum Foundation, Sept. 2023. URL: https://crypto.ethereum.org/events/minrootanalysis2023.pdf.

## Outreach

[LN18] G. Leurent and M. Naya-Plasencia. "La fagilité inattendue du chiffrement symétrique". In: *La Recherche*. 514. Sophia Publications, Nov. 2018, pp. 54-56.

[BCC+21] X. Bonnetain, A. Canteaut, V. Cortier, P. Gaudry, L. Hirschi, S. Kremer, S. Lacour, M. Lequesne, G. Leurent, L. Perrin, A. Schrottenloher, E. Thomé, S. Vaudenay, and C. Vuillot. "Le traçage anonyme, dangereux oxymore – Analyse de risques à destination des non-spécialistes". In: *Le droit face au coronavirus*. Ed. by Club des juristes. LexisNexis, Dec. 2021. ISBN: 978-2-7110-3639-4.
<figure><img src="image_6.png" /></figure>
# 1. Introduction

Cryptography enables secure communication in the presence of an adversary, with tools to guarantee the confidentiality and authenticity of messages, and to authenticate users. It is a vital part of the today's digital world, where we exchange private information over the internet, we buy goods and services on the web, industrial control systems are networked, banks settle financial transactions online, and state agencies communicate remotely. Indeed, we have strong evidence that adversaries are trying to intercept communications and to penetrate computer systems, from cybercriminals to state agencies performing massive surveillance and to private companies collecting personal data for targeted advertising.

Cryptographic schemes are designed with a bottom-up approach, starting from primitives that operate on small messages and achieve a well-defined security notion (such as being hard to invert). Then, primitives are used inside a mode of operation (or mode) and a protocol to deal with session establishment and arbitrary messages.

In order to allow security evaluation of the schemes, the algorithms must be published, and their security must rely on a small piece of information that is different for each user, and kept secret: the key. These principles have been established as early as 1883 by Auguste Kerckhoffs:

<figure><img src="image_7.png" /></figure>

1. Le système doit être matériellement, sinon mathématiquement, indéchiffrable;

2. Il faut qu'il n'exige pas le secret, et qu'il puisse sans inconvénient tomber entre les mains de l'ennemi;

3. La clef doit pouvoir en être communiquée et retenue sans le secours de notes écrites, et être changée ou modifiée au gré des correspondants;

4. Il faut qu'il soit applicable à la correspondance télégraphique;

5. Il faut qu'il soit portatif, et que son maniement ou son fonctionnement n'exige pas le concours de plusieurs personnes;

6. Enfin, il est nécessaire, vu les circonstances qui en commandent l'application, que le système soit d'un usage facile, ne demandant ni tension d'esprit, ni la connaissance d'une longue série de règles à observer.

— Auguste Kerckhoffs, [Ker83]

<figure><img src="image_8.png" /></figure>

## 1.1 Symmetric and asymmetric cryptography

The most natural cryptographic construction use the same key to encrypt a message and to decrypt it; it has been used since antiquity to protect military communications. Today, we denote the corresponding field as *symmetric cryptography* or *secret-key cryptography*.

**Symmetric cryptography.** Symmetric primitives are mostly dedicated designs that try to mix the key and the message in a complex way following the notions of confusion and diffusion formalized by Shannon in 1949 [Sha49]. We have four main types of primitives in
use today: block ciphers (such as AES [AES]), stream ciphers (such as Salsa20 [Ber08]), hash functions (such as the SHA standards [SHA1; SHA2; SHA3]), and cryptographic permutations (such as Ke'acc-f [SHA3]).

Symmetric primitives usually work on small blocks of fixed size (n bits, typically n ∈ {64, 128, 256} for block ciphers, and 256 ≤ n ≤ 2048 for hash functions and cryptographic permutations). Then, they are used inside a mode of operation to deal with arbitrary-length messages. A mode divides the message M into n-bit blocks mᵢ, and processes the blocks one by one through the primitive with various chaining rules. Standard modes of operation starting from a block cipher can provide encryption (CBC, CTR), authentication (CBC-MAC, PMAC), or authenticated encryption (GCM, OCB). Rogaway gives a good overview of the main block-cipher modes and their security [Rog11]. Similarly, the sponge construction and its variants turn a cryptographic permutation into a hash function, a stream cipher, or an authenticated encryption. Hash functions are typically considered a primitive, but they are actually built using a mode of operation (often Merkle-Damgård or HAIFA) from a smaller primitive: a compression function.

In the last years, an important trend is the design of *lightweight* primitives, for use in embedded devices with very limited power (medical implants, contactless smart cards, sensor nodes, ...), where standard cryptography is too expensive. In particular, the US National Institute of Standards and Technology (NIST) has recently organized a competition to select new standards in this field.<fnref n="1" />

Some industry applications use proprietary (non-public) algorithms, in particular for lightweight use cases where standard algorithms do not fit. In most cases, these algorithms turn out to be weak and can be broken in practice, such as CSS [Ste99] (used for the DRM system of DVDs), PC1 (used for the DRM system of Amazon ebooks) [BLR13], Keeloq [IKD+08; EKM+08] (used in car keys from multiple manufacturers), DST 40 [WMA+19] (also used in car keys) or MiFare [GKM+08] (used in transport card such as the Oyster card in London).

**Asymmetric cryptography.** On the other hand asymmetric cryptography, or public-key cryptography uses different keys to encrypt a message and to decrypt it. Therefore, the encryption key does not have to be kept secret, and can be widely distributed. This solves the problem of key distribution, which is a big drawback of symmetric cryptography.

The most widely used constructions today are based on hard problems from number theory: the Diffie-Hellman key exchange [DH76] relies on the hardness of computing discrete logarithms, while the RSA signature and encryption scheme [RSA78] relies on the hardness of factoring.

However, those constructions would be broken by a quantum computer, if such a device can be built. Indeed, Shor's algorithm [Sho94] computes discrete logarithms and factors integers in quantum polynomial time. Following recent advances in quantum information theory, there is a strong interest in constructions that rely on hard problems that are believed to resist quantum computers, such as code-based cryptosystems [McE78] or lattice-based cryptosystems [Ajt96; Reg05]. The NIST has recently organized a standardization process for this type of post-quantum algorithms.<fnref n="2" />

**Hybrid systems.** Many security systems rely on public-key cryptography for key establishment, but only secret-key cryptography can offer sufficient performance to process bulk messages. Therefore, in practice, we use hybrid schemes that combine public-key cryptography and symmetric cryptography.

<footnote n="1">¹https://csrc.nist.gov/projects/lightweight-cryptography</footnote>

<footnote n="2">²https://csrc.nist.gov/projects/post-quantum-cryptography</footnote>
## 1.2 Evaluating cryptographic schemes

Since the seminal work of Goldwasser and Micali [GM84], provable security has become the accepted practice in cryptography. Proposals for new schemes and protocols are expected to come with a security reduction, showing that the system is secure under a reasonable security assumption, or security model, for the underlying primitive(s).

A security proof starts by defining a security notion, and bounds the probability (or advantage) of an adversary to break that security notion, depending on the resources she can use, and the security of the primitive. Provable security focuses on asymptotic security: a mode is secure if the bound decreases exponentially with $n$.

**Concrete security.** In order to better understand the security of cryptographic schemes, the “concrete security” [BDJ+97] approach writes explicit bounds on the security depending on the parameters of the system. This allows to select appropriate parameters. For instance, the security proofs of several CBC-MAC variants [BKR94; PR00] can be written as:

$$ \mathrm{Adv}_{\mathrm{CBC-MAC-E}}^{\mathrm{PRF}} \le \mathrm{Adv}_{E}^{\mathrm{PRP}} + \frac{\sigma^2}{2^n}, $$

where $E$ is an $n$-bit block cipher, and $\sigma$ the amount of data authenticated. This means that CBC-MAC is a secure family of pseudo-random functions (PRF) as long as $\sigma \ll 2^{n/2}$, and the block cipher is a secure pseudo-random permutation family (PRP).

In practice, the bounds of many modes of operation include a term in the order of $\sigma^2/2^n$, where $\sigma$ is the total length of the queries made by the adversary. This means that the mode is only secure when $\sigma \ll 2^{n/2}$, which is called birthday-bound security.

**Cryptanalysis.** Cryptanalysis is another way to evaluate the security of cryptographic schemes, using a whole range of algorithmic knowledge to search for efficient attacks. There are classical techniques that apply to large classes of schemes (such as differential [BS91] and linear [Mat94] cryptanalysis), but cryptanalysis is still a difficult task because these techniques must be tailored to each scheme, and new techniques must often be devised.

Cryptanalysis is a crucial part of cryptographic research because we cannot prove unconditionally that a cipher is secure. In particular, we cannot prove the security of cryptographic primitives, because we cannot reduce their security to the security of a lower-level components. Therefore, a large, public cryptanalysis effort is of utmost importance. If such an effort unveils weaknesses in a cryptographic construction, it will be deprecated, hopefully before the weaknesses lead to practical breaks. Conversely, a continued cryptanalysis effort lasting over several years without finding security weaknesses is a good way to build trust in the security of a construction. For instance the AES standard is a widely available and well trusted block cipher, because numerous experts have tried to break it in the last 25 years.

## 1.3 Cryptography usage in practice

Cryptography is now used routinely in our daily lives. Most of the devices with wireless communication use some kind of encryption, because radio transmissions are easy to intercept: Wi-Fi uses WEP (based on RC4) or WPA (based on AES), cell phone communications are encrypted with Kasumi, SNOW 3G, AES, or ZUC, Bluetooth uses E0, cordless phones use the DECT Standard Cipher, etc. Cryptography is also widely used to authenticate legitimate users of a system: credit cards use public-key cryptography to prove to a reader that they are genuine; wireless keys fobs or cards are used to open cars, to access public transports, or to enter buildings; and passports contain an RFID chip to authenticate them.
<figure><img src="image_9.png" /><figcaption>**Figure 1.1:** TLS: an example of secure channel establishment.</figcaption></figure>

One of the most successful deployments of cryptography in practice is the SSL/TLS protocol, with more than 80% of pages loaded on the web now encrypted with TLS.<fnref n="3" /> It is also a good example to understand what a real-world attacker can do.

**The Transport Layer Security protocol (TLS).** TLS is a transport protocol that can be used to encapsulate various internet protocols. It is widely used today on the internet, with most HTTP and IMAP connection secured by TLS (HTTP over TLS is denoted as HTTPS). TLS derives from SSL, originally designed by Netscape, with SSL 2.0 released in 1995 and SSL 3.0 in 1996. Development of the protocol was then taken over by the IETF, and later versions are denoted as TLS, with four version up to date: TLS 1.0 in 1999, TLS 1.1 in 2006, TLS 1.2 in 2008, and TLS 1.3 in 2018.

TLS is a hybrid protocol, using public-key cryptography for key establishment, and symmetric cryptography to encrypt and authenticate the actual data with the session key. When a client connects to a server, they start a handshake phase, where public-key cryptography is used to authenticate the server and to establish the session key, and parameters of the connection are negotiated (in particular the choice of ciphers to use). Figure 1.1 shows a typical example of TLS handshake and data transmission.

When used properly, TLS guarantees the identity of the server (and optionally the identity of the client), and protects the data from interception and modification.

**The man-in-the-browser setting.** When TLS is used to secure web connections, an attacker can use the man-in-the-browser setting to mount powerful attacks in practice (Figure 1.2). This setting was first considered in the BEAST attack [DR11], and assumes that:

1. The attacker has access to the network and can read and modify network packets. This is easy to realize when the victim is connected to an open Wi-Fi network, as used in many public spaces.

2. The victim is logged-in to a valuable website (such as a webmail, or an online bank). Since HTTP is a stateless protocol, the victim's browser uses an authentication token (usually a secret cookie) to identify queries to the website, and every HTTP query includes this token in a header.

3. The victim visits an attacker-controlled website.

<footnote n="3">³https://letsencrypt.org/stats/</footnote>
<figure><img src="image_10.png" /><figcaption>Figure 1.2: The man-in-the-browser setting.</figcaption></figure>

```javascript
var url = "https://10.0.0.1/index.html";
varabh = new XMLHttpRequest;
while(true) {
 abh.open("HEAD", url, false);
 abh.withCredentials = true;
 abh.send();
 abh;abort();
}
```

<caption>Figure 1.3: Simple JavaScript code to encrypt chosen messages to a target website.</caption>

In practice, the attacker can use phishing, or modify a web page on the fly if the victim visits a non-encrypted website.

When those conditions are met, the attacker can use the malicious website to send arbitrary JavaScript code to the victim. This code will be executed by the victim's browser, and can make arbitrary queries to the target website (see Figure 1.3 for a concrete example). Since HTTP is stateless, every query includes the authentication token. The attacker cannot read the plaintext messages with the token or receive the answers from the target website, but she can ask for the encryption of chosen messages that include the token, and capture the corresponding ciphertexts on the network. This is a powerful attack scenario, showing that chosen- plaintext attacks are actually practical.

The attacker will try to exploit weaknesses of TLS to recover the authentication token. If she succeeds, she can use the token to authenticate as the victim on the target website, and extract all the information she wants.

**The chosen-prefix secret-suffix model.** In order to make attacks easier to explain, Hoang et al. have proposed a simple model to capture the type of attacks possible in the man-in-the-browser setting [HRR+15]. The attacker must recover a secret value $S$, given access to an oracle that computes the encryption of $M \parallel S$ for a chosen prefix $M$:

$$ \mathcal{O}: M \to \mathcal{E}(M \parallel S). $$

This is an important model because it corresponds to practical adversaries in the man-in-the-browser setting, even though chosen- plaintext attacks can seem artificial. It is also sufficiently generic to capture most attacks in practice. In particular, the attacker can vary the length of the prefix, and move the secret suffix across block boundaries.
<table><caption>**Table 1.1:** Symmetric cryptography usage on the web, according to different sources. Telemetry data [Moz23] is from Firefox Nightly; it represents the percentage of actual connections using each cipher. Internet scan data [Cen23] is from Censys [DAM+15]; it represents the percentage of public internet services that would use each cipher. The discrepancy in Chacha-Poly usage is due to different client-side preferences.</caption><thead><tr><th>Source</th><th>Telemetry [Moz23]<br>per connection</th><th>Internet scan [Cen23]<br>per service (host, port)</th></tr></thead><tbody><tr><td><strong>Encryption</strong></td><td></td><td></td></tr><tr><td>AES-GCM</td><td>98.7%</td><td>61.8%</td></tr><tr><td>Chacha-Poly</td><td>0.6%</td><td>32.9%</td></tr><tr><td>AES-CBC</td><td>0.7%</td><td>5.2%</td></tr><tr><td>3DES-CBC</td><td>0.0001%</td><td>0.1%</td></tr><tr><td><strong>MAC</strong></td><td></td><td></td></tr><tr><td>HMAC-SHA256</td><td>76.7%</td><td>67.9%</td></tr><tr><td>HMAC-SHA384</td><td>22.5%</td><td>26.9%</td></tr><tr><td>HMAC-SHA1</td><td>0.7%</td><td>5.2%</td></tr></tbody></table>

Moreover, if the attacker wins this game, there is a real impact, with plaintext recovery and access to a secure resource when the secret is an access token. We will use this setting when describing attacks against modes of operation, rather than the distinguishers used in security proofs.

**Primitive usage.** The vast majority of deployed cryptography uses public standards that have been well analyzed. Unfortunately, many old standards are known to be insecure, because of mistakes in their design or inadequate security level, but still have non-negligible usage. For instance, GSM encryption (using A5/1 [BBK08]) and WEP (using RC4 [FMS01; TWP08]) can be broken easily.

We give some statistics about current (late 2023) cryptography usage in the web (HTTPS traffic) in Table 1.1: we see that almost all traffic is secured with robust algorithms: AES-GCM or Chacha-Poly for encryption, HMAC-SHA256 or HMAC-SHA384 for authenticity. However, there is still some fraction of the traffic that uses HMAC-SHA1 and non-zero usage of 3DES (triple DES).

## 1.4 Cryptanalysis beyond primitives

Cryptanalysis techniques are mostly used to target primitives and assess their security. However, we can also apply those techniques to modes of operations and protocols.

### 1.4.1 Generic attacks

Generic attacks are attacks that don't use any specific property of the block cipher. A generic attack against a mode of operation will work for any instantiation with a concrete block cipher. While dedicated attacks using properties of the block cipher are more powerful in general, generic attacks uncover properties of the mode itself.

Typically, cryptanalysis is used to study the security of primitives, and upper layers (modes and protocols) are studied with security proofs. However, there are many cases where security proofs do not give a full picture of the security of a scheme, and studying generic attacks gives a better understanding of the security. This occurs in the following typical situations:
**Some proofs are flawed:** several high-profile modes of operations have been broken, even though they had been proven secure, such as EAX' [MLM+14], or OCB2 [IIM+19]. Indeed, security proofs are very technical; it is easy to make a mistake, and hard to verify the correctness of a proof.

**Some proofs are not tight:** when there is a gap between the proof and the best attack, more analysis is needed. For instance, CENC [Iwa06] and SUM-ECBC [Yas10] were initially proven secure up to $2^{2n/3}$ queries, but no attack faster than $2^n$ was known; after further analysis, it turned out that the security of CENC is essentially $2^n$ [IMV16], while the security of SUM-ECBC is about $2^{3n/4}$ [LNS18; KLL20].

**The security depends on the model used:** security proofs make assumption about the power of the adversary (such as knowing or choosing the plaintext), and this has a large impact on the achieved security. For instance encryption without authentication is secure against passive adversaries, but insecure against active adversaries. More recently, cryptography have been studied in a quantum setting, and many standardized MACs proven secure in the classical setting were shown insecure [KLL+16a].

**Modes with similar proofs can have different security:** even if the proof is tight, the security degradation outside the domain of the proof can range from low-impact distinguishers to devastating key-recovery. For instance, PMAC is secure up to $2^{n/2}$ queries [Rog04], and there is a matching forgery attack [LKS+06]. However, small variations of PMAC become susceptible to a key-recovery attack with $2^{n/2}$ queries, even though the security proof is the same [FLS15].

**Understanding attacks helps us design better modes:** Understanding generic attacks also helps to design more secure modes. For instance, the generic attack by Preneel and van Oorschot [Pv95] against iterated MACs explains the constructions used for MACs with security beyond the birthday bound: RMAC [JJV02] and the Wegman-Carter MAC [WC81] are randomized, while SUM-ECBC [Yas10] and PMAC+ [Yas11] use a $2^n$-bit internal state.

**Real-world usage sometimes violates the assumptions of the proofs:** SHA-1 has been broken decades ago, but it has stayed in use for a long time in protocols whose proofs assumed collision-resistance, because deprecation takes time, and attacks against primitives do not directly translate to attacks on real-world protocols (even when they invalidate the proofs). Block ciphers with 64-bit blocks (such as 3DES) have also been used with an amount of data that violates the assumptions of the proofs [BL16a].

### 1.4.2 Real-world impact of cryptanalysis

Weak cryptography can be used long after weaknesses have been found by the academic community. Unfortunately, public demonstrations of high-profile attacks seem to be the only way to convince the industry to move away from widely used standards with known weaknesses, as expressed by AlFardan and Paterson:

> "Our long-term aim is to ensure that weak encryption options are eliminated from TLS, to the eventual benefit of all users of TLS. Experience shows that the only way to make this happen is to make the attacks as powerful as possible and build proof-of-concept implementations of them.
> 
> — Nadhem AlFardan and Kenny Paterson, [AP13a]
<figure><img src="image_11.png" /><figcaption>**Figure 1.4:** Hash function usage in certificates from top websites (150 000 certificates).
Source: [HBK+11] (2009-2011), https://www.ssllabs.com/ssl-pulse/ (after 2012).</figcaption></figure>

For instance, den Boer and Bosselaers found weaknesses in MD5 as early as 1993, with a collision attack on the compression function [dB94]. Even after the full collision attack of Wang *et al.* in 2004 [WY05], many users argued that collisions only had a limited impact on applications. Indeed, the attacker must choose *both messages* to exploit a collision, and she has little control over the values of the actual colliding messages, where the differences are inserted. In particular, MD5 continued to be used to sign website certificates, as seen in Figure 1.4. It took a public demonstration of the creation of a rogue certificate in 2009 to eliminate MD5 from certificate authorities [SSA+09]. The same story happened with SHA-1: a collision attack has been known since 2005 [WYY05], but due to its high computational complexity, it was only implemented in practice in 2017, using a large GPU cluster [SBK+17]. SHA-1 has been widely used until 2015, and there was still non-negligible usage of SHA-1 in 2020 (outside web certificates), when we demonstrated a practical impersonation attack against the PGP/GnuPG Web-of-Trust using weaknesses of SHA-1.

As another example, several attacks against TLS have been announced in the last years, and forced the deployment of countermeasures, even though the underlying weaknesses were known for a long time. The BEAST attack [DR11] is due to the use of predictable IVs, which was known to be an issue since at least 1995.<fnref n="4" /> The CRIME attack [RD12] uses compression, which was seen as a problem in 2002 [Kel02]. The Lucky Thirteen [AP13b] and POODLE [MDK14] attacks use a padding oracle, as defined by Vaudenay [Vau02]. In 2013 and 2015, new attacks against RC4 use in TLS [ABP+13; GPv15; VP15] used biases in the keystream that have been known since 2000 [FM01; MS02]. Many of these attacks are based on the man-in-the-browser attacker model.

**Algorithm negotiation and downgrade attacks.** Another issue in practice is the possibility of downgrade attacks when a client and a server negotiate the protocol to use and its parameters (in particular algorithms and key sizes). Algorithm negotiation is designed so that the client and server agree on the *best* algorithm that they both support. However, in some cases an attacker can force them to use the *worst* algorithm that they support. TLS supports a huge range of ciphersuites, including modern authenticated encryption algorithms such as AES-GCM, and obsolete algorithms like DES and RC4, but the obsolete algorithms are often enabled to support legacy clients.

<footnote n="4">⁴http://web.cs.ucdavis.edu/~rogaway/papers/draft-rogaway-ipsec-comments-00.txt</footnote>
<figure><img src="image_12.png" /><figcaption>**Figure 1.5:** SSL/TLS versions supported by top websites (150 000 websites). Source: https://www.ssllabs.com/ssl-pulse/.</figcaption></figure>

This has been exploited in many different attacks over the years, leading deprecation of older standards and ciphers one by one. The SSLStrip [Mar09] removes redirections from HTTP to HTTPS, so that the client keeps using unsecured HTTP even if the server wants to use HTTPS. The POODLE [MDK14] attacks exploits insecure version fallback from TLS to SSL 3.0. The FREAK [BBD+15] and Logjam [ABD+15] attacks exploit export-grade ciphers that are weak on purpose, but that many clients and servers still supported. Downgrade attacks are also a concern in telephony network, where phones will switch to the insecure GSM network if more secure networks (3G, 4G, 5G) are jammed.

In particular, some attacks exploiting weaknesses of cryptographic algorithms are possible as long as the algorithms are *supported* by implementations, even if they are not used in normal conditions.

In recent years, there has been significant improvements, with TLS 1.3 disabling many legacy algorithms (in particular MD5 and SHA-1), and including a robust downgrade-detection mechanism [BBF+16]. Web browsers are also disabling TLS 1.0 and TLS 1.1, which don't offer modern authenticated encryption algorithms and depend on SHA-1.

## 1.5 Prelude: the birthday bound

The security of the vast majority of cryptosystems is affected by the presence of collisions. This is a well-known issue for hash functions: due to the birthday paradox we expect to find collisions in an $n$-bit hash function with roughly $2^{n/2}$ queries. Intuitively, with $2^{n/2}$ queries, there are about $2^{n-1}$ pairs of queries, and each pair is a collision with probability $2^{-n}$ if it behaves randomly. The pairs are not independent, but assuming independence gives a simple explanation that is quite close to the truth.

More formally, we consider $t$ independent random variables in $\{0, 1\}^n$. The probability that they are all distinct is

$$ \Pr[\text{no collision}] = 1 \times \frac{2^n - 1}{2^n} \times \frac{2^n - 2}{2^n} \times \frac{2^n - 3}{2^n} \times \dots = \prod_{i=0}^{t-1} \left(1 - \frac{i}{2^n}\right) \\ \approx \exp\left(-\frac{t^2}{2^{n+1}}\right) $$
A variant with two sets of random variables is also useful for cryptographic applications. Given two random subsets $S, T \subset \{0, 1\}^n$, they have a non-empty intersection with high probability as soon as $|S| \cdot |T| \gtrsim 2^n$.

We note that the theoretical analysis assumes independent random variables. In practice, we often apply it to cryptographic functions that are not actually random, but deviation from the random behavior would typically be a sign of a deeper weakness in the cryptosystem. Moreover, experiments can validate this heuristic analysis.

### 1.5.1 Finding collisions efficiently

The birthday paradox shows that collisions exist after roughly $2^{n/2}$ evaluations of a random function $h$. This defines the security level of an ideal hash function in the information-theoretic model, where we only count oracle calls, and we don't consider the additional computations required to locate the collision.

In practice, we find collisions efficiently by building a list of $2^{n/2}$ inputs and outputs of the hash function, and sorting it according to the hash output. Then we locate the collisions by traversing the list. This requires $O(n \times 2^{n/2})$ operations and $O(n)$ memory. There are more advanced techniques with almost the same time complexity using very little memory. The rho method ($\rho$) by Pollard [Pol75] considers iterates of the function $h: x_i = h(x_{i-1})$. After some iterations, the values enter a cycle, and the cycle entry is a collision. Using Floyd's tortoise and hare algorithm, the cycle entry is detected with constant memory: a collision is found with $O(2^{n/2})$ operations and $O(1)$ memory.

The variant of van Oorschot and Wiener [vW99] has essentially the same complexity, but uses distinguished point to allow efficient parallelization. Moreover, it generalizes well to the search for multiple collisions: finding $m$ collisions requires a memory $O(m)$ and time $O(2^{n/2} \times \sqrt{m})$. The time complexity matches the information-theoretic lower bound up to a constant factor.

When looking for a collision between two sets $S$ and $T$, we sort both of them and traverse them simultaneously to locate collisions. If the sets correspond to the evaluations of two functions $h$ and $g$ (i.e. $S = \{h(x) : x\}, T = \{g(y) : y\}$), we can use the memory-less algorithms by defining a helper function

$$ \phi(x) = \begin{cases} h(x) & \text{if } x \text{ is odd} \\ g(x) & \text{if } x \text{ is even} \end{cases} $$

With constant probability, a collision in $\phi$ is a collision between $h$ and $g$. For further details about algorithmic aspects of collision finding, we refer to the work of Joux [Jou09].

### 1.5.2 Birthday-bound security

Birthday attacks are very common across symmetric cryptography; they affect hash functions, MACs, block cipher modes of operation, and even stream ciphers [Gol97]. In most cases, there is a matching proof and the security of the construction is well understood. However, it is important to study the security loss around the birthday bound to better understand the modes, and to select adequate parameters for real-world use.

In particular, the security of a block cipher is often reduced to the key size $\kappa$: the best attack should be the exhaustive search of the key, with complexity $2^{\kappa}$. However, birthday attacks on modes of operation show that the security is threatened when $2^{n/2}$ blocks of data are processed. Therefore, the block size $n$ is also an important security parameter.

Surprisingly, this aspect of block cipher security is often overlooked, and block ciphers with small block size are commonly used ($n = 128$ is the typical case, but $n = 64$ is sometimes used for legacy or lightweight systems). This contrasts with the case of hash functions or stream cipher, where birthday attacks apply directly to the primitives and constructions with a state size $n$ smaller than 160 have been deprecated.
### 1.5.3 Security beyond the birthday bound

In order to make block ciphers with a small block size more usable in practice, new modes of operation have been designed to stay secure after more than $2^{n/2}$ blocks of data. This requires very careful design, and advanced proof techniques to demonstrate security. Some of these modes are secure up $2^{2n/3}$, $2^{3n/4}$ or even $2^n$ blocks of data. For encryption, an important example is CENC [Iwa06] a modification of the counter mode secure up to roughly $2^n$ blocks of data [IMV16]. For authentication, several MACs have been proposed with security beyond the birthday bound, such as SUM-ECBC [Yas10] and PMAC+ [Yas11]. Alternatively, several recent constructions use a tweakable block-cipher as the underlying primitive rather than a block cipher. This enables higher security without increasing the internal state size.

#### Outline

In this thesis, I present several results obtained by applying cryptanalysis techniques beyond primitives, to reveal properties of modes and protocols that are not captured by security proofs. Most of the results rely on finding collision between carefully crafted sets or functions, showing the importance of the birthday paradox across many aspects of symmetric cryptography.

In particular, I present many surprising or unexpected results:

* The sum of two hash functions ($h_1(m) \oplus h_2(m)$) is often weaker than the initial functions (Chapter 2);

* SHA-1 signatures can be abused in practice (Chapter 3);

* Secure channel protocols (TLS, SSH, IPsec) are broken by chosen-prefix collisions on the underlying hash function;

* The use of an internal checksum in a hash function (as in the GOST standards) makes it weaker when used in HMAC (Chapter 4);

* Block ciphers with a 64-bit block size (3DES, Blowfish) can be abused, leading to practical plaintext recovery (Chapter 5);

* The CTR mode leaks information about the plaintext after roughly $2^{n/2}$ blocks, just like the CBC mode (Chapter 5);

* Cryptanalysis techniques based on collisions can be used against several MACs with security beyond the birthday bound (Chapter 6);

* Widely used MAC constructions are broken in the quantum setting, even though quantum computers were believed to affect mainly public key cryptography (Chapter 7).
## 2. Generic Attacks Against Hash Functions and Hash Combiners

This chapter begins with a review of the state of the art, and includes new results based on articles [LW15] and [BDG+20], found in Appendix A and B.

Cryptographic hash functions are crucial components in many information security systems, used for various purposes such as building digital signature schemes, message authentication codes, commitments schemes, or password hashing functions. A hash function $H : \{0, 1\}^* \to \{0, 1\}^n$ takes an arbitrary length input and produces an $n$-bit output or digest. Hash functions are used in many settings with various security requirements; the general expectation is that a hash function should behave like a random function from $\{0, 1\}^*$ to $\{0, 1\}^n$. More concretely, the main security notions expected from a hash function are:

**Collision resistance.** It should be hard to find two messages $M \neq M'$ with $H(M) = H(M')$.

**Second-preimage resistance.** Given a challenge message $C$, it should be hard to find $M \neq C$ with $H(M) = H(C)$.

**Preimage resistance.** Given a target hash value $\overline{H}$, it should be hard to find $M$ with $H(M) = \overline{H}$.

Since generic collision attacks have complexity $2^{n/2}$, and generic preimage (and second-preimage) attacks have complexity $2^n$, a secure hash function should have the same level of resistance.

### Iterated hash functions

In practice, hash function are built by iterating a compression function with fixed-length inputs. In this chapter, we focus on narrow-pipe designs, i.e. we assume that the internal state size is the same as the output size $n$. The message $M$ is first split into blocks $m_0, \dots, m_{L-1}$; for simplicity, we assume that the message length is a multiple of the block size, and we ignore the padding. The hash function iterates a series of compression

<figure><img src="image_13.png" /><figcaption>**Figure 2.1:** Iterated hash function.</figcaption></figure>
functions $h^{(i)}$ over an internal state $x$, with the initial value denoted as IV. Finally, the hash value is computed with a finalization function $g$ (see Figure 2.1):

$$x_0 = \text{IV} \qquad x_{i+1} = h^{(i)}(x_i, m_i) \qquad H(M) = g(x_L, |M|)$$

The finalization function $g$ takes the message length as a parameter; this is denoted as MD strengthening. For simplicity, we sometimes write $h$ instead of $h^{(i)}$, and $g(x)$ with the length being implicit.

This generic description includes two widely-used constructions as special case:

**The Merkle-Damgård construction [Mer90; Dam90]** uses the same compression function $h$ for all steps ($\forall i, h^{(i)} = h$), as well as for the finalization ($g = h$). It used by standards SHA-1 [SHA1] and SHA-2 [SHA2].

**The HAIFA construction [BD07]** is a strengthened variant of the Merkle-Damgård construction where each compression function takes the block index as a parameter, and the finalization function takes a special parameter to make it different from the compression function. This avoids “cut-and-paste” attacks that move blocks of message around. This mode was used by several candidates in the SHA-3 competition, such as BLAKE [AHM+10] and Skein [FLS+10].

We use the notation $h^*$ to denote the iterated compression function (without the finalization function): $h^*(m_0 \parallel m_1 \parallel m_2) = h_2(h_1(h_0(IV, m_0), m_1), m_2)$. For simplicity, we also abuse this notation with an extra input argument corresponding to the initial state: $h^*(x, m_0 \parallel m_1 \parallel m_2) = h(h(h(x, m_0), m_1), m_2)$ (with the block index implicit).

There has been a lot of work on generic attacks on iterated hash functions, in particular after the seminal multicollision attack of Joux [Jou04]. There are many security notions that fall between collision-resistance and preimage-resistance, and we need cryptanalysis to understand their security. In many cases, we find attacks with complexity close to the birthday bound, but some attacks are quite involved.

## 2.1 Generic attacks on hash functions

The Merkle-Damgård construction was proposed because it preserves collision resistance: any collision in the iterated hash function implies a collision in the compression function. In particular, if the compression function is collision-resistant (in the sense that no collision is known, and it is infeasible to find one explicitly), then the iterated hash function is collision-resistant. Generically, finding a collision in the compression function requires $2^{n/2}$ operations (due to the birthday paradox).

The Merkle-Damgård construction also preserves preimage resistance: a preimage in the iterated hash function implies a preimage of the finalization function. Generically, finding a preimage of the finalization function requires $2^n$ computations.

More generally, the Merkle-Damgård construction and its variants have been proven indifferentiable up to the birthday bound [CDM+05]. This means that the hash function behaves like a random oracle, assuming that the compression function is ideal.

However, several generic attacks have been proposed, showing that an attacker can break some security notions if she can perform more than $2^{n/2}$ operations. These attacks are based on special structures of messages, build from well-crafted collisions.

### 2.1.1 Collision extension

An important property of iterated hash function is that collisions in the internal state can be extended. Indeed, let us consider two messages $M, M'$ of the same length. If $h^*(M) = h^*(M')$ then for any suffix $S$ we have $h^*(M \parallel S) = h^*(M' \parallel S)$ (this implies $H(M \parallel S) = H(M' \parallel S)$).
<figure><img src="image_14.png" /><figcaption>Figure 2.2: Joux’s multicollision.</figcaption></figure>

In particular, this distinguishes a narrow-pipe hash function from an ideal hash function using $O(2^{n/2})$ operations (finding many related collisions is hard for an ideal hash function).

### 2.1.2 Multicollisions and attack against concatenation [Jou04]

**Multicollision.** A multicollision is a large set of messages $\mathcal{M}$ such that all messages have the same digest. In 2004, Joux introduced a simple technique to build a multicollision efficiently for narrow-pipe hash functions, as shown in Figure 2.2:

1. Starting from the IV, find a collision $m_0, m'_0$: $x_1 = h(\text{IV}, m_0) = h(\text{IV}, m'_0)$

2. Starting from $x_1 = h^*(m_0)$, find a collision $m_1, m'_1$: $x_2 = h(x_1, m_1) = h(x_1, m'_1)$

3. Starting from $x_2 = h^*(m_0 \| m_1)$, find a collision $m_2, m'_2$: $x_3 = h(x_2, m_2) = h(x_2, m'_2)$

4. ...

Since the internal states collide at every step, each collision is independent of the choice of the previous messages. After $t$ iterations, we obtain a set of $2^t$ messages with the same digest: $[m_0 \| m_1 \| m_2 \| \dots], [m'_0 \| m'_1 \| m'_2 \| \dots], [m_0 \| m'_1 \| m_2 \| \dots], [m'_0 \| m'_1 \| m_2 \| \dots], [m_0 \| m_1 \| m'_2 \| \dots], \dots$. Each step requires roughly $2^{n/2}$ work to find a collision, so that a multicollision of size $2^t$ is built with complexity $t \cdot 2^{n/2}$ in a narrow-pipe function. However, it would require roughly $2^{n \cdot (2^t - 1)/2^t}$ operations for an ideal $n$-bit hash function (almost $2^n$ for moderately large values of $t$).

**Breaking the concatenation of two hash functions.** Joux used multicollisions to break the concatenation of two hash functions: $x \mapsto H_1(x) \| H_2(x)$, with $H_1$ and $H_2$ two narrow-pipe hash functions, each with a state size of $n$ bits. Surprisingly, the concatenation offers the same security as a single hash function, even though it has a larger internal state and a larger output size.

In order to find a collision, the attacker first builds a multicollision $\mathcal{M}$ of size $2^{n/2}$ for $H_1$. Then she evaluates $H_2$ over all messages in the multicollision, in order to find two messages $(M, M') \in \mathcal{M}$ with $H_2(M) = H_2(M')$. This produces a collision for the concatenation with complexity $\tilde{O}(2^{n/2})$ because all messages in $\mathcal{M}$ have the same hash under $H_1$.

In order to find a preimage of a target value $\overline{H}_1 \| \overline{H}_2$, the attacker first builds a multicollision $\mathcal{M}$ of size $2^n$ for $H_1$ with final state $x_*$. Then she tries random blocks $r$ until she finds one such that $g_1(h_1(x_*, r)) = \overline{H}_1$ (therefore, $\forall M \in \mathcal{M}, H_1(M \| r) = \overline{H}_1$). Finally, she iterates over all messages $M \in \mathcal{M}$, until $H_2(M \| r) = \overline{H}_2$. This produces a preimage for the concatenation with complexity $\tilde{O}(2^n)$.

### 2.1.3 Expandable messages and second-preimage attack with a long challenge [KS05]

**Expandable message.** An expandable message is a large set of messages $\mathcal{M}$ of different lengths, such that all messages have the same digest. It is obtained with the same process as a multicollision, using messages pairs $(m, m')$ of different lengths at each step (see Figure 2.3).
<figure><img src="image_15.png" /><figcaption>**Figure 2.3:** Kelsey and Schneier's expandable message.</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>**Figure 2.4:** Second-preimage attack.</figcaption></figure>

**Second-preimage attack.** The Merkle-Damgård construction resists preimage attacks, but Kelsey and Schneier have proposed a second-preimage attack with complexity $2^t + 2^{n-t}$, assuming that we are given a challenge message $C$ of length $2^t$ (Figure 2.4).

The attacker first evaluates the hash function over the challenge message $C$, and stores all $2^t$ internal states $x_i$ encountered during the computation of $H(C)$, so that connecting to a random $x_i$ only requires $2^{n-t}$ random trials due to the birthday paradox. In order to deal with the MD strengthening, the attacker builds an expandable message $\mathcal{M}$ covering lengths up to $2^t$, with final state $x_*$. Then she tries random blocks $r$ until $h(x_*, r) = x_{i*} \in \{x_i\}$. We denote the final part of the challenge starting from $x_{i*}$ as $C_*$. Finally, the attacker selects the message $m$ of length $i^* - 1$ in the expandable message, and builds the second preimage as $m \parallel r \parallel C_*$. We have $h^*(m \parallel r) = x_{i*}$, therefore $h^*(m \parallel r \parallel C_*) = h^*(C)$; moreover the new message has the same length as the challenge, so that the finalization function is the same, and $H(m \parallel r \parallel C_*) = H(C)$.

The attack is not applicable to constructions with different compression functions $h^{(i)}$ at each step. Actually, this was one of the motivations to introduce the HAIFA framework.

### 2.1.4 Diamond structures and herding attack [KK06]

**Diamond structure.** Given a set of internal states $x_i$, the diamond structure of Kelsey and Kohno is a set of messages $S_i$ such that all internal states reach a common value $x_*$: $\forall i, h^*(x_i, S_i) = x_*$.

Kelsey and Kohno use an iterative procedure to reduce the size of the set $\{x_i\}$. Starting from $2^t$ internal states, they evaluate the compression function with $2^{n/2-t/2}$ random message blocks from each state. Each state is part of a collision with high probability: there are $2^{n/2-t/2}$ successors of a given state, and $2^{n/2+t/2}$ successors of the other states. They select a set of collisions without overlapping states, in order to obtain a new set of internal states for the next block with (essentially) half the size of the initial set. After $O(t)$ iterations, a single final state is reached, so that building the full structure requires $O(2^{(n+t)/2})$ operations. The structure has the shape of a binary tree (as shown by Figure 2.5), and the message $S_i$ corresponding to an input state $x_i$ is obtained by following the path from a leaf to the root.

**Herding attack.** Kelsey and Kohno use this structure to attack commitment schemes: an attacker can publish the hash value $g(x_*)$ (after the finalization function), and later build a message with this hash value using the diamond structure. This attack seems almost
<figure><img src="image_17.png" /><figcaption>**Figure 2.5:** Kelsey and Kohno's diamond structure.</figcaption></figure>

as hard as finding preimages, but it is in fact significantly easier for narrow-pipe hash functions. They describe two different scenarios:

* If the attacker has a small set of $2^t$ predefined messages $M_i$, she builds a diamond structure starting from the states obtained after processing the messages ($x_i = h^*(M_i)$) with complexity $2^{(n+t)/2}$. She publishes the common hash value $g(x_*)$, and she knows the messages $S_i$ such that $H(M_i \parallel S_i) = g(x_*)$ for each $i$.

* If the attacker wants to herd any possible message to a fixed hash value, she builds a diamond structure from a set of $2^{n/3}$ arbitrary internal states, with complexity $2^{2n/3}$. After publishing the common hash value $g(x_*)$, she can generate a message $S$ such that $H(C \parallel S) = g(x_*)$ for any challenge $C$ with complexity $2^{2n/3}$. She just has to evaluate $h^*(C \parallel r)$ for $2^{2n/3}$ choices of $r$, until reaching one of the states $x_i$ in the diamond structure. Then she recovers the message $S_i$ from the diamond structure to build the full message $S = r \parallel S_i$ with $H(C \parallel S) = H(C \parallel r \parallel S_i) = g(x_*)$.

## 2.2 Combiners

In order to build systems that are more resilient, a natural idea is to combine several cryptographic primitives, so that a weakness in one primitive does not break the whole system. In particular, this has been used in TLS version 1.0 and 1.1, with the XOR of two MAC algorithms (HMAC-MD5 and HMAC-SHA-1); the designers explain [RFC2246]: "In order to make the PRF as secure as possible, it uses two hash algorithms in a way which should guarantee its security if either algorithm remains secure."

There are two classical combiners for hash function: the concatenation combiner $H_1(M) \parallel H_2(M)$ and the XOR combiner $H_1(M) \oplus H_2(M)$ (Table 2.1). The concatenation combiner has the advantage of being *robust*: as long as one of the function is collision-resistant, the concatenation is collision-resistant. However, we have seen that it does not increase the security, because of the multicollision attack of Joux.

The security of the XOR combiner is not as well understood. Hoch and Shamir [HS08] proved that it is indifferentiable from a random oracle up to the birthday bound when the compression functions are modelled as random oracles (or even as *weak* random oracles). In particular, this implies security at least $2^{n/2}$ for collisions and preimages. For collision resistance, the bound is tight, since it is matched with the generic birthday attack bound. However, the security against preimage attacks is an open problem: there is a trivial attack with complexity $2^n$, but this leaves a gap between the best attack and the known security proof.

**Our results.** In the following we describe new attacks against the XOR combiner, when using two narrow-pipe hash functions with state size $n$ bits. We first describe a new
<table><caption>**Table 2.1:** Classical combiners with two *n*-bit narrow-pipe hash functions.</caption><thead><tr><th rowspan="2">Combiner</th><th colspan="2">Concatenation</th><th colspan="2">XOR</th></tr><tr><th>H<sub>1</sub>(M) || H<sub>2</sub>(M)</th><th></th><th>H<sub>1</sub>(M) &oplus; H<sub>2</sub>(M)</th><th></th></tr></thead><tbody><tr><td><strong>Robustness</strong></td><td colspan="2">Robust collision-resistance</td><td colspan="2">Robust PRF</td></tr><tr><td><strong>Security</strong> (up to log factors)</td><td>Attack</td><td>Proof</td><td>Attack</td><td>Proof</td></tr><tr><td><strong>Preimage security</strong></td><td></td><td></td><td></td><td></td></tr><tr><td>Ideal hash functions</td><td>2<sup>2n</sup></td><td>2<sup>2n</sup></td><td>2<sup>n</sup></td><td>2<sup>n</sup></td></tr><tr><td>HAIFA</td><td>2<sup>n</sup> [Jou04]</td><td>2<sup>n</sup></td><td>2<sup>5n/6</sup> § 2.4</td><td>2<sup>n/2</sup> [HS08]</td></tr><tr><td>Merkle-Damgård</td><td>2<sup>n</sup> [Jou04]</td><td>2<sup>n</sup></td><td>2<sup>3n/5</sup> § 2.6</td><td>2<sup>n/2</sup> [HS08]</td></tr><tr><td><strong>Collision security</strong></td><td></td><td></td><td></td><td></td></tr><tr><td>Ideal hash functions</td><td>2<sup>n</sup></td><td>2<sup>n</sup></td><td>2<sup>n/2</sup></td><td>2<sup>n/2</sup></td></tr><tr><td>HAIFA</td><td>2<sup>n/2</sup> [Jou04]</td><td>2<sup>n/2</sup></td><td>2<sup>n/2</sup></td><td>2<sup>n/2</sup> [HS08]</td></tr><tr><td>Merkle-Damgård</td><td>2<sup>n/2</sup> [Jou04]</td><td>2<sup>n/2</sup></td><td>2<sup>n/2</sup></td><td>2<sup>n/2</sup> [HS08]</td></tr></tbody></table>

structure, the interchange structure in Section 2.3. Using this structure, we obtain an attack with complexity $2^{5n/6}$ using short messages, applicable to any narrow-pipe hash function, in Section 2.4. Then we describe a different attack using cycles in the functional graph, with complexity $2^{3n/4}$, in Section 2.5. This attack uses long messages and is only applicable to Merkle-Damgård hash functions. Finally, we present an improved attack with complexity $2^{3n/5}$ in Section 2.6, combining ideas from the two previous attacks.

## 2.3 The interchange structure

We now consider two narrow-pipe hash functions $H_1$ and $H_2$ with compression functions respectively $h_1^{(i)}$ and $h_2^{(i)}$, and finalization functions $g_1$ and $g_2$. The interchange structure is a new structure to control simultaneously the behavior of two independent hash computations which share the same input message. An interchange structure is a set of messages $\mathcal{M}$ and two sets of internal states, $\mathcal{A}$ for $H_1$ and $\mathcal{B}$ for $H_2$, such that: for any value $A$ from $\mathcal{A}$ and any value $B$ from $\mathcal{B}$, we can derive a message $M_{A,B}$ from $\mathcal{M}$ such that $h_1^*(M_{A,B}) = A$ and $h_2^*(M_{A,B}) = B$. Therefore, we can select states from $\mathcal{A}$ and $\mathcal{B}$ independently using this structure.

The main idea is to consider several chains of internal states reached by processing a common message $\mathcal{M}$ from different starting points (note that the message $\mathcal{M}$ is not fixed in advance, but will be determined when building the structure). More precisely, the message $\mathcal{M}$ is denoted as the *primary message*, and divided in several chunks: $\mathcal{M} = M_0 \parallel M_1 \parallel \dots$ (as discussed later, a chunk will consist of several message blocks). We denote chains of internal states for $H_1$ as $a_j$, and the individual states of the chain as $a_j^i$, with $h_1^*(a_j^i, M_i) = a_j^{i+1}$. Similarly, we denote chains for $H_2$ as $b_k$, with $h_2^*(b_k^i, M_i) = b_k^{i+1}$. When considering both hash functions, message block $M_i$ leads from the pair of states $(a_j^i, b_k^i)$ to $(a_j^{i+1}, b_k^{i+1})$, which is denoted:

$$ (a_j^i, b_k^i) \stackrel{M_i}{\rightsquigarrow} (a_j^{i+1}, b_k^{i+1}). $$

### 2.3.1 Switch structure.

First we build special structures called *switches* in order to jump between chains in a controlled way. A switch allows jumping from a specific pair of chains $(a_{j_0}, b_{k_0})$ to a different pair of chains $(a_{j_0}, b_{k_1})$ using a secondary message chunk $M_i'$, in addition to the
normal transitions using chunk $M_i$ of the primary message $\mathcal{M}$:

$$ (a_j^i, b_k^i) \underset{\sim}{\overset{M_i}{\rightleftharpoons}} (a_j^{i+1}, b_k^{i+1}) : \quad \text{normal transition for each chain } (\forall j \forall k) \\ (a_{j_0}^i, b_{k_0}^i) \underset{\sim}{\overset{M'_i}{\rightleftharpoons}} (a_{j_0}^{i+1}, b_{k_1}^{i+1}) : \quad \text{jump from chains } (a_{j_0}, b_{k_0}) \text{ to } (a_{j_0}, b_{k_1}) $$

The main message chunk $M_i$ and the secondary message chunk $M'_i$ are determined when building the switch, with the following constraints:

$$ h_1^*(a_{j_0}^i, M_i) = h_1^*(a_{j_0}^i, M'_i) \qquad h_2^*(b_{k_1}^i, M_i) = h_2^*(b_{k_0}^i, M'_i) $$

We start with a multicollision of size $2^{n/2}$ satisfying the first equality, and select two messages $(M_i, M'_i)$ satisfying the second equality. The chains are defined by following the main message:

$$ a_j^{i+1} = h_1^*(a_j^i, M_i) \qquad b_k^{i+1} = h_2^*(b_k^i, M_i) $$

This defines a switch structure with complexity $\tilde{O}(2^{n/2})$. A simple example is depicted in Figure 2.6. We note that the secondary message chunk $M'_i$ should only be used when the state is $(a_{j_0}^i, b_{k_0}^i)$.

### 2.3.2 Interchange structure.

By combining several switches, we build an interchange structure with starting points $IV_1$ and $IV_2$ and ending points $\{A_j\}$ and $\{B_k\}$ ($0 \le j, k < 2^t$), so that we can select a message ending in any state $(A_j, B_k)$. Figure 2.7 shows one possible way to build such a structure, and Figure 2.8 shows how to select a given message in the structure. The chains $a_j, j \ne 0$ and $b_k, k \ne 0$ are initialized arbitrarily, and the message chunks are determined when building the switches.

An interchange structure with $2^t$ chains for each function requires about $2^{2t}$ switches. Since we can build a switch for a cost of $\tilde{O}(2^{n/2})$, the total structure is built with $\tilde{O}(2^{2t+n/2})$ operations.

## 2.4 Preimage attack against the XOR combiner

Finally, we use an interchange structure with ending points $\{A_j\}$ and $\{B_k\}$, ($0 \le j, k < 2^t$) to build a preimage attack as follows. Let $\overline{H}$ denote the target value. We select a random message block $r$, and we compute two lists by evaluating the compression functions after the interchange structure: $\{A'_j = g_1(h_1(A_j, r))\}$ and $\{B'_k = \overline{H} \oplus g_2(h_2(B_k, r))\}$. We expect a match between the lists with probability $2^{2t-n}$. After about $2^{n-2t}$ random choices of $r$, we get a match $(j^*, k^*)$: $g_1(h_1(A_{j^*}, r)) = \overline{H} \oplus g_2(h_2(B_{k^*}, r))$. Therefore, we construct a preimage of $\overline{H}$ by concatenating the message leading to $(A_{j^*}, B_{k^*})$ in the interchange structure, and the block $r$. We obtain

$$ H_1(M_{A_{j^*}, B_{k^*}} \parallel r) \oplus H_2(M_{A_{j^*}, B_{k^*}} \parallel r) = g_1(h_1(A_{j^*}, r)) \oplus g_2(h_2(B_{k^*}, r)) = \overline{H} $$

**Complexity analysis.** Building the interchange structures requires $\tilde{O}(2^{2t+n/2})$ evaluations of the compression function, while the preimage search requires about $2^{n-t}$ evaluations. The optimal complexity is reached when both steps take the same time, i.e. $t = n/6$. This gives a complexity of $\tilde{O}(2^{5n/6})$.
<figure><img src="image_18.png" /><figcaption>**Figure 2.6:** A single switch: jump from $(a_0, b_0)$ to $(a_0, b_1)$ by using $M'$ (dashed lines) instead of $M$ (solid lines).</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>**Figure 2.7:** Overview of an interchange structure.</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>**Figure 2.8:** Using of the interchange structure to reach output $(A_1, B_2)$.</figcaption></figure>
## 2.5 Preimage attack using cycles in the functional graph

We now assume that the hash functions $H_1$ and $H_2$ use the Merkle-Damgård construction, so that the compression function is the same at every step. This gives more freedom to the attacker, and more advanced techniques have been proposed to find preimages of the XOR combiner with a smaller complexity. In the section, we present an alternative description of the multi-cycle idea introduced in [BWG+17], to obtain a simplified attack with complexity $\tilde{O}(2^{3n/4})$.

This attack uses long messages that repeat a fixed message block $\beta$ (for instance, $\beta = 0$). When evaluating $h^*$ on such a message, we iterate a fixed function $x \mapsto h(x, \beta)$. Assuming that this function behaves as a random function, we expect to reach a cycle after roughly $2^{n/2}$ iterations, and the cycle has length roughly $2^{n/2}$. More precisely, there are several components in the functional graph with cycles of different lengths; the main component has expected size $0.76 \times 2^n$ with a cycle of expected size $\sqrt{\pi/8} \times 2^{n/2}$ [FO90].

We iterate the function $h_1(\cdot, \beta)$ starting from $IV_1$, until we reach a cycle; we denote the cyclic points as $\{A_j\}$ and its length as $\ell_1$. Similarly, we obtain a cycle $\{B_k\}$ of length $\ell_2$ for the function $h_2(\cdot, \beta)$ starting from $IV_2$. We assume that $\ell_1$ and $\ell_2$ are relatively prime<fnref n="1" /> with $\ell_1 < \ell_2$, and of the order of $2^{n/2}$.

This simple structure provides an alternative way to control independently the behavior of $H_1$ and $H_2$, by varying the length of a message $M = \beta^\lambda$. Indeed, with $\lambda > \mu$, with $\mu = \Theta(2^{n/2})$ the distance to reach both cycles, the final state is of form $(A_j, B_k)$; moreover, with a suitable choice of the indices of $A_j$ and $B_k$ we have:

$$h_1^*(\beta^\lambda) = A_\lambda \mod \ell_1$$

$$h_2^*(\beta^\lambda) = B_\lambda \mod \ell_2$$

Therefore, we obtain a message reaching a specific state $(A_{j^*}, B_{k^*})$ by solving a set of modular equations: $\lambda \equiv j^* \mod \ell_1$, $\lambda \equiv k^* \mod \ell_2$. Using the Chinese remainder theorem, we deduce a length $\lambda \ge \mu$ such that $h_1^*(\beta^\lambda) = A_{j^*}$ and $h_2^*(\beta^\lambda) = B_{k^*}$. For a random $(j^*, k^*)$, the length $\lambda$ is uniformly distributed between $\mu$ and $\mu + \ell_1\ell_2$.

The full attack requires an expandable message to deal with the MD strengthening. It produces a message of length $2^{3n/4}$ with the following steps, as shown in Figure 2.9:

1. Build an expandable message $\mathcal{M}$, with maximum length $2^{3n/4}$, with final states $s_1, s_2$.

2. Find the cycle $\{A_j\}$ of $h_1(\cdot, \beta)$ and the cycle $\{B_k\}$ of $h_2(\cdot, \beta)$, starting from $s_1$ and $s_2$.

3. For a random block $r$, match $\{g_1(h_1(A_j, r))\}$ and $\{g_2(h_2(B_k, r)) \oplus \overline{H}\}$.

If there is a match $(j^*, k^*)$, find the length $\lambda$ such that $h_1^*(s_1, \beta^\lambda) = A_{j^*}$ and $h_2^*(s_2, \beta^\lambda) = B_{k^*}$ using the Chinese remainder theorem.

If $\lambda < 2^{3n/4}$, select the message $m$ of length $2^{3n/4} - \lambda - 1$ in the expandable message. The preimage is $M = m \parallel \beta^\lambda \parallel r$.

Otherwise, repeat Step 3.

**Complexity analysis.** Step 1 has complexity $O(2^{3n/4})$ and step 2 has complexity $O(2^{n/2})$.

Each iteration of Step 3 (for each try of $r$) has complexity $O(2^{n/2})$. On average there is a single match $(j^*, k^*)$, and the probability that $\lambda < 2^{3n/4}$ is $2^{-n/4}$. Therefore, we expect $2^{n/4}$ iterations, with a total complexity $2^{3n/4}$.

<footnote n="1">¹This happens with probability $6/\pi^2 \approx 0.61$ for random integers.</footnote>
<figure><img src="image_21.png" /><figcaption>**Figure 2.9:** Preimage attack on the XOR combiner based on cycles.</figcaption></figure>

## 2.6 Improved preimage attack using cycles in the functional graph

Finally, we present the best known attack, with complexity $2^{3n/5}$. This unpublished attack is an improved variant of the attack given in [BDG+20], using the short cycle idea from [GHK+23]; it is a joined work with Xavier Bonnetain, Rachel Heim Boissier and André Schrottenloher.

The first improvement is to consider several connections from the IV to the cycle. In the final step, each target ($A_j, B_k$) can now be reached in many different ways, and this improves the probability that one of the corresponding messages $\beta^\lambda$ is short. In order to build the connections efficiently, we precompute $2^{3n/5}$ points in the functional graph, together with their distance to a fixed cyclic point. Therefore, starting from a random point, we only need $2^{2n/5}$ iteration to reach a precomputed point, and to deduce the connection to the cycle. Moreover, we use an interchange structure to provide independent choices of the connections in $H_1$ and $H_2$.

The second improvement is to select a value $\beta$ such that the cycles in the main component of $h_1(\cdot, \beta)$ and $h_2(\cdot, \beta)$ are shorter than average, with $\ell_1, \ell_2 \lesssim 2^{9n/20}$. This requires on average $2^{n/10}$ random choices of $\beta$, and each trial requires $2^{n/2}$ evaluations of the compression function in order to identify the main cycle. Thanks to the shorter cycles, the length $\lambda$ computed from the Chinese remainder theorem will be at most $\ell_1\ell_2 \approx 2^{9n/10}$.

The attack produces a message of length $2^{3n/5}$ with the following steps (see Figure 2.10):

1. Build an expandable message $\mathcal{M}$, with maximum length $2^{3n/5}$, with final state $s_1, s_2$.

2. Build an interchange structure $\mathcal{I}$ with $2^{n/20}$ endpoints $\{x_u\}$ and $\{y_v\}$, starting from $(s_1, s_2)$.

3. Find $\beta$ such that $\ell_1, \ell_2 \lesssim 2^{9n/20}$. Denote the cycle of $h_1(\cdot, \beta)$ as $\{A_j\}$ and the cycle of $h_2(\cdot, \beta)$ as $\{B_k\}$.

4. Precompute a set of $2^{3n/5}$ points in the main component of $h_1(\cdot, \beta)$ and $h_2(\cdot, \beta)$, with known distances to the main tree root.

5. Choose $2^{3n/20}$ random blocks $\rho_w$; for all interchange endpoints $x_u$ and $y_v$ compute the distance from $h_1(x_u, \rho_w)$ and $h_2(y_v, \rho_w)$ to the respective cycle.

6. For a random block $r$, match $\{g_1(h_1(A_j, r))\}$ and $\{g_2(h_2(B_k, r)) \oplus \bar{H}\}$.

If there is a match $(j^*, k^*)$, then for each $x_u, y_v, \rho_w$, find the length $\lambda$ such that $h_1^*(x_u, \rho_w \parallel \beta^\lambda) = A_{j^*}$ and $h_2^*(y_v, \rho_w \parallel \beta^\lambda) = B_{k^*}$ using the Chinese remainder theorem.
<figure><img src="image_22.png" /><figcaption>**Figure 2.10:** Improved preimage attack on the XOR combiner based on cycles.</figcaption></figure>

If $\lambda < 2^{3n/5}$, select the message $\mu$ such that $h_1^*(s_1, \mu) = x_u$, $h_2^*(s_2, \mu) = y_v$ in the interchange structure and the message $m$ of length $2^{3n/5} - \lambda - 2 - |\mu|$ in the expandable message. The preimage is $M = m \| \mu \| \rho_w \| \beta^\lambda \| r$.

Otherwise, repeat Step 6.

**Complexity analysis.** Step 1 has complexity $O(2^{3n/5})$; step 2 has complexity $\tilde{O}(2^{n/2 + 2 \times n/20}) = \tilde{O}(2^{3n/5})$; step 3 has complexity $\tilde{O}(2^{3n/5})$; step 4 has complexity $O(2^{3n/5})$.

Step 5 has complexity $O(2^{3n/20} \times 2^{n/20} \times 2^{2n/5}) = O(2^{3n/5})$ using the points precomputed at step 4. Since we use the main component of $h_1(\cdot, \beta)$ and $h_2(\cdot, \beta)$, each point $h_1(x_u, \rho_w)$ or $h_2(y_v, \rho_w)$ has a constant probability to reach the cycle.

Each iteration of Step 6 (for each try of $r$) has complexity $\ell_2 = O(2^{9n/20})$. There is a match $(j^*, k^*)$ with probability $O(2^{2 \times 9n/20 - n}) = O(2^{-n/10})$. In this case we obtain $2^{n/20} \times 2^{n/20} \times 2^{3n/20} = 2^{n/4}$ candidates $\lambda$; each one is smaller than $2^{3n/5}$ with probability $\Omega(2^{3n/5}/2^{2 \times 9n/20}) = \Omega(2^{-3n/10})$; in total, we obtain one $\lambda < 2^{3n/5}$ with probability $2^{n/4} \times 2^{-3n/10} = 2^{-n/20}$. Therefore, we expect $O(2^{3n/20})$ iterations of Step 6, with a total complexity $O(2^{3n/20} \times 2^{9n/20}) = O(2^{3n/5})$.

## 2.7 Conclusion

The interchange structure is a novel construction that gave the first generic attack against the XOR combiner. This result is rather surprising: the sum of two ideal narrow-pipe hash functions only has about $5n/6$ bits of security against preimage attacks. In particular, the sum is weaker than the initial functions. More advanced attacks reduce this complexity in the case of Merkle-Damgård hash functions: the best known attack has complexity $2^{3n/5}$. Since many practical hash functions are narrow-pipe (e.g. SHA-1, SHA-2, Whirlpool, RIPEMD, GOST, BLAKE, Skein...), the XOR combiner will usually provide a weaker security than the component hash functions.

In [BDG+20] (Appendix B), we also propose new attacks against more advanced combiners such as the “hash twice” construction, and the Zipper hash. These attacks benefit from the use of the interchange structure.
3. Chosen-Prefix Collision Attacks

This chapter is based on articles [LP19], [LP20] and [BL16b], found in Appendix C, D and E.

The main security property expected from cryptographic hash functions is collision resistance: it should be hard for an adversary to compute two distinct messages $M$ and $M'$ that map to the same hash value $H(M) = H(M')$. 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.

**Impact of collision attacks.** Collision attacks return random-looking messages $M$ and $M'$. In order to break a real-world application, they must somehow be hidden as junk inside meaningful messages.

An attacker can exploit the collision extension property: she chooses a common prefix $P$ before computing the collision $(M, M')$, and adds a common suffix $S$ after the collision. This results in colliding messages $H(P \parallel M \parallel S) = H(P \parallel M' \parallel S)$ where $P$ and $S$ are chosen meaningful messages. This technique was used to mount a “poisoned-message” attack against document formats with some level of programmability [DL05; GIS06; Alb17]. The attacker builds a prefix that hides the collision blocks by defining a variable, and uses an `if-then-else` switch depending on that variable to display two different contents. She obtains two messages with the same hash that display a different meaningful content, depending on which message of the colliding pair $(M, M')$ is inserted. As a concrete example, the SHA-1 collision of Stevens et al. [SBK+17] used this trick to produce two colliding PDFs.

However, this structure can be detected in the resulting document. More generally, this approach is usually not sufficient to break real-world applications.

**Chosen-prefix collision attacks.** A chosen-prefix collision attack [SLW07] is a stronger variant of collision attack. The attacker is challenged with two message prefixes $P$ and $P'$, and her goal is to compute two messages $M$ and $M'$ such that $H(P \parallel M) = H(P' \parallel M')$. Chosen-prefix (CP) collisions are usually harder to produce than (identical-prefix) collisions, but the practical impact of such an attack is more significant. A CP collision attack indicates the ability of an attacker to obtain a collision even though random differences (thus potentially some meaningful information) were inserted as message prefix.

**Application to digital certificates.** A digital certificate is essentially a signature of an identity and a cryptographic key: $C = \text{sign}(\text{id}, k)$. The user presents her identity information and cryptographic key to a certificate authority who computes the signature. In practice, the signature is computed over a hash: $C = \text{sign}(H(\text{id} \parallel k))$. Therefore, if an attacker generates a collision $H(\text{id} \parallel k) = H(\text{id}' \parallel k')$, she can request a certificate for $(\text{id}, k)$ (assuming the identity id is correct) and reuse the signature as a certificate for $(\text{id}', k')$.
<figure><img src="image_23.png" /><figcaption>**Figure 3.1:** Colliding certificates using an identical-prefix collision.</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>**Figure 3.2:** Colliding certificates using a chosen-prefix collision.</figcaption></figure>

Using an identical-prefix collision attack, it is hard to generate a collision with different meaningful identities. However, it is possible to generate a collision with two different keys for the same identity. The attacker starts the collision attack after processing *id*, and hides the colliding messages *M*, *M*′ inside the cryptographic keys (Figure 3.1). This was demonstrated on X.509 certificated signed with MD5 [LW05]. The attacker generates RSA moduli with known factorization by choosing only the low-order bits.

A chosen-prefix collision gives more freedom to the attacker. She can use two different identities *id*, *id*′ as prefixes, and compute a collision (Figure 3.2). If *id* is her identity, and *id*′ the identity of a victim, this results in an impersonation attack, because she obtains a valid certificate under the name of *id*′. This was demonstrated on X.509 certificates signed with MD5 [SLW07], and a more advanced variant of this attack resulted in a rogue certificate authority [SSA+09].

**Our results.** In this chapter we present new chosen-prefix collision attacks, and new applications of CP collisions. In particular, we have computed the first SHA-1 CP collision. The main goal of those results is to demonstrate that weaknesses of MD5 and SHA-1 are not just theoretical issues: they can be exploited to mount practical attacks against real-world systems.

We assume that the hash function considered is an *n*-bit narrow pipe primitive, based on a Merkle-Damgård-like operating mode. In addition, we assume that the compression function is built upon a block cipher in Davies-Meyer mode: $h(x, m) = E_m(x) + x$, with + a group operation (MD5 and SHA-1 use modular addition).

## 3.1 From collisions to chosen-prefix collisions

The most widely used hash functions since the 1990's are based on similar design principles, and are collectively called the MD-SHA family: MD4 [Riv91], MD5 [RFC1321], SHA-1 [SHA1], SHA-2 [SHA2] (SHA-2 is a family of functions including SHA-224, SHA-256, SHA-384 and SHA-512). There is a large body of previous work on cryptanalysis of the MD-SHA family. In particular, the early members of the family have been broken in practice, with actual collisions given for MD4 [Dob96; WLF+05], MD5 [WY05], and SHA-1 [WYY05; SBK+17] (Table 3.1). On the other hand, SHA-2 is still considered secure. SHA-3 does not follow these design principles and is also considered secure.

### 3.1.1 Cryptanalysis of the MD-SHA family

Collision attacks against MD-SHA hash functions are based on differential cryptanalysis, where an attacker manages to somewhat control the output of the compression function. Several important ideas were used to turn differential cryptanalysis into an effective tool against hash functions:

**Local collisions [Dob97].** An important trick to build high probability differential trails is to construct local collisions: small message differences whose influence is immediately corrected with other message differences inserted in the subsequent steps. In MD4
and MD5, this trick ensures many rounds without any difference in the internal state, so that those rounds don't contribute to the probability.

**Linearization [CJ98].** In order to build differential trails with high probability for SHA-1, a linearized version of the step function is used. Thanks to the linearity of the message expansion, a combination of disturbances and corrections gives a series of local collisions. Differential trails with a low-weight output difference $\delta_O$ can be used to find near-collisions in the compression function (i.e. two outputs that are close to a collision).

**Message modification [BC04; WYY05].** In a differential attack against a hash function, the attacker can choose messages that directly satisfy some of the constraints of the path, because there is no secret key. While the conditions in the first steps are easy to satisfy, more advanced techniques have been introduced to extend the usage of these degrees of freedom to later rounds in order to speed-up collision search: neutral bits (firstly introduced for cryptanalysis of SHA-0 [BC04; BCJ+05]), message modifications [WYY05] and boomerangs/tunnels [Kli06; JP07].

**Non-linear trails [WYY05].** In order to get more flexibility on the differential trails, the first few steps can use non-linearity instead of following the constraints of the linearized step function. This does not affect the complexity of the search for conforming messages (thanks to message modification techniques), but it allows building trails from an arbitrary input difference to a good fixed output difference $\delta_O$ (or its opposite $-\delta_O$).

**Multi-block technique [CJ98; WYY05].** The multi-block technique takes advantage of the Davies-Meyer construction used inside the compression function ($h(x, m) = E_m(x) + x$). Because of the feed-forward, an attacker can use several differential trails in $E$, and several near-collisions blocks, to iteratively affect the internal state. In particular, using non-linearity in the first steps, she can derive two related trails $0 \stackrel{\delta_M}{\rightleftharpoons} \delta_O$ and $\delta_O \stackrel{-\delta_M}{\rightleftharpoons} -\delta_O$ in $E$ from a single linear trail, by swapping the message pair. When conforming messages are found for each block, this leads to a collision because the internal state differences cancel out (see Figure 3.3).

**Birthday phase for chosen-prefix collisions [SLW07; Ste13].** Differential techniques have also been used for chosen-prefix collision attacks. An attacker can relax the last steps of the differential trail to allow a set $\mathcal{D}$ of output differences rather than a single $\delta_O$. She can also use several differential trails, and use the union of the corresponding sets. Starting from two different prefixes $P, P'$, the chosen-prefix collision attack has two stages (see Figure 3.4):

* In the *birthday stage*, the attacker uses a generic collision search with message blocks $m_0, m'_0$ to reach a difference $\delta = H(P' \parallel m'_0) - H(P \parallel m_0)$ in $\mathcal{D}$ with complexity roughly $\sqrt{\pi \cdot 2^n / |\mathcal{D}|}$.

* In the *near-collision stage*, she builds a differential trail $\delta \rightsquigarrow -\delta$ using non-linearity in the first steps, and searches for a conforming message to build the chosen-prefix collision.

**Multi-block for chosen-prefix collisions [SLW07].** If a collection of differential trails affecting separate parts of the internal state is available, chosen-prefix collision attacks can be greatly improved. In particular, if an arbitrary input difference $\delta_R$ can be decomposed as $\delta_R = -(\delta_O^{(1)} + \delta_O^{(2)} + \cdots + \delta_O^{(r)})$, where each $\delta_O^{(i)}$ can be reached as the output of a differential trail, the attacker just has to find near-collision blocks with output differences $\delta_O^{(1)}, \dots, \delta_O^{(r)}$ (see Figure 3.5).
Alternatively, if this only covers a subset of input differences, the multi-block technique is combined with a birthday stage. This approach was notably applied to MD5 [SLW07].

### 3.1.2 New techniques for chosen-prefix collisions

The CP collision attack against MD5 [SLW07] uses dedicated differential paths in order to control separate parts of the internal state difference. This requires dedicated analysis to find suitable trails. In this section we present a more generic way to build CP collision attacks, reusing an existing collision attacks. This is particularly well-suited to SHA-1, given the limited freedom in the construction of differential trails.

The main improvement comes from how we use multiple near-collision blocks. For instance, let us consider a trail allowing a set $\mathcal{D}$ of output differences. Using two near-collision blocks we can start from any difference in the set $\mathcal{S} := \{\delta_1 + \delta_2 : \delta_1, \delta_2 \in \mathcal{D}\}$, and cancel it iteratively with a first block following a trail $\delta_1 + \delta_2 \rightsquigarrow -\delta_1$ and a second block following a trail $\delta_2 \rightsquigarrow -\delta_2$. The set $\mathcal{S}$ grows with the number of blocks: this reduces the cost of the birthday search in exchange for a more expensive near-collision stage.

While there are previous chosen-prefix collision attacks using several near-collision blocks [LPR+07; Pey07; SLW07; SSA+09; MRS15], these attacks use a collection of differential trails to impact different parts of the state (each block uses a different trail). Previous chosen-prefix collision attacks based on a single trail (against SHA-1 [Ste13] and MD5 [SSA+09, Section 6]) used only one near-collision block. On the opposite, our technique can be used with a single differential trail, or a collection of trails without any special property.

**Overview of the attack.** Our strategy is composed of two phases. After processing the two prefixes, the first phase uses a generic birthday search to reach a chaining value difference in a predefined set $\mathcal{S}$. In the second phase, we use several near-collision blocks to map the chaining variable difference to a collision, using techniques developed for collision attacks.

The second phase is the most challenging. The attacker uses a graph $\mathcal{G}$, where each node represents a chaining variable difference in the set $\mathcal{S}$. A directed edge from node $i$ to node $j$ represents a way for an attacker to reach chaining variable difference $j$ from difference $i$ with a single message block; the details of the differential trail are attached to the edge. A path in the graph from a node $\delta$ to the node 0 corresponds to a sequence of output differences that ends up with a collision.

### 3.1.3 Building the set $\mathcal{S}$ and the graph $\mathcal{G}$

We consider that the attacker knows some good core differential trails for the internal block cipher $E$, that is differential trails that go from early steps to late steps of $E$. We denote the set of all possible output differences as $\mathcal{D}$ (in particular, we have $0 \in \mathcal{D}$, and $\delta \in \mathcal{D} \iff -\delta \in \mathcal{D}$ because of symmetries).

We further assume that any input difference for $E$ can be mapped to any of the core differential trails inside the primitive. With functions of the MD-SHA family, this is achieved with the non-linear part of the trail in the first steps of the function.

**Simple graph.** For simplicity, we fix a maximum number of block $t$ for the near-collision phase. We deduce that the set of differences that can be corrected is

$$ \mathcal{S} := \{\delta_1 + \delta_2 + \cdots \delta_t : \delta_1, \delta_2, \cdots \delta_t \in \mathcal{D}\}. $$

We build the graph $\mathcal{G}$ by adding an edge between nodes $i$ and $j$ when $i - j \in \mathcal{D}$. We obtain a simple attack by taking the shortest paths in this graph, as illustrated by Figure 3.6.
<figure><img src="image_25.png" /><figcaption>**Figure 3.3:** 2-block collision attack using a linear trail $\delta_I \stackrel{\delta_M}{\rightleftharpoons} \delta_O$ and two non-linear trails $0 \rightsquigarrow \delta_I$ and $\delta_O \rightsquigarrow -\delta_I$. Green values between bracket represent differences in the state.</figcaption></figure>

<figure><img src="image_26.png" /><figcaption>**Figure 3.4:** Single-block chosen-prefix collision attack with a birthday stage. The linear trail $\delta_I \rightsquigarrow \delta_O$ is relaxed to reach a set $S$ of feasible differences.</figcaption></figure>

<figure><img src="image_27.png" /><figcaption>**Figure 3.5:** Multi-block chosen-prefix collision attack. We assume that an arbitrary difference $\delta_R$ can be decomposed as $\delta_R = -(\delta_O^{(1)} + \delta_O^{(2)} + \cdots + \delta_O^{(r)})$, where each $\delta_O^{(i)}$ can be reached as the output of a differential trail.</figcaption></figure>

<figure><img src="image_28.png" /><figcaption>**Figure 3.6:** Graph search.</figcaption></figure>

<figure><img src="image_29.png" /><figcaption>**Figure 3.7:** With clustering.</figcaption></figure>

<figure><img src="image_30.png" /><figcaption>**Figure 3.8:** Bi-directional.</figcaption></figure>
**Clustering.** In order to minimize the complexity of the near-collision phase of the attack, we use a clustering technique to exploit multiple paths in the graph (see Figure 3.7). Indeed, the search for near-collision blocks is a random process that generates many message pairs following the trail until some intermediate step, and verifies the final difference. Therefore, the attacker does not have to commit to a fixed output difference. If a single core trail produces several output differences that correspond to useful edges in the graph, the attacker can run the search for near-collision blocks and stop as soon as one of them is obtained.

Concretely, let us assume we have two output differences $\delta_1$ and $\delta_2$ compatible with the same differential trail, that can each be reached with a cost of $C_{\text{block}}$. There are two different ways to erase a difference $-\delta_1 - \delta_2$ in the state:

* a block with difference $\delta_1$, followed by a block with difference $\delta_2$;

* a block with difference $\delta_2$, followed by a block with difference $\delta_1$.

If we don't decide in advance the target difference for the first block, the search is expected to reach either $\delta_1$ or $\delta_2$ with a cost of only $0.5 C_{\text{block}}$, leading to an attack complexity of $1.5 C_{\text{block}}$ rather than $2 C_{\text{block}}$.

**Bi-directional search.** Since the CP collision attack is essentially a path search in a graph, we use a bi-directional search to reduce the size of the precomputed graph. More precisely, when we evaluate the cost of a node, instead of just looking it up in the graph, we recompute all edges starting from the current node to see if they reach the graph. Indeed, the complexity of the birthday search is essentially $\sqrt{\pi \cdot 2^n / |S|}$, therefore we need a large set $S$, but storing it becomes an issue.

This is illustrated by Figure 3.8, where black dots correspond to precomputed nodes stored in the graph, and white dots are only computed during the online phase. We can't compute exactly the size of the implicit graph, but we can evaluate it experimentally.

**Implicit edges.** We build the graph with a fixed set $\mathcal{D}$ of potential output differences with high probability. However, the messages produced by the near-collision block search can reach many other output differences. Some of them can be useful in our attack, even if they have a lower probability: we can use a block as long as the new state difference is closer to a collision. Therefore, during the near-collision phase, we also keep blocks that don't correspond to a difference in $\mathcal{D}$, and look up the new state difference in the graph.

## 3.2 Chosen-prefix collision attack against SHA-1

To apply the method to SHA-1, we reuse as much as possible the details of the collision attack from [SBK+17]. In particular, we use the best core trail known for attacks against SHA-1, and we reuse the GPU code from the collision attack [SBK+17]. We denote the complexity to find a block conforming to the trail (with an optimal output difference) as $C_{\text{block}}$; this cost was estimated as $C_{\text{block}} = 2^{64.7}$ SHA-1 evaluations on a GTX-970 GPU.

### 3.2.1 Improvements to near-collision block search

As a first contribution, we propose improvements to the collision attack from Eurocrypt 2013 [Ste13] and its GPU implementation from Crypto 2017 [SBK+17]. Through better use of degrees of freedom (message modifications and boomerangs) and code improvements, we gained a factor between 8 and 10 (depending on GPU architecture) on the time needed to find a conforming block.

With these improvements, we obtain the cost of a near-collision block as $C_{\text{block}} = 2^{61.2}$ SHA-1 evaluations on a GTX-970 GPU, and $C_{\text{block}} = 2^{61.6}$ on a GTX 1060.
### 3.2.2 Parameters of the attack

**Differential trails.** As in the previous chosen-prefix collision attack on SHA-1 [Ste13], we consider several variants of the core trail by changing some of the message constraints in the last steps (in particular, we flip the sign of some message bits), and we relax the last steps to reach a larger set of output difference. However, we do this more exhaustively than Stevens: he only describes a set $\mathcal{D}$ of size 192 with cost at most $1.15 \cdot C_{\text{block}}$, but we found a set of size 8768 with cost at most $8 \cdot C_{\text{block}}$, including 576 values with cost at most $1.15 \cdot C_{\text{block}}$. In particular, this directly leads to an improvement of the single-block chosen-prefix collision from [Ste13], with complexity roughly $\sqrt{\pi \cdot 2^{160}/8768} \approx 2^{74.3}$, rather than $\sqrt{\pi \cdot 2^{160}/192} \approx 2^{77}$.

**Building the graph $\mathcal{G}$.** We first build a graph with all nodes that are reachable with a path of cost at most 24 $C_{\text{block}}$ and up to 10 blocks. This results in a graph with $2^{36.2}$ nodes, which requires 2 TB of storage (storing only the nodes and their cost). Using the bi-directional method above, our simulations show that there are around $2^{38}$ differences $\delta$ that can be used in this attack, with at most 11 blocks. Further simulations show that the average cost from a node in the graph to a collision is around $2 C_{\text{block}}$ when using implicit edges.

### 3.2.3 Running the attack in practice

Running an attack on this scale is a significant challenge. Following previous work [KPS15; SBK+17], we use GPUs for this computation, because they offer a better performance/price ratio.

Overall, for the attack parameters chosen, the birthday part costs about $2^{62.05}$ SHA-1 computations, while the near-collision part is expected to require $1 C_{\text{block}}$ for the last block, and $1 C_{\text{block}}$ in total for all the previous blocks. The total complexity is estimated as equivalent to $2^{63.5}$ SHA-1 evaluations on a GTX 1060 GPU, less than four times higher than the cost of an identical-prefix collision. Since SHA-1 is a 160-bit hash function, the expected security level for (CP) collision attacks is $2^{80}$.

**A GPU cluster.** When running this computation in 2019, we originally estimated that our attack would cost around US$160k by renting GPUs from a cloud provider such as Amazon or Google (using spot or preemptible prices). However, since our computations do not require communication between the GPUs, nor fancy inter-GPU task scheduling, we instead rented cheaper GPUs from providers that use gaming or mining cards in consumer-grade PCs, rather than the datacenter-grade hardware used by big cloud providers. Services like **gpuserversrental.com** rented GTX 1060 or GTX 1080 GPUs for a price below 5 cents per month per CUDA core; this translates to a total cost around US$75k to compute a chosen-prefix collision.

Our cluster was made of 150 machines with 6 GPU each (with a mix of GTX 1060 3G, and GTX 1060 6G), and one master node with two 2 TB hard drives in a RAID configuration. The master node had a Core i7 CPU, but the GPU nodes had low-end Pentium or Celeron CPU with two cores.

**Running the attack.** The birthday phase is relatively straightforward, using the parallel collision search of van Oorschot and Wiener [vW99].

The near-collision phase is very technical and very complex. Every time a block is found, we have to prepare the search for the next block. This first requires traversing the graph $\mathcal{G}$ to find the parameters for the next block, and to generate a new non-linear trail for the early steps. We used tools similar to [DR06], which take a lot of parametrization and trial-and-error to have a proper non-linear trail that fits nicely with the core differential
path. This was automated to some extent, but still took between a few hours and a few days of manual work to prepare for each block.

After two months of computations, we successfully obtained a CP collision for SHA-1. Our collision uses only 9 near-collision blocks because some implicit edges correspond to shortcuts in the graph.

## 3.3 Impersonation attack against the PGP Web-of-trust

Our demonstration of a chosen-prefix collision targets the PGP/GnuPG Web of Trust. More precisely, our goal is to create two PGP keys with different UserIDs, so that key B is a legitimate key for Bob (to be signed by the Web of Trust), but the signature can be transferred to key A which is a forged key with Alice's ID. This will succeed if the hash values of the identity certificates collide, as in previous attacks against X.509 MD5-based certificates [SLW07; SSA+09]. Moreover, due to details of the PGP/GnuPG certificate structure, our attack can reuse a single CP collision to target arbitrary users Alice and Bob: for each victim, the attacker only needs to create a new key embedding the collision, and to collect a SHA-1 signature. This is arguably the first practical attack against a real-world security application using weaknesses of SHA-1.

### 3.3.1 Exploiting a chosen-prefix collision

We focus on the identity certificates that will be hashed and signed. Following [RFC4880], the hash computation done during certificate signing includes the public key packet, then a UserID or user attribute packet, and finally a signature metadata packet and a trailer. Our attack uses two public keys of different sizes, so that the remaining fields to be signed are misaligned, and we can hide the UserID of key A in another field of key B. Following RFC 4880, the signature metadata packet is protected by a length value at the beginning *and at the end*, so that we have to use the same signature metadata packet in key A and key B (we cannot stuff data in the hashed subpacket). Therefore, we can only play with the UserID and/or user attribute packets. Still, a user attribute packet with a JPEG image gives us enough freedom to build colliding certificates, because typical JPEG readers ignore any bytes after the End of Image marker (ff d9). This gives us some freedom to stuff arbitrary data in the certificate.

More precisely, we build keys A and B as follows. Key A contains an 8192-bit RSA public key, and a UserID field corresponding to Alice. On the other hand, key B contains a 6144-bit RSA public key, and a user attribute containing a JPEG image.

**Content of identity certificates.** Figure 3.9 shows a template of the values included in the identity certificate: those values are hashed when signing a key, and we want the two hashes to collide. In this example, the UserID field of key A contains "Alice <alice@example.com>", and the image in key B is a valid JPEG image that will be padded with junk data after the End of Image marker. The real JPEG file is 181 bytes long<fnref n="1" /> (from ff d8 to ff d9), and it is padded with 81 bytes, so that the file included in the key is 262 bytes long (here the padding includes 46 bytes corresponding to the end of the modulus of key A, 5 bytes corresponding to the exponent of key A, and 30 bytes corresponding to Alice's UserID).

After computing the CP collision, we obtain a pair of keys with colliding certificates:

* https://sha-mbles.github.io/alice.asc

* https://sha-mbles.github.io/bob.asc

<footnote n="1">¹Building a JPEG image smaller than 256 bytes is not easy, but it is possible.</footnote>
<figure><img src="image_31.png" /><figcaption>**Figure 3.9:** Construction of colliding OpenPGP identity certificates.</figcaption></figure>

The colors correspond to the packets hashed when computing the signature: first, the **public key packet** (with header), then the **UserID** or **user attribute**, and finally the **signature packet and trailer**. Arrows show when a value is chosen in one key and copied to the other.

We use the following symbols:

* 01 Value fixed by the specifications, or chosen in advance (length of fields, UserID, ...)

* ?? Bytes determined by the chosen-prefix collision algorithm

* !! Bytes selected after finding the collision, to generate an RSA modulus

* .. Bytes that are copied from the other certificate

* ** Time-stamps chosen by the attacker

* $$ Time-stamp chosen by the signer

Underlined values correspond to packet headers (type and length).
<figure><img src="image_32.png" /><figcaption>**Figure 3.10: SIGMA's** A mutually-authenticated key exchange protocol.</figcaption></figure>

## 3.4 Transcript collision attacks

Many popular cryptographic protocols have been defined using hash functions MD5 and SHA-1, which are vulnerable to collision attacks and chosen-prefix collision attacks.

Practitioners commonly believe that collisions only affect non-repudiable signatures (like certificates), but that signatures and MACs used within protocols are safe as long as they include unpredictable contents, such as nonces [RFC4894; RFC4270]. In these cases, protocol folklore says that a second preimage attack would be required to break these protocols, and such attacks are still considered hard, even for MD5.

Conversely, theoretical cryptographers routinely assume collision-resistance in proofs of security for these protocols. For example, various proofs of TLS [JKS+12; KPW13; GKS13] assume collision-resistance even though the most popular hash functions used in TLS at the time were MD5 and SHA-1. Whom shall we believe? Either it is the case that cryptographic proofs of these protocols are based on too-strong (i.e. false) assumptions that should be weakened, or that practitioners are wrong and collision resistance is required for protocol security.

In this section, we clarify this situation by investigating the use of hash functions in the authenticated key exchanges. We describe a generic class of attacks called transcript collision attacks, demonstrating that, contrary to common belief, collisions can be used to break fundamental security guarantees of these protocols.

### 3.4.1 Authenticated Key Exchange

Authenticated Key Exchange (AKE) protocols are executed between two parties, usually called client and server or initiator and responder, in order to establish a shared session key that can be used to encrypt subsequent messages. A typical example is the SIGMA' protocol depicted in Figure 3.10. This protocol is a variant of the basic SIGMA (sign-and-mac) protocol from [Kra03] which served as the inspiration for the key exchanges used in many protocols including IKE, OTR, and JFK.

In SIGMA', the initiator $A$ first sends a message $m_1$ to $B$, consisting of a Diffie-Hellman public value $g^x$, along with some protocol-specific parameters $info_A$ that may include, for example, a nonce, a protocol version, a proposed ciphersuite, etc. $B$ responds with a message $m_2$ containing its own Diffie-Hellman public value $g^y$ and some parameters $info_B$. $A$ and $B$ have now completed an anonymous Diffie-Hellman exchange and can compute the shared secret $g^{xy}$ and use it to derive the session key. However, before using the session key, they authenticate each other by exchanging digital signatures over the protocol transcript $H(m_1 || m_2)$ using their long-term signing keys ($sk_A, sk_B$). (Digital signature
<figure><img src="image_33.png" /><figcaption>**Figure 3.11:** Man-in-the-middle credential forwarding attack on SIGMA'. The attacker creates a transcript collision by tampering with the messages shown in red. At the end of the protocol, the client and server have seemingly authenticated each other, but the attacker knows both connection keys, and hence can read or write any data.</figcaption></figure>

algorithms typically hash their arguments before signing them, and we have chosen to make this hashing explicit in our presentation of SIGMA'.) By signing the transcript, A and B verify that they agree upon all the elements of the key exchange, and in particular, that a network attacker has not tampered with the messages. Finally, A and B also prove to each other that they know the session key $g^{xy}$ by exchanging MACs computed with this key over their own identities.

Like other AKE protocols, SIGMA' aims to prevent message tampering, peer impersonation, and session key leakage, even if the network and other clients and servers are under the control of the adversary. Formally, authenticating the transcript guarantees matching conversations, that is, that the two parties agree on each other's identity and other important protocol parameters.

### 3.4.2 Transcript collision attacks

The alert reader will notice that SIGMA' does not in fact guarantee that A and B agree on the message sequence $m_1 \parallel m_2$; it only guarantees that they agree on the hash of this sequence. What if a network attacker were to tamper with the messages, so that A and B see different message sequences but the hashes of the two sequences is the same? In that case, the protocol will proceed to completion but the integrity and authentication guarantees no longer hold.

Figure 3.11 illustrates such an attack in the man-in-the-middle setting. The attacker intercepts messages sent between A and B. She sends her own message $m'_1 = g^{x'} \parallel info'_A$ to B and her own response $m'_2 = g^{y'} \parallel info'_B$ to A. Suppose she can choose these messages such that the authenticated transcripts match:

$$H(m_1 \parallel m'_2) = H(m'_1 \parallel m_2)$$

We call this a transcript collision. Now, the attacker can simply forward A's signature over this transcript to B and vice versa. A and B will accept the signatures since the hashed transcripts match and the signing keys are correct. However, the attacker knows the session
keys ($g^{x'y}, g^{xy'}$) on both connections (since she knows $x', y'$). Hence, the attacker has fully hijacked both connections and can now send messages to B pretending to be A and to A pretending to be B. This is an impersonation attack that breaks peer authentication.

If the boundaries between the messages $m_1$ and $m_2$ are not clearly demarcated, there are a number of trivial attacks that can ensure that $m_1 \parallel m'_2 = m'_1 \parallel m_2$ with no need for hash collisions. In the following examples, we will assume that each message (and each message field) is prefixed with its length.

### 3.4.3 A generic transcript collision

The main challenge in implementing the attack in Figure 3.11 is that the attacker has to compute the messages $m'_1$ and $m'_2$ after receiving $m_1$ but before the responder has sent her response $m_2$. The feasibility of the attack depends on the contents and formats of these messages.

Suppose the responder B always sends the same message $m_2$ for every request; that is, she uses the same (static) Diffie-Hellman value $g^y$ and same parameters $info_B$. This situation occurs, for example in protocols like QUIC, where the server uses a static configuration. In that case, after receiving $m_1$, the attacker can compute a transcript collision by finding $x', y'$, $info'_A$, $info'_B$ such that $H(m_1 \parallel m'_2) = H(m'_1 \parallel m_2)$. This requires $2^{n/2}$ hash evaluations, because of the birthday paradox.

### 3.4.4 A chosen-prefix transcript collision

We now consider a more efficient attack that works even when B sends an unpredictable $m_2$ containing a fresh (ephemeral) Diffie-Hellman value $g^y$ and a previously unknown $info_B$. However, we assume that the length of $m_2$ ($\ell_m$) is fixed and known to the attacker. Moreover, suppose that in the second message of SIGMA', $info_B$ is allowed to have arbitrary length and arbitrary contents. That is, even if $info_B$ has junk data at the end, A will accept the message. Specifically, suppose that $info_B = len_B \parallel data_B$ where $data_B$ is opaque data that will be ignored by A. Such “collision-friendly” messages exist in TLS, IKE, and SSH.

Under this condition, the attacker can compute a transcript collision by constructing a chosen-prefix collision ($C_1, C_2$) of $\ell_1$ and $\ell_2$ bytes respectively, such that:

$$H(m_1 \parallel \underbrace{[g^{y'} \parallel \text{len}'_B \parallel C_1 \parallel -]}_{m'_2}) = H(\underbrace{[g^{x'} \parallel C_2]}_{m'_1})$$

where $\text{len}'_B = \ell_1 + \ell_m$. Note that we have left empty space (written $-$) of size $\ell_m$ bytes that still needs to be filled after $C_1$ in $info'_B$.

After receiving $m_1$ from A and computing $C_1, C_2$, the attacker sends $m'_1$ to B. When B responds with $m_2$ (of size $\ell_m$ bytes), she stuffs $m_2$ at the end of $info'_B$ (in place of $-$) and sends $m'_2$ to A. Due to the collision extension property, we have:

$$H(m_1 \parallel \underbrace{[g^{y'} \parallel \text{len}'_B \parallel C_1 \parallel m_2]}_{m'_2}) = H(\underbrace{[g^{x'} \parallel C_2]}_{m'_1} \parallel m_2)$$

That is, the attacker has obtained a transcript collision and the impersonation attack succeeds.
<table><caption>**Table 3.1:** Complexity of collision attacks (SHA-1 equivalents on GTX 1060 GPU)</caption><thead><tr><th rowspan="2">Function</th><th rowspan="2">MD5 (n = 128)</th><th colspan="2">SHA-1 (n = 160)</th><th rowspan="2">MD5 || SHA-1<br>(w/ multicollision)</th></tr><tr><th>previous</th><th>§ 3.2</th></tr></thead><tbody><tr><td>Collision</td><td>2<sup>16</sup> [SSA+09]</td><td>2<sup>64.7</sup> [SBK+17]</td><td>2<sup>61.6</sup></td><td>2<sup>67.6</sup></td></tr><tr><td>CP collision</td><td>2<sup>39.1</sup> [SSA+09]</td><td>2<sup>77.1</sup> [Ste13]</td><td>2<sup>63.5</sup></td><td>2<sup>67.6</sup></td></tr></tbody></table>

### 3.4.5 Application to TLS, IKE and SSH

The transcript-collision attack exploits hash collisions in combination with flexible protocol-specific message formats. This trick can be applied to several mainstream protocols such as TLS, IKE, and SSH.

In [BL16b] (Appendix E), we demonstrate how a man-in-the-middle attacker can impersonate TLS 1.2 clients, TLS 1.3 servers, and IKEv2 initiators. We also show how a network attacker can downgrade TLS 1.1 and SSH-2 connections to use weak ciphers. We have implemented proofs-of-concept exploit demos for three of these attacks to demonstrate their practicality, and provide attack complexities for the others. We believe that ours are the first hash collision-based attacks on the cryptographic constructions within these protocols. This settles the debate on whether the security of mainstream cryptographic protocols depends on collision resistance. We recommend that weak hash functions like MD5 and SHA-1 should be disabled from Internet protocols.

## 3.5 Conclusion

Chosen-prefix collisions have first been demonstrated on MD5 in 2007 [SLW07]. In this chapter we demonstrated them on SHA-1 for the first time. We summarize the complexity of known attacks in Table 3.1. We also provide several new applications of CP collisions, clearly showing that MD5 and SHA-1 signatures can be abused in practice. The transcript-collision attacks are hard to deploy in the wild because the CP collision must be computed online; on the other hand, the PGP impersonation attack is easy to mount because the CP collision is a precomputation, independent of the target identity.

**Responsible disclosure.** Our transcript-collision attacks on TLS were responsibly disclosed under the name SLOTH<fnref n="2" /> in 2015 (CVE-2015-7575) and have resulted in security updates to several TLS libraries. Our chosen-prefix attack on SHA-1 was also responsibly disclosed under the name Shambles<fnref n="3" /> in 2019 (CVE-2019-14855). In particular, we contacted the authors of GnuPG and OpenSSL.

### 3.5.1 SHA-1 usage and deprecation

SHA-1 has been known to be broken since 2005 [WYY05]. NIST has been relatively fast to deprecate SHA-1 usage for signatures:

> "Federal agencies should stop using SHA-1 for digital signatures, digital time stamping and other applications that require collision resistance as soon as practical, and must use the SHA-2 family of hash functions for these applications after 2010."

> — NIST, March 15, 2006

<footnote n="2">²https://www.mitls.org/pages/attacks/SLOTH</footnote>

<footnote n="3">³https://sha-mbles.github.io</footnote>
However, SHA-1 was still used in many different contexts when we demonstrated our chosen-prefix collision attack in early 2020, including within signatures. In late 2020, NIST announced than it would retire SHA-1 for all usages in 2030, due in part to our chosen-prefix collision attack.<fnref n="4" />

**X.509 certificates.** The CA/Browser Forum decided to sunset SHA-1 in October 2014, and its members were not supposed to issue SHA-1 certificates after 2016. Web browsers have enforced similar rules, and major browsers started to reject SHA-1 certificates in early 2017. Figure 1.4 shows hash function usage in the certificates of top websites: SHA-1 was still used until 2016 and stopped being used in early 2017, around the time the first collision was announced [SBK+17].

For non-web clients, SHA-1 certificates have been supported longer in some applications. For instance, OpenSSL has deprecated SHA-1 signatures with version 3.0.0 in September 2021.

**PGP / GnuPG.** There are currently two supported branches of GnuPG: GnuPGv1 is the “legacy” (or “classic”) branch, and GnuPGv2 is the “modern” branch. The first version of GnuPGv2 dates back to 2006, and the “legacy” branch is no longer recommended, but the transition took a long time. In particular, GnuPGv1 was still the default version in Fedora 29 (released in October 2018), and in Ubuntu 16.04 LTS (supported until April 2021).

GnuPG supports many different algorithms, including SHA-1. Moreover, SHA-1 is the default algorithm for identity certification in GnuPGv1. This is why we targeted PGP in our demonstration of chosen-prefix collisions. After we disclosed our results to the GnuPG team, SHA-1 signatures are no longer trusted in the GnuPGv2 branch.

The current draft of the next PGP standard [WHW+23] deprecates MD5 and SHA-1, and defines a new signature format adding a salt at the beginning of the hashed data. This prevents attacks were one party generates a collision and asks another party to sign it.

**TLS handshake.** In TLS 1.0 and 1.1, the handshake is hashed with the concatenation of SHA-1 and MD5. Using the multicollision attack from Joux [Jou04], computing a CP collision for MD5 || SHA-1 is not much harder than for SHA-1. This makes those versions vulnerable to transcript-collision attacks. Figure 1.5 shows TLS usage for top websites: TLS 1.0 and 1.1 are being phased out, but they were still used when we demonstrated our attack. TLS 1.0 and 1.1 have been deprecated in 2021 [RFC8996], mostly because of SHA-1 weaknesses.

In TLS 1.2, the hash function used is configurable. In 2015, many servers and client supported MD5, and some used it in normal usage: this was the default configuration of Java clients and servers. MD5 has been disabled in many libraries after disclosing our attack. In late 2019, the vast majority of clients and servers supported SHA-1, and some servers actually *preferred* to use SHA-1, even when the client offers better algorithms.<fnref n="5" />,<fnref n="6" /> Usage of MD5 and SHA-1 has been deprecated in 2021 [RFC9155].

Modern clients (such as web browsers and OpenSSL) have removed support for TLS 1.0 and 1.1, as well as SHA-1 support to sign the handshake.

**DNSSEC.** SHA-1 was still used in DNSSEC, with 18% of the top-level domains using SHA-1 in early 2020.<fnref n="7" /> Since DNSSEC signatures include user-supplied content, CP collisions could potentially be used to attack the DNSSEC system.

<footnote n="4">⁴https://csrc.nist.gov/Projects/Hash-Functions/NIST-Policy-on-Hash-Functions</footnote>

<footnote n="5">⁵http://web.archive.org/web/20191227174651/https://censys.io/domain/report?field=443.https.tls signature.hash_algorithm</footnote>

<footnote n="6">⁶http://web.archive.org/web/20191227174551/https://censys.io/domain?q=443.https.tls. signature.hash_algorithm%3Asha1</footnote>

<footnote n="7">⁷https://www.dns.cam.ac.uk/news/2020-02-14-sha-mbles.html</footnote>
# 4. Generic Attacks Against Hash-Based MACs

*This chapter is based on articles [LPW13] and [DL14; DL16], found in Appendix F and G.*

Message Authentication Codes (MACs) are an important type of symmetric cryptography primitives, used to verify the integrity and authenticity of messages. The sender of a message uses a MAC to compute a tag from the message and a shared secret key. The tag is appended to the message and the receiver can recompute the tag using the key, and reject the message when it does not match the received tag. Common MAC algorithms are built from block ciphers (e.g. CBC-MAC, PMAC), from hash functions (e.g. HMAC, NMAC), or from universal hash functions (e.g. GMAC, Poly1305, UMAC).

## 4.1 Security of MAC algorithms

The main security requirement of a MAC is the resistance to forgery: it should be hard for an adversary to forge a valid tag without knowing the key. We define two variants of forgery attacks, assuming oracle access to the MAC with the secret key:

**Existential forgery.** After querying the oracle to obtain the tags of some chosen messages, the adversary must predict the tag of a message that has not been queried.

**Universal forgery.** The adversary is given a challenge message $C$ before interacting with the oracle. She can query any message excepted $C$, and must predict the tag of $C$.

It should also be impossible to recover the secret key excepted by exhaustive search. In addition, cryptanalysts have studied state-recovery attacks, where the adversary attempts to recover the internal state of the MAC.

### 4.1.1 Generic forgery attack against iterative MACs

Preneel and van Oorschot described a generic attack against all deterministic iterated MACs with a state size of $n$ bits [Pv95] based on collisions. After $2^{n/2}$ queries with small messages of the same length, we expect that two messages reach the same internal state. If the message pair $(M, M')$ produces an internal collision, then for any suffix $S$ the pair $(M \parallel S, M' \parallel S)$ also collides in the tag: $\text{MAC}(M \parallel S) = \text{MAC}(M' \parallel S)$. Therefore, we can create a forgery by asking for $\text{MAC}(M \parallel S)$ and using it to predict $\text{MAC}(M' \parallel S)$.

This attack is similar to the collision extension property of hash functions, but the attacker does not have access to the internal state, because a MAC is a keyed function. However, the internal collision can be detected because it implies a collision in the tag. For some MACs there are also false-positive pairs colliding on the tag but not on the internal state, but they are filtered out by testing the forgery attack.
### 4.1.2 Security loss beyond the birthday bound

Even though all deterministic iterated MACs have essentially the same security bound, the impact of the attacks can be quite different. For instance, the Envelope MAC [Tsu92] and the Sandwich MAC [Yas07] are two similar MAC constructions based on hash functions with an n-bit internal state:

$$ \begin{aligned} \text{Envelope}_k(M) &= H(k \parallel M \parallel k) \\ \text{Sandwich}_k(M) &= H(\text{pad}(k) \parallel \text{pad}(M) \parallel \text{pad}(k)) \end{aligned} $$

where pad pads its input to an integer number of blocks. Both modes are secure up to the birthday bound, and the generic forgery attack matches the bound. However, there is a more complex key-recovery attack against the envelope MAC with birthday complexity [Pv96].

**Key-recovery attack against the Envelope MAC.** For simplicity, we assume that the hash function uses n-bit message blocks, and that the size of the key is also n bits. The attacker considers n-bit messages $(M, M')$, with the last bit equal to zero $(M[n-1] = M'[n-1] = 0)$. After querying $2^{n/2}$ messages she expects a collision in the internal state:

$$ h^*(k \parallel M) = h^*(k \parallel M') $$

She detects the hash collision as a MAC collision $(\text{Envelope}_k(M) = \text{Envelope}_k(M'))$, and she verifies that it is an internal state collision with a few extra queries.

Next, she queries the MAC of $n-1$-bit messages $M[0..n-2]$ and $M'[0..n-2]$. If $k[0] = 0$, then the tags collide because the first two blocks processed by the hash function are the same as in the internal collision $h^*(k \parallel M) = h^*(k \parallel M')$:

$$ \begin{aligned} k \parallel M[0..n-2] \parallel k[0] &= k \parallel M[0..n-2] \parallel 0 = k \parallel M \\ k \parallel M'[0..n-2] \parallel k[0] &= k \parallel M'[0..n-2] \parallel 0 = k \parallel M' \end{aligned} $$

The collision is preserved by the final block, because its content is the same for both messages $(k[1..n-1])$.

On the other hand, if $k[0] = 1$, the tags are different with high probability because we have two different values for the second block $(M[0..n-2] \parallel 1$ and $M'[0..n-2] \parallel 1)$ that are not known to collide. Using this technique, the adversary recovers the key iteratively (bit-by-bit or byte-by-byte), building a special collision corresponding to each successive partial guess. She obtains a key-recovery attack with complexity $\tilde{O}(2^{n/2})$.

This attack does not apply to the Sandwich MAC, because the padding after the message prevents mixing message bits and key bits in the same block. This shows that modes with similar security proofs can have different security degradation beyond the birthday bound.

## 4.2 Hash-based MACs

In this chapter we study MAC algorithms based on a hash function such as HMAC [BCK96], one of the most widely used MACs. Using a hash function H, HMAC is defined as

$$ \text{HMAC}(k, M) = H(k \oplus \text{opad} \parallel H(k \oplus \text{ipad} \parallel M)), $$

with ipad and opad two fixed constants of size one block. More generally, we consider a class of iterative designs based on a family of compression functions $h^{(i)}$ and a finalization function g, following Chapter 2. For simplicity, we assume that the internal state and
<figure><img src="image_34.png" /><figcaption>**Figure 4.1:** Hash-based MAC. Only the initial value and the final transformation are keyed.</figcaption></figure>

the tag are both n-bit long. The message M is divided into L blocks $x_i$, and the tag $\tau$ is computed as (see Figure 4.1):

$$x_0 = I_k \qquad x_{i+1} = h^{(i)}(x_i, m_i) \qquad \tau = g_k(x_L, |M|).$$

The message processing updates the internal state starting from a key-dependent value $I_k$, and the output is produced with a key-dependent finalization function $g_k$. On the other hand the state update does not depend on the key.

Our description covers **HMAC** [BCK96], **Sandwich-MAC** [Yas07] and **Envelope-MAC** [Tsu92] with common narrow-pipe hash functions. In particular, we consider that the finalization function depends on the message length $|M|$, because many hash functions use MD strengthening. When the hash function uses the Merkle-Damgård mode, the compression function is the same at every step, and we denote it as $h(\forall i, h^{(i)} = h)$.

We know that iterated hash functions are indifferentiable up to the birthday bound, assuming that the compression function is ideal [CDM+05]. This also implies that hash-based MACs are secure up to the birthday bound.

**Our results.** In the following we study the security of hash-based MACs above the birthday bound. We give generic state-recovery attacks with complexity $\tilde{O}(2^{n/2})$ when the hash function follows the Merkle-Damgård mode (Section 4.3) and $\tilde{O}(2^{4n/5})$ for the more general HAIFA mode (Section 4.4). This contradicts previous beliefs that state-recovery attacks should have complexity $2^n$. We also extend these to key-recovery attacks when the hash function uses an internal checksum (Section 4.5).

## 4.3 State-recovery attack using cycles

Our first attack uses long messages repeating a fixed block $\beta$ (for instance, $\beta = 0$). We assume that the hash function uses the Merkle-Damgård construction, so that the compression function $h$ is the same at every step. When evaluating the MAC on such a message, we actually iterate a fixed function $\phi: x \mapsto h(x, \beta)$; our goal is to exploit properties of the functional graph of $\phi$. We travel in the graph by querying the oracle using consecutive $\beta$ message blocks. However, since the key is unknown, we do not have access to the internal state; we can only detect collisions because they are preserved by the finalization function.

### 4.3.1 Forgery

We start with a forgery attack based on collisions. This attack exploits the cycle length of the main component of $\phi$. Since $\phi$ is a public function, we identify the main component and its main cycle with $O(2^n/2)$ operations; we denote its length as $\ell$.

Assuming that $\phi$ behaves as a random function, the expected tail length (the distance to the cycle) is $\sqrt{\pi 2^{n-3}}$ and the expected cycle length is also $\sqrt{\pi 2^{n-3}}$ [FO90]. Moreover, the main component has expected size $0.76 \times 2^n$ [FS09, §VII.14].
**Naive attack.** We first assume that no length padding is used in the hash function, so that the finalization function $g$ does not depend on the message length. In this case, it is quite easy to obtain a collision, and therefore a forgery. We consider the following messages

$$M_1 = \beta^{2^{n/2}}$$

$$M_2 = \beta^{2^{n/2}+\ell}$$

With constant probability, the initial value $I_k$ is in the main component, and the sequence of $2^{n/2}$ $\beta$ blocks is sufficiently long to enter the cycle. In this case, the two MAC outputs will collide.

**Dealing with MD strengthening.** In order to deal with the MD strengthening, we must generate two messages of the same length. We use the following trick: we start from a message $M = \beta^{2^{n/2}} \parallel \alpha \parallel \beta^{2^{n/2}}$ with an arbitrary block $\alpha \neq \beta$. With constant probability, the internal state reaches the main cycle after the first series of $\beta$, and again after the second series of $\beta$. In this case, we can add $\ell$ $\beta$ blocks in the first or the second series to obtain two colliding messages of the same length (see Figure 4.2):

$$M_1 = \beta^{2^{n/2}} \parallel \alpha \parallel \beta^{2^{n/2}+\ell}$$

$$M_2 = \beta^{2^{n/2}+\ell} \parallel \alpha \parallel \beta^{2^{n/2}}$$

**Complexity analysis.** The attack has complexity $O(2^{n/2})$ and succeeds if

1. $I_k$ is in the main component of $\phi$;

2. The cycle is reached after less than $2^{n/2}$ blocks $\beta$;

3. The state reached after $\alpha$ is also in the main component of $\phi$;

4. The cycle is reached after less than $2^{n/2}$ blocks $\beta$.

Events 1 and 3 have probability about 0.76, while events 2 and 4 have probability at least $1/2$ given that the expected tail length is shorter than $2^{n/2}$. Overall the success probability is at least 0.14. The attack can be repeated with a random prefix block if needed.

### 4.3.2 State recovery

We now extend the forgery attack into a state-recovery attack. We use an additional property of the graph of a random mapping: the graph contains a giant tree of expected size $0.48 \times 2^n$ [FS09, §VII.14]. Therefore, starting from a random node in the graph, there is a constant probability to enter the cycle at one specific node: the root of the giant tree. Since $\phi$ is a public function, we identify this node offline with complexity $O(2^{n/2})$.

When the forgery attack above succeeds, there is a constant probability that the first cyclic node is exactly the root of the giant tree. Therefore, we obtain a state-recovery attack by searching for the smallest length $z$ such that the cycle is reached after processing $\beta^z$. If the cycle is reached, we know that the following two messages have a constant probability to have the same MAC:

$$M_1 = \beta^z \parallel \alpha \parallel \beta^{2^{n/2}+\ell}$$

$$M_2 = \beta^{z+\ell} \parallel \alpha \parallel \beta^{2^{n/2}}$$

In order to avoid false negatives, we repeat queries with several choices of $\alpha$ for each $z$, to obtain a high-selectivity test. Using a binary search, we need only $O(n)$ queries to find the smallest $z$ reaching the cycle. With constant probability, the state after processing the message $\beta^z$ is the root of the giant tree.

**Complexity analysis.** The attack has complexity $\tilde{O}(2^{n/2})$ and succeeds with constant probability.
<figure><img src="image_35.png" /><figcaption>**Figure 4.2:** Cycle-based collision.</figcaption></figure>

## 4.4 State-recovery attack based on chains

We now propose an attack applicable to HAIFA hash functions, i.e. with different compression functions $h^{(i)}$ at each step, but we sometimes omit the step index for simplicity. Again, we use a fixed long message, but since we have different functions we cannot use properties of the functional graph. Instead, we study the entropy loss.

### 4.4.1 Entropy loss

When we iterate a fixed sequence of random functions, the image space is reduced at each step. More precisely, we have the following lemma:

**Lemma 1.** Let $f_1, f_2, \dots, f_{2^s}$ be a sequence of random functions over the set of $2^n$ elements, with $s \le n/2$ and $g_i \triangleq f_i \circ \dots \circ f_2 \circ f_1$. Then, the images of two arbitrary inputs to $g_{2^s}$ collide with probability of about $2^{s-n}$, i.e. $\Pr_{x,y}[g_{2^s}(x) = g_{2^s}(y)] = \Theta(2^{s-n})$.

In order to exploit this property, we fix a message $C$ of length $2^s$, and query the oracle with messages of the form $r \parallel C$. If we denote the function $x \mapsto h^{(i)}(x, C[i-1])$ as $f_i$ ($1 \le i \le 2^s$), the final state after processing $r \parallel C$ is in the image space of $g_{2^s} \triangleq f_{2^s} \circ \dots \circ f_2 \circ f_1$. This set has properties similar to the root of the giant tree used in the previous attack: we can sample the set offline, it has reduced entropy, and we can build messages that reach this set online. In order to obtain a state-recovery attack, we need to match the unknown states obtained through online queries with the known states computed offline.

### 4.4.2 Using collision filters

A collision filter for an offline state $x$ is a pair of blocks $b \neq b'$ such that $h(x, b) = h(x, b')$. Given a message $M$, we test whether the state obtained after processing $M$ is equal to $x$ by comparing the tags of $M \parallel b$ and $M \parallel b'$. Building the filter has complexity $O(2^{n/2})$ and using it has complexity $O(|M|)$.

Alternatively, we can build the filter online, and evaluate it on offline states. An online collision filter for a message $M$ is a pair of blocks $b \neq b'$, such that $\text{MAC}(M \parallel b) = \text{MAC}(M \parallel b')$.
<figure><img src="image_36.png" /><figcaption>**Figure 4.3:** Chain-based state recovery. We detect a match between the gray points (•) using the diamond test built online.</figcaption></figure>

Given a state $x$, we test whether the state obtained after processing $M$ is equal to $x$ by comparing $h(x, b)$ and $h(x, b')$. Building the filter has complexity $O(|M| \times 2^{n/2})$ and using it has complexity $O(1)$.

**State recovery.** We obtain a first attack using online collision filters:

1. (online) Fix a message $C$ of length $2^s$. Query the oracle with $2^u$ messages $M_j = [j] \parallel C$. Build a collision filter for each message $M_j$.

2. (offline) Starting from $2^t$ arbitrary starting points, iterate the compression function with the fixed message $C$.

3. (offline) Test each image point $x$ obtained in Step 2 against each of the messages $M_j$. If a match is found, the state reached after $M_j$ is $x$.

**Complexity analysis.** In Step 3, we match a set of size $2^u$ and a set of size $2^t$. According to Lemma 1, each pair collides with probability $2^{s-n}$. Therefore, the attack is successful with high probability if $t + u \ge n - s$.

The optimal trade-off is obtained with $u = s$ and $t = n - 2s$, with the following complexity:

$$ \text{Step 1:} \quad 2^{s+u+n/2} = 2^{n/2+2s} \quad \text{Step 2:} \quad 2^{s+t} = 2^{n-s} \quad \text{Step 3:} \quad 2^{t+u} = 2^{n-s} $$

The optimal complexity is $O(2^{5n/6})$ when $s = n/6$. More generally, we obtain an attack with complexity $O(2^{n-s})$ when $s \le n/6$.

### 4.4.3 Using a diamond filter

Building the filters is the bottleneck of the attack. In order to build filters for $2^u$ messages $M_j$ more efficiently, we use the diamond structure of Kelsey and Kohno [KK06]. Since the construction of the diamond structure is based on collisions, we can build a diamond for the unknown states corresponding to online queries. This requires $\tilde{O}(2^{(n+u)/2})$ queries, with messages of length $O(|M_j|)$.

We obtain messages $m_j$ such that all messages $M_j \parallel m_j$ reach the same state. Then we build a collision filter $(b, b')$ for the final state of the diamond, and we obtain filters for all messages $M_j$. We test whether the state obtained after processing $M_j$ is equal to $x$ by comparing $h^*(x, m_j \parallel b)$ and $h^*(x, m_j \parallel b')$. Building the filter for $2^u$ messages has complexity $O(|M_j| \times 2^{(n+u)/2})$, and using a single filter has complexity $O(u)$.

**State recovery.** We obtain an improved attack using the online diamond filter (Figure 4.3):

1. (online) Fix a message $C$ of length $2^s$. Query the oracle with $2^u$ messages $M_j = [j] \parallel C$. Build a diamond filter for all messages $M_j$.
<figure><img src="image_37.png" /><figcaption>**Figure 4.4:** HMAC based on a hash function with a checksum (dashed lines) and a length-padding block. We only detail the first hash function call.</figcaption></figure>

2. (offline) Starting from $2^t$ arbitrary starting points, iterate the compression function with the fixed message $C$.

3. (offline) Test each image point $x$ obtained in Step 2 against each of the messages $M_j$. If a match is found, the state reached after $M_j$ is $x$.

**Complexity analysis.** Again, the attack is successful with high probability if $t+u \ge n-s$.

The optimal trade-off is obtained with $u = s$ and $t = n - 2s$, with the following complexity:

$$ \text{Step 1: } 2^{s+u/2+n/2} = 2^{n/2+3s/2} \quad \text{Step 2: } 2^{s+t} = 2^{n-s} \quad \text{Step 3: } 2^{t+u} = 2^{n-s} $$

The optimal complexity is $\tilde{O}(2^{4n/5})$ when $s = n/5$. More generally, we obtain an attack with complexity $\tilde{O}(2^{n-s})$ when $s \le n/5$.

## 4.5 Key-recovery attack against HMAC-GOST

Finally, we consider HMAC used with a hash function with an internal checksum. The checksum computes the sum (XOR) of all message blocks, and uses this sum as an extra input to the finalization function. This technique is supposed to improve the security of a hash function, assuming that controlling the checksum would be an additional challenge for an adversary. Previous work have shown that the checksum fails to improve the security on many cases [GK08], but we obtain a more surprising result: the checksum makes the hash function weaker, enabling key-recovery attack faster than exhaustive search on HMAC.

Notable examples of hash functions with a checksum are the standards from the Russian government: GOST [Dol10] and Streebog [DD13]. Figure 4.4 shows the evaluation of HMAC with a Merkle-Damgård hash function with a checksum.

**State recovery.** First, we note that the checksum does not prevent the state-recovery attacks. Concretely, the attack of Section 4.3 is based on detecting collisions between pairs of messages

$$ M_1 = \beta^z \parallel \alpha \parallel \beta^{2n/2+\ell} \qquad M_2 = \beta^{z+\ell} \parallel \alpha \parallel \beta^{2n/2} $$

Since the messages have the same checksum, a collision in the state will be preserved.

We use the state-recovery attack to recover the internal state $x_*$ before the checksum is processed.
**Key recovery.** In HMAC, $k \oplus \text{ipad}$ is prepended to a message $M$, and $(k \oplus \text{ipad}) \parallel M$ is hashed by the underlying hash function $H$. Therefore, the final checksum value is $\sigma = \text{Sum}^{\oplus}((k \oplus \text{ipad}) \parallel M) = k \oplus \text{ipad} \oplus \bigoplus M_i$. We take advantage of the fact that $\sigma$ contains the key, and can be controlled by changing the message. We inject a known difference in the checksum to perform a kind of related-key attack on the finalization function $g$, even though we have access to a single HMAC key.

More precisely, we use Joux's multicollision attack [Jou04] to generate a large set of messages with the same value $x_*$ before the finalization, but with different values of the checksum. We detect MAC collisions among those messages, and we assume that the collisions happen when processing the checksum. For each such collision, we have $g(x_*, k \oplus \text{ipad} \oplus \bigoplus M_i) = g(x_*, k \oplus \text{ipad} \oplus \bigoplus M'_i)$, and we compute the input difference $\Delta M = \bigoplus M_i \oplus \bigoplus M'_i$.

Finally, we compute $g(x_*, m)$ offline for a large set of random values $m$, and we collect collisions. Again, we compute the input difference $\Delta m = m \oplus m'$ for each collision, and we match $\Delta m$ to the previously stored $\Delta M$. When a match is found between the differences we look for the corresponding values and we have $k \oplus \text{ipad} \oplus \bigoplus M_i = m$ (or $m'$) with high probability. This gives the value of the key $k$.

**Application.** We obtain an attack with complexity $2^{3n/4}$ on HMAC-GOST and an attack with complexity $2^{4n/5}$ on HMAC-Streebog. The attack on HMAC-Streebog is less efficient because Streebog uses the HAIFA construction, which makes the key-recovery attack more complex.

## 4.6 Conclusion

In the chapter we have demonstrated state-recovery attacks for hash-based MACs with complexity below $2^n$. In particular, our generic attacks are more efficient than dedicated attacks (presented as distinguishing-H attacks) that have been published against hash functions of the MD-SHA family [KBP+06; RR08; WYW+09].

For Merkle-Damgård hash functions we obtain an attack with complexity $\tilde{O}(2^{n/2})$, matching the security proof. For HAIFA hash functions, we obtain an attack with complexity $\tilde{O}(2^{4n/5})$, leaving a gap with the proven security bound.

In the full paper [DL16] (Appendix G), we extend the framework for state-recovery attacks. We observe that our state-recovery attacks are similar to collision-finding algorithms: the attack from Section 4.3 is similar to Pollard's rho algorithm, while the attack from Section 4.4 is similar to the parallel algorithm of van Oorschot and Wiener [vW94]. We point out that Pollard's rho algorithm returns one specific collision with high probability: the root of the giant tree. This property is used in our state-recovery attack. We show that the algorithm of van Oorschot and Wiener also returns collisions from a small set. Based on this observation, we obtain different attacks with various trade-offs between the message length and the complexity of the attacks, as shown in Figure 4.5.

Those techniques have also been used to devise universal forgery attacks, where the attacker is given a long challenge, and must predict the MAC of the challenge after interacting with the oracle [PW14; GPS+14; DL14].
<figure><img src="image_38.png" /><figcaption>**Figure 4.5:** Trade-offs between the message length and the complexity for state-recovery attacks.</figcaption></figure>
# 5. Generic Attacks Against Encryption Modes

This chapter is based on articles [BL16a] and [LS18], found in Appendix H and I.

Block ciphers (such as DES or the AES) are probably the most widely used cryptographic primitives. Formally, a block cipher is just a keyed family of permutations over $n$-bit blocks, but when combined with a mode of operation, it can provide confidentiality (e.g. using CBC, or CTR), authenticity (e.g. using CBC-MAC, PMAC, or GMAC), or authenticated encryption (e.g. using GCM, CCM, or OCB). A mode of operation defines how to divide a message into blocks, and how to process the blocks one by one with some chaining rule.

When analyzing the security of block cipher modes of operations, there is frequently a term $\sigma^2/2^n$ in the security proof (with $\sigma$ the total length of the queries made by the adversary, and $n$ the block size), due to the PRF/PRP switching lemma [BKR94]. Indeed, a block cipher is idealized as a pseudo-random permutation (PRP) family, but proofs often need it to behave as a pseudo-random function (PRF) family. The difference between a PRF and a PRP is that PRFs have collisions, which are detected with probability at most $\sigma^2/2^n$. More generally, most proof techniques fail at the birthday bound; this explains why we use modes with birthday security.

## 5.1 CBC and CTR

Two important examples are the CBC (Cipher-Block Chaining) mode and the CTR (Counter) mode; they are the most widely used modes of operation used for symmetric encryption.

**The CBC mode.** CBC is one of the oldest encryption modes, standardized in 1980 [NBS80], and still widely used. The message $M$ is divided into blocks $m_i$, $0 \le i < L$ and is encrypted

<figure><img src="image_39.png" /><figcaption>Figure 5.1: CBC mode.</figcaption></figure>

<figure><img src="image_40.png" /><figcaption>Figure 5.2: CTR mode.</figcaption></figure>
as (see Figure 5.1):

$$c_i = E_k(m_i \oplus c_{i-1}),$$

where $c_{-1}$ is an initialization value usually denoted as IV. For simplicity, we assume that all message sizes are a multiple of the block size.

CBC has been proven secure up to $2^{n/2}$ blocks of messages [BKR94; PR00]. On the other hand there is a simple birthday attack against CBC: after $2^{n/2}$ message blocks encrypted with the same key (in the same message or in different messages), a collision between two ciphertext blocks $c_i = c_j$ is expected. Since $E_k$ is a permutation, a collision in the output means that the inputs are the same ($m_i \oplus c_{i-1} = m_j \oplus c_{j-1}$), which reveals the XOR of two plaintext blocks:

$$m_i \oplus m_j = c_{i-1} \oplus c_{j-1}.$$

**The CTR mode.** The CTR mode was first proposed in 1979 [DH79], but standardized more recently in 2001 [NIS01]. It is now widely used: in particular, it provides the encryption part of authenticated encryption modes CCM and GCM. The counter mode turns a block cipher into a stream cipher: a counter is encrypted to generate a keystream that is xored with the message. More precisely, the message $M$ is divided into blocks $m_i, 0 \le i < L$ which are encrypted as (see Figure 5.2):

$$c_i = E_k(i) \oplus m_i,$$

For simplicity we consider a stateful variant of the counter mode with a global counter that is maintained across messages and initialized as 0.

If $E_k$ is a pseudo-random function, rather than a pseudo-random permutation, then CTR is secure up to $2^n$ blocks [BDJ+97]. However, in the common case where $E_k$ is a permutation, CTR is proven secure only up to $2^{n/2}$ blocks, and there is a matching distinguishing attack with complexity $2^{n/2}$. If a message where all the plaintext blocks are equal is encrypted, then all the ciphertext blocks will be pairwise different. Indeed, all the $E_k(i)$ are unique, because $E_k$ is a permutation. More generally, with known plaintext, the adversary can reconstruct the keystream blocks $c_i \oplus m_i$ and observe that they are distinct. This distinguishes the counter mode from an ideal encryption scheme, because random data would collide after roughly $2^{n/2}$ blocks.

More interestingly, McGrew proposed a method to eliminate impossible values for the plaintext [McG12]. Given two encrypted blocks $c_i = E_k(i) \oplus m_i$ and $c_j = E_k(j) \oplus m_j$, we have $E_k(i) \neq E_k(j)$, therefore we deduce

$$m_i \oplus m_j \neq c_i \oplus c_j.$$

Using prior knowledge about the plaintext (such as a dictionary), an attacker can eventually recover the right plaintext.

**Security of CTR and CBC.** It is interesting to compare the birthday attacks against CBC and CTR. Both attacks have the same complexity, and show that the proofs are tight. However, they are quite different:

* The CBC attack is based on detecting collisions, and directly leaks information about the plaintext;

* The CTR attack is based on detecting the absence of collisions, and only leaks impossible values of the plaintext.

In general, there is a folklore belief that the leakage of the CTR mode is not as bad as the leakage of the CBC mode. For instance, Ferguson, Schneier and Kohno wrote (in the context of a 128-bit block cipher):
> CTR leaks very little data. [...] It would be reasonable to limit the cipher mode to 2⁶⁰ blocks, which allows you to encrypt 2⁶⁴ bytes but restricts the leakage to a small fraction of a bit. When using CBC mode you should be a bit more restrictive. [...] We suggest limiting CBC encryption to 2³² blocks or so.

> — Cryptography Engineering, [FSK11, Section 4.8.2]

**Our results.** In this chapter we study the impact of birthday attacks on CBC and CTR. We show that both modes suffer plaintext-recovery attacks with birthday complexity in realistic settings. Moreover, we demonstrate the CBC attack in practice with ciphers with 64-bit blocks, showing that they do not offer meaningful security.

## 5.2 Birthday-bound security

While block ciphers with $n$-bit blocks and $\kappa$-bit keys are required to resist any attack with up to $2^n$ data and $2^\kappa$ time, most modes of operation are only proven secure up to $2^{n/2}$ blocks of plaintext. Rogaway summarizes the situation as follows:

> In general, unless special efforts are taken, almost any mode of operation based on an $n$-bit blockcipher will admit attacks that employ $\sigma = 2^{n/2}$ blocks. [...] Do birthday-bound attacks on CBC, CFB, and OFB actually matter? They are of relatively little concern when the blockcipher has a blocksize of $n = 128$ bits, but the attacks can be a serious concern when employing a blockcipher of $n = 64$ bits, requiring relatively frequent rekeying to keep $\sigma \ll 2^{32}$.

> — Phillip Rogaway, [Rog11, p. 36]

The main countermeasure against birthday attacks is to change the key frequently, before reaching the birthday bound under any single key. For instance, if the key is changed after $2^{n/2-16}$ blocks, a collision attack against a given key only succeeds with probability $2^{-32}$, and an attacker has to collect $2^{32}$ different sessions to mount an attack with high probability.

If implemented properly, this is an effective security measure to strengthen block ciphers with a small block-size. We stress that the key must be changed *well before* $2^{n/2}$ blocks, despite misleading recommendations in published standards. For instance, ISO used to recommend:

> Generally, for a block cipher with block size of $n$ bits, the maximum amount of plaintext that can be encrypted before rekeying must take place is $2^{(n/2)}$ blocks, due to the birthday paradox. As long as the implementation of a specific block cipher do not exceed these limits, using the block cipher will be safe.

> — ISO/IEC JTC1 SC27, May 2014 [ISO14]

NIST had a similar recommendation for 3DES, a legacy standard with a 64-bit block size (denoted as TDEA in NIST documents):

> The security of TDEA is affected by the number of blocks processed with one key bundle. One key bundle **shall not** be used to process more than $2^{32}$ 64-bit data blocks.

> — NIST, January 2012 [NIS12]

Those recommendations are inadequate, because collisions occur with high probability (close to 0.39) with only $2^{n/2}$ blocks. Similarly, many internet standards (IPsec, TLS, SSH)
do not specify a session limit, and many applications allowed very long sessions with the same key, up to or even above $2^{n/2}$ blocks.

## On the practical (in-)security of 64-bit block ciphers

With a modern block cipher with 128-bit blocks such as AES, the birthday bound corresponds to 256 EB ($2^{68}$ bytes). While this leaves a safe margin for common uses of cryptography today, the resulting security is still lower than could be expected of 128-bit security and might be an issue in the future. As a point of comparison, the worldwide data storage capacity is estimated to be around 8 ZB ($2^{73}$ bytes) in 2021 [Sta22b], and the global Internet traffic is estimated around 4 ZB ($2^{72}$ bytes) per year in 2022 [Sta22a].

More strikingly, the birthday bound corresponds to only 32 GB for a block cipher with 64-bit blocks. There are real-world scenarios in which this amount of data may be encrypted under a block cipher with 64-bit blocks: 3G telephony connections (UMTS) are encrypted with KASUMI using the f8 mode, and Internet protocols like OpenVPN, TLS, SSH, and IPsec use 3DES or Blowfish as legacy ciphers for interoperability. In these scenarios, 32 GB of data can be transferred in less than one hour with a fast connection. In the following, we investigate the practical impact of birthday attacks, with a focus on block ciphers with 64-bit blocks.

**Previous work.** McGrew has investigated plaintext-recovery attacks on 64-bit ciphers in CBC, CFB, and CTR modes [McG12]. He studied the amount of information leakage by assuming that the attacker can observe all the ciphertext in an encrypted stream, and she has some (incomplete) knowledge of the plaintext. We revisit the results of McGrew by considering a stronger adversary model (with chosen plaintext rather than known plaintext), and more advanced algorithms to solve the underlying problems.

## 5.3 Plaintext-recovery attack against CBC

We consider collision attacks against the CBC mode in the chosen-prefix secret-suffix model [HRR+15]. The attacker must recover a t-block secret S, given access to an oracle that computes the encryption of M $\parallel$ S for a chosen message M. Using the collision attack above, the attacker queries $2^q$ arbitrary messages of u block each, corresponding to $\sigma = (t + u) \times 2^q$ blocks of data. She expects on average $\sigma^2 \times 2^{n-1}$ collisions among the ciphertext blocks.

**Using short messages.** When $u \ll t$, most collisions reveal the XOR between two blocks from S. The attacker collects these relations until she learns the XOR between all pairs of blocks from S. We model a relation as an edge in a graph whose vertexes are the plaintext blocks; with high probability, the graph will be fully connected when there are more than $\Theta(t \ln(t))$ edges. We deduce the following complexity (up to constant factors):

$$ \sigma^2 \times 2^{n-1} \approx t \ln(t) \\ \sigma \approx \sqrt{t \ln(t)} \times 2^{n/2} $$

At this point, there are $\sigma = \sqrt{t \ln(t)} \times 2^{n/2}$ ciphertext blocks from S, and $u/t \times \sigma = u \times \sqrt{\ln(t)/t} \times 2^{n/2}$ from M. We expect $u \ln(t) > 1$ collisions across the two sets; this reveals at least one block of secret, and the others are deduced using the relations between the blocks from S.
**Using longer messages.** When $u \gtrsim t$, most collisions are between two blocks from $M$, and the attacker doesn't learn anything from such collisions. But some collisions reveal the XOR between a block from $S$ and a block from $M$; we expect $u2^q \times t2^q \times 2^{-n} = tu \times 2^{2q-n}$ collisions of this type. In order to recover the full secret, the attacker needs on average $t \times H_t$ such collisions, following the analysis of the coupon collector's problem (with $H_t$ the harmonic numbers $H_t = \sum_{i=1}^t 1/i$). We deduce the complexity of the attack:

$$t \times H_t \approx t \ln(t) = tu \times 2^{2q-n}$$
$$\sigma = u2^q = \sqrt{u \ln(t)} \times 2^{n/2}$$

Using longer queries increases the data complexity of the attack, but it reduces the total number of queries from $O(\sqrt{\ln(t)/t \times 2^{n/2}})$ to $O(\sqrt{\ln(t)/u \times 2^{n/2}})$. In practice, this results in a faster attack overall when there is a minimal delay for each query.

**With rekeying.** If the lifetime of a key is limited to $2^r \lesssim 2^{n/2}$ blocks of data, this increases the complexity of the attack, but does not prevent it. Using the short message attack, we can make $2^r/t$ queries per key, so that we make $2^q$ queries spread over $t \times 2^{q-r}$ different keys. Collision between ciphertext blocks encrypted with different keys are useless, but we still expect on average $2^{2r-n-1}$ collisions per key, i.e. $t \times 2^{q+r-n-1}$ useful collisions in total. We obtain the following complexity (up to constant factors):

$$t \times 2^{q+r-n-1} \approx t \ln(t)$$
$$\sigma = t \times 2^q \approx t \ln(t) \times 2^{n-r}$$

If $r$ is slightly below $n/2$ the attack still has complexity close to $2^{n/2}$, because for each key there is a non-negligible probability that a collision occurs.

### 5.3.1 Usage of 64-bit block ciphers

When we performed this analysis in 2016, there was a non-negligible usage of block ciphers with 64-bit blocks, mostly 3DES and Blowfish. In most cases, there was no limit to session length, or a limit close to $2^{32}$ blocks (insufficient to prevent the attack).

**Usage in TLS.** In TLS 1.0 and 1.1, 3DES is the mandatory encryption algorithm, so all TLS libraries implemented it and a vast majority of web servers supported it. Before we disclosed our results, mainstream TLS libraries still treated 3DES to be at the same security level as AES. For example, OpenSSL included 3DES ciphersuites in its HIGH-security list. Until 2014, OpenSSL even considered 3DES as more secure than AES-128 because of its larger key.

In 2016, telemetry results showed around 1% usage of 3DES in web browsers for HTTPS traffic. Actually, 3DES usage increased in 2015, after RC4 was deprecated due to practical attacks [ABP+13]. 3DES was recommended as the backup cipher in place of RC4, for legacy server or clients without AES support. Surprisingly, scan results showed that many servers that would use 3DES actually supported AES, but preferred to use 3DES.

TLS does not explicitly limit the amount of data encrypted with the same key. When using HTTPS, HTTP/1.1 supports sending multiple messages in the same TLS session. In practice, web browsers did not force any rekeying, and we found many web servers that supported long-lived connections with a large amount of data without rekeying. We measured that 0.6% of the top 100k websites would both use 3DES with an up-to-date browser, and supported long sessions. This included high-profile websites such as **ebay.com**.
**Usage in OpenVPN.** OpenVPN is a popular open-source VPN solution. Before version 2.4 (released in December 2016), the default encryption for the transport protocol of OpenVPN was Blowfish, a block cipher with 64-bit blocks, in CBC mode. OpenVPN supports two different ways of generating session keys to encrypt the messages. In pre-shared-key mode, static keys are used for all the traffic. In particular, there is no limit to the lifetime of those keys. In TLS mode, session keys are generated with a TLS handshake, using certificates to authenticate the peers. The session keys are updated periodically, with limits on the number of packets, the number of bytes, or a session time. The default configuration rekeys the tunnel every hour. In addition, the tunnel is rekeyed shortly before $2^{32}$ packets in TLS mode, because the packet counter is a 32-bit integer. In pre-shared-key mode, the packet counter is a 64-bit integer.

**Usage in SSH.** In SSH version 1, the strongest available ciphers are all block ciphers with 64-bit blocks: 3DES, Blowfish, and IDEA, and although SSH 2 introduced AES, it still labeled 3DES as the mandatory cipher. Consequently, popular implementations such as OpenSSH still used 3DES as the default cipher for SSH-1 connections. SSH standards recommend that implementations rekey after every 1 GB of data (or after every $2^{n/4}$ blocks when $n \ge 128$ [NKB06]), but many popular SSH clients do not implement this feature.

### 5.3.2 Practical attacks against CBC with 64-bit block ciphers

As explained in Section 1.3, the man-in-the-browser setting is a practical model for attacks against websites, where the attacker targets an authentication token that is included in every query. Therefore, she can directly apply the chosen-prefix secret-suffix attack given above. We observe that most of the traffic generated is known or predictable. The requested URL is chosen by the attacker, and all the headers excepted the authentication token are predictable and can be observed in any plaintext HTTP traffic.

We have demonstrated two versions of the attack, against OpenVPN tunneling and against TLS encryption. We assume that the token takes two blocks, and that the attacker has aligned it to a block boundary using other headers.

**Proof-of-concept attack against OpenVPN.** To demonstrate the attack against OpenVPN, we used a pre-shared-key tunnel between two physical machines running Linux, with Firefox Developer Edition 47.0a2 on one side, and an nginx server on the other side. Access to the server was protected by BasicAuth (in plaintext inside the tunnel). Using the default OpenVPN settings, the tunnel was encrypted with Blowfish in CBC mode.

We used JavaScript code to send a large number of requests to the server though the tunnel. We found that increasing the size of the request to 4 kB did not significantly reduce the query rate, but reduced the number of queries required for the attack. In our setting, the browser generated about 2900 requests per second, using several web Workers running in parallel. The full attack is expected to use about $2^{36.6}$ blocks (780 GB) to recover a two-block secret out of 4 kB messages, corresponding to about 19 hours in this setting. In our demo, it took 18.6 hours and 705 GB, and we successfully recovered the 16-byte authentication token.

**Proof-of-concept attack against TLS.** In our setup we used Firefox Developer Edition 47.0a2 running on Linux and an IIS 6.0 server in a Windows Server 2003 R2 SP2 Virtual machine. The default configuration of IIS 6.0 with all recommended updates offered only RC4 and 3DES ciphers, and 3DES was used with Firefox and other browsers where RC4 is disabled. Moreover, IIS 6.0 supports HTTP/1.1 and keeps an active connection open for an arbitrary long time.

We used JavaScript to generate queries but we note that with several Workers running in parallel, Firefox opened a few parallel connections to the server (typically, 6) and split
the requests over these connections. For our attack, we need to maximize the throughput
over a *single* connection. This can be achieved by disturbing some of the connections so
that most of the requests are sent in a single connection. In our setup, we used `iptables`
rules to limit the rate of all connections except one.

On Firefox Developer Edition 47.0a2, with a few dozen **Workers** running in parallel, we could send up to 2000 requests per second in a single TLS connection. To further reduce the time needed for the attack, we injected a padding cookie to expand the requests to 4 KB (512 blocks). In our setting this reduced the rate to 1500 requests per second, but still lead to a faster attack. Again, the full attack should require $2^{36.6}$ blocks (780 GB) to recover a two-block token, which should take 38 hours in our setting. Experimentally, we recovered the token (a two-block cookie) after only 30.5 hours and 610 GB.

### 5.3.3 Responsible disclosure.

Our attack was responsibly disclosed in 2016 under the name **Sweet32**, using the website **sweet32.info**. We have contacted the OpenVPN team, as well as various website owners, browser vendors, and TLS libraries. The TLS vulnerability received CVE number CVE-2016-2183, and the OpenVPN vulnerability is tracked as CVE-2016-6329.

Several standards have been updated to deprecate 64-bit block ciphers or impose data limits:

* NIST has reduced the maximum amount of plaintext allowed to be encrypted under a single 3DES key from $2^{32}$ blocks to $2^{20}$ [NIS17]. They later announced that 3DES usage for encryption would be deprecated in 2023, and disallowed after 2023 [NIS19].

* ISO has updated its recommendations on block size [ISO19];

Software vendors have also deprecated 3DES:

* Mozilla has implemented data limits (at most $2^{20}$ records for 3DES) in Firefox 51 (released in January 2017) and disabled 3DES by default in Firefox 93 (released in October 2021). Google disabled 3DES in Chrome 93 in August 2021.

* OpenVPN 2.4 (released in December 2016) has introduced ciphersuite negotiation, defaulting to AES-GCM, instead of a fixed ciphersuite defaulting to Blowfish-CBC. Moreover, it rekeys every $2^{23}$ blocks (64 MB) when using a 64-bit block cipher.

* OpenSSL has deprecated 3DES with version 1.1.0 in August 2016.

* OpenSSH removed 3DES from the default client configuration with version 7.4 in December 2016.

## 5.4 The missing difference problem

We now consider the security of the CTR mode against birthday attacks. There is a well-known distinguisher based on the absence of collision in the keystream, and McGrew has formulated a plaintext-recovery attack as a simple algorithmic problem [McG12]. In the chosen-prefix secret-suffix model (with a single block secret $S$), an attacker collects two types of ciphertexts blocks $c_i = E_k(i) \oplus m_i$:

* encrypted blocks corresponding to a known plaintext block $m_i$; we denote the corresponding keystream as $a_i = m_i \oplus c_i = E_k(i)$;

* encrypted blocks corresponding to the fixed secret $S$; we denote the corresponding ciphertext as $b_j = S \oplus E_k(j)$.
**Algorithm 1** Known-prefix sieving.

**Input:** $n, z < n, \mathcal{A}, \mathcal{B}, \mathcal{S} \subseteq \{0\}^z \times \{0, 1\}^{n-z}$
$h \leftarrow \text{Empty hash table.}$

for $b$ in $\mathcal{B}$ do

$$h[b_{[0...(z-1)]}] \stackrel{\cup}{\leftarrow} \{b_{[z...(n-1)]}\}$$

end for

for $a$ in $\mathcal{A}$ do

$$v_a \leftarrow a_{[z...(n-1)]}$$

for $v_b$ in $h[a_{[0...(z-1)]}]$ do

Remove $0 \parallel (v_a \oplus v_b)$ from $\mathcal{S}$;

end for

end for

return $\mathcal{S}$

McGrew observes that all values $a_i \oplus b_j$ are different from $\mathcal{S}$:

$$i \neq j \Rightarrow E_k(i) \neq E_k(j) \Rightarrow a_i \neq b_j \oplus S \Rightarrow S \neq a_i \oplus b_j.$$

Therefore, we consider an attacker that collects a set of keystream blocks $\mathcal{A} = \{a_i\} \subseteq \{0, 1\}^n$ and a set of encryption of the secret $\mathcal{B} = \{b_j\} \subseteq \{0, 1\}^n$. We further assume some prior knowledge about the secret: $\mathcal{S} \in \mathcal{S} \subseteq \{0, 1\}^n$. In order to recover the secret $\mathcal{S}$, the attacker has to solve the following algorithmic problem:

**Definition 1** (Missing Difference Problem). Given two sets $\mathcal{A}$ and $\mathcal{B}$, and a hint $\mathcal{S}$, find the value $\mathcal{S} \in \mathcal{S}$ such that:

$$\forall (a, b) \in \mathcal{A} \times \mathcal{B}, \mathcal{S} \neq a \oplus b.$$

In the information theoretic setting, this problem can be solved with $|\mathcal{A}| = |\mathcal{B}| = \tilde{O}(2^{n/2})$ for any set $\mathcal{S}$, and requires at least $|\mathcal{A}| \times |\mathcal{B}| = \Omega(2^n)$ when $|\mathcal{S}| \ge 2$. However, the analysis is more complex when taking into account the cost of the computations required to recover $\mathcal{S}$. McGrew introduces two algorithms for this problem:

* A sieving algorithm that iterates over $\mathcal{A} \times \mathcal{B}$ and discards values from $\mathcal{S}$ until there is only one value left. This requires $|\mathcal{A}| = |\mathcal{B}| = \tilde{O}(2^{n/2})$ and time $\tilde{O}(2^n)$.

* A searching algorithm that iterates first over $s \in \mathcal{S}$, then over $a \in \mathcal{A}$ and checks whether $s \oplus a \in \mathcal{B}$ to discard $s$. With an optimal parameter choice, this requires $|\mathcal{A}| = \tilde{O}(2^{n/2}/\sqrt{|\mathcal{S}|})$, $|\mathcal{B}| = \tilde{O}(2^{n/2}\sqrt{|\mathcal{S}|})$ and time $\tilde{O}(2^{n/2}\sqrt{|\mathcal{S}|})$.

In the following we describe more efficient algorithms for this problem. We consider that $\mathcal{A}$ and $\mathcal{B}$ correspond to oracle queries, so that we want to minimize $|\mathcal{A}|$ and $|\mathcal{B}|$ as well as the time complexity.

### 5.4.1 Known-prefix sieving

In many concrete attack scenarios, an attacker knows some bits of the secret message in advance. We model this by assuming that the secret is known to start with $z$ zero bits.<fnref n="1" /> We propose an algorithm to solve the missing difference problem efficiently in this context (Algorithm 1).

Since $\mathcal{S}$ is known to start with $z$ zeroes, we look for $z$-bit collisions between $\mathcal{A}$ and $\mathcal{B}$. With $|\mathcal{A}| = |\mathcal{B}| = \sqrt{n-z} \times 2^{n/2}$ we expect $(n-z) \times 2^{n-z}$ collisions. For each collision,

<footnote n="1">¹Our result can be generalized to a known prefix instead of zero prefix, and to $\mathcal{S}$ being an affine space of dimension $n-1$.</footnote>
**Algorithm 2** Fast-convolution sieving.

**Input:** $\mathcal{A}, \mathcal{B}, t \le n$

$C_{\mathcal{A}}, C_{\mathcal{B}}, C_{\mathcal{A} \oplus \mathcal{B}} \leftarrow$ arrays of $2^{n-t}$ integers initialized to 0;

**for** $a$ **in** $\mathcal{A}$ **do**

Increment $C_{\mathcal{A}}[a_{0..(n-t-1)}]$

**end for**

**for** $b$ **in** $\mathcal{B}$ **do**

Increment $C_{\mathcal{B}}[b_{0..(n-t-1)}]$

**end for**

$C_{\mathcal{A} \oplus \mathcal{B}} \leftarrow \text{FASTCONVOLUTION}(C_{\mathcal{A}}, C_{\mathcal{B}})$

$u \leftarrow \text{argmin}_i C_{\mathcal{A} \oplus \mathcal{B}}[i]$

Run known prefix sieving (Algorithm 1), knowing that $T(S) = u$

we discard the corresponding value from $S$. Following the analysis of the coupon collector, we expect to discard all wrong values. Therefore, we recover $S$ with $\tilde{O}(2^{n/2})$ queries and memory, and $\tilde{O}(2^{n-z} + 2^{n/2})$ operations.

With $z = 0$, the algorithm is the same as McGrew's sieving algorithm, but with $z \ge n/2$ we have an algorithm with optimal complexity $\tilde{O}(2^{n/2})$, more efficient than McGrew's searching algorithm.

### 5.4.2 Fast-convolution sieving

When we have no prior information on the secret ($S = \{0,1\}^n$), we can reduce the complexity of the sieving algorithm by using sets $\mathcal{A}$ and $\mathcal{B}$ of size $2^m \gg 2^{n/2}$, rather than $\tilde{O}(2^{n/2})$ as required to uniquely identify $S$. If we consider all the values $a \oplus b$ for $(a,b)$ in $\mathcal{A} \times \mathcal{B}$, we expect that they are close to uniformly distributed over $\{0,1\}^n \setminus S$, so that every value except $S$ is reached about $2^{2m-n}$ times, while $S$ is never hit. Increasing $m$ makes the gap more visible than with sets of size only $\tilde{O}(2^{n/2})$. Therefore, we consider buckets of several candidates $s$, and accumulate the number of $a \oplus b$ in each bucket. With buckets of $2^t$ values, each bucket receives $2^t \times 2^{2m-n}$ values on average, but the bucket containing $S$ receives only $(2^t - 1) \times 2^{2m-n}$ values. If we model the counters as random variables following a binomial distribution, the variance $\sigma^2$ is about $2^{m+t/2-n/2}$. Therefore, the bias will be detectable when $\sigma \ll 2^{2m-n}$, i.e. when $t < 2m - n$.

Concretely, we use a truncation function $T$ that keeps only $n-t$ bits of an $n$-bit word. We consider the values $T(a \oplus b)$ for all $(a,b) \in \mathcal{A} \times \mathcal{B}$, and count how many times each value is reached. If $m$ is large enough, the lowest counter corresponds to $T(S)$.

For a given multi-set $\mathcal{X}$, we consider an array of $2^{n-t}$ counters $C_{\mathcal{X}}$, to represent how many times each value $T(x)$ is reached:

$$C_{\mathcal{X}}[i] = |\{x \in \mathcal{X} : T(x) = i\}|, \quad i \in \{0, \dots, 2^{n-t} - 1\}.$$

Our goal is to compute $C_{\mathcal{A} \oplus \mathcal{B}}$ efficiently from $\mathcal{A}$ and $\mathcal{B}$, where $\mathcal{A} \oplus \mathcal{B}$ is the multi-set $\{a \oplus b : (a,b) \in \mathcal{A} \times \mathcal{B}\}$. We observe that:

$$\begin{align*}
C_{\mathcal{A} \oplus \mathcal{B}}[i] &= |\{(a, b) \in \mathcal{A} \times \mathcal{B} : T(a \oplus b) = i\}| \\
&= \sum_{j \in \{0,1\}^{n-t}} |\{a \in \mathcal{A} : T(a) = j\}| \times |\{b \in \mathcal{B} : T(b) = i \oplus j\}| \\
&= \sum_{j \in \{0,1\}^{n-t}} C_{\mathcal{A}}[j] C_{\mathcal{B}}[i \oplus j]
\end{align*}$$

This is a form of convolution that can be computed efficiently using the Fast Walsh-Hadamard Transform, in the same way we use the Fast Fourier Transform to compute
circular convolutions. We obtain all the values $C_{A \oplus B}[i]$ simultaneously with complexity $\tilde{O}(2^{n-t})$.

This results in an algorithm with complexity $\tilde{O}(2^m + 2^{n-t})$ (Algorithm 2), with $m > (n+t)/2$. We optimize the complexity by choosing $t = n/3$ and $m = 2n/3 + \ln(n)/2$ such that the time complexity, data complexity, and memory usage are all in $\tilde{O}(2^{2n/3})$.

## 5.5 Plaintext-recovery attack against CTR

The missing difference algorithms give new attacks against the CTR mode and other related constructions, such as Wegman-Carter-Shoup MACs.

### 5.5.1 Attacking CTR in the chosen-prefix secret-suffix model

We consider collision attacks against the CTR mode in the chosen-prefix secret-suffix model [HRR+15], given an oracle $\mathcal{O}: M \mapsto \mathcal{E}(M \parallel S)$.

Instead of having the chosen message $M$ and the secret $S$ encrypted in separate blocks, the attacker can use a message $M$ of length $n/2$, so that the first block of plaintext contains $n/2$ known bytes and $n/2$ secret bytes. By making a large number of queries with the same message $M$, she applies the known prefix sieving algorithm to this block and recovers the first $n/2$ secret bytes with complexity $\tilde{O}(2^{n/2})$.

Then she makes a set of queries with an empty message $M$, so that the first block of plaintext contains $n$ bytes of $S$. Since the first $n/2$ bytes have been recovered already, she applies the known-prefix sieving again with complexity $\tilde{O}(2^{n/2})$. Eventually, the full secret is recovered iteratively with complexity $\tilde{O}(|S| \times 2^{n/2})$.

In practice, the man-in-the-browser setting gives enough freedom to the attacker to do this block splitting by varying the length of some headers.

### 5.5.2 Attacking Wegman-Carter-Shoup MACs

Because the fast convolution algorithm requires few assumptions, it is applicable to other modes of operation based on CTR. We consider the Wegman-Carter-Shoup MAC construction [Sho96]; it uses a block cipher $E$ and a keyed universal hash function $h$, with keys $k_1$ and $k_2$. Given a message $M$ and a nonce $N$, the MAC is defined as:

$$ \mathrm{MAC}(N, M) = h_{k_1}(M) \oplus E_{k_2}(N) $$

To apply our attack, we use two fixed messages $M$ and $M'$, and we capture many values $\mathrm{MAC}(N, M)$ in a list $\mathcal{A}$ and values $\mathrm{MAC}(N', M')$ in a list $\mathcal{B}$, all using unique nonces. We remark that $\forall N \neq N': E_{k_2}(N) \oplus E_{k_2}(N') \neq 0$, therefore we recover $h_{k_1}(M) \oplus h_{k_1}(M')$ by solving the missing difference problem with $\mathcal{A}$ and $\mathcal{B}$.

In practical constructions such as GMAC [MV04] and Poly1305 [Ber05], $h$ is a polynomial evaluation and recovering $h_{k_1}(M) \oplus h_{k_1}(M')$ is sufficient to recover the hash key $k_1$, leading to universal forgeries.

**Comparison with previous attacks against GMAC.** There are several known attacks against GCM and GMAC, but none of them seems to allow universal forgery with just $2^{2n/3}$ blocks of data and $2^{2n/3}$ computations. In particular, Handschuh and Preneel [HP08] gave a weak-key attack that can also be used to recover the hash key without weak key assumptions, using roughly $2^{n/2}$ messages of $2^{n/2}$ blocks. Later work extended these weak key properties [Saa12; PC15] but an attack still requires about $2^n$ blocks in total when no assumptions are made about the key.

A work done in parallel with ours recovers the hash key using $\mathcal{O}(2^{n/2})$ short queries, and $\mathcal{O}(2^n)$ computation [LP18]. Actually, their attack is essentially equivalent to the