Meet-in-the-Filter and Dynamic Counting with Applications to Speck

Alex Biryukov; Luan Cardoso dos Santos; Je Sen Teh; Aleksei Udovenko; Vesselin Velichkov

doi:10.1007/978-3-031-33488-7_6

Meet-in-the-Filter and Dynamic Counting with Applications to Speck

Alex Biryukov, Luan Cardoso dos Santos, Je Sen Teh, Aleksei Udovenko^*, Vesselin Velichkov

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract / Description of output

We propose a new cryptanalytic tool for differential cryptanalysis, called meet-in-the-filter (MiF). It is suitable for ciphers with a slow or incomplete diffusion layer such as the ones based on Addition-Rotation-XOR (ARX). The MiF technique uses a meet-in-the-middle matching to construct differential trails connecting the differential’s output and the ciphertext difference. The proposed trails are used in the key recovery procedure, reducing time complexity and allowing flexible time-data trade-offs. In addition, we show how to combine MiF with a dynamic counting technique for key recovery. We illustrate MiF in practice by reporting improved attacks on the ARX -based family of block ciphers Speck. We improve the time complexities of the best known attacks up to 15 rounds of Speck 32 and 20 rounds of Speck 64/128. Notably, our new attack on 11 rounds of Speck 32 has practical analysis and data complexities of 2^24.66 and 2^26.70 respectively, and was experimentally verified, recovering the master key in a matter of seconds.

Original language	English
Title of host publication	Applied Cryptography and Network Security
Subtitle of host publication	21st International Conference, ACNS 2023, Proceedings
Editors	Mehdi Tibouchi, XiaoFeng Wang
Publisher	Springer
Pages	149-177
Number of pages	29
Volume	13905
ISBN (Electronic)	9783031334887
ISBN (Print)	9783031334870
DOIs	https://doi.org/10.1007/978-3-031-33488-7_6
Publication status	Published - 29 May 2023
Event	21st International Conference on Applied Cryptography and Network Security - Kyoto, Japan Duration: 19 Jun 2023 → 22 Jun 2023 Conference number: 21

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	13905
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	21st International Conference on Applied Cryptography and Network Security
Abbreviated title	ACNS 2023
Country/Territory	Japan
City	Kyoto
Period	19/06/23 → 22/06/23

Keywords / Materials (for Non-textual outputs)

ARX
Differential cryptanalysis
Speck
Symmetric-key

Access to Document

10.1007/978-3-031-33488-7_6Licence: All Rights Reserved

Meet-In-The-Filter_BIRYUKOV_DOA16032023_AFV_CC BYAccepted author manuscript, 1.19 MBLicence: Creative Commons: Attribution (CC-BY)

https://eprint.iacr.org/2022/673Licence: Creative Commons: Attribution (CC-BY)
https://link.springer.com/chapter/10.1007/978-3-031-33488-7_6#chapter-infoLicence: All Rights Reserved

Cite this

Biryukov, A., Cardoso dos Santos, L., Teh, J. S., Udovenko, A., & Velichkov, V. (2023). Meet-in-the-Filter and Dynamic Counting with Applications to Speck. In M. Tibouchi, & X. Wang (Eds.), Applied Cryptography and Network Security : 21st International Conference, ACNS 2023, Proceedings (Vol. 13905, pp. 149-177). (Lecture Notes in Computer Science; Vol. 13905). Springer. https://doi.org/10.1007/978-3-031-33488-7_6

@inproceedings{7a10d781e1c34ce29b6ed6622aebc021,

title = "Meet-in-the-Filter and Dynamic Counting with Applications to Speck",

abstract = "We propose a new cryptanalytic tool for differential cryptanalysis, called meet-in-the-filter (MiF). It is suitable for ciphers with a slow or incomplete diffusion layer such as the ones based on Addition-Rotation-XOR (ARX). The MiF technique uses a meet-in-the-middle matching to construct differential trails connecting the differential{\textquoteright}s output and the ciphertext difference. The proposed trails are used in the key recovery procedure, reducing time complexity and allowing flexible time-data trade-offs. In addition, we show how to combine MiF with a dynamic counting technique for key recovery. We illustrate MiF in practice by reporting improved attacks on the ARX -based family of block ciphers Speck. We improve the time complexities of the best known attacks up to 15 rounds of Speck 32 and 20 rounds of Speck 64/128. Notably, our new attack on 11 rounds of Speck 32 has practical analysis and data complexities of 224.66 and 226.70 respectively, and was experimentally verified, recovering the master key in a matter of seconds.",

keywords = "ARX, Differential cryptanalysis, Speck, Symmetric-key",

author = "Alex Biryukov and {Cardoso dos Santos}, Luan and Teh, {Je Sen} and Aleksei Udovenko and Vesselin Velichkov",

note = "Funding Information: The work was supported by the Luxembourg National Research Fund{\textquoteright}s (FNR) and the German Research Foundation{\textquoteright}s (DFG) joint project APLICA (C19/IS/13641232) and FNR{\textquoteright}s project SP2 (PRIDE15/10621687/SPsquared).; 21st International Conference on Applied Cryptography and Network Security, ACNS 2023 ; Conference date: 19-06-2023 Through 22-06-2023",

year = "2023",

month = may,

day = "29",

doi = "10.1007/978-3-031-33488-7_6",

language = "English",

isbn = "9783031334870",

volume = "13905",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "149--177",

editor = "Mehdi Tibouchi and XiaoFeng Wang",

booktitle = "Applied Cryptography and Network Security",

address = "United Kingdom",

}

