Toaster to Generate Random Numbers

45 views
Skip to first unread message

Omar Bohsali

unread,
Jan 8, 2003, 4:51:36 PM1/8/03
to
Hello.

Is it possible to use thermal noise to generate random numbers.

My idea is the following:

Get a toaster, and measure the noise generated by it. Amplify the noise, and
then have it digitized by a program that will turn it into numbers.

One question still lingers in my plan:

Is thermal noise random?

Some people say that it is, some say that it isn't.

Please enlighten me.

--
Thank You,

Omar Bohsali
http://www.omarbohsali.com
"There are 10 types of people in this world. People who understand Binary,
and people who don't"

fungus

unread,
Jan 8, 2003, 5:02:09 PM1/8/03
to
Omar Bohsali wrote:
> Hello.
>
> Is it possible to use thermal noise to generate random numbers.
>
> My idea is the following:
>
> Get a toaster, and measure the noise generated by it. Amplify the noise, and
> then have it digitized by a program that will turn it into numbers.
>

Is it a good idea to have a toaster turned on 24/7?

I'm sure most toasters will burn out pretty fast
if you try it.


> Please enlighten me.
>

Try this instead: http://www.lavarnd.org/

Any moving image will do - paper streamers
blowing in a fan, feed the result into a
cheap webcam and hash the result.


--
<\___/>
/ O O \
\_____/ FTB.

lurker

unread,
Jan 8, 2003, 5:36:47 PM1/8/03
to

So is this a "think different" type of question? Usually when we
think about gathering entropy from thermal noise we are talkikg about
sillicon chips or diodes.

Casey Schaufler

unread,
Jan 8, 2003, 6:59:08 PM1/8/03
to
Omar Bohsali wrote:
>
> Hello.
>
> Is it possible to use thermal noise to generate random numbers.
>
> My idea is the following:
>
> Get a toaster, and measure the noise generated by it. Amplify the noise, and
> then have it digitized by a program that will turn it into numbers.

Be careful not to step on the LavaRand patients.
Yes, someone has a patient on gathering random
numbers by pointing digital cameras at a set of
lava lamps. Your notion might infringe on that
patient in that it differs only by the wavelength
of radiation measured.

--

Casey Schaufler Manager, Trust Technology, SGI
ca...@sgi.com voice: 650.933.1634
cas...@pager.sgi.com Pager: 877.557.3184

Paul Pires

unread,
Jan 8, 2003, 8:00:00 PM1/8/03
to

Casey Schaufler <ca...@sgi.com> wrote in message news:3E1CBB4C...@sgi.com...

> Omar Bohsali wrote:
> >
> > Hello.
> >
> > Is it possible to use thermal noise to generate random numbers.
> >
> > My idea is the following:
> >
> > Get a toaster, and measure the noise generated by it. Amplify the noise, and
> > then have it digitized by a program that will turn it into numbers.
>
> Be careful not to step on the LavaRand patients.
> Yes, someone has a patient on gathering random
> numbers by pointing digital cameras at a set of
> lava lamps. Your notion might infringe on that
> patient in that it differs only by the wavelength
> of radiation measured.

This is good an example of why spell checkers are the spawn
of the devil. They don't fix errors, they just make them consistent.

Have patience my son.

Paul

Carlos Moreno

unread,
Jan 8, 2003, 8:11:37 PM1/8/03
to

Omar Bohsali wrote:

> Hello.
>
> Is it possible to use thermal noise to generate random numbers.
>
> My idea is the following:
>
> Get a toaster, and measure the noise generated by it. Amplify the noise, and
> then have it digitized by a program that will turn it into numbers.
>
> One question still lingers in my plan:
>
> Is thermal noise random?
>
> Some people say that it is, some say that it isn't.


The discussion is mostly philosophical. Most (sane) people
should agree that thermal noise can be considered random
for all practical purposes from any conceivable point of
view.

Now, the "philosophical" argument could be based on the
doubt if thermal noise is a signal truly unpredictable, or
if it is just that we don't have the capacity to predict it.

In fact, even more philosophically, some could argue that
"randomness" does not exist in nature, and that it is only
a theoretical concept in our minds. Everything is predictable,
only that there are many things for which we don't have the
means or the capacity or the knowledge necessary to predict
it, so we call them "random", "unpredictable".

After all, one could argue that given the *exact* values
for *all* the phisical parameters (speed, position,
electrical charge, etc.) of every single particle or point
of matter one second after the "big bang", then you could
(theoretically speaking) determine the *exact* state of
the universe *at any given time* (i.e., position and
speed of *every* single particle in the universe).

Sad notion, isn't it?

Carlos
--


Ant

unread,
Jan 8, 2003, 8:26:50 PM1/8/03
to
"Paul Pires" <dio...@got.net> wrote in message
news:nyOdnRKzRtJ...@got.net...

>
> Casey Schaufler <ca...@sgi.com> wrote in message
news:3E1CBB4C...@sgi.com...
> > Omar Bohsali wrote:
> > >
> > > Hello.
> > >
> > > Is it possible to use thermal noise to generate random numbers.
> > >
> > > My idea is the following:
> > >
> > > Get a toaster, and measure the noise generated by it. Amplify the noise,
and
> > > then have it digitized by a program that will turn it into numbers.
> >
> > Be careful not to step on the LavaRand patients.
> > Yes, someone has a patient on gathering random
> > numbers by pointing digital cameras at a set of
> > lava lamps. Your notion might infringe on that
> > patient in that it differs only by the wavelength
> > of radiation measured.
>
> This is good an example of why spell checkers are the spawn
> of the devil. They don't fix errors, they just make them consistent.
>
> Have patience my son.
>
> Paul

LOL! I propose the use of newsgroup noise.


John Elsbury

unread,
Jan 8, 2003, 8:35:53 PM1/8/03
to
On Wed, 8 Jan 2003 16:51:36 -0500, "Omar Bohsali"
<omarb...@omarbohsali.com> wrote:

>Hello.
>
>Is it possible to use thermal noise to generate random numbers.

Yes. To get useful results in a decent timeframe, however, you would
have to look at the variability of the temperature of the thermal
source over time, which (I guess) depends to some extent on its mass.
Most implementations I am aware of use noise from a noise diode or
transistor junction operated at somewhere over it's breakdown voltage.
Alternatively you could use any thermionic valve (tube) or a neon,
etc. as a noise source or even something like a geiger counter or
similar particle detector.

I expect, if you do a google search on "schematic random noise
generator" you should get some ideas.
>

<snip wacky toaster idea>

Benjamin Goldberg

unread,
Jan 8, 2003, 8:52:59 PM1/8/03
to
Carlos Moreno wrote:
[snip]

> After all, one could argue that given the *exact* values
> for *all* the phisical parameters (speed, position,
> electrical charge, etc.) of every single particle or point
> of matter one second after the "big bang", then you could
> (theoretically speaking) determine the *exact* state of
> the universe *at any given time* (i.e., position and
> speed of *every* single particle in the universe).
>
> Sad notion, isn't it?

Supposing for a moment that you could build a "universe simulator" to
make this determination -- obviously, you're trying to measure how
things are "now", so you'd have to run the simulator up to the point in
time that we exist -- some problems, and questions arise:

1/ Is possible to run the simulated universe faster than the passage
of time of the actual universe? I suspect not.

2/ Would the simulated humans in the simulated universe be "real
people," with souls as real as our own?

3/ Assuming that there is a God, and that miracles *have* happened
(at least one miracle from at least one holy book), wouldn't that mean
that to make the simulated universe behave the same as our own did, we
would have to create miracles in the simulated universe, precisely the
same as God's miracles in our own real universe?

4/ If everything is determinable, do we have free will?

5/ If we could somehow run the simulator faster than the real
universe, then could we simulate the present and the future? (Keeping
in mind that to simulate the near past and the present, the simulator
would need to be simulating itself!)

--
$..='(?:(?{local$^C=$^C|'.(1<<$_).'})|)'for+a..4;
$..='(?{print+substr"\n !,$^C,1 if $^C<26})(?!)';
$.=~s'!'haktrsreltanPJ,r coeueh"';BEGIN{${"\cH"}
|=(1<<21)}""=~$.;qw(Just another Perl hacker,\n);

Bill Unruh

unread,
Jan 8, 2003, 8:44:58 PM1/8/03
to
"Omar Bohsali" <omarb...@omarbohsali.com> writes:

]Hello.

]Is it possible to use thermal noise to generate random numbers.

]My idea is the following:

]Get a toaster, and measure the noise generated by it. Amplify the noise, and
]then have it digitized by a program that will turn it into numbers.

??? a toaster? What aspect of the toaster do you plan on measuring to
get the noise?

Anyway, run a DC current through a resistor and measure the voltage.
This will give you a variety of noises. Some (1/f) have long time scale
correlations, some (higher frequency) is pretty white in spectrum.


]One question still lingers in my plan:

]Is thermal noise random?

No physical source is "random". They all have biases, correlations, etc.
You can work to get rid of them. Exactly how predictable they make the
noise is a different question. Ie, you might have a correlation which
affects say 1 bit out of 100 if you do not work very hard (ie 99 bits of
"randomness" per 100 bits).

]Some people say that it is, some say that it isn't.

]Please enlighten me.

Alun Jones

unread,
Jan 8, 2003, 8:48:28 PM1/8/03
to
In article <avik6q$cii$1...@nntp.itservices.ubc.ca>, un...@string.physics.ubc.ca (Bill Unruh) wrote:
>??? a toaster? What aspect of the toaster do you plan on measuring to
>get the noise?

Spread sardines on the toast, and you'll have a nice poisson distribution :-)

Alun.
~~~~

[Please don't email posters, if a Usenet response is appropriate.]
--
Texas Imperial Software | Try WFTPD, the Windows FTP Server. Find us at
1602 Harvest Moon Place | http://www.wftpd.com or email al...@texis.com
Cedar Park TX 78613-1419 | VISA/MC accepted. NT-based sites, be sure to
Fax/Voice +1(512)258-9858 | read details of WFTPD Pro for XP/2000/NT.

lurker

unread,
Jan 8, 2003, 8:56:26 PM1/8/03
to

Wouldn't this scenario require a Bell's theorem/many worlds structure
to the cosmos that had every possible branching possibility happening
some where/time?

Andrew Swallow

unread,
Jan 8, 2003, 9:06:06 PM1/8/03
to
"Benjamin Goldberg" <gol...@earthlink.net> wrote in message
news:3E1CD5FB...@earthlink.net...
> Carlos Moreno wrote:
> [snip]
[snip]

>
> 3/ Assuming that there is a God, and that miracles *have* happened
> (at least one miracle from at least one holy book), wouldn't that mean
> that to make the simulated universe behave the same as our own did, we
> would have to create miracles in the simulated universe, precisely the
> same as God's miracles in our own real universe?
>

Sounds like a job for the debug package. Adjust the appropriate variables
and array enrties.

> 4/ If everything is determinable, do we have free will?
>

In computer games players can make the characters go through doors
and climb ladders. The characters cannot go through walls. God
probably developed similar rules for us.

> 5/ If we could somehow run the simulator faster than the real
> universe, then could we simulate the present and the future? (Keeping
> in mind that to simulate the near past and the present, the simulator
> would need to be simulating itself!)
>

Recursive simulations!

Andrew Swallow

Alun Jones

unread,
Jan 8, 2003, 9:23:53 PM1/8/03
to
In article <avij86$q2$1...@newsg3.svr.pol.co.uk>, "Ant" <n...@home.today> wrote:
>LOL! I propose the use of newsgroup noise.

Wouldn't help - it's obviously non-random.

Paul Crowley

unread,
Jan 8, 2003, 10:25:08 PM1/8/03
to
al...@texis.com (Alun Jones) writes:

> In article <avij86$q2$1...@newsg3.svr.pol.co.uk>, "Ant" <n...@home.today> wrote:
> >LOL! I propose the use of newsgroup noise.
>
> Wouldn't help - it's obviously non-random.

I'm not sure of that at all! :-)

(Seriously, the reason not to rely on newsgroup noise in a
cryptographic context is that it's available to your attacker...)
--
__ Paul Crowley
\/ o\ s...@paul.ciphergoth.org
/\__/ http://www.ciphergoth.org/

Joerg Woelke

unread,
Jan 8, 2003, 9:38:43 PM1/8/03
to
Hi!

Carlos Moreno wrote:

[ snip ]

> Now, the "philosophical" argument could be based on the
> doubt if thermal noise is a signal truly unpredictable, or
> if it is just that we don't have the capacity to predict it.

I always thought radioactive decay is random.
"http://www.fourmilab.ch/hotbits/"

> Carlos

Greets, J"o!

--
sigfault

johnekus

unread,
Jan 8, 2003, 11:47:31 PM1/8/03
to
Why would a toaster be any better at deriving random sequences than anyone
else.

Just because a guy can address an audience at a wedding and make a few good
comments about the guests of honor doesn't necessarily make him a better
random sequence generator.

Daaaauuuh!

JK

http://www.crak.com

Home of Gulpit, the packet sniffer for the masses


"Omar Bohsali" <omarb...@omarbohsali.com> wrote in message
news:avi6h7$5tj$1...@bob.news.rcn.net...

johnekus

unread,
Jan 8, 2003, 11:50:34 PM1/8/03
to
I am only going to say this one more time...


The best random number generator is a set of AOL CD_ROMs hanging from
strings in front of colored lights.

You point a fan at the whole deal, use a web cam to sample the colors and
mix all the data using Yarrow.

http://www.crak.com

Home of Gulpit the packet sniffer for the masses.

JK

"Omar Bohsali" <omarb...@omarbohsali.com> wrote in message
news:avi6h7$5tj$1...@bob.news.rcn.net...

Michael Amling

unread,
Jan 9, 2003, 8:22:19 AM1/9/03
to
johnekus wrote:
> The best random number generator is a set of AOL CD_ROMs hanging from
> strings in front of colored lights.
>
> You point a fan at the whole deal, use a web cam to sample the colors and
> mix all the data using Yarrow.

It would be cheaper to just point the fan at a microphone.

--Mike Amling

Mark H. Wood

unread,
Jan 9, 2003, 9:36:54 AM1/9/03
to
In comp.security.misc Carlos Moreno <moreno_at_mo...@xx.xxx> wrote:
>
> Omar Bohsali wrote:
>
>> Hello.
>>
>> Is it possible to use thermal noise to generate random numbers.

Intel seems to think so. See the Pentium 4 datasheet.

[snippage]


> Now, the "philosophical" argument could be based on the
> doubt if thermal noise is a signal truly unpredictable, or
> if it is just that we don't have the capacity to predict it.

How, exactly, could we possibly know the difference? (Since we're
being "philosophical" here.)

> In fact, even more philosophically, some could argue that
> "randomness" does not exist in nature, and that it is only
> a theoretical concept in our minds. Everything is predictable,
> only that there are many things for which we don't have the
> means or the capacity or the knowledge necessary to predict
> it, so we call them "random", "unpredictable".

Both Newtonian and relativistic mechanics are founded on this idea.
It works well on large scale. Dynamics is full of results which show
a surprising amount of order in apparently "random" behavior.

> After all, one could argue that given the *exact* values
> for *all* the phisical parameters (speed, position,

Heisenberg argued that you cannot know both concurrently on the small
scale, and he seems to be right.

> electrical charge, etc.) of every single particle or point
> of matter one second after the "big bang", then you could
> (theoretically speaking) determine the *exact* state of
> the universe *at any given time* (i.e., position and
> speed of *every* single particle in the universe).

David Gerrold wrote a story (_When HARLIE Was One_) featuring a
machine which could model the Universe exactly, but the problem was
that it (necessarily) runs in slower than real time. So it turns out
that the best way to know what the Universe is going to do is to watch
it and see. :-P

--
Mark H. Wood, Lead System Programmer mw...@IUPUI.Edu
MS Windows *is* user-friendly, but only for certain values of "user".

Mark H. Wood

unread,
Jan 9, 2003, 9:44:48 AM1/9/03
to
In comp.security.misc Benjamin Goldberg <gol...@earthlink.net> wrote:
[snip]

> Supposing for a moment that you could build a "universe simulator" to
> make this determination -- obviously, you're trying to measure how
> things are "now", so you'd have to run the simulator up to the point in
> time that we exist -- some problems, and questions arise:
>
> 1/ Is possible to run the simulated universe faster than the passage
> of time of the actual universe? I suspect not.
>
> 2/ Would the simulated humans in the simulated universe be "real
> people," with souls as real as our own?

Alternately, what does that say about the reality of souls? or the
meaning of "reality"? (Are you uncomfortable yet?)

> 3/ Assuming that there is a God, and that miracles *have* happened
> (at least one miracle from at least one holy book), wouldn't that mean
> that to make the simulated universe behave the same as our own did, we
> would have to create miracles in the simulated universe, precisely the
> same as God's miracles in our own real universe?

3.1: Does that mean that the person operating the simulation is God
in the simulated universe, since he created it and exercises
intimate control over all aspects of its operation? How do you feel
*now*?

> 4/ If everything is determinable, do we have free will?

If we don't, it doesn't matter since there is really nobody here.

> 5/ If we could somehow run the simulator faster than the real
> universe, then could we simulate the present and the future? (Keeping
> in mind that to simulate the near past and the present, the simulator
> would need to be simulating itself!)

Ah, here we go! See Goedel's Incompleteness Theorem. (There's a
nicely accessible exposition on incompleteness, infinite recursion,
and other tasty aspects of self-reference in Douglas Hofstadter's book
_Goedel, Escher, Bach: an Eternal Golden Braid_. It's also a very
good read.)

Mark H. Wood

unread,
Jan 9, 2003, 10:07:33 AM1/9/03
to
In comp.security.misc Andrew Swallow <am.sw...@eatspam.btinternet.com> wrote:
> "Benjamin Goldberg" <gol...@earthlink.net> wrote in message
> news:3E1CD5FB...@earthlink.net...
> [snip]
>>
>> 3/ Assuming that there is a God, and that miracles *have* happened
>> (at least one miracle from at least one holy book), wouldn't that mean
>> that to make the simulated universe behave the same as our own did, we
>> would have to create miracles in the simulated universe, precisely the
>> same as God's miracles in our own real universe?
>>
>
> Sounds like a job for the debug package. Adjust the appropriate variables
> and array enrties.

Ooh, see Diane Duane's "Young Wizards" books, with magicians running
around tweaking the "kernels" of various universes. (_The Wizard's
Dilemma_ especially, but start with _So You Want to Be a Wizard_ or
you'll be missing some background material.)

Barry Margolin

unread,
Jan 9, 2003, 10:33:40 AM1/9/03
to
In article <3E1CCC49...@xx.xxx>,

Carlos Moreno <moreno_at_mo...@xx.xxx> wrote:
>The discussion is mostly philosophical. Most (sane) people
>should agree that thermal noise can be considered random
>for all practical purposes from any conceivable point of
>view.

For crypto purposes, the issue isn't whether it's random, but whether it's
"random enough" -- i.e. are there enough random bits to be useful in
seeding an RNG? This depends, of course, on how precisely we're able to
measure the temperature -- the most randomness is in the low-order bits, so
the more precisely we can measure, the more low-order bits we have. But
more precise measurements also entails more expensive equipment, so there
will be a tradeoff between crypto strength and cost.

--
Barry Margolin, bar...@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.

Casey Schaufler

unread,
Jan 9, 2003, 12:08:17 PM1/9/03
to
Paul Pires wrote:
>
> Casey Schaufler <ca...@sgi.com> wrote in message news:3E1CBB4C...@sgi.com...
> > Omar Bohsali wrote:
> > >
> > > Hello.
> > >
> > > Is it possible to use thermal noise to generate random numbers.
> > >
> > > My idea is the following:
> > >
> > > Get a toaster, and measure the noise generated by it. Amplify the noise, and
> > > then have it digitized by a program that will turn it into numbers.
> >
> > Be careful not to step on the LavaRand patients.
> > Yes, someone has a patient on gathering random
> > numbers by pointing digital cameras at a set of
> > lava lamps. Your notion might infringe on that
> > patient in that it differs only by the wavelength
> > of radiation measured.
>
> This is good an example of why spell checkers are the spawn
> of the devil. They don't fix errors, they just make them consistent.
>
> Have patience my son.

As it turns out my spelling of any given word has been shown to
be sufficiently random as to qualify as a cryptographicly strong
random number seed. At least I used real words this time!

For some time the Amdahl Unix (remember them?) man page for
ispell was noted as "dedacaded to Casey Schaufler". Good fun.

lurker

unread,
Jan 9, 2003, 12:36:53 PM1/9/03
to

Since detection of random noise is a serial process shouldn't you use
more than one toaster/detector combo to flatten the distribution?
>

Bill Unruh

unread,
Jan 9, 2003, 12:42:59 PM1/9/03
to
Carlos Moreno <moreno_at_mo...@xx.xxx> writes:


]Omar Bohsali wrote:

]The discussion is mostly philosophical. Most (sane) people


]should agree that thermal noise can be considered random
]for all practical purposes from any conceivable point of
]view.

No, it is not. The noise structure of "thermal noise"-- eg the noise
coming from a resistor with a constant current source across it, has
correlations, especially at long times (1/f noise). Furthermore, stray
capacitances, inductances, etc, also introduce correlations into the
noise. All physical systems have such correlations. Some are well
understood, some not. Such correlations mean that the source is NOT
"random" (ie, uncorrelated white noise-- or each bit value equal
probablility 1 and 0 and no correlations between bits).


