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 betw...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/164485 |
| _version_ | 1811685112363876352 |
|---|---|
| author | Peyrin, Thomas Tan, Quan Quan |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Peyrin, Thomas Tan, Quan Quan |
| author_sort | Peyrin, Thomas |
| collection | NTU |
| 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. 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. |
| first_indexed | 2024-10-01T04:39:21Z |
| format | Journal Article |
| id | ntu-10356/164485 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T04:39:21Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | ntu-10356/1644852023-02-28T20:10:54Z Mind your path: on (key) dependencies in differential characteristics Peyrin, Thomas Tan, Quan Quan School of Physical and Mathematical Sciences Science::Mathematics Differential Cryptanalysis Key Dependent 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 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. Published version 2023-01-30T02:01:40Z 2023-01-30T02:01:40Z 2022 Journal Article 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 2519-173X https://hdl.handle.net/10356/164485 10.46586/tosc.v2022.i4.179-207 2-s2.0-85143725797 4 2022 179 207 en IACR Transactions on Symmetric Cryptology © 2022 Thomas Peyrin, Quan Quan Tan. This work is licensed under a Creative Commons Attribution 4.0 International License. application/pdf |
| spellingShingle | Science::Mathematics Differential Cryptanalysis Key Dependent Characteristics Peyrin, Thomas Tan, Quan Quan Mind your path: on (key) dependencies in differential characteristics |
| 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 | Science::Mathematics Differential Cryptanalysis Key Dependent Characteristics |
| url | https://hdl.handle.net/10356/164485 |
| work_keys_str_mv | AT peyrinthomas mindyourpathonkeydependenciesindifferentialcharacteristics AT tanquanquan mindyourpathonkeydependenciesindifferentialcharacteristics |