Perfect secrecy of block ciphers

Is it right that all block ciphers don't provide perfect secrecy like AES? If it's true, how can we prove that? If it's not true can you tell me a sample? Any reference or guidance would be appreciated.

• AES does not provide perfect secrecy. – mat Sep 18 '17 at 8:55

1 Answer

Perfect secrecy, in the sense defined by Shannon, means that observing the ciphertext does not allow an attacker (who has no knowledge of the key) to learn any new information about the plaintext beyond what they already possess.

(Note that there are no restrictions on what the attacker may already know about the plaintext; for example, they might already know that the plaintext is one of two specific messages, and just want to know which one. Also, for technical reasons, we generally assume that there's an upper bound on the length of the plaintext, and that this upper bound is public information, i.e. already known to the attacker. This is because no cipher capable of encrypting arbitrarily long messages can perfectly hide their length.)

Importantly, unlike more modern computational definitions of security (such as semantic security), the definition of perfect secrecy does not assume anything about the amount of computing power available to the attacker. Thus, for example, the attacker is free to generate any number of candidate keys and to try to decrypt the ciphertext with each of them.

Based on this, it's easy to show that no cipher can possibly provide perfect secrecy unless the number of possible keys is at least as large as the number of possible plaintexts. If there are $k$ possible keys and $n$ possible plaintexts, then the attacker (who, in this case, is assumed to know nothing about the plaintext in advance except that it's one of the $n$ possibilities) can simply try to decrypt the ciphertext with each of the $k$ keys, and thus obtain (up to) $k$ distinct decrypted messages. If $k < n$, the attacker has thereby just learned something about the plaintext: namely that it's not one of the $n - k$ possible messages that the ciphertext did not decrypt to using any of the keys.

(We can also extend the same result into a proof that no cipher can provide perfect secrecy if the same key is used to encrypt multiple message, unless the key is at least as long as the combined length of all the messages.)

A block cipher like AES normally has a fixed key length (e.g. 128 bits for AES-128, or 256 bits for AES-256). While in principle a block cipher like AES could provide perfect secrecy if the messages were no longer than the key, and if each key was only used to encrypt one message, in practice an encryption scheme capable of only encrypting up to 256 bits of plaintext per key would be pretty useless.

Thus, normally, AES is used with a mode of operation that allows it to be used to encrypt multiple messages of (more or less) arbitrary length. Such modes of operation make AES into a practical general-purpose encryption scheme — but, as an inevitable side effect of allowing longer and/or more messages to be encrypted with the same key, the resulting encryption scheme cannot possibly provide perfect secrecy.

(Fortunately, they do still provide provable practical security against computationally limited real-world attackers who cannot just test every 256 bit AES key by brute force — something which appears to be safely beyond the reach of mankind.)