2
$\begingroup$

I just started my network security course and came across the below question. Could some one help me here.

User A wish to send a 128-bit secret message, S, to user B. As the preliminary step, both A and B agree to use a 128-bit secret key, K, selected uniformly at random. At the time of transmission, A considers two different ways to secure the secret message, S. The first way is to encrypt S using the key, K, as one-time pad and send S ⊕ K to B. Alternatively, the second method is to directly use AES algorithm to encrypt S. In this case, the secret message, S, needs to be encrypted as a single 128-bit block. Despite of using either one-time pad or AES, suppose that an adversary, C, knows some initial portion of the original secret message, S, and can see the entire encrypted message during transmission. The primary intention of the adversary, C, is to recover full secret message from the encrypted message by trying every possible key. In this situation, which method among the one-time pad and AES would be more secure?

Select one:

  1. Both methods are equal. The adversary can decrypt the ciphertext in both the methods
  2. One-time pad
  3. AES
  4. Both methods are equal. The adversary cannot decrypt the ciphertext in both the methods

My understanding:

In case of one time pad, as the attacker already knows the initial portion of plaintext and complete cipher text, attacker can just XOR them to get the initial portion of key. Attacker has to use brute force for the remaining key bits.

But in the case of AES, the attacker has to try 2^128 combinations to get the complete plain text.

So, AES is more secure than one-time-pad in this case.

In course content, answer is given as :

  1. Both methods are equal. The adversary cannot decrypt the ciphertext in both the methods
$\endgroup$
1
  • 5
    $\begingroup$ Brute force doesn't work on a one time pad as any plaintext bit that you will get after XOR is equally likely. The size of the remaining secret therefore doesn't matter. Actually, for AES something similar will be the case, as many keys may produce the initial plaintext, so even bruteforcing won't gain you much. Information theoretically the AES block cipher is slightly less secure as some key / plaintext combinations may be more likely. AES becomes less secure once more ciphertext / plaintext is available (but still within AES bounds, if applied corrrectly). $\endgroup$
    – Maarten Bodewes
    Apr 1 at 7:48
1
$\begingroup$

So, AES is more secure than one-time-pad in this case.

No, the one-time pad is perfectly secure, so it cannot be less secure than AES. What's tripping you up is you're not understanding a subtle detail of what perfect secrecy means. People often misunderstand it to mean "the attacker cannot learn what the plaintext is," but in reality it means this:

  • No matter how hard they analyze the ciphertext, it cannot help the attacker learn anything more about the plaintext other than what they can figure out through other means.

Take your argument here:

In case of one time pad, as the attacker already knows the initial portion of plaintext and complete cipher text, attacker can just XOR them to get the initial portion of key. Attacker has to use brute force for the remaining key bits.

Here the initial portion of plaintext is something that the attacker learned not by cryptanalysis, but through some other means. So the question is whether analyzing the ciphertext can gain them additional knowledge about the plaintext. And the perfect secrecy of one-time pads tells us that it cannot, because given just the ciphertext and initial portion of plaintext, every possible remaining portion of plaintext is equally likely.

Another way to put this is that given the initial portion of plaintext, analyzing the OTP ciphertext isn't any more effective than just looking at that initial portion of plaintext and guessing how it might continue. Like, if the initial portion says ATTACK AT D, you might guess the full plaintext is likelier to be ATTACK AT DAWN than ATTACK AT DUSK just because dawn attacks are more common than dusk attacks. But no matter how hard you analyze the ciphertext, it won't help to settle this any further.


In course content, answer is given as :

  1. Both methods are equal. The adversary cannot decrypt the ciphertext in both the methods

I think this answer is wrong, depending how we interpret the question though. A brute-force attack might learn something about the plaintext in the AES scenario; but "might" is a key word there, there's no guarantee.

The idea would be to do this. Given ciphertext $C$ and partial plaintext $P'$ of length $l$ (in bits), go over every possible AES key $K_i$, and:

  1. Compute $P_i = \mathrm{AES}^{-1}_K(C)$ (the AES decryption of $C$ with key $K_i$);
  2. If the first $l$ bits of $P_i$ matches $P'$, then add $P_i$ to the set $S$ of candidate plaintexts; otherwise, discard $P_i$.

Now, for the security of AES in this scenario to be the same as one-time-pad, the resulting set $S$ must be of size $2^{128-l}$—the set of candidate decryptions must be the same as the set of all possible 128-bit strings that start with $P'$.

But all it takes for this to fail is that there exist a single collision—a pair of keys $K_1$ and $K_2$ such that $\mathrm{AES}^{-1}_{K_1}(C) = \mathrm{AES}^{-1}_{K_2}(C)$ (i.e., that $C$ decrypts to the same plaintext for both keys). And such collisions are indeed possible. And if there are such collisions, then there will also be "missing" plaintexts in $S$, which the attacker therefore learns are impossible given $C$ and $P'$.

Ultimately the course's question is vague, because it has these problems:

  1. "Can the attacker decrypt the ciphertext" is a simplistic goal. As I mention above, the sort of goal that cryptography normally contemplates is "can the attacker learn something about the plaintext by analyzing the ciphertext," which may fall short of a full decryption.
  2. In the AES scenario the question poses, it's possible but not certain that the attacker could rule out some candidate plaintexts. But the question isn't formulated in a way where we know for sure whether to count that as "the attacker can" vs. "the attacker can't."

There's two key certainties here, though:

  1. The one-time pad is perfectly secure but AES is not.
  2. Network security textbooks often don't teach cryptography exactly right
$\endgroup$

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.