John Larkin wrote:


There are lots of digital chips, including some Intel processors, that
have cryptographic-grade random number generators on-chip.

One of the main features of the cryptography grade RNG is the self test
subsystem that continuously monitors that 1) RNG is in the good health
2) RNG had not been tampered with. If there is no such subsystem, the
RNG is consumer or amateur grade, not cryptography grade.

One common
technique is to use a bunch of asynchronous ring oscillators to
scramble pseudo-random shift registers. Lots of references on the web.

Just to remember that a deterministic function over the random number
don't add to the randomness. So the output hash should not generate more
of the scrambled bits then the true entropy of the random source.

I have a technique that uses an i/o pin as a noisy/chaotic RC ramp
generator. Fun, but essentially useless.

I used to measure the timing of self charge/discharge of the uncommited
MCU input to set up the seed for the PRNG for the rolling code.


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

On Sun, 24 Oct 2010 11:21:04 -0500, Vladimir Vassilevsky
wrote:



John Larkin wrote:


There are lots of digital chips, including some Intel processors, that
have cryptographic-grade random number generators on-chip.

One of the main features of the cryptography grade RNG is the self test
subsystem that continuously monitors that 1) RNG is in the good health
2) RNG had not been tampered with. If there is no such subsystem, the
RNG is consumer or amateur grade, not cryptography grade.

One common
technique is to use a bunch of asynchronous ring oscillators to
scramble pseudo-random shift registers. Lots of references on the web.

Just to remember that a deterministic function over the random number
don't add to the randomness. So the output hash should not generate more
of the scrambled bits then the true entropy of the random source.

Post-hashing can remove any 1/0 (DC) bias and remove other
autocorrelations as a physical source tends to have. Do all that a
dozen times, as you can in an FPGA, and things get pretty good.

Things are more interesting if you XOR *into* a pseudo-random shift
register, instead of merely with the output of one.



I have a technique that uses an i/o pin as a noisy/chaotic RC ramp
generator. Fun, but essentially useless.

I used to measure the timing of self charge/discharge of the uncommited
MCU input to set up the seed for the PRNG for the rolling code.

Similar idea, but I would keep using it. Hanging a cap on the pin
helps. If the discharge time is short and is itself a function of
random values, the combination of discharge time feedback, threshold
uncertainty, dielectric absorption, and cap TC (use a really bad cap)
add to the fun.

John

John Larkin wrote:

On Sun, 24 Oct 2010 11:21:04 -0500, Vladimir Vassilevsky
wrote:
John Larkin wrote:



There are lots of digital chips, including some Intel processors, that
have cryptographic-grade random number generators on-chip.

One of the main features of the cryptography grade RNG is the self test
subsystem that continuously monitors that 1) RNG is in the good health
2) RNG had not been tampered with. If there is no such subsystem, the
RNG is consumer or amateur grade, not cryptography grade.


One common
technique is to use a bunch of asynchronous ring oscillators to
scramble pseudo-random shift registers. Lots of references on the web.

Just to remember that a deterministic function over the random number
don't add to the randomness. So the output hash should not generate more
of the scrambled bits then the true entropy of the random source.

Post-hashing can remove any 1/0 (DC) bias and remove other
autocorrelations as a physical source tends to have. Do all that a
dozen times, as you can in an FPGA, and things get pretty good.

Yes, the post processing obfuscates the obvious dependencies, but it
can't generate more of the entropy then the entropy of the source.

Things are more interesting if you XOR *into* a pseudo-random shift
register, instead of merely with the output of one.

Again, you can't make more randomness by mixing random states with
deterministic states. Although this procedure adds some "salt" to the
common PRNG.

I have a technique that uses an i/o pin as a noisy/chaotic RC ramp
generator. Fun, but essentially useless.

I used to measure the timing of self charge/discharge of the uncommited
MCU input to set up the seed for the PRNG for the rolling code.

Similar idea, but I would keep using it. Hanging a cap on the pin
helps. If the discharge time is short and is itself a function of
random values, the combination of discharge time feedback, threshold
uncertainty, dielectric absorption, and cap TC (use a really bad cap)
add to the fun.

VLV

Michael A. Terrell wrote:
John Larkin wrote:
On Fri, 22 Oct 2010 00:53:55 -0400, "Michael A. Terrell"
wrote:

Jim Thompson wrote:
I'd like to conjure up a random bit generator.

Just feed it a clock and have it generate random bits.

74HC... components preferred... I have most everything in that family
in my parts bin ;-)

XOR some of Sloman's messages. ;-)
Those aren't very random. He keeps saying the same stuff, over and
over.


If you XOR enough of them, the typos add up into a random mess.

The preferred method of guaranteeing ranDUMB bits, is make like a
witch and HEX-or them...

Vladimir Vassilevsky wrote:


Robert Baer wrote:
Vladimir Vassilevsky wrote:


There is approximately a zillion of ways of making quazi random (or
true random) generator from whatever stuff you got in the drawers.

