Why is onetime pad not able to be brute forced no matter how

Why is one-time pad not able to be brute forced no matter how fast your computer is or trying every possible decryption key?

Solution

First you have to understand why it is possible to do exhaustive key searches on other systems.

Suppose you have a plaintext of length n, ciphertext of the same length n, and a key of length k (all in bits). Then by trying all possible keys we obtain at most 2k candidate plain texts. If the system has some kind of validation or message integrity built into it then it might be rather less than 2k. It has to be at least 1, and it might only be 1, in which case exhaustive search always works against that system .

But supposing the system itself doesn\'t tell us which key is correct : if k is much smaller than n, then only a very small proportion of all possible length-n messages will be represented in our exhaustive search. One of them is the correct plaintext, and the rest are not. How do we normally know which one is right? The answer is that normally the others will be garbage, because if you pseudo-randomly choose 2k strings of length n, for k significantly smaller than n, then with very high probability all of them will be garbage. It\'s only because what we start with is known to be an encrypted message that we have any right to expect any of the outputs to make sense.

So, normally speaking if we find a candidate key that produces sense, we\'re fairly confident that we\'ve broken the message. We still might not know for sure. For example, perhaps by chance the system has two different keys, one of which deciphers the given ciphertext to \"attack at dawn\", and the other deciphers it to \"attack at dusk\". But for cryptosystems that are subject to exhaustive search this must be very unlikely, and so as soon as we find a message that makes sense we have far more confidence than the sender of the message is comfortable with us having, that it is indeed the message they sent. If these are the only two candidate plaintexts that make sense, we\'ve already learned way more about the message than the sender would like. Furthermore suppose the sender uses the same key more than once, and the same key produces sense for multiple different ciphertexts. This almost cannot happen by chance, so we are now very confident that we have brute-forced the key.

Now, what about OTP? Then k = n, so even if the outputs were pseudo-random we\'d expect many candidates that make sense. What\'s even worse, exhaustively trying every single key generates every single text of length n as a candidate plaintext. Specifically, the message M is generated by the key M XOR C, where C is the ciphertext. It is guaranteed that we will find a key that deciphers the message to \"attack at dawn\", and another that deciphers to \"attack at dusk\", and another that deciphers to \"mine\'s a pint!\", and so on for every message of that length.

So if we do our exhaustive search, all it will tell us is that \"the plaintext could be any message of length n\". Which we knew already. We can still rule out the garbage, but doing so leaves us with every single non-garbage message of the correct length.

This can be explain with another example -

If you have, P1P2P3P4K1K2K3K4=C1C2C3C4

where each P, K and C are one bit, then C1C2C3C4

can have any value possible.

Now assume your brute force will try A1A2A3A4

as key, then C1C2C3C4A1A2A3A4=Z1Z2Z3Z4 will have any value as well. There is no way to test if Z1Z2Z3Z4=P1P2P3P4 though. As there is no relationship at all between different bits then every Z value will be equally likely.

That\'s why an OTP is perfectly secure for messages of a particular size. Modern ciphers such as AES do have a relationship between the bits, so there are possibilities to check if you have the correct plaintext for a given key with an amount of certainty. With an OTP, the chance that you get the plaintext bit back is exactly 0.5 per bit - i.e. you don\'t know if you guessed right or not.