Scott Nelson

unread,
Jan 9, 2003, 1:03:53 PM1/9/03
to
On Wed, 8 Jan 2003 16:51:36 -0500, "Omar Bohsali"
<omarb...@omarbohsali.com> wrote:

>Hello.
>
>Is it possible to use thermal noise to generate random numbers.
>

>My idea is the following:
>
>Get a toaster, and measure the noise generated by it. Amplify the noise, and
>then have it digitized by a program that will turn it into numbers.
>

>One question still lingers in my plan:
>
>Is thermal noise random?
>
>Some people say that it is, some say that it isn't.
>
>Please enlighten me.

Your first step on the path to enlightenment:
DON'T CROSS POST THIS KIND OF QUESTION.

All noise is in a sense random, that's why we call it "noise".

Our best physics models say that heat is the result of
molecular motion, and molecular motion is dependant on
particles which are subject to quantum uncertainties.
Thermal noise is therefore subject to quantum effects,
_if you attempt to measure it with enough precision_.

But most thermal detectors measure collections of molecules,
and the collections exceed 1,000,000,000,000,000,000 in number.
At that scale, truly unpredictable results are rare.

But as long as one is willing to measure the temperature
for a long time, and distill the information down sufficiently,
it's possible to get high quality randomness, even with a
toaster and a glass thermometer.


Scott Nelson <sc...@helsbreth.org>

Douglas A. Gwyn

unread,
Jan 9, 2003, 12:18:56 PM1/9/03
to
Guy Macon wrote:
> If I put it anywhere in the universe, I have to update the
> universe simulator to simulate a universe with a universe
> simulator in it. Then I have to update the universe
> simulator to simulate a universe with a universe simulator
> that simulates a universe with a universe simulator in it.

Why not simulate a universe containing the contrary
simulator.

Mok-Kong Shen

unread,
Jan 9, 2003, 1:50:31 PM1/9/03
to

Do you think that with unbiasing and further xor-ing
a sufficient number of such sequences is a satisfactory
solution?

M. K. Shen

Bill Unruh

unread,
Jan 9, 2003, 2:36:14 PM1/9/03
to
Mok-Kong Shen <mok-ko...@t-online.de> writes:

Maybe. The original may well be good enough already ( are you really
worried if the effective entropy of 100 bits is really only that of 99
bits? )
Biasing is an easy one to handle. Other correlations can be more
difficult to detect and eliminate. If you understand your noise stream,
then correcting it for such correlations is not hard. It is the
understanding that can be hard.

]M. K. Shen

Alun Jones

