EEVblog Electronics Community Forum

Electronics => Microcontrollers => Topic started by: Stonent on December 08, 2013, 01:31:58 am

Title: Floating input pin to induce randomness
Post by: Stonent on December 08, 2013, 01:31:58 am
I'm working on an idea for a gift based on a small LED matrix necklace. I'd like to randomly change the image on it, and at first thought about some kind of switch that is very sensitive to motion but then thought what about leaving an input pin floating but tied to a part of the necklace that touches bare skin?

It will most likely be based on an ATTiny 2313V or 4313 and powered by a CR2032 battery.

What do you think? Leave a pin floating and use it tied to an interrupt? Or use an analog input that is sampled every so often to grab a number that will control the period of time each image is displayed?

And I understand that I could just as easily have it generate random numbers internally, but I want to have it interactive in some way.
Title: Re: Floating input pin to induce randomness
Post by: dannyf on December 08, 2013, 01:38:39 am
Just sample any pin, Vcc, Vref, a floating pin, or ground pin, etc., literally any pin.

Take the LSB and use a series of LSBs from consecutive sampling to form a random number of desirable width.

Title: Re: Floating input pin to induce randomness
Post by: nctnico on December 08, 2013, 08:26:08 pm
Use the ADC with a few mm of trace on it. Floating input pins will eventually charge to a fixed level.
Title: Re: Floating input pin to induce randomness
Post by: daqq on December 10, 2013, 10:58:28 am
Bad idea - floating input pins are a bad idea all around - they can actually increase your power consumption. Also, ESD - tying a pin into a neklace, well SOME protection should be there.

For randomness you should use an ADC noise (which the 2313 does not have), but it does have a comparator - you might use that somehow.
Title: Re: Floating input pin to induce randomness
Post by: Psi on December 10, 2013, 12:09:56 pm
The random number functions tend to be a bit crap for things you want to "look" random. They're more of a mathematically random system.

A way i found to work well is to fill the eeprom up with the kind of random number you're after. Leave one byte free and have this increment every time the mcu starts.
Use this number as the starting address to begin reading the eeprom.

