True Random Number Generator for a True Hacker (2015) | Hacker News Reader

True Random Number Generator for a True Hacker (2015)

hackaday.com

67 pointsguiambros30 comments

Couldn’t you just hook up a light sensor, temperature sensor, etc and take the last few decimal places of the reading for a random number? You could have multiple and combine the numbers to create larger random numbers. For instance, you have a temperature sensor that reads 72.5946023544 F. This number is always varying, because the temperature in the room isn’t constant. You take the last 4 decimal places, 3544, and there’s your random number. I realize you couldn’t read a temperature sensor to that many decimals, but its just an example. It is never going to create a predictable pattern because its based on something unpredictable.

> Couldn’t you just hook up a light sensor, temperature sensor, etc and take the last few decimal places of the reading for a random number

Heat-entropy is of course one of the best and truest sources of random number generation. But a temperature sensor is far more complicated than what you actually need.

All resistors vary their resistance by temperature. This is called Johnson Nyquist noise (https://en.wikipedia.org/wiki/Johnson%E2%80%93Nyquist_noise). Effectively, every resistor you have on the board is generating white noise.

The question is how to cleanly separate the white noise out, amplify it to measurable levels, and then how to feed that into a computer. Various "white noise generators" trace their true entropy to heat noise (ex: Intel's RDRAND assembly instruction has an oscillator which likely varies due to circuit-level heat noise).

I bet that the voltage across any 10 MOhm resistor would be very noisy, and that could probably be a source of noise for any hardware generator design. The issue with MOhm level resistors is that you start to vary the resistance with physical interaction (a human is in the single-digit MOhm region: so if a human touches the circuit board, the circuit may drop its resistance down to 5MOhms or less, which could affect your circuit design very severely).

You could, and this is more or less how your computer generates random data currently. It takes in lots of data from the environment that would be hard or almost impossible to predict. But the amount of entropy you get out of that might be too low for your needs, so instead you use it as a seed for a pseudorandom number generator.

On Linux you can just feed /dev/random with whatever data you want, and it will be part of your seed.

As far as I know, RNGs on computers use the first few digits, not the last. The reason why, and the problem with using the last, is that your laptop probably measures the voltage of a thermistor coupled to a resistor using an ADC. So you're dependent on an ADC (analog-digital converter) chip that takes voltage and gives you a digital signal. If you have a 12-bit ADC (commonly used to measure voltage), that means you get 2^12=4096 bins. So if your maximum and minimum voltage from the thermistor perfectly line up with the ADC's range, and your temperature can vary from -50 to +50C, then you get increments of 0.025 degrees C. It's pretty easy to see that the last few digits are very much not random, and using them would not work!

(if you spend a bajillion dollars to set up a 32-bit ADC with everything needed, and have a 100C range, you get increments of 100/2^32 = 2.33e-8, now that's precise! This probably would be a bad way to get randomness for about 20 other reasons, though)

I read a whitepaper recently that a MEMS accelerometer can provide sufficient entropy to derive random numbers from. Either way, I would treat external sensors as only a raw entropy source, and use them to drive a CSPRNG reseeded from an entropy pool. I don't think it's cryptographically secure to use the values directly. (Maybe an expert could chime in here?)

I've been looking at ways to get cryptographically secure random bytes on low power micros, and that's the approach I'm taking. The standard for CSPRNGs is AES-GCM, which is a bit heavy, though. Anyone know if Fortuna still acceptable to use?

Looks fine for home made RNG, but not enough for production. What's missed there, since method is using data from MCU RAM, it's better to test MCU RAM first without XOR. Can we be confident that certain bit will be more likely to invert with XOR than another? Would zero's density depend on page index etc. XOR hides a lot of obvious source data errors, which better to fix before applying XOR to avoid some hidden patterns. Also there needs to be some test for input source, for example if page has less than 90% of "ones", skip it, since it cannot provide enough amount of bit inverts to make it random (we need to have enough '1' to invert every bit several times to make it unpredictable).

your 'production' requirements don't have things to do with randomness. its common for cryptographic use cases to have some more steep post processing requirements for randomness sources to avoid some pitfals, but in reality, 111111111 is just as random as 0000000 or 01010101010 as long as it's not a perpetuated pattern?

There is no aim to get one or zero in output. We need to have enough ones for XOR algorithm to invert bits. A xor 1 => inverted A. A xor 0 = A. So if we have too few ones, source data will remain unchanged and that quickly become a pattern. The same is if we have too few zeros and amount of inverts become predictable.

If you need separate hardware anyway, why not just get a ChaosKey¹ and be done with it?

1. http://altusmetrum.org/ChaosKey/

HackADay is a hardware engineering site. The aim of the site is to explore hardware designs.

The ChaosKey is a standard back-to-back transistor-amplifier, likely using Shot-noise or maybe Avalanche Noise as its source of randomness. Nonetheless, I find it to be not too useful, because any modern chip has RDRAND or RDSEED assembly instructions (which the Intel and AMD CPUs use a simple RNG to generate true randomness to those instructions).

So the only reason you'd be building a hardware RNG is because... you're building a hardware design to begin with. The cool thing about this post is that it requires ONLY the microcontroller (no need for the ADC or back-to-back transistors that ChaosKey's design has).

ChaosKey looks like a standard white-noise generator hooked up to a USB Stick. Learning of other methodologies (like what is discussed in Hackaday) is kind of more interesting.

I build an avalanche random number generator based on this: https://emergent.unpythonic.net/01257868826

More fun

Hey, that's my website! I'm tickled pink to see it linked in a comment here.

That device ran for literally ages, mostly to produce massive input files for DIEHARDER to attempt to prove its worth as a RNG. I am sure it did that more often than it was used to seed the Linux /dev/random.

The project was also fun because of the "every last cycle" optimization of AVR assembler code to achieve the 2Mb/s generation rate of whitened bits.

Yes man, was fun to build it. But I pussied out with the layout etching and ordered them custom etched from ebay as a service. During high school I would have done it myself.

BTW, Do you have an up to date software. I remember I run into trouble the last time I tried to use it.

Great project. Thanks a lot.

No, sadly I haven't touched the project in ages.

Will it remain random at high/low voltage and temperatures?

It seems to be whitened, so as long as there is some random information, it will produce good random numbers (but maybe slowly).

The idea is cool: like how to get a random flips out of a biased coin, as long as each flip is independent. You flip the coin twice, repeatedly for as long as you obtain two equal results. Upon your first encounter of two different results, you map (tails,head) to tails and (head,tails) to head. That way you obtain an unbiased toss.

My personal favourite is still the Geiger counter.

how about feeding a white noise signal into a microcontroller and have it sample the random voltages and convert it into a string of numbers.

> how about feeding a white noise signal into a microcontroller

Yeah, its a lot easier to make an RNG if someone already made one for you. How did you create the white-noise signal itself??

----------------

The question is: where did the white-noise come from? And is there any physical way we can "prove" that the white-noise makes a good generator?

The simplest design (IMO anyway) is to start with the Shot Noise (https://en.wikipedia.org/wiki/Shot_noise) that has been well documented in the NP-junction (NPN Transistors, Diodes, etc. etc). The simplest NP-junction is your standard diode... and then just measure the current that goes through that diode (especially if its backwards)

You can measure that current through a series of amplifiers: BJT Transistors to hone in on the noise and amplify it to measurable levels. Then use a microcontroller to read that.

----------------

I'm no expert on hardware RNGs / white noise generators, but that's the kind of thinking you'd need to make one. You have to start with a principle source of noise, and then build a design to amplify that noise as cleanly as possible.

------------------

The hypothesis of this "hackaday" post is that the bootup of uninitialized RAM is a true source of randomness. I'm inclined to believe it (at least, the experimental results show it is at least somewhat reliable), but I'm not 100% sure why.

A common way to handle this for non-cryptographic randomness without using any extra hardware is leave a pin floating that has an A/D converter on it and oversampling it to measure the lowest one or two bits.

Feeding in white noise though requires something to generate that white noise. When extra hardware is available you absolutely generate that noise and getting a higher quality and more reliable source of randomness.

Wouldnt you need some kind if RNG to produce the noise in the first place?

I always sample a few least-significant bits from an floating ADC input. That universal background noise should be pretty random, right?

the example project of the led curtains, beautiful implementation of his idea. really cool stuff!

I tried to search for it but found no pictures. Do you have any?

I wish I could find it again, but I saw a project once that was a meter-long stick of white or blue LEDs hooked up to dozens of shift registers. An RNG would clock in ones or zeros at the end of the stick, and they would shift off to the other end of the stick at a pretty high rate. It was a really neat effect! I've been collecting parts to try to recreate it on my own, but... I'd love to be able to find the original again. If anyone else has seen this, I'd like to hear about it.

BTW truly random numbers can not be used for live communications encryption as they can not be reproduced by the recipient UNLESS they have a EXACT replica of the random numbers or its audio image in a recording (See: American SIGSALY machine during WW2). However pseudo-random numbers can be reproduced live by the recipient via prearrangement but not easily by an outsider (See: German ENIGMA machine also WW2 vintage).

POTUS Thomas Jefferson invented a really amazing encryption machine in 18th century using a quasi-pseudo-random arrangement which utilized the ancient encryption art of Steganography. (See: Jefferson Wheel Cypher). It helped us beat the Brits here in USA and abroad. :P

You are talking about symmetric keys. There's nothing random about it, except for perhaps the generation of said key. If you have a mechanism to generate the same key on both ends, then the mechanism /is/ the key.

They're talking about a product that used one time pads, and you know they must be random to work. The pads were put on vinyl records, and used to encode audio signals for telephone lines.

https://en.wikipedia.org/wiki/SIGSALY

I think you are talking about a OTP here, which needs to be shared before communicating.

But random numbers are also used to generate public/private key combinations, which can be used for live communication after a handshake.

But random number are basic construct of higher level protocol. See Diffie–Hellman key exchange.

Reply on news.ycombinator.com