Revisiting the Biclique Attack on the AES

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

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

Resumo

The AES Cipher is one of the most widely used block ciphers throughout the world for the better part of two decades now. Despite its relevancy, there has been no great progress in the attempts at finding exploitable flaws or cryptanalysis techniques that are able to find the secret key in less time than simple exhaustive search for its full version. The only exception is biclique cryptanalysis which was used more than once to recover the secret key in marginally less time than simple brute force. The last improvement happened 8 years ago. This paper finds the best results for all but one of the variations attempted on the AES, through the help of the concept of generator sets for related-key differentials, in terms of time complexity as well as a software that semi-automates tests on general word-based ciphers.

Referências

Abed, F., Forler, C., List, E., Lucks, S., and Wenzel, J. (2012). Biclique cryptanalysis of the PRESENT and LED lightweight ciphers. IACR Cryptology ePrint Archive, 2012:591.

Abed, F., Forler, C., List, E., Lucks, S., and Wenzel, J. (2014). A framework for automated independent-biclique cryptanalysis. In Fast Software Encryption: 20th International Workshop, FSE 2013, Singapore, March 11-13, 2013. Revised Selected Papers 20, pages 561–581. 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.

C¸ oban, M., Karakoç, F., and Boztaş, Ö. (2012). Biclique cryptanalysis of TWINE. In International Conference on Cryptology and Network Security, pages 43–55. Springer.

Daemen, J. and Rijmen, V. (2013). The design of Rijndael: AES-the advanced encryption standard. Springer Science & Business Media.

de Carvalho, G. et al. (2022). Generator sets for the selection of key differences in the biclique attack. In Anais do XXII Simpósio Brasileiro em Segurança da Informação e de Sistemas Computacionais, pages 1–14. SBC.

de Carvalho, G. C. and Kowada, L. A. (2020). The first biclique cryptanalysis of serpent-256. In Anais do XX Simpósio Brasileiro em Segurança da Informação e de Sistemas Computacionais, pages 29–42. SBC.

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.

Liu, Y.,Wang, Q., and Rijmen, V. (2016). Automatic search of linear trails in arx with applications to speck and chaskey. In Applied Cryptography and Network Security: 14th International Conference, ACNS 2016, Guildford, UK, June 19-22, 2016. Proceedings 14, pages 485–499. Springer.

Mouha, N.,Wang, Q., Gu, D., and Preneel, B. (2011). Differential and linear cryptanalysis using mixed-integer linear programming. In International Conference on Information Security and Cryptology, pages 57–76. Springer.

Rouquette, L., Gerault, D., Minier, M., and Solnon, C. (2022). And rijndael? automatic related-key differential analysis of rijndael. In Progress in Cryptology-AFRICACRYPT 2022: 13th International Conference on Cryptology in Africa, AFRICACRYPT 2022, Fes, Morocco, July 18–20, 2022, Proceedings, pages 150–175. Springer.

Sun, L., Wang, W., and Wang, M. (2017). Automatic search of bit-based division property for arx ciphers and word-based division property. In Advances in Cryptology–ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part I 23, pages 128–157. 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.