This text file discusses the ecbs algorithm mainly using ecbs8() as the example, but it all applies the same to ecbs64(), just with everything 8 times bigger.
#----------------------------------------------------------------------------
# testecbs8.readme
#----------------------------------------------------------------------------
ecbs8 is a variable state size algorithm using only 8 bit unsigned chars
for the algortihm to reduce as much as possible to a minimm state size
in order to expose weaknesses and to study the effectiveness of the
various components.
ecbs8 is composed of LFSR elements, taps, counters, a shift counter,
and some structural constants, and in ecbs8, some semiconstants,
variables that normally do not change, but may change rarely.
The algorithm generally goes like this.
1 increment taps
2 increment 4 adders as one giant 256 bit unsigned integer
3 add adder values to the elements selected by four of the 8 taps.
These taps don't matter, and they can be plus minus XOR or
multiply, but I avoid multiply because its supposedly slow.
4 update lfsr[tap1] with formula using tap1, tap2, tap3, and tap4.
5 decrement shift, rolling from 0 to some tap element & 7. If it's
still 0, then set to 7. Value zero is not used.
6 rotate right lfsr[tap1] shift bits
7 use lfsr elements of two selected taps to select a tap to swap
8 swap selected tap value with its neighbor to the right, cycling
back to swap with tap1 when tap8 is selected. (There are 8 taps,
named tapa1 to tapa8)
9 update lfsr[tap5] with formula using tap5, tap6, tap7, and tap8
10 decrement shift, rolling from 0 to some tap element & 7. If it's
still 0, then set to 7. Value zero is not used.
11 rotate lfsr[tap5] shift bits
12 check reset value and call ecbs8setsize if match.
13 return(lfsra[tapa1] ^ lfsra[tapa5]);
So where a traditional LFSR does
increment taps
do formaula
return value of tap1
ecbs8 does
increment taps
increment adders
mix adders into LFSR
do formula for lfsra[tapa1]
rotate lfsr[tap1]
swap taps
do formula for lfsra[tapa5]
rotate lfsr[tap5]
check resize and possibly call ecbs8setsize
return value (lfsr[tap1] ^ lfsr[tap5])
ecbs8 has 8 taps and 9 - 127 lfsr elements. Each tap points to
an element of the LFSR. The tap values MUST be unique.
Each tap value is decremented and when it drops below 0, is reset
to the last LFSR element. Apart from being unique, and within the
range 0 to last element, there is no restrictions on tap values.
They do not need to be uniformly distributed, or irreducible primitive
polynomials modulo 2. The tap values do have an effect on period. They
can make shorter or longer underlying periods, but that's irrelevant
because it's overcome by tap swaps and counters. Also, because the
formulas use ADD, SUB, MULT and XOR, it's really a NLFSR but I just
use LFSR from force of habit. But it's nonlinear and chaotic and so
tap values don't matter. This is not a maximal length LFSR, but its
got enough bits that get used enough to make for very long overall
periods.
ecbs8 also has four 8 bit counters used together as a single monotonic
counter. The variable names are adder1, adder2, adder3, and adder4. I did
not name them "counter*" because I might use counter or counter* for
some other debugging tasks. adder1 is incremented on every call to
ecbs8. When adder1 rolls over from 255 to 0, then adder2 is incremented.
When adder2 rolls over, adder3 is incremented, and so on.
Regardless whether the adders are incremented or not, their values are
added to LFSR elements based on the newly incremented tap values.
This means they are easy seed targets along with LFSR elements, since
starting values don't matter.
Now we are ready for a standard LFSR update in which we XOR, ADD,
and MULTIPLY LFSR elements based on tap values and add them to the
primary tap LFSR element. This is the first formula line. There is
quite a bit to learn about the formula and its effects when combining
ADD, XOR and MULTIPLY. I don't use SUBTRACT because its effects are
identical to ADD. How you parenthesize the formulas doesn't make much
difference and can generate many different formulas consisting of
identical components.
In the traditional basic LFSR algorithm, the primary tap is updated all
in one long formula, and that value is returned by the function call,
or maybe XOR'd with something such as a counter, and returned.
In ecbs8, we have two of those formula lines, one for taps 1-4 and
a second one for taps 5-8. In between, those updates we do two things.
First the LFSR element of tapa1 is rotated based on a shift value which
is a 3 bit decrementing variable.
After that we also have another thing unique to ecbs8. We select one of
the taps, based on XOR of two LFSR elements, and swap its contents with
its neighbor tap to the right, cycling back to tap1 when tap8 is selected.
Additionally we also rotate a secondary tap, tap5, decrementing and
reusing the same shift variable to specify how many bits to rotate.
This second rotate uses the same shift variable but since we only use
the 7 possible rotate amounts, the rotate values alternate between
the tap1 and tap5 rotates so that each one gets all possible rotate
values, in order as shown below. These are swaping the values of the
taps which are indexes into the LFSR array.
rotate amount 7 6 5 4 3 2 1 7 6 5 4 3 2 1 7 6 5 4 3 2 1
which tap 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1
tap5> 6 4 2 7 5 3 1 6 4 2 7 5 3 1
tap1> 7 5 3 1 6 4 2 7 5 3 1 6 4 2
So they use the same rotate values in the same order, just offset by 3.
The shift variable is not randomized because that seems to cause
correlations, and we have too much memory access already anyway. The
benefit is not worth the computation needed.
UPDATE! I changed my mind and added random shift variable by using some
lfsr element AND with 7 and if still 0, then reset to 7. This should
produce a very long shift period.
So where a normal LFSR with no fancy stuff, just the absolute minimum,
looks like this
unsigned char lfsr8 (void) {
++tap1;
if (tap1 > length) {
tap1 = 0;
}
++tap2;
if (tap2 > length) {
tap2 = 0;
}
++tap3;
if (tap3 > length) {
tap3 = 0;
}
++tap4;
if (tap4 > length) {
tap4 = 0;
}
++tap5;
if (tap5 > length) {
tap5 = 0;
}
++tap6;
if (tap6 > length) {
tap6 = 0;
}
++tap7;
if (tap7 > length) {
tap7 = 0;
}
++tap8;
if (tap8 > length) {
tap8 = 0;
}
lfsr[tap1] ^= ( lfsr[tap2] ^ lfsr[tap3] ^ lfsr[tap4] ^ lfsr[tap5] ^
lfsr[tap6] ^ lfsr[tap7] ^ lfsr[tap8] );
return( lfsr[tap1] ^ lfsr[tap5]);
}
ecbs8 looks like this. Just scroll down and skim through it to get
the feel for what it does. I'll discuss some interesting aspects below.
/* function implementation */
unsigned char ecbs8 (void) {
unsigned char swap;
unsigned char tmp;
static char shift = 7;
--tapa1;
if (tapa1 > maxtap) {
tapa1 = maxtap;
}
--tapa2;
if (tapa2 > maxtap) {
tapa2 = maxtap;
}
--tapa3;
if (tapa3 > maxtap) {
tapa3 = maxtap;
}
--tapa4;
if (tapa4 > maxtap) {
tapa4 = maxtap;
}
--tapa5;
if (tapa5 > maxtap) {
tapa5 = maxtap;
}
--tapa6;
if (tapa6 > maxtap) {
tapa6 = maxtap;
}
--tapa7;
if (tapa7 > maxtap) {
tapa7 = maxtap;
}
--tapa8;
if (tapa8 > maxtap) {
tapa8 = maxtap;
}
++adder1;
if (adder1 == 0) {
++adder2;
if (adder2 == 0) {
++adder3;
if (adder3 == 0) {
++adder4;
}
}
}
lfsra[tapa2] += adder1;
lfsra[tapa3] += adder2;
lfsra[tapa6] += adder3;
lfsra[tapa7] += adder4;
lfsra[tapa1] += ((lfsra[tapa1] ^ (lfsra[tapa2] * (lfsra[tapa3]|1))) + lfsra[tapa4]);
--shift;
if (shift == 0) {
shift = (lfsra[6] & 7);
if (shift == 0) {
shift = 7;
}
}
lfsra[tapa1] = ((lfsra[tapa1] >> shift) | (lfsra[tapa1] << (8-shift)));
swap = (lfsra[tapa2] ^ lfsra[tapa3]) & 7;
switch (swap) {
case 0: tmp = tapa1;
tapa1 = tapa2;
tapa2 = tmp;
break;
case 1: tmp = tapa2;
tapa2 = tapa3;
tapa3 = tmp;
break;
case 2: tmp = tapa3;
tapa3 = tapa4;
tapa4 = tmp;
break;
case 3: tmp = tapa4;
tapa4 = tapa5;
tapa5 = tmp;
break;
case 4: tmp = tapa5;
tapa5 = tapa6;
tapa6 = tmp;
break;
case 5: tmp = tapa6;
tapa6 = tapa7;
tapa7 = tmp;
break;
case 6: tmp = tapa7;
tapa7 = tapa8;
tapa8 = tmp;
break;
case 7: tmp = tapa8;
tapa8 = tapa1;
tapa1 = tmp;
break;
default: break;
}
lfsra[tapa1] += ((lfsra[tapa5] ^ (lfsra[tapa6] * (lfsra[tapa7]|1))) + lfsra[tapa8]);
--shift;
if (shift == 0) {
shift = (lfsra[1] & 7);
if (shift == 0) {
shift = 7;
}
}
lfsra[tapa5] = ((lfsra[tapa5] >> shift) | (lfsra[tapa5] << (8-shift)));
/*
This whole thing is because of using 8bit unsigned chars to match
match values. In the 64bit version it's just a single line.
*/
switch (reset) {
case 1 :
if ( (lfsra[tapa1] ^ 255) == power) {
setsize = (lfsra[tapa8] + MINLEN + 1) & (MAXLEN-1);
setsize |= (MAXLEN/2);
ecbs8setsize(setsize);
}
break;
case 2 :
if ( ((lfsra[tapa1] ^ 255) == 0) &&
((lfsra[tapa2] & power) == power)) {
setsize = (lfsra[tapa8] + MINLEN + 1) & (MAXLEN-1);
setsize |= (MAXLEN/2);
ecbs8setsize(setsize);
}
break;
case 3 :
if ( ((lfsra[tapa1] ^ 255) == 0) && ((lfsra[tapa2] ^ 255) == 0) &&
((lfsra[tapa3] & power) == power) ) {
setsize = (lfsra[tapa8] + MINLEN + 1) & (MAXLEN-1);
setsize |= (MAXLEN/2);
ecbs8setsize(setsize);
}
break;
case 4 :
if ( ((lfsra[tapa1] & 255) == 0) && ((lfsra[tapa2] & 255) == 0) &&
((lfsra[tapa3] & 255) == 0) &&
((lfsra[tapa8] & power) == power) ) {
setsize = (lfsra[tapa8] + MINLEN + 1) & (MAXLEN-1);
setsize |= (MAXLEN/2);
ecbs8setsize(setsize);
}
break;
case 5 :
if ( ((lfsra[tapa1] & 255) == 0) && ((lfsra[tapa2] & 255) == 0) &&
((lfsra[tapa3] & 255) == 0) && ((lfsra[tapa4] & 255) == 0) &&
((lfsra[tapa5] & power) == power) ) {
setsize = (lfsra[tapa8] + MINLEN + 1) & (MAXLEN-1);
setsize |= (MAXLEN/2);
ecbs8setsize(setsize);
}
break;
case 6 :
if ( ((lfsra[tapa1] & 255) == 0) && ((lfsra[tapa2] & 255) == 0) &&
((lfsra[tapa3] & 255) == 0) && ((lfsra[tapa4] & 255) == 0) &&
((lfsra[tapa5] & 255) == 0) &&
((lfsra[tapa6] & power) == power) ) {
setsize = (lfsra[tapa8] + MINLEN + 1) & (MAXLEN-1);
setsize |= (MAXLEN/2);
ecbs8setsize(setsize);
}
break;
case 7 :
if ( ((lfsra[tapa1] & 255) == 0) && ((lfsra[tapa2] & 255) == 0) &&
((lfsra[tapa3] & 255) == 0) && ((lfsra[tapa4] & 255) == 0) &&
((lfsra[tapa5] & 255) == 0) && ((lfsra[tapa6] & 255) == 0) &&
((lfsra[tapa7] & power) == power) ) {
setsize = (lfsra[tapa8] + MINLEN + 1) & (MAXLEN-1);
setsize |= (MAXLEN/2);
ecbs8setsize(setsize);
}
break;
case 8 :
if ( ((lfsra[tapa1] & 255) == 0) && ((lfsra[tapa2] & 255) == 0) &&
((lfsra[tapa3] & 255) == 0) && ((lfsra[tapa4] & 255) == 0) &&
((lfsra[tapa5] & 255) == 0) && ((lfsra[tapa6] & 255) == 0) &&
((lfsra[tapa7] & 255) == 0) &&
((lfsra[tapa8] & power) == 0) ) {
setsize = ((adder1+adder2+adder3+adder4) + MINLEN + 1);
setsize |= (MAXLEN/2);
ecbs8setsize(setsize);
}
break;
default : break;
}
return(lfsra[tapa1] ^ lfsra[tapa5]);
} /* END ecbs8 */
Ignore the big switch (reset) junk at the end for now. I'll get to it later.
First of all, I use decrements for the taps and shift register because
it should be easier for the compiler to optimize that way.
So we go through and decrement all the taps, and the four counters, named
adder1 to adder4. Then the adders are added into selected taps LFSR
elements. The ADDs could be any combination of ADD, SUB, MULT, and XOR.
I just use ADD to keep it simple. One of each would be better. Note that I
don't update lfsra[tapa1] and lfsra[tapa5] because they already get
updated elsewhere.
lfsra[tapa2] += adder1;
lfsra[tapa3] += adder2;
lfsra[tapa6] += adder3;
lfsra[tapa7] += adder4;
Now if my LFSR was to enter a short cycle, then by mixing in the adders,
of which at least one changes on every cycle, then my LFSR will be in
a state that it could not have entered by the primary tapa1 and tapa5
updates using the formulas only. So if there is a short cycle, I am
virtually guranteed to enter a completely different cycle, usually
the next time around, or at least within a few calls. So as long as we
use the adders, short cycles cease to exist because we are constantly
flipping through them from the outside influence of the adders. This
also means you shouldn't muck with the adders too much, but the
ecbs8setsize function does update them. But it should not be used more
than 2^16, or really far less then that. Default resetpower is 24,
approximately once every 16 million calls. However in testing extremely
bad configurations, a lower resetpower can keep the same initializtion
passing bigger and bigger tests in practrand. For random full configurations
the resetpower can be effectively turned off by setting it higher than
the amount of numbers we can generate in a reasonable time.
Finally, we do the first of our two formulas.
lfsra[tapa1] += ((lfsra[tapa1] ^ (lfsra[tapa2] * (lfsra[tapa3]|1))) + lfsra[tapa4]);
This formula can get stuck in all zero's state, so we must use the adders
to prevent that. As long as we have at least one adder, the all zero state
is not a problem. Also notice that we have an XOR, and MULTIPLY and an ADD
of LFSR elements. The multiply is OR'd with 1 to make it always be odd.
This makes it non-bijective, It means that one state can be entered from
multiple previous states. This is normally considered a very bad thing. But
for security it's a good thing because it prevents past preditibility from
known state and preserves predetermined output of forward state. The bit
argument against non-bijective state transitions is that we are guranteed
not to utilize all possible states, because whatever state we enter, there
are three other possible states that would have entered the exact same state.
My counter argument is that if you have enough states, using a small sample
of them is still good enough. And if the number of states you do have is
larger than the seed data, it doesn't matter anyway. Your period is always
limited by the amount of seed data anyway.
The other argument for bijective and against non bijective algorithms is
that you have many short periods, and also typically including the infamous
repeating length 1 period. But that cannot happen in ecbs because of the
adders, so it's not an issue. We have jillions of smaller periods that we
take one number from each. So if we have of jillions of really tiny short
cycles, it doesn't matter because we only take one number from that
particular configuration and then switch to another by swapping taps and
adding the adders.
But now that we've done the formula, we next rotate the primary tap.
Decrement the shift variable and rotate that amount. This generally
doubles the normal period that it would have had. This helps scramble
the formula effects and we do two formuals to use up all 8 taps,
and rotating tapa5 after use in the second formula.
But first we gotta do a tap swap. We use the XOR of two LFSR elements
selected by least used taps and AND with 7 to select a tap, then swap
that tap with the next tap to its right, cycling back to tap1 when
tap8 is selected to swap. This is a bubble sort in reverse used to
scamble the taps order. The tap values are never changed so all taps
stay in their same relative positions, but the elements they point
to are changed between calls such that the formula elements selected
for the the operations in the formulas are NOT what they would have
been for those same hardcoded taps, because they swapped the LFSR
elements they point to. This is another way of breaking out of a
short cycle. We never use the same LFSR twice, just another version
of the same length LFSR but with the operations on the tap elements
all swoapped around. It's the exact same as having all possible
combinations of operations on the same LFSR elements in the code,
just doing it dynamically as we go.
So we've swapped taps, and ecbs8 does the second formula using
taps 5 - 8. It's the same formula, just different taps. Then we
decrement the shift variable and rotate tap5 which is another
tap position that gets updated. The tapa5 update happens AFTER
the second formula so its previous value was used in the formula.
Then we check the resize function and execute or not, and finally
we return the XOR of tapa1 and tapa5. That's why I had the rotate
for tapa5, so we would use a different value than used in the
formula line, for the return value. That tapa5 update might be
better used only for the return value and not update the LFSR element,
but I think it's obscure enough because of the XOR and we need the
diffusion. But with tapa1, and tapa5, and the adders, we can have
6 LFSR elements update on each cycle, and thats about 50 percent if
you have very small lfsr lengths. But using normal two or three digit
lengths, its very slow diffusion. It's not really that bad because of
the tap swaps, we constantly pick from randomly changing selection
of elements instead of stepping through them linearly.
I still haven't explained the ecbs8setsize function.
This function is called after seeding the LFSR and adders. The
setsize function sets the lfsrlength to the value given and then it
scrambles the taps to assign new values for them. It does that by
assigning each element of a temporary array, it's own index value
as the element value. That array of numbers, ordered 0 to lfsrlength,
is then scrambled by swapping the elements at random by calling the
current ecbs8() function to get pseudo random numbers. This is just
a naive swap, not Fischer-Yates, but it's good enough until I fix it.
After mixing up the temp array we select the first 8 values as our tap
positions. At this point, the function sets the lfsrlength and maxtap
global variables to the new values.
From now on the ecbs8 function is using the new length and new taps.
Then the ecbs8setsize function uses the temporary array to reset the
taps a second time, using the new taps and new lfsrlength. After
this reset, the length is not changed, but the taps are swapped a
second time from scratch. Finally the ecbs8setsize function uses ecbs8
calls to add a number to each adder, thus changing them all. The adders
update is why ecbs8setsize should not be called too often.
While the ecbs8setsize function is using ecbs8 to get pseudo random
numbers, it might turn out that ecbs8 calls ecbs8setsize becuase of
its natural occurance every 2^n calls or so. ecbs8setsize just
uses a busy flag and ignores those calls. Not efficient, but not bad
for normal use when it will only be called once in millions of cycles
at most. ecbs8setsize is only going to call ecbs8() for random number
a few thousand times at most so it won't hit the busy flag very often.
Finally, if ecbs8setsize is called, the (tapa1 XOR tapa5) return value
will be different from what was just calculated for return. That return
value could be stored in a temp variable and returned as it was
before the ecbs8setsize call, but I think just skipping that value is
fastest and best for the algorithms resistance to analysis. For security
and better unpredictibilty I leave it as it is now.
One thing about the 8 bit version, or even the 64 bit version is
that you can have more than 4 adders. The 8 bit version really needs
8 adders and since they rarely get updated, the extra processing is
insignificant to the overall algorithm speed.
So because of all the uncertainty in which values are used for what,
I think this ia a good example of what you are NOT supposed to do.
This is a randomly generated random number generator. Not a good idea
supposedly, but can you find all the flaws in it that mathematics is
certain exist?
If there is a short period can you find a way for it to exist for any
length of time without being negated by the adders, tap swaps, and
periodic size resets?
Also notice that with ecbs8, the entire algorithm is really a single
example of many variants. Virtually any hardcoded value can be changed
without affecting the quality of the PRNG. That is in stark contrast
to all others where almost any change of any constant will cause toial
failure immediately.
For example, you can change any of the taps used to select taps to swap.
You can use only one tap element or XOR many of them together. You can
hardcode the LFSR elements to update from the adders almost any way you
want. No matter how you change these constants, the algorithm will
function the same way, because the underlying hardcoded taps are
constantly changing anyway. This means that almost any hardcoded values
in the algorithm can be arbitraily changed and it is still be the exact
same underlying algorithm.
But what this also means is that anybody can have their own unqiue
version of this algorithm that is essentially the exact same algorithm
but structurally seeded such that it will never ever produce the same
numbers as any other version.
If you want cryptographically secure, then just add entropy to any
of the LFSR elements or one of the adders, or both alternating, or
damm near anything else you can think of. Just adding /dev/urandom
once in a while is good enough.
I think of things this way. For this algorithm with n bits of state,
you may get only about 2^(n/2) or some such lesser figure of usefull
states. If I try to calculate all the states of ecbs8, I can't really
decide what is state and what is not. Are the temporary swap variables
state. I know all the ones that store information are state, but
some of them don't store but use and modify state. Lets just call
the standard stuff the primary state. For ecbs8 that is
4 adders
9+ LFSR elements
8 taps
1 shift
1 resetpower
1 resetcheckvalue
In minimal size thats 4*8 + 9*8 + 8*8 + 1*3 + 1*7 + 24 = 202
The actual final period may be far less then 2^202-1. Far more likely
its closer to 2^64 because we only have 32 bits of adders and 72 bits of
LFSR elements, so those are going to be 2^32 * 2^72 = 2^104 possible
states. It will most likely hit them all given enough time, and
very uniformly randomly at that. Average period of length 9 ecbs8
is probably greater than 2^64 and less than 2^104. Now thats for ecbs8,
but the exact same thing exists in 16, 32 and 64 bit versions, and
those are many many orders of magnitude larger periods. For the 16 bit
version, period length is the least of your concerns. For the 64 bit
version, it's not a concern.
This is the scaled down version of ecbs. You can run the program with
CLI switches in various configurations and using dump files as special
key files. testecbs8 and testecbs64 have a -f CLI option that specifies
a key file to set state to any exact state you want. You can reproduce
any state you have by using the dumpstate function or flag, to create
a dump file that specifies the exact complete state of the PRNG.
By doing this you can easily test the same CLI switches with different
seed values without specifiying all that junk on the command line. The
file looks like this.
[me@mymachine ecbs8test]$ ./testecbs8 -t -z -dd
testecbs8.c Sat Aug 27 23:28:28 2022
MAXINP = 65536 ( Input buffer size)
MAXOUT = 65536 (Output buffer size)
MAXLEN - 1 = 31 (Maximum LFSR size)
MINLEN + 1 = 9 (Minimum LFSR size)
constantflag = 0 constant1 = 170 constant2 = 85
totalseedchars = 0 cripple = 0 tapswap = 0
adders = 0 0 0 0 resetpower = 0
lfsralen = 9 shift = 3
tapa1 = 0
tapa2 = 1
tapa3 = 2
tapa4 = 3
tapa5 = 4
tapa6 = 5
tapa7 = 6
tapa8 = 7
lfsra[0] = 0
lfsra[1] = 0
lfsra[2] = 0
lfsra[3] = 0
lfsra[4] = 0
lfsra[5] = 0
lfsra[6] = 0
lfsra[7] = 0
lfsra[8] = 0
lfsra[9] = 0
lfsra[10] = 0
lfsra[11] = 0
lfsra[12] = 0
lfsra[13] = 0
lfsra[14] = 0
lfsra[15] = 0
lfsra[16] = 0
lfsra[17] = 0
lfsra[18] = 0
lfsra[19] = 0
lfsra[20] = 0
lfsra[21] = 0
lfsra[22] = 0
lfsra[23] = 0
lfsra[24] = 0
lfsra[25] = 0
lfsra[26] = 0
lfsra[27] = 0
lfsra[28] = 0
lfsra[29] = 0
lfsra[30] = 0
[me@mymachine ecbs8test]$
That particular configuration fails practrand immediately. And adding 1 bits
to the lfsra values doesn't help. But, make it a larger size with setsize
allowed like this.
./testecbs8 -t -z -S15 -dd > out
./testecbs8 -f out | RNG_test stdin64
Then it passes practrand for quite a while. This is the new out file.
./testecbs8 -t -z -S15 -dd > out
constantflag = 0 constant1 = 170 constant2 = 85
totalseedchars = 0 cripple = 0 tapswap = 0
adders = 0 0 0 0 resetpower = 24
lfsralen = 15 shift = 5
tapa1 = 0
tapa2 = 1
tapa3 = 2
tapa4 = 3
tapa5 = 4
tapa6 = 5
tapa7 = 6
tapa8 = 7
This is the old out file that fails practrand immediately no matter how
many 1 bits you put in the lfsra elements. The difference is size of the
LFSR in the new that passes practrand is 15 and the old one is 9. Also,
the new one allows resizeing by calling ecbs8setsize once every 2^24
calls, wherease resetpower is set to 0 in the failed out file below.
./testecbs8 -t -z -dd > out
constantflag = 0 constant1 = 170 constant2 = 85
totalseedchars = 0 cripple = 0 tapswap = 0
adders = 0 0 0 0 resetpower = 0
lfsralen = 9 shift = 1
tapa1 = 0
tapa2 = 1
tapa3 = 2
tapa4 = 3
tapa5 = 4
tapa6 = 5
tapa7 = 6
tapa8 = 7
But, if I turn on ecbs8setsize by setting resetpower to 24 or some value
that will be used, then it starts to pass practrand even with all 0 lfsra
elements? On the other hand, if I disable ecbs8setsize in the new size
15 out file that passed practrand before, then the larger one still passed
practrand to 1 GB. Now these are just quick less than a few minutes tests,
but this is how I figure out whats important and whats not.
Now the smaller 8bit version, testecbs8 will always fail practrand with
enough stuff disabled. But it still passed to a surprising degree, even
with more than one component disabled or crippled. I have run many tests
of crippled versions to 32TB in practrand, but this one is the finalized
version with the randomized shift variable and this one has not been fully
tested yet. But from past experience, I am 99.99999 percent confident.
Note that testing also means a lot of coding and recompiling to find out
things you can't do with command line switches, like outputing intermediate
values instead of the normal ecbs8() return value.
Also, there are two Constant values to replace the formula lines with, but
you can't just change one to have lfsra[tapa1] use the constant and
lfsra[tapa5] uses the normal formula or vice versa. I would have to have
three ecbs8constant() functions for that, so if you set one constant,
then the other constant will use its default value.
The same thing applies to turning off rotates with -T CLI option. You can't
specify to turn off one or the other and have the other use the normal
shift update. It's all or nothing. But, I don't think I need that granularity
for testing. Everything would be turned on for any practical use, so I
just need enough stuff to tweak that I can see that the whole is indeed
greater than the sum of its parts. And I think is you try to calculate
the minimum, maximum, and average final output period, it's pretty involved,
but even if you lowball some hard to quantify things, then numbers add
up to very large numbers of possible states, even given the non-bijective
use of MULT (element | 1) which always makes the element value an odd
number. Because there are two multiplies, we always have four possible
preceding states that could have entered any given state. If you try to
check all four previous states, each of those has four previous states
the could have led to that particular state. Therefore you have 4^n
possible previous states that could have lead to the current state, where
n is the number previous states back you want to look at. This is what
prevents cryptographers from determining previous states even given the
entire current state. There no additional entropy required. Of course,
the algorithm is completly deterministic going forward, so if the
cryptographer gets the compete current state, then he has won the battle.
But if he can only get partial state, we might have a chance to keep him
from discovering the number sequence. I think he needs more than half
of the current state to have any chance of predicting future state. In
factg I think he really needs at least statesize-128 or so bits of the
full complete state. I also think the bigger the statesize, the harder
it would be to obtain statesize-128 bits simply from the output of
the PRNG. This is why I think it just might be suitable for cryptographic
use.
But apart from that, it also produces good numbers almost no matter what.
Thats an important cryptographic property that is underrated. Just being
mathematically proven and sound is not really good enough if you have to
avoid certain constants and weak keys and so forth. If it's robust, you
don't have to worry about those things. And ecbs is robust.
Ask yourself, can you take your 64 bit algorithm and scale it down to
8 bits and still pass practrand to 32 terabytes? Can you also disable
or cripple parts of your scaled down algorithm and still pass practrand
to 32 terabytes? Does your algorithm scale down and still have no weak keys?
I'm not saying you can remove everything or just anything, the algorithm
does have to have a definition, but in arriving at the definition, I used
the testing to figure out which parts are most critical and which parts
are just nice to have. Then all we need do is insist on using the full
finalized algorithm and base the critique on the final version used as
designed, especially the 64 bit version. And we can scale things down and
remove some things for speed and still have confidence in a PRNG that will
produce very long period uniformly distributed random numbers.
Links to professional PRNG sites and a lot of discussion about ecbs
Explanation and detailed description of the algorithms and why they are as they are
A cryptographic cipher program that leaves no trace of itself after use. How ecbscryptogen works.
View or Download testecbs64.c, testecbs8.c, ecbscrypto.c, ecbscryptogen.c and some minor utilities.
Last updated Sun Sep 11 11:43:29 PDT 2022