Automated Truncation of Differential Trails and Trail Clustering in ARX

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

doi:10.1007/978-3-030-99277-4_14

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 proceeding › Conference 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⁻⁶². 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 language	English
Title of host publication	Selected Areas in Cryptography
Subtitle of host publication	28th International Conference, Virtual Event, September 29 – October 1, 2021, Revised Selected Papers
Editors	Riham Al Tawy, Andreas Hülsing
Publisher	Springer
Number of pages	31
ISBN (Electronic)	978-3-030-99277-4
ISBN (Print)	978-3-030-99276-7
DOIs	https://doi.org/10.1007/978-3-030-99277-4_14
Publication status	Published - 27 Mar 2022
Event	28th Conference on Selected Areas in Cryptography - Virtual Duration: 29 Sept 2021 → 1 Oct 2021 https://www.sac2021.ca/home

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer, Cham
Volume	13203
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	28th Conference on Selected Areas in Cryptography
Abbreviated title	SAC 2021
Period	29/09/21 → 1/10/21
Internet address	https://www.sac2021.ca/home

Keywords / Materials (for Non-textual outputs)

Symmetric-key
Block ciphers
Differential cryptanalysis
Truncated Differentials
ARX
SPECK

Access to Document

10.1007/978-3-030-99277-4_14Licence: All Rights Reserved

Automated Truncation_BIRYUKOV_DOA23082021_AFVAccepted author manuscript, 432 KBLicence: All Rights Reserved

https://link.springer.com/chapter/10.1007/978-3-030-99277-4_14Licence: All Rights Reserved

Cite this

Biryukov, A., Cardoso dos Santos, L., Feher, D., Velichkov, V., & Vitto, G. (2022). Automated Truncation of Differential Trails and Trail Clustering in ARX. In R. Al Tawy, & A. Hülsing (Eds.), Selected Areas in Cryptography: 28th International Conference, Virtual Event, September 29 – October 1, 2021, Revised Selected Papers (Lecture Notes in Computer Science; Vol. 13203). Springer. https://doi.org/10.1007/978-3-030-99277-4_14

Biryukov, Alex ; Cardoso dos Santos, Luan ; Feher, Daniel et al. / Automated Truncation of Differential Trails and Trail Clustering in ARX. Selected Areas in Cryptography: 28th International Conference, Virtual Event, September 29 – October 1, 2021, Revised Selected Papers. editor / Riham Al Tawy ; Andreas Hülsing. Springer, 2022. (Lecture Notes in Computer Science).

@inproceedings{45751854eeb44c8a85ecbb84b9bba494,

title = "Automated Truncation of Differential Trails and Trail Clustering in ARX",

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.",

keywords = "Symmetric-key, Block ciphers, Differential cryptanalysis, Truncated Differentials, ARX, SPECK",

author = "Alex Biryukov and {Cardoso dos Santos}, Luan and Daniel Feher and Vesselin Velichkov and Giuseppe Vitto",

note = "Funding Information: Acknowledgements. The authors thank the anonymous reviewers for their time and for the insightful comments and corrections. Luan Cardoso dos Santos was supported by the Luxembourg National Research Fund project SP2 (PRIDE15/ 10621687/SPsquared). Daniel Feher and Giuseppe Vitto were supported by the Luxembourg National Research Fund project FinCrypt (C17/IS/11684537). Funding Information: This work was supported by the Luxembourg National Research Fund (FNR) projects FinCrypt (C17/IS/11684537) and SP2 (PRIDE15/10621687/SPsquared). Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 28th Conference on Selected Areas in Cryptography , SAC 2021 ; Conference date: 29-09-2021 Through 01-10-2021",

year = "2022",

month = mar,

day = "27",

doi = "10.1007/978-3-030-99277-4_14",

language = "English",

isbn = "978-3-030-99276-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

editor = "{Al Tawy}, Riham and Andreas H{\"u}lsing",

booktitle = "Selected Areas in Cryptography",

address = "United Kingdom",

url = "https://www.sac2021.ca/home",

}

Biryukov, A, Cardoso dos Santos, L, Feher, D, Velichkov, V & Vitto, G 2022, Automated Truncation of Differential Trails and Trail Clustering in ARX. in R Al Tawy & A Hülsing (eds), Selected Areas in Cryptography: 28th International Conference, Virtual Event, September 29 – October 1, 2021, Revised Selected Papers. Lecture Notes in Computer Science, vol. 13203, Springer, 28th Conference on Selected Areas in Cryptography , 29/09/21. https://doi.org/10.1007/978-3-030-99277-4_14

Automated Truncation of Differential Trails and Trail Clustering in ARX. / Biryukov, Alex; Cardoso dos Santos, Luan; Feher, Daniel et al.
Selected Areas in Cryptography: 28th International Conference, Virtual Event, September 29 – October 1, 2021, Revised Selected Papers. ed. / Riham Al Tawy; Andreas Hülsing. Springer, 2022. (Lecture Notes in Computer Science; Vol. 13203).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Automated Truncation of Differential Trails and Trail Clustering in ARX

AU - Biryukov, Alex

AU - Cardoso dos Santos, Luan

AU - Feher, Daniel

AU - Velichkov, Vesselin

AU - Vitto, Giuseppe

N1 - Funding Information: Acknowledgements. The authors thank the anonymous reviewers for their time and for the insightful comments and corrections. Luan Cardoso dos Santos was supported by the Luxembourg National Research Fund project SP2 (PRIDE15/ 10621687/SPsquared). Daniel Feher and Giuseppe Vitto were supported by the Luxembourg National Research Fund project FinCrypt (C17/IS/11684537). Funding Information: This work was supported by the Luxembourg National Research Fund (FNR) projects FinCrypt (C17/IS/11684537) and SP2 (PRIDE15/10621687/SPsquared). Publisher Copyright: © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

PY - 2022/3/27

Y1 - 2022/3/27

N2 - 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.

AB - 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.

KW - Symmetric-key

KW - Block ciphers

KW - Differential cryptanalysis

KW - Truncated Differentials

KW - ARX

KW - SPECK

U2 - 10.1007/978-3-030-99277-4_14

DO - 10.1007/978-3-030-99277-4_14

M3 - Conference contribution

SN - 978-3-030-99276-7

T3 - Lecture Notes in Computer Science

BT - Selected Areas in Cryptography

A2 - Al Tawy, Riham

A2 - Hülsing, Andreas

PB - Springer

T2 - 28th Conference on Selected Areas in Cryptography

Y2 - 29 September 2021 through 1 October 2021

ER -

Biryukov A, Cardoso dos Santos L, Feher D, Velichkov V, Vitto G. Automated Truncation of Differential Trails and Trail Clustering in ARX. In Al Tawy R, Hülsing A, editors, Selected Areas in Cryptography: 28th International Conference, Virtual Event, September 29 – October 1, 2021, Revised Selected Papers. Springer. 2022. (Lecture Notes in Computer Science). doi: 10.1007/978-3-030-99277-4_14

Automated Truncation of Differential Trails and Trail Clustering in ARX

Abstract / Description of output

Publication series

Conference

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Cite this