Paper 2022/673

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

Alex Biryukov, University of Luxembourg
Luan Cardoso dos Santos, University of Luxembourg
Je Sen Teh, University of Luxembourg, University Sains Malaysia
Aleksei Udovenko, University of Luxembourg
Vesselin Velichkov, University of Edinburgh
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)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
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
2022-05-31: approved
2022-05-30: received
See all versions
Short URL
https://ia.cr/2022/673
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2022/673}},
      url = {https://eprint.iacr.org/2022/673}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.