What makes AES look like an ideal cipher?

Question

There are 2¹²⁸! permutations on 128-bit inputs. AES supports a maximum key length of 256 bits, therefore offers at most 2²⁵⁶ permutations. The total number of 128-bit permutations is much larger than what offered by AES, which means AES actually only explores a very tiny portion of the permutation space.

Questions:

1. Given AES doesn't support > 256-bit key length, what makes people believe AES (or any "good" cipher currently being used) would look similar to the ideal cipher that chooses a 128-bit permutation randomly? Put it another way, what makes people believe AES is better than another cipher with 256-bit key length which can give 2²⁵⁶ different permutations?

2. Is it possible to develop an ideal cipher with enough key length which runs encryption and decryption in polynomial time? The key length would be at least log((2¹²⁸)!). My poor math gives a result somewhat close to 128*(2¹²⁸). So I guess the answer to this question would be no. But it strengthens Question 1 by giving an idea how insufficient AES key length is: The ideal cipher requires an exponentially larger key length.

Answer 1

AES is not an ideal cipher, nor is it intended to be an ideal cipher. AES is meant to be a practical cipher that offers a strength close to the key size. That means it is computationally infeasible to find the key even if given the plaintext and the ciphertext. AES - when correctly used with a strong mode of operation - produces ciphertext is indistinguishable from random if the adversary can choose the plaintext input to the cipher themselves (IND-CPA).

The next question is why people think that AES is better than other ciphers with the same key size. Cryptographers generally don't really think that. There are other ciphers that may have better characteristics when it comes to protection against side channel attacks. Other ciphers have a larger % of rounds to spare when it comes to protection against certain attacks. Or they may have a larger block size, or they do not have a clear mathematical structure etc. etc.

AES has been studied a lot, and few attacks have come close to breaking AES. It is relatively fast compared with other block ciphers, and it has a serviceable key and block size. The algorithm is well understood, and there are many hardware implementations of AES, including newer x64 and ARM CPUs. So it is standardized, popular, well understood, but not necessarily the most secure cipher. It doesn't need to be, for most situations it is secure enough.

When you are talking about implementing an ideal cipher you seem to go over the key requirements of a one time pad. The one time pad requires a key the same size as the plaintext / ciphertext. Moreover, you won't be able to distinguish a good key from a bad key for a single block. But what happens if you have multiple blocks to compare? With each block a specific key becomes more likely. As such, it makes very little sense to try and create an ideal block cipher.

The ideal cipher is mainly a theoretical construction, useful in proofs. But beware that inserting an actual block cipher in place of an idealized block cipher may not result in a secure construction. For instance, a hash function could well be secure when constructed using an ideal cipher, while it could be vulnerable with AES-256 due to related key attacks.

Answer 2

There is a perfect cipher – one-time pad (OTP). In many cases, it is not much practical because of the key size requirements.

AES is rather some imperfect but practical cipher.

Having a that allows all the permutations for 128-bit blocks would be neither perfect nor practical:

• The key size is obviously impractical and infeasible. Even copying such key would probably take longer than exhaustive search of AES-128…
• Maybe the cipher would be perfect under some assumptions for encrypting a tiny 128-bit message. But then, you need to encrypt some larger message (which is quite common; 128 bits are not enough even for SMS…), so you lose the theoretical perfection.
• Using larger blocks would obviously require larger keys.
• Using smaller blocks would compromise security sooner than it would make the key size practical. There are known attacks for 64-bit block ciphers (see https://sweet32.info/ ), but still, a constant-size key that can describe any of those (2^64)! permutations is too large.