Hardware RNG (measures AC mains chaos to make random numbers)

[Sceadwian]

The problem with the entire concept of a random number being 'not predictable' is that that is impossible to start from; all random numbers depend on some form of predictability it's impossible to avoid, you can obfuscate it out of human comprehension and make it very difficult mathematically (to the point of being practically impossible) but there will always be some method of determining the value given a set of known conditions otherwise there is no method that could be used to generate the numbers to begin with.

It's basic if you think about it logically. How can you define a number without having a way to define the number? It just can't happen.

 

[misterT]

Accidental double post, sorry.

 

[misterT]

The problem with the entire concept of a random number being 'not predictable' is that that is impossible to start from

The problem with predictability is that you would have to know all the information history and that is impossible to start from.

you can obfuscate it out of human comprehension and make it very difficult mathematically

Mathematics obfuscate things out of human comprehension? I always thought mathematics was the way to make logical sense of things.

How can you define a number without having a way to define the number?

No way.. but there can be random events without numbers.

 

[()blivion]

The problem with predictability is that you would have to know all the information history and that is impossible to start from.

When saying this you quote Sceadwian, but doesn't that also have implications for part of what I was talking about? I though you only needed to know the complete quantum state of a system at any given time, to be able to know it's future states? and that the past was largely irreverent?

For example, if I flip a coin hundreds of times, and it appears to be perfect 50/50 odds, then I flip it five more times and it lands on heads each time, then the odds of it landing on heads the sixth time are still 50/50. Because the systems pattern is still 50/50 chances, regardless of it's past history or states. Or is that apples and oranges from the discussion?

 

[Sceadwian]

The problem with predictability is that you would have to know all the information history and that is impossible to start from

This is not a problem in deterministic systems.

All deterministic systems require that. The only reason this is a problem from the human perspective is even though we live in a deterministic world we can no predict it. This is our failure not the system.

There is no possibility of a quantum effect without a waveform collapse or waveform interaction, until a collapse/interaction nothing can exist, but for anything to exist an interaction/collapse must occur, something must be able to be defined from the pure function. To observe an effect defines the event/Waveforms that created it within a certain degree of error of measurement, this is in and of itself is basic quantum theory.

 

[Sceadwian]

It's apples and oranges from the discussion, the state of an object can not be removed from it's history.

 

[Mr RB]

What is it good for then? I mean what are the potential uses of pure random data.. I have some in mind (monte carlo methods, compressed sensing.. etc.), but those can be done perfectly well with pseudo RNG.
...

Glad you could pop in MisterT. The main use is for making seed tables or smallish password strings. You are familiar with my software Black PRNG and using it to generate large amounts of high quality data, and my other project the hardware encryption dongle we discussed here in another thread. So ideally the simple little hardware RNG would be used to generate data sets with an extremely high unpredictability byte to byte. The problem with using standard PRNGs for making seed tables is that while their data quality is good there are processes that correlate each byte to the ones before it, that just doesn't occur in a hardware RNG. So hardware RNGs offer slightly reduced data quality but (hopefully) have perfect unpredictability.

I was under the impression that there was the the real random part, coming from the mains line sensing... then some PRNG firmware in the PIC? I guess we are not talking about your OTHER PIC RNG stuff eh? So your saying the random number component is fed raw into a PC for further use?...

Yes. Please read my page! It outputs the 3 actual PIC hardware timer LSB bits, triggered from different mains cycles, hashed together and then sent out raw to the PC via serial. It's just raw entropy with no math processes added.

I was under the impression that we were gathering our data from inside/under the noise floor? Even though mains is high current/voltage and low impedance, the noise area should be a "fragile" realm, prone to all sorts of influence. Though, now that you mention entropy+pattern = entropy, it may not matter either way. Since adding any kind of influence would be helping, not hurting the randomness... Correct? I still think with this current system there are still ways for (B) though. ...

It's very hard, practically impossible to "swamp' the entropy in the mains cycle. As an example if the mains waveform had a small 17kHz component, and you added a 5kHz component, that small 17kHz component would still remain and could still be extracted. Now if the mains waveform contained a random component, then adding 5kHz, or any other signal to it won't remove that random component.

