11
$\begingroup$

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.
    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).
    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.     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?

$\endgroup$
7
$\begingroup$

No, one can not claim that AES has perfect secrecy for a key size and message size of 128 bits. The answer quoted in the second part of the question is seriously wrong.

Perfect secrecy is an information-theoretic concept, assuming an adversary with infinite computing power, and AES is not safe against that.

In the context of the question: revealing $\operatorname{AES}_k(x)$ to an indefinitely powerful adversary, even with uniformly random $k$ used for no other purpose, has overwhelming chances to allow elimination of many possible values of $x$; that can be done by deciphering what's given with all keys $k$ and finding values never reached. Assimilating AES to a perfect cipher, there will be about $2^{128-1/\log(2)}\approx2^{126.56}$ such values. That gives the adversary sizable probability (about $1/e\approx0.368$ ) to eliminate with certainty a random value as a possible $x$ . Computing the exact advantage given by revealing $\operatorname{AES}_k(x)$ is left as an exercise to the reader, but I guess it is in the order of one bit of information about $x$.

As rightly pointed out, things would be different for the different question of what would happen if $\operatorname{AES}_0(k)\oplus x$ was revealed.

$\endgroup$
  • 2
    $\begingroup$ In principle, this isn't enough since you are only using the key once, and for an amount that is within the "perfect secrecy" bound. See my answer. $\endgroup$ – Yehuda Lindell Dec 20 '17 at 12:42
  • 1
    $\begingroup$ "to an indefinitely adversary"? $\endgroup$ – ilkkachu Dec 20 '17 at 14:47
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ AES as a way of permuting a key stream is not what block ciphers are about. Just inverting each bit in the key stream would have the same effect. So please be aware that this is only an example to explain the second part that provides the answer. Yehuda, I hope you agree with above? $\endgroup$ – Maarten Bodewes Dec 20 '17 at 13:29
  • $\begingroup$ The first paragraph is still interesting, it would be perfectly secure and also require AES meaning to decrypt you would need the key and also to exist after 1998. $\endgroup$ – daniel Dec 20 '17 at 13:50
  • 1
    $\begingroup$ @MaartenBodewes Of course, there is no reason to do this. It has the same security as a regular one-time pad but is unnecessarily complicated. $\endgroup$ – Yehuda Lindell Dec 20 '17 at 15:36
  • $\begingroup$ Forgive my near-complete ignorance of crypto, but even if the header length were 32 bits, leaving 96 bits of message, wouldn't there still be 2^96 possible values of k that give you the initial header, leaving every possible suffix as possibilities, and therefore revealing nothing about the body? I'm pretty sure that's how it works with k ⊕ x at least. $\endgroup$ – Mooing Duck Dec 21 '17 at 1:17
  • $\begingroup$ @MooingDuck that is true for k ⊕ x, but its trickier for the c=AESk⁡(x). If the header was 127 bits, for k ⊕ x its still a 50/50 guess what the last bit is and you have no hints. For c=AESk⁡(x) you could possibly get hints to what the last bit is by ruling out some values of x, if you are allowed to have the message re sent many times with a header of your choosing then you could work out what the last bit is. $\endgroup$ – daniel Dec 21 '17 at 9:23

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.