unread,
Jan 9, 2003, 3:56:03 PM1/9/03
to
In article <87hecjg...@saltationism.subnet.hedonism.cluefactory.org.uk>,
Paul Crowley <pa...@JUNKCATCHER.ciphergoth.org> wrote:
>al...@texis.com (Alun Jones) writes:
>
>> In article <avij86$q2$1...@newsg3.svr.pol.co.uk>, "Ant" <n...@home.today> wrote:
>> >LOL! I propose the use of newsgroup noise.
>>
>> Wouldn't help - it's obviously non-random.
>
>I'm not sure of that at all! :-)
>
>(Seriously, the reason not to rely on newsgroup noise in a
>cryptographic context is that it's available to your attacker...)

Although not reliably, and not necessarily in the same order as your own.

The non-randomness comes from a few things:

1. Spam, which can be relied upon to repeat itself hugely.
2. The use of English language almost exclusively.
3. Headers and other formatting items that cause repeatable patterns.

It's possible that you could strip out much of the non-random portions of
Usenet, but I can't see it as something you could reliably use, even for an
application where randomness is required, but you don't care whether an
outsider gets the same random data as you.

Barry Margolin

unread,
Jan 9, 2003, 4:38:39 PM1/9/03
to
In article <DllT9.305$NT1.12...@newssvr11.news.prodigy.com>,

Alun Jones <al...@texis.com> wrote:
>In article <87hecjg...@saltationism.subnet.hedonism.cluefactory.org.uk>,
>Paul Crowley <pa...@JUNKCATCHER.ciphergoth.org> wrote:
>>al...@texis.com (Alun Jones) writes:
>>
>>> In article <avij86$q2$1...@newsg3.svr.pol.co.uk>, "Ant" <n...@home.today> wrote:
>>> >LOL! I propose the use of newsgroup noise.
>>>
>>> Wouldn't help - it's obviously non-random.
>>
>>I'm not sure of that at all! :-)
>>
>>(Seriously, the reason not to rely on newsgroup noise in a
>>cryptographic context is that it's available to your attacker...)
>
>Although not reliably, and not necessarily in the same order as your own.
>
>The non-randomness comes from a few things:
>
>1. Spam, which can be relied upon to repeat itself hugely.
>2. The use of English language almost exclusively.
>3. Headers and other formatting items that cause repeatable patterns.
>
>It's possible that you could strip out much of the non-random portions of

Maybe the result of compressing the posts would be a better seed, as
compression should remove much of the redundancy.

>Usenet, but I can't see it as something you could reliably use, even for an
>application where randomness is required, but you don't care whether an
>outsider gets the same random data as you.

Although the outsider has access to all the messages, he doesn't know which
messages you digested and in which order you scanned them to produce your
random seed. Also, there's quite a bit of server-specific data, such as
article numbers, and Path and Xref headers, so unless he's using the same
news server as you are he won't get the same results.

Walter Roberson

unread,
Jan 9, 2003, 4:56:12 PM1/9/03
to
In article <3e1db2a1...@netnews.worldnet.att.net>,
lurker <n...@nospam.org> wrote:
:Since detection of random noise is a serial process shouldn't you use

:more than one toaster/detector combo to flatten the distribution?

As we are talking about toasters, detection of random noise
would be a *cereal* process. To change the distribution, use
a different grain of bread ;-)
--
Rump-Titty-Titty-Tum-TAH-Tee -- Fritz Lieber

lurker

unread,
Jan 9, 2003, 6:11:08 PM1/9/03
to
On 9 Jan 2003 21:56:12 GMT, robe...@ibd.nrc-cnrc.gc.ca (Walter
Roberson) wrote:

Can you substitute hash browns for bread?

Guy Macon

unread,
Jan 9, 2003, 7:35:55 PM1/9/03
to


Barry Margolin wrote:

>For crypto purposes, the issue isn't whether it's random, but whether it's
>"random enough" -- i.e. are there enough random bits to be useful in
>seeding an RNG? This depends, of course, on how precisely we're able to
>measure the temperature -- the most randomness is in the low-order bits, so
>the more precisely we can measure, the more low-order bits we have. But
>more precise measurements also entails more expensive equipment, so there
>will be a tradeoff between crypto strength and cost.

While it is true that more precision entails more expensive equipment,
Using an analog high-pass filter and amplifier will cheaply move those
low order bits higher. It's not too hard to amplify and measure the
noise if you don't mind losing the signal on the way.

--
Email Guy Macon guymacon+YOUR NAME GOES HE...@spamcop.net <html><head></head>
<body><a href="http://www.guymacon.com/resume.html" >Electrical engineer</a>
for hire: Los Angeles / Orange County CA USA 714-670-1687 See my resume at
http://www.guymacon.com/resume.html .</body><html><!-- www.guymacon.com -->

Guy Macon

unread,
Jan 9, 2003, 7:44:39 PM1/9/03
to


Bill Unruh wrote:

> The noise structure of "thermal noise"-- eg the noise
> coming from a resistor with a constant current source across it, has
> correlations, especially at long times (1/f noise).

There is a problem with the theory that resistors have 1/f noise.
What is the amplitude of the signal at DC? At very, very close
to DC? Are the real-world answers really infinty and very, very
large?

Of course it would take forever to answer the first question with
an experiment and a very, very long time to answer the second.

Guy Macon

unread,
Jan 9, 2003, 7:49:56 PM1/9/03
to


Barry Margolin wrote:

>Although the outsider has access to all the messages, he doesn't know which
>messages you digested and in which order you scanned them to produce your
>random seed. Also, there's quite a bit of server-specific data, such as
>article numbers, and Path and Xref headers, so unless he's using the same
>news server as you are he won't get the same results.

In other word, you randomly picked a newsserver and randomly picked
the articles to process, keeping those decisions secret. Have you
really increased the entropy over that of the RNG you used to do
the choosing?

Barry Margolin

unread,
Jan 9, 2003, 8:27:19 PM1/9/03
to
In article <v1s65ur...@corp.supernews.com>,

Guy Macon <. http://www.guymacon.com/resume.html .> wrote:
>Barry Margolin wrote:
>
>>Although the outsider has access to all the messages, he doesn't know which
>>messages you digested and in which order you scanned them to produce your
>>random seed. Also, there's quite a bit of server-specific data, such as
>>article numbers, and Path and Xref headers, so unless he's using the same
>>news server as you are he won't get the same results.
>
>In other word, you randomly picked a newsserver and randomly picked
>the articles to process, keeping those decisions secret. Have you
>really increased the entropy over that of the RNG you used to do
>the choosing?

I think so.

Suppose you have an RNG that chooses a random integer from 1 to 10. You
keep the past 10 days of newspapers, and use this number to select which of
them to digest to seed your random number sequence.

At first glance this doesn't seem to be any better -- you're just selecting
among 10 random number sequences, which you could just as easily do with
the original integer. But the difference is that the function changes
every day. If the simple RNG produces 1 today and 1 tomorrow, you'll get
different sequences.

I admit that I'm not a mathematician and I haven't done a detailed
analysis. The above example is really simple and has flaws (e.g. 1 today
is the same as 2 tomorrow), but I expect that it could be improved upon to
produce good results (e.g. when a newspaper is used, take it out of the set
so that it won't be used again).

Paul Crowley

unread,
Jan 9, 2003, 9:25:05 PM1/9/03
to
al...@texis.com (Alun Jones) writes:
> The non-randomness comes from a few things:
>
> 1. Spam, which can be relied upon to repeat itself hugely.
> 2. The use of English language almost exclusively.
> 3. Headers and other formatting items that cause repeatable patterns.
>
> It's possible that you could strip out much of the non-random portions of
> Usenet, but I can't see it as something you could reliably use, even for an
> application where randomness is required, but you don't care whether an
> outsider gets the same random data as you.

You don't need to strip out the non-random portions. Just estimate
the entropy conservatively and hash the lot, repetition and all. See
the Yarrow paper for a discussion...

Phil Fites

unread,
Jan 9, 2003, 6:37:37 AM1/9/03
to
No, no, no. Everyone knows it was a really hot cup of black tea
that provided the randomness that led to the Infinite
Improbability Drive... :-)

Omar Bohsali wrote:

> Hello.
>
> Is it possible to use thermal noise to generate random numbers.
>
> My idea is the following:
>
> Get a toaster, and measure the noise generated by it. Amplify the noise, and
> then have it digitized by a program that will turn it into numbers.
>
> One question still lingers in my plan:
>
> Is thermal noise random?
>
> Some people say that it is, some say that it isn't.
>
> Please enlighten me.
>

> --


> Thank You,
>
> Omar Bohsali
> http://www.omarbohsali.com

Carlos Moreno

unread,
Jan 10, 2003, 10:41:11 AM1/10/03
to

Benjamin Goldberg wrote:

> Carlos Moreno wrote:
> [snip]


>
>>After all, one could argue that given the *exact* values
>>for *all* the phisical parameters (speed, position,

>>electrical charge, etc.) of every single particle or point
>>of matter one second after the "big bang", then you could
>>(theoretically speaking) determine the *exact* state of
>>the universe *at any given time* (i.e., position and
>>speed of *every* single particle in the universe).
>>

>>Sad notion, isn't it?


>>
>
> Supposing for a moment that you could build a "universe simulator" to
> make this determination -- obviously, you're trying to measure how
> things are "now", so you'd have to run the simulator up to the point in
> time that we exist -- some problems, and questions arise:
>
> 1/ Is possible to run the simulated universe faster than the passage
> of time of the actual universe? I suspect not.
>
> 2/ Would the simulated humans in the simulated universe be "real
> people," with souls as real as our own?
>

> 3/ Assuming that there is a God, and that miracles *have* happened
> (at least one miracle from at least one holy book), wouldn't that mean
> that to make the simulated universe behave the same as our own did, we
> would have to create miracles in the simulated universe, precisely the
> same as God's miracles in our own real universe?
>

> 4/ If everything is determinable, do we have free will?
>

> 5/ If we could somehow run the simulator faster than the real
> universe, then could we simulate the present and the future? (Keeping
> in mind that to simulate the near past and the present, the simulator
> would need to be simulating itself!)


Well, you kind of agree with me in that this is a *philosophical*
debate, and not a scientific/practical one :-)

A few comments:

I'm not talking about building a machine that will calculate
everything; I'mtalking about *the calculability* itself;
yes, we can not possibly measure every phisical parameter
of every single particle and/or point of matter of the
Universe. But assuming that, at a given time, every single
particle of the Universe *does have* a given value for each
of those parameters, then the philosophical question is:
would those values be sufficient information to determine
*everything* about every single particle of the universe at
*any given time*? (past or future)

From the "purely scientific" (i.e., atheist :-)) point
of view, I would argue "yes" (or at least, I would say
"I tend to believe yes until proven the contrary" -- but
since the contrary can not be proven -- neither this
argument -- then I'll stick to my "philosophical" belief
that it is (would be) possible).

