Unbreakable code using XOR for one time pad?
in [Cryptography]
|
Prev: Cipher challenge
Next: Rolex Oyster Perpetual Cosmograph Daytona Mens Watch 116523-WDO Collection
From: Bill B on 14 Nov 2008 00:43 On Nov 12, 10:27 pm, Bryan Hussein Olson <fakeaddr...(a)nowhere.org> wrote: > Bill B wrote: > > Guy Macon wrote: > >> Bill B wrote: > >>> Why does the key need to be random? > >> Try it yourself with this 1 byte message: "Y" > > [...] > > > Now, if Eve knows the answer is "Y" or "N" she has > > the option of xoring character 0 against the byte "Y" > > to obtain "Y", or she can use character 23 to obtain > > "N" > > > She basically has the choice of making the text say anything she > > wants. > > > How can she possibly find the real message? > > The fact that special-case message spaces show a pattern of redundancy > that may tolerate corresponding redundancy in the key is not > particularly interesting. A uniform random key-stream can support > perfect secrecy in the general case. When we have special-case info > about the message space, we can often use it to encode more efficiently, > which is a better tactic than weakening our key-generation requirements. > > If Alice and Bob know their message space precisely in advance, say it > contains M message of non-zero probability, then they can encode any > message in B = ceiling(lg(M)) bits. They can then achieve prefect > secrecy using only B bits of (uniform random) key. Note that in in Bill > B's example, M is two and B is one; he could have used one bit of key > rather than one byte. > > -- > --Bryan Using one bit of key seems to yield only two possible outcomes, the original byte (bit =0) or the inversion of the original (bit =1). What am I missing? -Bill
From: Guy Macon on 14 Nov 2008 05:04 Bill B wrote: > >Bryan Hussein Olson wrote: > >> Bill B wrote: >> >> > Guy Macon <http://www.GuyMacon.com/>wrote: >> > >> >> Bill B wrote: >> >> >> >>> Why does the key need to be random? >> >> >> >> Try it yourself with this 1 byte message: "Y" >> >> [...] >> >> > Now, if Eve knows the answer is "Y" or "N" she has >> > the option of xoring character 0 against the byte "Y" >> > to obtain "Y", or she can use character 23 to obtain >> > "N" >> >> > She basically has the choice of making the text say anything she >> > wants. >> >> > How can she possibly find the real message? >> >> The fact that special-case message spaces show a pattern of redundancy >> that may tolerate corresponding redundancy in the key is not >> particularly interesting. A uniform random key-stream can support >> perfect secrecy in the general case. When we have special-case info >> about the message space, we can often use it to encode more efficiently, >> which is a better tactic than weakening our key-generation requirements. >> >> If Alice and Bob know their message space precisely in advance, say it >> contains M message of non-zero probability, then they can encode any >> message in B = ceiling(lg(M)) bits. They can then achieve prefect >> secrecy using only B bits of (uniform random) key. Note that in in Bill >> B's example, M is two and B is one; he could have used one bit of key >> rather than one byte. > >Using one bit of key seems to yield only two possible outcomes, the >original byte (bit =0) or the inversion of the original (bit =1). > >What am I missing? What he is saying is true, but it is also trivial and thus not particularly interesting. In my made-up example, I specified a one-byte message with the plaintext equal to "Y" and a one byte OTP key. That gives the attacker who tries brute force 256 possible guesses that result in the 256 possible values of that plaintext byte with no way to tell which is correct. He is pointing out that if I limit my possible plaintexts to "Y" or "N", I can encode my plaintext with one bit and then encrypt it using a 1-bit one-time-pad. This leaves the attacker with a really easy brute-force guessing task; guess that the key is a 0, then guess that the key is a 1. And yet, even with a single bit key, a godlike attacker with infinite time, infinite computer power, infitite cleverness and infinite kwoledge with the only exceptions being not knowing the plaintext or the key still can't tell which of the two possible plaintexts I sent. IOW, it is an unbreakable cipher. -- Guy Macon <http://www.GuyMacon.com/>
From: Bryan Hussein Olson on 14 Nov 2008 06:20 Bill B wrote: > On Nov 12, 10:27 pm, Bryan Hussein Olson <fakeaddr...(a)nowhere.org> > wrote: >> Bill B wrote: >>> Guy Macon wrote: >>>> Bill B wrote: >>>>> Why does the key need to be random? >>>> Try it yourself with this 1 byte message: "Y" >> [...] >> >>> Now, if Eve knows the answer is "Y" or "N" she has >>> the option of xoring character 0 against the byte "Y" >>> to obtain "Y", or she can use character 23 to obtain >>> "N" >>> She basically has the choice of making the text say anything she >>> wants. >>> How can she possibly find the real message? >> The fact that special-case message spaces show a pattern of redundancy >> that may tolerate corresponding redundancy in the key is not >> particularly interesting. A uniform random key-stream can support >> perfect secrecy in the general case. When we have special-case info >> about the message space, we can often use it to encode more efficiently, >> which is a better tactic than weakening our key-generation requirements. >> >> If Alice and Bob know their message space precisely in advance, say it >> contains M message of non-zero probability, then they can encode any >> message in B = ceiling(lg(M)) bits. They can then achieve prefect >> secrecy using only B bits of (uniform random) key. Note that in in Bill >> B's example, M is two and B is one; he could have used one bit of key >> rather than one byte. > > Using one bit of key seems to yield only two possible outcomes, the > original byte (bit =0) or the inversion of the original (bit =1). > > What am I missing? What are you missing? Hard to tell from this distance, but I can offer a few notes. *You* specified the case where Eve knows that there are only two possible messages. The issue here is not that a one-bit key will "yield only two possible outcomes"; it is that if there are only two possible outcomes then Alice needs just one random bit of key to achieve perfect secrecy. That bit must be equally likely to be zero versus one. You might also be missing the technical definition of perfect secrecy: the plaintext and ciphertext are independent, in the mathematical, statistical sense. http://en.wikipedia.org/wiki/Statistical_independence Independence implies that the ciphertext is useless to Eve. Any plaintext's probability given the ciphertext is equal to its probability without the ciphertext. The OTP was invented several times, and who first realized its important secrecy propertis is not entirely clear. There is no doubt about who proved the results: http://en.wikipedia.org/wiki/Communication_Theory_of_Secrecy_Systems http://netlab.cs.ucla.edu/wiki/files/shannon1949.pdf Bill B, whatever you are missing, if you read, study, and understand parts I and II of that paper, you will miss it no more. -- --Bryan
From: Bryan Hussein Olson on 14 Nov 2008 06:27 Guy Macon wrote: > What he is saying is true, but it is also trivial and thus not > particularly interesting. Could be... could be. Nevertheless, what I've been saying is no more trivial and no less interesting than anything you, Mr. Macon, wrote in this thread. -- --Bryan
From: Bill B on 14 Nov 2008 23:59
On Nov 14, 3:20 am, Bryan Hussein Olson <fakeaddr...(a)nowhere.org> wrote: > Bill B wrote: > > On Nov 12, 10:27 pm, Bryan Hussein Olson <fakeaddr...(a)nowhere.org> > > wrote: > >> Bill B wrote: > >>> Guy Macon wrote: > >>>> Bill B wrote: > >>>>> Why does the key need to be random? > >>>> Try it yourself with this 1 byte message: "Y" > >> [...] > > >>> Now, if Eve knows the answer is "Y" or "N" she has > >>> the option of xoring character 0 against the byte "Y" > >>> to obtain "Y", or she can use character 23 to obtain > >>> "N" > >>> She basically has the choice of making the text say anything she > >>> wants. > >>> How can she possibly find the real message? > >> The fact that special-case message spaces show a pattern of redundancy > >> that may tolerate corresponding redundancy in the key is not > >> particularly interesting. A uniform random key-stream can support > >> perfect secrecy in the general case. When we have special-case info > >> about the message space, we can often use it to encode more efficiently, > >> which is a better tactic than weakening our key-generation requirements. > > >> If Alice and Bob know their message space precisely in advance, say it > >> contains M message of non-zero probability, then they can encode any > >> message in B = ceiling(lg(M)) bits. They can then achieve prefect > >> secrecy using only B bits of (uniform random) key. Note that in in Bill > >> B's example, M is two and B is one; he could have used one bit of key > >> rather than one byte. > > > Using one bit of key seems to yield only two possible outcomes, the > > original byte (bit =0) or the inversion of the original (bit =1). > > > What am I missing? > > What are you missing? Hard to tell from this distance, but I can offer a > few notes. *You* specified the case where Eve knows that there are only > two possible messages. The issue here is not that a one-bit key will > "yield only two possible outcomes"; it is that if there are only two > possible outcomes then Alice needs just one random bit of key to achieve > perfect secrecy. That bit must be equally likely to be zero versus one. > > You might also be missing the technical definition of perfect secrecy: > the plaintext and ciphertext are independent, in the mathematical, > statistical sense. > > http://en.wikipedia.org/wiki/Statistical_independence > > Independence implies that the ciphertext is useless to Eve. Any > plaintext's probability given the ciphertext is equal to its probability > without the ciphertext. > > The OTP was invented several times, and who first realized its important > secrecy propertis is not entirely clear. There is no doubt about who > proved the results: > > http://en.wikipedia.org/wiki/Communication_Theory_of_Secrecy_Systems > http://netlab.cs.ucla.edu/wiki/files/shannon1949.pdf > > Bill B, whatever you are missing, if you read, study, and understand > parts I and II of that paper, you will miss it no more. > > -- > --Bryan I didn't specify a yes/no answer. I only mentioned that if Eve knew the answer was yes or no, she needed only two bytes of key, and you clarified that to be two bits, which is correct and enlightning. But that leads us to the ridiculous case where a long cyphertext is the same as the plain text except for the misspelling of one word, and no key is needed, not even a 1 or zero. -Bill |