AVR Hardware RNG questions...

[alank2]

Hi Everyone,

So, I found this LM393 based solution here:

http://www.jtxp.org/tech/xr232usb_en.htm

I like that it doesn't require 10+ volts to operate and I built up one and it does look decent on my scope.

My questions are?

1.  Why XOR each random byte with a previous one from X bytes ago, in the case of this example, 512 bytes ago.  What purpose does this serve?

2.  He uses a technique of running assembly that bumps a counter and checks to see if the input pin from the hardware RNG has changed.  If it has, then we uses the LSB of that counter (which also happens to divide it by 2) as the random bit.  So, a signal change means grab a bit from the timer.  He isn't using a real AVR timer, but a register in his loop that he is incrementing.

Do each of these things effectively become some type of filter?  For whitening?  Something else?

His source code has three versions of the assembly.  One that skips the xor, and another that calls itself raw data (no timer bit grabbing).

Thanks,

Alan

[alank2]

Also, if you are really smart, can this be adapted to run on 3.3V with modifying the circuit?  Right now if I turn the voltage down to 3.3V, it it becomes periodic.

[Hideki]

Also, if you are really smart, can this be adapted to run on 3.3V with modifying the circuit?  Right now if I turn the voltage down to 3.3V, it it becomes periodic.

From the page you linked to: "The proposed noise circuitry works reliable with operating voltage from 4 V up."

[orolo]

1.  Why XOR each random byte with a previous one from X bytes ago, in the case of this example, 512 bytes ago.  What purpose does this serve?

In bit stream generators like this, it is customary to 'scramble' the hardware genereated bits in order to mask any correlation that might show up. The general idea is that the hardware side is not truly random, but only random to some degree, an imperfect entropy source. An example is /dev/random in linux: it takes entropy timing intervals between key presses and other such events, and then passes those bits through a strong (for the time I reviewed the code, years ago) hash function, like SHA-2. The result is a highly scrambled sequence of bits, not fully random, but good enough for most purposes.

In this case, I think the author tried to reduce correlation between succesive bits xoring the current output with some long past output, in order to reduce transient artifacts.

2.  He uses a technique of running assembly that bumps a counter and checks to see if the input pin from the hardware RNG has changed.  If it has, then we uses the LSB of that counter (which also happens to divide it by 2) as the random bit.  So, a signal change means grab a bit from the timer.  He isn't using a real AVR timer, but a register in his loop that he is incrementing.

