24
$\begingroup$

The Wikipedia entry on One Time Pads (OTPs) states that if this cipher is used properly; ie, the keys are truly random and each part of the key is independent of every other part, it's uncrackable, and yields perfect secrecy, i.e., $H(M|C) = H(M)$.

It gives an example saying that a cryptanalysis on a plaintext "HELLO" will yield all plaintexts like "HELLO", "LATER", with equal probabilities.

Now, consider some OTP encrypted data that I know are English sentences. With infinite computational power, I generate all plaintexts. Now, becasuse each word of the sentence is related to nearby words, I can at the very least narrow down the list of possibilities (I don't know the combinatorics of cramming English sentences into M letters), which does not equal perfect secrecy (entropy $H(M)$ appears to have decreased!).

In short, OTP guarantees $H(M|C) = H(M)$, but my question is that $H(M)$ will be reduced by knowledge of the plaintext, so how is prefect secrecy being ensured?

$\endgroup$

migrated from security.stackexchange.com Dec 6 '15 at 19:31

This question came from our site for information security professionals.

  • $\begingroup$ @user12480 OTP guarantees H(M|C) = H(M), but my question is that H(M) will be reduced by knowledge of the plaintext, and OTP can't do anything about it. So how is it ensuring prefect secrecy, give any plaintext. $\endgroup$ – prakharsingh95 Dec 6 '15 at 18:19
  • $\begingroup$ Simple answer: And what does this knowledge get you? Nothing. You are as smart as before because you still have no idea what the original message was, and even if you would knew the message: Without knowing the used key, you can't prove that this was the original message. $\endgroup$ – Nova Dec 6 '15 at 23:31
21
$\begingroup$

You've actually been trapped by the mindset that OTP will hide all information about the underlying plaintext.

This is not true as you have observed.

The definition of perfect secrecy, given in Introduction to Modern Cryptography by Katz-Lindell, reads like this:

Definition 2.3 An encryption scheme $(\text{Gen, Enc, Dec})$ with message space $\mathcal M$ is perfectly secret if for every probability distribution over $\mathcal M$, every message $m\in\mathcal M$, and every ciphertext $c\in \mathcal C$ for which $\Pr[C=c]>0$:

$$\Pr[M=m\mid C=c]=\Pr[M=m]$$

In other words, if you have the ciphertext at hand, you won't learn anything new that you didn't already know about the plaintext.

The OTP satisfies this (proved in "Introduction to Modern Cryptography") and thereby is perfectly secret as an encryption scheme. In short it first shows that $\Pr[C=c\mid M=m']=2^{-l}$, then uses this to show that $\Pr[C=c]=2^{-l}$ and concludes via $\Pr[M=m\mid C=c]=Pr[M=m]$ (using Bayes' theorem).

$\endgroup$
  • 1
    $\begingroup$ Hi, one more doubt popped up. OTP is telling me the length of the plaintext. That is a decrease in entropy that a perfect cipher (one that yields variable length ciphertext) will avoid. So it's not perfect secrecy anymore right (assuming the message space has non-uniform length messages)? $\endgroup$ – ps95 Sep 28 '16 at 6:19
  • 3
    $\begingroup$ @prakharsingh95 I'm pretty sure it is implicitely assumed here that the message space only contains fixed-size messages (which you can also see in the proof sketch where the message length $l$ is a fixed value). It is not an objective of (common) cryptography to hide the message length. $\endgroup$ – SEJPM Sep 28 '16 at 14:25
  • 2
    $\begingroup$ Oh I see. So long as the message space is finite, I can pad it to make equal length messages, so I guess no need to hide the length o_O. $\endgroup$ – ps95 Sep 28 '16 at 14:36
10
$\begingroup$

What you propose is equivalent to trying to do cryptanalysis without any cipher text or other material.

Equivalently, you could just take the small plaintext seed that you know, and nothing else, and run it through a probabilistic language model to predict the most likely message. (e.g., a Markov chain text generator). Obviously, it doesn't get you very far...

Consider for example, that one knowns the plaintext "attack at d___". I for one would be reluctant to rely entirely on a language model to decide if I should ready my defences for "dawn" or "dusk".

The key point here is that, all things being equal, access to the OTP-encrypted cipher text gives you no new information (beyond perhaps an upper bound on message length).

$\endgroup$
9
$\begingroup$

You stated:

"I can at the very least narrow down the list of possibilities."

Here's an example of why OTP is perfect secrecy, and why your statement, although true, doesn't matter.

I have a sentence which I wrote, and after encrypting it with an OTP, it looks like this:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Good luck decrypting that! Maybe you can narrow that down to a few million (or billion?) English sentences, but that doesn't help you. And how would you know that it's a sentence to begin with? Furthermore, as the size of the data increases, the number of possibilities approaches infinity. Even a single character message is impossible to decrypt:

a

You can narrow a single character down to 128 (or 256 or 65K depending on the encoding) possibilities, but again, that doesn't really help you much.

$\endgroup$
  • $\begingroup$ This is good I think! $\endgroup$ – Cary Bondoc Feb 5 '16 at 6:15
  • 2
    $\begingroup$ @prakharsingh95 and how does knowing the frequency of English letters help with a OTP encoded message? Variation on a Caesar shift, sure, but with a random OTP key, there isn't any pattern that would let you identify identical characters in the ciphertext. $\endgroup$ – Baldrickk Jun 12 '17 at 13:15
  • $\begingroup$ @Baldrickk think of decryption as finding the message 'M' that maximizes probability 'Pr{C|M}' over observed ciphertext 'C'. Any information about the message 'M' not contained in the ciphertext increases this probability, increasing the likelihood of the decrypted text being correct. For example, if you had a single letter of ciphertext that you had to decrypt, the chance of it being any letter is 1 in 26. But if you also knew that the letter in the cipher text was part of an English word, you could use the frequency of English letters to bet on "e", and you would be right 12.7% of the time. $\endgroup$ – ps95 Jun 16 '17 at 8:49
  • $\begingroup$ @Baldrickk To be precise, a 1 in 26 estimate yields an entropy of 4.7 bits per character, while if you use the frequency of letters, it's 4.11 bits. But this is just for one letter. If you use longer length ciphertexts, you can narrow it down much further (~2 bits per letter), which is a 6.5 fold improvement! $\endgroup$ – ps95 Jun 16 '17 at 9:01
  • $\begingroup$ @prakharsingh95 any reference for those numbers? All that is saying, that if you know that the plaintext is English, the output of your "guesses" should also resemble English. You don't know any more than you did before you started guessing. "the monkey eats the bananna" is still no more likely than "This is a 28 character line." $\endgroup$ – Baldrickk Jun 16 '17 at 11:00

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.