Paper 2021/1194

Automated Truncation of Differential Trails and Trail Clustering in ARX

Alex Biryukov, Luan Cardoso dos Santos, Daniel Feher, Vesselin Velichkov, and Giuseppe Vitto

Abstract

We propose a tool for automated truncation of differential trails in ciphers using modular addition, bitwise rotation, and XOR (ARX). The tool takes as input a differential trail and produces as output a set of truncated differential trails. The set represents all possible truncations of the input trail according to certain predefined rules. A linear-time algorithm for the exact computation of the differential probability of a truncated trail that follows the truncation rules is proposed. We further describe a method to merge the set of truncated trails into a compact set of non-overlapping truncated trails with associated probability and we demonstrate the application of the tool on block cipher Speck64. We have also investigated the effect of clustering of differential trails around a fixed input trail. The best cluster that we have found for $15$ rounds has probability $2^{-55.03}$ (consisting of 389 unique output differences) which allows us to build a distinguisher using $128$ times less data than the one based on just the single best trail, which has probability $2^{-62}$. Moreover, we show examples for Speck64 where a cluster of trails around a suboptimal (in terms of probability) input trail results in higher overall probability compared to a cluster obtained around the best differential trail.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. Minor revision.
Keywords
Symmetric-keyBlock CiphersDifferential CryptanalysisTruncated DifferentialsARXSpeck
Contact author(s)
giuseppe vitto @ uni lu
alex biryukov @ uni lu
luan cardoso @ uni lu
daniel feher @ uni lu
vvelichk @ ed ac uk
History
2021-09-17: received
Short URL
https://ia.cr/2021/1194
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1194,
      author = {Alex Biryukov and Luan Cardoso dos Santos and Daniel Feher and Vesselin Velichkov and Giuseppe Vitto},
      title = {Automated Truncation of Differential Trails and Trail Clustering in ARX},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1194},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1194}},
      url = {https://eprint.iacr.org/2021/1194}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.