4
$\begingroup$

Let's suppose I encrypt an 1MiB plaintext with AES-256 in ECB mode but using different keys for each 16-byte block (I know this is weird but it's just an example).

Remembering that a different 256-bit key will be used for each 128-bit block, so if the adversary wants to break a block, a brute-force in the key space of 2^256 will be needed, and due to the Pigeonhole principle, many different keys will produce the same plaintext (I suppose).

Will this scheme have the same security as a one-time pad?

$\endgroup$
3
  • 1
    $\begingroup$ Title: You encrypt the plain text, which then produces cipher text... $\endgroup$
    – Paul Uszak
    Jul 3, 2023 at 3:10
  • $\begingroup$ Fixed. I'm always in the clouds, sorry. $\endgroup$
    – alpominth
    Jul 3, 2023 at 6:46
  • 1
    $\begingroup$ Definitely not practical: assuming all the keys are independent, you now need to transfer twice as much key information securely to your recipient, compared to simple one-time pad. If the keys are not independent, then you likely don't have OTP-equivalent security. $\endgroup$ Jul 3, 2023 at 13:57

3 Answers 3

1
$\begingroup$

Yes it is. With a small but important caveat.

And the reason is that the key entropy (256 bits) exceeds any possible message entropy (128 bits). Simples.

It's easy to read "AES" and infer that it can't be as good as a one time pad (OTP). But that's a fallacy within this narrow context. Consider correctly implemented AES as a compressive mixing function, say $\theta$. 384 (as 256 + 128) bits go in, 128 bits come out.

$$ AES_k(m) \rightarrow \theta_k \; (m) \rightarrow k \oplus m $$

If the Kolmogorov entropy of $k$ exceeds that of $m$, the system by definition must be a OTP. Recall that the mixing function only became a mathematical XOR when computers arose. Before then all that was required was a keyed bijective relationship between plain text and cipher text. Something like a DIANA table. That works on A-Z letters, and $\theta$ works on 128 bit binary data.

And now that Kolmogorov has been dragged up, to the caveat. $k$ must be truly random. So no counters, random number generators e.t.c. No books on your shelf or music files on your PC. There must be a physical device producing the key material, with an expected entropy $> \frac{1}{2}$ bits/bit.

Seems a daft way to encrypt :-)

$\endgroup$
10
  • $\begingroup$ Yes, it is a stupid way to encrypt something. I asked this because a cipher that allows arbitrary block sizes and key lengths could possible be used together with a form of hash table, for example, hash a seed, split in 64-bits words and divide by a (large) number and associate each number to a position in a large data chunk (a form of "hash table"), and use for each block multiple pieces of the "hash table" mapped by the word divided by the position on "hash table". Just a idea that I need to investigate and study a lot more. $\endgroup$
    – alpominth
    Jul 3, 2023 at 6:29
  • 4
    $\begingroup$ This is incorrect: Even with the key chosen uniformly random, there is no reason to believe that AES is truly a random permutation without any "imperfections". Thus it's unlikely to achieve the notion of perfect secrecy that a one-time pad does. $\endgroup$
    – ManfP
    Jul 3, 2023 at 8:28
  • $\begingroup$ @ManfP Perfection irrelevance. It only has to be bijective (with a key). Don't think AES, just think bijection function $\theta$. The "perfect security arises from the truly random key material. $\endgroup$
    – Paul Uszak
    Jul 3, 2023 at 11:50
  • 1
    $\begingroup$ @PaulUszak what you need is not a bijection between plaintext and ciphertext though - but a bijection between key and ciphertext, for each fixed message (assuming that the keys are as large as the block size; if they are larger, you want that the preimage of every ciphertext has the same size). It is very unlikely that AES has that property. $\endgroup$
    – ManfP
    Jul 4, 2023 at 12:27
  • 1
    $\begingroup$ @PaulUszak AES(-128) is a bijection from message to ciphertext (for a fixed key). That does NOT imply it being a bijection from key to ciphertext (for a fixed message). $\endgroup$
    – ManfP
    Jul 4, 2023 at 20:28
