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: Guy Macon on 12 Nov 2008 16:53 David Eather wrote: >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. Actually, I picked that size because it's the largest that is available in the Micro-SD form factor. If you need less, buy a smaller/cheaper card. If you need more, carry multiple cards or go to a USB drive - those go up to a terabyte. >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. A quick Google search finds much faster HRNGs... Hotbits gets 100 bytes/second from a $329 detector -- about what you estimate above. http://www.fourmilab.ch/hotbits/hardware3.html Here is a low-cost HRNG that does with a 9600 BPS (1 KByte/second) RS232 output: http://www.cryogenius.com/hardware/rng/ The VIA PadLock Security Engine does over 100 KBytes/second: http://www.via.com.tw/en/initiatives/padlock/hardware.jsp http://www.via.com.tw/en/downloads/whitepapers/initiatives/padlock/evaluation_padlock_rng.pdf Here is an expensive HRNG that does 160 MBytes/second: http://true-random.com/ Another HRNG that does 262 KBytes/second: http://www.protego.se/sg200_d.htm http://www.protego.se/sg200_i1.htm Picking one from the middle of the speed range. The VIA PadLock Security Engine will generate a gigabyte in under three hours, and is cheap enough that buying ten or a hundred of them is feasible. -- Guy Macon <http://www.GuyMacon.com/>
From: Guy Macon on 12 Nov 2008 18:06 Unruh wrote: >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. Hmmm. Is it really? Let's assume a 1 in a million chance of getting each key. That's 6 times 20 bits, or 120 bits. Not too far from the AES-128 keysize. Even if we assume a one in 16,384 chance for each, the more-secure 9-key scheme that I discussed in the same post would be 9 times 14 bits -- 126 bits. >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. I would make the same bet, but the above is an argument against all shared secret ciphers -- they all need a key transmission mechanism -- so we would both be laying bets on public key ciphers. As for the "far more secure", Given the basic scheme of sending multiple OTP keys and XORing them at the end, sending at least one of the keys using public key encryption would make the key distribution mechanism at least as secure as simply using public key encryption would be, and certainly would make the chances of an attacker getting that key far lower that the one in a million used in the above calculation. -- Guy Macon <http://www.GuyMacon.com/>
From: rossum on 12 Nov 2008 18:07 On Wed, 12 Nov 2008 12:35:08 -0800, Bryan Hussein Olson <fakeaddress(a)nowhere.org> wrote: >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. Not so I'm afraid, unless you are using an operating system specifically designed to be secure. With most operating systems you have no control over whether or not parts of your program (such as the key or the plaintext) are written to swap disk and are potentially recoverable by an attacker at a later stage. Securely erasing something is not a trivial problem. It is not really practical to melt down all you hard drives (or dissolve them in acid) when exiting your program. rossum
From: Bryan Hussein Olson on 12 Nov 2008 18:26 rossum wrote: > Bryan Hussein Olson wrote: > >> 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. > Not so I'm afraid, unless you are using an operating system > specifically designed to be secure. With most operating systems you > have no control over whether or not parts of your program (such as the > key or the plaintext) are written to swap disk and are potentially > recoverable by an attacker at a later stage. That's a possible threat to any cryptosystem. The issue here is making sure the sender does not re-use section of key-stream, and that's a SMOP. -- --Bryan
From: Bill B on 12 Nov 2008 22:38
On Nov 11, 9:14 am, Guy Macon <http://www.GuyMacon.com/> wrote: > 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/> Flipping coins seems a waste of time since any single byte character will be random. Let's use an easy single byte key of character zero so the cypherbyte is the same as the plaintext byte "Y" = "Y" . Alice does her thing and sends the "Y" byte to Bob. Bob knows the key is "0" and discovers the message is "Y" Eve, evesdrops and obtains the cypherbyte "Y" and xors "Y" against all 256 possible characters and arrives at 256 answers, which proves nothing, unless she confines it to letters of the alphabet, in which case only 52 will be correct, again proving nothing. 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? -Bill |