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: David Eather on 12 Nov 2008 10:46 Guy Macon wrote: > Unruh wrote: >> Guy Macon <http://www.GuyMacon.com/> writes: >> >>> 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. >> And then you have to keep track of where in the key you are > > Yes, but doing so isn't difficult, and it isn't all that hard > to search the entire key if you lose your place > > It might be flawed in a way you haven't considered. You said an 8 GB card, so I expect from specification that a 4 GB file would be too small. Many people regard generating a few hundred bits of genuine random data per second to be good going. Lets just call it 128 bytes per second - 1024 bits per second. To generate the 8 GB of random data you suggest will take approximately 2 years, so I hope you are not travelling soon. Also, you will need to hold 2 distinct and separate, one time pads for each person you intended to communicate with - not just one. This is so that you and the other party don't simultaneously transmit a message using the same portion of OTP. So 4 years of generation, assuming that it is perhaps somewhat uncertain as to who will generate and send the most data, and multiply that by every contingency about who you might have to contact. Maybe it is easier just to stay at home or use a conventional PKI and symmetric cipher combination.
From: Bryan Hussein Olson on 12 Nov 2008 15:15 Guy Macon wrote: > He *correctly* argues that the XOR of two random keys is a random key. Not really. The important argument is that the XOR of a random key and something that may or may not be a random key, is a random key (provided that the something and the random key are independent). -- --Bryan
From: Bryan Hussein Olson on 12 Nov 2008 15:35 Guy Macon wrote: > Unruh wrote: >> And then you have to keep track of where in the key you are > > Yes, but doing so isn't difficult, and it isn't all that hard > to search the entire key if you lose your place When receiving a message, the search-the-entire-key tactic should work, but the danger is at the time of sending a message. But Macon is right, tracking what we've used (or erasing it after use) shouldn't be difficult. A simple matter of programming, as they say. -- --Bryan
From: Bryan Hussein Olson on 12 Nov 2008 16:15 David Eather wrote: > Also, you will need to hold 2 distinct and separate, one time pads for > each person you intended to communicate with - not just one. This is so > that you and the other party don't simultaneously transmit a message > using the same portion of OTP. So 4 years of generation, assuming that > it is perhaps somewhat uncertain as to who will generate and send the > most data, and multiply that by every contingency about who you might > have to contact. There's a better way to handle that. Alice takes key bits from the start of the pad, Bob from the end. They define a movable boundary that starts in the middle. If Alice notices that Bob has used a bunch more of the pad than she has, she sends a message granting Bob more of the pad, moving the boundary. They authenticate using Carter-Wegman hashing with OTP encryption, so they are still secure against computationally unbounded attackers. (The boundary protocol has to be a bit more sophisticated, to tolerate undelivered or delayed messages.) > Maybe it is easier just to stay at home or use a conventional PKI and > symmetric cipher combination. You know you're in trouble when PKI is the easy alternative. -- --Bryan
From: Unruh on 12 Nov 2008 16:23
Bryan Hussein Olson <fakeaddress(a)nowhere.org> writes: >Guy Macon wrote: >> He *correctly* argues that the XOR of two random keys is a random key. >Not really. The important argument is that the XOR of a random key and >something that may or may not be a random key, is a random key (provided >that the something and the random key are independent). While what you say is true, what he said was what I reported. He said-- make 6 random keys. Send them via 6 different routes to the other side. The other side xors the 6 together to use as the key. That maeans that if an enemy gets up to 5 of them, the resultant key is still completely unpredictable. That depends CRUCIALY on all 6 being truely random keys. If one of them is not, and the enemy gets all of them but that one, then the resultant key is weak. He then argues that the probability of anyone getting all 6 is low and you are OK. But the probblility of someone getting all 6 is surely far far greater than the probablility of someone guessing a private key for a symmetric cypher, or getting say an AES key via exhaustive search. Ie one is trading a proveably secure cypher with an insecure key transmission mechanism for one which is not provably secure, but far more secure key transmission procedure. I know where I would lay my bets as to security. >-- >--Bryan |