Welcome to the resource topic for 2022/1734
Title:
Mind Your Path: On (Key) Dependencies in Differential Characteristics
Authors: Thomas Peyrin, Quan Quan Tan
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.
ePrint: https://eprint.iacr.org/2022/1734
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .