30

I am reading "Serious cryptography" and he wrote the following:

Informational security is based not on how hard it is to break a cipher, but whether it’s conceivable to break it at all. A cipher is informationally secure only if, even given unlimited computation time and memory, it cannot be broken. Even if a successful attack on a cipher would take trillions of years, such a cipher is informationally insecure.

Then, he proceeded to write that the one-time pad is informationally secure.

I don't understand this at all. If we see a cyphertext, such as 00110, we know that the corresponding plaintext has 5 bits as well, and the cypher key will also have 5 bits, thus 2^5*2^5=1024 possible combinations. Bruteforcing 1024 will yield a result. Even if the cyphertext is huge and bruteforcing won't be practical, it is still theoretical possible, no?

If it is theoretical possible, wouldn't it deem the one-time pad as informationally insecure?

What am I missing here?

2
  • 1
    In Cryptography, usually, the length of the message is not assumed to be secret.
    – kelalaka
    May 6 at 18:49
  • 2
    If the message length reveals information, that's the domain of traffic analysis rather than cryptography. The usual defence is to pad messages to a fixed length (and perhaps to send messages at a constant rate, using empty messages as needed). May 6 at 21:27

3 Answers 3

95

Bruteforcing all 1024 possibilities will yield a result.

Yes, a result. But even if you iterate all 32 5-bit combinations, you still have no idea which one the "correct" one is. That's what makes it informationally secure: Even if you iterate every key (and thus, every possible message), you don't know which of these messages is the one that was sent.

For example, imagine the following message:

ATTACK AT 8

It's 11 characters long, and you could conceivably iterate the space of all 11-character strings. This will yield results such as:

PIZZA TIME!
YOZNACKS :)
ATTACK AT 3
ATTACK AT 8
IN UR BASE!

Now you look at all these messages and you still are none the wiser. In fact, you don't even need the ciphertext at all. Knowing the length of the message, you can simply iterate the entire message-space and all you will know for sure is that one of these messages must be the correct one.


To break it down even further, imagine your message is just a single bit, either 1 or 0. To encrypt it, you either decide to "flip" it or not (meaning, you XOR it with 1 or 0).

This leaves us with the following 4 states:

  1. Message 0, Key 0 => Ciphertext 0
  2. Message 0, Key 1 => Ciphertext 1
  3. Message 1, Key 0 => Ciphertext 1
  4. Message 1, Key 1 => Ciphertext 0

You then present the ciphertext to the attacker, while keeping the key secret. Say, you present 1. According to the table, the message was either 0 with a key of 1, or the message was 1 with a key of 0. But since the attacker does not know the key, they only have a 50% chance of guessing the correct bit - which is the best they can do in a perfect system.

For every bit in the message, the chance of successfully guessing the message is divided by half. And again, you can only guess the message - there is no indication whether your guess is correct or not.

19
  • 45
    @YozNacks Think about it like this: If I picked a card out of a 52 card deck, then handed you the deck and you looked at every card, you could also "see" my card - but you wouldn't know which one of these would be my card. (It was the 6 of Spades by the way :P)
    – user163495
    May 5 at 12:51
  • 6
    Minor nitpick: Given a 5 bit ciphertext, you don't need to iterate through all 1024 possible message-key pairs, you just need to iterate through the 32 possible keys. Of course, it doesn't really matter either ways.
    – nobody
    May 5 at 13:19
  • 9
    @KrazyGlew That doesn't quite help with a one time pad. You just end up with a bunch of human language plaintext's that are all equally likely, and there is no way to tell them apart. It does work for other real world ciphers, because normal ciphers are not information theoretically secure.
    – nobody
    May 6 at 5:29
  • 10
    @OscarBravo No, the Enigma was broken because they re-used the same key for two different messages. Even if you know my message ends in "Heil Hitler", you still get every possible message before that.
    – user163495
    May 6 at 10:57
  • 8
    This is a good explanation, and from an information-theoretic standpoint, the most important part is hidden in the note "in fact, you don't even need the ciphertext at all". In other words, having the ciphertext without the OTP does nothing to change your estimate of the probability of a given plaintext, or in other other words: it gives you zero information.
    – hobbs
    May 6 at 16:45
10

MechMK1 answer is a very good explanation and I just want to make some additions:

Yes, if the cipher text is 5 Bits your adversary has learned that the message was 5 bits. Especially, he has learned, that there was communication at all, which maybe something you might want to avoid. That is why in such cases one performs dummy communication to keep the line busy.

The term "informationally secure" refers to the content of your message and what the adversary might theoretically learn about the plain text by observing the cipher text. To quantify this, one can use the concept of mutual information. Mutual information can be thought of as follows (I find the definition I(X;Y)=H(X)-H(X|Y) being the most convenient for this purpose) : You have some uncertainty, what the message is (usually measured by its entropy). Now you observe the cipher text. Afterwards your uncertainty about the message is reduced to the conditional entropy given you know the cipher text. The difference between those twos, namely the mutual information, quantifies how much learned. For one time pads, this difference is 0, which means you haven't learned anything. Note that we have no requirement that the plain text message are somehow equidistributed, only the key.

Regarding you brute force method: You could do that, but you still haven't learned anything. All possible decryptions are equally likely.

1

Instead of thinking of decrypting a single message, think of that idea of "breaking" the code. Suppose we have an algorithmic cypher, a hundred messages encrypted using it, and a mega-powerful science fiction computer (simulating "unlimited computation time and memory"). It blasts through gagillions of cyphers and finds one with reasonable results for all 100 messages. We think we've "broken" the cypher, in the sense that we can quickly decode the 101st message using our guessed algorithm. We could give our solution to anyone to let them easily decode future messages.

Now try that on a 1-time pad and you'll see it won't work. Let's go nuts and say a spy has given us everything -- the real contents of the first 100 messages together with confirmation of the first 100 entries in the pad. How can we use that to decode the 101st message? Well, not at all. The 101st entry in the pad is independently random. It's like looking at a sequence of 100 numbers, being asked to guess the next, and being told "BTW, these are all random". This is what the author means by writing it's not conceivable to break a 1-time pad in the sense of breaking an algorithmic one.

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.