Abstract
In this paper, we present some new applications of the bounds for the differential probability of a SDS (Substitution-Diffusion-Substitution) structure by Park et al. at FSE 2003. Park et al. have applied their result on the AES cipher which uses the SDS structure based on MDS matrices. We shall apply their result to practical ciphers that use SDS structures based on {0,1}-matrices of size n×n. These structures are useful because they can be efficiently implemented in hardware. We prove a bound on {0,1}-matrices to show that they cannot be MDS and are almost-MDS only when n = 2,3, or 4. Thus we have to apply Park’s result whenever {0,1}-matrices where n ≥ 5 are used because previous results only hold for MDS and almost-MDS diffusion matrices. Based on our bound, we also show that the {0,1}-matrices used in E2, Camellia, and MCrypton are optimal or almost-optimal among {0,1}-matrices. Using Park’s result, we prove differential bounds for the E2 and MCrypton ciphers, from which we can deduce their security against boomerang attack and some of its variants. At ICCSA 2006, Khoo and Heng constructed block cipher-based universal hash functions, from which they derived Message Authentication Codes (MACs) which are faster than CBC-MAC. Park’s result provides us with the means to obtain a more accurate bound for their universal hash function. With this bound, we can restrict the number of MAC’s performed before a change of MAC key is needed.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
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.R., Tavares, S. (eds.) SAC 2000. LNCS, vol. 2012. Springer, Heidelberg (2001)
Barreto, P.S.L.M., Rijmen, V.: The WHIRLPOOL Hashing Function. Primitive submitted to NESSIE, revised on May 2003 (September 2000), http://paginas.terra.com.br/informatica/paulobarreto/WhirlpoolPage.html
Biham, E., Dunkelman, O., Keller, N.: The Rectangle Attack - Rectangling the Serpent. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 340–357. Springer, Heidelberg (2001)
Biham, E., Dunkelman, O., Keller, N.: Related-Key Boomerang and Rectangle Attack. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 507–525. Springer, Heidelberg (2005)
Biham, E., Shamir, A.: Differential Cryptanalysis of DES-like Cryptosystems. Journal of Cryptology 4 (1991)
Brassard, G.: On computationally secure authentication tags requiring short secret shared keys. In: Crypto 1983, pp. 79–86. Springer, Heidelberg (1983)
Daemen, J., Rijmen, V.: The Wide Trail Strategy. In: Honary, B. (ed.) Cryptography and Coding 2001. LNCS, vol. 2260, pp. 222–238. Springer, Heidelberg (2001)
Daemen, J., Rijmen, V.: The Design of Rijndael: AES, The Advanced Encryption Standard. Springer, Heidelberg (2002)
Daemen, J., Govaerts, R., Vandewalle, J.: Correlation Matrices. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 275–285. Springer, Heidelberg (1995)
Daemen, J., Knudsen, L., Rijmen, V.: The Block Cipher Square. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 149–165. Springer, Heidelberg (1997)
Hong, S., Lee, S., Lim, J., Sung, J., Cheong, D., Cho, I.: Provable Security against Differential and Linear Cryptanalysis for the SPN Structure. In: Schneier, B. (ed.) FSE 2000. LNCS, vol. 1978, pp. 273–283. Springer, Heidelberg (2001)
Kanda, M., Moriai, S., Aoki, K., Ueda, H., Takashima, Y., Ohta, K., Matsumoto, T.: E2 - A New 128-bit Block Cipher. IEICE Transactions Fundamentals - Special Section on Cryptography and Information Security, vol. E83-A no. 1, pp. 48-59 (2000)
Kelsey, J., Kohno, T., Schneier, B.: Amplified Boomerang Attacks Against Reduced-Round MARS and Serpent. In: Schneier, B. (ed.) FSE 2000. LNCS, vol. 1978, pp. 75–93. Springer, Heidelberg (2001)
Khoo, K., Heng, S.H.: New Constructions of Universal Hash Functions based on Function Sum. In: Gavrilova, M.L., Gervasi, O., Kumar, V., Tan, C.J.K., Taniar, D., Laganá, A., Mun, Y., Choo, H. (eds.) ICCSA 2006. LNCS, vol. 3982, pp. 416–425. Springer, Heidelberg (2006)
Lim, C.H., Korkishko, T.: mCrypton - A Lightweight Block Cipher for Security of Low-Cost RFID Tags and Sensors. In: Song, J.-S., Kwon, T., Yung, M. (eds.) WISA 2005. LNCS, vol. 3786, pp. 243–258. Springer, Heidelberg (2006)
Matsui, M.: Linear Cryptanalysis Method for DES Cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994)
Nyberg, K.: Differentially Uniform Mappings for Cryptography. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 55–64. Springer, Heidelberg (1994)
Park, S., Sang, 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.) FSE 2003. LNCS, vol. 2887, pp. 247–260. Springer, Heidelberg (2003)
Rijmen, V., Daemen, J., Preneel, B., Bosselars, A., Win, E.D.: The Cipher Shark. In: Gollmann, D. (ed.) FSE 1996. LNCS, vol. 1039, pp. 99–111. Springer, Heidelberg (1996)
Stinson, D.R.: On the connections between universal hashing, combinatorial designs and error-correcting codes. In: Congressus Numerantium, vol. 114, pp. 7–27 (1996)
Wagner, D.: The Boomerang Attack. In: Knudsen, L.R. (ed.) FSE 1999. LNCS, vol. 1636, pp. 156–170. Springer, Heidelberg (1999)
Wallen, J.: Design Principles of the KASUMI Block Cipher, http://citeseer.ist.psu.edu/wallen00design.html
Wegman, M.N., Carter, J.L.: New hash functions and their use in authentication and set equality. Journal of Computer and System Sciences 22(3), 265–279 (1981)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Choy, J., Khoo, K. (2008). New Applications of Differential Bounds of the SDS Structure. In: Wu, TC., Lei, CL., Rijmen, V., Lee, DT. (eds) Information Security. ISC 2008. Lecture Notes in Computer Science, vol 5222. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85886-7_26
Download citation
DOI: https://doi.org/10.1007/978-3-540-85886-7_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85884-3
Online ISBN: 978-3-540-85886-7
eBook Packages: Computer ScienceComputer Science (R0)