Bug? VERY predictable output from random()

[atom-smasher]

VERY predictable output from random(), after being seeded with an incrementing counter.

Attached sketch shows how I'm getting four streams of almost perfectly sequential numbers from an algorithm that uses multiple calls to random() after using an incrementing counter as a seed via randomSeed(). It should not be possible to get anything orderly from that, especially over such an immediately short period.

The sketch (below) produces mac-addresses as my original script does, then has four columns: The first three columns show sequential numbers from the high-byte of the last octet, the fourth column shows sequential numbers from the low-byte of the last octet.

Right from the start, with seed 0xb53fdfdf:

// Random Seed:    0xb53fdfdf
     e2:fa:74:b3:a5:9c            9
     0e:9c:eb:97:7f:4c        4        c
     3a:3e:62:7a:59:fc    f         
     6a:e0:d9:5e:34:ac            a
     96:82:50:41:0e:5c        5     
     c2:24:c7:25:e8:0c    0         
     f2:c6:3e:08:c3:bc            b
     1e:68:b5:ec:9d:6c        6     
     4a:0a:2c:d0:77:1c    1         
     7a:ac:a3:b3:52:cc            c
     a6:4e:1a:97:2c:7c        7     
     d2:f0:91:7a:06:2c    2         
     02:92:08:5e:e1:dc            d
     2e:34:7f:42:bb:8d        8     
     5a:d6:f6:25:95:3d    3         
     8a:78:6d:09:70:ed            e
     b6:1a:e4:ec:4a:9d        9        d
     e2:bc:5a:d0:24:4d    4         
     12:5e:d1:b3:ff:fd            f
     3e:00:48:97:d9:ad        a     
     6a:a2:bf:7b:b3:5d    5         
     9a:44:36:5e:8e:0d            0
     c6:e6:ad:42:68:bd        b     
     f2:88:24:25:42:6d    6         
     22:2a:9b:09:1d:1d            1
     4e:cc:12:ec:f7:cd        c     
     7a:6e:89:d0:d1:7d    7         
     aa:10:00:b4:ac:2d            2
     d6:b2:77:97:86:de        d     
     02:54:ee:7b:60:8e    8         
     32:f6:65:5e:3b:3e            3
     5e:98:dc:42:15:ee        e        e
     8a:3a:53:25:f0:9e    9         
     b6:dc:ca:09:ca:4e            4
     e6:7e:41:ed:a4:fe        f     
     12:20:b8:d0:7f:ae    a         
     3e:c2:2e:b4:59:5e            5
     6e:64:a5:97:33:0e        0     
     9a:06:1c:7b:0e:be    b         
     c6:a8:93:5e:e8:6e            6
     f6:4a:0a:42:c2:1e        1     
     22:ec:81:26:9d:ce    c         
     4e:8e:f8:09:77:7f            7
     7e:30:6f:ed:51:2f        2     
     aa:d2:e6:d0:2c:df    d         
     d6:74:5d:b4:06:8f            8
     06:16:d4:97:e0:3f        3        f
     32:b8:4b:7b:bb:ef    e         
     5e:5a:c2:5f:95:9f            9
     8e:fc:39:42:6f:4f        4     
     ba:9e:b0:26:4a:ff    f         

That's seeded with 0x3ffe883c, and that output is near the beginning.

The first three columns to the right of the MAC addresses all show the high-byte of the last octet:

• The 1st column shows 0xf - 0xf, sequentially
• The 2nd column shows 0x4 - 0x4, sequentially
• The 3rd column shows 0x9 - 0x9, sequentially

The 4th column counts the low-byte of the last octet over a longer period, but the whole pattern repeats almost perfectly, and seemingly indefinitely, regardless of how it's seeded. Not the behaviour I expect from a PRNG!

Just looking at the "random" MAC addresses I was wanting, it's obvious that the low-byte of the last octet is repeating for 14-15 times (14.7, on average) and then incrementing. Again, should be 100% impossible to get this from any self-respecting PRNG being seeded by a counter.

nb the sketch has a delay() towards the bottom, so it scrolls up on a console at human-readable speed. For data-collection, just comment out the delay.

nb2 the random seed can be set manually.

sketch:

/*
  ===========================================

  buggy "random()" function, as observed here:
  https://github.com/atom-smasher/esp8266_beaconSpam

  this sketch starts with a random seed "randomMacSeed"

  that seeds the prng via "randomSeed()" and an incrementing counter

  calls to "random()" are producing some very predictable outputs!

  this sketch shows the mac-addresses as they would be generated,
  and derived from those mac-addresses are four columns, all counting
  incrementally, with very few errors

  expected results: using an incrementing counter to seed the prng, i expect
  to NOT have predictable output like this

  ===========================================
*/

const uint64_t randomMacSeed = os_random();     // random seed on startup
//const uint64_t randomMacSeed = 0x1234abcd ;   // fixed seed; make it your own

uint32_t i = 0;
uint8_t  macAddr[5];

void mayhemMac(uint32_t ssidNum) {
  randomSeed(uint32_t((randomMacSeed) + (ssidNum)));
  macAddr[0] = uint8_t(random(0x0, 0x100)) & 0xfe | 0x02 ;
  macAddr[1] = uint8_t(random(0x0, 0x100));
  macAddr[2] = uint8_t(random(0x0, 0x100));
  macAddr[3] = uint8_t(random(0x0, 0x100));
  macAddr[4] = uint8_t(random(0x0, 0x100));
  macAddr[5] = uint8_t(random(0x0, 0x100));
}

void setup() {

  // start serial
  Serial.begin(115200);
  //Initialize serial and wait for port to open:
  while (!Serial) {
    delay(10);
  }
  // wait for serial port to connect
  delay(300);
  Serial.println();

  Serial.printf("\n// Random Seed:    0x%x\n",  uint64_t(randomMacSeed));

}

void loop() {

    for (i = 0; ; i++) {
      yield(); // needed for extra-large lists
      mayhemMac(i);
      Serial.printf("     %02x:%02x:%02x:%02x:%02x:%02x",
        macAddr[0], macAddr[1], macAddr[2], macAddr[3], macAddr[4], macAddr[5]);
        yield();

        if (0 == i % 3) {
          Serial.printf("            %x", macAddr[5] >> 0x4);
        }
        if (1 == i % 3) {
          Serial.printf("        %x     ", macAddr[5] >> 0x4);
        }
        if (2 == i % 3) {
          Serial.printf("    %x         ", macAddr[5] >> 0x4);
        }
        if (1 == i % 15) {
          Serial.printf("   %x", macAddr[5] & 0x0f );
        }

       Serial.println(); 
       delay(200);

       }
    }

Edited to correct how the seed is displayed, and share output with a verified seed.

[nforystek]

I think they would have to incorporate a battery, I just read Arduino has a 58-day limit in buffer overflow with the millis(). I always wonder how that goes. I imagine three internal tickers, one starting at zero, the other at the negative most number, and they both go forward equal same increment rate, and one starts at the positive most spectrum, and goes backwards at half the rate, all three then are part of calculation to issue a millis(), and because millis is never more than a second, you need then to get the calendar clocking segments like second and weeks, whereas when the timer reaching overflow threat approaches, it begins in reverse and the prior reversing one picks up in rate, and the last most slows in rate, like washing or something like that never has a second, but you probably also then need to incorporate dates as a bar association reset of approaching is when? In rate of millis() used to possible catch the buffer overflow and it's a big Y2K mess! But I say that because I think these timer states would be flash saved when booted down, or at a last state type of mode, then booting up the random seeding is partial to the system is unique in back powered up. IDK, though. Tuff one.

[nforystek]

I just read Arduino has a 58-day limit in buffer overflow with the millis(). I always wonder how that goes. I imagine three internal tickers, one starting at zero, the other at the negative most number, and they both go forward equal same increment rage, and one starts at the positive most spectrum, and goes backwards at half the rate, all three then are part of calculation to issue a millis(), and because millis is never more than a second, you need then to get the calendar clocking segments like second and weeks, whereas when the timer reaching overflow threat approaches, it begins in reverse and the pri9or reversing one picks up in rate. Something like that never has a second however, and then pending you can wait out how many years to possible catch the buffer overflow and it's a big Y2K mess! But I say that because I think these timer states would be flash saved when booted down, or at a last state type of mode, then booting up the random seeding is partial to the system is unique in back powered up. IDK, though. Tuff one. You could ignore real time and develop in the calendar intervals, second, minute, day, week, month and year. Just say all Arduino start at a date when powered and kept from the user interaction.

Actually, there is a better way. Query the US court system for the jury selection method, and you'll be going over it in review.