Paper 2016/096

Provable Security Evaluation of Structures against Impossible Differential and Zero Correlation Linear Cryptanalysis

Bing Sun, Meicheng Liu, Jian Guo, Vincent Rijmen, and Ruilin Li

Abstract

Impossible differential and zero correlation linear cryptanalysis are two of the most important cryptanalytic vectors. To characterize the impossible differentials and zero correlation linear hulls which are independent of the choices of the non-linear components, Sun et al. proposed the structure deduced by a block cipher at CRYPTO 2015. Based on that, we concentrate in this paper on the security of the SPN structure and Feistel structure with SP-type round functions. Firstly, we prove that for an SPN structure, if \alpha_1\rightarrow\beta_1 and \alpha_2\rightarrow\beta_ are possible differentials, \alpha_1|\alpha_2\rightarrow\beta_1|\beta_2 is also a possible differential, i.e., the OR "|" operation preserves differentials. Secondly, we show that for an SPN structure, there exists an r-round impossible differential if and only if there exists an r-round impossible differential \alpha\not\rightarrow\beta where the Hamming weights of both \alpha and \beta are 1. Thus for an SPN structure operating on m bytes, the computation complexity for deciding whether there exists an impossible differential can be reduced from O(2^{2m}) to O(m^2). Thirdly, we associate a primitive index with the linear layers of SPN structures. Based on the matrices theory over integer rings, we prove that the length of impossible differentials of an SPN structure is upper bounded by the primitive index of the linear layers. As a result we show that, unless the details of the S-boxes are considered, there do not exist 5-round impossible differentials for the AES and ARIA. Lastly, based on the links between impossible differential and zero correlation linear hull, we projected these results on impossible differentials to zero correlation linear hulls. It is interesting to note some of our results also apply to the Feistel structures with SP-type round functions.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in EUROCRYPT 2016
Keywords
Impossible differentialZero correlation linearSPN structureFeistel structureAESCamelliaARIA
Contact author(s)
happy_come @ 163 com
History
2016-02-05: received
Short URL
https://ia.cr/2016/096
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/096,
      author = {Bing Sun and Meicheng Liu and Jian Guo and Vincent Rijmen and Ruilin Li},
      title = {Provable Security Evaluation of Structures against Impossible Differential and Zero Correlation Linear Cryptanalysis},
      howpublished = {Cryptology ePrint Archive, Paper 2016/096},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/096}},
      url = {https://eprint.iacr.org/2016/096}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.