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: Unruh on 13 Nov 2008 00:26 Guy Macon <http://www.GuyMacon.com/> writes: >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. This reminds me of the Drake equation. Mutiply a bunch of totally unknown probabilities together and then declare the answer as cast in stone and correct.("I have no idea what the probability of life arising on a planet the same temperature distance from a star as the earth is, so because I have no idea, that probablilty must be about 1/2--- OOOh look how probably life on other planets is ") I would estimate the probability of getting each key for a determined attacker as 1/10 not 1/1000000. What does that do to your estimate? >>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. Sure. It would make the total probability essentially the chance of breaking the public key cypher. So why not send the message that way?
From: David Eather on 13 Nov 2008 00:32 Guy Macon wrote: > 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. > > So, 24hrs for everyone you intend to communicate with (using Brian's suggestion for more efficient OTP use). Plus the time for all the couriers etc. With the OTP split into many shares there is also the growing risk that one of the shares will not be delivered, making the OTP useless. That all seems a lot of work and risk, compared to exchanging a public key and using a symmetric cipher.
From: Bryan Hussein Olson on 13 Nov 2008 01:27 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
From: Bryan Hussein Olson on 13 Nov 2008 02:54 David Eather wrote: > Guy Macon wrote: [...] >> 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. >> > So, 24hrs for everyone you intend to communicate with (using Brian's > suggestion for more efficient OTP use). Plus the time for all the > couriers etc. With the OTP split into many shares there is also the > growing risk that one of the shares will not be delivered, making the > OTP useless. So how about this: I run the key generator as a background daemon and maintain a pool of several dozen GB of randomness. When I need gigabytes of key to share, I'm ready immediately, a few times over. I can keep up a one-new-party-per-day average long term. That's practical. My courier would usually be I. I've worked projects where early on, the participants all met and exchanged PGP keys. We could about as easily have exchanged OTP keys big enough to finish the project without sharing more. If we use carriers and couriers to send key shares, that does not necessarily mean we have to accept that any one failure of delivery makes our OTP useless. We could use a threshold scheme. With a 5-of-6 scheme, we can establish the shared key if any five of the six shares get through, while the attacker would have to intercept five of six (without detection). > That all seems a lot of work and risk, compared to exchanging a public > key and using a symmetric cipher. Most of that work and risk we could automate away. The reason PK systems are practical is that a whole lot of people have done a whole lot of work on them -- and frankly, even so, most of them are not all that practical. The reason OTP systems are not practical is partly the intrinsic disadvantages, but largely that no one in the public sphere has implemented and OTP competently. That said, I'm here arguing a position I do not actually espouse. (I don't actually talk like that predicate nominative at the start of my second paragraph either.) Our important challenge today is to get basically competent crypto built into the systems people actually use. Nevertheless, I think building a competent OTP implementation would be a worthwhile project, a vastly better investment than most of the wastes of time we see here. -- --Bryan
From: Guy Macon on 13 Nov 2008 04:32
Bill B wrote: >Flipping coins seems a waste of time When encouraging someone who does not understand OTP to try it himself with a 1-byte text and a 1-byte key, I want him to do everything exactly as he would with a larger text and key. Any variation (such as skipping the part about making the key using a HRNG) will leave a nagging doubt in his mind about the validity of his findings. -- Guy Macon <http://www.GuyMacon.com/> |