How is one-time pad secure against infinite computational resources?

Question

Shannon's one-time pad is often used as an example of an information-theoretically secure system. An information-theoretically secure communication can not be broken by someone who has "infinite" computational resources.

If I am correct till here then let's say the message is $l$ bits long. Then, so is the key $S$. Can't someone just try all $2^l$ keys which is easy if they have infinite computational resources?

I guess, if the attacker can not spot the correct message than it makes sense but what if the message was English text? The key among the $2^l$ that produces valid English clearly can be found.

Answer 1

One Time Pad (OTP) requires uniform random key bits to be information-theoretically secure. Once the key is transmitted securely with a trusted carrier, than the messages transmitted between the two sides are secure as long as the keystream is never used again ( keywords: two-time pad, many-time pad, and crib-dragging).

In the correct usage of OTP, the attacker cannot learn anything about the message other than the message length of the transmitted message.

Once an eavesdropper obverserved an $\ell$ length OTP message, then all possible English text of size $\ell$ are possible candidates. The question is how can you distinguish?. For example, you expected that your enemy will attack tomorrow but don't know the time. You received a message of size 14 characters (Well, omit the encoding). Is it $\texttt{ATTACK AT DOWN}$ or $\texttt{ATTACK AT NOON}$? How you can decide which one? Why do we limit these two messages, because it is educational. What about $\texttt{WAIT FOR ORDER}$?. Usually the (military) messages are not this short long, so there will be numerous possibilities for each message. Even for two possible messages you fail to distinguish, how you can distinguish if there is more than one possibility?

You may some candidates of possible messages, however, this is your prejudice about the messages. If you look at the historical exploits, you will see that either weak random, or two time-pad for the exploits!

Now, why do you limit the message to meaningfull English? Maybe they are just coordinates? Maybe some other binary data!

To make it more interesting, let they sent a single bit! 1 for attack 0 for wait in every minute. Can you distinguish?

No matter what computainally power you have, you cannot distinguish the two messages!

Answer 2

Given a cipher text of length $L$, and plain texts of the same length $L$ are equally likely (as all keys are of the same length and random). Any attacker has no way of telling which is right.