Generating random numbers

[JonnyBoats]

I have seen lots of techniques used to generate "random" numbers such as avalanche diodes etc. Here is one I had not seen before, use of a cheap SDR dongle:

http://blog.cros13.net/2014/08/cheap-entropy-using-your-rtl-sdr-as.html

Has anyone else tried this? What do you think?

[Kjelt]

I think that I would like to see the diehard testsuite results of 80MB of such generated random numbers first before I judge.

That said, the first sentence is in my opinion bullshit:

Whether you are using a block cipher or a stream cipher the foundation of your key's strength is quality of the random number generator used as an entropy source.

It is not the key's strength, it is the IV's or nonce (in ctr mode) strength that is at stake which is still not good cryptographically speaking but less bad, not preferred anyway.

Then he babbles on about OTP which is not very much used anymore and if used, the random numbers can be generated offline from all kinds of entropy sources or hell even statistically derivated from known true random tables.
I don't see the value in a tv signal usb stick as entropy source, but if it generates a near perfect diehard testscore I would be impressed.

[Kjelt]

I have done testing with an open base transistor using the diode as noise source even that one although pretty good did not pass the die hard tests.
Besides one should never forget that an opponent if having access near this device can manipulate such entropy harvester with a simple transmitter.
I don't see the application also, for a PC to generate random numbers is not a big deal these days, superduper and other algo's that do pass the diehard test are good enough for 99% of the security applications.
For an embedded standalone device now that is the real challenge 

[dannyf]

I have done testing with an open base transistor using the diode as noise source even that one although pretty good did not pass the die hard tests.

Depending on how you did it.

My preferred way is to use adc and retain the lsb only.

[Kjelt]

did that, analysed how many ls bits could be used. Gonna share some insight info: the lsb of a stm8 is totally NOT random 
ended up using some other bits higher up that provided better results but still not good enough.

[FrankBuss]

If you have some randomness, would you get pure random values if you calculate SHA256 of it? Or use it as a seed for a software RNG and seed and run this a few times for each value.

[Kjelt]

If you have a random number created from true entropy you can use it as a seed for a prng, this can be a lfsr (weak) or aes round(s) or other prng.
You can not use a prng forever, now and then you have to re-seed it, the best long time before it overflows, and if possible as many times as you can regenerate a true random number from the entropy.

[dannyf]

I ran a random number generator on stm32f: lsb for 32 bits, on an empty pin.

Since I don't have swo, I didn't have a way to output it easily but here are some numbers from the generator:

a5990a5a 309a5e05 a84bfa7d d42f424a 7430bd32 343e8550 bcf4a5f7 45b5c9a1

256 bits are short but it looks reasonably random.

[David Hess]

I have seen this before in the form of an FM radio tuned to an unused channel.  The output from the FM discriminator was used as a noise source.

[djacobow]

I did the RTL dongle randomness thing awhile back and iterated a few times with the DIEHARD and NIST tests. I was able to get a system that generated bitstreams that passed all most of the DIEHARD tests most of the time. It definitely passed all the FIPS-140 tests all the time.

I wasn't simply taking the bits that came out of the radio. I had to munge them down a fair bit, cutting down the bandwidth of the RNG in the process. I seem to remember using a sliding window in which some bytes were bit-reversed some weren't, and there was a lot of xoring and a bit more shuffling and then xoring with previous output. I think I was probably getting one bit out for every byte out of the radio.

[Kjelt]

I ran a random number generator on stm32f: lsb for 32 bits, on an empty pin.
Since I don't have swo, I didn't have a way to output it easily but here are some numbers from the generator:
a5990a5a 309a5e05 a84bfa7d d42f424a 7430bd32 343e8550 bcf4a5f7 45b5c9a1
256 bits are short but it looks reasonably random. 

First of all you can not analyze small parts of data, the software is also looking for patterns in each 1..255th bit for instance in a series to search for patterns.
Because if the pattern is that in a sample of 80MB each 40th bit for instance is always zero then your crypto key of 128 bits has only the security of a 127 bits key.
Then you should know the difference between a statistic random number and a cryptographic secure random number, the first (statistic) means that all values occur equally in the sample so it should behave like a stochastic draw (for instance an ideal dice) but the requirement for a cryptographic random number is harder namely it should be totally unpredictable. That is why statistic rng are not suited for cryptography.

That said, taking a manual quick look at your samples    If you ever install this rng in a casino let me know the name of it since I am not shy of making some money on the side, although the number of 0's (126) and 1's (124) is pretty good (statistically) if you look at 4 bits pairs (nibbles) the result is horrible:


nibble   times occurs

0        5
1        1
2        3
3        5
4        8
5        9
6        0
7        3
8        2
9        4
A        9
B        4
C        2
D        3
E        2
F        4

