Automatic search for key-bridging technique: applications to LBlock and TWINE. (English) Zbl 1387.94089

Peyrin, Thomas (ed.), Fast software encryption. 23rd international conference, FSE 2016, Bochum, Germany, March 20–23, 2016. Revised selected papers. Berlin: Springer (ISBN 978-3-662-52992-8/pbk; 978-3-662-52993-5/ebook). Lecture Notes in Computer Science 9783, 247-267 (2016).
Summary: Key schedules in block ciphers are often highly simplified, which causes weakness that can be exploited in many attacks. At ASIACRYPT 2010, O. Dunkelman et al. [Lect. Notes Comput. Sci. 6477, 158–176 (2010; Zbl 1253.94045)] proposed a technique using the weakness in the key schedule of AES, called key-bridging technique, to improve the overall complexity. The advantage of key-bridging technique is that it allows the adversary to deduce some sub-key bits from some other sub-key bits, even though they are separated by many key mixing steps. Although the relations of successive rounds may be easy to see, the relations of two rounds separated by some mixing steps are very hard to find. In this paper, we describe a versatile and powerful algorithm for searching key-bridging technique on word-oriented and bit-oriented block ciphers. To demonstrate the usefulness of our approach, we apply our tool to the impossible differential and multidimensional zero correlation linear attacks on 23-round LBlock, 23-round TWINE-80 and 25-round TWINE-128. To the best of our knowledge, these results are the currently best results on LBlock and TWINE in the single-key setting.
For the entire collection see [Zbl 1344.68014].


94A60 Cryptography


Zbl 1253.94045
Full Text: DOI


