EUROCRYPT 2001: Advances in Cryptology — EUROCRYPT 2001 pp 420-436

# 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)

## Abstract

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.

## Keywords

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

## References

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.
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, http://csrc.nist.gov/encryption/aes/round2/AESAlgs/Rijndael/Rijndael.pdf, 1999.
6. 6.
H. Feistel, Cryptography and computer privacy, Scientific American, Vol. 228, No. 5, pp. 15–23, May 1973.
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.
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.

## 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