Teensy 4.1 Random Number Generator

randomvibe

Well-known member
Finally jumped on the Teensy 4 bandwagon. Just received a couple of 4.1 boards, and two 4.0 boards. Tried compiling a T3.6 robotic project on the 4.1, but got this error related to my Random Number Generator (RNG) function:

Code:
'SIM_SCGC6' was not declared in this scope

I did found this thread by @manitou:

HTML:
https://forum.pjrc.com/threads/54711-Teensy-4-0-First-Beta-Test?p=195000&viewfull=1#post195000

Is that the latest on RNG for Teensy 4? Couldn't find anything on the official Teensy library site:

HTML:
https://www.pjrc.com/teensy/td_libs.html

Is the T4 RNG really slower than the T3.6?
 
yep, as noted in this post, T4 TRNG is much slower than T3.5/3.6 TRNG. T4 TRNG has lots of tuning options, mainly to strengthen "randomness" at a cost of even slower speed. Limited documentation due to NDA requirements. Paul hopes to integrate T3/T4 TRNG into entropy library ...
 
Running the Teensy4.1 TRNG exclusively with 0.1 million samples took ~90 minutes - too slow.

Using the TRNG as a random seed for the ISAAC PRNG is a decent cryptographic generator and very fast. 0.1 million samples ran in 0.028 seconds. I plotted the random numbers and its histogram. No discernible patterns can be seen. Histogram is flat as expected. See images:

randhist.jpg

randhist.jpg

An astronomical number of samples are required to detect bias. The ISAAC PRNG has not been broken since 2001 according to this article:

http://www.burtleburtle.net/bob/rand/isaacafa.html
 

Attachments

  • randplot.jpg
    randplot.jpg
    231.3 KB · Views: 86
Paul hopes to integrate T3/T4 TRNG into entropy library ...

Here's a copy of Entropy (which will be in 1.53-beta2) with Teensy 4.x TRNG support. On Teensy 3.5 & 3.6 it's still using the slow timer drift approach rather than the hardware random.
 

Attachments

  • Entropy.cpp
    14.9 KB · Views: 239
Here's a copy of Entropy (which will be in 1.53-beta2) with Teensy 4.x TRNG support. On Teensy 3.5 & 3.6 it's still using the slow timer drift approach rather than the hardware random.

this .cpp requires the TRNG_... symbols. I don't find them defined yet in imxrt.h.
 
For non-cryptographic work, I recommend using one of the Xorshift variants; many of them are as random as Mersenne Twister, but much faster. In fact, my preferred one, using only the 32 high bits of Xorshift64*, passes all BigCrush tests, and has a 64-bit state and period of 264-1 (zero initial state is the only invalid one); making it in a real sinse even more random than Mersenne Twister. For Teensy 3.x and 4.x, Xorshift64* is ridiculously fast, just a handful of cycles per 32-bit pseudorandom number generated, and it is random enough for even scientific simulations and statistical work.

(TestU01's BigCrush is a library for testing randomness, and at least in some sense represents the "state of the art" in randomness tests. It does not test for cryptographic security, it is more about whether patterns can be detected in the generated sequences or not.)

Xorshift and other linear feedback shift register type generators are also nice in that they typically work fine with any state except all-zeros. This means that if you have a hardware randomness source, you can exclusive-or it to the Xorshift state (as long as the result is nonzero!), adding entropy from the HW source to the generated sequence. This is how desktop and server computers manage their security-sensitive pseudo-random number generation. (Cryptographically secure sequences are furthermore put through a cryptographic hash function, optionally dropping some of the output bits.)

Cryptographically secure pseudorandom number generators have a different qualification criteria: most of the bits in each generated value should be unpredictable, not just random. In particular, knowing N previous values, the number of possible values for the next generated values should not decrease. Typical implementations use only a part of the generated values, combining them into chunks of a suitable size, and putting each chunk through a cryptographically secure hash function, essentially producing a stream of cryptographically secure and random bits. Really paranoid implementations drop also a fraction of bits from that output, making hash collisions basically irrelevant – but in all cases, the state of the original pseudorandom number generators being secret and not extractable/observable is key. (Dropping bits from the output is an effort of providing even less information about that internal state.)

Personally, I see 'pseudorandom', 'hardware-random', and 'crypto-random' as separate facilities, all producing good random numbers, but for different purposes; (and that list in order of increasing computational resources needed per output word). Pseudorandom should be fast and pass most/all BigCrunch tests; hardware-random could be used to seed or import entropy to pseudorandom generation; and crypto-random used for anything related to security.

Just my opinion, though.
 
Personally, I see 'pseudorandom', 'hardware-random', and 'crypto-random' as separate facilities, all producing good random numbers, but for different purposes; (and that list in order of increasing computational resources needed per output word). Pseudorandom should be fast and pass most/all BigCrunch tests; hardware-random could be used to seed or import entropy to pseudorandom generation; and crypto-random used for anything related to security.

Just my opinion, though.

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

I'm asking because the Entropy library appears to be unmaintained (I sent an email to Walter Anderson - so far no reply) and as far as I know, there is no other good quality random number library for the Arduino world. An earlier library called "True Random" was so buggy that it really can't be taken seriously.

Entropy is GPLv3. Not a huge problem, but I would prefer to eventually replace it with something MIT licensed.

My gut feeling is most people want something simple, like what you get from /dev/urandom on Linux...


if you have a hardware randomness source, you can exclusive-or it to the Xorshift state (as long as the result is nonzero!), adding entropy from the HW source to the generated sequence. This is how desktop and server computers manage their security-sensitive pseudo-random number generation.

Currently Entropy is about hardware random only, with some "whitening" done in the case of the timers.

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?

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?
 
Here's a copy of Entropy (which will be in 1.53-beta2) with Teensy 4.x TRNG support. On Teensy 3.5 & 3.6 it's still using the slow timer drift approach rather than the hardware random.

I've added hardware TRNG for T3.5/3.6 to attached Entropy.cpp. Random bits are generated at 7.5 megabits/sec compared with 125 bits/sec for duelling clocks (timer drift approach).

ref T3.5/3.6 TRNG
 

Attachments

  • Entropy.cpp
    15.9 KB · Views: 162
Last edited:
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 264-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 */
}

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.)

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.
 
Back
Top