Automated Truncation of Differential Trails and Trail Clustering in ARX

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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.
Original languageEnglish
Title of host publicationSelected Areas in Cryptography
Subtitle of host publication28th International Conference, Virtual Event, September 29 – October 1, 2021, Revised Selected Papers
EditorsRiham Al Tawy, Andreas Hülsing
PublisherSpringer International Publishing
Number of pages31
ISBN (Electronic)978-3-030-99277-4
ISBN (Print)978-3-030-99276-7
DOIs
Publication statusPublished - 27 Mar 2022
Event28th Conference on Selected Areas in Cryptography - Virtual
Duration: 29 Sept 20211 Oct 2021
https://www.sac2021.ca/home

Publication series

NameLecture Notes in Computer Science
PublisherSpringer, Cham
Volume13203
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference28th Conference on Selected Areas in Cryptography
Abbreviated titleSAC 2021
Period29/09/211/10/21
Internet address

Keywords / Materials (for Non-textual outputs)

  • Symmetric-key
  • Block ciphers
  • Differential cryptanalysis
  • Truncated Differentials
  • ARX
  • SPECK

Fingerprint

Dive into the research topics of 'Automated Truncation of Differential Trails and Trail Clustering in ARX'. Together they form a unique fingerprint.

Cite this