From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt,alt.security,alt.security.pgp,comp.security.pgp.discuss Subject: Re: Bob spills the beans about real cryptography Date: Tue, 25 Nov 1997 20:38:37 GMT Lines: 47 Message-ID: <347b3391.971888@news.io.com> References: <347aec1a.9997385@nntp.ix.netcom.com> <65etku$2ab$1@news.ox.ac.uk> <347b0e35.18728269@nntp.ix.netcom.com> <65f6ab$e44$1@news.ox.ac.uk> On 25 Nov 1997 18:44:27 GMT, in <65f6ab$e44$1@news.ox.ac.uk> in sci.crypt patrick@gryphon.psych.ox.ac.uk (Patrick Juola) wrote: >[...] >*IF* the OTP is used properly (with all the caveats that we know so >well by now), it's unconditionally secure. However, the OTP is a >very difficult system to use properly, and the chance of a catastrophic >key-management failure is too high to neglect in most situations. This is the conventional view, which I now believe is false. The OTP which is "unconditionally secure" is *not* the realized OTP which is used in practice, but instead the *theoretical* OTP which has an ideal random keying source. Since that source does not exist in reality, the "unconditionally secure" OTP also does not exist in reality. There is another level of difference here before we get to a conventional stream cipher, and that is the ever-increasing "entropy" in the output of the physically-random generator used for OTP keying material. But, again, we cannot quantify this, and especially we cannot guarantee it: Should there come a time when the generator produces *less* "entropy" than we expect, and the plaintext has *more* "entropy" than we expect, the plaintext will not be protected: it will "leak" information (even if just a fractional bit). Clearly, any such system could not be *unconditionally* secure, even if *generally* secure in practice. All of this comes before we face the difficulty of generating, transporting, and keeping the keying material in absolute security. Part of the problem here is that the words "one-time" serve to confuse the issue. We *can* attain one-time-ness; we *cannot* attain the theoretical-class randomness which is required by the cipher described by the name "one-time pad." I claim that the "unconditionally secure" OTP is a *theoretical* concept, and its proof is confined to theory. A *realized* "OTP" is *not* really an OTP at all, in that same sense. The seeming advantage of the OTP over all other ciphers is illusion rather than reality. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ The Crypto Glossary: http://www.io.com/~ritter/GLOSSARY.HTM
From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt Subject: Re: ONE TIME PAD? Date: Tue, 25 Nov 1997 22:40:25 GMT Lines: 53 Message-ID: <347b53a7.2307534@news.io.com> References: <3479ae8d.1381598@news.io.com> <64ugau$8a4$1@news.ox.ac.uk> <64uqcq$rs7@newsops.execpc.com> <64v67g$r7i$1@news.ox.ac.u <65egu7$kv1$1@news.ysu.edu> <wtshaw-2511971427260001@207.101.116.48> On Tue, 25 Nov 1997 14:27:26 -0600, in <wtshaw-2511971427260001@207.101.116.48> in sci.crypt wtshaw@itexas.net (W T Shaw) wrote: >In article <65egu7$kv1$1@news.ysu.edu>, an096@yfn.ysu.edu (David A. Scott) >wrote: > >> In a previous article, ritter@io.com (Terry Ritter) says: >> > >> >"It is possible to design *unbreakable ciphers*. To do so, the key >> >must be randomly selected (i.e., each key must have the same chance of >> >being chosen) and used only once. Furthermore, the length of the key >> >must be equal to or greater than the length of the plaintext to be >> >enciphered." While Scott's article has not arrived here yet, I think it important to note that this was not *me* talking; this was me selecting a *quote* from Meyer and Matyas. This quote is their particular view of the one-time pad, and emphasizes the need for randomness. Later quotes showed how central the concept of randomness was to the OTP security proof. I didn't go back to Shannon, because I wanted views of that work which had presumably matured over time. >There is a big difference between absolutely unbreakable and *functionally >unbreakable*. The latter would not necessarily require either of the >above. Meanwhile, other desired characteristics of ciphers could be >included. Now, this is no excuse for accepting bad design, as the primary >goal is to twart the cracker in any system to the extent that he gives >up. If you do that, the system is equivalent to the absolutely >unbreakable one in effect. My point in entering this thread is to take on what I perceive as the fundamental basis for contention: the delusion that a "one-time pad" is mathematically-proven to be absolutely secure, and therefore is better than any other cipher. Once one buys into this delusion, the issues become things like: "Why would anyone use anything *other* than an OTP," "If other ciphers are good, why don't they have proofs like an OTP," "If your favorite cipher is so good, prove it," and "So what if I have to transport an OTP key; once I do, the cipher is unbreakable." Then we go round and round, as we have been. The problem is in the original assumption that a realized OTP *is* a mathematically-proven unbreakable cipher; this is false. Only the *theoretical* OTP is proven unbreakable. And the theoretical OTP is just an *idea*, an unachievable goal. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ The Crypto Glossary: http://www.io.com/~ritter/GLOSSARY.HTM
From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt,alt.security,alt.security.pgp,comp.security.pgp.discuss Subject: Re: Bob spills the beans about real cryptography Date: Wed, 26 Nov 1997 19:56:31 GMT Lines: 91 Message-ID: <347c7e4f.10318738@news.io.com> References: <347aec1a.9997385@nntp.ix.netcom.com> <65etku$2ab$1@news.ox.ac.uk> <347b0e35.18728269@nntp.ix.netcom.com> <65f6ab$e44$1@news.ox.ac.uk> <347b3391.971888@news.io.com> <david-2511971427460001@lax-ca69-58.ix.netcom.com> <wtshaw-2511972153060001@207.101.116.63> On Tue, 25 Nov 1997 21:53:06 -0600, in <wtshaw-2511972153060001@207.101.116.63> in sci.crypt wtshaw@itexas.net (W T Shaw) wrote: >In article <david-2511971427460001@lax-ca69-58.ix.netcom.com>, >david@sternlight.com (David Sternlight) wrote: > >> In article <347b3391.971888@news.io.com>, ritter@io.com (Terry Ritter) wrote: >> >There is another level of difference here before we get to a >> >conventional stream cipher, and that is the ever-increasing "entropy" >> >in the output of the physically-random generator used for OTP keying >> >material >> >> Is there any evidence that a random generator based on cosmic ray impacts >> has any serial weakness? I've never seen any serious proposal for this, and it takes some sort of serious proposal to start to identify problems. Personally, I would expect that any such machine on the surface of the Earth would be somewhat directional, and thus show some sort of daily and perhaps yearly pattern. Further, if we use some sort of Geiger-Muller tube, it necessarily has response and quench time which will hide any other arrival in this same time period. And the data rate is probably low at best. Certainly we expect a Poisson distribution of periods between pulses, which then must be processed into a flat distribution. >The cost David, the cost, remember the cost. Better to measure raindrops >in Florida or weigh sand grains. A detector that might pretend to measure >cosmic ray impacts is measuring byproducts from collisions of cosmic rays >with other particles, and is therefore subject to noise from other >sources.--International Classroom, circa 1959. > >Mere radiation detecting, since particles are emitted from far from >critical masses in relatively random fashion, would make a better choice. David's article not having shown up yet locally, let me just make a few comments that probably will not be very satisfying. In really-random generators, there is a history of people having their favorite noise sources. Some people like thermal noise, some like the emission of sub-atomic particles, others have other ideas. Once having decided on a noise source, there is a history of people doing increasingly deep analyses of the result, often requiring continuing modification or even re-engineering of the noise-sensing machinery. Normally, the author gives us a usable system, but few if any put their system forth as being "provably random." The rain idea (which should be ideal shot noise!) seems attractive, but then we have to wait for rain. If we sprinkle our own, then we probably can't trust the results. I have considered using a sheet of partially-conductive rubber in a rainstorm. The rubber should compress under a raindrop impact, which would deliver a noticeable voltage pulse (when driven by a current). But when we get down to it, aren't there larger and smaller raindrops? And when a large raindrop impacts, does this not splatter new false "raindrops," thus hiding real (small) raindrops? And if we *do* get some large ones, doesn't the mere presence of the added water mass (as it rolls away) now tend to hide small real raindrops? And what about wind, and rain at an angle? And on and on. This same process of analysis proceeds through many different sources of noise and detection processes. Thermal noise has its own problems, and it takes extensive amplification at wide bandwidth and good sampling to attain what seem like good random results. But thermal noise is tiny indeed, and we also get random-like results from structured signals (e.g., music) and digital noise (device switching) and power noise (switching power supply pulses). Yet none of these things actually *is* random, so how can we *prove* that they (or something else) are not present? There are a couple of vignettes about all this on my pages at: http://www.io.com/~ritter/RES/RNGMACH.HTM#McKean87 Also see: http://www.io.com/~ritter/RES/RNGMACH.HTM#Rand55 If anyone knows of any other published accounts of randomness-sensing machinery, please let me know and I will try to include them in my next page update. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ The Crypto Glossary: http://www.io.com/~ritter/GLOSSARY.HTM
From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt,alt.security,alt.security.pgp,comp.security.pgp.discuss Subject: Re: Bob spills the beans about real cryptography Date: Thu, 27 Nov 1997 16:39:36 GMT Lines: 34 Message-ID: <347da215.3074506@news.io.com> References: <347b0e35.18728269@nntp.ix.netcom.com> <65f6ab$e44$1@news.ox.ac.uk> <347b3391.971888@news.io.com> <65gs7u$jjr$1@news.ox.ac.uk> <347C42B1.FF6@medit3d.com> <MPG.ee6d272a579961b989683@news.ccinet.net> On Thu, 27 Nov 1997 00:44:28 -0600, in <MPG.ee6d272a579961b989683@news.ccinet.net> in sci.crypt grizz@the.bears.den (Grizz) wrote: >[...] >I've been reading these arguments about OTP's and randomness for some >time now and you people seem to be missing two important points. First >there is no such thing as true random numbers and second OTP's do not >need true random number sequences to be unconditionally secure. At least for me the issue has not been conditional versus unconditional security, but instead, PROOF of security. The basis for the PROOF of OTP security is the theoretical-class randomness used in a theoretical OTP. So if we want that same proof to apply to a realized OTP, we must PROVE that our real RNG has theoretical-class randomness in practice. But such proof seems impossible. Instead of viewing the crypto landscape as being partitioned between the proven OTP (and friends) versus unproven everything else, we now see that the actual partition is between proven theoretical systems and unproven realized systems of all kinds, including any realized OTP. I find this a more reasonable and more satisfactory view of cryptography. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ The Crypto Glossary: http://www.io.com/~ritter/GLOSSARY.HTM
From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt Subject: Re: ONE TIME PAD? Date: Mon, 01 Dec 1997 19:17:03 GMT Lines: 56 Message-ID: <34830d22.5777581@news.io.com> References: <3473aaa9.54902385@nntp.ix.netcom.com> <wtshaw-2011970015400001@207.101.116.44> <34747e42.16121902@nntp.ix.netcom.com> <6520ko$4b8$1@news.ox.ac.uk> <3474a93f.27126095@nntp.ix.netcom.com> <652dbi$76d@news.microsoft.com> <EK0sxF.5yK.0.sheppard@torfree.net> <3476d8b2.875829@nntp.ix.netcom.com> <wtshaw-2311970126420001@207.101.116.46> <34785b2d.10001110@nntp.ix.netcom.com> <347943D6.167E@medit3d.com> <34798f8b.5552654@nntp.ix.netcom.com> On Mon, 24 Nov 1997 14:38:51 GMT, in <34798f8b.5552654@nntp.ix.netcom.com> in sci.crypt rcktexas@ix.netcom.com (R. Knauer-AIMNET) wrote: >On Mon, 24 Nov 1997 10:07:34 +0100, Colin Dooley <colin@medit3d.com> >wrote: > >>[...] >>The theory (and practice) shows that these "breakable" methods >>are secure enough even for military purposes. Why complicate >>your life with all the problems caused by one time pads? > >Simple - until I see how these systems are provably secure, I will be >forced to fall back on the only 100.000% unbreakable system, the OTP. This seems a simple statement of the fundamental issue in this thread, which of course Bryan Olson has confused in his past few postings. The issue is "PROVABLE security." Clearly, Bob assumes that a realized one time pad *is* provably secure, and that anything else is less. >Can you tell me of a system that in provably secure to 99.999%, and if >so would you trust extremely valuable information with it - like >something that involves your own life? IOW, if the adversary cracks >your code, you are instantly a dead person. The classic information-theoretic proof of security for a one time pad requires theoretical-class perfect randomness. This is probably not achievable, and certainly not provable. We cannot hope to test every possible relationship which might show non-randomness. Any particular relationship can only be measured statistically, and even a 99.999% probability that a relation does not exist is not *proof*. So if we go by the classic proof, the only provably secure one time pad is a *theoretical* one time pad, which is only good for sending theoretical data (or perhaps theoretically sending real data). This proof does not apply to a real system. As soon as the one time pad is used in practice, it becomes a stream cipher with a huge key. Now, perhaps one could take on the particular characteristics of a particular random number machine and show these sufficient for security in practice, which might be some sort of "proof." That would still be better than most systems, but only relevant here if such were actually achieved. The classic proof simply does not apply. The blanket statement that a realized one time pad is "100.000% unbreakable" is just false. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ The Crypto Glossary: http://www.io.com/~ritter/GLOSSARY.HTM
From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt,alt.security,alt.security.pgp,comp.security.pgp.discuss Subject: Re: Bob spills the beans about real cryptography Date: Mon, 01 Dec 1997 18:21:54 GMT Lines: 28 Message-ID: <3483003a.2473022@news.io.com> References: <347b0e35.18728269@nntp.ix.netcom.com> <65f6ab$e44$1@news.ox.ac.uk> <347b3391.971888@news.io.com> <65gs7u$jjr$1@news.ox.ac.uk> <347C42B1.FF6@medit3d.com> <347F1FF0.805F734@munich.netsurf.de> On Fri, 28 Nov 1997 20:48:00 +0100, in <347F1FF0.805F734@munich.netsurf.de> in sci.crypt Joachim Durchholz <joachim.durchholz@munich.netsurf.de> wrote: >[...] >If you want a source of *real* random numbers, take some >quantum-mechanical device. Like some radioactive substance and a Geiger >counter, calibrated so that the probability of an event per (say) >millisecond is 50% (you'd have to take the decrease in radioactivity >into account though). This seems to be a popular suggestion lately. The latest Cryptologia [Oct 1997, 21(4): 351] provides a little more handwaving: The source would be a thorium-impregnated mantle for a Coleman lantern. A commercial PC Geiger Counter would produce a pulse and sample an 8-bit value from a counter running at 1 MHz or better. My guess is that the practical problems would involve the lack of very short periods between pulses, and reducing correlations due to short periods. "Entropy" could be condensed by hashing, which should give very satisfactory practical results, but with no guarantees. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ The Crypto Glossary: http://www.io.com/~ritter/GLOSSARY.HTM
From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt,alt.security,alt.security.pgp,comp.security.pgp.discuss Subject: Re: Bob spills the beans about real cryptography Date: Mon, 01 Dec 1997 18:25:17 GMT Lines: 38 Message-ID: <348300e5.2643978@news.io.com> References: <3471bc2f.11666034@nntp.ix.netcom.com> <3474a68f.26438907@nntp.ix.netcom.com> <654c4h$o77$1@gannett.math.niu.edu> <3475f84b.36668836@nntp.ix.netcom.com> <65cdme$aql$1@gannett.math.niu.edu> <347a396d.49042068@nntp.ix.netcom.com> <3n2it8qjx.fsf@kmac.terisa.com> On 24 Nov 1997 21:56:34 -0800, in <3n2it8qjx.fsf@kmac.terisa.com> in sci.crypt EKR <ekr@terisa.com> wrote: >[...] >Loosely speaking, the probability that a system as a whole will be >compromised is >1-(1-Pcryptosystem)(1-Pusers) > >where >Pcryptosystem=the probability that the system will be compromised through >some inherent weakness (e.g. cryptanalylis, brute force) >Pusers=the probability that the system can be compromised through the >users, e.g. by rubber hose cryptanlysis, key reuse, weak keys, >bribery, etc. > >Now, we know that for the OTP, Pcryptosystem is zero. I.e. >it's unconditionally secure. This is the conventional view, which I now believe is false. The "unconditionally secure" OTP is a *theoretical* entity, which uses a handwaved random generator with assumed perfect theoretical randomness properties. If we realize an OTP for actual use and desire a similar proof of "unconditional security," we must *also* realize a random-number source with guaranteed theoretical-class randomness. We do not have such generators. We do have good sources of really random numbers. But we cannot prove with absolute certainty that they are indeed *perfectly* random. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ The Crypto Glossary: http://www.io.com/~ritter/GLOSSARY.HTM
From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt,alt.security,alt.security.pgp,comp.security.pgp.discuss Subject: Re: Bob spills the beans about real cryptography Date: Mon, 01 Dec 1997 20:13:47 GMT Lines: 129 Message-ID: <34831a40.9136451@news.io.com> References: <3471bc2f.11666034@nntp.ix.netcom.com> <3474a68f.26438907@nntp.ix.netcom.com> <654c4h$o77$1@gannett.math.niu.edu> <3475f84b.36668836@nntp.ix.netcom.com> <65cdme$aql$1@gannett.math.niu.edu> <347a396d.49042068@nntp.ix.netcom.com> <3n2it8qjx.fsf@kmac.terisa.com> <348300e5.2643978@news.io.com> <3lny4hp7c.fsf@kmac.terisa.com> On 01 Dec 1997 10:51:19 -0800, in <3lny4hp7c.fsf@kmac.terisa.com> in sci.crypt EKR <ekr@terisa.com> wrote: >ritter@io.com (Terry Ritter) writes: > >> On 24 Nov 1997 21:56:34 -0800, in <3n2it8qjx.fsf@kmac.terisa.com> in >> sci.crypt EKR <ekr@terisa.com> wrote: >> >> >[...] >> >Loosely speaking, the probability that a system as a whole will be >> >compromised is >> >1-(1-Pcryptosystem)(1-Pusers) >> > >> >where >> >Pcryptosystem=the probability that the system will be compromised through >> >some inherent weakness (e.g. cryptanalylis, brute force) >> >Pusers=the probability that the system can be compromised through the >> >users, e.g. by rubber hose cryptanlysis, key reuse, weak keys, >> >bribery, etc. >> > >> >Now, we know that for the OTP, Pcryptosystem is zero. I.e. >> >it's unconditionally secure. >> >> This is the conventional view, which I now believe is false. >Since my argument was that even in the face of an unconditionally >secure cryptosystem, it was still possible for a conventional >cryptosystem to be stronger as a total system, a fortiori, a >this applies to a non-unconditionally secure OTP. You said: "Pcryptosystem=the probability that the system will be compromised through some inherent weakness," and "for the OTP, Pcryptosystem is zero. I.e. it's unconditionally secure." But no real one time pad has such a proof. And if you are going to argue about imaginary things, it scarcely seems right to claim that *my* argument is "just semantics" (see below). >> The "unconditionally secure" OTP is a *theoretical* entity, which uses >> a handwaved random generator with assumed perfect theoretical >> randomness properties. >> >> If we realize an OTP for actual use and desire a similar proof of >> "unconditional security," we must *also* realize a random-number >> source with guaranteed theoretical-class randomness. We do not have >> such generators. >> >> We do have good sources of really random numbers. But we cannot prove >> with absolute certainty that they are indeed *perfectly* random. >You're just arguing semantics. I disagree. >There's always a theory part and >an implementation part. Theoretically an OTP is secure. It >can be implemented insecurely. The reality is much worse than this. In fact, an OTP *cannot* be implemented with *proven* security. >Due to the limitations of >the physical world, it cannot be implemented completely securely. Anything can be implemented poorly. The problem is that, even when implemented as well as possible, the realized one time pad *still* does not have the theoretical property which is ascribed to it, or at least we cannot prove it does. Such proof is the whole basis for this conversation. >Conventional cryptosystems aren't even perfectly secure >in theory, though. This is not universal. In fact, it has gotten disturbingly popular to write articles which claim *proven* security, when in fact that security is based on unattainable theoretic components. However, even if a conventional cryptosystem *did* have a theoretical analog which was proven perfectly secure, if that proof did not apply to the real system, the proof would be totally irrelevant as support for any idea that the real cryptosystem was better than any other. >This isn't that important since the practical >considerations of using an OTP are so different from those with >a conventional cryptosystem. The issue to the newbies we see here every month or so is PROVABLE security in a REAL system. But since the security proof for one time pads does not survive the transition from theory to reality, their whole argument has a false basis. The cryptographic community bears some amount of blame for this by not making the issue clear from the outset. The *theoretical* quality of the proven secure one time pad is something which should be in every text, but, alas, is not. >But, imagine two systems which were similar in usage, but whereas >one was provably secure (to some level) and the other wasn't. >For instance, imagine we knew factoring was hard, then a >system like RSA which was provably as hard as factoring would >be superior to RSA (which hasn't been proved to be as hard >as factoring) provided that they could be used in similar ways. First, Bob has not been arguing this. Next, in this example we do *not* have a system which is proven secure in theory, as would correspond to the theoretical one time pad. Last, proof is proof. A proven-in-theory system is fine as long as we use it for sending theoretical data. But if the proof does not survive the transition to a real system, it is no proof at all for that system. A proof which does not apply is a just a delusion; it has absolutely no relevance. It does *not* give us any confidence in the real system. There is *no* advantage to using a real one time pad based on the proof of absolute security in a theoretical one time pad. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ The Crypto Glossary: http://www.io.com/~ritter/GLOSSARY.HTM
From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt,alt.security,alt.security.pgp,comp.security.pgp.discuss Subject: Re: Bob spills the beans about real cryptography Date: Tue, 02 Dec 1997 04:45:06 GMT Lines: 110 Message-ID: <34839228.2906161@news.io.com> References: <3471bc2f.11666034@nntp.ix.netcom.com> <3474a68f.26438907@nntp.ix.netcom.com> <654c4h$o77$1@gannett.math.niu.edu> <3475f84b.36668836@nntp.ix.netcom.com> <65cdme$aql$1@gannett.math.niu.edu> <347a396d.49042068@nntp.ix.netcom.com> <3n2it8qjx.fsf@kmac.terisa.com> <348300e5.2643978@news.io.com> <34830e17.20494489@nntp.ix.netcom.com> On Mon, 01 Dec 1997 20:15:22 GMT, in <34830e17.20494489@nntp.ix.netcom.com> in sci.crypt rcktexas@ix.netcom.com (R. Knauer-AIMNET) wrote: >On Mon, 01 Dec 1997 18:25:17 GMT, ritter@io.com (Terry Ritter) wrote: > >>This is the conventional view, which I now believe is false. > >Each time I begin to think we have these OTP/randomness issues under >control, another problem pops up. > >>The "unconditionally secure" OTP is a *theoretical* entity, which uses >>a handwaved random generator with assumed perfect theoretical >>randomness properties. > >Please give us your definition of "perfect theoretical randomness". Nope. This is not my definition to give. Perfect randomness is constructed by a mathematical handwave in the proof that the theoretical one time pad is absolutely secure. I previously gave several of those proof descriptions. None quantified what randomness was. This is theoretical math: they don't have to say what randomness is; they just imply what it is not. If someone says "I can predict thus and so" they just say, "Nope, the sequence is absolutely random and not predictable," and that is that. >I have been working on the basis that "perfect theoretical randomness >for purposes of crypto" is that the next bit in the random stream is >not predictable with a probability significantly greater than 1/2. >Granted that is not as stringent as "perfect theoretical randomness" >in general, but it is my understanding that it is both necessary and >sufficient for the purposes of cryptography. This *is* a stringent requirement. It is my understanding that this means that, given knowledge of *all* previous bits, using *every* possible test, the next bit *still* cannot be predicted better than chance. This is another theoretical math handwave definition. It describes a result, rather than a way to get that result. It cannot be verified by testing, because it is impossible to enumerate every possible test so each can be checked. The usual mathematical approach (I believe) is to prove that if one could make such a prediction in the context of the defined system, then one could also solve some hard problem. But I don't think this is your approach. >>If we realize an OTP for actual use and desire a similar proof of >>"unconditional security," we must *also* realize a random-number >>source with . We do not have such generators. > >Not knowing your definition of "guaranteed theoretical-class >randomness" I cannot comment whether such RNGs exist or not. I would >argue that crypto-grade RNGs can be achieved in QM. There is little argument that good randomness exists at the quantum level, regardless of whether it is fundamental or the complex result of hidden variables. That randomness probably will not have the desirable flat distribution we would like, however, and so must be processed even in the best possible case. But to use quantum randomness it must be detected, and this normally requires some sensitive device which is an imperfect human construct. For example, a Geiger-Muller tube takes some time to avalanche, and much longer to clear out. Events in that period are lost. So not only do we lose short-period events, but it also not possible to know the precise time between the lost event and the next event, which is the theoretical random value we want. There are no doubt other deviations to handle. I know of no way to perfectly sense quantum events. No doubt we would want to hash what randomness we detect. But doing this is both beneficial and dangerous. It is beneficial because it tends to "concentrate" randomness within the hash value, which is what we want. It is dangerous because even non-random inputs look random when hashed. This means that faulty detection could result in predictable values which still look random on the surface. >>We do have good sources of really random numbers. > >The criterion above for crypto-grade randomness does not require >perfection, just "significantly greater than 1/2". But 0.5 *is* perfection. To the extent that any delta above that can be detected, only perfection counts. It is hard to imagine that there possibly can be a delta value below which we have (proven) security in practice. If you are pinning your hopes on "significantly," I doubt it was meant to be taken that way. >>But we cannot prove >>with absolute certainty that they are indeed *perfectly* random. > >Can we prove with some measurable certainty that they are >*cryptographically* random? If you mean by "cryptographically random" the phrase "cannot predict the next bit with probability greater than 0.5," my guess would be that any such generator would be difficult to produce, and impossible to prove. It might work, and you might think it works, but you could never know for sure. Which is right back where we were, of course. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ The Crypto Glossary: http://www.io.com/~ritter/GLOSSARY.HTM
From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt Subject: Re: ONE TIME PAD? Date: Tue, 02 Dec 1997 01:32:26 GMT Lines: 102 Message-ID: <34835f43.4158034@news.io.com> References: <3473aaa9.54902385@nntp.ix.netcom.com> <wtshaw-2011970015400001@207.101.116.44> <34747e42.16121902@nntp.ix.netcom.com> <6520ko$4b8$1@news.ox.ac.uk> <3474a93f.27126095@nntp.ix.netcom.com> <652dbi$76d@news.microsoft.com> <EK0sxF.5yK.0.sheppard@torfree.net> <3476d8b2.875829@nntp.ix.netcom.com> <wtshaw-2311970126420001@207.101.116.46> <34785b2d.10001110@nntp.ix.netcom.com> <347943D6.167E@medit3d.com> <34798f8b.5552654@nntp.ix.netcom.com> <34830d22.5777581@news.io.com> <34832b72.28009795@nntp.ix.netcom.com> On Mon, 01 Dec 1997 21:34:27 GMT, in <34832b72.28009795@nntp.ix.netcom.com> in sci.crypt rcktexas@ix.netcom.com (R. Knauer-AIMNET) wrote: >On Mon, 01 Dec 1997 19:17:03 GMT, ritter@io.com (Terry Ritter) wrote: > >>The classic proof simply does not apply. The blanket statement that a >>realized one time pad is "100.000% unbreakable" is just false. > >To use your terminology, I meant theoretically unbreakable. > >I, like you, have doubts about "practical randomness" in the classical >realm, even with physical systems, because we cannot certify that the >output stream is "practically random", even for crypto. My position is that we cannot certify that any stream is *perfectly* random, as required for the usual OTP proof. This places the realized OTP back in the body of all realized ciphers, instead of making it a special case. On the other hand, I would think that it *should* be possible to in some sense "certify" that a random stream "seems like" it ought to be random *enough* for practical use. This is just no *proof*. >I would like to believe, however, that there are certain kinds of >randomness that will suffice for crypto, albeit not with 100.000% >certainty. Once we give up the holy grail of absolute certainty, we can then begin to discuss practical cryptography in general, and stream ciphers in particular. But this idea of "percentage of certainty" is strange. It would seem to me that the only way to get such a value is to know more than we can possibly know. Nor would "percentage of randomness" be better, for if there were some maximally-random stream, we could just send that, or easily correct any stream we produce. But this conflicts with the idea of unpredictability. The usual approach to describing cipher strength is to build a cipher which contains within it multiple puzzles, each having independent strength, but which cannot be solved independently. We collect every approach we can think of to start such solutions, and estimate the effort required in each case. We then report the minimum effort as the cipher strength. This of course depends upon seeing an appropriate attack, and evaluating it properly, which are both major problems in cryptography. I have no doubt that this whole process may seem an incredible way to support the main feature which cryptography should provide -- strength -- but there it is. Since the ultimate source of strength in a realized OTP is the really random generator, any analysis of the system must be heavily involved with the specific design and analysis of the actual generator itself. We cannot handwave our way out of defining that before we analyze it. >If I were to build a classical H/W RNG that put out what I >believed to be a random stream - one that you could not predict the >next bit with a probability significantly greater that 1/2 - would >that not qualify as an "almost perfectly" random OTP? I suppose that is a good definition, but we must understand that this does not mean that only do analysis at bit level, or just think about the next bit. Quite often really random RNG's will have some amount of correlation between local bits. And there may well be circumstances where correlation would be conditional on prior values or even sequences. It is also quite common in noise-based equipment that extraneous electronic noise (e.g., repetitive pulses from a switching supply) could be interpreted by the equipment as real noise and so produce correlations with widely-spaced bits. And if the fundamental basis for collecting values is bytes (words, etc.) instead of bits, then a bit-level analysis may not find correlations which naturally exist. >If not, what attack would you implement to decrypt my ciphertext if I >used it? Just because we cannot use the information-theoretic proof of security on a realized OTP does not mean that we now have a new attack: A realized one time pad may well be secure in practice. But, in this still theoretical context, the cryptanalyst would "simply" *find* some relationship in the sequence, and then use that to acquire some amount of information from the ciphertext. In practice, a properly used real one time pad with an extensively analyzed (and post-processed!) really random generator is likely to be very secure. So the real issues in practice are those which have more risk, the issues of assuring proper use, and guaranteeing the security of the pad itself. Which is what everybody was basically getting at before I dropped in. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ The Crypto Glossary: http://www.io.com/~ritter/GLOSSARY.HTM
From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt Subject: Re: Real Random Number Generator Algorithm Publication Date: Tue, 16 Dec 1997 21:34:09 GMT Lines: 34 Message-ID: <3496f37b.1914332@news.io.com> References: <01bd0023$5eb3d0e0$c901a8c0@comm> <3485E90C.124F@helsbreth.org> <348603a1.43586684@nntp.ix.netcom.com> <EKqHAo.69G.0.sheppard@torfree.net> <3488b2d3.18863924@nntp.ix.netcom.com> <348D9411.60842FCE@stud.uni-muenchen.de> <348da790.28113815@nntp.ix.netcom.com> <348E0262.41C6@medit3d.com> <348ea4c1.5211103@nntp.ix.netcom.com> <1997121203112074952@zetnet.co.uk> <34913aa2.5163344@nntp.ix.netcom.com> <1997121400380274952@zetnet.co.uk> <3493ed9b.5440753@nntp.ix.netcom.com> <wtshaw-1612971423480001@207.101.116.61> On Tue, 16 Dec 1997 14:23:33 -0600, in <wtshaw-1612971423480001@207.101.116.61> in sci.crypt wtshaw@itexas.net (W T Shaw) wrote: >In article <3493ed9b.5440753@nntp.ix.netcom.com>, rcktexas@ix.netcom.com wrote: >>[...] >> >I should also have mentioned that OTPs don't provide any protection against >> >message modification attacks, >> >> I simply do not see that - please elaborate. > >Say you send the same message to three people, with three pads, differing >only slightly. Learn the contents of one and solve all the pads, and hope >the sender is dumb enough to reuse a pad. Perhaps a better example would be in sending the same message to two people, using two pads. The Opponents intercept one (as ciphertext) and hold it, then penetrate physical security of the recipient of the other message to get the plaintext. Since they assume or know the same message was sent in both instances, they now know the plaintext of the first message, and also the content of the first pad, even though that has neither been "attacked" nor physically exposed. Then The Opponents can *change* the content of the intercepted message to read as they want, encipher it under the one-time pad they now know, and send it along, to produce the results they want. Nobody will question that message, since everyone knows that a one-time pad system is absolutely secure beyond any possible question. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ The Crypto Glossary: http://www.io.com/~ritter/GLOSSARY.HTM
Terry Ritter, his current address, and his top page.
Last updated: 1998-01-16