Everybody has a sound card, so we all have a physically-random noise generator -- a source of absolute randomness -- right? A discussion starting with sound cards recording noise, and ending with theories of randomness.
Subject: Re: Random numbers from a sound card? Date: Mon, 25 Jan 1999 20:11:33 +0100 From: Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de> Message-ID: <36ACC1E5.90C4C2BC@stud.uni-muenchen.de> References: <36acb8b1.5374650@news.willapabay.org> Newsgroups: sci.crypt Lines: 15 David Ross wrote: > > How would you test the 'quality' of the generated random number > stream? There are tests for statistical quality, e.g. Maurer's universal statistical test. I am ignorant of tests for crypto quality. I guess the issue of cryptological strength is inherently fuzzy and not entirely separable from subjectivity and concepts like confidence intervals, i.e. no security can be claimed on an absolute scale in practice. But experts might refute my un-knowledgeable assertions. M. K. Shen
Subject: Re: Random numbers from a sound card? Date: Mon, 25 Jan 1999 21:21:09 GMT From: phr@netcom.com (Paul Rubin) Message-ID: <phrF64wn9.J9M@netcom.com> References: <36acb8b1.5374650@news.willapabay.org> Newsgroups: sci.crypt Lines: 20 In article <36acb8b1.5374650@news.willapabay.org>, David Ross <ross@hypertools.com> wrote: > Has anyone had success using a sound card (like a Sound Blaster) to >generate streams of random numbers? Yes, see http://www.lila.com/nautilus/index.html and download the source from one of the sites mentioned there. > What sort of audio source would you suspect would be the best to use >in generating random numbers? We ask the user to blow into the microphone to make noise, IIRC. > How would you test the 'quality' of the generated random number >stream? We just test the total amount of energy in the audio to make sure the mic isn't dead. We expect that the raw audio will have lots of correlation, so we run it through a hash function or block cipher; I don't remember the details.
Subject: Re: Random numbers from a sound card? Date: Tue, 26 Jan 1999 07:09:28 +0800 From: Nathan Kennedy <blaaf@hempseed.com> Message-ID: <36ACF9A8.CF6CF898@hempseed.com> References: <36acb8b1.5374650@news.willapabay.org> Newsgroups: sci.crypt Lines: 32 David Ross wrote: > > Has anyone had success using a sound card (like a Sound Blaster) to > generate streams of random numbers? Sure. My favorite (T)RNG method. > > What sort of audio source would you suspect would be the best to use > in generating random numbers? I tune a cheap AM radio to a loud static channel, and wire that into the mic port. > How would you test the 'quality' of the generated random number > stream? Of course, you can't test the 'quality' by looking at the random numbers generated. You need to estimate the entropy of your source, and of course it's always going to be an estimate, you can almost never prove it. What I did, was compress it, multiply my hash size by the compression ratio by a fudge factor of 10. Then I would hash that much data, and assumed that the result was very close to 100% entropy. This is rather paranoid and slow though. If you don't need 100% entropy just go ahead and continually sample /dev/audio for data and use it as entropy for a PRNG, and sample the PRNG as often as you like. The quality should still be excellent... As long as you've got >128 bits of entropy total and the PRNG does its job, the result should be quite secure as long as nothing gets compromised. Nate
Subject: Re: Random numbers from a sound card? Date: Tue, 26 Jan 1999 09:41:42 +0100 From: Cuykens Anthony <cuykens.a@protonworld.com> Message-ID: <36AD7FC6.674ABAEC@protonworld.com> References: <36ACF9A8.CF6CF898@hempseed.com> Newsgroups: sci.crypt Lines: 53 Hi, I do remember of a way a teacher told me to generate a "true" random generator. You select some measurable information about your noise source (in your case, lets says the frequence, the loudness, ...). Then you sample you source at fixed interval and you check all your informations. For each coosen information, if it is higher than the same info at the last sample, the output is one, otherwize the result is zero. At each sample, this method will give you one bit per criterion. This is just an idea, what does guru think of it? Nathan Kennedy wrote: > David Ross wrote: > > > > Has anyone had success using a sound card (like a Sound Blaster) to > > generate streams of random numbers? > > Sure. My favorite (T)RNG method. > > > > > What sort of audio source would you suspect would be the best to use > > in generating random numbers? > > I tune a cheap AM radio to a loud static channel, and wire that into the > mic port. > > > How would you test the 'quality' of the generated random number > > stream? > > Of course, you can't test the 'quality' by looking at the random numbers > generated. You need to estimate the entropy of your source, and of course > it's always going to be an estimate, you can almost never prove it. > > What I did, was compress it, multiply my hash size by the compression ratio > by a fudge factor of 10. Then I would hash that much data, and assumed > that the result was very close to 100% entropy. This is rather paranoid > and slow though. If you don't need 100% entropy just go ahead and > continually sample /dev/audio for data and use it as entropy for a PRNG, > and sample the PRNG as often as you like. The quality should still be > excellent... As long as you've got >128 bits of entropy total and the PRNG > does its job, the result should be quite secure as long as nothing gets > compromised. > > Nate -- Anthony Cuykens
Subject: Re: Random numbers from a sound card? Date: 26 Jan 1999 10:18:04 +0100 From: Jon Haugsand <haugsand@procyon.nr.no> Message-ID: <yzo90eqv1df.fsf@procyon.nr.no> References: <36AD7FC6.674ABAEC@protonworld.com> Newsgroups: sci.crypt Lines: 26 * Cuykens Anthony | I do remember of a way a teacher told me to generate a "true" random | generator. You select some measurable information about your noise source (in | your case, lets says the frequence, the loudness, ...). Then you sample you | source at fixed interval and you check all your informations. For each coosen | information, if it is higher than the same info at the last sample, the output | is one, otherwize the result is zero. At each sample, this method will give you | one bit per criterion. I am not sure that this will be random enough. I would guess that as the number of concectutive ones increases, the probability to get a zero the next time also increases. Better is to make two samples not too close in time and output a one if the first is higher, and output a zero if the second is higher. Better still is to measure some quantity twice (e.g. sound level) and use the least significant bit and output a one if you measure 10, output a zero if you get 01. If you get 11 or 00, discard those. -- Jon Haugsand Norwegian Computing Center, <http://www.nr.no/engelsk/> <mailto:haugsand@nr.no> Pho: +47 22852608 / +47 22852500, Fax: +47 22697660, Pb 114 Blindern, N-0314 OSLO, Norway
Subject: Re: Random numbers from a sound card? Date: Tue, 26 Jan 1999 20:47:01 GMT From: randombit@my-dejanews.com Message-ID: <78l9k2$dsh$1@nnrp1.dejanews.com> References: <yzo90eqv1df.fsf@procyon.nr.no> Newsgroups: sci.crypt Lines: 14 In article <yzo90eqv1df.fsf@procyon.nr.no>, Jon Haugsand <haugsand@procyon.nr.no> wrote: > * Cuykens Anthony > | I do remember of a way a teacher told me to generate a "true" random > | generator. Your teacher was just trying to communicate that you need a physical signal to start with, as deterministic algorithms can't produce unpredictability (aka randomness). Computers that can roll dice are not Turing machines. -----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Subject: Re: Random numbers from a sound card? Date: Wed, 27 Jan 1999 01:33:31 GMT From: rcktexas@ix.netcom.com (R. Knauer) Message-ID: <36ae6c8a.51870215@nntp.ix.netcom.com> References: <78l9k2$dsh$1@nnrp1.dejanews.com> Newsgroups: sci.crypt Lines: 14 On Tue, 26 Jan 1999 20:47:01 GMT, randombit@my-dejanews.com wrote: >Computers that can roll dice are not Turing machines. You got a computer that can roll dice - a completetly non-deterministic machine that can compute algorithmically? Bob Knauer "An honest man can feel no pleasure in the exercise of power over his fellow citizens." --Thomas Jefferson
Subject: Re: Random numbers from a sound card? Date: Tue, 26 Jan 1999 17:19:57 +0800 From: Nathan Kennedy <blaaf@hempseed.com> Message-ID: <36AD88BD.3397761D@hempseed.com> References: <36AD7FC6.674ABAEC@protonworld.com> Newsgroups: sci.crypt Lines: 30 Cuykens Anthony wrote: > > Hi, > > I do remember of a way a teacher told me to generate a "true" random > generator. You select some measurable information about your noise source (in > your case, lets says the frequence, the loudness, ...). Then you sample you > source at fixed interval and you check all your informations. For each coosen > information, if it is higher than the same info at the last sample, the output > is one, otherwize the result is zero. At each sample, this method will give you > one bit per criterion. > > This is just an idea, what does guru think of it? > That's just one way of converting a raw sampled value into a bit stream... It doesn't assure any randomness. It would probably be very predictable in the short term, and likely biased as well. Certainly, applying this to soundcard sampled data is little better than the raw output of /dev/audio. The best approach is not to waste any entropy, and just feed the raw data to a hungry hash function, which will process it into an unbiased output. The hash never has more entropy than what it is seeded with, however! Bruce Schneier has an excellent paper on PRNGs on his site (www.counterpane.com), which could serve as a good introduction. Nate
Subject: Re: Random numbers from a sound card? Date: Tue, 26 Jan 1999 21:26:38 GMT From: ross@hypertools.com (David Ross) Message-ID: <36ae3069.15236697@news.willapabay.org> References: <78l32u$fr4@trebuchet.eng.us.uu.net> <36ae089d.5049458@news.willapabay.org> <36AD7FC6.674ABAEC@protonworld.com> Newsgroups: sci.crypt Lines: 35 On 26 Jan 1999 13:55:26 -0500, giff@eng.us.uu.net (Frank Gifford) wrote: >In article <36ae089d.5049458@news.willapabay.org>, >David Ross <ross@hypertools.com> wrote: >> Have tried something very similar to that. I am attempting to >>create a rotortable of all 256 byte values placed in 'random' order, >>but the (8 bit) SoundBlaster seems reluctant to produce a 0xC0 byte. >>I infer this because in over 80% of the rotortables I create, 0xC0 is >>the last table entry. > >How are you creating the tables? I would assume that since you are creating >rotors, that each value appears in the rotor exactly once. Are you swapping >values or some other method? Personally, I would suspect your creation >routine is not doing what you want instead of bad numbers. Giff - I create one rotor at a time, waiting for each one of the 256 bytevalues to come in from the SoundBlaster before I go on to the next rotor. A very simple piece of code, done in assembly language. - several bytes commonly occurred toward the end of each rotor, but 0xC0 was by far the most popular as the last byte. (Incidentally, I'm using an ES1688 sound chip set up to emulate a SoundBlaster.) - the process of rotor creation took _much_ more time than I had estimated. - using a 'small' (50+) rotor encryption scheme to encrypt the SoundBlaster bytes before sending them to the rotor sorting routine sped up the process by about 20X. David Ross ross@hypertools.com
Subject: Re: Random numbers from a sound card? Date: 26 Jan 1999 17:30:58 -0500 From: giff@eng.us.uu.net (Frank Gifford) Message-ID: <78lfn2$g6t@trebuchet.eng.us.uu.net> References: <36ae3069.15236697@news.willapabay.org> Newsgroups: sci.crypt Lines: 44 In article <36ae3069.15236697@news.willapabay.org>, David Ross <ross@hypertools.com> wrote: > I create one rotor at a time, waiting for each one of the 256 >bytevalues to come in from the SoundBlaster before I go on to the next >rotor. A very simple piece of code, done in assembly language. Does this mean that (for a given rotor) you loop through rotor positions and get a value from SB that has not been used yet, and then do the remaining positions that way? So if SB gives you the same byte several times in a row that you ignore the duplicates? > - several bytes commonly occurred toward the end of each rotor, but >0xC0 was by far the most popular as the last byte. Assuming I understand your process, that means 0xC0 is very unlikely in a byte stream. In that case, SB in your set up is probably a bad choice for a random number generator. You may have to investigate your set up a bit more. Not enough static for input? > - the process of rotor creation took _much_ more time than I had >estimated. If you are doing it the way above, then yes indeed. When you get to the last two values, you are waiting for either of them to be generated so you can fill in the last piece of the rotor. You might want to look into generating a simple rotor and use the random numbers to swap entries in the rotor. Then you can simplify your code and generate a new rotor in a known amount of time. > - using a 'small' (50+) rotor encryption scheme to encrypt the >SoundBlaster bytes before sending them to the rotor sorting routine >sped up the process by about 20X. Does this mean you take the values from SB, pipe through your rotors, and then use the results to create/modify a rotor? In that case, this may be the source of weird results. I would recommend checking your set up of SB to see whether the bytes it generates directly is really 'random' and not biased. -Giff -- giff@uu.net Too busy for a .sig
Subject: Re: Random numbers from a sound card? Date: Tue, 26 Jan 1999 22:20:11 GMT From: phr@netcom.com (Paul Rubin) Message-ID: <phrF66u1o.JBE@netcom.com> References: <36ae089d.5049458@news.willapabay.org> <36AD7FC6.674ABAEC@protonworld.com> Newsgroups: sci.crypt Lines: 24 In article <36ae089d.5049458@news.willapabay.org>, David Ross <ross@hypertools.com> wrote: >Nathan Kennedy wrote: > >> > What sort of audio source would you suspect would be the best to use >> > in generating random numbers? >> >> I tune a cheap AM radio to a loud static channel, and wire that into the >> mic port. > Have tried something very similar to that. I am attempting to >create a rotortable of all 256 byte values placed in 'random' order, >but the (8 bit) SoundBlaster seems reluctant to produce a 0xC0 byte. >I infer this because in over 80% of the rotortables I create, 0xC0 is >the last table entry. > > I'd guess that the 'consumer-grade' A->D & D->A converters used >in common sound cards are susceptible to all sorts of troubles like >this, i.e. missing codes and/or monotonicity problems. Don't even think of using raw soundblaster output as actual random data rather than just as an entropy source. Even if the a/d converter is terrific, it's still likely to pick up correlated noise from various sources in the PC. Run the audio bits through a cryptographic hash function or something similar before using it.
Subject: Re: Random numbers from a sound card? Date: Tue, 26 Jan 1999 18:31:52 -0500 From: "Kazak, Boris" <bkazak@erols.com> Message-ID: <36AE5068.7AD8@erols.com> References: <phrF66u1o.JBE@netcom.com> Newsgroups: sci.crypt Lines: 56 Paul Rubin wrote: > > In article <36ae089d.5049458@news.willapabay.org>, > David Ross <ross@hypertools.com> wrote: > >Nathan Kennedy wrote: > > > >> > What sort of audio source would you suspect would be the best to use > >> > in generating random numbers? > >> > >> I tune a cheap AM radio to a loud static channel, and wire that into the > >> mic port. > > Have tried something very similar to that. I am attempting to > >create a rotortable of all 256 byte values placed in 'random' order, > >but the (8 bit) SoundBlaster seems reluctant to produce a 0xC0 byte. > >I infer this because in over 80% of the rotortables I create, 0xC0 is > >the last table entry. > > > > I'd guess that the 'consumer-grade' A->D & D->A converters used > >in common sound cards are susceptible to all sorts of troubles like > >this, i.e. missing codes and/or monotonicity problems. > > Don't even think of using raw soundblaster output as actual random > data rather than just as an entropy source. Even if the a/d converter > is terrific, it's still likely to pick up correlated noise from > various sources in the PC. Run the audio bits through a cryptographic > hash function or something similar before using it. ----------------------------------------- Let's be practical... It is perfectly possible to use the sound card for random number generation if we come up with a way to provide a random acoustic input on its microphone connector. Consider such a simple system: HHHHHHHHHHHHHHHH HH H MMM HH H MMMMM HH OOOOOOOOOO H MMMMM HH OOOOOOOOOOOO H MMM HHHHHHHHHHHHHHHH where HH is a Housing (just a glass or plastic bottle), OO are Objects (a pseudo-scientific baptism for 100-200 peas or beans), MM is a Microphone. Now if we start rotating the Housing around its horizontal axis, the Objects will produce a loud Random Rattle, and the Microphone will transmit this rattle to the sound card. My questions are: How many Objects are needed and what must be the speed of rotation that will assure the True Randomness? What estimates can be given for Degree of Correlation and for Period of Repetition, depending on the system parameters? The System is not patented, it is hereby placed in the public domain. Respectfully BNK
Subject: Re: Random numbers from a sound card? Date: Wed, 27 Jan 1999 01:34:38 GMT From: rcktexas@ix.netcom.com (R. Knauer) Message-ID: <36ae6d00.51988195@nntp.ix.netcom.com> References: <phrF66u1o.JBE@netcom.com> Newsgroups: sci.crypt Lines: 14 On Tue, 26 Jan 1999 22:20:11 GMT, phr@netcom.com (Paul Rubin) wrote: >Run the audio bits through a cryptographic >hash function or something similar before using it. Any recommendations on which hash function or something similar? Bob Knauer "An honest man can feel no pleasure in the exercise of power over his fellow citizens." --Thomas Jefferson
Subject: Re: Random numbers from a sound card? Date: Wed, 27 Jan 1999 18:31:02 GMT From: randombit@my-dejanews.com Message-ID: <78nm16$cvg$1@nnrp1.dejanews.com> References: <36ae6d00.51988195@nntp.ix.netcom.com> Newsgroups: sci.crypt Lines: 46 In article <36ae6d00.51988195@nntp.ix.netcom.com>, rcktexas@ix.netcom.com wrote: > On Tue, 26 Jan 1999 22:20:11 GMT, phr@netcom.com (Paul Rubin) wrote: > > >Run the audio bits through a cryptographic > >hash function or something similar before using it. > > Any recommendations on which hash function or something similar? > > Bob Knauer You'll be told to use an established one, say MD5. Doesn't matter too much. But what you *must* be careful with is this: A sample output of MD5 will look random -that's its job :-) It will appear to have full entropy. In order to know how many bits you have to distill with MD5, or any other hash, you need to measure your entropy/raw bit. Then you can convince skeptics that you are driving the hash with enough entropy. If your hash function is *not* a crypto-strong one, then you can directly measure the quality of its output ---since its not crypto strong, by definition its output (when given very redundant input) will be crappy. Parity-of-N has this property. When N is large enough, for a given raw-entropy-rate, the parity output is indistinguishable from crypto-strong (ie, uniformly distributed) output. When N is insufficient, you can see it with an entropy measure. ----- "Many tame, conformist types felt the need to describe anti-social actions as 'sick'." -Ted K -----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Subject: Re: Random numbers from a sound card? Date: Wed, 27 Jan 1999 18:18:17 GMT From: randombit@my-dejanews.com Message-ID: <78nl8u$ca5$1@nnrp1.dejanews.com> References: <36ae089d.5049458@news.willapabay.org> <36AD7FC6.674ABAEC@protonworld.com> Newsgroups: sci.crypt Lines: 37 In article <36ae089d.5049458@news.willapabay.org>, ross@hypertools.com (David Ross) wrote: > Nathan Kennedy wrote: > > > > What sort of audio source would you suspect would be the best to use > > > in generating random numbers? > > > > I tune a cheap AM radio to a loud static channel, and wire that into the > > mic port. FM has better hiss. I leave it to RF folks to explain why. Probably because FM listens to wider chunks of the aether than AM. Or because of the design of FM receivers amplifying component-noise more? > Have tried something very similar to that. I am attempting to > create a rotortable of all 256 byte values placed in 'random' order, > but the (8 bit) SoundBlaster seems reluctant to produce a 0xC0 byte. > I infer this because in over 80% of the rotortables I create, 0xC0 is > the last table entry. > > I'd guess that the 'consumer-grade' A->D & D->A converters used > in common sound cards are susceptible to all sorts of troubles like > this, i.e. missing codes and/or monotonicity problems. > > David Ross ross@hypertools.com Yes. You have to assume everything is imperfect. Your raw source is biassed, your whole amplification/detection (ie, digitization) chain has got holes in it (in either time or frequency domains), and you're in a fun digital-switching environment for extra bonus problems. This is why measurement is so much better than handwaving. -----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Subject: Re: Random numbers from a sound card? Date: Wed, 27 Jan 1999 20:47:32 GMT From: ross@hypertools.com (David Ross) Message-ID: <36af78e0.12951524@news.willapabay.org> References: <78nl8u$ca5$1@nnrp1.dejanews.com> Newsgroups: sci.crypt Lines: 22 On Wed, 27 Jan 1999 18:18:17 GMT, randombit@my-dejanews.com wrote: >In article <36ae089d.5049458@news.willapabay.org >ross@hypertools.com (David Ross) wrote: > What sort of audio source would you suspect would be the best to use >in generating random numbers? > >>> I tune a cheap AM radio to a loud static channel, and wire that into the >>> mic port. > >>FM has better hiss. I leave it to RF folks to explain why. Probably >>because FM listens to wider chunks of the aether than AM. Or because >>of the design of FM receivers amplifying component-noise more? I see this 'better hiss' quality too, and suspect that it is due to the FM detection scheme. In my case, the FM limiter & detector puts out a waveshape which is more linear in the voltage range where I'm digitizing. This yields a flatter distribution of A->D output bytes but is a bit slower. David Ross ross@hypertools.com
Subject: Re: Random numbers from a sound card? Date: Tue, 26 Jan 1999 00:28:16 GMT From: rcktexas@ix.netcom.com (R. Knauer) Message-ID: <36ad09fc.46447347@nntp.ix.netcom.com> References: <36ACC1E5.90C4C2BC@stud.uni-muenchen.de> Newsgroups: sci.crypt Lines: 35 On Mon, 25 Jan 1999 20:11:33 +0100, Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de> wrote: >> How would you test the 'quality' of the generated random number >> stream? >There are tests for statistical quality, e.g. Maurer's universal >statistical test. I am ignorant of tests for crypto quality. That's because there aren't any. It is a fundamental precept of crytpography that randomness is a property of how a number is generated, not a property of a number itself. >I guess the issue of cryptological strength is inherently fuzzy Not really. The OTP system is proveably secure. >and not entirely separable from subjectivity and concepts like >confidence intervals, i.e. no security can be claimed on an absolute >scale in practice. But experts might refute my un-knowledgeable >assertions. If someone tells you that he can demonstrate that a given number is crypto-grade random without considering the way it is generated, he is making a fundamental error, one of the most widespread errors in cryptography. Bob Knauer "An honest man can feel no pleasure in the exercise of power over his fellow citizens." --Thomas Jefferson
Subject: Re: Random numbers from a sound card? Date: Tue, 26 Jan 1999 14:19:59 +0100 From: Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de> Message-ID: <36ADC0FF.68F55692@stud.uni-muenchen.de> References: <36ad09fc.46447347@nntp.ix.netcom.com> Newsgroups: sci.crypt Lines: 14 R. Knauer wrote: > >I guess the issue of cryptological strength is inherently fuzzy > > Not really. The OTP system is proveably secure. Once again I assert that this is a (for all practical purposes) useless fact, because OTP presuppose (absolutely) true randomness and there is no way of determining that in practice. I suppose (with my meager knowledge of physics) this is almost the same as saying at at at 0 Kelvin you can halt the motions of all atoms (but you can't get to 0 Kelvin, only very close to it). M. K. Shen
Subject: Re: Random numbers from a sound card? Date: Tue, 26 Jan 1999 19:11:42 GMT From: rcktexas@ix.netcom.com (R. Knauer) Message-ID: <36ae0cb6.27338280@nntp.ix.netcom.com> References: <36ADC0FF.68F55692@stud.uni-muenchen.de> Newsgroups: sci.crypt Lines: 68 On Tue, 26 Jan 1999 14:19:59 +0100, Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de> wrote: >> Not really. The OTP system is proveably secure. >Once again I assert that this is a (for all practical purposes) >useless fact, Sorry, but that's nonsense. For all practical purposes the OTP is proveably secure. That means that you can build an OTP system that is secure to within a level of precision can be made arbitrarily small. To do that you must build a physical device which can generate all possible sequences of a given finite length equiprobably. That is possible using quantum mechanical processes and good electronic design. The hot line between Washington and Moscow is (supposedly) protected by an OTP. Conversations on that line can be tapped and interfered with in principle by anyone close enough to the equipment. Do you think the two most dangerous govts in the world would trust the fate of Planet Earth to an insecure communications link? Hardly. Nothing we humans build is Perfect, but we are able to build things that are very damn close to Perfect. We can build TRNGs that are perfect enough to send messages which would take more energy to analyze than is available in the Universe. How much more Perfect do you want, even in a practical sense? >because OTP presuppose (absolutely) true randomness >and there is no way of determining that in practice. Sure there is. Just look at how the numbers are being generated. That will tell you if they are random. >I suppose >(with my meager knowledge of physics) this is almost the same as >saying at at at 0 Kelvin you can halt the motions of all atoms You are not aware of the so-called "zero point" vacuum fluctuations which persist even at 0 Kelvin. If all motion stopped at 0 Kelvin, the Universe would cease to exist - no photons, no particles, no forces - nothing. >(but you can't get to 0 Kelvin, only very close to it). You can get exceedingly close to it, like one milli-degree close to it. That's one thousandth of a degree close to it. How much closer would you want to get to be closer than very close to it? Is calculus impossible because numbers can never actually reach the limit required to calculate a derivative or an integral? People in the 17th century, when Newton and Leibnitz invented calculus, thought calculus was wrong because those limits could never be reached in a "practical" sense. Yet calculus went on being correct despite them. And crypto-grade randomness goes on being correct in a very practical sense too, despite the lack of perfection in a practical sense. Bob Knauer "An honest man can feel no pleasure in the exercise of power over his fellow citizens." --Thomas Jefferson
Subject: Re: Random numbers from a sound card? Date: Wed, 27 Jan 1999 14:56:34 +0100 From: Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de> Message-ID: <36AF1B12.FBD87AB5@stud.uni-muenchen.de> References: <36ae0cb6.27338280@nntp.ix.netcom.com> Newsgroups: sci.crypt Lines: 28 R. Knauer wrote: > > Nothing we humans build is Perfect, but we are able to build things > that are very damn close to Perfect. We can build TRNGs that are > perfect enough to send messages which would take more energy to > analyze than is available in the Universe. > > How much more Perfect do you want, even in a practical sense? I am not against having something ideal and perfect as a standard for approximation (to be strived at in practice) or for pedagogical purpose. But to say there IS (in the sence of EXISTS) something perfect can be misleading. > > >because OTP presuppose (absolutely) true randomness > >and there is no way of determining that in practice. > > Sure there is. Just look at how the numbers are being generated. That > will tell you if they are random. To 'just look' is certainly not ensuring (compare watching a magician pulling rabits out of his hat). We have to ascertain how 'random' the sequence we get really is. And that's one of the real and big problem for the practice. M. K. Shen
Subject: Re: Random numbers from a sound card? Date: Wed, 27 Jan 1999 15:02:36 GMT From: rcktexas@ix.netcom.com (R. Knauer) Message-ID: <36af2a34.18209443@nntp.ix.netcom.com> References: <36AF1B12.FBD87AB5@stud.uni-muenchen.de> Newsgroups: sci.crypt Lines: 17 On Wed, 27 Jan 1999 14:56:34 +0100, Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de> wrote: >But to say there IS (in the sense of EXISTS) something >perfect can be misleading. Does a Perfect Circle EXIST? If you say is does, is that misleading? Bob Knauer "No Freeman shall ever be debarred the use of arms. The strongest reason for the people to retain the right to keep and bear arms is, as a last resort, to protect themselves against tyranny in government." --Thomas Jefferson
Subject: Re: Random numbers from a sound card? Date: Wed, 27 Jan 1999 16:44:40 +0100 From: Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de> Message-ID: <36AF3468.78EDE075@stud.uni-muenchen.de> References: <36af2a34.18209443@nntp.ix.netcom.com> Newsgroups: sci.crypt Lines: 16 R. Knauer wrote: > > On Wed, 27 Jan 1999 14:56:34 +0100, Mok-Kong Shen > <mok-kong.shen@stud.uni-muenchen.de> wrote: > > >But to say there IS (in the sense of EXISTS) something > >perfect can be misleading. > > Does a Perfect Circle EXIST? > > If you say is does, is that misleading? If the word 'IS' is employed in a context without the connotation of 'EXISTS' then it is NOT misleading, otherwise it IS misleading. M. K. Shen
Subject: Re: Random numbers from a sound card? Date: Wed, 27 Jan 1999 16:15:17 GMT From: rcktexas@ix.netcom.com (R. Knauer) Message-ID: <36af3b4d.22586607@nntp.ix.netcom.com> References: <36AF3468.78EDE075@stud.uni-muenchen.de> Newsgroups: sci.crypt Lines: 20 On Wed, 27 Jan 1999 16:44:40 +0100, Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de> wrote: >If the word 'IS' is employed in a context without the connotation >of 'EXISTS' then it is NOT misleading, otherwise it IS misleading. You are beginning to sound just like Bill Clinton: "It all depends on what the meaning of the word 'is' is." <jeez> Bob Knauer "No Freeman shall ever be debarred the use of arms. The strongest reason for the people to retain the right to keep and bear arms is, as a last resort, to protect themselves against tyranny in government." --Thomas Jefferson
Subject: Re: Random numbers from a sound card? Date: Wed, 27 Jan 1999 17:46:44 +0100 From: Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de> Message-ID: <36AF42F4.5B9DC5CD@stud.uni-muenchen.de> References: <36af3b4d.22586607@nntp.ix.netcom.com> Newsgroups: sci.crypt Lines: 23 R. Knauer wrote: > > On Wed, 27 Jan 1999 16:44:40 +0100, Mok-Kong Shen > <mok-kong.shen@stud.uni-muenchen.de> wrote: > > >If the word 'IS' is employed in a context without the connotation > >of 'EXISTS' then it is NOT misleading, otherwise it IS misleading. > > You are beginning to sound just like Bill Clinton: > > "It all depends on what the meaning of the word 'is' is." That way clearly stated in my previous post, quoted below: But to say there IS (in the sense of EXISTS) something perfect can be misleading. A word can have a multitude of meanings. I was prudent enough to put the parentheses above to make sure that there could be no misunderstanding. I regret that my attempt was appraently not successful. M. K. Shen
Subject: Re: Random numbers from a sound card? Date: Wed, 27 Jan 1999 17:36:54 GMT From: rcktexas@ix.netcom.com (R. Knauer) Message-ID: <36af4e20.27405937@nntp.ix.netcom.com> References: <36AF42F4.5B9DC5CD@stud.uni-muenchen.de> Newsgroups: sci.crypt Lines: 34 On Wed, 27 Jan 1999 17:46:44 +0100, Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de> wrote: >> "It all depends on what the meaning of the word 'is' is." >That way clearly stated in my previous post, quoted below: > But to say there IS (in the sense of EXISTS) something > perfect can be misleading. >A word can have a multitude of meanings. I was prudent enough >to put the parentheses above to make sure that there could be >no misunderstanding. I regret that my attempt was appraently >not successful. You must be a mathematician. As Greg Chaitin says in his latest book. "The Unknowable", physicists have a sense of humor (BTW, I am a physicist), but mathematicians do not have a sense of humor. Which is not completely true because Chaitin is a mathematician and he has a sense of humor. Whatever. Bob Knauer "No Freeman shall ever be debarred the use of arms. The strongest reason for the people to retain the right to keep and bear arms is, as a last resort, to protect themselves against tyranny in government." --Thomas Jefferson
Subject: Re: Random numbers from a sound card? Date: Wed, 27 Jan 1999 12:02:38 -0600 From: Medical Electronics Lab <rosing@physiology.wisc.edu> Message-ID: <36AF54BE.5771@physiology.wisc.edu> References: <36AF1B12.FBD87AB5@stud.uni-muenchen.de> Newsgroups: sci.crypt Lines: 23 Mok-Kong Shen wrote: > I am not against having something ideal and perfect as a standard > for approximation (to be strived at in practice) or for pedagogical > purpose. But to say there IS (in the sence of EXISTS) something > perfect can be misleading. Kind of depends on how you define "perfect". Perfect for what and measured in what way? We can certainly build a TRNG which is perfect in any measureable sense. > To 'just look' is certainly not ensuring (compare watching a > magician pulling rabits out of his hat). We have to ascertain > how 'random' the sequence we get really is. And that's one of > the real and big problem for the practice. Which is what makes this whole discussion so much fun. DIEHARD and Diaphony and autocorrelation all measure "random" in a slightly different way. If the output of a TRNG appears random to all those tests, we can say it "looks" random. It is "perfect" as far as we can measure. Isn't that good enough? Patience, persistence, truth, Dr. mike
Subject: Re: Random numbers from a sound card? Date: Wed, 27 Jan 1999 12:06:35 -0700 From: "Tony T. Warnock" <u091889@cic-mail.lanl.gov> Message-ID: <36AF63BB.18D3EEA9@cic-mail.lanl.gov> References: <36AF54BE.5771@physiology.wisc.edu> Newsgroups: sci.crypt Lines: 46 Medical Electronics Lab wrote: > Mok-Kong Shen wrote: > > I am not against having something ideal and perfect as a standard > > for approximation (to be strived at in practice) or for pedagogical > > purpose. But to say there IS (in the sence of EXISTS) something > > perfect can be misleading. > > Kind of depends on how you define "perfect". Perfect for what and > measured in what way? We can certainly build a TRNG which is > perfect in any measureable sense. > > > To 'just look' is certainly not ensuring (compare watching a > > magician pulling rabits out of his hat). We have to ascertain > > how 'random' the sequence we get really is. And that's one of > > the real and big problem for the practice. > > Which is what makes this whole discussion so much fun. DIEHARD > and Diaphony and autocorrelation all measure "random" in a slightly > different way. If the output of a TRNG appears random to all those > tests, we can say it "looks" random. It is "perfect" as far > as we can measure. Isn't that good enough? > > Patience, persistence, truth, > Dr. mike It's not clear what is wanted here. In limit (infinitely long sequences) both the complexity based and the frequency (statistical) based definitions of random are equivalent (per Martin Lof). For finite sequences (actually for computable sequences, IMHO) these are not necessarily equivalent. It is easy to produce sequences that satisfy the strong law of large numbers. Champernowne's sequence comes to mind: 01,1011,100101110111,.... It is not very complex computationally. It does have the proper frequency of everything, that is, each k bit sequence has limiting frequence 1/2^k. Unfortunately I do not know of any easily constructed sequence that satisfy the law of the iterated logarithm. I do not even know how to test for this. It would be a requirement for a "statistically random" sequence. It's possible that one can only list a set of criteria and check if your sequence satisfy them. Again, most of these criteria are not computable but "almost all" sequences satisfy them Tony
Subject: Re: Random numbers from a sound card? Date: Wed, 27 Jan 1999 23:01:14 GMT From: rcktexas@ix.netcom.com (R. Knauer) Message-ID: <36af98b1.46494265@nntp.ix.netcom.com> References: <36AF54BE.5771@physiology.wisc.edu> Newsgroups: sci.crypt Lines: 50 On Wed, 27 Jan 1999 12:02:38 -0600, Medical Electronics Lab <rosing@physiology.wisc.edu> wrote: >> To 'just look' is certainly not ensuring (compare watching a >> magician pulling rabits out of his hat). We have to ascertain >> how 'random' the sequence we get really is. And that's one of >> the real and big problem for the practice. >Which is what makes this whole discussion so much fun. Then you're a masochist. :-) Once you catch on to all this, you will see why. >DIEHARD >and Diaphony and autocorrelation all measure "random" in a slightly >different way. Those things don't measure the crypto-grade randomness of finite numbers at all. They try to make inferences about the generator from finite samples, which is useless for purposes of crypto. They will pass the outputs of PRNGs that can be cracked. We need an update to the Snake Oil FAQ desperately! >If the output of a TRNG appears random to all those >tests, we can say it "looks" random. Just what makes a finite number produced by a TRNG "look random"? Why do you thing that characteristics that apply only to infinite numbers can also apply to finite ones with equal certitude? What does "vanishingly small" mean to you? >It is "perfect" as far as we can measure. That measure is worthless for crypto-grade random numbers. > Isn't that good enough? Nope. Not even close. Bob Knauer "No Freeman shall ever be debarred the use of arms. The strongest reason for the people to retain the right to keep and bear arms is, as a last resort, to protect themselves against tyranny in government." --Thomas Jefferson
Subject: Re: Random numbers from a sound card? Date: Thu, 28 Jan 1999 12:47:39 -0600 From: Medical Electronics Lab <rosing@physiology.wisc.edu> Message-ID: <36B0B0CB.1974@physiology.wisc.edu> References: <36af98b1.46494265@nntp.ix.netcom.com> Newsgroups: sci.crypt Lines: 56 R. Knauer wrote: > > Then you're a masochist. :-) :-) I think you're right about that! > Once you catch on to all this, you will see why. It's pretty clear we have different opinions. The best I can hope for is more descriptions so I can find out what the core assumption is that we disagree on. Neither one of us will change :-) > Those things don't measure the crypto-grade randomness of finite > numbers at all. They try to make inferences about the generator from > finite samples, which is useless for purposes of crypto. They will > pass the outputs of PRNGs that can be cracked. So you need an infinite sequence of bits to prove that something is crypto-grade random, yes? > Just what makes a finite number produced by a TRNG "look random"? Is a 10 megabyte block of random bits a single number? Or is it 80 million individual numbers? For the latter case, it looks random if it can pass all the tests for randomness that mathematicians have dreamed up. In the former case, if it isn't printable ascii, then it will probably look random no matter what. > Why do you thing that characteristics that apply only to infinite > numbers can also apply to finite ones with equal certitude? What characteristics are you talking about? Integrals over a finite range and binomial or poisson distributions are all based on finite samples. All the DIEHARD tests are based on finite samples. I am assuming that Marsaglia knows what he's doing, but maybe you can correct him? > What does "vanishingly small" mean to you? Less than I can measure. > That measure is worthless for crypto-grade random numbers. Yes, well, expand on "crypto-grade" a bit. > > Isn't that good enough? > > Nope. Not even close. :-) See, I told you we disagree. Let's keep it that way, makes for a nice long discussion. Patience, persistence, truth, Dr. mike
Subject: Re: Random numbers from a sound card? Date: Thu, 28 Jan 1999 23:07:11 GMT From: rcktexas@ix.netcom.com (R. Knauer) Message-ID: <36b0d008.1959958@nntp.ix.netcom.com> References: <36B0B0CB.1974@physiology.wisc.edu> Newsgroups: sci.crypt Lines: 111 On Thu, 28 Jan 1999 12:47:39 -0600, Medical Electronics Lab <rosing@physiology.wisc.edu> wrote: >It's pretty clear we have different opinions. The best I can >hope for is more descriptions so I can find out what the core >assumption is that we disagree on. Neither one of us will change You will change once you catch on. I did. A year ago I came onto sci.crypt with ill-formed notions of crypto-grade randomness. After what seemed like a thousand posts from many participants, the truth emerged. I have capsulized that truth several times recently but some people, including you, still have not caught on. When you do catch on, you will look back and wonder how you could have been so confused about such a straightforward concept. I did. >So you need an infinite sequence of bits to prove that something >is crypto-grade random, yes? You cannot prove the crypto-grade randomness of a finite number algorithmically. You can for an infinite number, but that is useless. The only way you can prove the crypto-grade randomness of a finite number is to consider the method of generation. If the generator is a TRNG, as we have defined it here several times recently, then the numbers it generates are crypto-grade random numbers. >Is a 10 megabyte block of random bits a single number? Yes. >Or is it 80 million individual numbers? Yes. >For the latter case, it looks >random if it can pass all the tests for randomness that >mathematicians have dreamed up. Wrong. You might be able to infer some things about the numbers that fool you into thinking they are random, but that does not make them crypto-random. Keep in mind that many PRNGs pass statistical tests. >In the former case, if it isn't >printable ascii, then it will probably look random no matter >what. Numbers don't "look" crypto-random. The number 1111111111 is a crypto-grade random number, because it was generated by a TRNG. Or, may it is not because it was not generated by a TRNG. You cannot tell unless you know the generation process. Tell me if you think 111111111 is crypto-grade random or not. >> Why do you thing that characteristics that apply only to infinite >> numbers can also apply to finite ones with equal certitude? >What characteristics are you talking about? The characteristic of randomness. Infinite numbers have characteristics which can be related to randomness. If an infinite number is a normal number, it is random. Finite numbers cannot be normal numbers - they are not big enough. For example, if you can prove that pi is a normal number, then it is a random number. >Integrals over a >finite range and binomial or poisson distributions are all based >on finite samples. Do they measure crypto-grade randomness of finite numbers? If they could, these algorithms you propose could also be used to solve Godel's incompleteness problem, Turing's halting problem and Chaitin's complexity problem. >All the DIEHARD tests are based on finite >samples. I am assuming that Marsaglia knows what he's doing, >but maybe you can correct him? You correct him, when you discover the truth. >> What does "vanishingly small" mean to you? >Less than I can measure. Explain your method of measurement. >Yes, well, expand on "crypto-grade" a bit. Proveably secure when used with the OTP cryptosystem. >:-) See, I told you we disagree. Let's keep it that way, >makes for a nice long discussion. Last time it was over 1,000 posts. I am beginning to think I was the only one who got anything out of them. Bob Knauer "No Freeman shall ever be debarred the use of arms. The strongest reason for the people to retain the right to keep and bear arms is, as a last resort, to protect themselves against tyranny in government." --Thomas Jefferson
Subject: Re: Random numbers from a sound card? Date: Fri, 29 Jan 1999 11:47:15 +0100 From: Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de> Message-ID: <36B191B3.89CCEFA3@stud.uni-muenchen.de> References: <36b0d008.1959958@nntp.ix.netcom.com> Newsgroups: sci.crypt Lines: 19 R. Knauer wrote: > > > You cannot prove the crypto-grade randomness of a finite number > algorithmically. You can for an infinite number, but that is useless. > > The only way you can prove the crypto-grade randomness of a finite > number is to consider the method of generation. If the generator is a > TRNG, as we have defined it here several times recently, then the > numbers it generates are crypto-grade random numbers. Ah! Finally one knows exactly what the term 'crypto-grade random numbers' you employ means: These are DEFINED to be the output from a hardware generator. If follows obviously then that there is NO need whatsoever of testing the sequences obtained, since they are BY DEFINITION 'crypto-grade'! M. K. Shen
Subject: Re: Random numbers from a sound card? Date: Fri, 29 Jan 1999 13:37:25 GMT From: rcktexas@ix.netcom.com (R. Knauer) Message-ID: <36b1b932.2360123@nntp.ix.netcom.com> References: <36B191B3.89CCEFA3@stud.uni-muenchen.de> Newsgroups: sci.crypt Lines: 26 On Fri, 29 Jan 1999 11:47:15 +0100, Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de> wrote: >> The only way you can prove the crypto-grade randomness of a finite >> number is to consider the method of generation. If the generator is a >> TRNG, as we have defined it here several times recently, then the >> numbers it generates are crypto-grade random numbers. >Ah! Finally one knows exactly what the term 'crypto-grade random >numbers' you employ means: These are DEFINED to be the output >from a hardware generator. If follows obviously then that there >is NO need whatsoever of testing the sequences obtained, since they >are BY DEFINITION 'crypto-grade'! Are you being deliberatly obtuse - or does it come naturally? Nothing that you said above follows from what I said. A TRNG is not a True Random Number Generator just because it is a hardware device. Bob Knauer "No Freeman shall ever be debarred the use of arms. The strongest reason for the people to retain the right to keep and bear arms is, as a last resort, to protect themselves against tyranny in government." --Thomas Jefferson
Subject: Re: Random numbers from a sound card? Date: 29 Jan 1999 09:14:11 -0500 From: juola@mathcs.duq.edu (Patrick Juola) Message-ID: <78sfnj$ouo$1@quine.mathcs.duq.edu> References: <36B191B3.89CCEFA3@stud.uni-muenchen.de> Newsgroups: sci.crypt Lines: 21 In article <36B191B3.89CCEFA3@stud.uni-muenchen.de>, Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de> wrote: >R. Knauer wrote: >> > >> >> You cannot prove the crypto-grade randomness of a finite number >> algorithmically. You can for an infinite number, but that is useless. >> >> The only way you can prove the crypto-grade randomness of a finite >> number is to consider the method of generation. If the generator is a >> TRNG, as we have defined it here several times recently, then the >> numbers it generates are crypto-grade random numbers. > >Ah! Finally one knows exactly what the term 'crypto-grade random >numbers' you employ means: These are DEFINED to be the output >from a hardware generator. No. Not all hardware generators are TRNG. -kitten
Subject: Re: Random numbers from a sound card? Date: Fri, 29 Jan 1999 08:38:00 -0700 From: "Tony T. Warnock" <u091889@cic-mail.lanl.gov> Message-ID: <36B1D5D8.9E4A7B55@cic-mail.lanl.gov> References: <36b0d008.1959958@nntp.ix.netcom.com> Newsgroups: sci.crypt Lines: 35 R. Knauer wrote: > The characteristic of randomness. Infinite numbers have > characteristics which can be related to randomness. If an infinite > number is a normal number, it is random. Finite numbers cannot be > normal numbers - they are not big enough. > > For example, if you can prove that pi is a normal number, then it is a > random number. Normality is certainly necessary but not sufficient. It's a good start. More than normality is needed. I can give you many normal numbers but none of them are "random." Champernowne's number is the simplest example: 1,10,11,100,101,110,111,...=11011100101110111.... It is easy to prove that all k-bit patterns have the proper frequency. This is all that is needed for normality. (The concept of normality was introduced by Borel about 1909.) The digits of a normal number satisfy the strong law of large numbers, that is, 1/2 ones, 1/2 zeros, 1/4 00's, 1/4 01's, 1/4 10's, 1/4 11's, ..., 1/1024 1101101101's, etc. The problem is that the strong law of large numbers is not very strong. In Champernowne's number, the excess of ones over zeros grows as N/log(N) for N bits. The ratio goes like 1/2+1/log(N), really slow. The dispersion is also not correct. The law of the iterated logarithm fails for all these sequences. Of course both the above laws (large numbers, iterated logarithm) are statistical in nature and do not indicate how difficult it is to guess successive bits of a number. Complexity of computation and statistical properties are only equivalent in the limit of infnitely many infinitely long sequences. Tony
Subject: Re: Random numbers from a sound card? Date: Sat, 30 Jan 1999 03:09:39 GMT From: rcktexas@ix.netcom.com (R. Knauer) Message-ID: <36b272f8.49918378@nntp.ix.netcom.com> References: <36B1D5D8.9E4A7B55@cic-mail.lanl.gov> Newsgroups: sci.crypt Lines: 70 On Fri, 29 Jan 1999 08:38:00 -0700, "Tony T. Warnock" <u091889@cic-mail.lanl.gov> wrote: >Normality is certainly necessary but not sufficient. It's a good start. >More than normality is needed. I can give you many normal numbers but none >of them are "random." Are they infinite? >Champernowne's number is the simplest example: >1,10,11,100,101,110,111,...=11011100101110111.... It is easy to prove that >all k-bit patterns have the proper frequency. Yes, but only if the number is infinite. >This is all that is needed >for normality. (The concept of normality was introduced by Borel about >1909.) The digits of a normal number satisfy the strong law of large >numbers, that is, 1/2 ones, 1/2 zeros, 1/4 00's, 1/4 01's, 1/4 10's, 1/4 >11's, ..., 1/1024 1101101101's, etc. Chaitin cover this in his papers - for those who want an accessible reference. >The problem is that the strong law of large numbers is not very strong. In >Champernowne's number, the excess of ones over zeros grows as N/log(N) for >N bits. Is that really a problem? Whoevewr said that bias was an intrinsic property of infinite random numbers? >The ratio goes like 1/2+1/log(N), really slow. The dispersion is >also not correct. The law of the iterated logarithm fails for all these >sequences. This what I like about the Internet in general, and Usenet forums like sci.crypt in particular. There is always someone who knows the something about something - someone who is willing to jump in and expose that. Without the Truth to seek out, life is completely meaningless. [Cf. Camus, "The Myth Of Sysiphus" and the concept of "Lucidity".] Your further elaborations would be most higly regarded by me amd all the lurkers on sci.crypt. The concept of randomness is fundamental to an understanding of how we consider Order, the thing which distinguishes us from dirt. The concept of randomness is at the heart of Quantum Mechanics, which has incredible predictive value. >Of course both the above laws (large numbers, iterated logarithm) are >statistical in nature and do not indicate how difficult it is to guess >successive bits of a number. Complexity of computation and statistical >properties are only equivalent in the limit of infnitely many infinitely >long sequences. Another excellent contribution to the FAQ on crypto-grade randomness. But I point out that computational complexity has nothing fundamental to do with crypto-grade randomness, nor QM. In those realms everything is possible, even the most simple of sequences. In fact, I believe we are here because the simpler sequences prevailed. Bob Knauer "No Freeman shall ever be debarred the use of arms. The strongest reason for the people to retain the right to keep and bear arms is, as a last resort, to protect themselves against tyranny in government." --Thomas Jefferson
Subject: Re: Random numbers from a sound card? Date: Sat, 30 Jan 1999 14:51:49 GMT From: rcktexas@ix.netcom.com (R. Knauer) Message-ID: <36b31a67.8855773@nntp.ix.netcom.com> References: <36B1D5D8.9E4A7B55@cic-mail.lanl.gov> Newsgroups: sci.crypt Lines: 38 On Fri, 29 Jan 1999 08:38:00 -0700, "Tony T. Warnock" <u091889@cic-mail.lanl.gov> wrote: >Champernowne's number is the simplest example: >1,10,11,100,101,110,111,...=11011100101110111.... It is easy to prove that >all k-bit patterns have the proper frequency. This is all that is needed >for normality. (The concept of normality was introduced by Borel about >1909.) The digits of a normal number satisfy the strong law of large >numbers, that is, 1/2 ones, 1/2 zeros, 1/4 00's, 1/4 01's, 1/4 10's, 1/4 >11's, ..., 1/1024 1101101101's, etc. >The problem is that the strong law of large numbers is not very strong. In >Champernowne's number, the excess of ones over zeros grows as N/log(N) for >N bits. The ratio goes like 1/2+1/log(N), really slow. The dispersion is >also not correct. The law of the iterated logarithm fails for all these >sequences. In re-reading this I spotted something I do not understand. You state that for the Champernowne number "all k-bit patterns have the proper frequency". I assume that is true for k = 1, one of the possible values for k. Then you say that in Champernowne's number there is an "excess of ones over zeros". How can that be if "all k-bit patterns have the proper frequency"? The "proper frequency" for k = 1 as described by you: "The digits of a normal number satisfy the strong law of large numbers, that is, 1/2 ones, 1/2 zeros". How come you state that Champernowne's number has an "excess of ones over zeros"? Bob Knauer "No Freeman shall ever be debarred the use of arms. The strongest reason for the people to retain the right to keep and bear arms is, as a last resort, to protect themselves against tyranny in government." --Thomas Jefferson
Subject: Re: Random numbers from a sound card? Date: Sat, 30 Jan 1999 14:31:17 -0500 From: "Trevor Jackson, III" <fullmoon@aspi.net> Message-ID: <36B35E04.3DF9ED19@aspi.net> References: <36b31a67.8855773@nntp.ix.netcom.com> Newsgroups: sci.crypt Lines: 46 R. Knauer wrote: > On Fri, 29 Jan 1999 08:38:00 -0700, "Tony T. Warnock" > <u091889@cic-mail.lanl.gov> wrote: > > >Champernowne's number is the simplest example: > >1,10,11,100,101,110,111,...=11011100101110111.... It is easy to prove that > >all k-bit patterns have the proper frequency. This is all that is needed > >for normality. (The concept of normality was introduced by Borel about > >1909.) The digits of a normal number satisfy the strong law of large > >numbers, that is, 1/2 ones, 1/2 zeros, 1/4 00's, 1/4 01's, 1/4 10's, 1/4 > >11's, ..., 1/1024 1101101101's, etc. > > >The problem is that the strong law of large numbers is not very strong. In > >Champernowne's number, the excess of ones over zeros grows as N/log(N) for > >N bits. The ratio goes like 1/2+1/log(N), really slow. The dispersion is > >also not correct. The law of the iterated logarithm fails for all these > >sequences. > > In re-reading this I spotted something I do not understand. You state > that for the Champernowne number "all k-bit patterns have the proper > frequency". I assume that is true for k = 1, one of the possible > values for k. > > Then you say that in Champernowne's number there is an "excess of ones > over zeros". How can that be if "all k-bit patterns have the proper > frequency"? The "proper frequency" for k = 1 as described by you: "The > digits of a normal number satisfy the strong law of large numbers, > that is, 1/2 ones, 1/2 zeros". > > How come you state that Champernowne's number has an "excess of ones > over zeros"? Because all the leading zeros are suppressed. > > > Bob Knauer > > "No Freeman shall ever be debarred the use of arms. The strongest > reason for the people to retain the right to keep and bear arms is, > as a last resort, to protect themselves against tyranny in government." > --Thomas Jefferson
Subject: Re: Random numbers from a sound card? Date: Sun, 31 Jan 1999 00:06:40 GMT From: rcktexas@ix.netcom.com (R. Knauer) Message-ID: <36b39e73.42659320@nntp.ix.netcom.com> References: <36B35E04.3DF9ED19@aspi.net> Newsgroups: sci.crypt Lines: 17 On Sat, 30 Jan 1999 14:31:17 -0500, "Trevor Jackson, III" <fullmoon@aspi.net> wrote: >> How come you state that Champernowne's number has an "excess of ones >> over zeros"? >Because all the leading zeros are suppressed. Can you elaborate with an example. Bob Knauer "I place economy among the first and most important virtues and public debt as the greatest dangers to be feared. We must not let our rulers load us with perpetual debt." --Thomas Jefferson
Subject: Re: Random numbers from a sound card? Date: 26 Jan 1999 14:59:26 -0500 From: juola@mathcs.duq.edu (Patrick Juola) Message-ID: <78l6qu$k97$1@quine.mathcs.duq.edu> References: <36ADC0FF.68F55692@stud.uni-muenchen.de> Newsgroups: sci.crypt Lines: 25 In article <36ADC0FF.68F55692@stud.uni-muenchen.de>, Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de> wrote: >R. Knauer wrote: > >> >I guess the issue of cryptological strength is inherently fuzzy >> >> Not really. The OTP system is proveably secure. > >Once again I assert that this is a (for all practical purposes) >useless fact, because OTP presuppose (absolutely) true randomness >and there is no way of determining that in practice. Not quite. The randomness that the OTP presumes works out to be exactly the same problem as key generation for a key system -- if (somehow) the attacker can predict which key you are going to use, then the attacker can unbutton your messages more or less at will. Similarly if the attacker can force you to use a particular key. So, yes, you'll probably not build a "perfect" OTP in practice, any more than you'll be able to get a bug-free computer program. That doesn't mean that there aren't techniques that are *less* likely to approach perfection than others. -kitten
Subject: Re: Random numbers from a sound card? Date: Tue, 26 Jan 1999 18:15:11 +0000 From: pla@sktb.demon.co.uk (Paul L. Allen) Message-ID: <f8BSgej030n@sktb.demon.co.uk> References: <36ad09fc.46447347@nntp.ix.netcom.com> Newsgroups: sci.crypt Lines: 38 In article <36ad09fc.46447347@nntp.ix.netcom.com> rcktexas@ix.netcom.com (R. Knauer) writes: > On Mon, 25 Jan 1999 20:11:33 +0100, Mok-Kong Shen > <mok-kong.shen@stud.uni-muenchen.de> wrote: > > >> How would you test the 'quality' of the generated random number > >> stream? > > >There are tests for statistical quality, e.g. Maurer's universal > >statistical test. I am ignorant of tests for crypto quality. > > That's because there aren't any. > > It is a fundamental precept of crytpography that randomness is a > property of how a number is generated, not a property of a number > itself. I'd be *extremely* worried about a sound card (particularly with little in the way of input) picking up mains power hum and radiated noise from signal lines in the computer. Obviously they'll only affect a few of the lower bits of output (or you'd hear it when you played sounds back) but that might be enough to weaken the randomness enough to cause problems. Boiling down the entropy with a cryptographic hash function probably gets rid of it, but if you have a crappy sound card you may have to do a lot more boiling away than with a good one. Noise diodes strike me as being safer. The fundamental mechanism of noise generation in them may well be chaotic and I've seen worries that chaotic loci can be close to periodic for long periods of time, but there are likely to be many individual sources of chaotic noise in the diode (due to random distribution of dopant atoms) which may make things alot safer. Probably. It really needs somebody whose done detailed work on those noise mechanisms to comment. --Paul
Subject: Re: Random numbers from a sound card? Date: Tue, 26 Jan 1999 20:12:38 GMT From: randombit@my-dejanews.com Message-ID: <78l7je$cc6$1@nnrp1.dejanews.com> References: <36acb8b1.5374650@news.willapabay.org> Newsgroups: sci.crypt Lines: 79 In article <36acb8b1.5374650@news.willapabay.org>, ross@hypertools.com (David Ross) wrote: > Has anyone had success using a sound card (like a Sound Blaster) to > generate streams of random numbers? Yes. > What sort of audio source would you suspect would be the best to use > in generating random numbers? I used an old radio shack mono fm radio, with antenna removed, tuned to hiss, at high volume, fed into the sound card. Later I got a video/radio digitizer, which I can tune to FM hiss, which is more self contained. This produces an apparently uniformly distributed noise spectrum, using a pc-based spectrum analyzer. But this doesn't have full entropy, and you have to distill (see RFC 1750) the bits. I experimented with parity-of-N bits, and used Maurer's Universal statistical test for RNGs to measure the entropy. When you distill enough, the entropy reaches its expected value. Some people might recommend a strong hashing function (e.g., a thousand raw bits hashed with MD5 down to a fixed output size). This is complex and I found unnecessary; simple parity works, though it may waste more bits than a serious hash would. But bits are cheap, and xor is fast. > How would you test the 'quality' of the generated random number > stream? 1. Marsaglia's Diehard suite of statistical (structure) tests. This suite goes far beyond the FIPS suggestions. 2. Maurer's Universal statistical test, which approximates the entropy of a sample using a formally motivated, compression-like algorithm. As "calibration standards" I used the "RAND million normal digits and their deviant friends", and also block ciphers run in feedback modes (ie, as PRNGs). I've also got a parallel-port compatible geiger counter and a microcurie of americium, but i haven't careful studies on these yet. But they are cool toys :-) You will learn that you *always* have to distill raw bits. And you may observe that very few hardware RNGs actually monitor their output quality (especially on-line), though it seems to me you should. Also note that a 'loud' source of hiss is preferable. Were I using an acoustic microphone as my raw input, I would locate it next to the frother on my espresso machine and blow steam out of it, rather than counting on the wind or ambient brownian effects. Note that even using a highly structured signal (e.g., digitized video program including your local receiver noise) you could generate good bits, but you'd have to distill bushels of them. Have fun, randombit -----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Subject: Re: Random numbers from a sound card? Date: Tue, 26 Jan 1999 22:13:11 GMT From: ross@hypertools.com (David Ross) Message-ID: <36ae33b7.16083306@news.willapabay.org> References: <78l7je$cc6$1@nnrp1.dejanews.com> Newsgroups: sci.crypt Lines: 60 Randombit - Thanks for an informative post. On Tue, 26 Jan 1999 20:12:38 GMT, randombit@my-dejanews.com wrote: > ross@hypertools.com (David Ross) wrote: >> Has anyone had success using a sound card (like a Sound Blaster) to >> generate streams of random numbers? ... >> What sort of audio source would you suspect would be the best to use >> in generating random numbers? > >I used an old radio shack mono fm radio, with antenna removed, >tuned to hiss, at high volume, fed into the sound card. > >Later I got a video/radio digitizer, which I can tune to >FM hiss, which is more self contained. > >This produces an apparently uniformly distributed noise spectrum, >using a pc-based spectrum analyzer. > >But this doesn't have full entropy, and you have to distill (see >RFC 1750) the bits. I experimented with parity-of-N bits, >and used Maurer's Universal statistical test for RNGs to measure >the entropy. When you distill enough, the entropy reaches its >expected value. > >Some people might recommend a strong hashing function (e.g., a thousand >raw bits hashed with MD5 down to a fixed output size). This is >complex and I found unnecessary; simple parity works, though it >may waste more bits than a serious hash would. But bits are cheap, >and xor is fast. Lets say I'm digitizing a sine wave of constant frequency & amplitude. If it has a 1 Volt peak amplitude and if I digitize at a constant rate, won't 1/2 of my samples yield a value of either >+.707 Volt or < -.707 Volt? Seems like a built-in bias toward higher numbers... After looking at 'random' noise on an oscilloscope, I'd expect to see this same bias when digitizing noise... Digitizing either a sawtooth or a triangle waveform should get rid of this inbuilt bias, but where to find 'sawtooth noise' is beyond me. >> How would you test the 'quality' of the generated random number >> stream? >1. Marsaglia's Diehard suite of statistical (structure) tests. >2. Maurer's Universal statistical test >As "calibration standards" I used the "RAND million normal digits and their >deviant friends", and also block ciphers run in feedback modes (ie, >as PRNGs). Thanks for these suggestions. >Also note that a 'loud' source of hiss is preferable. A 'loud' source of hiss may put the range of the A->D converter down lower on a sinusoidal waveform. In this more linear area of the waveform, you would get a more even distribution of digitized values and begin to eliminate some of the inbuilt bias mentioned above. David Ross ross@hypertools.com
Subject: Re: Random numbers from a sound card? Date: Wed, 27 Jan 1999 18:09:54 GMT From: randombit@my-dejanews.com Message-ID: <78nkp9$bol$1@nnrp1.dejanews.com> References: <36ae33b7.16083306@news.willapabay.org> Newsgroups: sci.crypt Lines: 28 In article <36ae33b7.16083306@news.willapabay.org>, ross@hypertools.com (David Ross) wrote: > Lets say I'm digitizing a sine wave of constant frequency & > amplitude. If it has a 1 Volt peak amplitude and if I digitize at a > constant rate, won't 1/2 of my samples yield a value of either >+.707 > Volt or < -.707 Volt? Seems like a built-in bias toward higher > numbers... The threshold of your detector, which decides whether a voltage is to be called a 0 or a 1 (for this clock period), will determine your 0:1 bias. (In addition to your raw waveform's properties!) This threshold will interact with DC biases in your waveform. And both will drift, and differ between parts. You will not ever get perfect 0:1 ratios ---for instance, amplifiers may switch from 0->1 faster than 1->0 (even for CMOS) so you must plan for it. Happily, combining multiple bits (e.g., parity ) brings the ratio near 1:1 exponentially fast. Again, RFC 1750 is the bible. Shannon is the Prophet. -----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Subject: Re: Random numbers from a sound card? Date: Thu, 28 Jan 1999 18:10:41 GMT From: randombit@my-dejanews.com Message-ID: <78q96o$ka6$1@nnrp1.dejanews.com> References: <36AF1E85.280B09D4@stud.uni-muenchen.de> <78l7je$cc6$1@nnrp1.dejanews.com> Newsgroups: sci.crypt Lines: 32 In article <36AF1E85.280B09D4@stud.uni-muenchen.de>, Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de> wrote: > randombit@my-dejanews.com wrote: > > > > > Note that even using a highly structured signal (e.g., digitized > > video program including your local receiver noise) you could generate > > good bits, but you'd have to distill bushels of them. > > I find your experience interesting. (In another thread I suggested > obtaining good bit sequences from such materials as natural > language texts.) > > M. K. Shen > There is a big difference. Eve does not know the local, instantaneious electromagnetic conditions around my receiver, nor does she know what my local electronics are doing. The point is that measuring something physical is nothing like playing with text streams, unless you you get them via UDP and have a real bad link :-) ------------ "Properly done science is a sort of masochistic game where one beats one's head against a wall until it falls down, and then goes in search of another wall." --Steven Vogel -----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Subject: Re: Random numbers from a sound card? Date: Thu, 28 Jan 1999 19:54:22 +0100 From: Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de> Message-ID: <36B0B25E.9FD6F2A@stud.uni-muenchen.de> References: <78q96o$ka6$1@nnrp1.dejanews.com> Newsgroups: sci.crypt Lines: 22 randombit@my-dejanews.com wrote: > > There is a big difference. Eve does not know the local, instantaneious > electromagnetic conditions around my receiver, nor does she know what > my local electronics are doing. > > The point is that measuring something physical is nothing like > playing with text streams, unless you you get them via UDP and > have a real bad link :-) In principle you are right. However, I assume that the choice of the (publically known) texts that go into the process of generating the bit sequences is secret information and can't be guessed by the analyst. Thus, assuming adequate processing, one should obtain things appropriate for use. Of course, one does not generate in this way the legendary ideal OTP. But security is in my humble opinion an issue dependent also on the cost and the like and I believe that under certain real circumstances obtaining bit sequences from software can be justified. M. K. Shen
Subject: Re: Random numbers from a sound card? Date: Thu, 28 Jan 1999 21:36:44 GMT From: "patix" <patix@friko.onet.pl> Message-ID: <ML4s2.5136$014.554762@news.tpnet.pl> References: <78q96o$ka6$1@nnrp1.dejanews.com> Newsgroups: sci.crypt Lines: 27 randombit@my-dejanews.com wrote in message <78q96o$ka6$1@nnrp1.dejanews.com>... >In article <36AF1E85.280B09D4@stud.uni-muenchen.de>, > >There is a big difference. Eve does not know the local, instantaneious >electromagnetic conditions around my receiver, nor does she know what >my local electronics are doing. > >The point is that measuring something physical is nothing like >playing with text streams, unless you you get them via UDP and >have a real bad link :-) OK , but if she assume that it is 50Hz (Europe power) and let 30 KHz from Your monitor display , and if it happen to be true ? I have question:Haw should we test hardawre random generator to "be shoure" that it is realy some haw random ? patix
Subject: Re: Random numbers from a sound card? Date: 29 Jan 1999 08:44:58 -0500 From: juola@mathcs.duq.edu (Patrick Juola) Message-ID: <78se0q$or1$1@quine.mathcs.duq.edu> References: <78q96o$ka6$1@nnrp1.dejanews.com> Newsgroups: sci.crypt Lines: 25 In article <78q96o$ka6$1@nnrp1.dejanews.com>, <randombit@my-dejanews.com> wrote: >In article <36AF1E85.280B09D4@stud.uni-muenchen.de>, > Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de> wrote: >> randombit@my-dejanews.com wrote: >> > >> >> > Note that even using a highly structured signal (e.g., digitized >> > video program including your local receiver noise) you could generate >> > good bits, but you'd have to distill bushels of them. >> >> I find your experience interesting. (In another thread I suggested >> obtaining good bit sequences from such materials as natural >> language texts.) >> > >There is a big difference. Eve does not know the local, instantaneious >electromagnetic conditions around my receiver, nor does she know what >my local electronics are doing. No, but Mike does. He's fully capable of broadcasting (known) noise of some sort near your site. -kitten
Subject: Re: Random numbers from a sound card? Date: Tue, 26 Jan 1999 22:55:51 +0000 From: pla@sktb.demon.co.uk (Paul L. Allen) Message-ID: <f8pGhDj030n@sktb.demon.co.uk> References: <36AE059A.9BA@physiology.wisc.edu> <36acb8b1.5374650@news.willapabay.org> Newsgroups: sci.crypt Lines: 13 In article <36AE059A.9BA@physiology.wisc.edu> Medical Electronics Lab <rosing@physiology.wisc.edu> writes: > DIEHARD from Marsaglia I can never find a URL for that when I need it. I saw Marsglia posted his various PRNGs the other week and mentioned it but no URL. Actually, I am more interested in the accompanying docs than the actual tests right now. What a shame we can't get the FAQ updated. --Paul
Terry Ritter, his current address, and his top page.
Last updated: 1999-02-20