Heisenberg said that the exact position and velocity
can not be known at the same time. *Even if that were
true* (which I don't believe for a second that it is;
after all, Newton said that F=m*a, and someone in the
late 1800s said "Heavier-than-air flying machines are
impossible to build", etc.), that [Heisenberg's principle]
doesn't necessarily mean that the position and speed
do not have certain exact values at a given time; the
way I see it, it means that there is no way for us to
determine those (exact) values (since determining
them would imply that some other particle has to
interact with them, and thus affect the values).


As for your point 4... Why is it so hard to believe
that we do not really have free will?? Free will may
be an extremely abstract concept that lives only in
our "cognitive" ways of perceiving the universe...

I mean, after all, the exact position and state of
my body and my mind 1 minute from now will be one
and only one. Whatever it is, *it will be* that
particular *one* set of values; not two, not three
(yeah, we could talk about three possibilities; but
only one will happen -- the one that happens). That
I can not know it right now, that's a different thing.
And that part of it will involve all of the molecules
interactions that happened inside my brain to take
the decisions that will lead to that state [that we
call "free will"], that's another thing -- but it is
also part of that future state. We want to call it
free will, because that's how we perceive it. We
make a decision, and we cause the future to go one
way or another -- but is that decision the cause?
Or is it the effect? (of the state of the zillions
of molecules of our brain, that had a given position
and speed and parameters which are deterministically
going to produce a certain chain of events)

Look at it from this point of view... Let's define
a truly random process as it is "mathematically"
defined. So, there is the random process, and there
are particular realizations of that process... Would
you say that a particular realization of that process
is a random process?? I would say it's not. It is
one particular realization (that from the practical
point of view you could call it random because one
might not have sufficient information or capacity
to predict things, that's another thing).

So, you could say that "reality" (i.e., the current
state of the entire universe) as a function of time
*is one and only one* realization of the presumably
random process that is "reality".... So, what's
truly random about it??

Sure, from our (practical) point of view, the future
does have randomnes, given the ridiculously impossible
that would be to predict it by "calculating" things
based on the position and speed of every single
particle (we don't even need to go as far as to
prove that building such universe simulator is
impossible :-)).

Yes, all the above discussion assumes that the
Universe *does follow* certain rules (call them
Physics, mathematics, etc.), and that those rules
have no exception (regardless of whether or not
we know those rules, or if it is possible at all
to know/understand those rules given the structure
and the capacity of our brains/minds). So, in other
words, I'm arguing that all the above discussion
makes sense only if there is no God, or if there
is, then that God(s) created those "rules" and will
unconditionally stick to the "non violation" of
those rules. (the "miracles" that religions talk
about *may* be based on the rules of the universe,
BTW :-) -- how do you define a "miracle"? I
would define it as something that my current
knowledge about the rules of the universe does
not allow me to understand it :-))

Carlos Moreno

unread,
Jan 10, 2003, 10:52:39 AM1/10/03
to

Bill Unruh wrote:


I think you have a misconception here... (though I wonder if it
is me who has the misconception).

To me, the definition of "random" (if there is one), involves
*only* unpredictability and lack of any fixed pattern.

Uniformly distributed and uncorrelated are different things
(they imply stronger requirements).

In other words, having a higher probability of taking one
particular value still doesn't make it predictable. (i.e.,
you still can not predict if three consecutive coin tosses
will produce at least one head -- you could systematically
state it as your "prediction", and you will be right more
often than wrong... But you did not *predict* the outcome,
and the fact that you get three tails or not *is still* a
random variable).

Now, of course, for many applications (including particularly
cryptography), non-uniformly distributed random sources are
useless (unless you can process them and extract as much
uniformly-distributed data as possible). But that's a
practical consideration; despite thermal noise exhibiting
certain correlation characteristics, *it is* still random
(well, philosophical discussions aside :-)). And of course,
as you say, in most practical cases, the correlation exhibited
by thermal noise is almost sure below the practical limit
of observability, and/or would not affect the system for
which we're using it on.

Carlos
--

Barry Margolin

unread,
Jan 10, 2003, 11:01:34 AM1/10/03
to
In article <3E1EE997...@xx.xxx>,

Carlos Moreno <moreno_at_mo...@xx.xxx> wrote:
>I mean, after all, the exact position and state of
>my body and my mind 1 minute from now will be one
>and only one. Whatever it is, *it will be* that
>particular *one* set of values; not two, not three
>(yeah, we could talk about three possibilities; but
>only one will happen -- the one that happens).

The Many-Universes interpretation of Quantum Mechanics is based on the idea
that *all* the possibilities happen. At each decision point, the universe
splits up into different universes, each with different results.

So Schrodinger's Cat really is both dead and alive, but in different
universes. Opening the box allows you to find out which universe you're
in. But meanwhile, in one of the other universes, the other you is opening
the box and finding out something different.

Barry Margolin

unread,
Jan 10, 2003, 11:17:36 AM1/10/03
to
In article <3E1EEC47...@xx.xxx>,

Carlos Moreno <moreno_at_mo...@xx.xxx> wrote:
>Now, of course, for many applications (including particularly
>cryptography), non-uniformly distributed random sources are
>useless (unless you can process them and extract as much
>uniformly-distributed data as possible).

If you know the nature of the correlation, it seems like it should not be
too difficult to create an algorithm to remove that component of the raw
data to produce a random stream with the properties you want.

Also, I intuitively expect that these correlations are minimized if you
measure precisely enough and only use the low-order bits. E.g. firefly
flashes and women's periods are known to sync up, but I presume it's only
at low-precision measurements; if you measure fireflies to .1-second
precision and women living together to 1-day preciseion, high correlations
will be seen, but not if you measure them to the microsecond and use the
lowest 2 decimal places.

I suppose it's possible that some of these correlations take place at the
quantum level, so that they'll appear at all precisions that we're able to
measure.

Alun Jones

unread,
Jan 10, 2003, 11:30:44 AM1/10/03
to
In article <3E1D5F6F...@rogers.com>, Phil Fites <fi...@rogers.com> wrote:
>No, no, no. Everyone knows it was a really hot cup of black tea
>that provided the randomness that led to the Infinite
>Improbability Drive... :-)

Strictly speaking, the cup of hot tea was only a convenient generator of
brownean motion. Any observable brownean motion source could presumably do
the same. Going back to the toaster, you could watch the dust motes as they
fly into and out of the turbulent stream of hot air above the toaster.

How long before someone adds the concept of a "self-winding watch" and
smart-card, and produces a smart-card whose randomness is generated by however
many 'jigs' or 'jogs' it gets in the carrier's pocket? Absolutely no use for
a server, but great for a personal identification card!

Carlos Moreno

unread,
Jan 10, 2003, 11:46:14 AM1/10/03
to

Carlos Moreno wrote:

>
> [...]


Ooops, how rude of me! I didn't even sign the
message! :-)

Cheers,

Carlos
--


Barry Margolin

unread,
Jan 10, 2003, 12:01:18 PM1/10/03
to
In article <UyCT9.110$Bh3.13...@newssvr12.news.prodigy.com>,

Alun Jones <al...@texis.com> wrote:
>How long before someone adds the concept of a "self-winding watch" and
>smart-card, and produces a smart-card whose randomness is generated by however
>many 'jigs' or 'jogs' it gets in the carrier's pocket? Absolutely no use for
>a server, but great for a personal identification card!

Sounds like a neat idea. Quick, apply for the patent!

If the card has a keypad for entering a PIN (like SecurID cards), perhaps
it could instead incorporate pressure sensitivity. The high-order bits
could be used as a biometric authenticator (users are probably pretty
consistent about how hard they press the keys, and differ enough for it to
be a useful authenticator when combined with the knowledge of the PIN),
while the low-order bits could be used by the RNG.

Jonathan Day

unread,
Jan 10, 2003, 12:13:45 PM1/10/03
to
"Omar Bohsali" <omarb...@omarbohsali.com> wrote in message news:<avi6h7$5tj$1...@bob.news.rcn.net>...

> Hello.
>
> Is it possible to use thermal noise to generate random numbers.

Yes, it is. The most trivial way to demonstrate this is to get a
highly precice Analog to Digital Converter and connect it to
nothing. No input signal at all. The drift on the lowest bits are
caused by a mix of thermal noise and voltage instability.

The function to estimate this noise is:

