More Accurate Differential Properties of LED64 and Midori64
In differential cryptanalysis, a differential is more valuable than the single trail belonging to it in general. The traditional way to compute the probability of the differential is to sum the probabilities of all trails within it. The automatic tool for the search of differentials based on Mixed I...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2018-09-01
|
| Series: | IACR Transactions on Symmetric Cryptology |
| Subjects: | |
| Online Access: | https://tosc.iacr.org/index.php/ToSC/article/view/7298 |
| _version_ | 1818394125612875776 |
|---|---|
| author | Ling Sun Wei Wang Meiqin Wang |
| author_facet | Ling Sun Wei Wang Meiqin Wang |
| author_sort | Ling Sun |
| collection | DOAJ |
| description | In differential cryptanalysis, a differential is more valuable than the single trail belonging to it in general. The traditional way to compute the probability of the differential is to sum the probabilities of all trails within it. The automatic tool for the search of differentials based on Mixed Integer Linear Programming (MILP) has been proposed and realises the task of finding multiple trails of a given differential. The problem is whether it is reliable to evaluate the probability of the differential traditionally. In this paper, we focus on two lightweight block ciphers – LED64 and Midori64 and show the more accurate estimation of differential probability considering the key schedule. Firstly, an automated tool based on Boolean Satisfiability Problem (SAT) is put forward to accomplish the automatic search of differentials for ciphers with S-boxes and is applied to LED64 and Midori64. Secondly, we provide an automatic approach to detect the right pairs following a given differential, which can be exploited to calculate the differential property. Applying this technique to the STEP function of LED64, we discover some differentials with enhanced probability. As a result, the previous attacks relying upon high probability differentials can be improved definitely. Thirdly, we present a method to compute an upper-bound of the weak-key ratio for a given differential, which is utilised to analyse 4-round differentials of Midori64. We detect two differentials whose weak-key ratios are much lower than the expected 50%. More than 78% of the keys will make these two differentials being impossible differentials. The idea of the estimation for an upper-bound of the weak-key ratio can be employed for other ciphers and allows us to launch differential attacks more reliably. Finally, we introduce how to compute the enhanced differential probability and evaluate the size of keys achieving the improved probability. Such a property may incur an efficient weak-key attack. For a 4-round differential of Midori64, we obtain an improved differential property for a portion of keys. |
| first_indexed | 2024-12-14T05:56:14Z |
| format | Article |
| id | doaj.art-59335815f2784285a8003fc51ceeeaab |
| institution | Directory Open Access Journal |
| issn | 2519-173X |
| language | English |
| last_indexed | 2024-12-14T05:56:14Z |
| publishDate | 2018-09-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | IACR Transactions on Symmetric Cryptology |
| spelling | doaj.art-59335815f2784285a8003fc51ceeeaab2022-12-21T23:14:34ZengRuhr-Universität BochumIACR Transactions on Symmetric Cryptology2519-173X2018-09-012018310.13154/tosc.v2018.i3.93-123More Accurate Differential Properties of LED64 and Midori64Ling Sun0Wei Wang1Meiqin Wang2Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, China; School of Physical and Mathematical Sciences, Nanyang Technological UniversitySchool of Software, Shandong University; Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong UniversityKey Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong UniversityIn differential cryptanalysis, a differential is more valuable than the single trail belonging to it in general. The traditional way to compute the probability of the differential is to sum the probabilities of all trails within it. The automatic tool for the search of differentials based on Mixed Integer Linear Programming (MILP) has been proposed and realises the task of finding multiple trails of a given differential. The problem is whether it is reliable to evaluate the probability of the differential traditionally. In this paper, we focus on two lightweight block ciphers – LED64 and Midori64 and show the more accurate estimation of differential probability considering the key schedule. Firstly, an automated tool based on Boolean Satisfiability Problem (SAT) is put forward to accomplish the automatic search of differentials for ciphers with S-boxes and is applied to LED64 and Midori64. Secondly, we provide an automatic approach to detect the right pairs following a given differential, which can be exploited to calculate the differential property. Applying this technique to the STEP function of LED64, we discover some differentials with enhanced probability. As a result, the previous attacks relying upon high probability differentials can be improved definitely. Thirdly, we present a method to compute an upper-bound of the weak-key ratio for a given differential, which is utilised to analyse 4-round differentials of Midori64. We detect two differentials whose weak-key ratios are much lower than the expected 50%. More than 78% of the keys will make these two differentials being impossible differentials. The idea of the estimation for an upper-bound of the weak-key ratio can be employed for other ciphers and allows us to launch differential attacks more reliably. Finally, we introduce how to compute the enhanced differential probability and evaluate the size of keys achieving the improved probability. Such a property may incur an efficient weak-key attack. For a 4-round differential of Midori64, we obtain an improved differential property for a portion of keys.https://tosc.iacr.org/index.php/ToSC/article/view/7298DifferentialAutomatic searchSATLED64Midori64 |
| spellingShingle | Ling Sun Wei Wang Meiqin Wang More Accurate Differential Properties of LED64 and Midori64 IACR Transactions on Symmetric Cryptology Differential Automatic search SAT LED64 Midori64 |
| title | More Accurate Differential Properties of LED64 and Midori64 |
| title_full | More Accurate Differential Properties of LED64 and Midori64 |
| title_fullStr | More Accurate Differential Properties of LED64 and Midori64 |
| title_full_unstemmed | More Accurate Differential Properties of LED64 and Midori64 |
| title_short | More Accurate Differential Properties of LED64 and Midori64 |
| title_sort | more accurate differential properties of led64 and midori64 |
| topic | Differential Automatic search SAT LED64 Midori64 |
| url | https://tosc.iacr.org/index.php/ToSC/article/view/7298 |
| work_keys_str_mv | AT lingsun moreaccuratedifferentialpropertiesofled64andmidori64 AT weiwang moreaccuratedifferentialpropertiesofled64andmidori64 AT meiqinwang moreaccuratedifferentialpropertiesofled64andmidori64 |