According to the paper, the computational complexity of the attack (on AES-128) is 2^126.18. The attack requires, however, 2^88 plaintext/ciphertext pairs. What this means is that a machine of size 2^88 (the pairs must be stored somewhere) will succeed at breaking AES in 2^126 steps.
Now consider another scenario: a machine of size 2^88, with 2^88 small AES processors (admittedly, an AES circuit is a constant factor larger than a circuit to store 256 bits; the point still stands). This machine will success in bruteforcing an AES key in 2^(128-88) = 2^40 steps, much faster than the BKR attack. Perhaps now would be a good time to bring up Daniel Bernstein's paper "Understanding bruteforce," which makes the same point, but takes it even further, with a description of a parallel architecture for cost-efficient bruteforcing.
This is not, of course, to discredit the impressive research done by the BKR paper authors. This is important research, and allows us to have better insight (and attacks) into the cipher used to protect all kinds of communication around us. The authors themselves acknowledge that their results do not affect the security of AES in practice:
As our attacks are of high computational complexity, they do not threaten the practical use of AES in any way.So the sky is not really falling. A theoretical break has been done, and it might even lead to a practical attack in the future, but not today.
