Best attack estimates on AES

Question

The wikipedia article on the Advanced Encryption Standard claims an attack against AES-128 with complexity $2^{126.1}$. The NIST call for proposals for post-quantum cryptography (table on page 18) estimates $2^{143}$ classical gates for key-search attack against AES-128.

1. What does the number in the wikipedia article mean? Number of gates or something else?
2. Where do these numbers come from?
3. What is the estimate for brute-force attack? My naive estimate for AES-128 says $2^{128}$ times the cost for doing 1 AES encryption.

Answer 1

1. The $2^{126.1}$ value is the number of AES encryptions (or equivalent computational workload) required by the attack. There is also a substantial data requirement that $2^{56}$ matched plaintext/ciphertext pairs are required with the attacker having chosen the ciphertext pair and then been provided with the corresponding plaintext pair.

2. The wikipedia numbers come from Tao and Wu's paper Improving the Biclique Cryptanalysis of AES which builds on the work of Bogdanov, Khovratovich and Rechberger in their paper Biclique Cryptanalysis of the Full AES. I do not know of a source for the NIST numbers, though they do not seem wholly unreasonable. Circuit efficient implementations of AES for FPGAs report tens of thousands of gates being required (see e.g. Hernandez et al. Low-Cost Advanced Encryption Standard (AES) VLSI Architecture: A Minimalist Bit-Serial Approach) and this circuit will require many gates to be repeatedly evaluated for a single AES encryption. More specifically, the major gate count is in the implementation of the $S$-box which will need to be evaluated 16 times every rounds for ten rounds.

3. The cost for a brute force decryption is an expected $2^{127}$ encryptions (if we assume that there is a causal solution), with a data requirement of at most one or two matched plaintext/ciphertext pairs.