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 the attacks with the minimal data complexity of the unicity distance, the ones with computational complexity 2126.67 (for AES- 128), 2190.9 (for AES-192) and 2255 (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 the attacks with data complexity less than the full codebook, for AES-128, the ones of computational complexity 2126.16 are fastest. Within these, the one with data complexity 264 requires the smallest amount of data. Thus, the original attack (with data complexity 288) did not have the optimal data complexity for AES-128. Similar findings are observed for AES-192 as well (data complexity 248 as against 280 in the original attack). For AES-256, we find an attack that has a lower computational complexity of 2254.31 as compared to the original attack complexity of 2254.42. – Among all the attacks covered, the ones of computational complexity 2125.56 (for AES-128), 2189.51 (for AES-192) and 2253.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. © Springer International Publishing Switzerland 2015.