You can add more complexity, such as having multiple index bytes which are used in sequence if you feel this one byte may exceed its 100,000 writes in normal operation . (eg, if you're using watchdog, brownout).

If you want it to have some actual randomness you can use the comparator noise to set the starting position instead of having a byte incremented.
Title: Re: Floating input pin to induce randomness
Post by: Kjelt on December 10, 2013, 01:32:06 pm
For randomness you should use an ADC noise
If you mean the lsb of an adc with any input then this is not very random at all (tested this and they are very predictable so even the samplerate is important here) but might be good enough for this application.
If you mean that the inputsignal for the ADC has random properties this could be used over time as a source of entropy.
Title: Re: Floating input pin to induce randomness
Post by: NANDBlog on December 10, 2013, 02:05:07 pm
Lot of years ago, I was playing with binary counters and 555s (It wasback in highscool). I left a pin floating. I was perfectly able to pick up 50 Hz (60 for you) in the walls from 20cm distance wit a generic 74 logic gate and 5cm wire, so it was not random anymore.
I would rather make a ring oscillator and sample that. http://nandblog.com/ring-oscillator-time/ (http://nandblog.com/ring-oscillator-time/) or amplify thermal noise, or combination of the ideas given here. Be sure to check it against http://tools.ietf.org/html/rfc4086 (http://tools.ietf.org/html/rfc4086), so they cannot crack the toy ;)
Title: Re: Floating input pin to induce randomness
Post by: c4757p on December 10, 2013, 02:32:43 pm
Yes, sampling a fast oscillator not locked to your own (preferably with lots of phase noise) can work well. Make sure you don't accidentally make an injection-locked oscillator (http://en.m.wikipedia.org/wiki/Injection_locking) out of your main clock though!

You can also use a reverse-biased B-E junction as a noise diode, though you'll need at least 7V or so. I have done that for a similar (but all-analog) blinky-LED doohickey and it works pretty well.
Title: Re: Floating input pin to induce randomness
Post by: dannyf on December 10, 2013, 05:43:45 pm
Quote
If you mean the lsb of an adc with any input then this is not very random at all (tested this and they are very predictable so even the samplerate is important here)

Other than the stock Arduino adc (analogRead()) that is incorrectly implemented, I have yet to say a properly implemented adc not generating sufficiently random data.

The most common mistake is too fast adc that yields some banding - the tendency for the output data to be in certain bands.

The approach essentially depends on the notion that an adc has some inherent randomness - typically the lsb is not stable in the last few lsbs.
Title: Re: Floating input pin to induce randomness
Post by: Kjelt on December 10, 2013, 07:12:07 pm
The approach essentially depends on the notion that an adc has some inherent randomness - typically the lsb is not stable in the last few lsbs.
That is something I researched and tested, I needed entropy for a cryptographically secure random generator. This is ofcourse the most demanding application for randomness.
The thought that the lsb of the adc was random was tested with multiple sampling rates and different kind of input signals and unfortunately found to be not good enough for this purpose (tested with the diehard testsuite, it failed miserably).
The floating base of a normal transistor and some form of amplification of that noise signal as input to an adc was pretty good (schematics can be found on the net and were posted somewhere on this forum also not so long ago) but still very easy to manipulate with an outside signal.
Title: Re: Floating input pin to induce randomness
Post by: SeanB on December 10, 2013, 07:18:04 pm
Use a forward biased LED and AC couple it to the ADC with a lot of gain and you will have a lot of noise along with randomness from the ambient light as well.
Title: Re: Floating input pin to induce randomness
Post by: dannyf on December 10, 2013, 07:44:38 pm
Quote
The thought that the lsb of the adc was random was tested with multiple sampling rates and different kind of input signals and unfortunately found to be not good enough for this purpose (tested with the diehard testsuite, it failed miserably).

There are many reasons that an approach could fail. The fact that it failed doesn't by itself mean that the approach is fundamentally flawed.

If you post your code, schematic and data obtained, I am happy to help you - cannot assure that it will pass any test per se.

The same approach actually does not require a pin to float - you can adc a grounded pin, or a pin connected to an internal source (Vcc or Vref for example). It also works better with higher resolution adc modules (12-bit vs. 10-bit for example).
Title: Re: Floating input pin to induce randomness
Post by: Kjelt on December 10, 2013, 08:10:38 pm
There are many reasons that an approach could fail. The fact that it failed doesn't by itself mean that the approach is fundamentally flawed.
If you post your code, schematic and data obtained, I am happy to help you - cannot assure that it will pass any test per se.
The same approach actually does not require a pin to float - you can adc a grounded pin, or a pin connected to an internal source (Vcc or Vref for example). It also works better with higher resolution adc modules (12-bit vs. 10-bit for example).
As I said I researched it quite a bit and know what can be done there and what not and it is very tricky with a lot of pitholes if you don't test the result. In my company they used a certain algorithm also based on adc noise for years but actually testing it with for instance diehard is quite an eyeopener, it needs 80MB of the generated data to start with and then it keeps on searching for repeating patterns, and it finds enough.
If you don't need it for a cryptographically secure application it probably will be good enough.  If you ever have time, generate 80MB of data from your adc lsb with whatever input you like and run it past the diehard testsuite  ;)
Title: Re: Floating input pin to induce randomness
Post by: Kjelt on December 10, 2013, 08:29:30 pm
BTW there is a difference between statistically randomness and secure randomness,
James Reed has stated this beautifully in an 1977 article called "cracking a random number generator":

Quote
-The usual statistical standards, states that a sequence of numbers, that cannot be discriminated from a sequence of independent uniform deviates from the
unit interval, is considered random. PRNGs that are acceptable by these standards are suitable for simulations, games, and similar applications.

-The cryptography standards have to do with predictability. It is less important whether the sequence is uniformly distributed, but it is essential that knowing part of the sequence does not contribute any knowledge about other parts. This requirement is called unpredictability.
Title: Re: Floating input pin to induce randomness
Post by: dannyf on December 10, 2013, 10:20:52 pm
Quote
it needs 80MB of the generated data...

Again, it is hard to discuss in the abstract. and  you certainly don't need 80MB to share the code, schematic or data or your results - being there and done that.

I am happy to help, again.
Title: Re: Floating input pin to induce randomness
Post by: Stonent on December 11, 2013, 01:21:29 am
Once I get the matrices from Jameco, I will start working on the software. I think the code will be a tight fit but doable.

I've got about 21 patterns that fit in the 5x7 space.
Title: Re: Floating input pin to induce randomness
Post by: dannyf on December 11, 2013, 01:33:29 am
For that, a simple pseudo random variable will work: smaller footprint, and faster execution.

Randomness is over-rated.
Title: Re: Floating input pin to induce randomness
Post by: Stonent on December 11, 2013, 01:38:43 am
For that, a simple pseudo random variable will work: smaller footprint, and faster execution.

Randomness is over-rated.

Well I wanted to hopefully add some level of interactiveness to it. I guess I'll see how the code goes when I get into it.
Title: Re: Floating input pin to induce randomness
Post by: c4757p on December 11, 2013, 01:50:17 am
And I understand that I could just as easily have it generate random numbers internally, but I want to have it interactive in some way.

I completely missed this line.

Generate random numbers internally, and then bias them with a deterministic measurement?
Title: Re: Floating input pin to induce randomness
Post by: Stonent on December 11, 2013, 03:27:09 am
And I understand that I could just as easily have it generate random numbers internally, but I want to have it interactive in some way.

I completely missed this line.

Generate random numbers internally, and then bias them with a deterministic measurement?

Well whatever I do all has to fit in the 2k flash space / 512 bytes of RAM. I figured asking it to do random numbers would take up more flash.
Title: Re: Floating input pin to induce randomness
Post by: c4757p on December 11, 2013, 03:39:35 am
Not much flash at all, if you code efficiently. A Mersenne twister would use a lot of RAM, though, but this algorithm (http://en.wikipedia.org/wiki/Linear_congruential_generator) is very small.
Title: Re: Floating input pin to induce randomness
Post by: Stonent on December 11, 2013, 03:52:47 am
Not much flash at all, if you code efficiently. A Mersenne twister would use a lot of RAM, though, but this algorithm (http://en.wikipedia.org/wiki/Linear_congruential_generator) is very small.

Well now that I think about I need it to erase hard drives and display images.
Title: Re: Floating input pin to induce randomness
Post by: codeboy2k on December 11, 2013, 04:33:15 am
You can use the ADC as a random source, as dannyf says, but no matter what, the entropy generated from sampling the ADC will have bias. Thus it's not truly random, and will fail tests for randomness, such as the Diehard tests, as Kjelt says.  It can likely be used as is for games, blinky lights and what not.

The random sampled data from the ADC can be whitened with a small LFSR, a TGFSR, a huffman compression, a CRC calculation, or a pass through a tiny Mersenne twister (http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/TINYMT/index.html). In a much more simpler way, suitable for a small micro in software, you can examine the bits two at a time and output 1 bit ala Von Neumann: "1,0" -> 1 , "0,1" -> 0 , ("00"|"11")->discard. You can also take the sampled output from two ADCs and XOR them together to get 1 bit stream.

Any of those methods would make it statistically more random, but not necessarily cryptographically random. Clearly Stonent doesn't need cryptographic randomness :) 


Title: Re: Floating input pin to induce randomness
Post by: Stonent on December 11, 2013, 05:57:28 am
Any of those methods would make it statistically more random, but not necessarily cryptographically random. Clearly Stonent doesn't need cryptographic randomness :)

I would call it interactive randomness. Maybe where if the ADC is completely free air that the changing of images slows down significantly but if the input pin picks up something from the necklace making skin contact intermittently that it makes it more likely to change the image. The circuit that I'm going to be basing this on was originally designed to use a push button to change to the next image. Maybe I'll try to find a really small SPST switch that pulls the pin low and makes the images only cycle maybe once ever 10 or 15 seconds but if left open it starts changing more with activity.

Or even forego the switch and come up with some kind of part of the necklace like a clasp or something that depending on its position it changes the behavior.
Title: Re: Floating input pin to induce randomness
Post by: Psi on December 11, 2013, 06:16:57 am
You could add a SPI/I2C temp sensor to your micro, that would give you some unpredictability you could use.
Especially if the sensor could do 0.1 deg C resolution
Title: Re: Floating input pin to induce randomness
Post by: mimmus78 on December 11, 2013, 11:05:05 am
24 bit ADC is better :-)
Title: Re: Floating input pin to induce randomness
Post by: dannyf on December 11, 2013, 12:27:33 pm
Quote
if the input pin picks up something...

This is where you completely missed the approach outlined earlier. The point isn't to adc anything - if you did that, you will have biasness in the output as pointed out to you by others.

The point, instead, is to utilize the inherent randomness in the adc module - even if you adc a fixed voltage, you don't get the same results - by picking up the lsb.

Again, for what you do, a pseudo random number generator wold work more than fine.
Title: Re: Floating input pin to induce randomness
Post by: Kaptein QK on December 11, 2013, 12:58:56 pm
I got a good result from the following method:
http://www.avrfreaks.net/index.php?name=PNphpBB2&file=viewtopic&t=45522 (http://www.avrfreaks.net/index.php?name=PNphpBB2&file=viewtopic&t=45522)

Only 4 resistors and one cap, and it is good enough for blinky lights and stuff like that.

Title: Re: Floating input pin to induce randomness
Post by: dannyf on December 11, 2013, 02:28:24 pm
Two similar approaches, along the same vine of thoughts:

1) use the onboard low-power oscillator: better with rc but crystal oscillator works as well. Use it to gate the main oscillator and pick the lsb.

2) use two io pins, + a cap (to gnd) and a resistor (to vcc / or one io pin). Use one io pin to discharge the cap and another to read the voltage over the cap as it is being charged by Vcc / the other io pin. Once the 2nd io pin turns high (you can use external int on that pin), read a timer powered by the main oscillator, and then reset the timer and discharges the capacitor.

