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: Bryan Hussein Olson on 11 Nov 2008 03:45 Gordon Burditt wrote: >>> You are right, if the key is truly random, never reused, and kept >> secret, the one-time pad provides perfect secrecy otherwise very simple >> attack can render it useless. >>> You may readhttp://en.wikipedia.org/wiki/One-time_pad. >>> >>> But, it is not very convenient to use in practice. >>> >>> regards, >>> Jyoti >> Why does the key need to be random? >> Why not set up a key that decodes the text in some >> different meaning so the attacker thinks he found >> the solution, but was totally wrong? > > Using a random key means that all possible plaintext messages of > the same length are equally likely. There's a key for not just > *one* incorrect decoding, there's a key for *all possible* incorrect > decodings of the same length. Bravo! The O.P.'s question here is, in my estimation, the single most frequently asked question here on sci.crypt. Today there are more know-nothings posting on s.c. than ever before, but that detraction is more than offset by increase in participants who take cryptology seriously, and respond with real answers. Bravo! I have one nit to pick: it's not that all ciphertexts are equally likely; it's that thier probabilities do not change when given the OTP ciphertext. Perfect secrecy means that the ciphertext and plaintext are independent, in the mathematical, statistical, probabilistic sense. > If there's any structure to the key, then that can be used to decide > that some of the incorrect decodings are wrong because the corresponding > key is unlikely or impossible. Sure. "One time pad" is a technical term, a 'term of art'. It implies, by definition, that the key-stream is truely random -- all possible key-streams are equally likely. That, along with some trivial mechanics and some subtle issues such as length (which Gordon Burditt nailed), implies perfect secrecy. For more, check out the foundation paper: Shannon, Claude; "Communication Theory of Secrecy Systems", Bell System Technical Journal, vol.28(4), page 656�715, 1949. When I was young in cryptology, looking up that paper was a significant effort. Today it's a few minutes of Googling; no excuses. -- --Bryan
From: Unruh on 11 Nov 2008 11:31 Bill B <wrongaddress(a)att.net> writes: >Encoding data using the XOR function against a "one time pad" of the >same or longer length of the file seems to yield an unbreakable cypher >message since there is more than one solution using different keys. >For example, the message "The quick brown fox" can be encoded by >XORing each character against a key of say >"abcdefghijklmnopqrstuvwxyz" producing a cyphertext message of decimal >characters '"53,10,6,68,20,19,14,11,2,74,9,30,2,25,1,80,23,29,11" >Decoding this message using the original key produces the >original message of "The quick brown fox" >However, if the cyphertext is XORed against a different set of decimal >key characters of say; >"97,98,99,100,120,114,116,114,34,56,108,122,34,125,110,55,55,61,43, >116,117,118,119,120,121,122" the output will be: >"The lazy red dog" >So, it appears that using a one time pad (single use of key) >will yield an unbreakable code, since there are many solutions >to the problem. In other words, using the appropriate key will produce >whatever results are desired and the original message can never be >found without knowing the correct key. >Have I missed something? Had you looked up "One Time Pad' you would have found a description equivalent to what you state. And a proof of its security essentially the same as yours.s. You would also have found out why it is problematic-- that key can NEVER EVER be reused for anything which means that you have to somehow securely exchange a key larger than any message or set of messages you will ever transmit. >-Bill
From: Unruh on 11 Nov 2008 11:36 Bill B <wrongaddress(a)att.net> writes: >On Nov 10, 10:50 pm, "Jyoti Sharma" <jyoti.mic...(a)gmail.com> wrote: >> On Tue, 11 Nov 2008 12:06:20 +0530, Bill B <wrongaddr...(a)att.net> wrote: >> > Encoding data using the XOR function against a "one time pad" of the >> > same or longer length of the file seems to yield an unbreakable cypher >> > message since there is more than one solution using different keys. >> >> You are right, if the key is truly random, never reused, and kept secret, the one-time pad provides perfect secrecy otherwise very simple attack can render it useless. >> >> You may readhttp://en.wikipedia.org/wiki/One-time_pad. >> >> But, it is not very convenient to use in practice. >> >> regards, >> Jyoti >Why does the key need to be random? Because if it is not random, the attacker has information which can be used to decode. >Why not set up a key that decodes the text in some >different meaning so the attacker thinks he found >the solution, but was totally wrong? Because you must assme that the attacker has somehow gotten some part of the message ( eg through spying, rubberhose crypto,...) and is tryng to get another part of it. He will from what he knows realise that "the key is set up that decodes the test in some different manner", and then can use the non-randomness to read the rest of the message. The requirement of crypto is that assuming the attacker has not only the encrypted text but also all of the plain text for all messages in the past-- the crypto must protect future messages even under that assumption.
From: Guy Macon on 11 Nov 2008 12:14 Bill B wrote: >Why does the key need to be random? >Why not set up a key that decodes the text in some >different meaning so the attacker thinks he found >the solution, but was totally wrong? Try it yourself with this 1 byte message: "Y" Generate a 1 byte key by flipping a coin 8 times. Ecrypt using Windows calculator (scientific mode has XOR). Set up a scenario as follows. Alice knows the random key and the plaintext message. Have her encrypt it as described above and send the resulting ciphertext to Bob. Bob knows only the random key. have him decrypt it as described above. He should see the "Y" plaintext. Eve doesn't know the key. She intercepts the ciphertext. Have Eve try all 256 possible 8-bit keys. Post anything interesting that you notice about the list of 256 possible plaintexts here in sci.crypt. Now try it with your "key that decodes the text in some different meaning so the attacker thinks he found the solution, but was totally wrong". Make it so that the wrong answer is "N". Go through the snenario again, with Eve knowing one additional thing -- she knows that the key was chosen with your "key that decodes the text in some different meaning so the attacker thinks he found the solution, but was totally wrong" method. Did Eve's job get any easier or harder? Seriously; sit down and try it yourself with one byte. You will learn a lot, and everything you learn will apply to a longer key/message -- it will just take a lot longer to do (too long to do it by hand). Please post what you learned and any questions you have along the way. Advanced study: Eve knows the plaintext and the ciphertext. Can she figure out the key? Same as above with a new plaintext that Eve doen't know and a new key. Can Eve figure out the plaintext or the key? Now let Eve *choose* the first plaintext instad of just knowing it. Next, let Eve not only choose the plaintext, but let her also modify the ciphertext instead of just reading it. Finally, re-use the key instead of making a new one with new coin flips every time. (a big no-no). Can Eve figure out the plaintext or the key? Post what you learned and any questions you have along the way. -- Guy Macon <http://www.GuyMacon.com/>
From: Guy Macon on 11 Nov 2008 13:20
Unruh wrote: >Had you [Bill B] looked up "One Time Pad' you would have found >a description equivalent to what you state. And a proof of its >security essentially the same as yours.s. You would also have >found out why it is problematic-- that key can NEVER EVER be >reused for anything which means that you have to somehow securely >exchange a key larger than any message or set of messages you >will ever transmit. Other than the difficulty of exchanging any key of any size, the days when exchanging a key larger than any message or set of messages you will ever transmit was extra-difficult are long gone. An 8GB micro-SD card is 11mm x 15mm x 1mm, (0.43" X 0.59" X 0.039") and costs about $20 USD. I also don't consider it to be all that difficult to exchange the keys. Here is one way: Prepare six 256GB random keys using different kinds of HRNGs running on seperate PCs. Store 3 of them on USB thumb drives. Send the three thumb drives by Fedex, UPS, and US Mail using different names and addresses at the source city and destination city. Send the other three files over the internet from different computers and different ISPs using email, FTP and BitTorrent. At both ends, XOR the six files together to create matching 265GB keys. Not very difficult, and it would very very hard to intercept all six files; miss one and you have zero chance of breaking the OTP. If you are the CIA or DOD or a bank that will be using the keys for billion-dollar transactions, send another 3 files by seperate trusted couriers. The difficulty of sending a single keyfile is overblown. I do agree, however, that trying to send a different keyfile to each of a couple of hundred people would be difficult to manage, and doing so in advance of knowing who the recipients are is impossible. That being said, I don't see any real need to upgrade from "takes longer than the age of the universe using a computer the size of the universe to break" to "cannot be broken even with infinite time and infinite computer resources." -- Guy Macon <http://www.GuyMacon.com/> |