International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Kaisa Nyberg

Publications

Year
Venue
Title
2021
TOSC
Statistical Model of Correlation Difference and Related-Key Linear Cryptanalysis 📺
Kaisa Nyberg
The goal of this work is to propose a related-key model for linear cryptanalysis. We start by giving the mean and variance of the difference of sampled correlations of two Boolean functions when using the same sample of inputs to compute both correlations. This result is further extended to determine the mean and variance of the difference of correlations of a pair of Boolean functions taken over a random data sample of fixed size and over a random pair of Boolean functions. We use the properties of the multinomial distribution to achieve these results without independence assumptions. Using multivariate normal approximation of the multinomial distribution we obtain that the distribution of the difference of related-key correlations is approximately normal. This result is then applied to existing related-key cryptanalyses. We obtain more accurate right-key and wrong-key distributions and remove artificial assumptions about independence of sampled correlations. We extend this study to using multiple linear approximations and propose a Χ2-type statistic, which is proven to be Χ2 distributed if the linear approximations are independent. We further examine this statistic for multidimensional linear approximation and discuss why removing the assumption about independence of linear approximations does not work in the related-key setting the same way as in the single-key setting.
2019
JOFC
Multidimensional Linear Cryptanalysis
Linear cryptanalysis introduced by Matsui is a statistical attack which exploits a binary linear relation between plaintext, ciphertext and key, either in Algorithm 1 for recovering one bit of information of the secret key of a block cipher, or in Algorithm 2 for ranking candidate values for a part of the key. The statistical model is based on the expected and observed bias of a single binary value. Multiple linear approximations have been used with the goal to make the linear attack more efficient. More bits of information of the key can potentially be recovered possibly using less data. But then also more elaborated statistical models are needed to capture the joint behaviour of several not necessarily independent binary variables. Also more options are available for generalising the statistics of a single variable to several variables. The multidimensional extension of linear cryptanalysis to be introduced in this paper considers using multiple linear approximations that form a linear subspace. Different extensions of Algorithm 1 and Algorithm 2 will be presented and studied. The methods will be based on known statistical tools such as goodness-of-fit test and log-likelihood ratio. The efficiency of the different methods will be measured and compared in theory and experiments using the concept of advantage introduced by Selçuk. The block cipher Serpent with a reduced number of rounds will be used as test bed. The multidimensional linear cryptanalysis will also be compared with previous methods that use biasedness of multiple linear approximations. It will be shown in the simulations that the multidimensional method is potentially more powerful. Its main theoretical advantage is that the statistical model can be given without the assumption about statistical independence of the linear approximations.
2017
JOFC
2016
TOSC
Improved Parameter Estimates for Correlation and Capacity Deviates in Linear Cryptanalysis
Céline Blondeau Kaisa Nyberg
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.
2015
JOFC
2015
CRYPTO
2014
EUROCRYPT
2014
FSE
2013
EUROCRYPT
2013
FSE
2012
ASIACRYPT
2012
FSE
2009
FSE
2006
FSE
1996
ASIACRYPT
1996
FSE
1995
JOFC
1994
EUROCRYPT
1994
EUROCRYPT
1994
FSE
1993
EUROCRYPT
1993
FSE
1992
CRYPTO
1992
EUROCRYPT
1991
EUROCRYPT
1990
EUROCRYPT

Program Committees

Crypto 2023
FSE 2022
FSE 2020
FSE 2019
FSE 2018
Crypto 2016
Eurocrypt 2015
Asiacrypt 2013
Crypto 2012
Eurocrypt 2012
FSE 2011
FSE 2010
Asiacrypt 2010
Asiacrypt 2009
FSE 2009
FSE 2008 (Program chair)
Asiacrypt 2008
FSE 2007
FSE 2006
Asiacrypt 2006
Eurocrypt 2006
Eurocrypt 2005
PKC 2005
FSE 2005
FSE 2004
FSE 2003
Eurocrypt 2002
FSE 2002
FSE 2001
Eurocrypt 2001
Eurocrypt 2000
Eurocrypt 1998 (Program chair)
Eurocrypt 1997
Asiacrypt 1996