Abstract
This paper studies the upper bounds of the maximum differential and linear characteristic probabilities of Feistel ciphers with SPN round function. In the same way as for SPN ciphers, we consider the minimum number of differential and linear active s-boxes, which provides a measure of the upper bounds of these probabilities, in order to evaluate the security against differential and linear cryptanalyses. The purpose of this work is to clarify the (lower bound of) minimum numbers of active s-boxes in some consecutive rounds of Feistel ciphers, i.e., in three, four, six, eight, and twelve consecutive rounds, using differential and linear branch numbers Pd, Pl, respectively. Furthermore, we investigate the necessary condition for desirable P-functions, which means that the round functions are invulnerable to both differential and linear cryptanalyses. As an example, we show the round function of Camellia, which satisfies the condition.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
K. Aoki, T. Ichikawa, M. Kanda, M. Matsui, S. Moriai, J. Nakajima, and T. Tokita, “Camellia: A 128-bit Block Cipher Suitable for Multiple Platforms-Design and Analysis-,” Selected Areas in Cryptography — 7th Annual International Workshop, SAC2000, LNCS in this proceeding.
K. Aoki, K. Kobayashi, and S. Moriai, “Best Differential Characteristic Search of FEAL,” Fast Software Encryption — 4th International Workshop, FSE’97, LNCS 1267, pp.41–53, 1997.
K. Aoki, and K. Ohta, “Strict Evaluation of the Maximum Average of Differential Probability and the Maximum Average of Linear Probability,” IEICE Transactions Fundamentals of Electronics, Communications and Computer Sciences, Vol. E80-A, No. 1, pp. 2–8, 1997.
E. Biham, “On Matsui’s Linear Cryptanalysis,” Advances in Cryptology — EUROCRYPT’ 94, LNCS 950, pp.341–355, 1995.
E. Biham, R. Anderson, and L. R. Knudsen, “Serpent: A NewBlo ck Cipher Proposal,” Fast Software Encryption — 5th International Workshop, FSE’98, LNCS 1372, pp.222–238, 1998.
E. Biham, and A. Shamir, “Differential cryptanalysis of DES-like cryptosystems,” Journal of Cryptology, Vol.4, No.1, pp.3–72, 1991.
Data Encryption Standard, FIPS-PUB-46, 1977.
J. Daemen, L. Knudsen, and V. Rijmen, “The block cipher Square,” Fast Software Encryption — 4th International Workshop, FSE’97, LNCS 1267, pp.54–68, 1997.
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 Workshop 2000, 2000. (LNCS to appear).
L. R. Knudsen, “Practically Secure Feistel Ciphers,” Fast Software Encryption — Cambridge Security Workshop, LNCS 809, pp.211–221, 1994.
M. Kanda, Y. Takashima, T. Matsumoto, K. Aoki, and K. Ohta, “A strategy for constructing fast round functions with practical security against differential and linear cryptanalysis,” Selected Areas in Cryptography — 5th Annual International Workshop, SAC’98, LNCS 1556, pp.264–279, 1999.
X. Lai, J. L. Massey, and S. Murphy, “Markov ciphers and differential cryptanalysis,” Advances in Cryptology — EUROCRYPT’91, LNCS 547, pp.17–38, 1991.
M. Matsui, “Linear cryptanalysis method for DES cipher,” Advances in Cryptology— EUROCRYPT’93, LNCS 765, pp.386–397, 1994.
M. Matsui, “On Correlation Between the Order of S-boxes and the Strength of DES,” Advances in Cryptology — EUROCRYPT’94, LNCS 950, pp.366–375, 1995.
M. Matsui, “NewBlo ck Encryption Algorithm MISTY,” Fast Software Encryption— 4th International Workshop, FSE’97, LNCS 1267, pp.54–68, 1997.
S. Moriai, K. Aoki, and K. Ohta, “The Best Linear Expression Search of FEAL,” IEICE Transactions Fundamentals of Electronics, Communications and Computer Sciences, Vol. E79-A, No. 1, pp. 2–11, 1996.
K. Nyberg, “Linear Approximation of Block Ciphers,” Advances in Cryptology —EUROCRYPT’94, LNCS 950, pp.439–444, 1995.
K. Nyberg, and L. R. Knudsen, “Provable Security Against a Differential Attack,” Journal of Cryptology, Vol. 8 No. 1, pp. 27–37, 1995.
V. Rijmen, J. Daemon, B. Preneel, A. Bosselaers, and E. D. Win, “The cipher SHARK,” Fast Software Encryption — Third International Workshop, LNCS 1039, pp.99–111, 1996.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kanda, M. (2001). Practical Security Evaluation against Differential and Linear Cryptanalyses for Feistel Ciphers with SPN Round Function. In: Stinson, D.R., Tavares, S. (eds) Selected Areas in Cryptography. SAC 2000. Lecture Notes in Computer Science, vol 2012. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44983-3_24
Download citation
DOI: https://doi.org/10.1007/3-540-44983-3_24
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42069-9
Online ISBN: 978-3-540-44983-6
eBook Packages: Springer Book Archive