Biclique Cryptanalysis of Block Ciphers LBlock and TWINE-80 with Practical Data Complexity

Document Type: ORIGINAL RESEARCH PAPER

Authors

1 Department of Electrical Engineering Sharif University of Technology

2 Shahid Beheshti University

3 Sharif University of Technology,

4 Department of Electrical Engineering Sharif University of Technology

Abstract

In the biclique attack, a shorter biclique usually results in less data complexity, but at the expense of more computational complexity. The early abort technique can be used in partial matching part of the biclique attack in order to slightly reduce the computations. In this paper, we make use of this technique, but instead of slight improvement in the computational complexity, we keep the amount of this complexity the same and reduce the data complexity enormously by a shorter biclique.
With this approach, we analysed full-round of LBlock, and also LBlock with modified key schedule (which was designed to resist biclique attack) both with data complexity 2^12, while the data complexity of the best biclique attack on the former was 2^52 and for the latter there is no attack on the full-round cipher, so far. Then we proposed a new key schedule that is more resistant against biclique cryptanalysis, though the low diffusion of the cipher makes it vulnerable to this attack regardless of the strength of the key schedule. Also using this method, we analyzed TWINE-80 with 2^12 data complexity. The lowest data complexity for the prior attack on the TWINE-80 was 2^60. In all the attacks presented in this paper, the computational complexities are slightly improved in comparison to the existing attacks.

Keywords


[1] Ahmadi, Siavash, et al. ”Biclique cryptanalysis of LBlock with modified key schedule.” Information Security and Cryptology (ISCISC), 2015 12th International Iranian Society of Cryptology Conference on. IEEE, (2015)

[2] Shibutani, K., Isobe, T., Hiwatari, H., Mitsuda, A., Akishita T., and Shirai, T.: Piccolo: An UltraLightweight Blockcipher, CHES 2011, LNCS 6917, pp. 342-357, Springer, Heidelberg, (2011)

[3] Bogdanov, A., Knudsen, L., 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. 450466. Springer, Heidelberg (2007)

[4] Guo, J., Peyrin, T., Poschmann, A., Robshaw, M.: The LED Block Cipher. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 326341.Springer, Heidelberg (2011)

[5] Gong, Z., Nikova, S., Law, Y.W.: KLEIN: A New Family of Lightweight Block Ciphers. In: Juels, A., Paar, C. (eds.) RFIDSec 2011. LNCS, vol. 7055, pp. 118. Springer, Heidelberg (2012)

[6] Aumasson, J.P., Henzen, L., Meier, W., NayaPlasencia, M.: Quark: A lightweight hash. In: Mangard and Standaert F.X. (eds.): CHES 2010, LNCS, vol. 6225, pp. 115 Springer, Heidelberg (2010)

[7] Guo, J., Peyrin, T., Poschmann, A.: The PHOTON family of lightweight hash functions. In Phillip Rogaway (ed.): CRYPTO 2011, LNCS, vol.6841, pp. 222-239. Springer, Heidelberg (2011)

[8] Bogdanov, A., Knezevic, M., Leander, G., Toz, D., Varici, K., Verbauwhede, I.: SPONGENT: A lightweight hash function. In Bart Preneel and Tsuyoshi Takagi (eds.): CHES 2011, LNCS, vol.6917, pp. 312-325. Springer, Heidelberg (2011)

[9] Wu, W., Zhang, L.: LBlock: A lighweight block cipher in: Lopez, J., Tsudik, G. (Eds.), ACNS, in: Lecture Notes in Computer Science, vol. 6715, pp. 327-344, (2011)

[10] Li, Y.: Integral Cryptanalysis on Block Ciphers (in Chinese): [D]. Beijing: Institue of Software, Chinese Academy of Sciences, (2012)

[11] Liu, Y., Gu, D., Liu, Z., Li, W.: Impossible differential attacks on reduced-round lblock. In Ryan, M., Smytg, B, and Wang, G., editors, Information Security Practice and Experience, volume 7232 of Lecture Notes in Computer Science, Pages 97-108. Springer Berlin / Heidelberg, (2012)

[12] Soleimany H., Nyberg K.: Zero-Correlation Linear Cryptanalysis of Reduced-Round LBlock, In proceeding of Workshop on Coding and Cryptography, WCC’13, (2013)

[13] Emami, S., McDonald, C., Pieprzyk, J., Steinfeld, R.: Truncated Differential Analysis of ReducedRound LBlock. In Cryptology and Network Security (pp. 291-308). Springer International Publishing (2013)

[14] Bogdanov, A., Boura, C., Rijmen, V., Wang, M., Wen, L., Zhao, J.: Key Difference Invariant Bias in Block Ciphers. In Advances in CryptologyASIACRYPT 2013 (pp. 357-376). Springer Berlin Heidelberg (2013)

[15] Wang, Y., Wu, W., Yu, X., Zhang, L.: Security on LBlock against Biclique Cryptanalysis, WISA 2012, LNCS 7690, pp 1-14, Springer, Heidelberg, (2012)

[16] Karakoc, F., Demirci, H., Harmanci, A.E.: Biclique cryptanalysis of LBlock and TWINE, Information Processing Letters, Volume 113, Issue 12, pp. 423429, (2013)

[17] Suzaki, T., Minematsu, K., Morioka, S. and Kobayashi, E.: TWINE : A Lightweight Block Cipher for Multiple Platforms. SAC 2012, LNCS, vol. 7707, pp. 339-354, Springer-Verlag (2012)

[18] Najarkolaei, S. R. H., Ahangarkolaei, M. Z., Ahmadi, S., and Aref, M. R.: Biclique cryptanalysis of Twine-128. In Information Security and Cryptology (ISCISC), 2016 13th International Iranian Society of Cryptology Conference on (pp. 46-51). IEEE (2016)

[19] Bogdanov, A., Khovratovich, D., Rechberger, C.: Biclique Cryptanalysis of the Full AES, ASIACRYPT 2011, LNCS, vol. 7073, pp. 344-371. Springer, Heidelberg (2011)

[20] Abed, F., Forler, C., List, E., Lucks, S., Wenzel, J., A Framework for Automated Biclique Cryptanalysis of Block Ciphers, FSE 2013, (2013)

[21] Ahmadian, Z., Salmasizadeh, M., Aref, M.R.: Biclique Cryptanalysis of the Full-round KLEIN Block Cipher, Cryptology ePrint Archive, Report 2013/097 (2013)

[22] Ahmadi, S., Ahmadian, Z., Mohajeri, J., and Aref, M.R.:Low Data Complexity Biclique Cryptanalysis of Block Ciphers with Application to Piccolo and HIGHT.” IEEE Trans. Information Forensics and Security 9.10 (2014): 1641-1652.

[23] Song, J., Lee, K., and Lee, H.: Biclique cryptanalysis on lightweight block cipher: HIGHT and Piccolo. International Journal of Computer Mathematics, (2013)

[24] Wang, Y., Wu, W., and Yu, X.: Biclique Cryptanalysis of Reduced-Round Piccolo Block Cipher, ISPEC 2012, LNCS 7232, pp. 337-352, Springer, Heidelberg (2012)

[25] Lu, J., Kim, J., Keller, N., Dunkelman, O.: Improving the Efficiency of Impossible Differential Cryptanalysis of Reduced Camellia and MISTY1, CT-RSA 2008, LNCS Volume 4964, pp 370-386, (2008)