Philip Guenther wrote in
<cakkmsniq-4zlisp5nwqsz4z367s2a0b8rxu5-urtqdnwqfr...@mail.gmail.com>:
|On Tue, May 17, 2022 at 1:10 PM Steffen Nurpmeso <stef...@sdaoden.eu> \
|wrote:
|> Joerg Sonnenberger wrote in
|> <yoqhj3yy9qrax...@bec.de>:
|>|Am Fri, May 13, 2022 at 09:43:26AM -0500 schrieb Luke Small:
|>|> I made a couple new versions of a new kind of arc4random_uniform-like
|> ...
|>|If your main use case is limiting the amount of cryptography when using
|>|small bounds, there is a much simpler approach to be taken here. For
|>|boundaries below 256, use arc4random_buf to extract one byte if bound is
|>|a power of two, otherwise two. This gives most of the performance
...
|> You can use (really implemented) _buf() if you need a 8-bit or
|> 16-bit etc number.
|>
|> I find that _uniform() often makes no difference to a simple
|> modulo because like the comment in _uniform() says "p > 0.5 (worst
|>case, usually far better", and usually RNGs sprinkle bits nicely,
|
|What does that statement mean? You seem to be saying "module is uniform,
|except when it isn't, which could be almost half the time for some cases,
|but when it's uniform it's uniform, so why bother making it actually
|correct and dependable".
|
|I mean, what does that _mean_??? It's as if I said "my text handling
Well it means this thread was too long.
|program handles all characters uniformly, except those with accents, but
|that's less than 10% of the characters I type, so it handles all characters
|uniformly." WTF, NO!
But it also means that
// calculates 2**32 % range
uint32_t t = (-range) % range;
for (;;) {
uint32_t r = rng();
if (r >= t)
where range is a very small number results in a very, very low
probability that r>=t is not true. For 16-bit 0xFFFF two zero
bytes had to occur in the upper 16-bit. And worse for 64-bit RNG.
So this is what i said. It depends on the application.
This gets hypothetic and is anyway beyond my mathematical
capabilities. I mean i look at /etc/ssh/moduli, so much on
cramping of random numbers.
The web site that has been linked from the man from the country
that has an even much worse Earth Country Overshoot Day than
Germany and is almost en par with Australia or even USA (April
3rd, pooh; never again a Saab! Cuba: Nov 25th, Jamaica Dec 20th)
said the bias for the number 52 is 0.00000121%. And what i posted
had ~0.008 that rand<0x01FFFFFF aka 32-bit high byte is 0, for
32-bit from getrandom(2) as well as mine (in "strong" mode,
SipHash on ARC4).
You need quite some samples to be able to find a statistical
frequency of that order. And it depends on the application of
that many samples exist.
And even TCP from RFC 793 / September 1981 has a 32-bit sequence
number.
But sure Philip, of course, yes, of course you are right: simply
call _uniform() and "milk the shit out of the random range" --
just use it and forget about the problem.
What surprised me was that the Apple code requires more calls, and
that today divisions and multiplications still matter. I think it
was the Cyrix 166+ (or was it Athlon 1600+) where +,-,<<,>> was
one cycle, * was ten cycles, and %,/ was fourty cycles. But
i think the Core i5 8th Gen that i have requires one cycle for all
of them. (And somewhere i read that there are CPUs where the
shift operators are now more expensive than multiplication.)
I do not really track any of that since 2005. That is nice: you
buy a laptop and suddenly have a NVME SSD that can 1.5GB/sec.
Wow.
|> 0 bytes "do not occur", so a 32-bit RNG value "is" >=0x01FFFFFF in
|> most cases for "my RNG" (of 100000 803/759/793 NOT; 776/805/793
|> NOT for Linux getrandom(2)), which is a pretty high cut off.
...
|Where do these ideas come from, that "0 bytes 'do not occur'"?? If your
|rand generator doesn't provide zero bytes at the expected frequency, you
|know, 1 in 256, then you're using a garbage random number generator.
|Please stop making such suggestions here because THEY ARE NOT TRUE ABOUT
|OPENBSD. Do ya'll not bother to test the claims that you make?
...
| for (;;) {
| u = arc4random();
| if ((u & 0xff000000) == 0 ||
| (u & 0x00ff0000) == 0 ||
| (u & 0x0000ff00) == 0 ||
| (u & 0x000000ff) == 0)
| break;
That is any-byte-0.
|00b82e5c 58
|ab478800 36
Seems random to me.
:)
--steffen
|
|Der Kragenbaer, The moon bear,
|der holt sich munter he cheerfully and one by one
|einen nach dem anderen runter wa.ks himself off
|(By Robert Gernhardt)
