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

[WTP Pepper]

I read with interest regarding the NZ National Lottery moving towards computer generated numbers and here is the problem.
The mass general public do not understand random numbers and do not understand computers and how they generate them.

Telling someone a series of number is random will not stand up to scrutiny by the general public regardless of who endorses it.
Bouncing balls in a drum and we can see what going on and are happy to see it's a pretty random chance. Just like Bingo here in the UK. Bouncing balls again.

It only takes an employee of the lottery to come up trumps without a visual source of randomness and the whole process and business of the lottery will fall apart overnight. Even if the chances of it happening with a bouncing ball machine is the same.

At school we were told the only true random event involves radioactive decay and exactly when a β particle would be emitted from a source. Try telling that to the masses who fund any lottery.

I have the background to understand basic RNG, but would query the background of a computer that simply spurted them out on a Saturday night.

 

[alec_t]

But despite his distrust of computers, Joe Public here in the UK is happy to buy Premium Bonds for which winning numbers are computer-generated .

 

[Mr RB]

...
Bouncing balls in a drum and we can see what going on and are happy to see it's a pretty random chance. Just like Bingo here in the UK. Bouncing balls again.

Apart from that it is not random! 1. once a ball number is picked that number cannot reoccur, which is extremely non-random behaviour. 2. There are significant mechanical biases with the balls and some balls get picked more than others.

...
At school we were told the only true random event involves radioactive decay and exactly when a β particle would be emitted from a source.
...

That's not true, entropy exists everywhere in varous forms. Radioactive decay is used for an example because it has a high entropy component in each "event" and also because it is fairly difficult to influence, although can be influenced by exposing the radioactive source to neutrons (ie other nearby radiation). As an anology, RF noise is seen as "bad" entropy because it can be influenced by other nearby RF energy. Radioactive decay noise can be influenced by other nearby radioactive energy, so neither system is more "truly" random. It's just that we have more RF sources around than we have radioactive sources around.

Anything in the real world has constant, pattern and bias components and an entropy component. All that is required is to measure with a high enough precision that the measuement LSB is far smaller than the noise (entropy) component and then the result will be "truly" unpredictable, which is as close to real world random as it ever gets.

 

[jpanhalt]

Apart from that it is not random! 1. once a ball number is picked that number cannot reoccur, which is extremely non-random behaviour.

Not so, at least not in American lotteries. Each of the numbers is independent. The probability of any number in each selection is not influenced by previous selections.

2. There are significant mechanical biases with the balls and some balls get picked more than others.

Yes, cheating can occur. Here is one (in)famous example: https://en.wikipedia.org/wiki/1980_Pennsylvania_Lottery_scandal

I have never played the lottery. It is a tax on the ignorant and poor, and no one has the cojones to call it what it is. I think the appeal of the bouncing balls is simply that they can be seen. A computer-driven lottery would be too easy to bias and too hard to prove. Earlier this afternoon, I searched on documented instances of lottery cheating by the states. To my surprise, it is quite rare. The above example is the only one I found.

John

 

[WTP Pepper]

From my experience, Premium Bonds have been gifts handed down and it would be interesting to see the stats of who among the young buy them compared to scratch cards and the Lotto Wed & Sat I think. Don't play it myself. A further Tax on the eternal stupid.

 

[WTP Pepper]

" There are significant mechanical biases with the balls and some balls get picked more than others. "

1. I don't think we have ever seen enough Lotto balls to go through the system to say this. Local rags printed the number of balls that came up in results over a period of a few years. At the time in the UK there was one draw a week. Hardly a statistical analysis of a few hundred samples. Still it keeps the masses pouring their money into the system believing their house number is something important.

2, You can influence any so called random event with outside influence. I think the comments made at school were more general and you don't have a U235 source tearing your cells apart at the side of a Strontium source, so background radiation wasn't even an influence on the lab model.

Still working on making myself a millionaire with a few tables and a Geiuyioiger counter....I'm turnig to slush and glowing green...

 

[Mr RB]

Not so, at least not in American lotteries. Each of the numbers is independent. The probability of any number in each selection is not influenced by previous selections.
...

Wow I didn't think they would do that! Here the lottery can only have one of each number ie you can pick
25,4,7,2,14,12
but not
25,4,25,25,7,25
as each ball can only be used once.

