4
$\begingroup$

There are 2128! permutations on 128-bit inputs. AES supports a maximum key length of 256 bits, therefore offers at most 2256 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 2256 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((2128)!). My poor math gives a result somewhat close to 128*(2128). 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.

$\endgroup$
  • 1
    $\begingroup$ Actually, there are $2^{128}!$ permutations on 128 bit inputs - that is a much bigger number (and so AES generation an even more tiny portion of the permutation space) $\endgroup$ – poncho May 13 at 18:37
  • $\begingroup$ @poncho Right. My poor math. Editing the question. $\endgroup$ – Cyker May 13 at 18:46
  • $\begingroup$ Can one claim that AES is a perfect cipher? : this is highly related to part 1 . 2) The problem as you noted is the size of the data that defines the permutation. Additionally, even if you solve that one, another problem how one transfers easily that ECB into CBC,CTR, etc. $\endgroup$ – kelalaka May 13 at 20:05
  • 1
    $\begingroup$ Imagine instead of AES we had a published, widely-shared codebook that contained $2^{128}$ randomly selected 128-bit permutations, each one assigned its own unique 128-bit index, and encrypted by picking one such index secretly at random as the key. That's just as much smaller than the space of 128-bit permutations, but how would efficiently you tell this use of the codebook apart from secret random permutations? Once you contemplate it this way, I don't think your question really is about AES, it's about whether block ciphers work conceptually at all. $\endgroup$ – Luis Casillas May 13 at 20:15
  • $\begingroup$ On 2, : Indeed, the key length is $\log_2(2^{128}!)$ in bit, and by Stirling's approximation that is $\approx(128-\log_2(e))\,2^{128}$, otherwise said $2^{134.98\ldots}$ bit. Indeed that's a problem for en/decryption in polynomial time... $\endgroup$ – fgrieu May 13 at 20:21
5
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ AES is not IND-CPA secure (which is inherent since it is a block cipher). Rather, the aim of AES is to be a PRP (or in fact, even more: namely a strong PRP). $\endgroup$ – hakoja May 13 at 20:43
  • 1
    $\begingroup$ @hakoja Sure, that's why I put in "when used correctly". Of course you need a mode of operation that produces the CPA security. I altered the answer a bit to highlight that even more. Otherwise people could have a look at this Q/A $\endgroup$ – Maarten Bodewes May 13 at 21:32
  • $\begingroup$ To summarize: 1. AES is not an ideal cipher. 2. Nobody currently knows how to efficiently recover the key given plaintexts and ciphertexts. 3. A formal proof may break if an ideal cipher is replaced by AES. Specifically, I don't think 2. implies computational infeasibility: It is not known to be hard, but not known to be not hard. $\endgroup$ – Cyker May 17 at 1:55
  • $\begingroup$ 1. right 2. right. 3. right. It is computationally infeasible to break AES given the currently known attacks, and we don't know if there are any better ones that would make it computationally feasible. $\endgroup$ – Maarten Bodewes May 17 at 13:06
-3
$\begingroup$

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.
| improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ This does not answer the question, which is about ideal ciphers, not perfect secrecy $\endgroup$ – Maeher May 14 at 11:37

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.