and that is just a simple 2 minute scan of the data, die hard would spit it out    But for simple (non cryptographic applications) it might well do.

[Kjelt]

The US discovered that China had broken some of its codes because of slight predictability in the source of its RNGs.

Interesting, do you have a URL , source for me?

[dannyf]

if you look at 4 bits pairs (nibbles) the result is horrible:

It depends on the particular runs. Here is another:

2b6857f4 9a054854 82ffd0b7 8b96a85f b52bfe55 fec54240 54142bca 35ed42a8

If you were to run the count tests, you should do it successively, in bit orders (shift the whole pattern by 1 bit), not in nipples (shift the whole patter by 4 bits).

It is built on the notion that there is unpredictability in the adc module. Because of that, this approach actually works on adc channels that are not implemented on a chip - the above random number for example comes from ADC_IN10 / ADC_Channel_10 which does not exist on STM32F030F.

[dannyf]

Similiar performance from STM8S003F:

8b9f1132 ec29d2a2 88c1c95f 4d7947ae 6fe552d5 547938e3 722ec547 bb7ea945

[dannyf]

The approach (using lsb of adc modules to generate random numbers) relies on a critical assumption: the adc modules we use are not designed by God. A typical 10-bit adc will easily fluctuate 8 (lowest) in readings and a typical 12-bit adc will fluctuate 20 - 30 in readings so there is plenty of "randomness" for you.

If you are so unfortunate that you get an ADC designed by God where it doesn't fluctuate nearly as much, you can still utilize this approach, with a twist:

1) count the number of times you have to read the adc before its lsb changes. Say it is N1;
2) count the number of times you have to read the adc before its lsb changes again. Say it is N2;
3) return (N1>N2)?1:0.

Obviously, more stable the adc readings are, the longer it takes to return a random bit.

You can then call the routine above multiple times to return any number of random bits.

[VK3DRB]

There may be no way to generate a random number. If all of the universe is predetermined from the Big Bang onwards (cause and effect ad infinitum), you cannot generate a truly random number. Of course, to the human observer you can generate "random" number because the human has no way to predict the outcome. No-one has ever been able to prove of disprove whether absolute randomness exists in the physical world, although there are theories.

Under the cosmological hypothesis of determinism, there is no randomness in the universe, only unpredictability, since there is only one possible outcome to all events in the universe.

I read in New Scientist magazine recently that despite scientific studies, no-one has ever been able to determine if humans have choice. A "random" selection may be cause and effect all the way, based upon past experiences and events, whether they be aware of them or not.

On the human observer level, maybe one good way to generate a pseudorandom number is to use a Geiger counter and count clock cycles between each background radiation particle detected.

[David Hess]

There may be no way to generate a random number. If all of the universe is predetermined from the Big Bang onwards (cause and effect ad infinitum), you cannot generate a truly random number. Of course, to the human observer you can generate "random" number because the human has no way to predict the outcome. No-one has ever been able to prove of disprove whether absolute randomness exists in the physical world, although there are theories.

Under the cosmological hypothesis of determinism, there is no randomness in the universe, only unpredictability, since there is only one possible outcome to all events in the universe.

I read in New Scientist magazine recently that despite scientific studies, no-one has ever been able to determine if humans have choice. A "random" selection may be cause and effect all the way, based upon past experiences and events, whether they be aware of them or not.

This will not prevent engineers from getting close enough for all practical purposes.

On the human observer level, maybe one good way to generate a pseudorandom number is to use a Geiger counter and count clock cycles between each background radiation particle detected.

The problem with background radiation is that someone else gets to determine the background.

[dannyf]

there is no randomness in the universe, only unpredictability,

Do you really care if something is random vs. unpredictable?

pseudorandom number is to use a Geiger counter

It is probably random; and it follows Poisson distribution.

[Kjelt]

there is no randomness in the universe, only unpredictability

That is exactly what we need for a cryptographically secure rng, unpredictability.

[AG6QR]

On the human observer level, maybe one good way to generate a pseudorandom number is to use a Geiger counter and count clock cycles between each background radiation particle detected.

That's been done, and works pretty well.  See here:

https://www.fourmilab.ch/hotbits/

In the "how HotBits works" tab, he explains the technique he uses to get a random bit.  He times the interval between two clicks, calls that T1, and then times the interval between two more clicks, and calls it T2.  If T1 equals T2 within the resolution of his clock, he discards both and tries again.  Otherwise, he returns a bit based on whether T1 is greater than or less than T2.  In order to eliminate any minuscule residual bias due to interval times gradually increasing, he flips the sense of the comparison each time he gets a new bit.

That's about as close to random as I can imagine.

Downsides are that it requires somewhat expensive equipment and it doesn't generate bits very rapidly.