1. I don't think we have ever seen enough Lotto balls to go through the system to say this. Local rags printed the number of balls that came up in results over a period of a few years. At the time in the UK there was one draw a week. Hardly a statistical analysis of a few hundred samples. Still it keeps the masses pouring their money into the system believing their house number is something important.
...

Yeah I could be wrong on that one. My comment was based on some memory of reading or hearing that when someone analysed the ball drops from many years of the lottery there were some numbers having a higher statistical bias.

A quick google turned up this page; "Study Proves Number Bias in UK Lottery";
https://www.lotterypost.com/news/102721

I do know there are proven statistical biases in other mechanical draw systems like roulette wheels, this has been a known problem and to combat it the casinos move roueltte tables between stands and to/from from storage, and even to other casinos, all in an attempt to stop people cheating by betting the bias. Which to me is not "cheating" anyway, they have the customer's right to pick the number they think gives the best results.

 

[jpanhalt]

My comment was based on some memory of reading or hearing that when someone analysed the ball drops from many years of the lottery there were some numbers having a higher statistical bias.

I did see some mention of the quality of the balls used, but no data. I did not see any statistical analysis of the weight distribution, quality control, or the weight after the numbers are painted on the balls.

I wonder whether numbers that require a lot of paint occur less frequently?

John

 

[4pyros]

I wonder whether numbers that require a lot of paint occur less frequently?

Well if they are vary light like ping pong balls than I would have to say yes!

 

[()blivion]

Smoke detectors have small harmless radioactive sources. Why don't you use that as the basis for a hardware PRNG?

 

[WTP Pepper]

A quick google turned up this page; "Study Proves Number Bias in UK Lottery";
https://www.lotterypost.com/news/102721

Written by academics and a Professor. Sorry. I am neither. I have however worked in the Maths/Electronics/Crypto industry for nigh on 25 years. It saddens me that people believe statistics on such a small number of samples. Professors included. It's like tossing a coin 3 times and 2 out of 3 come up heads. There is bound to be a bias on 3 counts. So heads are the best bet. So why are there not millionaires around who made a living backing heads?

I suspect regarding the roulette wheel, it was just a peak in such random statistics and gave the Casino owners (probably not mathematicians by any meansl) to fret and react. I suppose I don't blame them. A kind of response I would expect.

I love our UK paper the Daily Mail for such use of statistics. "Out of a study of 10 people, 3 didn't die horribly of Ebola because they drank red wine". The following week there is an article telling us red wine stops bowel cancer "A study has revealed" of 2 cancer patients.

Appologies to the forum for a little rant but there are too many who understand statistics but very few who understand statistical analysis....of anything!

No doubt 2 out of 5 will disagree

I still stand my claim that a bunch of spinning balls in a machine we can all see is about as good as it gets. It may not be truely randon but it's pretty damn close for those sat on their seats with their lotto tickets every week. Unless you want to chat about chaos modelling which says otherwise.....I await the formula for my future riches......

 

[edeca]

Appologies to the forum for a little rant but there are too many who understand statistics but very few who understand statistical analysis....of anything!

No doubt 2 out of 5 will disagree

I totally agree. A recent study showed that 87.3% of statistics are made up.

I am interested in the concept of using the radiation source from a smoke detector, unsure whether this is feasible.

 

[()blivion]

I totally agree. A recent study showed that 87.3% of statistics are made up.

Actually, a recent survey showed that 3 out of 4 people are 75% of the population.

 

[jpanhalt]

Written by academics and a Professor. Sorry. I am neither. I have however worked in the Maths/Electronics/Crypto industry for nigh on 25 years. It saddens me that people believe statistics on such a small number of samples. Professors included. It's like tossing a coin 3 times and 2 out of 3 come up heads. There is bound to be a bias on 3 counts.

I agree and disagree in part.

I have seen professors make senseless mistakes and terrible conclusions based on insufficient data.