This is more like /dev/random as I remember it. Use a discrete counter to time the difference between two events, and then discard all the bits save the least significant one (the most entropic, since it's updated more often. The greater the number of bits between events, the better.) This doesn't mean that last bit is truly random; it's just apparently the most random of them all, from an information theory viewpoint.

Do each of these things effectively become some type of filter?  For whitening?  Something else?

Think of the bit generator not as truly random, but as an entropy source of varying quality. Sadly, it's not as easy as discarding the wrong bits and keeping the good ones. The correlation is distributed among all the bits, and each one is truly random only to some degree. An intelligent attacker could predict patterns in the raw output, and build an attack from there. Since you can't discard the bad bits, at least you can mask the correlation toroughly hashing the bit stream with a strong cryptographic function. The xor mechanism is not thorough at all, but it's something: a LFSR with only one element. A longer, more thorough LFSR using several past inputs irregularly distributed would be better, and not that difficult to implement.

From a hardware point of view, I don't like this circuit. As I understand it, it depends on the noise on the power rail and the inverting input of the comparator to generate the timed events. A good part of that noise might come from clocking and I/O events in the logic ICs, which are not very random, or not random at all. The author also writes that the circuit is vulnerable to interference if not enclosed. Though I only browsed it quickly, the diehard test provided didn't seem that bright. Anyway, without a substantial investment of time, I coudln't say if this scheme is really good or not.

[bingo600]

Allan , maybe this one doesn't have the 4v min


http://robseward.com/misc/RNG2/#code

https://forum.arduino.cc/index.php?topic=161682.0


/Bingo

[alank2]

Bingo, I think those required the 10V+.

Thanks for the details orolo - I've been watching the circuit on my scope and at 5V, it will randomly slam to both rails and sometimes bounce between them a number of times before hitting the rail again.  I dropped it to 3.3V and it becomes mostly periodic, but altering the R2/10K to 40-60K seems to bring most of the chaos of the 5V mode with the 10K.  I think I am going to try the von Neumann approach of looking for a 10 or 01 combination to become 0 or 1 bits.  Looking at it on the scope, if I sample at 5uS periods, it looks like there won't be much of a pattern to it.  I'll try that and feed a long session of it to ENT and see how it does.

[alank2]

Also orolo - do you have any ideas for a 3.3V circuit that is oscillating wildly?

[orolo]

Instead of a zener, a low voltage bandgap could do the trick: a TL431 has 120nV/sqrtHz, and the TLV431 is even better at 200. I'll tinker a bit with that idea and come back with the results.

[tszaboo]

Also orolo - do you have any ideas for a 3.3V circuit that is oscillating wildly?

3 not gates in series  fed back as a ring will oscillate anywhere up to some 100Mhz.

[alank2]

An update - my experiments feeding the LM393 into an AVR input pin have not been so good.  Even if apply the Von Neumann technique of translating a 1 then 0 or 0 then 1 into a 1 or 0 bit, I still get results that are not even average of 190 or so instead of 127.5.  If I flip it, then it averages too low.  It makes me wonder if the physical attributes of the input pin such as it takes an absence of signal for a period of time for it to go low perhaps are a factor.

I also tried the watchdog method of using the watchdog timer to trigger an interrupt that uses the LSB timer clocked with the main clock.  It produces decent results, but is pretty slow if you need a lot of random data.  Can't beat how few components it needs though!

I read a page where someone was complaining that the AVR ADC was completely unsuitable (it might have been the LM393 page), but I'm not so sure about this.  I fed a white noise signal from my siglent generator into an ADC pin and have the best results so far.  7.3M samples chi-square 59.42 with ENT.  It can produce around 1200 bytes per second and that is only grabbing one ADC bit.  I'm using:

Code: [Select]

      for (c4=c5=0;c5<4;c5++)
        {
          again:
          ADCSRA|=_BV(ADIF) | _BV(ADSC);
          while (!(ADCSRA & _BV(ADIF)))
            ;
          c1=ADC & _BV(0);

          ADCSRA|=_BV(ADIF) | _BV(ADSC);
          while (!(ADCSRA & _BV(ADIF)))
            ;
          c2=ADC & _BV(0);
          if (c1==c2)
            goto again;

          c4<<=1;
          c4|=c1;//ADC & _BV(0);
        }

      tx(pgm_read_byte(&Hex[c4]));

So, what I'd love is if we could come up with a decent white noise generator that runs on 3.3V only.

Feeding the LM393 into the ADC gives terrible results.  ENT chi-square goes to 0.01 or 99.9 very quickly and stays there.  I tried to eliminate results that were railed such as 0 and 1023, but it still was terrible.

[orolo]

I've been experimenting with the TL431 for noise generation, and it looks promising. Since I'm breadboarding, I've started working at 5V, and then I'll reduce it to 3.3V.

The setup is: one TL431 is configured to output 2.5V like a zener, and is coupled via an RC high-pass to an op-amp (LM358) x100 non-inverting amp. The output is again RC high-pass coupled to a x50 LM358 non-inverting amp, for a total gain of 5000.

The low pass filters and the limited response of the 358 are chosen to give us uniform power noise only in the 1kHz-5kHz band, approx.

The resulting noise is quite satisfactory (see below for details):



Since the LM358 is quite noisy itself, I also disconnected the bandgap and measured the signal, to confirm that I was picking up bandgap noise and not other background signal. The noise is greatly diminished with the bandgap off.



Both the TL431 and LM358 should keep working at 3.3V. I'll experiment with that.

To extract binary data from this setup, I would design a comparator with hysteresis that is centered on the average of the noise. This is more or less equivalent to detecting when a random walk crosses two boundaries around the average: if the crossing is positive, a logic 0 to 1 transition happens. If the crossing is on the negative side, logic 1 to 0. This should give a random jittering square oscillator with an average frequency given by the distance between the boundaries, and with a frequency jitter almost normally distributed.

As long as I keep having free time, I'll keep experimenting with this idea.

Edit: by the way, the LFSR way to deskewing can be much better in throughput and security than Von Neumann correction if used right. An interesting reference. I also remember reading about some improvements to Von Neumann correction taking more than 2 bits, but the reference was in Spanish and buried somewhere in my library.

[alank2]

Can you post a schematic of what you are trying?  I can try to duplicate it.

[orolo]

Okay, after some more experimentation I'm abandoning the LM358 in favor of simple CE bjt amps, because this op-amp is unable to reach the higher rail and it spoils the behavior of the circuit. With a rail to rail op amp the circuit works, but I don't have any availabe. I've discovered this after painfully veroboarding a version of the circuit, and watching the assymetric behaviour. I should have expected it  .

Ok, the whole circuit is attached below. I used the LT1797, which is a R2R op-amp which comes with LTSPICE. The voltage source "Noisy" simulates the noise in the bandgap. Take the noise from the bandgap, and amplify it x5000, at the same time filtering it. This I did in my breadboarded version, and it worked fine. Then add a regulable amplifier after it, to fine-tune the noise level. After that, use a comparator with hysteresis to generate oscillations.

The comparator, having the resistors almost equal, has the higher hysteresis level at 3.75 volts, and the lower at 1.25 volts. That means that, when the noise goes over 3.75 volts the oscillator goes low (inverting), and it doesn't go high until the noise moves under 1.25 volts. And so on. A picture of the output signal of the comparator is attached below: as you can see, it is quite aperiodic, and its characteristics are statistically tractable, if we assume the noise source is white and filtered.

The last image attached is the noise spectrum from a simulation of a TL431 with the x5000 amp + filter applied.

I hope the idea is more or less clear.

Edit: there is a mistake in the picture of the circuit (not in the ASC model). The "rail" voltage is at 2.5V, not at 5V. Sorry.

[alank2]

That looks really good orolo.  Can a different opamp be substituted for the LT1797 - they are around $2.65 each at digikey.

Also, and I hesitate to ask because you have already done so much, what are your thoughts on a white noise generator?  This looks like it has a nice square wave output, but if that was skipped, could a white noise generator be done with less components and 3.3V ?  I had pretty good luck feeding the white noise from my SDG2082X into the ADC, but most white noise circuits I've found are for much higher voltages.

Thanks again!!!

Alan

[orolo]

Sorry for the delay. I'm intrigued enough about this circuit to build it, so I've ordered some MCP6241T, the cheapest rail to rail op amps I could find at Mouser. That, toghether with a noisy low voltage bandgap like TLV431, which I've also ordered, should work well below 3.3V.

I'm not really sure if a bandgap has really white noise, or there are other artifacts. Can a real white noise generator be built from a resistor? While I wait for the components to arrive, I'm going to try this:



The trouble with high value resistors is that even the pf capacitance of the JFET severely limits the bandwidth of the noise. Even the JFET cascode manages a -3dB point in the tens of kHz range. The noise at the source of the FET is:



And, after the two BJT amps, it is:



This noise source looks really interesting. I want to see what it looks like, the circuit is easy to build, but clearly it cannot be breadboarded, due the huge capacitances involved. I'll try with deadbug construction, and see what happens.

Trying a low voltage zener is useless, I think. If I remember correctly, at low voltages the dominant effect is tunneling, and the main source in that case is shot noise. The noise should not differ greatly from a regular diode.