As RC oscillators are fairly unstable (both in frequency + phase), you get fairly good results.
Title: Re: Floating input pin to induce randomness
Post by: dannyf on December 11, 2013, 02:29:08 pm
Just wanted to add that in the 2nd approach, you read the lsb as well.
Title: Re: Floating input pin to induce randomness
Post by: codeboy2k on December 11, 2013, 03:01:55 pm
I like both those from dannyf.  #1 uses just internal oscillators and counters, so fewer external parts.  #2 is interesting, but I'd rather it use the RC oscillator as well. I'm actually going to try that one out myself.

...... and don't forget, no matter which method you use to get that lsb, thou shalt whiten it :)

at least use the von Neumann method, which doesn't guarantee any more randomness than the source, but will guarantee a bitstream without any bias.

This thread has been very interesting with all the different approaches suggested.
Title: Re: Floating input pin to induce randomness
Post by: dannyf on December 11, 2013, 03:25:09 pm
The 2nd approach is actually how (external) rc oscillators are implemented on most mcus.
Title: Re: Floating input pin to induce randomness
Post by: dannyf on December 11, 2013, 11:27:29 pm
Quote
2) use two io pins, + a cap (to gnd) and a resistor (to vcc / or one io pin).

That is a more generic set-up.

On mcus where weak pull-up is available, you can actually save that resistor and use only one capacitor and use one io pin:

1) enable the weak pull-up on the io pin, set up the pin as output and output a low on that pin.
2) set up the rest of your system - rising edge on int or pcint, timer, etc.
3) turn that pin as input - the weak pull-up will start to charge up the capacitor.
4) once the voltage across the capacitor triggers the int / pcint: in the isr, turn the pin to output - this discharges the capacitor; read the timer's lsb, reset it (optionally), and then turns the pin into an input - this starts to charge up the capacitor again.

On the avr, the coding is slightly different as it doesn't have separate bits to enable the weak pull-up but the general idea remains the same.

The speed depends on the strength of the weak pull-up and the capacitor used.
Title: Re: Floating input pin to induce randomness
Post by: Stonent on December 12, 2013, 05:31:13 am
The idea will be this:

http://electronics.stackexchange.com/questions/82794/5x7-led-matrix-on-a-c-without-additional-parts (http://electronics.stackexchange.com/questions/82794/5x7-led-matrix-on-a-c-without-additional-parts)

(http://i.imgur.com/zVioBrC.jpg)

So adding parts makes it less presentable.