d it a bug):
* usr.bin/ssh/auth.c:
- *cp = hashchars[arc4random_uniform(sizeof(hashchars) - 1)];
+ *cp = hashchars[arc4random_range(0, sizeof(hashchars) - 1)];
Reconsidering, this one is probably better just as
arc4random_uniform(sizeof(hashchars)).
I was also wrong here.
I was confu
ch the old *_uniform() code.
>>
>> Below are the cases where I changed the behavior (I considered it a bug):
>>
>> * usr.bin/ssh/auth.c:
>>
>> - *cp = hashchars[arc4random_uniform(sizeof(hashchars) - 1)];
>> + *cp = hashchars[arc4ran
- *cp = hashchars[arc4random_uniform(sizeof(hashchars) - 1)];
+ *cp = hashchars[arc4random_range(0, sizeof(hashchars) - 1)];
Reconsidering, this one is probably better just as
arc4random_uniform(sizeof(hashchars)).
* usr.sbin/ftp-proxy/ftp-proxy.c:
- return (IPPORT_H
are rare.
For example, array indices run from 0 to sizeof(array)-1,
sizeof(array) points to the storage location beyond the last element,
and C programmers are used to that. So the was arc4random_uniform(3)
works feels familiar to C programmers, whereas your proposal
of arc4random_range(3)
vious ones (although I may be wrong) I fixed them. And in some
cases where it was very unclear, I didn't touch the old *_uniform() code.
Below are the cases where I changed the behavior (I considered it a bug):
* usr.bin/ssh/auth.c:
- *cp = hashchars[arc4random_uniform(sizeof(hash
We will not be using your code.
End of story.
Luke Small wrote:
> Marc, all you all have to do is say is that you all refuse to provide it.
Marc, all you all have to do is say is that you all refuse to provide it.
I was asked to at least provide evidence for correctness. I did so; and I’d
say I did a stellar job aside from getting some kind of statistical program.
The following has an attached source code for my test (along with
refe
On Sat, May 21, 2022 at 07:47:40AM -0500, Luke Small wrote:
> Perhaps it was rude sending off list stuff to the list. Your email sounded
> "less than friendly" and more of a professional challenge that you were
> definitely in the works to produce; much like Damien Miller’s challenge to
> prove cor
:
I worked in __builtin_clz(upperbound-1) mentioned earlier in the thread;
instead of my binary search. It made the knuth sort simulation run even
faster. arc4random_uniform now takes 130% of the time mine takes for a
series of random numbers decreasing from 65535 to 2.
“__builtin_clz((upperbound - 1
On Fri, May 20, 2022 at 09:48:28PM -0500, Luke Small wrote:
> Crystal: You can prove that for random, repetitive, correct, database
> record name generation using small upperbounds, the demonstrated 1/3-1/2
> runtime isn???t worth it for an upperbound like 26 - 92 in a business context
> that fight
Crystal: You can prove that for random, repetitive, correct, database
record name generation using small upperbounds, the demonstrated 1/3-1/2
runtime isn’t worth it for an upperbound like 26 - 92 in a business context
that fights for every last millisecond?
Bring it.
Prove the correctness of wha
wrote a highly dynamically allocated program to test at intervals of
intervals to show at various stages to show the degree that the output
remains random
This is an example of some output:
testing arc4random_uniform(5) and arc4random_uniform_small_unlocked(5):
256X
wrote a highly dynamically allocated program to test at intervals of
intervals to show at various stages to show the degree that the output
remains random
This is an example of some output:
testing arc4random_uniform(5) and arc4random_uniform_small_unlocked(5):
256X
Joerg Sonnenberger wrote in
:
|Am Wed, May 18, 2022 at 12:49:21PM +0200 schrieb Steffen Nurpmeso:
|> 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 +,-
Am Wed, May 18, 2022 at 12:49:21PM +0200 schrieb Steffen Nurpmeso:
> 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 cycle
Steffen Nurpmeso wrote in
<20220518104921.sr0ht%stef...@sdaoden.eu>:
...
|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 Saa
Philip Guenther wrote in
:
|On Tue, May 17, 2022 at 1:10 PM Steffen Nurpmeso \
|wrote:
|> Joerg Sonnenberger wrote in
|> :
|>|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
|> ..
een in the web page were because of less rnd
calls. That was a mistake.
> What Theo said is 100% right - the cost is dominated by that of the
> underlying RNG. If anyone wants a faster arc4random_uniform() then the
> first place to look it at arc4random().
One more reason to keep the curre
of suceeding (at least for small upper_bounds) than
mask-and-test, but my brain is too addled with a cold to calculate it :/
What Theo said is 100% right - the cost is dominated by that of the
underlying RNG. If anyone wants a faster arc4random_uniform() then the
first place to look it at arc4r
On Wed, May 18, 2022 at 02:50:28PM +1000, Damien Miller wrote:
> On Tue, 17 May 2022, Raimo Niskanen wrote:
>
> > Why reinvent the wheel?
> >
> > Here is a pretty good walkthrough of established methods:
> >
> > https://www.pcg-random.org/posts/bounded-rands.html
> >
> > It sounds to me as
> However, I don't see a speedup for either of the alternate approaches.
Or maybe, just maybe, the underlying function (arc4random, which in the
dominant case it is just a small chacha step) is so inexpensive relative
to the proposed higher-level logic changes? So this is all tilting at
windmills
On Tue, 17 May 2022, Raimo Niskanen wrote:
> Why reinvent the wheel?
>
> Here is a pretty good walkthrough of established methods:
>
> https://www.pcg-random.org/posts/bounded-rands.html
>
> It sounds to me as if your suggested methor essentially is
> "Bitmask with Rejection -- Apple's Meth
On Tue, May 17, 2022 at 1:10 PM Steffen Nurpmeso wrote:
> Joerg Sonnenberger wrote in
> :
> |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 l
Steffen Nurpmeso wrote in
<20220517220924.xohqc%stef...@sdaoden.eu>:
|Joerg Sonnenberger wrote in
| :
||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
...
|0 bytes "do not occur", so
Joerg Sonnenberger wrote in
:
|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
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
> function and some example functions which use them. Instead of having a
> sufficiently large random number greater than the modulus, I pick a random
>
getchar” doesn’t
> “see also” to getchar_unlocked() by the way.)
>
> If you look at profiling with programs that call it a lot,
> arc4random() inside arc4random_uniform() calls the expensive rekey
> function which makes it take more time. That’s why I can get around
> 2X-3X performance on
that call it a lot, arc4random()
inside arc4random_uniform() calls the expensive rekey function which makes
it take more time. That’s why I can get around 2X-3X performance on a
typical repetitive small upperbound loop and an extra 20% improvement on a
single 65536 Knuth shuffle, loop even though my
how often are you even
calling arc4random_uniform to consider it slow?!)
if the consequence is not a crash but instead subtly broken randomness,
how long do you think it's going to take to notice and report/fix it?
even *very* broken randomness in widespread software distributions
has been kno
No...am I incorrect, especially on OpenBSD?
Of course since you made such a remark, you seem like the kind of fellow
that would put the nail in the coffin for spite.
...now I sound like an asshole.
On Mon, May 16, 2022 at 4:00 PM Theo de Raadt wrote:
> hey luke you know you sound like an assho
hey luke you know you sound like an asshole right?
Luke Small wrote:
> If you’re not running a threaded program, my function wouldn’t be “less
> safe.”
>
> I’d imagine that 99% of programs aren’t multithreaded.
>
> On Mon, May 16, 2022 at 1:01 PM wrote:
>
> > > There is the specifically non
If you’re not running a threaded program, my function wouldn’t be “less
safe.”
I’d imagine that 99% of programs aren’t multithreaded.
On Mon, May 16, 2022 at 1:01 PM wrote:
> > There is the specifically non-threadsafe call getchar_unlocked() on
> OpenBSD
> > which is presumably available for pe
w upper bound then modulo will "remove a
|> lot of randomization". For example if you have a program which
|> generates Lotto numbers (1..49), then using _uniform() as it is will
|> generate many duplicates.
|
|Wut. The *WHOLE POINT* of arc4random_uniform() is that it ha
Luke Small on Sun, May 15 2022:
> The current implementation is nothing more than a naive arc4random() %
> upper_bound which trashes initial arc4random() calls it doesn’t like,
Yes, that's exactly what it is.
> The whole transformation by modulus of perfectly decent random data
> seems so awkward
Yeah. It most likely won't go in. From past experience and advice, not
necessarily just from a perceived lack of merit.
However, many, if not all of the arguments are based upon non-facts and
misconceptions from earlier submissions or just not understanding what the
software is doing.
The only re
I’m not trying to be rude, but you don’t realize what’s going on here:
uuu is a bitmask:
‘uuu’ (or (1 << bits)-1 ) in “ret = rand_holder & uuu;“ , only puts the
lower ‘bit’ quantity of bits of rand_holder into ret, then it right shifts
rand_holder afterward to trash them every time in the loop wh
ets the parameters of being a value less than the upper bound. Much
> > like
> > > arc4random_buf().
> > >
> > > If I use arc4random_uniform() repeatedly to create a random distribution
> > of
> > > say numbers less than 0x1000 or even something weird
gt; like
> > arc4random_buf().
> >
> > If I use arc4random_uniform() repeatedly to create a random distribution
> of
> > say numbers less than 0x1000 or even something weird like 0x1300 will the
> > random distribution be better with arc4random_uniform() or with mine
per bound. Much like
> arc4random_buf().
>
> If I use arc4random_uniform() repeatedly to create a random distribution of
> say numbers less than 0x1000 or even something weird like 0x1300 will the
> random distribution be better with arc4random_uniform() or with mine? For
> 0x1000
beginning of another) 32 bit pseudorandom
> cipher is "correct."
You don't need to understand chacha20 to understand .
arc4random_uniform() I certainly didn't when I wrote it.
The underlying CSPRNG is irrelevant to how arc4random_unifo
Do I really have to use specific terminology to make a point?
I'm not educated enough on chacha20 enough to know whether, like I pointed
out, whether choosing 5 bits from the middle of (or even from the tail end
of one and the beginning of another) 32 bit pseudorandom cipher is
"correct."
...corr
On Sun, 15 May 2022, Luke Small wrote:
> The current implementation is nothing more than a naive arc4random() %
> upper_bound which trashes initial arc4random() calls it doesn’t like, then
> transforms over a desired modulus. The whole transformation by modulus of
> perfectly decent random data see
;
> But I don't think anybody else execpt Luke was talking about
> "improving". The sole purpose of arc4random_uniform() is to give a
> good implementation of a random number function in a specific range
> using arc4random() as the source. This is needed because t
t has already more or less made that point.
>
I think I can say we know here uniformity is only *one* of the
desirable properties of a secure random generator.
But I don't think anybody else execpt Luke was talking about
"improving". The sole purpose of arc4random_uniform() is to give a
good implementation of a random number function in a specific range
using arc4random() as the source. This is needed because the naive
implementation arc4random() % upper_bound is not uniform.
-Otto
On Sun, May 15, 2022 at 11:44:29AM +0200, Otto Moerbeek wrote:
> On Sun, May 15, 2022 at 04:27:30AM -0500, Luke Small wrote:
> > How did someone prove the current implementation was cryptographically
> > sound? Did they run massive simulations which ran the gamut of the uint32_t
> > range which dem
Random generators have been analyzed for years.
Pick up "Concrete mathematics" by Don E. Knuth, read it, then come back
with actual science.
On Sun, May 15, 2022 at 04:27:30AM -0500, Luke Small wrote:
> I have a feeling that making it threadsafe under any quantity of threads
> and still perform is likely not feasible, but if I could; or if making a
> nonthreadsafe variant was possible:
>
> Creating a mathematical proof that somehow is
I have a feeling that making it threadsafe under any quantity of threads
and still perform is likely not feasible, but if I could; or if making a
nonthreadsafe variant was possible:
Creating a mathematical proof that somehow is “simple and probably correct”
enough, would be an impossible task even
On Sun, May 15, 2022 at 01:12:28AM -0500, Luke Small wrote:
> This is version 1, which I was pretty sure was secure.
>
> I revamped it with a few features and implanted the binary search for 'bit'
>
> in most cases, which aren't intentionally worst-case, it's pretty darned
> fast!
>
> This is a
r bound then modulo will "remove a
> > lot of randomization". For example if you have a program which
> > generates Lotto numbers (1..49), then using _uniform() as it is will
> > generate many duplicates.
>
> Wut. The *WHOLE POINT* of arc4random_uniform() is th
rst place?
> >
> > The problem is that if have a low upper bound then modulo will "remove a
> > lot of randomization". For example if you have a program which
> > generates Lotto numbers (1..49), then using _uniform() as it is will
> > generate many dupli
move a
> lot of randomization". For example if you have a program which
> generates Lotto numbers (1..49), then using _uniform() as it is will
> generate many duplicates.
Wut. The *WHOLE POINT* of arc4random_uniform() is that it has uniform
distribution. Says right so in the
Stuart Henderson wrote in
:
|On 2022/05/14 06:56, Luke Small wrote:
|> If I use arc4random_uniform() repeatedly to create a random distribution \
|> of
|> say numbers less than 0x1000 or even something weird like 0x1300 will the
|> random distribution be better with arc4random_
int
main() {
int results[3] = { 0, 0, 0 };
for (int i = 0; i < 10; i++) {
results[arc4random_uniform_fast_simple(3)]++;
}
for (int i = 0; i < 3; i++)
printf("%d: %d\n", i, results[i]);
return 0;
}
% ./a.out
0: 24809
1: 50
On 2022/05/14 06:56, Luke Small wrote:
> If I use arc4random_uniform() repeatedly to create a random distribution of
> say numbers less than 0x1000 or even something weird like 0x1300 will the
> random distribution be better with arc4random_uniform() or with mine?
there's no p
Look at my code. I don’t even use a modulus operator. I perform hit and
miss with a random bitstream.
How can I have a bias of something I don’t do? I return a bitstream which
meets the parameters of being a value less than the upper bound. Much like
arc4random_buf().
If I use arc4random_uniform
On Sat, May 14, 2022 at 05:48:10AM -0500, Luke Small wrote:
> arc4random_uniform_fast2 that I made, streams in data from arc4random() and
> uses the datastream directly and uses it as a bit by bit right "sliding
> window" in the last loop. arc4random_uniform() uses a modulus
arc4random_uniform_fast2 that I made, streams in data from arc4random() and
uses the datastream directly and uses it as a bit by bit right "sliding
window" in the last loop. arc4random_uniform() uses a modulus which I is
simple to implement, but I wonder how cryptographically sound o
rrect.
-Otto
On Fri, May 13, 2022 at 09:43:26AM -0500, Luke Small wrote:
> I made a couple new versions of a new kind of arc4random_uniform-like
> function and some example functions which use them. Instead of having a
> sufficiently large random number greater than the mod
I made a couple new versions of a new kind of arc4random_uniform-like
function and some example functions which use them. Instead of having a
sufficiently large random number greater than the modulus, I pick a random
number using arc4random() from a bitfield where the length of the bitfield
is
Theo Buehler wrote:
> I've now committed most of your diff, thanks once again.
>
> o I asked for further review on the kernel parts
> o I'm going to skip hack for now
>
> Here's a patch for libc, based on the previous discussion.
> I think this is easier to read and understand. No binary
I've now committed most of your diff, thanks once again.
o I asked for further review on the kernel parts
o I'm going to skip hack for now
Here's a patch for libc, based on the previous discussion.
I think this is easier to read and understand. No binary change on
amd64.
ok?
Index: lib
Matthew Martin writes:
> On Mon, Dec 07, 2015 at 09:33:47AM +0100, Theo Buehler wrote:
>> I think some of these are ok, but I'm unsure about some of the others.
>> Here are some of my concerns:
>>
>> - since arc4random_uniform can potentially loop indefinite
> I'll look into hack tonight when I have more time.
Honestly, I would prefer to leave hack as it is right now since it will
take some work to repair it anyway. I would not want to add another
layer of (potential) complications.
> > > Index: lib/libc/stdlib/rand.c
> > > =
On Mon, Dec 07, 2015 at 09:33:47AM +0100, Theo Buehler wrote:
> I think some of these are ok, but I'm unsure about some of the others.
> Here are some of my concerns:
>
> - since arc4random_uniform can potentially loop indefinitely, it
> might interfere with predictable tim
On Mon, Dec 07, 2015 at 12:49:17AM -0600, Matthew Martin wrote:
>
> Theo's diff inspired me to look for other cases of modulo bias. The
> following diff converts most modulus operations on a random number to
> use arc4random_uniform or & as appropriate. I excluded
&g
Theo's diff inspired me to look for other cases of modulo bias. The
following diff converts most modulus operations on a random number to
use arc4random_uniform or & as appropriate. I excluded
lib/libsqlite3/src/resolve.c
regress/lib/libevent/test-time.c
usr.sbin/nsd/rrl.c
usr.sbin/n
> I agree that simply "min = -upper_bound % upper_bound" should be
> sufficient in all cases, since u_int32_t arithmetic is defined as
> modulo 2**32 by the C standard, at least as of C99 and I think C89
> too. (Even if we supported any 1s-complement architectures, the
> compiler would still need
ion has for ranges that are not a power of 2. It works
> correctly, but there are some considerations (transparency and chroot
> jail compatibility) that have led me to look at alternative
> implementations. This is where arc4random_uniform comes in. The way it
> avoids biased results
id the systematic bias a naive
implementation has for ranges that are not a power of 2. It works
correctly, but there are some considerations (transparency and chroot
jail compatibility) that have led me to look at alternative
implementations. This is where arc4random_uniform comes in. The way it
avoids biased
70 matches
Mail list logo
