Generator sets for the selection of key differences in the Biclique Attack

• G. C. de Carvalho UFF
• L. A. B. Kowada UFF

DOI: https://doi.org/10.5753/sbseg.2022.224083

Resumo

Biclique cryptanalysis is the only known method faster than brute force for some block ciphers, such as the AES. The main phase of the attack is the Preparation phase in which the attacker selects the two families of key differences and chooses ways to partition the key space and the cipher. In the versions of biclique cryptanalysis used in literature, the selection of both families of key differences is done over the same set of key bits. We introduce our novel technique that involves a new concept of generator set of key differences where each key difference can be chosen from distinct sets of key bits. This also influences the way that the key space is partitioned, allowing for new possible bicliques with better time or data complexities. To demonstrate the power of this new technique, we present in this work an attack on the Serpent-256 that uses a negligible amount of data and remains close in terms of time complexity when compared to the best biclique attack applied to the cipher.

Palavras-chave: Biclique Attack, Cryptanalysis, Serpent Cipher, Block Ciphers

Referências

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

Biham, E., Anderson, R., and Knudsen, L. (1998). Serpent: A new block cipher proposal. In International Workshop on Fast Software Encryption, pages 222–238. Springer.

Biham, E., Dunkelman, O., and Keller, N. (2001a). Linear cryptanalysis of reduced round serpent. In International Workshop on Fast Software Encryption, pages 16–27. Springer.

Biham, E., Dunkelman, O., and Keller, N. (2001b). The rectangle attack—rectangling the serpent. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 340–357. Springer.

Biham, E., Dunkelman, O., and Keller, N. (2003). Differential-linear cryptanalysis of serpent. In International Workshop on Fast Software Encryption, pages 9–21. Springer.

Bogdanov, A., Chang, D., Ghosh, M., and Sanadhya, S. K. (2014). Bicliques with minimal data and time complexity for aes. In International Conference on Information Security and Cryptology, pages 160–174. Springer.

Bogdanov, A., Khovratovich, D., and Rechberger, C. (2011). Biclique cryptanalysis of the full AES. In International Conference on the Theory and Application of Cryptology and Information Security, pages 344–371. Springer.

Canteaut, A., Naya-Plasencia, M., and Vayssiere, B. (2013). Sieve-in-the-middle: Improved MITM attacks (Full Version). Cryptology ePrint Archive, Report 2013/324. https://eprint.iacr.org/2013/324.

Chen, S.-z. and Xu, T.-m. (2014). Biclique key recovery for ARIA-256. IET Information Security, 8(5):259–264.

Çoban, M., Karakoç, F., and Boztas, O. (2012). Biclique cryptanalysis of TWINE. In International Conference on Cryptology and Network Security, pages 43–55. Springer.

Collard, B., Standaert, F.-X., and Quisquater, J.-J. (2007a). Improved and multiple linear cryptanalysis of reduced round serpent. In International Conference on Information Security and Cryptology, pages 51–65. Springer.

Collard, B., Standaert, F.-X., and Quisquater, J.-J. (2007b). Improving the time complexity of matsui’s linear cryptanalysis. In International Conference on Information Security and Cryptology, pages 77–88. Springer.

de Carvalho, G. C. and Kowada, L. A. (2020). The first biclique cryptanalysis of Serpent-256. In SBSEG. SBC. [link].

Hong, D., Koo, B., and Kwon, D. (2011). Biclique attack on the full HIGHT. In International Conference on Information Security and Cryptology, pages 365–374. Springer.

Kelsey, J., Kohno, T., and Schneier, B. (2000). Amplified boomerang attacks against reduced-round mars and serpent. In International Workshop on Fast Software Encryption, pages 75–93. Springer.

Mala, H. (2014). Biclique-based cryptanalysis of the block cipher SQUARE. IET Information Security, 8(3):207–212.

Nechvatal, J., Barker, E., Bassham, L., Burr, W., Dworkin, M., Foti, J., and Roback, E. (2001). Report on the development of the Advanced Encryption Standard (AES).

Journal of Research of the National Institute of Standards and Technology, 106(3):511.

Nguyen, P. H., Wu, H., and Wang, H. (2011). Improving the algorithm 2 in multidimensional linear cryptanalysis. In Australasian Conference on Information Security and Privacy, pages 61–74. Springer.