One CANNOT compute (or generate from logic) a truly random number.

Sure you can. Just make a long enough daisy chain of logic gates and
compute a logic function from the input and the output of the chain. Now
apply a clock to the input. As pulse propagates through the chain, the
RMS jitter will add up and the output of the function will be truly
random. Ring Oscillators are the other example, but they are asynchronous.

Now, quasi-random number generators are a dime a dozen, like you imply.

Oh, I forgot to mention the whole class of PRNGs where one counter acts
as a source of the clock for the other counter. That is simple and
allows generation of the variety of random looking sequencies.


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com
Nope! An infinite number of gates has yet to be made.
One of the attributes of a large set of truly random numbers is the
fact that ANY sequence can be repeated, again and again - but not for an
infinite period.

On Sun, 24 Oct 2010 14:37:00 -0700, Robert Baer
wrote:

Vladimir Vassilevsky wrote:


Robert Baer wrote:
Vladimir Vassilevsky wrote:


There is approximately a zillion of ways of making quazi random (or
true random) generator from whatever stuff you got in the drawers.

One CANNOT compute (or generate from logic) a truly random number.

Sure you can. Just make a long enough daisy chain of logic gates and
compute a logic function from the input and the output of the chain. Now
apply a clock to the input. As pulse propagates through the chain, the
RMS jitter will add up and the output of the function will be truly
random. Ring Oscillators are the other example, but they are asynchronous.

Now, quasi-random number generators are a dime a dozen, like you imply.

Oh, I forgot to mention the whole class of PRNGs where one counter acts
as a source of the clock for the other counter. That is simple and
allows generation of the variety of random looking sequencies.


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com
Nope! An infinite number of gates has yet to be made.
One of the attributes of a large set of truly random numbers is the
fact that ANY sequence can be repeated, again and again - but not for an
infinite period.

---
If a neverending sequence is truly random, then the possibility exists
that it can repeat forever.


---
JF

John Larkin wrote:

Relay pullin time and bounce would make a nice randomizer, too.

I am not sure how many random bits could be extracted from one click of
a relay. Once I tested reed relay for life expectancy; the bounce
pattern looked very repeatable. BTW, the life term appeared to be not so
great: somewhat 500K cycles or so.

Unclocked ring oscillators are not deterministic. They will drift all
over the place with time, temperature, tiny Vcc variations, thermal
noise, and EMI from other sources. CMOS oscillators have ghastly phase
noise.

Agreed. Typical RMS jitter ~ 1% of the period, and a big part of it is
due to the unpredictable noise of the components.

The external RC thing can be made truly random, too.

Random, in this context, means that future states can't be predicted,
even given total knowledge of the hardware and the current state.
Which means that bad guys can never decode the pattern.

One should be very careful with the assesment of the amount of the true
random information. It is easy to make a RNG which could seem very solid
from first glance, but it would fail to the basic analysis.


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

On Sun, 24 Oct 2010 20:27:17 -0500, Vladimir Vassilevsky
wrote:



John Larkin wrote:

Relay pullin time and bounce would make a nice randomizer, too.

I am not sure how many random bits could be extracted from one click of
a relay. Once I tested reed relay for life expectancy; the bounce
pattern looked very repeatable. BTW, the life term appeared to be not so
great: somewhat 500K cycles or so.

If you timed the bounces to ns resolution, they would be pretty noisy.
Temperature, vibration, coil voltage variations, all sorts of things
would vary the timing and bounce details. Of course, using a relay for
making random numbers is a whimsy, not a very practical idea.

I agree about reeds. Even at low switching levels, they aren't very
reliable.

John

John Fields wrote:
On Sun, 24 Oct 2010 14:37:00 -0700, Robert Baer
wrote:

Vladimir Vassilevsky wrote:

Robert Baer wrote:
Vladimir Vassilevsky wrote:

There is approximately a zillion of ways of making quazi random (or
true random) generator from whatever stuff you got in the drawers.
One CANNOT compute (or generate from logic) a truly random number.
Sure you can. Just make a long enough daisy chain of logic gates and
compute a logic function from the input and the output of the chain. Now
apply a clock to the input. As pulse propagates through the chain, the
RMS jitter will add up and the output of the function will be truly
random. Ring Oscillators are the other example, but they are asynchronous.

Now, quasi-random number generators are a dime a dozen, like you imply.
Oh, I forgot to mention the whole class of PRNGs where one counter acts
as a source of the clock for the other counter. That is simple and
allows generation of the variety of random looking sequencies.


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com
Nope! An infinite number of gates has yet to be made.
One of the attributes of a large set of truly random numbers is the
fact that ANY sequence can be repeated, again and again - but not for an
infinite period.

---
If a neverending sequence is truly random, then the possibility exists
that it can repeat forever.


---
JF
Not quite..the _probability_ of any repetition is related to the
bitlength under observtion, factored into all of the other possible groups.
Repeat N times, and the probability, starting near zero, gets so
small that the engineering zero is most likely larger..