Abstract
In this paper we examine a class of product ciphers referred to as substitution-permutation networks. We investigate the resistance of these cryptographic networks to two important attacks: differential cryptanalysis and linear cryptanalysis. In particular, we develop upper bounds on the differential characteristic probability and on the probability of a linear approximation as a function of the number of rounds of substitutions. Further, it is shown that using large S-boxes with good diffusion characteristics and replacing the permutation between rounds by an appropriate linear transformation is effective in improving the cipher security in relation to these two attacks.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
C. M. Adams. A Formal and Practical Design Procedure for Substitution-Permutation Network Cryptosystems. Ph.D. thesis, Queen's University, Kingston, Ontario, 1990.
C. M. Adams. On immunity against Biham and Shamir's differential cryptanalysis.Information Processing Letters, 41(2):77–80, 1992.
C. M. Adams and S. E. Tavares. The structured design of cryptographically good S-boxes.Journal of Cryptology, 3(1):27–41, 1990.
F. Ayoub. The design of complete encryption networks using cryptographically equivalent permutations.Computers and Security, 2:261–267, 1982.
E. Biham and A. Shamir. Differential cryptanalysis of DES-like cryptosystems.Journal of Cryptology, 4(1):3–72, 1991.
E. Biham and A. Shamir. Differential cryptanalysis of FEAL and N-Hash.Advances in Cryptology: Proceedings of EUROCRYPT '91, Springer-Verlag, Berlin, pages 1–16, 1991.
E. Biham and A. Shamir. Differential cryptanalysis of Snefru, Khafre, REDOC-II, LOKI, and Lucifer.Advances in Cryptology: Proceedings of CRYPTO '91, Springer-Verlag, Berlin, pages 156–171, 1992.
E. Biham and A. Shamir. Differential cryptanalysis of the full 16-round DES.Advances in Cryptology: Proceedings of CRYPTO '92, Springer-Verlag, Berlin, pages 487–496, 1993.
E. F. Brickell, J. H. Moore, and M. R. Purtill. Structures in the S-boxes of DES.Advances in Cryptology: Proceedings of CRYPTO '86, Springer-Verlag, Berlin, pages 3–8, 1987.
L. Brown, J. Pieprzyk, and J. Seberry. LOKI—a cryptographic primitive for authentication and secrecy applications.Advances in Cryptology: Proceedings of AUSCRYPT '90, Springer-Verlag, Berlin, pages 229–236, 1990.
L. Brown and J. R. Seberry. On the design of permutation P in DES type cryptosystems.Advances in Cryptology: Proceedings of EUROCRYPT '89, Springer-Verlag, Berlin, pages 696–705, 1989.
M. H. Dawson and S. E. Tavares. An expanded set of S-box design criteria based on information theory and its relation to differential-like attacks.Advances in Cryptology: Proceedings of EUROCRYPT '91, Springer-Verlag, Berlin, pages 352–367, 1991.
H. Feistel. Cryptography and computer privacy.Scientific American, 228(5):15–23, 1973.
H. Feistel, W. A. Notz, and J. L. Smith. Some cryptographic techniques for machine-to-machine data communications.Proceedings of the IEEE, 63(11):1545–1554, 1975.
R. Forré. Methods and instruments for designing S-boxes.Journal of Cryptology, 2(3):115–130, 1990.
J. B. Kam and G. I. Davida. A structured design of substitution-permutation encryption networks.IEEE Transactions on Computers, 28(10):747–753, 1979.
L. R. Knudsen. Iterative characteristics of DES and s2-DES.Advances in Cryptology: Proceedings of CRYPTO '92, Springer-Verlag, Berlin, pages 497–511, 1993.
M. Matsui. Linear cryptanalysis method for DES cipher.Advances in Cryptology: Proceedings of EUROCRYPT '93, Springer-Verlag, Berlin, pages 386–397, 1994.
W. Meier and O. Staffelbach. Nonlinearity criteria for cryptographic functions.Advances in Cryptology: Proceedings of EUROCRYPT '89, Springer-Verlag, Berlin, pages 549–562, 1990.
National Bureau of Standards.Data Encryption Standard (DES). Federal Information Processing Standard Publication 46, U.S. Department of Commerce, January 1977.
K. Nyberg. Perfect nonlinear S-boxes.Advances in Cryptology: Proceedings of EUROCRYPT '91, Springer-Verlag, Berlin, pages 378–386, 1991.
K. Nyberg. On the construction of highly nonlinear permutations.Advances in Cryptology: Proceedings of EUROCRYPT '92, Springer-Verlag, Berlin, pages 92–98, 1992.
K. Nyberg. Differentially uniform mappings for cryptography.Advances in Cryptology: Proceedings of EUROCRYPT '93, Springer-Verlag, Berlin, pages 55–64, 1994.
L. O'Connor. An Analysis of Product Ciphers Based on the Properties of Boolean Functions. Ph.D. thesis, University of Waterloo, Ontario, 1992.
L. J. O'Connor. On the distribution of characteristics in bijective mappings.Advances in Cryptology: Proceedings of EUROCRYPT '93, Springer-Verlag, Berlin, pages 360–370, 1994.
J. Pieprzyk and G. Finkelstein. Towards effective nonlinear cryptosystem design.IEE Proceedings, Part E, 135(6):325–335, 1988.
B. Preneel, W. Van Leekwijck, R. Goevarts, and J. Vanderwalle. Propagation characteristics of boolean functions.Advances in Cryptology: Proceedings of EUROCRYPT '90, Springer-Verlag, Berlin, pages 161–173, 1991.
C. E. Shannon. Communication theory of secrecy systems.Bell System Technical Journal, 28:656–715, 1949.
A. Shimizu and S. Miyaguchi. Fast data encipherment algorithm: FEAL.Advances in Cryptology: Proceedings of EUROCRYPT '87, Springer-Verlag, Berlin, pages 267–278, 1988.
M. Sivabalan, S. E. Tavares, and L. E. Peppard. On the design of SP networks from an information-theoretic point of view.Advances in Cryptology: Proceedings of CRYPTO '92, Springer-Verlag, Berlin, pages 260–279, 1993.
A. F. Webster and S. E. Tavares. On the design of S-boxes.Advances in Cryptology: Proceedings of CRYPTO '85, Springer-Verlag, Berlin, pages 523–534, 1986.
Author information
Authors and Affiliations
Additional information
Communicated by Thomas A. Berson
This work was supported by the Natural Sciences and Engineering Research Council of Canada and the Telecommunications Research Institute of Ontario, and was presented at the rump session of CRYPTO '93. Howard Heys is now with Electrical Engineering, Faculty of Engineering and Applied Science, Memorial University of Newfoundland, St. John's, Newfoundland, Canada A1B 3X5.
Rights and permissions
About this article
Cite this article
Heys, H.M., Tavares, S.E. Substitution-permutation networks resistant to differential and linear cryptanalysis. J. Cryptology 9, 1–19 (1996). https://doi.org/10.1007/BF02254789
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02254789