Uhh, I think you've missed a key point. The new attack is a related-key attack. Related-key attacks are not relevant to most uses of AES. They're basically relevant only to: (a) people who use a block cipher improperly, (b) people who try to build a hash function out of a block cipher. (a) is poor practice anyway. So the main practical import of the new paper, in my opinion, is that AES is not a good basis for a hash function. But the smart money already suspected that already: people have been talking about how the AES key schedule is not the strongest part of the cipher since, oh, it was introduced.

It is NOT the case that AES-256 is only as good as a cipher with a 119-bit key. That's just not true.

And it is NOT the case that all it takes to break AES-256 is 2^119 steps of computation and 2^119 space. That's just not true, either. (You need the ability to mount related-key chosen-plaintext queries, which most well-designed systems do not permit.)

I think the practical import of this attack is much less than has been widely reported.

David:

True, it must have been emphasized that we are looking at a related-key attack scenario. But look at WPA's key packing...