In the zener diode RNGs they amplify 0.1mV of noise up to a 2v waveform, to make random numbers. So you CAN swamp that system by adding say 10mV of a particular frequency the amplifier will clip hard at 5v and the RNG output is "broken". Maybe that explains better the difference between this hardware RNG and many others that use voltage amplified white noise.

The problem with the entire concept of a random number being 'not predictable' is that that is impossible to start from; all random numbers depend on some form of predictability...

That is correct, the unpredictability exists in the AC mains waveform shape and timing, both being affected by everything connected to the mains. All power factors, currents drawn, surges and spikes from appliance events etc. That noise component was measured and is +/-50 to 100 counts on every mains half cycle. Also my simple algorithm hashes three bits from totally different mains cycles, so events that affected one cycle may not have affected the others, blending and improving the overall entropy.

Now if someone wants a clever challenge... I'm still looking for "Chaoscillator" ideas. That is an oscillator that reliably produces a fairly high frequency (say 50kHz or 50000 "events" per second) but where there is a significant chaos component in the waveform that cannot be predicted, and is hard to influence from external factors (so it must be L or C reactive, not just amplifying tiny noise signals). That would allow production of more bytes per second of data than the hardware RNG here that only makes 12.5 bytes per second.

 

[()blivion]

Now if someone wants a clever challenge... "Chaoscillator"

Analog LFSR like device.

Take a delayline, such as a pizeo unit with multiple taps, power one end of it with a low-Q oscillator, use Op-Amp circuits to feed the instantaneous signal at said taps back into the system in a quasi-XOR fashion. Make a few more taps at any point, doesn't matter. And feed all data points into some A2D converters. The various states will depend on other states from other times + temperature + oscillator frequency. If the circuit also has a really bad thermal coefficient, you could power a few 1/4 Watt resistors like they were heaters. Make it so the different power levels depend on the system output. You could do something similar to your oscillator if it was voltage controlled. And in the end, faster and faster units could be made very very small.

Not exactly a "Chaoscillator" but has about the same effect you're looking for I think.

 

[misterT]

... the unpredictability exists in the AC mains waveform shape and timing, both being affected by everything connected to the mains. All power factors, currents drawn, surges and spikes from appliance events etc. That noise component was measured and is +/-50 to 100 counts on every mains half cycle.

I would be very interested to see (somehow) if the AC mains noise has a fractal nature.. like noise in (digital) communication channels is very likely to be fractal. Cantor set or similar. I think even the Die Hard test does not test for fractal patterns. Fractals could also be an interesting starting idea for your clever challenge.

 

[MrAl]

Hello,

Eric had the right idea back in post #16 of this thread. Any random sequence that is of finite length is not really random. It has to be an infinite sequence, so lets do that then.

Back some years ago this would be much harder to do, but with today's computers with their huge memory space it's not as bad.

We need an infinite sequence, ie one that is truly infinite in nature. Here we can start with the number pi, the one we are all so familiar with:
3.14159...etc, etc.

It just so happens that it was determined a number of years ago that the digits of pi are truly random and go on forever. So the random number generator only has to calculate the digits of pi to be truly random.
There are some good algorithms out there that you can use. Granted it may take some time to start the algorithm.
Im sure pi isnt the only number either if you happen to think that one is too common.

Another idea is to generate random length ramps using a microcontroller and resistor and capacitor. Using a standard pseudo random generator in the uC, the ramps it creates with the R and C are then ADC sampled at random times determined by another random generator and noisy one shot with it's output time partially obtained from the previous sampling result. Should give some very hard to predict numbers.

 

[misterT]

So the random number generator only has to calculate the digits of pi to be truly random..

I could predict those "random numbers" using MrRB's Hardware RNG. If a number sequence is infinite (not repeating), it does not mean it is random.

 

[MrAl]

I could predict those "random numbers" using MrRB's Hardware RNG. If a number sequence is infinite (not repeating), it does not mean it is random.

Hello,


In a deep evil voice: "There is no random, only Zuel."

As Eric also mentioned every generator repeats at some point, but one that does not EVER repeat has got to be pretty nice.

Predict the digits of pi? Ok so what digit of pi did i just generate? Did i even use pi this time or some transcendental? If i did use pi, did i start at the 10th digit or the 10 millionth digit?

 

