<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<br>
<br>
<div class="moz-cite-prefix">On 7/30/21 11:37 AM, Jacob Christian
Munch-Andersen wrote:<br>
</div>
<blockquote type="cite"
cite="mid:70eedea6-8a80-44dc-8f97-57068c3da5c1@www.fastmail.com">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<title></title>
<style type="text/css">p.MsoNormal,p.MsoNoSpacing{margin:0}</style>
<div>It is an intriguing design, but it produces an even output
257 out of 512 times. </div>
</blockquote>
<br>
Took me a while to figure out why it was doing that. It wasn't the
"obvious" reason I thought of first. And it took another while to
figure out what to do about it. Thanks for pointing it out.<br>
<br>
<blockquote type="cite">The variable value lookup looks kind of
side-channely, I'm not sure if it is exploitable, but the general
consensus in modern cryptography is that we avoid such things
completely, because it is devilishly hard to assert that there is
no way to exploit that. The variable lookup is on the other hand
the only thing that makes this not trivially linearly solvable,
but I'm not sure if that is enough.<br>
</blockquote>
<br>
I'm aware that state leakage sunk arc4. And this is using part of
its state directly as one of the addends to the output. I don't
think there's any way to use a single addend without access to
either the sum, or the other addend, to do anything evil. I'm not
sure what construction would entirely avoid it, as the output of any
PRNG contains information about the state of the PRNG.<br>
<br>
Considering it carefully.... The observer is looking at the sum of
two values from the generator state.<br>
The first is novel each time, but the second is (pseudo)randomly
selected from the state. If the second happens to be the value that
was novel on any recent previous time, it shouldn't be possible to
tell because the currently novel value masks it. So there shouldn't
be any cases where output N matches output N+C for small C - it's
not possible for the same two values to be picked twice. <br>
<br>
It is possible for the novel value to be picked as the second term
making the output double a single value from the state. But there
is nothing special about a value that happens to be even.<br>
<br>
State compromise extensions are limited because Fibonacci generators
don't run backward. When you are looking at an output you can't
tell what two values added together to make that value, and one of
them disappeared when the generator cycled. Because one of the
addends that formed the Novel value disappears when the generator
cycles, you have no way to reconstruct the previous state given the
current state.<br>
<br>
Given the current state, you can tell what the most recent outputs
of the generators have been; The first three, plus the recent output
of PRNG, will allow you to identify which elements have been added
together to make the output. But this state compromise extension is
limited to 16 outputs; beyond that, information disappears from the
state (unless you can undo addition given only the sum) faster than
outputs make it available.<br>
<br>
So, I'm inclined to say 'state compromise extension' is likely to be
very short. I'm aware that I'm not the smartest monkey on the
planet, and I could be wrong. But I'm inclined to say it's not
likely.<br>
<br>
Output prediction is also something I don't think is likely; A
classic LFG of course has its formula where the output is absolutely
correlated with two specific previous outputs. But while the output
of each generator is subject to that three-point correlation, the
PRNG output, by itself, doesn't give clues about what the outputs of
the individual generators are. <br>
<br>
<blockquote type="cite"
cite="mid:70eedea6-8a80-44dc-8f97-57068c3da5c1@www.fastmail.com">
<div>Using only addition has two major issues, you stick
everything in the same linear space, and the higher order bits
never get to influence the lower order bits.<br>
</div>
</blockquote>
<br>
Hmmm. I like the longer period of the additive generators. OTOH,
the difference is a factor of 2^word length. If the longest
generator retains that factor it doesn't matter if the others do as
well. So if I leave the longest one additive, making the others
multiplicative should have no effect on the period. <br>
<br>
<blockquote type="cite"
cite="mid:70eedea6-8a80-44dc-8f97-57068c3da5c1@www.fastmail.com">
<div>While I'm no fan of creeping it to the absolute minimum, 2 kB
of state for an rng might be a bit excessive.<br>
</div>
</blockquote>
<br>
If I recall correctly, 4kB is one cache line on modern hardware; if
it fits in cache at all, then making it smaller can't make it
faster. That said, it could go down to 1kB with int32s, or even to
1/2kB with int16s. <br>
<br>
<blockquote type="cite"
cite="mid:70eedea6-8a80-44dc-8f97-57068c3da5c1@www.fastmail.com">
<div>You seem to have defined the size of integers to depend on
the platform, you can make multiple different versions optimized
for different platforms, but you should generally let the user
choose which one to use so that they can get the same result
across different platforms.<br>
</div>
</blockquote>
<br>
Yes. That is absolutely true, and needs corrected. A PRNG has to
give repeatable sequences in order to be useful. When we don't want
repeatable sequences we want to be using urand() or getrandom().<br>
<br>
Thanks for looking at it!<br>
<br>
Bear<br>
<br>
<br>
<br>
Updated code:<br>
<br>
uint64_t A[256];<br>
uint32_t N;<br>
<br>
uint64_t pseudorandom(){<br>
N--;<br>
A[N%256] = A[(N+5)%256] * A[(N+17)%256]; // <-
shorter period<br>
A[(N+17)%256] = A[(N+41)%256] * A[(N+72)%256]; // <-
generators are now<br>
A[(N+72)%256] = A[(N+120)%256] * A[(N+161)%256]; // <-
multiplicative<br>
A[(N+161)%256] = A[(N+163)%256] + A[(N+254)%256]; // <-
corrected formula<br>
A[(N+255)%256] = ~A[N%256]; // <- fixes autocorrelation of
first generator.<br>
return(A[N%256]+A[(A[(N+17)%256]+A[(N+72)%256])%256]);<br>
}<br>
<br>
void init(char *initstr){<br>
int count; int idx; int len = strlen(initstr); int shift;<br>
for (count = 0; count < len || count < 256; count++)<br>
A[(count + initstr[count % len])%256] += count +
(initstr[count%len] << (1 + count % 16));<br>
// guarantee invariant: at least one odd number in each
generator state.<br>
N=0; A[5]|=1; A[50]|=1; A[150]|=1; A[250]|=1;<br>
for (count = 0; count < 1024; count++){<br>
idx = pseudorandom()%256;<br>
A[idx] += pseudorandom()<<16;<br>
}<br>
}<br>
<br>
<br>
<br>
</body>
</html>