Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer 1

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, it is also one which looks like quite hard to prove. I assume proving this could actually 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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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