[()blivion]

irrational numbers
Pi and other irrational number have been used before as parts of encryption and such with much success. But as misterT pointed out, It has a predictable sequence, which by definition makes it nonrandom. The same can be said for LFSRs too though, but they make great RNG starting points. By them selves they are very predictable. But that can be fixed to a large degree by taking the output of other systems with entropy and feeding it into this system. It's more accurate to call such things "statistically random" though. But then that just brings us back to "nothing is ever truly random".

"chaoscillator"
IMO, A working chaoscillator will be purely analog memory, and will have a sufficient amount of positive feedback that the signal control becomes totally unstable. A "signal ouroboros" if you will. It wouldn't hurt to have other forms of "random" input as well, to help change it up a bit.

 

[Sceadwian]

That is correct, the unpredictability exists in the AC mains waveform shape and timing, both being affected by everything connected to the mains. All power factors, currents drawn, surges and spikes from appliance events etc. That noise component was measured and is +/-50 to 100 counts on every mains half cycle. Also my simple algorithm hashes three bits from totally different mains cycles, so events that affected one cycle may not have affected the others, blending and improving the overall entropy.

That is true from non-serious use of an RNG, suffice to say it is fine for typical uses of an RNG but not serious cryptography, statistically speaking the events that occur on an AC line will overall hold a certain pattern and produce non-random predictable patterns in the numbers generated that could be discovered by sufficient statistical analysis, this might seem like pedantry but RNG's are taken VERY seriously in some circles and mathematically speaking there is no possibility of a truly unpredictable system, all good modern cryptography also has to lend itself to a certain degree of security through obfuscation, such as hiding the specific hash methods and cryptographic sequences can't be known, otherwise the key's can be reverse engineered from say the passwords of users on a system using a dictionary based attack.

Future advancement in quantum computing will be the real problem because they'll provide solving ability that would make modern cryptography obsolete overnight, that however is many many years down the line for practical systems.

 

[jpanhalt]

Here's something a little lighter to consider. Tonight's winning pick 4 in Ohio was 2223. That sequence appears in pi (excluding the initial 3) at positions 14,668, 25,469, and 35,271. Isn't it just amazing they are each about 10E4 apart?

Now, if we only had a way to pick a random position in pi, we would be all set.

John

 

[Mr RB]

...Analog LFSR like device.

Take a delayline, such as a pizeo unit with multiple taps, power one end of it with a low-Q oscillator, use Op-Amp circuits to feed the instantaneous signal at said taps back into the system in a quasi-XOR fashion. Make a few more taps at any point, doesn't matter. And feed all data points into some A2D converters. The various states will depend on other states from other times + temperature + oscillator frequency.

I think that would qualify as a Chaoscillator, and it's a clever idea using different taps into an electromechanical device like a piezo delay line. The down side I think would be the complexity and need for specialsed hardware, multiple ADCs, difficulty simulating etc.

One of my ideas was to use a hex schmidt inverter IC as 6 independent RC oscillators, then resistor couple some of their outputs back into some of their inputs. With a schmidt RC osc a resistor to 5v or 0v changes the RC ramp slope and the duty cycle so they would be affecting the duty cycle of the other osc, I think its possible to find a configuration of 6 oscillators that would have a significant chaos component.

I would be very interested to see (somehow) if the AC mains noise has a fractal nature.. like noise in (digital) communication channels is very likely to be fractal. Cantor set or similar. I think even the Die Hard test does not test for fractal patterns. Fractals could also be an interesting starting idea for your clever challenge.
...

I only have a basic understanding of fractal RNGs having used them on occasion, but generally they use a feedback component and an offset component (like n = n*a + b). I'm sure that would occur on some scale in the mains noise, as the mains voltage and currents do compensate for load (being roughly regulated). And comms channels would definitely have fractal noise as they are a fixed datarate with some fixed data sizes and commonly recurring data patterns.

But the AC mains also has a real-world unpredictability, there is no way to predict when my nighbours brain neuron fires and he decided to put the kettle on, or to know when his fridge bimetallic strip flexes and his fridge motor kicks in etc. So even if there are longer term fractal patterns there must also be a high component of instantaneous and completely unpredictable noise?

