12
$\begingroup$

I'm taking a crypto class this semester and after learning the definition of a perfect cipher. I started wondering how this definition applies to AES.

Obviously AES isn't a perfect cipher, since the key length is only 256 bit at the maximum. But when talking about messages of sizes 128 bits to 256 bits, can one claim that AES is a perfect cipher?

Meaning, how can I prove that $\mathbb P(P|C) = \mathbb P(P)$, where $P$ is plaintext and $C$ is ciphertext ($\mathbb P(x)$ is probability of $x$)?

$\endgroup$
10
$\begingroup$

Short version: I don't think AES restricted to key-size messages is a perfect cipher, and I'm quite sure it can't be proven without breaking AES.

Long version:

A perfect cipher means that an attacker has the same chance to guess the plaintext if he has the ciphertext or he has no ciphertext at all, i.e. the ciphertext gives no information to someone who doesn't have the key (even with infinite computation resources).

AES itself is a 128-bit block cipher. To use it for longer messages, you need a mode of operation, and the probabilities in this statement will likely depend on the chosen mode. To avoid the complications, let's assume we have a 128 bit message encrypted with ECB mode (i.e. directly application of the block cipher), and the key is not reused for any other message.

$\newcommand\Enc{\operatorname{Enc}}\newcommand\P{\mathbb P}$Then we have a probability distribution $\P$ of the plaintext $P$ (this distribution is assumed to be known to the attacker), and on the (secret) key $K$ (which is assumed to be a uniform distribution). This induces a probability distribution of the ciphertext $C = \Enc_K(P)$ by $$\P(c=C) = \sum_{k} \P( K = k \text{ and } \Enc_k(P) = c) = \frac{1}{2^\text{key size}} \sum_k \P(\Enc_k(P) = c)$$ The conditional probability $\P(P=p|C=c)$ is defined as $$ \P(P=p|C=c) = \dfrac{\P(P = p \text{ and } C = c)}{\P(C = c) },$$ and for a perfect cipher we want that this is equal to $\P(P=p)$ for all $c$ and $p$.

In effect, this means at least that for each pair of 128-bit-blocks $(c, p)$ there must be an equal number of keys $k$ with $\Enc_k(p) = c$. With 128-bit keys, this would mean that each key maps a given plaintext on a different ciphertext, and all ciphertext blocks can be hit this way.

While this sounds like a reasonable property for a block cipher, most block ciphers (including AES) instead are trying to approximate a random permutation, where each key's actions are independent from each other – which includes the possibility that there are plaintexts $c$ and pairs of keys $k_1, k_2$ with $\Enc_{k_1}(c) = \Enc_{k_2}(c)$.

A proof that this is not possible could possibly (depending on the proof) provide a way to retrieve the key in a known-plaintext attack, which would mean that AES is broken for all practical uses (with more than one use of each key).

(This is similar for the one-time pad: correctly used, it is a prefect cipher, but using the same key twice, it is totally broken.)

AES doesn't look like easily broken, so we can assume that this is not possible.

$\endgroup$
1
$\begingroup$

Question five in this test seems to think it is equivalent but I am not convinced. If we take that question and make the header all but the last bit of the message, then its equivalent to asking about IND-CPA of a OTP vs a 128 bit keyed AES with a 128 bit length plaintext for an unbound attacker.

A unique plaintext will always map to a unique ciphertext, and this is true in reverse (why decryption gives one plaintext, not a number of possible answers which would make for a silly algorithm).

But the key-ciphertext does not have the same relationship as the plaintext-ciphertext. There is more than one key that can create the same ciphertext from the same plaintext, there are about 37% (1 / e) keys that can not create some ciphertext plaintext pairs. This means (for some reason I can't yet grasp... and I hope someone reading can fill it in for me) for a specific 128 bit block of ciphertext you have effectively less than 128 bits of key, and then over many messages of this type you have greater than a 50% chance of guessing the correct answer.

The 'necessary and sufficient condition' for perfect secrecy isn't that the key is as large as the message, but that is required. For example I could make a 128-bit block cipher that XORs each bit of the message with the parity bit of the key. This block cipher is horribly broken no matter the length of messages and keys.

$\endgroup$
  • 1
    $\begingroup$ Throwing n balls to n bins leaves n/e bins empty. It also has log(n) balls in the most populated bin. And therefor as in my answer. If both plaintext and key were chosen uniformly at random. Given the ciphertext and infinite compute power we have a probability log(n)/n to guess correctly $\endgroup$ – Meir Maor Dec 20 '17 at 17:10
0
$\begingroup$

Elaborating on Paŭlo's Answer If we have AES with 128 bit key and 128 bit messages. To meet the requirement for perfect cipher We need each Plain text to have a key which arrives at each possible cipher-text. Which means not only is the cipher a permutation with regards to the plain text it is a permutation with regards to the key as well.

This is very unlikely to be the case and probably provably not the case.

It is worth noting we normally try to model block ciphers like pseudo random permutations and for pseudo random permutation this is not what happens. If For every possible key a pick a uniformly random permutation, when I fix the plain text and look at the function on the key we get a random function not a random permutation. Collisions are expected, in fact a fair number of them. So knowing the Cipher text will actually eliminate 1/e of the plain texts which can't reach it with any key. And if we guess the most likely we will be correct with probability $O(n/2^n)$ rather then $O(1/2^n)$

This of course doesn't mean AES is insecure in any way, as this is only relevant to an attacker with infinite compute power

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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