New Method for Upper Bounding the Maximum Average Linear Hull Probability for SPNs

  • Liam Keliher
  • Henk Meijer
  • Stafford Tavares
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2045)


We present a new algorithm for upper bounding the maximum average linear hull probability for SPNs, a value required to determine provable security against linear cryptanalysis. The best previous result (Hong et al. [9]) applies only when the linear transformation branch number (B) is M or (M + 1) (maximal case), where M is the number of s-boxes per round. In contrast, our upper bound can be computed for any value of B. Moreover, the new upper bound is a function of the number of rounds (other upper bounds known to the authors are not). When B = M, our upper bound is consistently superior to [9]. When B = (M + 1), our upper bound does not appear to improve on [9]. On application to Rijndael (128-bit block size, 10 rounds), we obtain the upper bound UB = 2−75, corresponding to a lower bound on the data complexity of \( \frac{8} {{UB}} = {\text{2}}^{{\text{78}}} \) (for 96.7% success rate). Note that this does not demonstrate the existence of a such an attack, but is, to our knowledge, the first such lower bound.


substitution-permutation networks linear cryptanalysis maximum average linear hull probability provable security 


  1. 1.
    E. Biham, On Matsui’s linear cryptanalysis, Advances in Cryptology—EUROCRYPT'94, Springer-Verlag, pp. 341–355, 1995.Google Scholar
  2. 2.
    E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems, Journal of Cryptology, Vol. 4, No. 1, pp. 3–72, 1991.zbMATHCrossRefMathSciNetGoogle Scholar
  3. 3.
    J. Daemen, R. Govaerts, and J. Vandewalle, Correlation matrices, Fast Software Encryption: Second International Workshop, Springer-Verlag, pp. 275–285, 1995.Google Scholar
  4. 4.
    J. Daemen, L. Knudsen, and V. Rijmen, The block cipher SQUARE, Fast Software Encryption—FSE'97, Springer-Verlag, pp. 149–165, 1997.Google Scholar
  5. 5.
    J. Daemen and V. Rijmen, AES proposal: Rijndael,, 1999.
  6. 6.
    H. Feistel, Cryptography and computer privacy, Scientific American, Vol. 228, No. 5, pp. 15–23, May 1973.CrossRefGoogle Scholar
  7. 7.
    C. Harpes, G. Kramer, and J. Massey, Agener alization of linear cryptanalysis and the applicability of Matsui’s piling-up lemma, Advances in Cryptology—EUROCRYPT'95, Springer-Verlag, pp. 24–38, 1995.Google Scholar
  8. 8.
    H.M. Heys and S.E. Tavares, Substitution-permutation networks resistant to differential and linear cryptanalysis, Journal of Cryptology, Vol. 9, No. 1, pp. 1–19, 1996.zbMATHMathSciNetCrossRefGoogle Scholar
  9. 9.
    S. Hong, S. Lee, J. Lim, J. Sung, and D. Cheon, Provable security against differential and linear cryptanalysis for the SPN structure, Fast Software Encryption (FSE 2000), Proceedings to be published by Springer-Verlag.Google Scholar
  10. 10.
    L.R. Knudsen, Practically secure Feistel ciphers, Fast Software Encryption, Springer-Verlag, pp. 211–221, 1994.Google Scholar
  11. 11.
    M. Matsui, Linear cryptanalysis method for DES cipher, Advances in Cryptology—EUROCRYPT'93, Springer-Verlag, pp. 386–397, 1994.Google Scholar
  12. 12.
    M. Matsui, On correlation between the order of s-boxes and the strength of DES, Advances in Cryptology—EUROCRYPT'94, Springer-Verlag, pp. 366–375, 1995.Google Scholar
  13. 13.
    W. Meier and O. Staffelbach, Nonlinearity criteria for cryptographic functions, Advances in Cryptology—EUROCRYPT'89, Springer-Verlag, pp. 549–562, 1990.Google Scholar
  14. 14.
    K. Nyberg, Linear approximation of block ciphers, Advances in Cryptology—EUROCRYPT'94, Springer-Verlag, pp. 439–444, 1995.Google Scholar
  15. 15.
    C.E. Shannon, Communication theory of secrecy systems, Bell System Technical Journal, Vol. 28, no. 4, pp. 656–715, 1949.MathSciNetzbMATHGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2001

Authors and Affiliations

  • Liam Keliher
    • 1
  • Henk Meijer
    • 1
  • Stafford Tavares
    • 2
  1. 1.Department of Computing and Information ScienceQueen's UniversityKingstonCanada
  2. 2.Department of Electrical and Computer EngineeringQueen's UniversityKingstonCanada

Personalised recommendations