Ponder on this.

NOT random; PSEUDOrandom. Easily provable. Makes no difference if the cycle is 2^N long (large N), one of the keys is "cycle" - related to the length of the _ring_.

Async ring oscillators are not the same as pseudo-random shift registers. Ring oscillators are analog and drift/jitter all over the place, as whacked by Vcc, temperature, EMI from other circuits, and real electrical noise. A pseudo-random sequencer can be combined with such physical noise generators to clean up the statistics.

There are papers on using multiple ring oscillators as the basis for random number generators. On-chip, it's no big deal to make a few dozen async oscillators of various length, and mash up their outputs. On a pure-digital process, that's a good way to get randomness.

John

random

No, it's not.

random

So you are saying that the output may have a number repeated an arbitrary number of times? That zero may be repeated an arbitrary number of times? That (2^n-1) may be repeated an arbitrary number of times where n may be any integer? [[these are a few of the less obvious tests]]

random

I don't recall saying that.

John

random

Well, if that process truly generates random numbers, then those numbers must pass those and other tests. So....is the grass green?

random

Any random number generator that passes that test would have to have an arbitrarily long MTBF. And you'd have to test it for an arbitrarly large multiple of the age of the universe.

Seems to me that random numbers generated by a large number of physical processes, which include thermal drifts and Johnson noise, suitably mixed/hashed/scrambled, all done right, would pass any feasible test for randomness. Even if it is implemented inside an FPGA.

But a cryptographic-grade random number generator that never makes

There are papers on the subject, where people did the accepted math.

John

random

The math isn't the problem; it's the engineering (and of course, manufacturing).

random

Some of the papers reference chips that have over 100 free-running ring oscillators. They assume that maybe 25% of them might be locked (somehow, perhaps not at 1:1 ratios) at any one time. All will be whacked by several real, physical noise sources operating at widely differing time scales, picoseconds (Johnson and shot noise) to years (temperature, Vcc drift, cosmic rays, CMOS threshold changes, electromigration). I can't imagine that a few zener noise sources would be better.

Cosmic rays alone, hitting say 100,000 mosfets in 100 ring oscillators, would scramble things nicely. Or the occasional millikelvin temperature change.

This is *analog*, even inside an FPGA.

John

for random

Remember, you don't have to be able to predict the result, just reduce the universe of possible results, to break a cryptographic random number generator.

for random

I don't think so. Suppose you had a perfect random number generator, and wrote its values into a RAM. Now play the RAM over and over, so that the sequence repeats. Make the ram big enough for a repetition period of 1000 years. It's not random, but it's good enough.

Similarly, an analog noise based generator may not be perfect - it may have some autocorrelations on some time scales, maybe a little 1/f noise or something, but it's still unpredictable enough for any real-world application. After observing it for a while, you might be able to guess that the upcoming sequence might have a tiny bias of some sort, for some period of time.

Most physical noise generators benefit from some post-hashing.

John

for random

I know so. A "non-random" random number generator can (the simplest of a thousand errors) produce a colored the spectrum, weakening the cipher. With a design such as you propose, there is no way of knowing whether this has happened.

Yup!

Which is obfuscation.

Cryptographically strong random number generators are not as simple as you pretend.

for random

You wouldn't be able to ses the spectrum until you'd analyzed the sequence for many thousands of years. For the first millenium, it's perfectly random.

Sure. Hashing/scrambling can destroy small lingering autocorrelations, like you'd get from most physical processes. Done right, of course.

If all you need to do is generate unbreakable one-time pads, or generate random keys, it's not that hard to do. If you want to satisfy some of the more arcane theoretical tests for randomness, and you're willing to process *all* of the generated numbers for a few thousand years to see a weak correlation and yell GOTCHA!, then go for it.

Even a one-time pad, in actual use, will only expose a tiny burst of the output of a random number generator, xor'd with the plaintext. The bad guys don't get to see the continuous streaming output of the noise generator.

John

oscillators for random

the

I glad those who guard nuclear secrets and even banks are more paranoid than you!

"all"? That shows your complete lack of understanding, right there.

The less perfect the source the less perfect the pad.

...and I haven't even mentioned any active espionage inserted into the mix. Leave crypto stuff to the experts.

oscillators for random

papers

the

with

outputs.

OK, what other secure applications do you have in mind? Ones that will still be running a thousand years from now?

If it's unbreakable, it's perfect enough.

If the bad guys can access the random number sequence before it's xor'd with the payload, they'd probably be able to see the payload itself. Electronics is easy compared to social engineering.

John

oscillators for random

papers

the

the

with

for

outputs.

"Applications"? I was responding, with amazement, to "All you need to do...".

Which you don't know until someone does, *IF* they're nice enough to tell you. The chances are, they won't be.

Yep, "all you have to do"...

...is not use crypto designed on the Usenet. ;-)

for random

In particular with free running oscillators at various frequencies and in the same chip there is always the risk of entrainment. Some of the "variables" are then phase locked to each other and no longer independent and your apparent randomness could well be illusory.

IBM certainly know how to make notoriously weak random number generators that failed even the most basic tests eg. the infamous RANDU

Larkin would never spot this because he does not know enough mathematics to know what sorts of tests break random number generators. And by the sounds of it he subscribes strongly to the random algorithm approach which is well known to be extremely dodgy.

One way is to do a two generated bits to one output to ensure that there is never a detectable long term bias for 1 or 0. Usually XOR

Faster RNGs use a lowpass filtered feedback loop to remove any long term

He doesn't know enough mathematics to make sensible comments.

It is lucky that nothing he does depends on cryptographically strong RNGs. Even experts sometimes make tiny mistakes which permit clever attacks and is how certain French bank cards and Oyster cards were defeated (and incidentally many secure buildings entry cards).

Regards, Martin Brown

oscillators for random

the

That's why people use hundreds of them. Even if some phase lock, the phase lock pairings will hop around continuously, another sort of chaos. I've seen papers that asumed 25% would be locked at any instant, which seems pessimistic to me.

A moderately long ring oscillator in an FPGA would have an around-the-ring prop delay TC in the hundreds of picoseconds per degree C, so its frequency would be very unstable. And each oscillator would be different, due to routing and process variations. There would also be serious delay/frequency dependencies on Vcc. We build digital delay generators and have to really fight the effects of temperature, Vcc, routing, and crosstalk to get delay TCs below, say, 10 ps/K and jitter down into a few 10s of ps RMS... over deliberately short-as-possible paths. All those things become assets when you want to make random numbers.

Really, FPGAs are nasty, noisy, drifty analog parts.

As I notes several times, there are papers available on the use of multiple async ring oscillators to generate random numbers. And they do the math. Argue with them.

Another way is to xor the random data into the guts of a LFSR, to make it jump states often.

Again, do the analog noise source, and its scrambler, hundreds of times.

Those comments weren't sensible?

All I hear from you guys is generalities about how hard it is. No suggestions of actual implementation, or of circuit details.

I sort of invented another form of chaotic oscillator, suited to FPGA implememtation, that involves charging and discharging an external capacitor hung on a pin. But ring oscillators are probably more practical.

I'm talking about circuits to generate random numbers, not cryptographic algorithms. DES for example, and weak public-key systems, can be cracked by brute force, independent of the randomness of the key.

John

Interesting. Suppose you use a JPG picture file as a one time pad, and filter out any known standard sequences, long strings of 1s and 0s, etc. and just left the data?

Would that be random? How would it be broken?

-Bill