I'd like to see how you'd use a hardware fractal but it is a cool idea. Remember the real point of the Chaoscillator is to produce a real world physics based unpredictable component, where most fractals are algorithm and pattern generated.

... It has to be an infinite sequence, so lets do that then.

Back some years ago this would be much harder to do, but with today's computers with their huge memory space it's not as bad.

We need an infinite sequence, ie one that is truly infinite in nature. Here we can start with the number pi, the one we are all so familiar with:
3.14159...etc, etc.

Good to have you onboard. There are a couple of issues with Pi and similar systems. I proposed a non-repeating Pi based algorithm system in a previous thread discussion with MisterT, but it is non-random in that if someone has some previous data it is easy enough to find the location within Pi and know all future data. Also the idea of "generating an infinite length non-repeating string" is flawed as it cannot be done by a computer as no computer has an infinite number of states. Essentially to generate ANY infinite length non-repeating string the PC needs to have and process the data of all previous states, this applies to calculating Pi too. So it just runs out of memory.

... Another idea is to generate random length ramps using a microcontroller and resistor and capacitor. Using a standard pseudo random generator in the uC, the ramps it creates with the R and C are then ADC sampled at random times determined by another random generator and noisy one shot with it's output time partially obtained from the previous sampling result. Should give some very hard to predict numbers.

An excellent Chaoscillator idea! It's not entirely self contained being that it uses some math processing as part of the loop, but sounds workable. I particularly like RC solutions because of their simplicity and ease of simulation and 'scoping, and because RC slope->digital input triggering points are always unpredictable within some uV or even mV.

... Another idea is to generate random length ramps using a microcontroller and As Eric also mentioned every generator repeats at some point, but one that does not EVER repeat has got to be pretty nice. ...

Only a closed loop algorithmic generator with a limited number of states has a global repeat. Something based on real world entropy (like my hardware RNG) doesn't repeat. Only the normal repeats of small data sections determined by normal random statistics.

... "chaoscillator"
IMO, A working chaoscillator will be purely analog memory, and will have a sufficient amount of positive feedback that the signal control becomes totally unstable. A "signal ouroboros" if you will. It wouldn't hurt to have other forms of "random" input as well, to help change it up a bit.

More good ideas. I think that is the basic goal, to have something like a linear shift RNG but done with analog times or voltages (like RC RL LC etc), so some taps from the process feed back into its input and due to the fuzziness of the real world physics would become truly chaotic.

... this might seem like pedantry but RNG's are taken VERY seriously in some circles and mathematically speaking there is no possibility of a truly unpredictable system ...

Sorry Scaedwian this is simply not true. Mathematics might hold true inside a computer based algorithm, but there is no mathematics that will tell you the exact microsecond my neighbour's fridge turns on. Real entropy exists as a component within the real world, and CAN be extracted, and is beyond any predictable mathematical relationship.

... Here's something a little lighter to consider. Tonight's winning pick 4 in Ohio was 2223. That sequence appears in pi (excluding the initial 3) at positions 14,668, 25,469, and 35,271. Isn't it just amazing they are each about 10E4 apart?
...

Very cool, but hardly amazing. The fact that Pi conforms to a mathematical relationship means it is highly likely that there are numerous strong frequencies, you probably just discovered a frequency where Pi reacts with base 10 at roughly 10e4. Even though Pi is without an exact repeat it may have strong data trends at certain frequencies. That's probably a great argument AGAINST using Pi for RNG seeding?

Do you have a link to some Pi data >1Mb or so? I can run it through my entropy display software and see if it shows obvious trends.

 

[MrAl]

[pi as number generator]
Good to have you onboard. There are a couple of issues with Pi and similar systems. I proposed a non-repeating Pi based algorithm system in a previous thread discussion with MisterT, but it is non-random in that if someone has some previous data it is easy enough to find the location within Pi and know all future data. Also the idea of "generating an infinite length non-repeating string" is flawed as it cannot be done by a computer as no computer has an infinite number of states. Essentially to generate ANY infinite length non-repeating string the PC needs to have and process the data of all previous states, this applies to calculating Pi too. So it just runs out of memory.


