5
$\begingroup$

As I understand it, a plaintext encrypted using a One Time Pad is uncrackable because all possible plaintexts of the same length are possible. As a concrete example, if you decrypt the first 3 bytes of a 4-byte plaintext that you know is in English and get "HEL" (and you knew that was correct somehow), that does not help you decrypt the final byte. It is equally likely that the plaintext is "HELO", "HELP', "HELL", etc. and there is no way for you to know which is correct.

What is the concrete step(s) of AES (or a similar popular symmetric key encryption algorithm) that makes encrypting an n-byte plaintext with an n-byte key not the same as a One Time Pad?

It feels intuitive that if the key is shorter than the plaintext, then all plaintexts cannot be possible regardless of the algorithm. The other way around (key longer than the plaintext) is not intuitive.

$\endgroup$

1 Answer 1

5
$\begingroup$

Block ciphers, AES is a block cipher, encryption $Enc$ can be formalized as

$$Enc:\mathcal{P} \times \mathcal{K} \to \mathcal{C}$$ where $\mathcal{P}$ is the plaintext space, $\mathcal{K}$ is the keyspace, and $\mathcal{C}$ is the ciphertext space. Similarly the decryption; $$Dec :\mathcal{C} \times \mathcal{K} \to \mathcal{P}.$$ For a block cipher the $\mathcal{P} = \mathcal{C}$. The number of elements of this space is determined by the bits, for $\mathcal{P}$ it is determined by the block size. AES has 128-bit block size and it has $2^{128}$ message space for a single block. For DES it is $2^{64}$. AES has variable key sizes like 128,192, and 256, therefore, the keyspace $\mathcal{K}$ is $2^{128},2^{192},\text{ and } 2^{256}$, respectively.

We require the operation of a block cipher invertible[*] so that we can decrypt. Therefore the block ciphers are permutations. Each key from the keyspace selects a permutation for all possible permutations. The number of permutations of the message space is $2^b!$ where $b$ is the block size and for AES this is $2^{128}!$. With the Stirling's approximation $$2^{128}! \approx \sqrt{2\pi 2^{128}}(\frac{2^{128}}{e})^{2^{128}}.$$ That cannot be covered by the tiny keyspace $2^{128}$, tiny according to comparison, but huge for any classical computational power.

We expect that a block cipher behaves like a Pseudo-Random Permutation that is a function that cannot be distinguished from a random permutation and AES has believed to be one.

Back to your questions;

  • What is the concrete step(s) of AES (or a similar popular symmetric key encryption algorithm) that makes encrypting an n-byte plaintext with an n-byte key not the same as a One Time Pad?

Block ciphers use the confusion diffusion paradigm, Shannon 1945. Here, what related to your approximation is, changing one bit of the key will affect all ciphertext bits. If the cipher achieves the avalanche effect property then it will randomly flip half of the bits. Therefore all of the bits of the block are affected (affected doesn't mean changed) whereas in OPT changing one bit only affects one plaintext bit.

  • It feels intuitive that if the key is shorter than the plaintext, then all plaintexts cannot be possible regardless of the algorithm. The other way around (key longer than the plaintext) is not intuitive.

It is not all of the plaintexts, it is all of the permutations. In AES. all of the 128 bits are valid plaintext and plaintext space contains all. But block ciphers randomly select permutations from all possible permutations space. With the keyspace, we cannot cover all of the permutations. They are limited to keyspace.

This the distinction between the OTP and AES or any block cipher. In block ciphers, the key size is fixed no matter the length of the plaintext. In block ciphers, We use computational security since we cannot achieve informational security without key bits equal to message bits.

  • If the question is if the key is as large or larger than the plaintext, then why can AES be distinguished from a perfect cipher?

There is no guarantee that given a ciphertext $c$ decrypted under all possible keys $c=AES_k(x)$ gives all possible plaintexts or gives all but they are equally distributed. This is contradicting to perfect secrecy that OTP has.

To prove that AES has perfect secrecy in this sense, we need to fully analyze the AES. This is beyond our computation point. If possible, it may lead to a known-plaintext attack.

While it is reasonable property of a block cipher that reaches all possible plaintext, equally, most block ciphers try to approximate random permutation where each key is independent of the others. This means that we may not reach all plaintext with decryption of $c=AES_k(x)$ under all keys. Or similarly, possibly there are plaintexts where $E_{k_1}(c)=E_{k_2}(c)$.


[*] Block cipher need modes of operation, and not all modes require decryption, like CTR mode. In CTR mode, one can use Hash functions that are not permutations.

$\endgroup$
5
  • 1
    $\begingroup$ I'm guessing that the writer meant to ask is that if the key is as large or larger than the plaintext, then why can AES be distinguished from a perfect cipher? But I may be wrong about that, hard to tell. $\endgroup$
    – Maarten Bodewes
    Commented Feb 8, 2020 at 14:42
  • $\begingroup$ @kelalaka thank you for the detailed answer! i am interested in the difference between AES and OTP when the plaintext length <= key length. it sounds like the confusion diffusion part of the AES algorithm (the matrix row/column shifts) is what separates it from a one time pad. is that correct? or is there more to it, like XORing the round keys? thanks again! $\endgroup$
    – tau
    Commented Feb 8, 2020 at 17:27
  • 1
    $\begingroup$ @tau added an answer for <= part in the answer. OTP is simple but requires as many keys as plaintext that is hard to reach. Therefore, we work on computational secrecy. To achieve this one way is SPN bases block ciphers like AES. To achieve confusion diffusion AES uses the matrix row/column shifts and key x-oring round keys/. $\endgroup$
    – kelalaka
    Commented Feb 8, 2020 at 17:45
  • $\begingroup$ @kelalaka that makes sense, but why is there no guarantee in AES? what step in AES ruins any guarantee? $\endgroup$
    – tau
    Commented Feb 8, 2020 at 17:52
  • 1
    $\begingroup$ @tau updated the last part. I hope that it is more clear, now. $\endgroup$
    – kelalaka
    Commented Feb 8, 2020 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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