Paper 2014/100

Improved Slender-set Linear Cryptanalysis

Guo-Qiang Liu, Chen-Hui Jin, and Chuan-Da Qi


In 2013, Borghoff \emph{et al}. introduced a slender-set linear cryptanalysis on PRESENT-like ciphers with key-dependent secret S-boxes. In this paper, we propose an improved slender-set linear attack to PRESENT-like ciphers with secret S-boxes. We investigate three new cryptanalytic techniques, and use them to recover the secret S-boxes efficiently. Our first new idea is that we propose a new technique to support consistency of partitions of the input to the secret S-boxes. Our second new technique is that we present a more efficient method to recover the coordinate functions of secret S-boxes based on more information than that of Borghoff's attack. The third new technique is that we propose a method of constructing all correct coordinate function of secret S-boxes by pruning search algorithm. In particular, we implemented a successful linear attack on the full round Maya in practice. In our experiments, the correct S-box can be recovered with $2^{36}$ known plaintexts, $2^{18.9}$ time complexity and negligible memory complexity at a success rate of 87.5\%. Our attack is the improvement and sequel of Borghoff's work on PRESENT-like cipher with secret S-boxes.

Note: This is the full version of the FSE 2014 paper with the same title.

Available format(s)
Publication info
A minor revision of an IACR publication in FSE 2014
block cipherlinear cryptanalysisPRESENT-likesecret S-box
Contact author(s)
liuguoqiang87 @ hotmail com
2014-02-14: received
Short URL
Creative Commons Attribution


      author = {Guo-Qiang Liu and Chen-Hui Jin and Chuan-Da Qi},
      title = {Improved Slender-set Linear Cryptanalysis},
      howpublished = {Cryptology ePrint Archive, Paper 2014/100},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.