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 “simple and probably correct”
> enough, would be an impossible task even for a PhD mathematician.
>
> 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 demanded tight tolerances over varying length runs?
>
> How was rc4 cipher proven bad for pseudorandom numbers? I’d be willing to
> bet it wasn’t from a mathematical proof; it was from bad data.
>
> I’m guessing that large upperbounds approaching 2**32 don’t feed very
> soundly in the current implementation using a modulus; although I suspect
> that there isn’t much of a call for such things, I’m pretty sure I saw a
> 3,000,000,000 upperbound in the src partition tonight.
You miss the point completely. The point is: how do you derive a
uniformly distributed random function for a smaller range, given a
uniformly distibuted random function over the range [0-2^32-1].
The current implementation does exactly that and has all the
information in the comments to verify the uniformity claim. You only
need to use basic mathematical properties of modulo arithmetic to
do the verification.
-Otto
>
> On Sun, May 15, 2022 at 3:15 AM Otto Moerbeek <o...@drijf.net> wrote:
>
> > 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 sample run of my program with your piece of code included:
> > >
> > >
> > > 1 99319 100239
> > > 2 100353 99584
> > > 3 100032 99879
> > > 4 99704 100229
> > > 5 99530 99796
> > > 6 99617 100355
> > > 7 100490 100319
> > > 8 99793 100114
> > > 9 100426 99744
> > > 10 100315 100558
> > > 11 99279 99766
> > > 12 99572 99750
> > > 13 99955 100017
> > > 14 100413 100005
> > > 15 100190 100052
> > > 16 101071 100195
> > > 17 100322 100224
> > > 18 99637 99540
> > > 19 100323 99251
> > > 20 99841 100177
> > > 21 99948 99504
> > > 22 100065 100031
> > > 23 100026 99827
> > > 24 99836 99818
> > > 25 100245 99822
> > > 26 100088 99678
> > > 27 99957 99993
> > > 28 100065 99961
> > > 29 100701 100679
> > > 30 99756 99587
> > > 31 100220 100076
> > > 32 100067 100005
> > > 33 99547 99984
> > > 34 100124 100031
> > > 35 99547 100661
> > > 36 99801 99963
> > > 37 100189 100230
> > > 38 99878 99579
> > > 39 99864 99442
> > > 40 99683 100004
> > > 41 99907 100094
> > > 42 100291 99817
> > > 43 99908 99984
> > > 44 100044 100606
> > > 45 100065 100120
> > > 46 99358 100141
> > > 47 100152 100442
> > > 48 100000 100279
> > > 49 100486 99848
> >
> > Sadly a sample run cannot be used to proof your implementation is
> > correct. It can only be used to show it is not correct, like Philip
> > did. To show your implementation produces uniform results in all
> > cases, you need to provide a solid argumentation that is easy to
> > follow. So far you failed to do that and I do not see it coming, given
> > the complexituy of your implementation. The current implementation
> > has a straightforward argumentation as it uses relatively simple
> > mathematical properties of modulo arithmetic.
> >
> > It is also clear your code (as it uses statics) is not thread safe.
> >
> > So to answer you original question clearly: no, we will not accept this.
> >
> > -Otto
> >
> --
> -Luke
