Pages: 1 [2]   Go Down
Author Topic: Foolproofing a randomizer  (Read 3136 times)
0 Members and 1 Guest are viewing this topic.
Global Moderator
Dallas
Offline Offline
Shannon Member
*****
Karma: 212
Posts: 13085
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

More out of curiosity than anything, has anyone built a cheap "high" quality RNG for Arduino, for some value of "high"?

There is this...
http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1268761421

In my testing, it performed very poorly.  The raw and cooked values followed noticeable patterns.  The algorithm can sometimes take a very long time to generate values.

The strategy is just on the verge of working / not working.  Any little tweak of the code and the values fall into a degenerative state (e.g. all ones, always toggle, all zeros, no value produced).

Quote
I was thinking of connecting a reverse biased Zener...

The ideal hardware solution would generate an interrupt when more entropy is available.  This would allow data to be collected in the background.  Something like this may work...

● Relatively low speed independent "unstable" oscillator (the entropy source)

● Connected to an interrupt pin on the processor

● Timer 1 or timer 2 configured to "run free"

● When the interrupt fires, record the least significant bit from the timer

Quote
feed all that into a CRC-32

I'd stay away from CRC.  I don't think it works well as a random mixing function.

Quote
The PRNG could be an Xorshift type generator.  Something that doesn't need to keep too much state, but has good statistical performance.

I don't know if it's an Xorshift type generator but rand / random does well with most statistical tests.

Quote
Better would be something that is suited to feeding extra entropy into over time.

XOR values from rand with values from a hardware generator.
Logged

Ontario
Offline Offline
God Member
*****
Karma: 25
Posts: 913
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

The AVR-libc random() is a Park and Miller linear congruential PRNG with a period of 2^31.  It's fine if it's seeded properly, but it's not great.  I was thinking that something with a longer period might be nice.  Xorshift is fast, has a period of 2^64 and still only needs 64 bits of state.  Either way, the problem is really to seed it right.

Quote

That's interesting.  I wasn't able to see what he actually did to set-up/read the A2D.  I am not convinced that the A2D has enough sensitivity -- or maybe not enough sensitivity in all cases -- to get a useful amount of entropy without some extra wiring external to the Arduino.  The temperature sensor mentioned here looks like a better bet:

Quote

I'm not surprised that folks would have issues with using these directly to generate random bits.  The whitening algorithm is not guaranteed to complete in any specific time, which leads to problems if you use it in the normal course of getting random bits.  What I would propose is to use a source like this just to seed a conventional PRNG.  The conventional PRNG should be fast, with predictable run-time in the 100s of instructions.

Quote
independent "unstable" oscillator

Yes, the "clock skew" method.  This would be fine.

 That's kind of what I was also suggesting with feeding an analogue waveform into the A2D from a simple 555 circuit.  Only my feeling was that you should be able to get ~4 or more bits of entropy from the circuit on demand, and not have to have any code around for storing it or have to mess with interrupts.  Just read bits, wait a few ms and read more bits.

Quote
I'd stay away from CRC.  I don't think it works well as a random mixing function.

The idea would be to use this only for generating the seed.  If we guess that an A2D reading has 1/4 of a bit of entropy in it, we can read it 128 times and feed all the readings into a CRC-32 to obtain a concentrated 32-bit seed from that.  CRC has a couple of good properties:  It is easy to calculate and requires very little memory and it provably combines all the input bits into all the output bits.  It is not cryptographically secure, but that's not the requirement.  It performs the same basic function as the Von Neumann whitening, but has deterministic run time.

Quote
XOR values from rand with values from a hardware generator.

No, I don't like that.  I want the new entropy to go into the PRNG state, not just into the output.  Re-seeding via srandom(random() + new_entropy_bits) maybe.  I'm not sure if the properties of Park and Miller or Xorshift are suited to that.  I'm not an expert.

I also don't want to be obligated to come up with hardware randomness when the code asks for a PRNG, since that risks non-deterministic behaviour of the main get-me-a-random-number() method.
Logged

Global Moderator
Dallas
Offline Offline
Shannon Member
*****
Karma: 212
Posts: 13085
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

I was thinking that something with a longer period might be nice.  Xorshift is fast, has a period of 2^64 and still only needs 64 bits of state.

Do you have a generator in mind?

Quote
Either way, the problem is really to seed it right.

That's certainly the issue that comes up in the forum.

Quote
Quote
That's interesting.  I wasn't able to see what he actually did to set-up/read the A2D. 

