×

New criteria for linear maps in AES-like ciphers. (English) Zbl 1178.94184

Summary: In this paper, we study a class of linear transformations that are used as mixing maps in block ciphers. We address the question which properties of the linear transformation affect the probability of differentials and characteristics over Super boxes. Besides the expected differential probability (EDP), we also study the fixed-key probability of characteristics, denoted by \(\text{DP}[k]\). We define plateau characteristics, where the dependency on the value of the key is very structured. Our results show that the distribution of the key-dependent probability is not narrow for characteristics in the AES Super box and hence the widely made assumption that it can be approximated by the EDP, is not justified. Finally, we introduce a property of linear maps which hasn’t been studied before. We call this property related differentials. Related differentials don’t influence the EDP of characteristics, but instead they affect the distribution of their \(\text{DP}[k]\) values.

MSC:

94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Specification for the Advanced Encryption Standard (AES). Federal Information Processing Standards Publication 197 (2001)
[2] American Mathematical Society. Algebra, ISBN 0821816462 (1999)
[3] Anderson, R.A., Biham, E., Knudsen, L.R.: Serpent. Proc. of the 1st AES candidate conference, CD-1: Documentation, August 20–22, Ventura (1998)
[4] Aoki, K.: Maximum non-averaged differential probability. Selected Areas in Cryptography SAC ’98, LNCS 1556, pp. 118–130. Springer-Verlag (1998)
[5] Aoki, K., Ichikawa, T., Kanda, M., Matsui, M., Moriai, S., Nakajima, J., Tokita, T.: Camellia: a 128-bit block cipher suitable for multiple platforms–Design and analysis. In: Stinson, D., Tavares, S. (eds.) Selected Areas in Cryptography 2000, LNCS 2012, pp. 39–56. Springer-Verlag (2000) · Zbl 1037.94540
[6] Barreto, P., Rijmen, V.: The Anubis block cipher. First open NESSIE Workshop, Leuven, November 13–14, http://paginas.terra.com.br/informatica/paulobarreto/AnubisPage.html (2000)
[7] Biham, E., Shamir, A.: Differential cryptanalysis of DES-like Cryptosystems. J. Cryptol. 4(1), 3–72 (1991) · Zbl 0729.68017 · doi:10.1007/BF00630563
[8] Ben-Aroya, I., Biham, E.: Differential cryptanalysis of Lucifer. In: Stinson, D. (ed.) Advances in Cryptology, Proc. Crypto’93, LNCS 773, pp. 187–199. Springer-Verlag (1994) · Zbl 0871.94024
[9] Canteaut, A.: Differential cryptanalysis of Feistel ciphers and differentially {\(\delta\)}-uniform mappings. Workshop record of Selected Areas in Cryptography SAC ’97, pp. 172–184 (1997)
[10] Daemen, J., Govaerts, R., Vandewalle, J.: Weak keys of IDEA. In: Stinson, D. (ed.) Advances in Cryptology, Proc. Crypto’93, LNCS 773, pp. 224–231. Springer-Verlag (1994) · Zbl 0877.94031
[11] Daemen, J., Govaerts, R., Vandewalle, J.: A new approach to block cipher design. In: Anderson, R. (ed.) Proc. of Fast Software Encryption 1993, LNCS 809, pp. 18–32. Springer-Verlag (1994) · Zbl 0943.94518
[12] Daemen, J.: Cipher and hash function design. Strategies based on linear and differential cryptanalysis. Ph.D. thesis, Katholieke Universiteit Leuven (1995)
[13] Daemen, J., Knudsen, L.R. Rijmen, V.: The block cipher square. In: Biham, E. (ed.) Fast Software Encryption ’97, LNCS 1267, pp. 149–165. Springer-Verlag (1997) · Zbl 1385.94025
[14] Daemen, J., Peeters, M., Van Assche G., Rijmen, V.: Nessie proposal: the block cipher Noekeon. (Submitted to Nessie)
[15] Daemen, J., Rijmen, V.: The Design of Rijndael–AES, The Advanced Encryption Standard. Springer-Verlag (2002) · Zbl 1065.94005
[16] Daemen, J., Rijmen, V.: Understanding two-round differentials in AES. Security and Cryptography for Networks 2006 (SCN 2006), LNCS 4116, pp. 78–94. Springer-Verlag (2006) · Zbl 1152.94413
[17] Daemen, J., Rijmen, V.: Plateau characteristics. IET Inf. Secur. 1(1), 11–18 (2007) · doi:10.1049/iet-ifs:20060099
[18] Keliher, L.: Refined analysis of bounds related to linear and differential cryptanalysis for the AES. Advanced Encryption Standard–AES, 4th international conference (AES 2004), LNCS 3373, pp. 42–57. Springer-Verlag (2005) · Zbl 1117.94323
[19] Keliher, L., Sui, J.: Exact maximum expected differential and linear probability for 2-round advanced encryption standard (AES). IET Inf. Secur. 1(2), 53–57 (2007) · doi:10.1049/iet-ifs:20060161
[20] Knudsen, L.R.: Iterative characteristics of DES and s2-DES. In: Brickell, E.F. (ed.) Advances in Cryptology, Proc. CRYPTO’92, LNCS 746, pp. 497–511. Springer-Verlag (1993) · Zbl 0809.94018
[21] Knudsen, L.R.: Truncated and higher order differentials. In: Preneel, B. (ed.) Fast Software Encryption ’94, LNCS 1008, pp. 196–211. Springer-Verlag (1995) · Zbl 0939.94556
[22] Knudsen, L.R., Mathiassen, J.E.: On the role of key schedules in attacks on iterated ciphers. ESORICS 2004, LNCS 3193, pp. 322–334. Springer-Verlag (2004)
[23] Lai, X., Massey, J.L., Murphy, S.: Markov ciphers and differential cryptanalysis. In: Davies, D.W. (ed.) Advances in Cryptology, Proc. Eurocrypt’91, LNCS 547, pp. 17–38. Springer-Verlag (1991) · Zbl 0777.94013
[24] Lidl, R., Niederreiter, H.: Introduction to Finite Fields and Their Applications. Cambridge University Press, 1986 (Reprinted 1988) · Zbl 0629.12016
[25] Matsui, M.: New block encryption algorithm misty. In: Biham, E. (ed.) Fast Software Encryp tion ’97, LNCS 1267, pp. 64–74. Springer-Verlag (1997) · Zbl 1385.94061
[26] Nyberg, K.: Differentially uniform mappings for cryptography. In: Helleseth, T. (ed.) Advances in Cryptology, Proc. Eurocrypt’93, LNCS 765, pp. 55-64. Springer-Verlag (1993) · Zbl 0951.94510
[27] Nyberg, K., Knudsen, L.R.: Provable security against a differential attack. J. Cryptol. 8(1), 27–38 (1995) · Zbl 0817.94016 · doi:10.1007/BF00204800
[28] Park, S., Sung, S.H., Chee, S., E-J. Yoon, Lim, J.: On the security of Rijndael-like structures against differential and linear cryptanalysis. In: Zheng, Y. (ed.) Advances in Cryptology, Proceedings of Asiacrypt ’02, LNCS 2501, pp. 176–191. Springer-Verlag (2002) · Zbl 1065.68530
[29] Park, S., Sung, S.H., Lee, S., Lim, J.: Improving the upper bound on the maximum differential and the maximum linear hull probability for SPN structures and AES. In: Johansson, T. (ed.) Fast Software Encryption ’03, LNCS 2887, pp. 247–260. Springer-Verlag (2003) · Zbl 1254.94040
[30] Rijmen, V.: Cryptanalysis and design of iterated block ciphers. Doctoral Dissertation, October 1997, K.U. Leuven
[31] Rijmen, V., Daemen, J., Preneel, B., Bosselaers, A., De Win E.: The cipher SHARK. In: Gollmann, D. (ed.) Fast Software Encryption ’96, LNCS 1039, pp. 99–111. Springer-Verlag (1996) · Zbl 1373.94929
[32] Vaudenay, S.: On the need for multipermutations: cryptanalysis of MD4 and SAFER. In: Preneel, B. (ed.) Fast Software Encryption ’94, LNCS 1008, pp. 286–297. Springer-Verlag (1995) · Zbl 0939.94542
[33] Zheng, Y., Zhang, X.M.: Plateaued functions. Advances in Cryptology, ICICS ’99, LNCS 1726, pp. 284–300. Springer-Verlag (1999) · Zbl 0982.94038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.