Paper published in a book (Scientific congresses, symposiums and conference proceedings)
Meet-in-the-Filter and Dynamic Counting with Applications to Speck
Biryukov, Alexei; Cardoso Dos Santos, Luan; Teh, Je Sen et al.
2023In Tibouchi, Mehdi; Wang, Xiaofeng (Eds.) Applied Cryptography and Network Security, 21st International Conference, ACNS 2023, Kyoto, Japan, June 19–22, 2023, Proceedings, Part I
Peer reviewed
 

Files


Full Text
2022-673.pdf
Author preprint (1.24 MB)
Download

All documents in ORBilu are protected by a user license.

Send to



Details



Keywords :
Symmetric-key; Differential cryptanalysis; ARX; Speck
Abstract :
[en] 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 main idea of the MiF technique is to stop the difference propagation earlier in the cipher, allowing to use differentials with higher probability. This comes at the expense of a deeper analysis phase in the bottom rounds possible due to the slow diffusion of the target cipher. 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 ARXbased family of block ciphers Speck. We improve the time complexities of the best known attacks up to 15 rounds of Speck32 and 20 rounds of Speck64/128. Notably, our new attack on 11 rounds of Speck32 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. It significantly improves the previous deep learning-based attack by Gohr from CRYPTO 2019, which has time complexity 238. As an important milestone, our conventional cryptanalysis method sets a new high benchmark to beat for cryptanalysis relying on machine learning.
Disciplines :
Computer science
Author, co-author :
Biryukov, Alexei ;  University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
Cardoso Dos Santos, Luan ;  University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
Teh, Je Sen ;  University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > Cryptolux ; Universiti Sains Malaysia
Udovenko, Aleksei  ;  University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > Cryptolux
Velichkov, Vesselin;  University of Edinburgh
External co-authors :
yes
Language :
English
Title :
Meet-in-the-Filter and Dynamic Counting with Applications to Speck
Publication date :
2023
Event name :
21st International Conference on Applied Cryptography and Network Security
Event place :
Kyoto, Japan
Event date :
from 19-06-2023 to 22-06-2023
Audience :
International
Main work title :
Applied Cryptography and Network Security, 21st International Conference, ACNS 2023, Kyoto, Japan, June 19–22, 2023, Proceedings, Part I
Editor :
Tibouchi, Mehdi
Wang, Xiaofeng
Publisher :
Springer
Pages :
149-177
Peer reviewed :
Peer reviewed
Focus Area :
Security, Reliability and Trust
Additional URL :
FnR Project :
FNR13641232 - Analysis And Protection Of Lightweight Cryptographic Algorithms, 2019 (01/01/2021-31/12/2023) - Alex Biryukov
Funders :
FNR - Fonds National de la Recherche [LU]
Available on ORBilu :
since 19 December 2022

Statistics


Number of views
55 (8 by Unilu)
Number of downloads
17 (1 by Unilu)

Scopus citations®
 
0
Scopus citations®
without self-citations
0

Bibliography


Similar publications



Contact ORBilu