2 out of 6 bytes produced by BLI_rng_get_char_n() are predictable #91395

New Issue

Sybren A. Stüvel · 2021-09-14T09:20:11+02:00

Sybren A. Stüvel commented

2021-09-14 09:20:11 +02:00

System Information
Operating system: Kubuntu Linux 20.04 LTS

Blender Version
Broken: current master @ 9fe6854a93
Worked: didn't check with older versions

Short description of error
BLI_rng_get_char_n() seems to produce predictable bytes, regardless of the seed used.

Exact steps for others to reproduce the error
Run this program a few times, and take note of the fact that the seed changes on every run, but the magenta columns stay the same between runs.
P2390: (An Untitled Masterwork)


#include "BLI_rand.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

static struct RNG *rng = NULL;
static inline void maybe_initialise_rng(void);
static void free_rng(void);
void generate_random(void);

int main(void)
{
  for (int i = 0; i < 10; ++i) {
    generate_random();
  }
  return 0;
}

void generate_random()
{
  maybe_initialise_rng();

  uint8_t buffer[36];
  BLI_rng_get_char_n(rng, (char *)buffer, sizeof(buffer));
  for (int index = 0; index < (int)sizeof(buffer); index++) {
    if (index % 6 == 0) {
      printf("\033[95m");
    }
    printf("%02x ", buffer[index]);
    if ((index - 1) % 6 == 0) {
      printf("\033[0m");
    }
  }
  printf("\n");
}

static void free_rng()
{
  BLI_rng_free(rng);
  rng = NULL;
}

static inline void maybe_initialise_rng()
{
  if (rng != NULL) {
    return;
  }

  struct timespec ts;

  timespec_get(&ts, TIME_UTC);
  unsigned int seed = (ts.tv_nsec >> 32) ^ (ts.tv_nsec & 0xFFFFFFFF);
  rng = BLI_rng_new_srandom(seed);
  srand(seed);
  fprintf(stderr, "%s: RNG allocating, seeding with %u\n", __func__, seed);
  atexit(free_rng);
}

I compiled this with g++ -Wall -std=c++17 -o rng_test rng_test.cc -I ./source/blender/blenlib/ ../build_linux/lib/{libbf_blenlib.a,libbf_intern_guardedalloc.a}, but I've seen the same behaviour using it to generate random bytes for generating UUIDs within Blender, so this shouldn't be caused by my simplified compilation options.

This is a screenshot of the output I get on my machine (screenshotted so that the highlighted colums are maintained)

Proposed Solution

Fixing this issue would break a lot of things in existing files (e.g. layout of particles or hair, or patterns of procedural textures, etc.). Since there is no versioning possible here, this issue could be fixed in two steps:

Rename current broken API e.g. with a _deprecated prefix, but keep using it everywhere it is currently used in code.
Add a new API with proper behavior.
Use the new API everywhere it is possible without breaking compatibility, and also for new code.
Wait for the next compatibility-breaking release (Blender 4.0) to switch the whole existing code to the new API.

**System Information** Operating system: Kubuntu Linux 20.04 LTS **Blender Version** Broken: current master @ 9fe6854a93 Worked: didn't check with older versions **Short description of error** `BLI_rng_get_char_n()` seems to produce predictable bytes, regardless of the seed used. **Exact steps for others to reproduce the error** Run this program a few times, and take note of the fact that the seed changes on every run, but the magenta columns stay the same between runs. [P2390: (An Untitled Masterwork)](https://archive.blender.org/developer/P2390.txt) ```c #include "BLI_rand.h" #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> static struct RNG *rng = NULL; static inline void maybe_initialise_rng(void); static void free_rng(void); void generate_random(void); int main(void) { for (int i = 0; i < 10; ++i) { generate_random(); } return 0; } void generate_random() { maybe_initialise_rng(); uint8_t buffer[36]; BLI_rng_get_char_n(rng, (char *)buffer, sizeof(buffer)); for (int index = 0; index < (int)sizeof(buffer); index++) { if (index % 6 == 0) { printf("\033[95m"); } printf("%02x ", buffer[index]); if ((index - 1) % 6 == 0) { printf("\033[0m"); } } printf("\n"); } static void free_rng() { BLI_rng_free(rng); rng = NULL; } static inline void maybe_initialise_rng() { if (rng != NULL) { return; } struct timespec ts; timespec_get(&ts, TIME_UTC); unsigned int seed = (ts.tv_nsec >> 32) ^ (ts.tv_nsec & 0xFFFFFFFF); rng = BLI_rng_new_srandom(seed); srand(seed); fprintf(stderr, "%s: RNG allocating, seeding with %u\n", __func__, seed); atexit(free_rng); } ``` I compiled this with `g++ -Wall -std=c++17 -o rng_test rng_test.cc -I ./source/blender/blenlib/ ../build_linux/lib/{libbf_blenlib.a,libbf_intern_guardedalloc.a}`, but I've seen the same behaviour using it to generate random bytes for generating UUIDs within Blender, so this shouldn't be caused by my simplified compilation options. This is a screenshot of the output I get on my machine (screenshotted so that the highlighted colums are maintained) ![image.png](https://archive.blender.org/developer/F10411250/image.png) ------------------- # Proposed Solution Fixing this issue would break a lot of things in existing files (e.g. layout of particles or hair, or patterns of procedural textures, etc.). Since there is no versioning possible here, this issue could be fixed in two steps: - Rename current broken API e.g. with a `_deprecated` prefix, but keep using it everywhere it is currently used in code. - Add a new API with proper behavior. - Use the new API everywhere it is possible without breaking compatibility, and also for new code. - Wait for the next compatibility-breaking release (Blender 4.0) to switch the whole existing code to the new API.