[pseudo random number generator to real world ramp generator + sporadic ADC sampling]
An excellent Chaoscillator idea! It's not entirely self contained being that it uses some math processing as part of the loop, but sounds workable. I particularly like RC solutions because of their simplicity and ease of simulation and 'scoping, and because RC slope->digital input triggering points are always unpredictable within some uV or even mV.


Only a closed loop algorithmic generator with a limited number of states has a global repeat. Something based on real world entropy (like my hardware RNG) doesn't repeat. Only the normal repeats of small data sections determined by normal random statistics.


Very cool, but hardly amazing. The fact that Pi conforms to a mathematical relationship means it is highly likely that there are numerous strong frequencies, you probably just discovered a frequency where Pi reacts with base 10 at roughly 10e4. Even though Pi is without an exact repeat it may have strong data trends at certain frequencies. That's probably a great argument AGAINST using Pi for RNG seeding?

Do you have a link to some Pi data >1Mb or so? I can run it through my entropy display software and see if it shows obvious trends.

Hello again,

I guess if you knew that we would be using pi itself all by itself then it may not be too difficult to find a stream of data that matches your given stream, but that doesnt mean that you found the right stream.
Believe it or not, this is just like a pseudo random number generator algo except the PRNG repeats while pi does not repeat. The fact that we find similar strings in multiple places doesnt mean anything. Let me give a counter example...
we have the string 314, what is the next number?
If we start from the very beginning we would see 314 and then a 1 (as in 3141592) but how do we know the sender was starting at the beginning and not some other place in the multitude of digits?
To find out what would happen with another location instead of the 'correct' one we would look at more strings. We would find strings 3140, 3141, 3142, etc.. up to 3149, so that means we didnt do any better than if we just guessed 10 times. And it is the same with an PRNG as we could see the same string 314 to start with and then see 10 combinations of 314x.
So what is the difference?
The difference is that the PRNG must repeat due to the limited precision of the algorithm, while given enough computing time pi never repeats. Yes sub strings repeat and that is just nature, but once you think you've found a sub string that identifies the exact position in the digits of pi you look at one more digit and find that it's not really the right place.

Normally when i say 'generator' i mean an algorithm that is purely mathematical in some way and does not include real world chaos of any kind.

We obviously can not generate an infinite number of digits of pi, but we can generate a lot. In theory we could generate enough so that it would take an end user so much time to search that it would not be feasible.

I'll see if i can find the algorithm but there may be digits of pi on the web already.
BTW, what form does the data have to be in for you to be able to test it?

If you are after a real world chaos generator then that is different so we'd have to approach that differently as in the arbitrary ramp generator scheme. This would be cool to try
What do you mean though by 'not self contained' ? There has to be some outside real world influence if we want true chaos without having to generate an infinite number of digits.

 

[()blivion]

I think that would qualify as a Chaoscillator, and it's a clever idea using different taps into an electromechanical device like a piezo delay line. The down side I think would be the complexity and need for specialsed hardware, multiple ADCs, difficulty simulating etc.

It doesn't actually have to be electromechanical. Any medium that has a known time for a signal to propagate through, and that the time is slow enough to work with will work as a delay line. I was using a pizeo device just as an example because it's easy to understand. But point of fact there is a single wire only delay line memory devices that would work just as well. Better actually since it's just wire taping into it is as easy as soldering to it. But also a chain of inductors with grounded capacitors would work just as well. That's also how you could model such things in the sim.

As for being specialized, well... a high end RNG is going to be specialized, and one using radioactive sources would be more specialized. I would think my idea is a safe alternative. Your idea with the 6 gate Schmidt inverter IC is admittedly much more easy to do and more common.

RC slope->digital input triggering points are always unpredictable

If it's non-Schmidt triggered, yes. That's the illegal logic area which is classified as "result not determinable". I have always though of this and wanted to try and develop a RNG based on this practice, but digital logic's tend to fry when you put their inputs in the "illegal zone". And that scares me <)

Do you have a link to some Pi data >1Mb or so? I can run it through my entropy display software and see if it shows obvious trends.

http://www.superpi.net/

The software has also previously been run long enough that there should already be a huge file of pi floating around. You may have to ask around for it. But if not, making 10MB of pi with that program shouldn't be hard for most modern PCs.

