Paper 2022/673
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 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 ARX-based 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 $2^{24.66}$ and $2^{26.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 $2^{38}$. As an important milestone, our conventional cryptanalysis method sets a new high benchmark to beat for cryptanalysis relying on machine learning.
Metadata
- Available format(s)
- Category
- Attacks and cryptanalysis
- Publication info
- Published elsewhere. ACNS 2023
- DOI
- 10.1007/978-3-031-33488-7_6
- Keywords
- Symmetric-keyDifferential cryptanalysisARXSpeck
- Contact author(s)
-
alex biryukov @ uni lu
luan cardoso @ uni lu
jesen_teh @ usm my
aleksei @ affine group
vvelichk @ ed ac uk - History
- 2023-06-07: revised
- 2022-05-30: received
- See all versions
- Short URL
- https://ia.cr/2022/673
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/673, author = {Alex Biryukov and Luan Cardoso dos Santos and Je Sen Teh and Aleksei Udovenko and Vesselin Velichkov}, title = {Meet-in-the-Filter and Dynamic Counting with Applications to Speck}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/673}, year = {2022}, doi = {10.1007/978-3-031-33488-7_6}, url = {https://eprint.iacr.org/2022/673} }