[NiHaoMike]

Take the ADC data and encrypt it with AES or similar. For successive cycles, take the previous output, XOR it with the new ADC data, and encrypt it again.

[T3sl4co1l]

Take the ADC data and encrypt it with AES or similar. For successive cycles, take the previous output, XOR it with the new ADC data, and encrypt it again.

But how do you generate the key?! 

[Kjelt]

Take the ADC data and encrypt it with AES or similar. For successive cycles, take the previous output, XOR it with the new ADC data, and encrypt it again.

That is how you generate pseudo random numbers from a real random number (the seed). This can also be done with a lfsr but then if someone knows the depth of the lfsr and some states the next and previous states can be fully predicted.
The question here is how to capture real entropy, real random data that ( ideally ) can even not be manipulated from someone on the outside.

[Kjelt]

@ Danny can you show one series or share the xcel file. Looks pretty nice, but again for a real cryptographic rng you need to run it through the analysis tests.

[T3sl4co1l]

Take the ADC data and encrypt it with AES or similar. For successive cycles, take the previous output, XOR it with the new ADC data, and encrypt it again.

That is how you generate pseudo random numbers from a real random number (the seed). This can also be done with a lfsr but then if someone knows the depth of the lfsr and some states the next and previous states can be fully predicted.
The question here is how to capture real entropy, real random data that ( ideally ) can even not be manipulated from someone on the outside.

No, this isn't a seed method, this is an unbiasing method.  The simplified analog is not a seeded LFSR, it's an LFSR (or whatever combination of many, in parallel or chained?) with real entropy XOR'd into the feedback path.  The result depends on the input at all times, so is true random, assuming the entropy is clean to begin with.