I would be very interested to see (somehow) if the AC mains noise has a fractal nature.. like noise in (digital) communication channels is very likely to be fractal. Cantor set or similar. I think even the Die Hard test does not test for fractal patterns. Fractals could also be an interesting starting idea for your clever challenge.

Fractals, yes. I'm pro fractals, however they are still somewhat predictable. Power line noise is probably fractal in nature I would imagine. The analog delay line chaoscillator design I proposed would probably also have a very fractal nature. The signal that gets fed back to the system would probably need to have a lot of positive feedback for the system to work. This positive feedback would undoubtedly create and amplify a TON of harmonics. Harmonics = fractions... which of course = fractals. Long lines have capacitance and inductance, this should ring with a decaying rate. All the ringing together would create harmonics. So also fractal in nature.

I guess if you knew that we would be using pi itself all by itself then it may not be too difficult to find a stream of data that matches your given stream, but that doesnt mean that you found the right stream.
Believe it or not, this is just like a pseudo random number generator algo except the PRNG repeats while pi does not repeat. The fact that we find similar strings in multiple places doesnt mean anything. Let me give a counter example...
we have the string 314, what is the next number?
If we start from the very beginning we would see 314 and then a 1 (as in 3141592) but how do we know the sender was starting at the beginning and not some other place in the multitude of digits?
To find out what would happen with another location instead of the 'correct' one we would look at more strings. We would find strings 3140, 3141, 3142, etc.. up to 3149, so that means we didnt do any better than if we just guessed 10 times. And it is the same with an PRNG as we could see the same string 314 to start with and then see 10 combinations of 314x.
So what is the difference?
The difference is that the PRNG must repeat due to the limited precision of the algorithm, while given enough computing time pi never repeats. Yes sub strings repeat and that is just nature, but once you think you've found a sub string that identifies the exact position in the digits of pi you look at one more digit and find that it's not really the right place.

You make a good argument.

The only problem I see with pi, or the square root of 2, or 3, or ANY irrational number as a random number is that they are universal constants. This of course means that the whole sequence of "random" data is easily reproducible given the same starting information. This problem is also shared by PRNGs. How useful that is to an attacker is debatable. However a "truly random" number would not have this problem from the start. That is because there should be no correlation between data from any two points. It's just plain random.

Not to toot my own horn, but turn my design on billions of times, and it would never start the exact same way twice. And the stream of data flowing out of it would never be the same two values ever. The same thing for noise reading systems, such as Mr RB's device. This is because the signal never stops, it's infinite as far as man need be concerned. Or for the more picky, these things end when man does.

Normally when i say 'generator' i mean an algorithm that is purely mathematical in some way and does not include real world chaos of any kind.

Not that I'm correcting you, but I think what you are talking about is a "finite-state system". (not to be confused with finite-state machine, which implies JUST computers) In other words, some system that can only do things exactly accurately and according to "a plan", with finite measurements. This point highlights exactly why I feel a TRNG would be purely analog. Because, it may not be practical, but you can physically divide analog system down to infinitely smaller levels, (well... until you hit the quantum level) so it *IS* truly infinite. Maybe not in the time domain, but in space.

Anyway, I'm tired so I may be talking gibberish. I'll look at this again tomorrow and hopefully not turn bright red. /)
-()b

 

[jpanhalt]

@RB,

Please, no name calling.

Here is what I used: https://www.angio.net/pi/bigpi.cgi

It returns a result for 900,000 to 900,009 as 3587510954. Do you know whether that is correct? I only memorized pi to 10 decimal places (1415926535). At least it checks out that far.

I then searched on 900,000 and it appears at position 1,909,003 counting from the first digit after the decimal point. It also appears at position 1,938,145.

John (not related to Sceadwian)

Edit: My Social Security number (9 digits) did not occur in the first 200,000,000 digits. So, I guess that is as far as it goes. Do you think my bank accounts are safe from random hackers using pi? Yes, I realize 200,000,000 is only 9 digits.

 

[alec_t]

Next time you're at a party and someone asks you for a number to seed their PRNG you can recite pi to 30 decimal places, aided by remembering this jingle:-
"Now I, even I, would celebrate in rhymes inept the great immortal Syracusan, rivall'd nevermore, who in his wondrous life passed on before left men his guidance how to circles mensurate".