Finding Bit-Based Division Property for Ciphers with Complex Linear Layers
The bit-based division property (BDP) is the most effective technique for finding integral characteristics of symmetric ciphers. Recently, automatic search tools have become one of the most popular approaches to evaluating the security of designs against many attacks. Constraint-aided automatic tool...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2020-05-01
|
| Series: | IACR Transactions on Symmetric Cryptology |
| Subjects: | |
| Online Access: | https://tosc.iacr.org/index.php/ToSC/article/view/8570 |
| _version_ | 1798027575604281344 |
|---|---|
| author | Kai Hu Qingju Wang Meiqin Wang |
| author_facet | Kai Hu Qingju Wang Meiqin Wang |
| author_sort | Kai Hu |
| collection | DOAJ |
| description | The bit-based division property (BDP) is the most effective technique for finding integral characteristics of symmetric ciphers. Recently, automatic search tools have become one of the most popular approaches to evaluating the security of designs against many attacks. Constraint-aided automatic tools for the BDP have been applied to many ciphers with simple linear layers like bit-permutation. Constructing models of complex linear layers accurately and efficiently remains hard. A straightforward method proposed by Sun et al. (called the S method), decomposes a complex linear layer into basic operations like COPY and XOR, then models them one by one. However, this method can easily insert invalid division trails into the solution pool, which results in a quicker loss of the balanced property than the cipher itself would. In order to solve this problem, Zhang and Rijmen propose the ZR method to link every valid trail with an invertible sub-matrix of the matrix corresponding to the linear layer, and then generate linear inequalities to represent all the invertible sub-matrices. Unfortunately, the ZR method is only applicable to invertible binary matrices (defined in Definition 3).
To avoid generating a huge number of inequalities for all the sub-matrices, we build a new model that only includes that the sub-matrix corresponding to a valid trail should be invertible. The computing scale of our model can be tackled by most of SMT/SAT solvers, which makes our method practical. For applications, we improve the previous BDP for LED and MISTY1. We also give the 7-round BDP results for Camellia with FL/FL−1, which is the longest to date.
Furthermore, we remove the restriction of the ZR method that the matrix has to be invertible, which provides more choices for future designs. Thanks to this, we also reproduce 5-round key-dependent integral distinguishers proposed at Crypto 2016 which cannot be obtained by either the S or ZR methods. |
| first_indexed | 2024-04-11T18:53:50Z |
| format | Article |
| id | doaj.art-1b996b8a01f142eb881519991914afa9 |
| institution | Directory Open Access Journal |
| issn | 2519-173X |
| language | English |
| last_indexed | 2024-04-11T18:53:50Z |
| publishDate | 2020-05-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | IACR Transactions on Symmetric Cryptology |
| spelling | doaj.art-1b996b8a01f142eb881519991914afa92022-12-22T04:08:14ZengRuhr-Universität BochumIACR Transactions on Symmetric Cryptology2519-173X2020-05-012020110.13154/tosc.v2020.i1.396-424Finding Bit-Based Division Property for Ciphers with Complex Linear LayersKai Hu0Qingju Wang1Meiqin Wang2School of Cyber Science and Technology, Shandong University, Qingdao, Shandong, 266237, China; Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Qingdao, Shandong, 266237, ChinaInterdisciplinary Centre for Security, Reliability (SnT), University of Luxembourg, L-4364 Esch-sur-Alzette, LuxembourgSchool of Cyber Science and Technology, Shandong University, Qingdao, Shandong, 266237, China; Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Qingdao, Shandong, 266237, ChinaThe bit-based division property (BDP) is the most effective technique for finding integral characteristics of symmetric ciphers. Recently, automatic search tools have become one of the most popular approaches to evaluating the security of designs against many attacks. Constraint-aided automatic tools for the BDP have been applied to many ciphers with simple linear layers like bit-permutation. Constructing models of complex linear layers accurately and efficiently remains hard. A straightforward method proposed by Sun et al. (called the S method), decomposes a complex linear layer into basic operations like COPY and XOR, then models them one by one. However, this method can easily insert invalid division trails into the solution pool, which results in a quicker loss of the balanced property than the cipher itself would. In order to solve this problem, Zhang and Rijmen propose the ZR method to link every valid trail with an invertible sub-matrix of the matrix corresponding to the linear layer, and then generate linear inequalities to represent all the invertible sub-matrices. Unfortunately, the ZR method is only applicable to invertible binary matrices (defined in Definition 3). To avoid generating a huge number of inequalities for all the sub-matrices, we build a new model that only includes that the sub-matrix corresponding to a valid trail should be invertible. The computing scale of our model can be tackled by most of SMT/SAT solvers, which makes our method practical. For applications, we improve the previous BDP for LED and MISTY1. We also give the 7-round BDP results for Camellia with FL/FL−1, which is the longest to date. Furthermore, we remove the restriction of the ZR method that the matrix has to be invertible, which provides more choices for future designs. Thanks to this, we also reproduce 5-round key-dependent integral distinguishers proposed at Crypto 2016 which cannot be obtained by either the S or ZR methods.https://tosc.iacr.org/index.php/ToSC/article/view/8570Complex linear layerNon-binary matrixBit-based division propertySMT/SATInvertible |
| spellingShingle | Kai Hu Qingju Wang Meiqin Wang Finding Bit-Based Division Property for Ciphers with Complex Linear Layers IACR Transactions on Symmetric Cryptology Complex linear layer Non-binary matrix Bit-based division property SMT/SAT Invertible |
| title | Finding Bit-Based Division Property for Ciphers with Complex Linear Layers |
| title_full | Finding Bit-Based Division Property for Ciphers with Complex Linear Layers |
| title_fullStr | Finding Bit-Based Division Property for Ciphers with Complex Linear Layers |
| title_full_unstemmed | Finding Bit-Based Division Property for Ciphers with Complex Linear Layers |
| title_short | Finding Bit-Based Division Property for Ciphers with Complex Linear Layers |
| title_sort | finding bit based division property for ciphers with complex linear layers |
| topic | Complex linear layer Non-binary matrix Bit-based division property SMT/SAT Invertible |
| url | https://tosc.iacr.org/index.php/ToSC/article/view/8570 |
| work_keys_str_mv | AT kaihu findingbitbaseddivisionpropertyforcipherswithcomplexlinearlayers AT qingjuwang findingbitbaseddivisionpropertyforcipherswithcomplexlinearlayers AT meiqinwang findingbitbaseddivisionpropertyforcipherswithcomplexlinearlayers |