4
$\begingroup$

No, not necessarily. That depends heavily on the underlying algorithm (AES). Suppose that AES leaks information about one bit (of the input block) with negligible probability $\epsilon $. Then there exists an adversary that can distinguish between AES and OTP with probability $\leq \epsilon$ (this attack game is for one-block input only). AES is still secure in that case, but not as secure as OTP which is perfectly secure.

The above assumption is just an example to show that this depends tightly on the inner work of the block cipher.

$\endgroup$
4
  • $\begingroup$ We always can make AES secure against a chosen-plaintext attack. If the adversary can guess the message position s/he can just do (message XOR key) XOR message = key. What do you mean by "AES is [...] not as secure as OTP"? $\endgroup$ Jul 3, 2023 at 19:29
  • $\begingroup$ @CryptoLearner, If I understand it correctly, you are talking about CPA-security. I'm actually talking about EAV security according to the setting of the question ( but only for one-block-size input). $\endgroup$
    – canary
    Jul 3, 2023 at 21:20
  • $\begingroup$ so, can an unbounded eavesdropper learn anything from an OTP ciphertext, once it is Information-theoretic secure[en.wikipedia.org/wiki/Information-theoretic_security]? And what about AES? $\endgroup$ Jul 3, 2023 at 21:35
  • $\begingroup$ No adversary can learn anything (other than previously available information about the plaintexts) from an OTP ciphertext. For AES that depends on its internals. $\endgroup$
    – canary
    Jul 3, 2023 at 22:18
0
$\begingroup$

No, because any use of a deterministic/computationaly-secure cryptosystem makes it possible for an unbounded adversary to recover the cleartext. For example, if the encrypted cleartext carries certain recognizable semantics such as a specific text or code, that unbounded adversary could match it to a key.

However, OTP provides resistance against such an unbounded adversary. It functions as a perfect private channel, ensuring that the adversary will not learn anything beyond what they already knew (but think about CPA - chosen-plaintext attacks). Therefore, it's important to note that OTP provides a (I) information theoretically (II) private channel.

$\endgroup$
7
  • $\begingroup$ "No, because any use of a deterministic/computationally-secure cryptosystem makes it possible for an unbounded adversary to recover the cleartext" Counterexample: The XOR "cipher"(/vigenère), when used in this way. Though that's not to say that the same is (likely) to be true for AES... (granted, they are hardly "computationally secure" - so feel free to compose them with your favorite cipher under an independent second key) $\endgroup$
    – ManfP
    Jul 3, 2023 at 8:31
  • $\begingroup$ @ManfP, Sorry, but you seem to have some misunderstandings about basic security concepts. A perfectly private, information-theoretically secure channel assumes an unbounded adversary. On the other hand, a computationally private channel considers a bounded and limited adversary. Therefore, the latter is vulnerable when facing an unbounded adversary. Now, where do you think AES fits into this context? $\endgroup$ Jul 3, 2023 at 19:11
  • $\begingroup$ of course AES is not secure against unbounded adversaries. But the fact that "every" cryptosystem designed for computational security can't provide perfect security when used in the way OP describes (i.e., a block cipher with each key only used for one block) is false. For example, "AES without key schedule" (so with a 1408-1920 key per 128-bit block) would suffice, as it would effectively be a concatenation of a OTP with some other operations involving independent key material. $\endgroup$
    – ManfP
    Jul 4, 2023 at 12:25
  • $\begingroup$ @ManfP, I see that by unconditional or perfect secrecy, OTP always put a "lack of information" to the eavesdropper: how can s/he realize that any specific key is the real, since any other key decrypts to anything? So, the same isn't true in the OP context. Your last comment sound like: how to convert a computational (conditional) secure cryptosystem in an unconditional by a key choice. $\endgroup$ Jul 4, 2023 at 21:16
  • $\begingroup$ as I understand, converting a computationally secure cryptosystem into an unconditionally one ("same security as a OTP") is exactly what the question is about though. $\endgroup$
    – ManfP
    Jul 5, 2023 at 22:41

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.