Can one claim that AES has perfect secrecy for a key size and message size of 128 bits? While looking at this question I discovered the following here (question 5), and wanted to ask it as a separate question.


  Alice knows that she will want to send a single 128-bit message to Bob
   at some point in the future. To prepare, Alice and Bob first select a
   128-bit key k ∈ {0, 1}128 uniformly at random.
  &nbsp;&nbsp;&nbsp;&nbsp;When the time comes to
   send a message x ∈ {0, 1}128 to Bob, Alice considers two ways of
   doing so. She can use the key as a one time pad, sending Bob k ⊕ x.
   Alternatively, she can use AES to encrypt x. Recall that AES is a
   128-bit block cipher which can use a 128-bit key, so in this case she
   would encrypt x as a single block and send Bob AESk(x).
  &nbsp;&nbsp;&nbsp;&nbsp;Assume Eve
   will see either k ⊕ x or AESk(x), that Eve knows an initial portion of
   x (a standard header), and that she wishes to recover the remaining
   portion of x. If Eve is an all powerful adversary and has time to try
   out every possible key k ∈ {0, 1}128, which scheme would be more
   secure?


And the answer in the document is:


  They would be equally secure. Either way, Eve would not be able to
  learn the unknown portion of x.
  Even after trying every possible key
  (including the actual one), Eve will have no way of recognizing the correct
  plaintext or even narrowing down the possibilities in any way.
  &nbsp;&nbsp;&nbsp;&nbsp;Why is this? Well, since AES is a distinct permutation on {0, 1}128 under each possible key, and the key was selected uniformly at random, given any plaintext, each possible ciphertext is equally likely. So when AES is used for a single block with a random key of the same length, the effect is exactly the same as using a one time pad: the ciphertext reveals no information about the plaintext.


The question mentions a standard header, so I think its fair to assume we know all the plaintext except the very last bit. So my question, is this answer correct?
The answer is incorrect, but it's a bit more subtle than it seems. To make this clear, note that encrypting $x$ by computing $c=\operatorname{AES}_{0}(k) \oplus x$ would be perfectly secure (here the key is fixed to 0, but any fixed key value would give the same effect). This is due to the fact that AES is a permutation and so when $k$ is uniformly distributed, then $\operatorname{AES}_0(k)$ is a uniformly distributed value. More formally, for every $c$ and every $x$ there exists a $k$ such that $c=\operatorname{AES}_0(k)\oplus x$. In order to find this, compute $k = \operatorname{AES}_0^{-1}(c \oplus x)$. 

Now, when encrypting $\operatorname{AES}_k(x)$ the same argument fails. This is because for $c=\operatorname{AES}_k(x)$ there is no guarantee that decrypting $c$ under all possible keys gives all possible plaintexts. Thus, it is possible that there is only one $k$ (or a few $k$'s) that give you the known initial portion.