Improved Parameter Estimates for Correlation and Capacity Deviates in Linear Cryptanalysis
Statistical attacks form an important class of attacks against block ciphers. By analyzing the distribution of the statistics involved in the attack, cryptanalysts aim at providing a good estimate of the data complexity of the attack. Recently multiple papers have drawn attention to how to improve t...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2017-02-01
|
| Series: | IACR Transactions on Symmetric Cryptology |
| Subjects: | |
| Online Access: | https://tosc.iacr.org/index.php/ToSC/article/view/570 |
| _version_ | 1818675410497437696 |
|---|---|
| author | Céline Blondeau Kaisa Nyberg |
| author_facet | Céline Blondeau Kaisa Nyberg |
| author_sort | Céline Blondeau |
| collection | DOAJ |
| description | Statistical attacks form an important class of attacks against block ciphers. By analyzing the distribution of the statistics involved in the attack, cryptanalysts aim at providing a good estimate of the data complexity of the attack. Recently multiple papers have drawn attention to how to improve the accuracy of the estimated success probability of linear key-recovery attacks. In particular, the effect of the key on the distribution of the sample correlation and capacity has been investigated and new statistical models developed. The major problem that remains open is how to obtain accurate estimates of the mean and variance of the correlation and capacity. In this paper, we start by presenting a solution for a linear approximation which has a linear hull comprising a number of strong linear characteristics. Then we generalize this approach to multiple and multidimensional linear cryptanalysis and derive estimates of the variance of the test statistic. Our simplest estimate can be computed given the number of the strong linear approximations involved in the offline analysis and the resulting estimate of the capacity. The results tested experimentally on SMALLPRESENT-[4] show the accuracy of the estimated variance is significantly improved. As an application we give more realistic estimates of the success probability of the multidimensional linear attack of Cho on 26 rounds of PRESENT. |
| first_indexed | 2024-12-17T08:27:08Z |
| format | Article |
| id | doaj.art-1952e01031c442fe85d4b1bb8b474aed |
| institution | Directory Open Access Journal |
| issn | 2519-173X |
| language | English |
| last_indexed | 2024-12-17T08:27:08Z |
| publishDate | 2017-02-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | IACR Transactions on Symmetric Cryptology |
| spelling | doaj.art-1952e01031c442fe85d4b1bb8b474aed2022-12-21T21:56:43ZengRuhr-Universität BochumIACR Transactions on Symmetric Cryptology2519-173X2017-02-0116219110.13154/tosc.v2016.i2.162-191570Improved Parameter Estimates for Correlation and Capacity Deviates in Linear CryptanalysisCéline Blondeau0Kaisa Nyberg1Department of Computer Science, Aalto University School of ScienceDepartment of Computer Science, Aalto University School of ScienceStatistical attacks form an important class of attacks against block ciphers. By analyzing the distribution of the statistics involved in the attack, cryptanalysts aim at providing a good estimate of the data complexity of the attack. Recently multiple papers have drawn attention to how to improve the accuracy of the estimated success probability of linear key-recovery attacks. In particular, the effect of the key on the distribution of the sample correlation and capacity has been investigated and new statistical models developed. The major problem that remains open is how to obtain accurate estimates of the mean and variance of the correlation and capacity. In this paper, we start by presenting a solution for a linear approximation which has a linear hull comprising a number of strong linear characteristics. Then we generalize this approach to multiple and multidimensional linear cryptanalysis and derive estimates of the variance of the test statistic. Our simplest estimate can be computed given the number of the strong linear approximations involved in the offline analysis and the resulting estimate of the capacity. The results tested experimentally on SMALLPRESENT-[4] show the accuracy of the estimated variance is significantly improved. As an application we give more realistic estimates of the success probability of the multidimensional linear attack of Cho on 26 rounds of PRESENT.https://tosc.iacr.org/index.php/ToSC/article/view/570block cipherlinear cryptanalysiskey-recovery attackmultidimensional linear attackmultiple linear attackkey-dependencycorrelationcapacityknown plaintextdistinct known plaintextstatistical model |
| spellingShingle | Céline Blondeau Kaisa Nyberg Improved Parameter Estimates for Correlation and Capacity Deviates in Linear Cryptanalysis IACR Transactions on Symmetric Cryptology block cipher linear cryptanalysis key-recovery attack multidimensional linear attack multiple linear attack key-dependency correlation capacity known plaintext distinct known plaintext statistical model |
| title | Improved Parameter Estimates for Correlation and Capacity Deviates in Linear Cryptanalysis |
| title_full | Improved Parameter Estimates for Correlation and Capacity Deviates in Linear Cryptanalysis |
| title_fullStr | Improved Parameter Estimates for Correlation and Capacity Deviates in Linear Cryptanalysis |
| title_full_unstemmed | Improved Parameter Estimates for Correlation and Capacity Deviates in Linear Cryptanalysis |
| title_short | Improved Parameter Estimates for Correlation and Capacity Deviates in Linear Cryptanalysis |
| title_sort | improved parameter estimates for correlation and capacity deviates in linear cryptanalysis |
| topic | block cipher linear cryptanalysis key-recovery attack multidimensional linear attack multiple linear attack key-dependency correlation capacity known plaintext distinct known plaintext statistical model |
| url | https://tosc.iacr.org/index.php/ToSC/article/view/570 |
| work_keys_str_mv | AT celineblondeau improvedparameterestimatesforcorrelationandcapacitydeviatesinlinearcryptanalysis AT kaisanyberg improvedparameterestimatesforcorrelationandcapacitydeviatesinlinearcryptanalysis |