Improving the Biclique Cryptanalysis of AES

Biclique attack is currently the only key-recovery attack on the full AES with a single key. Bogdanov et al. applied it to all the three versions of AES by constructing bicliques with size 2(8) x 2(8) and reducing the number of S-boxes computed in the matching phase. Their results were improved later by better selections of differential characteristics in the biclique construction. In this paper, we improve the biclique attack by increasing the biclique size to 2(16) X 2(8) and 2(16) X 2(16). We have a biclique attack on each of the following AES versions: -AES-128 with time complexity 212613 and data complexity 2(16), AES-128 with time complexity 212601 and data complexity 272, - AES-192 with time complexity 218991 and data complexity 248, and -AES-256 with time complexity 225427 and data complexity 2(40). Our results have the best time complexities among all the existing keyrecovery attacks with data less than the entire code book.