(Forecasted weather * Actual Weather) % (Latest Opinion Poll)

Bill Unruh

unread,
Jan 10, 2003, 1:24:16 PM1/10/03
to
Barry Margolin <bar...@genuity.net> writes:

]In article <v1s65ur...@corp.supernews.com>,

]I think so.

So, you say that the randomness is not just the integers 1 to 10 but
also which day you apply it to. Of course narrowing down the day is not
that hard, so the randomness added by "which day" is not that great.
Ie, this is not a randomness amplification process.

Barry Margolin

unread,
Jan 10, 2003, 1:31:47 PM1/10/03
to
In article <avn34g$o9c$1...@nntp.itservices.ubc.ca>,

Bill Unruh <un...@string.physics.ubc.ca> wrote:
>So, you say that the randomness is not just the integers 1 to 10 but
>also which day you apply it to. Of course narrowing down the day is not
>that hard, so the randomness added by "which day" is not that great.
>Ie, this is not a randomness amplification process.

But in the case of using the news spool as the noise source, there's also
the fact that every site's news spool is different (so the perpetrator
would have to have access to your news spool), and constantly changing as
news flows in (so he would have to know the precise moment that you took
the snapshot).

Bill Unruh

unread,
Jan 10, 2003, 1:33:50 PM1/10/03
to
Carlos Moreno <moreno_at_mo...@xx.xxx> writes:


]Bill Unruh wrote:

]> Carlos Moreno <moreno_at_mo...@xx.xxx> writes:
]>
]> ]Omar Bohsali wrote:
]>
]> ]The discussion is mostly philosophical. Most (sane) people
]> ]should agree that thermal noise can be considered random
]> ]for all practical purposes from any conceivable point of
]> ]view.
]>
]> No, it is not. The noise structure of "thermal noise"-- eg the noise
]> coming from a resistor with a constant current source across it, has
]> correlations, especially at long times (1/f noise). Furthermore, stray
]> capacitances, inductances, etc, also introduce correlations into the
]> noise. All physical systems have such correlations. Some are well
]> understood, some not. Such correlations mean that the source is NOT
]> "random" (ie, uncorrelated white noise-- or each bit value equal
]> probablility 1 and 0 and no correlations between bits).


]I think you have a misconception here... (though I wonder if it
]is me who has the misconception).

]To me, the definition of "random" (if there is one), involves
]*only* unpredictability and lack of any fixed pattern.

Correlations imply predictability. If your height is correlated with
your weight, knowing your height I can predict your weight with better
than "random".


]Uniformly distributed and uncorrelated are different things
](they imply stronger requirements).

No, if it is not uniformly distributed (ie biased) then you can use that
information to predict with better than random certainty wha tthe next
number is. If you have correlations you can use them to make
predictions as well.

]In other words, having a higher probability of taking one


]particular value still doesn't make it predictable. (i.e.,
]you still can not predict if three consecutive coin tosses
]will produce at least one head -- you could systematically
]state it as your "prediction", and you will be right more
]often than wrong... But you did not *predict* the outcome,
]and the fact that you get three tails or not *is still* a
]random variable).

The question is not complete confidence, the question is whether the
procedure is better than "exhaustive search". By predictability in a
cryptographic sense is not meant deterministic predictability, but
probabilistic is also good. If a cryptographer could show that he could
use the last 10 entries in an RC4 stream to change the probablility of
the next output from completely random, this would be a form or "break"
of RC4. Of course the stronger the correlation the more predictable. If
the probablilities are only changed from uniform to say a 1/1000 bias,
this may not matter much, but a cryptographer would worry about it.
oAll of the "card counting " schemes to beat Las Vegas only change the
probabilities by a tiny amount, but they are enough to make you rich.

]Now, of course, for many applications (including particularly


]cryptography), non-uniformly distributed random sources are
]useless (unless you can process them and extract as much
]uniformly-distributed data as possible). But that's a
]practical consideration; despite thermal noise exhibiting
]certain correlation characteristics, *it is* still random
](well, philosophical discussions aside :-)). And of course,

Sorry at what level of correlation does it cease being "random" in your
definition. If only one bit in 10^12 is unpredictable is the system
still random?


]as you say, in most practical cases, the correlation exhibited


]by thermal noise is almost sure below the practical limit
]of observability, and/or would not affect the system for
]which we're using it on.

Probably true, and if you know about it, you can distill randomness out
of a correlated system. But you need to know about it.

]Carlos
]--

Bill Unruh

unread,
Jan 10, 2003, 1:37:57 PM1/10/03
to
Barry Margolin <bar...@genuity.net> writes:

]In article <3E1EEC47...@xx.xxx>,


]Carlos Moreno <moreno_at_mo...@xx.xxx> wrote:
]>Now, of course, for many applications (including particularly
]>cryptography), non-uniformly distributed random sources are
]>useless (unless you can process them and extract as much
]>uniformly-distributed data as possible).

]If you know the nature of the correlation, it seems like it should not be
]too difficult to create an algorithm to remove that component of the raw
]data to produce a random stream with the properties you want.

Sure, if you know them. The problem is people being told "A is random"
and not knowing about the biases and correlations.


]Also, I intuitively expect that these correlations are minimized if you


]measure precisely enough and only use the low-order bits. E.g. firefly
]flashes and women's periods are known to sync up, but I presume it's only
]at low-precision measurements; if you measure fireflies to .1-second
]precision and women living together to 1-day preciseion, high correlations
]will be seen, but not if you measure them to the microsecond and use the
]lowest 2 decimal places.

Actually I would not trust the low order bits in a piece of measuring
apparatus, since they could well be correlated due to the nature of the
measuring apparatus.

Know your source, and use it wisely -- this is about the best I would
say.

]I suppose it's possible that some of these correlations take place at the

Bill Unruh

unread,
Jan 10, 2003, 1:40:09 PM1/10/03
to
Guy Macon <. http://www.guymacon.com/resume.html .> writes:


]Bill Unruh wrote:

]> The noise structure of "thermal noise"-- eg the noise
]> coming from a resistor with a constant current source across it, has
]> correlations, especially at long times (1/f noise).

]There is a problem with the theory that resistors have 1/f noise.
]What is the amplitude of the signal at DC? At very, very close
]to DC? Are the real-world answers really infinty and very, very
]large?

]Of course it would take forever to answer the first question with
]an experiment and a very, very long time to answer the second.


1/f noise is very very poorly understood. The experimental fact is that
almost all systems which have been measured for a "very very " long
time, show 1/f noise, and there is no indication that it disappears at
"very very very" long times.

Barry Margolin

unread,
Jan 10, 2003, 2:25:11 PM1/10/03
to
In article <avn3u5$ojb$1...@nntp.itservices.ubc.ca>,

Bill Unruh <un...@string.physics.ubc.ca> wrote:
>Barry Margolin <bar...@genuity.net> writes:
>
>]In article <3E1EEC47...@xx.xxx>,
>]Carlos Moreno <moreno_at_mo...@xx.xxx> wrote:
>]>Now, of course, for many applications (including particularly
>]>cryptography), non-uniformly distributed random sources are
>]>useless (unless you can process them and extract as much
>]>uniformly-distributed data as possible).
>
>]If you know the nature of the correlation, it seems like it should not be
>]too difficult to create an algorithm to remove that component of the raw
>]data to produce a random stream with the properties you want.
>
>Sure, if you know them. The problem is people being told "A is random"
>and not knowing about the biases and correlations.