It doesn't work like this but this is how I visualize what happens: Enable the pull-up resistor so the pin goes high.  Turn off the pull-up resistor and start a conversion.  At a certain point, the falling pin voltage and the rising comparison voltage cross paths and the conversion completes.  The theory is that the two voltages cross at a random point in the conversion.

Quote
I am not convinced that the A2D has enough sensitivity

I believe it does.  From my testing, the problem is that the only potential source of entropy from an AVR processor is the digital noise generated by the processor itself which is not at all random. 

It's important to remember that AVR processors are meant to be very deterministic and it's tough to get anything random out of something that is deterministic.

Quote
-- or maybe not enough sensitivity in all cases -- to get a useful amount of entropy without some extra wiring external to the Arduino. 

I agree!

Quote
The temperature sensor mentioned here looks like a better bet:

My testing does not bear that out.  (comments in that thread)

Quote
Quote
I'd stay away from CRC.  I don't think it works well as a random mixing function.
It performs the same basic function as the Von Neumann whitening, but has deterministic run time.

The reason Von Neumann is not deterministic is because of a lack of entropy.  That potential problem also applies to CRC (and everything else).  If you can collect enough data (128 quarter bits in your example) for the CRC to produce a result than you can also collect enough data for Von Neumann to produce a result.  If you cannot collect enough data, then neither will produce a result.

Quote
Re-seeding via srandom(random() + new_entropy_bits) maybe. 

The problem with re-seeding is that it potentially invalidates the statistical tests that are performed on the generator to prove its quality.

Quote
Quote
XOR values from rand with values from a hardware generator.
No, I don't like that.

In that case...

Quote
The idea would be to use this only for generating the seed.

...is the best choice.
Logged

Global Moderator
Melbourne, Australia
Online Online
Brattain Member
*****
Karma: 511
Posts: 19365
Lua rocks!
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

I was thinking that something with a longer period might be nice. 

Mersenne Twister

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ewhat-is-mt.html

Claimed there:

Quote
Far longer period and far higher order of equidistribution than any other implemented generators. (It is proved that the period is 2^19937-1, and 623-dimensional equidistribution property is assured.)
Logged

http://www.gammon.com.au/electronics

Please post technical questions on the forum - not to me by personal message. Thanks a lot.

Ontario
Offline Offline
God Member
*****
Karma: 25
Posts: 913
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

I was thinking that something with a longer period might be nice. 
Mersenne Twister

I suspect you're joking, but M-T needs over 600 bytes of state and is pretty computationally expensive.  I want something with 48 or 64 bits of state that is computationally cheap.  And ideally something that has a known re-seeding procedure.  An L-C or LFSR is good for a small state.
Logged

Global Moderator
Netherlands
Offline Offline
Shannon Member
*****
Karma: 227
Posts: 14048
In theory there is no difference between theory and practice, however in practice there are many...
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

maybe this one?
Code:
/*
An example of a simple pseudo-random number generator is the
Multiply-with-carry method invented by George Marsaglia. It is
computationally fast and has good (albeit not cryptographically
strong) randomness properties.

m_w = <choose-initializer>;    // must not be zero
m_z = <choose-initializer>;    /* must not be zero
 
uint get_random()
{
    m_z = 36969 * (m_z & 65535) + (m_z >> 16);
    m_w = 18000 * (m_w & 65535) + (m_w >> 16);
    return (m_z << 16) + m_w;  /* 32-bit result
}
*/

void setup()
{
  Serial.begin(115200);
}

void loop()
{
  Serial.println(getRandom());
}


// An example of a simple pseudo-random number generator is the
// Multiply-with-carry method invented by George Marsaglia.
// two initializers (not null)
unsigned long m_w = 1;
unsigned long m_z = 2;

unsigned long getRandom()
{
    m_z = 36969L * (m_z & 65535L) + (m_z >> 16);
    m_w = 18000L * (m_w & 65535L) + (m_w >> 16);
    return (m_z << 16) + m_w;  /* 32-bit result */
}

Relative simple code, needs two longs = 64 bit -   < 10 uSec @16Mhz; randomness => google smiley
Logged

Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

Ontario
Offline Offline
God Member
*****
Karma: 25
Posts: 913
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Quote
Multiply-with-carry method invented by George Marsaglia

Yes, that's a good one too.  I did find it, but I was not personally familiar with it.
I think this one has a period of ~2^63 which is great.
Logged

Pages: 1 [2]   Go Up
Jump to: