On Thu, Aug 06, 2020 at 10:18:55AM -0700, Marc Plumb wrote:
Willy,
On 2020-08-05 11:30 p.m., Willy Tarreau wrote:
On Wed, Aug 05, 2020 at 03:21:11PM -0700, Marc Plumb wrote:
There is nothing wrong with perturbing net_rand_state, the sin is doing it with the raw entropy that is also the seed for your CPRNG. Use the output of a CPRNG to perturb the pool all you want, but don't do things that bit by bit reveal the entropy that is being fed into the CPRNG.
This is interesting because I think some of us considered it exactly the other way around, i.e. we're not copying exact bits but just taking a pseudo-random part of such bits at one point in time, to serve as an increment among other ones. And given that these bits were collected over time from not very secret sources, they appeared to be of lower risk than the output.
No. The output of a CPRNG can't be used to determine the internal state. The input can. The input entropy is the one thing that cannot be produced by a deterministic computer, so they are the crown jewels of this. It's much much safer to use the output.
OK, noted.
I didn't know about SFC32, it looks like a variation of the large family of xorshift generators, which is thus probably quite suitable as well for this task. Having used xoroshiro128** myself in another project, I found it overkill for this task compared to MSWS but I definitely agree that any of them is more suited to the task than the current one.
It's actually a chaotic generator (not a linear one like an xorshift generator), which gives it weaker period guarantees which makes it more difficult to reverse. With a counter added to help the period length.
I'll trust Amit that SFC32 isn't strong enough and look at other options -- I just thought of it as better, and faster than the existing one with the same state size. Maybe a larger state is needed.
Just to give a heads up on this, here's what I'm having pending regarding MSWS:
struct rnd_state { uint64_t x, w; uint64_t seed; uint64_t noise; };
uint32_t msws32(struct rnd_state *state) { uint64_t x;
x = state->w += state->seed; x += state->x * state->x; x = state->x = (x >> 32) | (x << 32); x -= state->noise++; return x ^ (x >> 32); }
It passes PractRand without any warning after 1 TB of data:
rng=RNG_stdin, seed=unknown length= 512 megabytes (2^29 bytes), time= 2.0 seconds no anomalies in 229 test result(s)
rng=RNG_stdin, seed=unknown length= 1 gigabyte (2^30 bytes), time= 4.3 seconds no anomalies in 248 test result(s)
rng=RNG_stdin, seed=unknown length= 2 gigabytes (2^31 bytes), time= 8.3 seconds no anomalies in 266 test result(s)
rng=RNG_stdin, seed=unknown length= 4 gigabytes (2^32 bytes), time= 15.8 seconds no anomalies in 282 test result(s)
rng=RNG_stdin, seed=unknown length= 8 gigabytes (2^33 bytes), time= 31.3 seconds no anomalies in 299 test result(s)
rng=RNG_stdin, seed=unknown length= 16 gigabytes (2^34 bytes), time= 61.9 seconds no anomalies in 315 test result(s)
rng=RNG_stdin, seed=unknown length= 32 gigabytes (2^35 bytes), time= 119 seconds no anomalies in 328 test result(s)
rng=RNG_stdin, seed=unknown length= 64 gigabytes (2^36 bytes), time= 242 seconds no anomalies in 344 test result(s)
rng=RNG_stdin, seed=unknown length= 128 gigabytes (2^37 bytes), time= 483 seconds no anomalies in 359 test result(s)
rng=RNG_stdin, seed=unknown length= 256 gigabytes (2^38 bytes), time= 940 seconds no anomalies in 372 test result(s)
rng=RNG_stdin, seed=unknown length= 512 gigabytes (2^39 bytes), time= 1906 seconds no anomalies in 387 test result(s)
rng=RNG_stdin, seed=unknown length= 1 terabyte (2^40 bytes), time= 3826 seconds no anomalies in 401 test result(s)
The two modifications compared to the original msws are:
- mix bits on output so that we don't reveal the internal state upon each call ;
- combination of the output with an independent noise variable whose purpose was to be updated upon IRQ and/or CPU usage and/or invocations. But on this point, while implementing it I figured that updating it on each invocation did already provide the frequent updates we were missing in Tausworthe that required the interrupt updates. I'd definitely update in update_process_times() so that it's not reduced to a pure counter, but the results, speed and simplicity look encouraging.
I'll try to work on finishing the patch proposal this week-end.
Regards, Willy