One good thing is, the scrambling is pretty good -- a single bit change can be expected to disturb an entire block of bits at a time.  It's also one bad thing: a blockwise cipher has no dependency on previous blocks.  So you'd want to chain them (which was as suggested, so I'm partly making things up here), or overlap the passes, or something like that.

Ed:
For the perturbed LFSR case, every input bit can push the current LFSR sequence into one of two subsequent states; after N bits, the possible states are 2^N (same as if the LFSR were evolved N times, if the pattern is unknown), so the equivalent block size would be an N bit cipher (which makes sense, after all).

A good reason not to use ADC readings is, an attacker could very easily bombard the device with a good RF field, or prod some pins or whatever, and cause it to read out of range, guaranteeing a read of all zeroes or all ones.  None of the examples posted even has an attempted sanity check, which would only be a crude workaround for a fundamental problem.

And what would you do about it?  Would you return a 'fail' condition and make the rest of the program more complicated trying to handle every contingency -- inevitably forgetting some?  Or, wait forever like a *nix urandom() call waiting for entropy?  Or just keep on pulling numbers out of your ass, say by evolving an LFSR (or any other de-weighting / scrambling method) without any new entropy -- this being the most insidious alternative, because it could be part of a library, invisible and undocumented, and you'd never suspect a thing!

Tim

[Kjelt]

If you use the entropy for a real random number with a sanity check (at least drop all '0's and all '1's) and generate with a n bit lfsr or for instance an n bit AES algo for generating pseudo random numbers you can indeed generate a lot of numbers before it overflows (return to a already used state), to keep it safe i would generate much less than 2^n-1 messages but still.
This gives a lot of time to generate a new seed or random number. For a constrained embedded device a small table of real random numbers would suffice for a lifetime but that is a bit cheating 

[German_EE]

This subject is outside my level of expertise but I am curious, if a random number generator requires a seed then how can it be truly random? If I was designing a random number generator I would take a natural noise source such as background radiation, amplify it and then feed it into a 20-bit ADC. The bottom sixteen bits should generate reasonably random numbers but if you want to go to extremes then build two of the systems and XOR the outputs.

The only other source of true randomness I can think of is the direction and speed of a woman in a large clothes shop but a system like this might be too expensive to run on a long-term basis. 

[Kjelt]

This subject is outside my level of expertise but I am curious, if a random number generator requires a seed then how can it be truly random?

It can NOT. A pseudo random number generator requires a seed. The seed for the prng is a "true" random number generated from entropy.

[Kjelt]

To explain it a bit more:
A good RNG can be used directly to generate random numbers. However often a true RNG is based on slow entropy sources and it takes a lot of time to generate enough random bits. Therefore often the RNG is used to produce one small stream of bits that is used as a “starter” for a PRNG, this small stream of bits is called a seed. The PRNG is a special software module that is capable of generating faster and larger streams of statistically random bits (that’s why it is called pseudo random bits since they are not truly random) see picture.

[T3sl4co1l]

If you're re-seeding the generator between intervals on the order of 2^N bits, you'll be producing large runs of sequentially generated bits that are therefore very vulnerable.  If the new seed is derived from the previous state (one or a few bits added), the new state will be even more vulnerable (within N bits, the bit(s) that changed, and when, will be apparent).  A fully new state (initialized with N true random bits) on an already-known generator requires no more than N bits to determine its new state.

If it's re-seeded less than every N bits, there is (ideally?) no coherency on the order of 2^N bits, so long-term attacks shouldn't prove very fruitful.  That makes breaking the generator somewhat harder.  Attacks on the order of N bits may prove fruitful, but will be much less useful: even if the generator is known, I think the prediction can't be any more accurate than B/N, for an average B bits of entropy injected into every N bits of output.

Tim

[VK3DRB]

The problem with background radiation is that someone else gets to determine the background.

I lived in a rather radioactive area for 13 years - near the Warby ranges in NE Victoria. All radioactivity is unsafe to some extent. The place is full of granite rocks and sandy granitic loam.... a good source of radioactive trace elements. The radioactivity levels lowered considerably as you walked from the Warbies to Wangaratta where the granite was much less, except where people built their entire homes and the big Anglican church out of the granite.

So you are correct, the frequency of pips in a Geiger counter is determined to some extent by people. The further I walked from the Warbies, the pips lowered in frequency.

I knew many people who lived on or near the Warbies who got cancer and died. I don't know if anyone has done a statistical study on cancer rates up there. I had a double whammy. The bricks of my house I built there had heaps of slightly radioactive quartz in them too. One family member got cancer, and I suspect the environment may have caused it, but there is no way to prove it.

[Kjelt]

If you're re-seeding the generator between intervals on the order of 2^N bits, you'll be producing large runs of sequentially generated bits that are therefore very vulnerable.  If the new seed is derived from the previous state (one or a few bits added), the new state will be even more vulnerable (within N bits, the bit(s) that changed, and when, will be apparent).  A fully new state (initialized with N true random bits) on an already-known generator requires no more than N bits to determine its new state.
If it's re-seeded less than every N bits, there is (ideally?) no coherency on the order of 2^N bits, so long-term attacks shouldn't prove very fruitful.  That makes breaking the generator somewhat harder.  Attacks on the order of N bits may prove fruitful, but will be much less useful: even if the generator is known, I think the prediction can't be any more accurate than B/N, for an average B bits of entropy injected into every N bits of output.
Tim

In the coursera course crypto1 somewhere in the mac part it was stated that with an 128 bit cypher you could only (with that specific scheme) use it for 2⁴⁸ i believe it was before it was "unsafe" , so yeah you should with the prng definitely stay far away from the theoretically 2ⁿ before it overflows. But even if you use one 128bits random number with a 128 bit AES cipher as prng and that for  2⁴⁸ messages you have a very long time for a constrained embedded device to generate a new rng. I mean it is not a google server, it is a constrained embedded device with let's say 10 messages an hour, 240 messages a day, it would take 3213184 milennia to overflow 

[VK3DRB]

About 20 years ago, I connected a pulse output from my Geiger counter to interrupt a microcontroller. The interrupt would reset a counter and on the next pulse, the count was taken and transmitted to a PC through the UART port. Then I would wait for the next pulse and start it all over again. The results appeared to be random.

Are the numbers in PI random? No-one knows.

[dannyf]

The interrupt would reset a counter and on the next pulse

That count would be random, but follows a poisson distribution.

Using its lsb would debias that series and create a random series with a uniform distribution.

[dannyf]

Here is the text file used for the last run.

The file is the raw capture from hyperterminal. It doesn't come out right in notepad but fine in wordpad - not sure why.

Excel should have no problem importing it - that's how I created the charts.

[dannyf]

The approach of using adc to generate random numbers and uart to export for analysis can be easily replicated onto other chips.

For example, the implementation is particularly simple on Arduino, from the canned adc + uart calls. However, before you use it, plot the Arduino generated random number in excel and  you will be surprised,

[dannyf]

The particularly chip I used for the generation of random numbers utilizes the internal rc oscillator (16Mhz, divided by 8. Untrimmed). It runs the usart1 at 19.2kbps no problem - didn't try higher baud rates.

Not bad for a rc oscillator spec'd at 1% accuracy.

[dannyf]

It doesn't come out right in notepad but fine in wordpad - not sure why.

I forgot to mention that I figured out why.

In coding my uart transmission routines, I decided to transmit the null char (so that the receiving routines know when a transmission is over).

That was causing the notepad, as well as copy-and-paste some trouble.

[dannyf]

Highest baud rate I tried on the STM32F030F (ghetto style, running on HSI) is 460Kbps.

No handshake at 920Kbps - I do have long and loose wires, however.