Score:4

If I encrypt a plaintext with different keys for each block, will I have the same security as a one-time pad?

il flag

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?

Paul Uszak avatar
cn flag
Title: You encrypt the plain text, which then produces cipher text...
alpominth avatar
il flag
Fixed. I'm always in the clouds, sorry.
Toby Speight avatar
in flag
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.
Score:4
ch flag

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.

Crypto Learner avatar
in flag
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"?
canary avatar
ch flag
@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).
Crypto Learner avatar
in flag
so, can an unbounded eavesdropper learn anything from an OTP ciphertext, once it is Information-theoretic secure[https://en.wikipedia.org/wiki/Information-theoretic_security]? And what about AES?
canary avatar
ch flag
No adversary can learn anything (other than previously available information about the plaintexts) from an OTP ciphertext. For AES that depends on its internals.
Score:1
cn flag

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 :-)

alpominth avatar
il flag
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.
ManfP avatar
cn flag
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.
Paul Uszak avatar
cn flag
@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.
jp flag
it's pretty likely to be pretty close, however.
jp flag
@PaulUszak Consider an encryption that only returns the ciphertext "ASDFGHJKLQWE" in cases where m="ATTACKATDAWN" k=1337, and in other cases where m is gibberish. Since we see the ciphertext "ASDFGHJKLQWE" and we assume m is not gibberish, we now know m and k. This is possible even if k is much longer than m. However, if we assume E has good properties and k is much longer than m, then this isn't possible with any significant probability.
Crypto Learner avatar
in flag
@PaulUszak, are you assuming that AES provides perfect security and is therefore resistant to an unbounded adversary? I have never come across such a claim in my reading.
Paul Uszak avatar
cn flag
@CryptoLearner I'm obviously having to go and re-edit this. I'm not suggesting any security of AES at all. It's irrelevant what it does as long as it's bijective - a one to one match between plain text and cipher text based on a key. That's what it does. It's exactly like XOR but with 128/256 bits at a time. With exactly the same strength as XOR. The security comes from the truly random key per block. Each cipher block can decrypt to many alternate plain text blocks, depending on the key. Just as a OTP.
ManfP avatar
cn flag
@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.
Paul Uszak avatar
cn flag
@ManfP If there is no bijection, how do we use AES across the world?
ManfP avatar
cn flag
@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).
Score:0
in flag

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.

ManfP avatar
cn flag
"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)
Crypto Learner avatar
in flag
@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?
ManfP avatar
cn flag
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.
Crypto Learner avatar
in flag
@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.
ManfP avatar
cn flag
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.
Crypto Learner avatar
in flag
Oh, I agree. But you sound similar to a high-profile user here. I think it would be more interesting if you gave us your answer - preferably using your real username. If you haven't given it to us, did you?
ManfP avatar
cn flag
I have no idea what you are talking about. This is my only stackexchange username.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.