Mind Your Path: On (Key) Dependencies in Differential Characteristics
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 bet...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2022-12-01
|
| Series: | IACR Transactions on Symmetric Cryptology |
| Subjects: | |
| Online Access: | https://tosc.iacr.org/index.php/ToSC/article/view/9976 |
| _version_ | 1811206001979817984 |
|---|---|
| author | Thomas Peyrin Quan Quan Tan |
| author_facet | Thomas Peyrin Quan Quan Tan |
| author_sort | Thomas Peyrin |
| collection | DOAJ |
| description |
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. n 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.
|
| first_indexed | 2024-04-12T03:40:03Z |
| format | Article |
| id | doaj.art-8d57c72e16d54c6da98e5cf8b3ad28dc |
| institution | Directory Open Access Journal |
| issn | 2519-173X |
| language | English |
| last_indexed | 2024-04-12T03:40:03Z |
| publishDate | 2022-12-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | IACR Transactions on Symmetric Cryptology |
| spelling | doaj.art-8d57c72e16d54c6da98e5cf8b3ad28dc2022-12-22T03:49:18ZengRuhr-Universität BochumIACR Transactions on Symmetric Cryptology2519-173X2022-12-012022410.46586/tosc.v2022.i4.179-207Mind Your Path: On (Key) Dependencies in Differential CharacteristicsThomas Peyrin0Quan Quan Tan1Nanyang Technological University, Singapore, SingaporeNanyang Technological University, Singapore, Singapore 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. n 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. https://tosc.iacr.org/index.php/ToSC/article/view/9976differential cryptanalysiskey dependent characteristicslightweight ciphersblock ciphers |
| spellingShingle | Thomas Peyrin Quan Quan Tan Mind Your Path: On (Key) Dependencies in Differential Characteristics IACR Transactions on Symmetric Cryptology differential cryptanalysis key dependent characteristics lightweight ciphers block ciphers |
| title | Mind Your Path: On (Key) Dependencies in Differential Characteristics |
| title_full | Mind Your Path: On (Key) Dependencies in Differential Characteristics |
| title_fullStr | Mind Your Path: On (Key) Dependencies in Differential Characteristics |
| title_full_unstemmed | Mind Your Path: On (Key) Dependencies in Differential Characteristics |
| title_short | Mind Your Path: On (Key) Dependencies in Differential Characteristics |
| title_sort | mind your path on key dependencies in differential characteristics |
| topic | differential cryptanalysis key dependent characteristics lightweight ciphers block ciphers |
| url | https://tosc.iacr.org/index.php/ToSC/article/view/9976 |
| work_keys_str_mv | AT thomaspeyrin mindyourpathonkeydependenciesindifferentialcharacteristics AT quanquantan mindyourpathonkeydependenciesindifferentialcharacteristics |