The higher-order meet-in-the-middle attack and its application to the Camellia block cipher. (English) Zbl 1291.94120
Summary: The Camellia block cipher has a 128-bit block length, a user key of 128, 192 or 256 bits long, and a total of 18 rounds for a 128-bit key and 24 rounds for a 192 or 256-bit key. It is a Japanese CRYPTREC-recommended e-government cipher, a European NESSIE selected cipher and an ISO international standard. The meet-in-the-middle attack is a technique for analysing the security of a block cipher. In this paper, we propose an extension of the meet-in-the-middle attack, which we call the higher-order meet-in-the-middle (HO-MitM) attack; the core idea of the HO-MitM attack is to use multiple plaintexts to cancel some key-dependent component(s) or parameter(s) when constructing a basic unit of ”value-in-the-middle”. Then we introduce a novel approach, which combines integral cryptanalysis with the meet-in-the-middle attack, to construct HO-MitM attacks on 10-round Camellia with the \(\mathrm{FL}/\mathrm{FL}^{-1}\) functions under 128 key bits, 11-round Camellia with the \(\mathrm{FL}/\mathrm{FL}^{-1}\) functions under 192 key bits and 12-round Camellia with the \(\mathrm{FL}/\mathrm{FL}^{-1}\) functions under 256 key bits. Finally, we apply an existing approach to construct HO-MitM attacks on 14-round Camellia without the \(\mathrm{FL}/\mathrm{FL}^{-1}\) functions under 192 key bits and 16-round Camellia without the \(\mathrm{FL}/\mathrm{FL}^{-1}\) functions under 256 key bits. The HO-MitM attack can potentially be used to cryptanalyse other block ciphers.
MSC:
| 94A60 | Cryptography |
References:
| [1] | 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, (Stinson, D. R.; Tavares, S. E., SAC 2000. SAC 2000, LNCS, vol. 2012 (2001), Springer: Springer Heidelberg), 39-56 · Zbl 1037.94540 |
| [2] | Bai, D.; Li, L., New impossible differential attacks on Camellia, (Ryan, M. D.; Smyth, B.; Wang, G., ISPEC 2012. ISPEC 2012, LNCS, vol. 7232 (2012), Springer: Springer Heidelberg), 80-96 · Zbl 1291.94054 |
| [3] | Biham, E.; Biryukov, A.; Shamir, A., Cryptanalysis of Skipjack reduced to 31 rounds using impossible differentials, (Stern, J., EUROCRYPT 1999. EUROCRYPT 1999, LNCS, vol. 1592 (1999), Springer: Springer Heidelberg), 12-23 · Zbl 0927.94013 |
| [4] | Biham, E.; Dunkelman, O.; Keller, N., The rectangle attack—rectangling the Serpent, (Pfitzmann, B., EUROCRYPT 2001. EUROCRYPT 2001, LNCS, vol. 2045 (2001), Springer: Springer Heidelberg), 340-357 · Zbl 0981.94017 |
| [5] | Biham, E.; Shamir, A., Differential cryptanalysis of DES-like cryptosystems, J. Cryptology, 4, 3-72 (1991) · Zbl 0729.68017 |
| [6] | Biryukov, A.; Nikolic, I., Automatic search for related-key differential characteristics in byte-oriented block ciphers: application to AES, Camellia, Khazad and others, (Gilbert, H., EUROCRYPT 2010. EUROCRYPT 2010, LNCS, vol. 6110 (2010), Springer: Springer Heidelberg), 322-344 · Zbl 1280.94041 |
| [7] | Biryukov, A.; Shamir, A., Structural cryptanalysis of SASAS, J. Cryptology, 23, 505-518 (2010) · Zbl 1201.94076 |
| [8] | Chen, J.; Jia, K.; Yu, H.; Wang, X., New impossible differential attacks of reduced-round Camellia-192 and Camellia-256, (Hawkes, P.; Parampalli, U., ACISP 2011. ACISP 2011, LNCS, vol. 6812 (2011), Springer: Springer Heidelberg), 16-33 · Zbl 1279.94063 |
| [10] | Daemen, J.; Knudsen, L. R.; Rijmen, V., The block cipher Square, (Biham, E., FSE 1997. FSE 1997, LNCS, vol. 1267 (1997), Springer: Springer Heidelberg), 149-165 · Zbl 1385.94025 |
| [11] | Demirci, H.; Selçuk, A. A., A meet-in-the-middle attack on 8-round AES, (Nyberg, K., FSE 2008. FSE 2008, LNCS, vol. 5086 (2008), Springer: Springer Heidelberg), 116-126 · Zbl 1154.68391 |
| [12] | Demirci, H.; Taşkm, I.; Çoban, M.; Baysal, A., Improved meet-in-the-middle attacks on AES, (Roy, B.; Sendrier, N., INDOCRYPT 2009. INDOCRYPT 2009, LNCS, vol. 5922 (2009), Springer: Springer Heidelberg), 144-156 · Zbl 1273.94345 |
| [13] | Diffie, W.; Hellman, M., Exhaustive cryptanalysis of the NBS data encryption standard, Computer, 10, 74-84 (1977) |
| [14] | Dunkelman, O.; Keller, N.; Shamir, A., Improved single-key attacks on 8-round AES-192 and AES-256, (Abe, M., ASIACRYPT 2010. ASIACRYPT 2010, LNCS, vol. 6477 (2010), Springer: Springer Heidelberg), 158-176 · Zbl 1253.94045 |
| [15] | Duo, L.; Li, C.; Feng, K., New observation on Camellia, (Preneel, B.; Tavares, S. E., SAC 2005. SAC 2005, LNCS, vol. 3897 (2006), Springer: Springer Heidelberg), 51-64 · Zbl 1151.94536 |
| [16] | Gilbert, H.; Minier, M., A collision attack on 7 rounds of Rijndael, (Proceedings of the Third Advanced Encryption Standard Candidate Conference (2000), NIST), 230-241 |
| [17] | Hatano, Y.; Sekine, H.; Kaneko, T., Higher order differential attack of Camellia(II), (Nyberg, K.; Heys, H. M., SAC 2002. SAC 2002, LNCS, vol. 2595 (2003), Springer: Springer Heidelberg), 39-56 · Zbl 1066.94543 |
| [18] | Hellman, M. E., A cryptanalytic time-memory trade-off, IEEE Trans. Inform. Theory, 26, 401-406 (1980) · Zbl 0436.94016 |
| [19] | Hu, Y.; Zhang, Y.; Xiao, G., Integral cryptanalysis of SAFER+, Electron. Lett., 35, 1458-1459 (1999) |
| [21] | Knudsen, L. R., Truncated and higher order differentials, (Preneel, B., FSE 1994. FSE 1994, LNCS, vol. 1008 (1995), Springer: Springer Heidelberg), 196-211 · Zbl 0939.94556 |
| [22] | Knudsen, L. R., DEAL—a 128-bit block cipher (1998), Department of Informatics, University of Bergen: Department of Informatics, University of Bergen Norway, Technical report |
| [23] | Knudsen, L. R.; Wagner, D., Integral cryptanalysis, (Daemen, J.; Rijmen, V., FSE 2002. FSE 2002, LNCS, vol. 2365 (2002), Springer: Springer Heidelberg), 112-127 · Zbl 1045.94527 |
| [24] | Lai, X., Higher order derivatives and differential cryptanalysis, (Communications and Cryptography (1994)), 227-233 · Zbl 0840.94017 |
| [25] | Liu, Y.; Li, L.; Gu, D.; Wang, X.; Liu, Z.; Chen, J.; Li, W., New observations on impossible differential cryptanalysis of reduced-round Camellia, (Canteaut, A., FSE 2012. FSE 2012, LNCS, vol. 7549 (2012), Springer: Springer Heidelberg), 90-109 · Zbl 1312.94072 |
| [26] | Lu, J., Cryptanalysis of block ciphers (2008), University of London: University of London UK, PhD thesis |
| [27] | Lu, J.; Wei, Y.; Fouque, P.-A.; Kim, J., Cryptanalysis of reduced versions of the Camellia block cipher, IET Inf. Secur., 6, 3, 228-238 (2012), A version appeared in Pre-proceedings of SAC 2011 |
| [28] | Lu, J.; Wei, Y.; Kim, J.; Pasalic, E., The higher-order meet-in-the-middle attack and its application to the Camellia block cipher (extended abstract), (Galbraith, S.; Nandi, M., INDOCRYPT 2012. INDOCRYPT 2012, LNCS, vol. 7668 (2012), Springer: Springer Heidelberg), 244-264 · Zbl 1295.94110 |
| [29] | Lu, J.; Wei, Y.; Pasalic, E.; Fouque, P.-A., Meet-in-the-middle attack on reduced versions of the Camellia block cipher, (Hanaoka, G.; Yamauchi, T., IWSEC 2012. IWSEC 2012, LNCS, vol. 7631 (2012), Springer: Springer Heidelberg), 197-215 · Zbl 1279.94097 |
| [30] | Mala, H.; Shakiba, M.; Dakhilalian, M.; Bagherikaram, G., New results on impossible differential cryptanalysis of reduced-round Camellia-128, (Jacobson, M. J.; Rijmen, V.; Safavi-Naini, R., SAC 2009. SAC 2009, LNCS, vol. 5867 (2009), Springer: Springer Heidelberg), 281-294 · Zbl 1267.94082 |
| [31] | Mala, H.; Dakhilalian, M.; Shakiba, M., Impossible differential cryptanalysis of reduced-round Camellia-256, IET Inf. Secur., 5, 129-134 (2011) |
| [32] | Matsui, M., Linear cryptanalysis method for DES cipher, (Helleseth, T., EUROCRYPT 1993. EUROCRYPT 1993, LNCS, vol. 765 (1994), Springer: Springer Heidelberg), 386-397 · Zbl 0951.94519 |
| [34] | Wei, Y.; Lu, J.; Hu, Y., Meet-in-the-middle attack on 8 rounds of the AES block cipher under 192 key bits, (Bao, F.; Weng, J., ISPEC 2011. ISPEC 2011, LNCS, vol. 6672 (2011), Springer: Springer Heidelberg), 222-232 · Zbl 1292.94151 |
| [35] | Wu, W.; Feng, D.; Chen, H., Collision attack and pseudorandomness of reduced-round Camellia, (Handschuh, H.; Hasan, M. A., SAC 2004. SAC 2004, LNCS, vol. 3357 (2005), Springer: Springer Heidelberg), 256-270 · Zbl 1117.94339 |
| [36] | Wagner, D., The boomerang attack, (Knudsen, L. R., FSE 1999. FSE 1999, LNCS, vol. 1636 (1999), Springer: Springer Heidelberg), 156-170 · Zbl 0942.94022 |
| [37] | Yeom, Y.; Park, S.; Kim, I., A study of integral type cryptanalysis on Camellia, (Proceedings of the 2003 Symposium on Cryptography and Information Security (2003), IEICE), 453-456 |
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.
