Originally Posted by

**PaulStoffregen**
Are you saying we should be 3 separate libraries? Or 1 library with 3 distinct APIs?

I mean 3 distinct APIs. Whether you want it all in one library, or split the crypto hash to a separate one, I do not know.

With a tested ISAAC-based PRNG, I'd be happy with a single one.

The Xorshift64*/hi-32 itself is trivial:

Code:

static volatile uint64_t prng_state; /* Any nonzero state is valid! */
uint32_t prng_u32(void)
{
uint64_t x = prng_state;l
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
prng_state = x;
return (x * UINT64_C(2685821657736338717)) >> 32;
}

If prng_state is initialized to nonzero value, it will never become zero, and the sequence generated by prng_u32() will pass all TestU01's BigCrunch tests. The period is 2^{64}-1, too.

To add entropy from any source, you simply exclusive-or any 64-bit word to prng_state that does not yield a zero, because zero is invalid state for LFSR-type generators.

Combining a fast prng_u32() function and a DMA or interrupt-based entropy mixing might need some atomic ops around the state access, the state being 64 bits.

You can combine a separate state and a randomly varying (DMA-modified?) entropy source using

Code:

static volatile uint64_t prng_state; /* Any nonzero state is valid! */
static volatile uint64_t entropy_source;
uint32_t prng_u32(void)
{
uint64_t x = prng_state ^ entropy_source;
x += !x;
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
prng_state = x;
return (x * UINT64_C(2685821657736338717)) >> 32;
}

where the x += !x just ensures zero state is never used. (It does not matter which other state is used; 1 is just as good as any other.)

A cryptographically secure PRNG could be as simple as

Code:

static volatile uint32_t cryptoprng_cache[16]; /* 512 bits */
static volatile unsigned char cryptoprng_have; /* Cached 32-bit words */
static inline uint32_t cryptoprng_u32(void)
{
if (cryptoprng_have < 1)
cryptoprng_refill();
return cryptoprng_cache[--cryptoprng_have];
}
void cryptoprng_refill(void)
{
uint32_t ciphertext[16] = {
prng_u32(), prng_u32(), prng_u32(), prng_u32(),
prng_u32(), prng_u32(), prng_u32(), prng_u32(),
prng_u32(), prng_u32(), prng_u32(), prng_u32(),
prng_u32(), prng_u32(), prng_u32(), prng_u32()
};
some_512_bit_crypto_hash(&cryptoprng_cache, ciphertext);
cryptoprng_have = 16; /* Or 8 - 15, if you want */
}

Originally Posted by

**PaulStoffregen**
How to blend true hardware random data with a pseudo-random generator isn't 100% clear to me. My gut feeling says to just xor the random bits into the seed value. Is that really the right way? Or is there some better practice?

Yes, exclusive-OR is the right way; it will never reduce entropy.

There is some math that proves that even when the xor'd values have little randomness in them, it will never reduce the randomness in the state.

The only problems are when generators have forbidden or weak states. (LFSRs tend to have only one, all zeros, which needs to be avoided; ISAAC's "weak states" are mathematical curiosities and do not affect its reliability; xor works fine for both.)

Originally Posted by

**PaulStoffregen**
Is there any really compelling reason to use simpler/faster pseudo random like LFSR or linear congruence when something like ISAAC offers to make the internal data secret at a cost of some RAM and only slightly slower speed?

Compelling? No. ISAAC is in public domain, and widely used as a cryptographically secure PRNG. I just haven't used ISAAC before. (On 64-bit arches, the above prng_u32() is significantly faster than ISAAC, and unlike ISAAC, LFSR behaviour is easily "proven" mathematically. Which is kinda important for scientific work, although I often do switch to Mersenne Twister just to avoid having to explain the PRNG choice.)

Any reason? The above prng_u32() only needs 64 bits of state, is fast enough to use even with the exclusion method (to get un-biased values within a range, dropping up to half the generated values), and is trivial to implement correctly. ISAAC is complex; you have to test the implementation against the original.

Don't use LCGs, they aren't random enough. Their non-randomness often appears obvious when used to e.g. initialize a 2D matrix (like LED strings).

Would I implement my own prng_u32() if verified-correct ISAAC is available? Probably not. ISAAC also passes BigCrush, and on a 32-bit architecture should be just as fast as the above prng_u32().

Getting a good random initial state is nontrivial, and generating 8192 bits of initial state is lots more work than generating 64 bits of initial state – but then again, you can safely use an internal PRNG to generate the initial state using a smaller truly random seed; for example, seed the ISAAC 1024-byte state with a Xorshift PRNG seeded with 64 bits of hardware random numbers, then continuously mix in entropy to the ISAAC state.