Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/164485
Title: Mind your path: on (key) dependencies in differential characteristics
Authors: Peyrin, Thomas
Tan, Quan Quan
Keywords: Science::Mathematics
Issue Date: 2022
Source: Peyrin, T. & Tan, Q. Q. (2022). Mind your path: on (key) dependencies in differential characteristics. IACR Transactions On Symmetric Cryptology, 2022(4), 179-207. https://dx.doi.org/10.46586/tosc.v2022.i4.179-207
Journal: IACR Transactions on Symmetric Cryptology
Abstract: Cryptanalysts have been looking for differential characteristics in ciphers for decades and it remains unclear how the subkey values and more generally the Markov assumption impacts exactly their probability estimation. There were theoretical efforts considering some simple linear relationships between differential characteristics and subkey values, but the community has not yet explored many possible nonlinear dependencies one can find in differential characteristics. Meanwhile, the overwhelming majority of cryptanalysis works still assume complete independence between the cipher rounds. We give here a practical framework and a corresponding tool to investigate all such linear or nonlinear effects and we show that they can have an important impact on the security analysis of many ciphers. Surprisingly, this invalidates many differential characteristics that appeared in the literature in the past years: we have checked differential characteristics from 8 articles (4 each for both SKINNY and GIFT) and most of these published paths are impossible or working only for a very small proportion of the key space. We applied our method to SKINNY and GIFT, but we expect more impossibilities for other ciphers. To showcase our advances in the dependencies analysis, in the case of SKINNY we are able to obtain a more accurate probability distribution of a differential characteristic with respect to the keys (with practical verification when it is computationally feasible). Our work indicates that newly proposed differential characteristics should now come with an analysis of how the key values and the Markov assumption might or might not affect/invalidate them. In this direction, more constructively, we include a proof of concept of how one can incorporate additional constraints into Constraint Programming so that the search for differential characteristics can avoid (to a large extent) differential characteristics that are actually impossible due to dependency issues our tool detected.
URI: https://hdl.handle.net/10356/164485
ISSN: 2519-173X
DOI: 10.46586/tosc.v2022.i4.179-207
Schools: School of Physical and Mathematical Sciences 
Rights: © 2022 Thomas Peyrin, Quan Quan Tan. This work is licensed under a Creative Commons Attribution 4.0 International License.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
ToSC2022_4_07.pdf613.22 kBAdobe PDFThumbnail
View/Open

SCOPUSTM   
Citations 50

2
Updated on Feb 24, 2024

Web of ScienceTM
Citations 50

1
Updated on Oct 27, 2023

Page view(s)

86
Updated on Feb 24, 2024

Download(s)

15
Updated on Feb 24, 2024

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.