Biryukov, A, Cardoso dos Santos, L, Teh, JS, Udovenko, A & Velichkov, V 2023, Meet-in-the-Filter and Dynamic Counting with Applications to Speck. in M Tibouchi & X Wang (eds), Applied Cryptography and Network Security : 21st International Conference, ACNS 2023, Proceedings. vol. 13905, Lecture Notes in Computer Science, vol. 13905, Springer, pp. 149-177, 21st International Conference on Applied Cryptography and Network Security, Kyoto, Japan, 19/06/23. https://doi.org/10.1007/978-3-031-33488-7_6

Meet-in-the-Filter and Dynamic Counting with Applications to Speck. / Biryukov, Alex; Cardoso dos Santos, Luan; Teh, Je Sen et al.
Applied Cryptography and Network Security : 21st International Conference, ACNS 2023, Proceedings. ed. / Mehdi Tibouchi; XiaoFeng Wang. Vol. 13905 Springer, 2023. p. 149-177 (Lecture Notes in Computer Science; Vol. 13905).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Meet-in-the-Filter and Dynamic Counting with Applications to Speck

AU - Biryukov, Alex

AU - Cardoso dos Santos, Luan

AU - Teh, Je Sen

AU - Udovenko, Aleksei

AU - Velichkov, Vesselin

N1 - Conference code: 21

PY - 2023/5/29

Y1 - 2023/5/29

N2 - We propose a new cryptanalytic tool for differential cryptanalysis, called meet-in-the-filter (MiF). It is suitable for ciphers with a slow or incomplete diffusion layer such as the ones based on Addition-Rotation-XOR (ARX). The MiF technique uses a meet-in-the-middle matching to construct differential trails connecting the differential’s output and the ciphertext difference. The proposed trails are used in the key recovery procedure, reducing time complexity and allowing flexible time-data trade-offs. In addition, we show how to combine MiF with a dynamic counting technique for key recovery. We illustrate MiF in practice by reporting improved attacks on the ARX -based family of block ciphers Speck. We improve the time complexities of the best known attacks up to 15 rounds of Speck 32 and 20 rounds of Speck 64/128. Notably, our new attack on 11 rounds of Speck 32 has practical analysis and data complexities of 224.66 and 226.70 respectively, and was experimentally verified, recovering the master key in a matter of seconds.

AB - We propose a new cryptanalytic tool for differential cryptanalysis, called meet-in-the-filter (MiF). It is suitable for ciphers with a slow or incomplete diffusion layer such as the ones based on Addition-Rotation-XOR (ARX). The MiF technique uses a meet-in-the-middle matching to construct differential trails connecting the differential’s output and the ciphertext difference. The proposed trails are used in the key recovery procedure, reducing time complexity and allowing flexible time-data trade-offs. In addition, we show how to combine MiF with a dynamic counting technique for key recovery. We illustrate MiF in practice by reporting improved attacks on the ARX -based family of block ciphers Speck. We improve the time complexities of the best known attacks up to 15 rounds of Speck 32 and 20 rounds of Speck 64/128. Notably, our new attack on 11 rounds of Speck 32 has practical analysis and data complexities of 224.66 and 226.70 respectively, and was experimentally verified, recovering the master key in a matter of seconds.

KW - ARX

KW - Differential cryptanalysis

KW - Speck

KW - Symmetric-key

U2 - 10.1007/978-3-031-33488-7_6

DO - 10.1007/978-3-031-33488-7_6

M3 - Conference contribution

AN - SCOPUS:85163397350

SN - 9783031334870

VL - 13905

T3 - Lecture Notes in Computer Science

SP - 149

EP - 177

BT - Applied Cryptography and Network Security

A2 - Tibouchi, Mehdi

A2 - Wang, XiaoFeng

PB - Springer

T2 - 21st International Conference on Applied Cryptography and Network Security

Y2 - 19 June 2023 through 22 June 2023

ER -

Biryukov A, Cardoso dos Santos L, Teh JS, Udovenko A, Velichkov V. Meet-in-the-Filter and Dynamic Counting with Applications to Speck. In Tibouchi M, Wang X, editors, Applied Cryptography and Network Security : 21st International Conference, ACNS 2023, Proceedings. Vol. 13905. Springer. 2023. p. 149-177. (Lecture Notes in Computer Science). doi: 10.1007/978-3-031-33488-7_6