Sybren A. Stüvel commented

2021-09-14 09:20:11 +02:00

Added subscriber: @dr.sybren

Sybren A. Stüvel commented

2021-09-14 09:20:30 +02:00

Added subscriber: @JacquesLucke

Sybren A. Stüvel changed title from ~~4 out of 6 bytes produced by BLI_rng_get_char_n() are predictable~~ to 2 out of 6 bytes produced by BLI_rng_get_char_n() are predictable

2021-09-14 09:20:40 +02:00

Dalai Felinto commented

2021-09-14 11:35:08 +02:00

Added subscriber: @dfelinto

Bastien Montagne commented

2021-09-20 16:52:28 +02:00

Changed status from 'Needs Triage' to: 'Confirmed'

Ray molenkamp commented

2021-09-20 18:49:13 +02:00

Added subscriber: @LazyDodo

Ray molenkamp commented

2021-09-20 18:49:13 +02:00

The seed function expands a 32 bit value into a 64 bit one with the following code:

 void seed(uint32_t seed)
  {
    constexpr uint64_t lowseed = 0x330E;
    x_ = (static_cast<uint64_t>(seed) << 16) | lowseed;
  }```

which leads to the following value for the first value of `x_` where any nibble marked X will have a fixed value

0x0000725f1ea2330e
0xXXXX........XXXX


`RandomNumberGenerator::seed_random(uint32_t seed)` tries to be clever and randomize the seed a little further however it seems unaware of the odd behavior of the `seed` function

void RandomNumberGenerator::seed_random(uint32_t seed)
{

this->seed(seed + hash[seed & 255]);
seed = this->get_uint32();
this->seed(seed + hash[seed & 255]);
seed = this->get_uint32();
this->seed(seed + hash[seed & 255]);

}```

this does a great job at randomizing bits 16..48 but "fixed" bits will still have their fixed values, which are reflected in the output of the RNG

Given there's many things relying on the behavior of this RNG it's not really recommended to change the seed function, however something like

{
constexpr uint64_t lowseed = 0x330E;
x_ = (static_cast<uint64_t>(seed) << 16) | lowseed;
x_ = x_ ^ static_cast<uint64_t>(seed);
}

would do the trick, The upper 16 bits being zero is not an issue since they are being discarded anyhow.

The seed function expands a 32 bit value into a 64 bit one with the following code: ``` void seed(uint32_t seed) { constexpr uint64_t lowseed = 0x330E; x_ = (static_cast<uint64_t>(seed) << 16) | lowseed; }``` which leads to the following value for the first value of `x_` where any nibble marked X will have a fixed value ``` 0x0000725f1ea2330e 0xXXXX........XXXX ``` `RandomNumberGenerator::seed_random(uint32_t seed)` tries to be clever and randomize the seed a little further however it seems unaware of the odd behavior of the `seed` function ``` void RandomNumberGenerator::seed_random(uint32_t seed) { ``` this->seed(seed + hash[seed & 255]); seed = this->get_uint32(); this->seed(seed + hash[seed & 255]); seed = this->get_uint32(); this->seed(seed + hash[seed & 255]); ``` }``` this does a great job at randomizing bits 16..48 but "fixed" bits will still have their fixed values, which are reflected in the output of the RNG Given there's many things relying on the behavior of this RNG it's not really recommended to change the seed function, however something like ``` void seed_all_bits(uint32_t seed) ``` { constexpr uint64_t lowseed = 0x330E; x_ = (static_cast<uint64_t>(seed) << 16) | lowseed; x_ = x_ ^ static_cast<uint64_t>(seed); } ``` ``` would do the trick, The upper 16 bits being zero is not an issue since they are being discarded anyhow.

Ray molenkamp commented

2021-09-20 19:53:01 +02:00

Unrelated, your initial seed selection based on time has some issues on windows where sizeof(long) == 4 even on 64 bit

  unsigned int seed = (ts.tv_nsec >> 32) ^ (ts.tv_nsec & 0xFFFFFFFF);

shifting a 32 bit variable by 32 bits has some fun undefined behavior (5.8 from the C++ spec) where the result (not in spec, but all compilers do this) is the original value rather than 0 , leading to ts.tv_nsec^ts.tv_nsec which is.... 0 :)

Unrelated, your initial seed selection based on time has some issues on windows where `sizeof(long) == 4` even on 64 bit ``` unsigned int seed = (ts.tv_nsec >> 32) ^ (ts.tv_nsec & 0xFFFFFFFF); ``` shifting a 32 bit variable by 32 bits has some fun undefined behavior (5.8 from the C++ spec) where the result (not in spec, but all compilers do this) is the original value rather than 0 , leading to `ts.tv_nsec^ts.tv_nsec` which is.... 0 :)

Raimund Klink commented

2021-09-21 10:23:06 +02:00

Added subscriber: @Raimund58

Philipp Oeser removed the

Download

What's New

Blender Studio

Manual

Developers Blog

Documentation

Benchmark

Blender Conference

Development Fund

One-time Donations

2 out of 6 bytes produced by BLI_rng_get_char_n() are predictable #91395

Proposed Solution