**Bicliques with Minimal Data and Time Complexity for AES (Extended Version)**

*Andrey Bogdanov and Donghoon Chang and Mohona Ghosh and Somitra Kumar Sanadhya*

**Abstract: **Biclique cryptanalysis is a recent technique that has been successfully applied to AES resulting in key recovery faster than brute force. However, a major hurdle in carrying out biclique cryptanalysis on AES is that it requires very high data complexity. This naturally warrants questions over the practical feasibility of
implementing biclique attack in the real world. In Crypto'13, Canteaut et al. proposed biclique attack where the data complexity of the attack was reduced to a single plaintext-ciphertext pair. However, no application of the same on AES was suggested.
In this paper, we re-evaluate the security-bound of full round AES against biclique attack. Under some reasonable
restrictions, we exhaustively analyze the most promising class of biclique cryptanalysis as applied to
AES through a computer-assisted search and find optimal attacks towards lowest computational and data
complexities:
- Among attacks with the minimal data complexity of the unicity distance, the ones with computational complexity 2^126.67 (for AES-128), 2^190.9 (for AES-192) and 2^255 (for AES-256) are the fastest. Each attack just requires 2 (for AES-128 and AES-192) or 3 (for AES-256) known plaintexts for success probability 1.
We obtain these results using the improved biclique attack proposed in Crypto'13.
- Among attacks with data complexity less than the full codebook, for AES-128, the ones of computational complexity 2^126.16 are fastest. Within these, the one with data complexity 2^64 requires the smallest amount of data. Thus, the original attack (with data complexity 2^88) did not have the optimal data complexity
for AES-128. Similar findings are observed for AES-192 as well (data complexity 2^48 as against 2^80 in the
original attack). For AES-256, we find an attack that has a lower computational complexity of 2^254.31 as
compared to the original attack complexity of 2^254.42.
- Among all attacks covered, the ones of computational complexity 2^125.56 (for AES-128), 2^189.51 (for AES-192) and 2^253.87 (for AES-256) are fastest, though requiring the full codebook. This can be considered as an indication of the limitations of the independent-biclique attack approach as applied to AES.

**Category / Keywords: **block ciphers, biclique cryptanalysis, meet-in-the-middle, key recovery, stars, AES-128, minimum data complexity

**Original Publication**** (with major differences): **ICISC 2014 (Shorter Version)

**Date: **received 13 Nov 2014, last revised 14 Nov 2014

**Contact author: **mohonag at iiitd ac in

**Available format(s): **PDF | BibTeX Citation

**Note: **Extended version of the work published in the proceedings of ICISC 2014

**Version: **20141114:165936 (All versions of this report)

**Short URL: **ia.cr/2014/932

[ Cryptology ePrint archive ]