Paper 2013/547

Automatic Security Evaluation of Block Ciphers with S-bP Structures against Related-key Differential Attacks

Siwei Sun, Lei Hu, Ling Song, Yonghong Xie, and Peng Wang


Counting the number of active S-boxes is a common way to evaluate the security of symmetric key cryptographic schemes against differential attack. Based on Mixed Integer Linear Programming (MILP), Mouha et al proposed a method to accomplish this task automatically for word-oriented symmetric-key ciphers with SPN structures. However, this method can not be applied directly to block ciphers of SPN structures with bitwise permutation diffusion layers (S-bP structures), due to its ignorance of the diffusion effect derived collaboratively by nonlinear substitution layers and bitwise permutation layers. Moreover, the MILP constrains presented in Mouha et al's method are not enough to describe the differential propagation behaviour of a linear diffusion layer constructed from a non-MDS code, even an almost MDS code. In this paper we extend Mouha et al's method for S-bP structures by introducing new representations for exclusive-or (XOR) differences to describe bit/word level differences simultaneously and by taking the collaborative diffusion effect of S-boxes and bitwise permutations into account. Our method is applied to the block cipher PRESENT-80, an international standard for lightweight symmetric key cryptography, to automatically evaluate its security against differential attacks. We obtain lower bounds on the numbers of active S-boxes in the single-key model for full 31-round PRESENT-80 and in related-key model for round-reduced PRESENT-80 up to 12 rounds, and therefore automatically prove that the full-round PRESENT-80 is secure against single-key differential attack, and the cost of related-key differential attack on the full-round PRESENT-80 is close to that of an exhaustive search: the best related-key differential characteristic for full PRESENT-80 is upper bounded by $2^{-72}$.

Available format(s)
Publication info
Preprint. Minor revision.
Block cipherSPN structureDifferential attackActive S-boxMixed-integer Linear Programming
Contact author(s)
shenxianbeibei @ gmail com
2013-09-04: received
Short URL
Creative Commons Attribution


      author = {Siwei Sun and Lei Hu and Ling Song and Yonghong Xie and Peng Wang},
      title = {Automatic Security Evaluation of Block Ciphers with S-bP Structures against Related-key Differential Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2013/547},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.