The Best Biclique Cryptanalysis of the Lightweight Cipher FUTURE

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

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

Resumo

In the past decade, lightweight cryptography has been of much interest in the academy, especially in regards to the cryptanalysis of such ciphers. The National Institute of Standards and Technology (NIST) is one of the responsible for this interest, given that they promoted in 2019 a public process to choose the American standard for lightweight cryptography. In 2022, the FUTURE cipher was published and has since been the target of much cryptanalysis, including integral, meet-in-the-middle and differential cryptanalysis in a very short period of time. Earlier this year, a biclique attack for FUTURE was published. We show in this paper, a biclique attack that is better than the one previously published, both in time, memory and data complexities, obtained through semi-automatic search and bicliques based on distinct generator sets. It requires 2^125.18 full computations of the cipher to run, while requiring only 2²⁰ data pairs and negligible memory. Prior to June of this year when an integral attack on FUTURE was published, it was also the fastest attack without using the full code-book of data. Still, when compared to it, our attack uses much less data while being only slightly slower, which presents a good trade-off.

Referências

Bellini, E., Gerault, D., Grados, J., Huang, Y. J., Makarim, R., Rachidi, M., and Tiwari, S. (2024). Claasp: A cryptographic library for the automated analysis of symmetric primitives. In Carlet, C., Mandal, K., and Rijmen, V., editors, Selected Areas in Cryptography – SAC 2023, pages 387–408, Cham. Springer Nature Switzerland.

Bogdanov, A., Chang, D., Ghosh, M., and Sanadhya, S. K. (2015). Bicliques with minimal data and time complexity for aes. In Information Security and Cryptology-ICISC 2014: 17th International Conference, Seoul, South Korea, December 3-5, 2014, Revised Selected Papers 17, pages 160–174. Springer.

Bogdanov, A., Khovratovich, D., and Rechberger, C. (2011). Biclique cryptanalysis of the full aes. In Advances in Cryptology–ASIACRYPT 2011: 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011. Proceedings 17, 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.

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. et al. (2023a). Revisiting the biclique attack on the aes. In Anais do XXIII Simpósio Brasileiro em Segurança da Informação e de Sistemas Computacionais, pages 153–166. 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.

de Carvalho, G. C., Neto, T. S., and do Rêgo Sousa, T. (2023b). Automated security proof of square, led and clefia using the milp technique. In Anais do XXIII Simpósio Brasileiro em Segurança da Informação e de Sistemas Computacionais, pages 445–455. SBC.

Gupta, K. C., Pandey, S. K., and Samanta, S. (2022). Future: a lightweight block cipher using an optimal diffusion matrix. In International Conference on Cryptology in Africa, pages 28–52. 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.

İlter, M. B. and Selçuk, A. A. (2022). Milp-aided cryptanalysis of the future block cipher. In International Conference on Information Technology and Communications Security, pages 153–167. Springer.

McKay, K., Bassham, L., Sönmez Turan, M., and Mouha, N. (2016). Report on lightweight cryptography. Technical report, National Institute of Standards and Technology.

Mondal, S. K., Rahman, M., Sarkar, S., and Adhikari, A. (2024). Yoyo cryptanalysis on future. International Journal of Applied Cryptography, 4(3-4):238–249.

Roy, H. S., Dey, P., Mondal, S. K., and Adhikari, A. (2024). Cryptanalysis of full round future with multiple biclique structures. Peer-to-Peer Networking and Applications, 17(1):397–409.

Schrottenloher, A. and Stevens, M. (2023a). Simplified modeling of mitm attacks for block ciphers: New (quantum) attacks. IACR Transactions on Symmetric Cryptology, 2023:146–183.

Schrottenloher, A. and Stevens, M. (2023b). Simplified modeling of mitm attacks for block ciphers: new (quantum) attacks. Cryptology ePrint Archive.

Shi, D., Sun, S., Song, L., Hu, L., and Yang, Q. (2023). Exploiting non-full key additions: Full-fledged automatic demirci-selcuk meet-in-the-middle cryptanalysis of skinny. Cryptology ePrint Archive, Paper 2023/255. [link]. org/2023/255.

Tao, B. and Wu, H. (2015). Improving the biclique cryptanalysis of aes. In Information Security and Privacy: 20th Australasian Conference, ACISP 2015, Brisbane, QLD, Australia, June 29–July 1, 2015, Proceedings 20, pages 39–56. Springer.

Xu, Z., Cui, J., Hu, K., and Wang, M. (2024). Integral attack on the full future block cipher. Tsinghua Science and Technology.