There have been several messages saying that thermal noise is 1/f. Well, I
don't know what that means, but I assumed it was the kind of knowledge that
would be useful in filtering out the correlation.

>Actually I would not trust the low order bits in a piece of measuring
>apparatus, since they could well be correlated due to the nature of the
>measuring apparatus.

Good point. And I presume the same may be true for an amplifier (one of
the other posts mentioned that you can get the low-order bits of a
measurement using a high-pass filter and then an amplifier).

Barry Margolin

unread,
Jan 10, 2003, 2:20:43 PM1/10/03
to
In article <avn3me$ohg$1...@nntp.itservices.ubc.ca>,

Bill Unruh <un...@string.physics.ubc.ca> wrote:
>oAll of the "card counting " schemes to beat Las Vegas only change the
>probabilities by a tiny amount, but they are enough to make you rich.

That's only because the house's advantage to begin with was tiny. But if
the house has a huge advantage, then adjusting the probabilities by a tiny
amount would still make the house a winner, but just by a smaller amount.

A simple Caesar cipher is like casino odds. All you need is a little edge,
like a table of letter and digraph frequencies (e.g. ETAOIN SHRDLU for
English), and you can easily crack the messages.

But most real codes are much harder than that, analogous to a casino with
huge house odds, aren't they? If you discover a bias that reduces cracking
time by 10%, but typical cracking time is 10 months, then it's *still* 9
months, which is OK. Unless the bias reduces the strength of the crypto
scheme by an order of magnitude, it's probably not a real problem.

Paul Crowley

unread,
Jan 10, 2003, 4:25:09 PM1/10/03
to
Barry Margolin <bar...@genuity.net> writes:
> There have been several messages saying that thermal noise is 1/f. Well, I
> don't know what that means, but I assumed it was the kind of knowledge that
> would be useful in filtering out the correlation.

There's no need to filter out the correlation. Just make a
conservative estimate of the entropy and feed all the raw data
straight to Yarrow:

http://www.counterpane.com/yarrow.html

Bill Unruh

unread,
Jan 10, 2003, 5:19:54 PM1/10/03
to
Barry Margolin <bar...@genuity.net> writes:

]In article <avn3me$ohg$1...@nntp.itservices.ubc.ca>,


]Bill Unruh <un...@string.physics.ubc.ca> wrote:
]>oAll of the "card counting " schemes to beat Las Vegas only change the
]>probabilities by a tiny amount, but they are enough to make you rich.

]That's only because the house's advantage to begin with was tiny. But if
]the house has a huge advantage, then adjusting the probabilities by a tiny
]amount would still make the house a winner, but just by a smaller amount.

]A simple Caesar cipher is like casino odds. All you need is a little edge,
]like a table of letter and digraph frequencies (e.g. ETAOIN SHRDLU for
]English), and you can easily crack the messages.

]But most real codes are much harder than that, analogous to a casino with
]huge house odds, aren't they? If you discover a bias that reduces cracking
]time by 10%, but typical cracking time is 10 months, then it's *still* 9
]months, which is OK. Unless the bias reduces the strength of the crypto
]scheme by an order of magnitude, it's probably not a real problem.


Sure. The question was whether physical process X was a good source of
random numbers. I have no idea what he wants them for. If it is to
decide whether to have eggs or ham for breakfast, then using his toaster
to decide is fine, no matter what the biases are. If he wants to use it
to design an online high volume betting game, the demands may well be
much more stringent. To decide he has to know how to balance the
possible correlations in the physical process and their effect on his
random stream against his use of that that stream. If he thinks he can
just plug his computer into his toaster and get a completely
unpredictable stream, then he is wrong. That does not mean it is not
good enough for what he wants. After all RC4 is terrible non-random
(only say 256 bits of randomness even in an output of 10^5 bits), but
it is good enough to hide secrets for most applications.
The correlations in physical sources tend to be much more linear than
the correlations in say RC4. Running the physical system through MD5
say, will make those linear correlations highly non-linear, and very
hard to use, and may even remove them altogether ( randomness
distillation).

I would suspect that measuing the noise out of a resistor with a
constant current source driving it, and then feeding the bits through
say MD5 with a 2-1 compression (ie 256 bits in for each 128 bits out)
would be wonderfully random for all applications-- until of course
someone decided to use only the high order bit of the voltage from the
resistor, with a perfect correlation over time.

Bill Unruh

unread,
Jan 10, 2003, 5:25:33 PM1/10/03
to
Barry Margolin <bar...@genuity.net> writes:

]In article <avn3u5$ojb$1...@nntp.itservices.ubc.ca>,


]Bill Unruh <un...@string.physics.ubc.ca> wrote:
]>Barry Margolin <bar...@genuity.net> writes:
]>
]>]In article <3E1EEC47...@xx.xxx>,
]>]Carlos Moreno <moreno_at_mo...@xx.xxx> wrote:
]>]>Now, of course, for many applications (including particularly
]>]>cryptography), non-uniformly distributed random sources are
]>]>useless (unless you can process them and extract as much
]>]>uniformly-distributed data as possible).
]>
]>]If you know the nature of the correlation, it seems like it should not be
]>]too difficult to create an algorithm to remove that component of the raw
]>]data to produce a random stream with the properties you want.
]>
]>Sure, if you know them. The problem is people being told "A is random"
]>and not knowing about the biases and correlations.

]There have been several messages saying that thermal noise is 1/f. Well, I
]don't know what that means, but I assumed it was the kind of knowledge that
]would be useful in filtering out the correlation.

No, thermal noise has a 1/f component to it at low frequencies. (This
means that there are long time correlations in the output of the noise).
And yes, knowing they are there, and estimating them or measuring them,
allows you to "remove them". But you have to know you have them to
remove them.

Thermal noise from a resistor does not just have 1/f correlations. It
also has other correlations as well (eg stray capacitances/inductance in the
system introduce correlations, dead times in A-D converters introduce
other correlations, etc).


]>Actually I would not trust the low order bits in a piece of measuring

Bill Unruh

unread,
Jan 10, 2003, 5:30:53 PM1/10/03
to
Paul Crowley <pa...@JUNKCATCHER.ciphergoth.org> writes:

]Barry Margolin <bar...@genuity.net> writes:
]> There have been several messages saying that thermal noise is 1/f. Well, I
]> don't know what that means, but I assumed it was the kind of knowledge that
]> would be useful in filtering out the correlation.

]There's no need to filter out the correlation. Just make a
]conservative estimate of the entropy and feed all the raw data
]straight to Yarrow:

Yarrow is a PRNG. Its purpose is effective (though not thoeretical)
randomness amplification. The output of yarrow can be no more random
than the input.

What you really want is randomness distillation (ie given N bits with r
bits of effective redundnacy in those N bits, to produce a set of N-r
bits bits with no redundancy. ) not randomness amplification. (given N
bits produce M>>N bits of output which are "pseudo" random.

As I said, I think taking the output of the physical process, and then
feeding it through a cryptographic hash is probably (I have no proof) a
wonderful distillation process.


]http://www.counterpane.com/yarrow.html

Paul Crowley

unread,
Jan 10, 2003, 9:25:09 PM1/10/03