[1] 1.Beaulieu, R., Shors, D., Smith, J., Treatman-Clark, S., Weeks, B., Wingers, L.: The SIMON and SPECK Families of Lightweight Block Ciphers. Cryptology ePrint Archive, Report 2013/404 (2013). · Zbl 1382.94059
[2] 2.Biryukov, A., Derbez, P., Perrin, L.: Differential analysis and meet-in-the-middle attack against round-reduced TWINE. In: Leander, G. (ed.) FSE 2015. LNCS, vol. 9054, pp. 3-27. Springer, Heidelberg (2015) · Zbl 1367.94300
[3] 3.Biryukov, A., Khovratovich, D., Nikolić, I.: Distinguisher and related-key attack on the full AES-256. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 231-249. Springer, Heidelberg (2009) · Zbl 1252.94051
[4] 4.Bogdanov, A.A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw, M., Seurin, Y., Vikkelsoe, C.: PRESENT: an ultra-lightweight block cipher. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 450-466. Springer, Heidelberg (2007) · Zbl 1142.94334
[5] 5.Bogdanov, A., Rechberger, C.: A 3-subset meet-in-the-middle attack: cryptanalysis of the lightweight block cipher KTANTAN. In: Biryukov, A., Gong, G., Stinson, D.R. (eds.) SAC 2010. LNCS, vol. 6544, pp. 229-240. Springer, Heidelberg (2011) · Zbl 1292.94032
[6] 6.Boura, C., Minier, M., Naya-Plasencia, M., Suder, V.: Improved Impossible Differential Attacks against Round-Reduced LBlock. Cryptology ePrint Archive, Report 2014/279 (2014). · Zbl 1306.94035
[7] 7.Boura, C., Naya-Plasencia, M., Suder, V.: Scrutinizing and improving impossible differential attacks: applications to CLEFIA, Camellia, LBlock and · Zbl 1306.94035
[8] 8.Daemen, J., Rijmen, V.: The Design of Rijndael: AES-the Advanced Encryption Standard. Springer, Berlin (2002) · Zbl 1065.94005
[9] 9.Derbez, P., Fouque, P.-A., Jean, J.: Improved key recovery attacks on reduced-round · Zbl 1306.94044
[10] 10.Dunkelman, O., Keller, N., Shamir, A.: Improved Single-Key Attacks on 8-Round AES. Cryptology ePrint Archive, Report 2010/322 (2010). · Zbl 1253.94045
[11] 11.Dunkelman, O., Keller, N., Shamir, A.: Improved single-key attacks on 8-round AES-192 and AES-256. In: Advances in Cryptology-ASIACRYPT 2010, pp. 158-176. Springer, Berlin (2010) · Zbl 1253.94045
[12] 12.Guo, J., Peyrin, T., Poschmann, A., Robshaw, M.: The LED block cipher. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 326-341. Springer, Heidelberg (2011) · Zbl 1291.94092
[13] 13.Hong, D., et al.: HIGHT: a new block cipher suitable for low-resource device. In: Goubin, L., Matsui, M. (eds.) CHES 2006. LNCS, vol. 4249, pp. 46-59. Springer, Heidelberg (2006) · Zbl 1307.94058
[14] 14.Khovratovich, D., Biryukov, A., Nikolic, I.: Speeding up collision search for byte-oriented hash functions. In: Fischlin, M. (ed.) CT-RSA 2009. LNCS, vol. 5473, pp. 164-181. Springer, Heidelberg (2009) · Zbl 1237.94068
[15] 15.Knudsen, L., Leander, G., Poschmann, A., Robshaw, M.J.B.: · Zbl 1297.94080
[16] 16.Ko, Y., Hong, S.H., Lee, W.I., Lee, S.-J., Kang, J.: Related key differential attacks on 27 rounds of XTEA and full-round GOST. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 299-316. Springer, Heidelberg (2004) · Zbl 1079.68548
[17] 17.Li, L., Jia, K., Wang, X.: Improved single-key attacks on 9-round AES-192/256. In: Cid, C., Rechberger, C. (eds.) FSE 2014. LNCS, vol. 8540, pp. 127-146. Springer, Heidelberg (2015) · Zbl 1360.94317
[18] 18.Li, R., Jin, C.: Meet-in-the-middle attacks on 10-round AES-256. In: Designs, Codes and Cryptography, pp. 1-13 (2015) · Zbl 1402.94062
[19] 19.Lin, L., Wu, W., Wang, Y., Zhang, L.: General model of the single-key meet-in-the-middle distinguisher on the word-oriented block cipher. In: Lee, H.-S., Han, D.-G. (eds.) ICISC 2013. LNCS, vol. 8565, pp. 203-223. Springer, Heidelberg (2014) · Zbl 1368.94113
[20] 20.Sun, B., Liu, Z., Rijmen, V., Li, R., Cheng, L., Wang, Q., Alkhzaimi, H., Li, C.: Links among impossible differential, integral and zero correlation linear cryptanalysis. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 95-115. Springer, Heidelberg (2015) · Zbl 1347.94059
[21] 21.Suzaki, T., Minematsu, K., Morioka, S., Kobayashi, E.: · Zbl 1327.94075
[22] 22.Wang, Y., Wu, W.: Improved multidimensional zero-correlation linear cryptanalysis and applications to LBlock and TWINE. In: Susilo, W., Mu, Y. (eds.) ACISP 2014. LNCS, vol. 8544, pp. 1-16. Springer, Heidelberg (2014) · Zbl 1318.94085
[23] 23.Wikipedia. Invariant Subspace -Wikipedia, The Free Encyclopedia (2015).
[24] 24.Wu, S., Wang, M.: Automatic search of truncated impossible differentials for word-oriented block ciphers. In: Galbraith, S., Nandi, M. (eds.) INDOCRYPT 2012. LNCS, vol. 7668, pp. 283-302. Springer, Heidelberg (2012) · Zbl 1295.94157
[25] 25.Wu, W., Zhang, L.: LBlock: a lightweight block cipher. In: Lopez, J., Tsudik, G. (eds.) ACNS 2011. LNCS, vol. 6715, pp. 327-344. Springer, Heidelberg (2011) · Zbl 1250.94047
[26] 26.Zheng, X., Jia, K.: Impossible differential attack on reduced-round TWINE. In: Lee, H.-S., Han, D.-G. (eds.) ICISC 2013. LNCS, vol. 8565, pp. 123-143. Springer, Heidelberg (2014) · Zbl 1445.94030
[27] 27.Zhijie, C.: Higher Algebra and Analytic Geometry. Springer, Berlin (2001)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.