The First Biclique Cryptanalysis of Serpent-256

• Gabriel C. de Carvalho UFF
• Luis A. B. Kowada UFF

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

Resumo

The Serpent cipher was one of the finalists of the AES process and as of today there is no method for finding the key with fewer attempts than that of an exhaustive search of all possible keys, even when using known or chosen plaintexts for an attack. This work presents the first two biclique attacks for the full-round Serpent-256. The first uses a dimension 4 biclique while the second uses a dimension 8 biclique. The one with lower dimension covers nearly 4 complete rounds of the cipher, which is the reason for the lower time complexity when compared with the other attack (which covers nearly 3 rounds of the cipher). On the other hand, the second attack needs a lot less pairs of plaintexts for it to be done. The attacks require 2^255.21 and 2^255.45 full computations of Serpent-256 using 2⁸⁸ and 2⁶⁰ chosen ciphertexts respectively with negligible memory.

Referências

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.

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, Ö. (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.

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.

Khovratovich, D., Leurent, G., and Rechberger, C. (2012). Narrow-Bicliques: cryptanalysis of full IDEA. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 392–410. 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.

Tao, B. and Wu, H. (2015). Improving the biclique cryptanalysis of AES. In Australasian Conference on Information Security and Privacy, pages 39–56. Springer.