On the other hand, one might posit that anyone can get make good conclusions from a megamouse experiment. The trick is to get cost effective data and sensible conclusions. For example, one can use the Yates correction (https://en.wikipedia.org/wiki/Yates_correction) to get down to more attainable sample sizes and still make valid conclusions.

John

 

[Sceadwian]

The first line in the Wikipedia entry for Yates correction is that it the correction may go too far and that it's uses are limited.

If there were a first law of science it's that you can NEVER have too much data, but you CAN have not enough. In many situations 'cost effective data' is simply not possible this is a fact of life that is totally unavoidable.

 

[()blivion]

Back on topic if I may...

Not to pis... errr... urinate on Mr.RBs parade, but I believe there are some serious problems with the USEFULNESS of his PRNG hardware that I would like to bring to attention. Hopefully a resolution can be found.

Basically, one generally needs and uses a good PRNG specifically for cryptography. This devices accuracy in emulating randomness aside, it would not make a great source for cryptography do to the following. Any entity that knows the approximate time and location of the operating PRNG hardware and system would also have trivial access to the source medium it was generating random date from. This COULD allow (A) Clone system based attacks, and (B) Forced biasing of the PRNG.

(A) Is possible because one could tap into your power line as close as is feasibly possible with a waveform analyzing system and record the data on the line down to a relatively arbitrary level of precision. With this information, the algorithm you use to construct your pseudo-random data, and your cipher text, the time it would take an attacker to crack your code would be quite feasible. Especially if they knew the approximate time that you created your cipher text. There may be some brute forcing involved, but it would be light and forward going. (i.e. not trapdoor functions)

(B) Is possible because, as Mr.RB pointed out, the exact noise on the line is determined by any devices attached to the line switching on and off at any given time. So if an attacker knows the time about that you are using your device, they could attach a sufficiently powerful load on the line and near your device as to dwarf other loads. They would also have accurate control of the devices on/off timing and duty cycle. Then... all that would need to be done is introduce an easy to pickup on signal, such as any signal that synchronizes with any part of the PRNG evenly. This could create significant and predictable bias in the output data, and thus in the cipher text.

A combination of both (A) and (B) would be even more devastating an attack.

Exactly how close the attacker has to be to the system, and exactly how much equipment would be needed, and how exact the known time encoding was done, are all things I can't speculate on. But a large organization would certainly have the best chances. And as is, I suspect it could be done by a small group or crafty individual.

 

[Mr RB]

Smoke detectors have small harmless radioactive sources. Why don't you use that as the basis for a hardware PRNG?

Because I didn't have one handy! Seriously though the radioactive Americum smoke detectors are old and have largely been phased out (from what little I know) and may be hard to find for most people, whereas the mains noise based system is neat and self-powered and accessible to almost everyone worldwide that might need some random numbers.

...
Written by academics and a Professor. Sorry. I am neither. I have however worked in the Maths/Electronics/Crypto industry for nigh on 25 years. It saddens me that people believe statistics on such a small number of samples. Professors included. It's like tossing a coin 3 times and 2 out of 3 come up heads.

I absolutely agree and was not saying that study proved anything, the page I linked to even discusses the likelyhood that their sample size was too small to really prove anything.

However re the roulette wheels that is a fact. I watched a documentary on people who were cheating the casinos and doing very well from it, it was quite normal for some roulette wheels to have a couple percent bias. Now the problem with roulette is better understood the casinos deal with it as I mentioned before. Also studies of other mechanical systems show definite biases once there are large enough sample sizes, you should not assume that just because something is mechanical that it must be without bias. Re the lottery balls if they are slipperier or heavier or slightly mishaped those differences could all easily introduce a bias.

If I saw a mechanical system that even with a small sample size was favoring some numbers, I would be betting with the bias. Long term it might turn out to be just a data trend OR there could be an actual bias.

... I believe there are some serious problems with the USEFULNESS of his PRNG hardware that I would like to bring to attention. Hopefully a resolution can be found.

Basically, one generally needs and uses a good PRNG specifically for cryptography.

You are talking about the RNG hardware (you said PRNG)? It's direct output is not ideal for cryptography as like all hardware RNGs it is "too" random and can produce a bad data set when you extract a short section of data.

... This COULD allow (A) Clone system based attacks, and (B) Forced biasing of the PRNG.

Cool, It's good to discuss potential issues.

... (A) (clone attacks) Is possible because one could tap into your power line as close as is feasibly possible with a waveform analyzing system and record the data on the line down to a relatively arbitrary level of precision. With this information, the algorithm you use to construct your pseudo-random data, and your cipher text, the time it would take an attacker to crack your code would be quite feasible. Especially if they knew the approximate time that you created your cipher text. There may be some brute forcing involved, but it would be light and forward going. (i.e. not trapdoor functions)

A valid point, although very difficult as even within my house there are things affecting the AC mains waveform shape, and you could never know the actual 5MHz timer sync within my device when it captured the data, nor the exact position on the mains waveform that was captured (the threshold trimpot adjustment inside the device). You would also not know the exact mains cycles I used, at the time it was used.

Those four points make it near impossible. However I still would NOT use the direct output of the RNG device as the crypto key! I said on my web page the device would be used to generate seeding data keys to then be used within a software PRNG. The is device is basically used for seed entropy that will later be turned into very high quality PRNG entropy.

... (B) (forced biasing) Is possible because, as Mr.RB pointed out, the exact noise on the line is determined by any devices attached to the line switching on and off at any given time. So if an attacker knows the time about that you are using your device, they could attach a sufficiently powerful load on the line and near your device as to dwarf other loads. They would also have accurate control of the devices on/off timing and duty cycle. Then... all that would need to be done is introduce an easy to pickup on signal, such as any signal that synchronizes with any part of the PRNG evenly. This could create significant and predictable bias in the output data, and thus in the cipher text.

Another great point, although I think you are wrong with this one. To force a bias over existing entropy requires "swamping" the existing entropy. This is quite possible with a diode junction noise based RNG but would be almost impossible with AC mains entropy. The AC mains entropy exists and is of a high power and low impedance, so the best you could hope would be to add or subtract some signal to that entropy, but not to replace the entropy. Remember entropy+pattern = entropy, regardless of what pattern you add to it.

Also there are again the factors of the 5MHz device sync being unknown and the comparator threshold voltage, and the time the data was extracted.

And the most important point (as I said on the web page) the main use of the device is not as a real time constantly running security device but to plug it in and generate a small set of good data, which is then used to "seed" a larger software PRNG system. For instance if you were building a PIC based encrypter and needed to make 1kbyte of good random data as its "seed table".

 

[misterT]

It's direct output is not ideal for cryptography as like all hardware RNGs it is "too" random and can produce a bad data set when you extract a short section of data.

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.

One thing that really interests me about random numbers is that a random signal (white noise) holds a huge amount of information... I would like to say it holds maximum amount, but I'm not sure about that.

 

[()blivion]

as I said on the web page...

That's something, I haven't looked at that page yet. Just going off the info in this thread. I probably should read ALL the info before opening my mouth

You are talking about the RNG hardware (you said PRNG)?

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?

Also studies of other mechanical systems show definite biases once there are large enough sample sizes, you should not assume that just because something is mechanical that it must be without bias. Re the lottery balls if they are slipperier or heavier or slightly mishaped those differences could all easily introduce a bias

Certainly true. Let me see if I can get this quote close to correct with out looking it up

"If you know the speed and direction of EVERY particle in a system, and all forces acting on them. Mathematically, it's possible to predict the future for that system with 100% accuracy"

Or something like that. Long story short, with enough information, nothing is unpredictable.... Mathematically.

To force a bias over existing entropy requires "swamping" the existing entropy.

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.

(B-2) An "entity" could seamlessly cut your mains and splice in a backup for a time. Such as an industrial sized UPS stuffed in a van. Then they would have 100% control over the major noise components in theory. Of course, one wouldn't be able to control what you turn on and off in your house... but they would still be able to fall back on (A) for those cases.

Finally, with respect, I find these comments mutually exclusive...

...there are things affecting the AC mains waveform shape...

and

To force a bias over existing entropy requires "swamping" the existing entropy. [snip] would be almost impossible with AC mains entropy.

Largely in part because entropy is roughly equal to waveform. Unless I misunderstand how your getting your random data. If not, then my point can be summed up like this...

Either (True) the waveform on the mains line is immutable, in which case you lose entropy and a snooper can acquire your starting data, leading directly to (A), Or (False) the mains waveform is dynamic and affected by line load, which leads directly to (B).

You really can't have it both ways here. And (B-2) is still possible either way.

I could be (probably am) wrong in some way, and this is of course intended as positive criticism as well. So it's possible that your device still has practical real world applications. But as misterT has said, I don't see how this is superior to a standard hardware RNG such as LFSR based unit as is.

Still a neat idea though.

 

[MrAl]

Hi,

Quantum entanglement is supposed to be the best way to encrypt information, but i've heard that has even been cracked now.

The idea here is not to really generate a random number really, it is to generate a number that is not predictable. A random number helps with this problem.

White noise is a good source of random data. White noise can be generated. Generated white noise is pretty good as we go up in precision. It's the precision that makes it more difficult to crack. Go up in precision and you're doing pretty well.