Forum Rule: Always post complete source code & details to reproduce any issue!
Results 1 to 14 of 14

Thread: Teensy 4.1 Random Number Generator

  1. #1
    Member randomvibe's Avatar
    Join Date
    Mar 2016
    Location
    CA
    Posts
    94

    Teensy 4.1 Random Number Generator

    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 Code:
    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 Code:
    https://www.pjrc.com/teensy/td_libs.html
    Is the T4 RNG really slower than the T3.6?

  2. #2
    Member randomvibe's Avatar
    Join Date
    Mar 2016
    Location
    CA
    Posts
    94
    Odd. Unable to edit my original post. Can this be changed?

  3. #3
    Senior Member+ manitou's Avatar
    Join Date
    Jan 2013
    Posts
    2,584
    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 ...

  4. #4
    Member randomvibe's Avatar
    Join Date
    Mar 2016
    Location
    CA
    Posts
    94
    512 random bits in 52780 us is too slow for my project.

    For now I will use the T4 true random number generator (TRNG) as the random seed.

    Then use a fast pseudo random generator (PRNG) in the feedback loop. Will try the ISAAC method, a fast cryptographic random number generator:

    https://forum.pjrc.com/threads/48745...l=1#post164151

  5. #5
    Member randomvibe's Avatar
    Join Date
    Mar 2016
    Location
    CA
    Posts
    94
    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:

    Click image for larger version. 

Name:	randhist.jpg 
Views:	23 
Size:	253.7 KB 
ID:	20532

    Click image for larger version. 

Name:	randhist.jpg 
Views:	21 
Size:	52.4 KB 
ID:	20533

    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
    Attached Thumbnails Attached Thumbnails Click image for larger version. 

Name:	randplot.jpg 
Views:	13 
Size:	231.3 KB 
ID:	20531  

  6. #6
    Senior Member PaulStoffregen's Avatar
    Join Date
    Nov 2012
    Posts
    22,685
    Quote Originally Posted by manitou View Post
    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.
    Attached Files Attached Files

  7. #7
    Senior Member+ manitou's Avatar
    Join Date
    Jan 2013
    Posts
    2,584
    Quote Originally Posted by PaulStoffregen View Post
    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.

  8. #8
    Senior Member
    Join Date
    Feb 2015
    Location
    Finland
    Posts
    216
    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.

  9. #9
    Senior Member PaulStoffregen's Avatar
    Join Date
    Nov 2012
    Posts
    22,685
    Quote Originally Posted by manitou View Post
    this .cpp requires the TRNG_... symbols. I don't find them defined yet in imxrt.h.
    Oh, yeah, those were separately committed to the core library.

    1.53-beta2 is now available with the updated imxrt.h file and this copy of Entropy.

    https://forum.pjrc.com/threads/61451...no-1-53-Beta-2

  10. #10
    Senior Member PaulStoffregen's Avatar
    Join Date
    Nov 2012
    Posts
    22,685
    Quote Originally Posted by Nominal Animal View Post
    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?

  11. #11
    Senior Member+ manitou's Avatar
    Join Date
    Jan 2013
    Posts
    2,584
    Quote Originally Posted by randomvibe View Post
    512 random bits in 52780 us is too slow for my project.
    Using Paul's TRNG sample mode configuration (2) from entropy lib in my T4 TRNG test sketch is faster (13484 us for 512 bits) and NIST statistical tests are good.

    https://forum.pjrc.com/threads/54711...l=1#post195000

  12. #12
    Senior Member+ manitou's Avatar
    Join Date
    Jan 2013
    Posts
    2,584
    Quote Originally Posted by PaulStoffregen View Post
    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
    Attached Files Attached Files
    Last edited by manitou; 06-20-2020 at 09:17 PM.

  13. #13
    Senior Member PaulStoffregen's Avatar
    Join Date
    Nov 2012
    Posts
    22,685
    I've updated Entropy here, so this will be in 1.53-beta3.

  14. #14
    Senior Member
    Join Date
    Feb 2015
    Location
    Finland
    Posts
    216
    Quote Originally Posted by PaulStoffregen View Post
    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 */
    }
    Quote Originally Posted by PaulStoffregen View Post
    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.)

    Quote Originally Posted by PaulStoffregen View Post
    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.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •