Proposal for a non-periodic CPRNG (WARNING: CROSSPOST!)

S

Sebastian Garth

I'd like to present a new variation of the standard Shrinking LFSR Generator (SLG) that, with just a few slight modifications, achieves both non-periodicity and a significantly improved level security. An SLG is of course currently considered impervious to cryptoanalysis except for the case where the characteristic polynomial is known (ie: public). So the first modification proposed is to have the polynomial change somehow over time. In this casewe'll simply increment the polynomial's binary representation whenever theLFSR's internal state has completed a complete cycle (which will be of course some length on [2, (2^N)-1], where N is the degree of the polynomial). The next modification is to dynamically increase the size of the LFSR whenever an overflow of the polynomial's binary representation is imminent. As an arbitrary convention (and better suggestions are certainly welcome here),the internal state of the LFSR is set to the seed and the binary representation of the polynomial is set to seed + 1. That's basically it!

In summary, the new design should demonstrate the following properties:

1) Non-periodicity;
2) Security; Implied by the current consensus that the only weakness of theSLG is the "known polynomial predicament".
3) Memory efficiency; This is implied by the fact that we are merely incrementing the polynomial's binary representation, and that for any given N thenumber of characteristic polynomials with maximal period ((2^N)-1) is T(N)where T is Euler's totient function, so of course the result is a very slow rate of growth indeed. To illustrate the point, if we were to imagine running the generator non-stop for a trillion years on today's computers, the amount of working memory needed would be much less so than what would be required to store the information contained in this very sentence!
4) Low algorithmic complexity; This is of course somewhat of a subjective statement, but just as an example, a very lightly optimized proof-of-conceptprogram written by the author was capable of producing about 3 million output bits per second. A highly optimized version might have produced 2 or 3 times as much, I imagine.
5) Capable of producing "sufficient" randomness; Implied by what research has been done on SLG's as well as the empirical evidence (albeit meager) that has been gathered thus far by the author. Up to this point, the testing Ihave conducted essentially amounts to running the output of the generator through the ENT tool and several file compressors. In the latter case, compression levels consistently amounted to 2% or less for streams up to 3000 bytes and 0% for anything larger, suggesting a high degree of entropy. A fair representation of the type of results obtained from the ENT tool are as follows:

Entropy = 7.999800 bits per byte.

Optimum compression would reduce the size
of this 1000000 byte file by 0 percent.

Chi square distribution for 1000000 samples is 277.12, and randomly
would exceed this value 16.31 percent of the times.

Arithmetic mean value of data bytes is 127.4699 (127.5 = random).
Monte Carlo value for Pi is 3.146724587 (error 0.16 percent).
Serial correlation coefficient is 0.000509 (totally uncorrelated = 0.0).

6) Bit-width neutrality; There is no need for carefully chosen "magic constants" which depend so delicately on machine word size and other such factors, and the input seed can be any arbitrary value whatsoever, even one whosemagnitude is several thousand bits or what have you.
7) Simplicity; The algorithm is arguably trivial to understand, easy to implement, and overall analysis of the algorithm should invariably prove to bea relatively straight-forward task.

A proof-of-concept implementation of the algorithm written in the C programming language can be found here (http://tinyurl.com/moar-zip). I would sincerely appreciate any comments relating to the algorithm, the source code, or anything else that may be relevant to the discussion here.
 
N

Nils M Holm

I'd like to present a new variation of the standard Shrinking
LFSR Generator (SLG) that, with just a few slight modifications,
achieves both non-periodicity and a significantly improved level
security. [...]

Although I lack the mathematical expertise to comment on your idea,
I think it looks interesting. However, I found the code to be a bit
hard to follow due to its formatting, so I took the liberty to give
it a slight overhaul. I think a proof of concept (POC) should be short
and crisp and easy to understand. Unreadable code may alienate people
before they are trying to comprehend the actual idea.

I would even go as far as to use a global/static slg structure
exclusively in a proof of concept, because I would consider the
creation and deletion of dynamic PRNGs to be outside its scope.
But then I have already spent too much time doing your work...

Anyway, here's a my version of your code. Do whatever you want with it!

/*
* Proof-of-concept for a non-periodic "self-shrinking linear
* feedback shift register"-based PRNG. Note: This source
* file can be included directly into a project (ie: without
* the need for separate compilation), if desired.
*
* Copyright (c) 2012 Sebastian Garth
*
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the "Software"), to deal in the Software without
* restriction, including without limitation the rights to
* use, copy, modify, merge, publish, distribute, sublicense,
* and/or sell copies of the Software, and to permit persons
* to whom the Software is furnished to do so, subject to the
* following conditions:
*
* The above copyright notice and this permission notice shall
* appear in all documentation pertaining to any products that
* include any portion of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY
* KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
* WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
* PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS
* OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
* OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
* OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/

/*
* - Did some basic re-formatting; made it fit in 80 cols.
* - Removed ugly trailing underscores from names.
* - Shortened some rather_long_names.
* - Why memset() an array before free()ing it in a POC?
* Let the security paranoids dwell on it later.
* - Removed casts from assignments from type void*.
* - Changed "type* foo" to "type *foo".
* - Made default seed 0 instead of time(); it's reproducible.
* - Removed all functions that do not do anything in
* example_1(). They are only confusing, IMO.
*
* -- nmh, 2012
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

struct slg {
size_t m_size;
unsigned char *m_poly,
*m_state,
*m_saved,
m_mask,
m_parity[1 << CHAR_BIT];
};

static void *slg_realloc(void *buffer, size_t old_size, size_t new_size) {
void *result = calloc(new_size, 1);

memcpy(result, buffer, old_size < new_size ? old_size : new_size);
free(buffer);
return result;
}

static void slg_resize(struct slg *prng, size_t size) {
prng->m_poly = slg_realloc(prng->m_poly, prng->m_size, size);
prng->m_state = slg_realloc(prng->m_state, prng->m_size, size);
prng->m_saved = slg_realloc(prng->m_saved, prng->m_size, size);
prng->m_size = size;
}

/*
* Generate a mask for cases where the upper bits of the
* last byte in our LFSR state exceed those of the poly.
*/
static void slg_setup_mask(struct slg *prng) {
unsigned char temp = prng->m_poly[prng->m_size - 1];

prng->m_mask = 0;
while (temp) {
temp >>= 1;
prng->m_mask <<= 1;
prng->m_mask |= 1;
}
}

void slg_seed(struct slg* prng, void *value, size_t size) {
unsigned char backup = 1, *array;

/*
* For the algorithm to work properly, trailing zero bytes must
* be truncated.
*/
for (array = value; size; --size)
if (array[size - 1])
break;
/*
* Sanity check. Not only would a zero value put the LFSR in a
* locked-up state, it would force slg_bit() and others into an
* infinite loop as well...
*/
if (!size) {
slg_seed(prng, &backup, 1);
return;
}
slg_resize(prng, size);
memcpy(prng->m_poly, value, size);
memcpy(prng->m_state, value, size);
memcpy(prng->m_saved, value, size);
slg_setup_mask(prng);
}

struct slg *slg_create(void) {
struct slg *prng = calloc(sizeof(struct slg), 1);
unsigned char value,
temp;
size_t index;

/*
* Generate a lookup table to speed up the parity-determination
* aspect of LFSR operation.
*/
for (index = 0; index < sizeof(prng->m_parity); ++index) {
value = 0;
temp = (unsigned char)index;
while (temp) {
value ^= temp & 1;
temp >>= 1;
}
prng->m_parity[index] = value;
}
slg_seed(prng, 0, 0);
return prng;
}

void slg_destroy(struct slg **prng) {
struct slg *self = *prng;

if (!self)
return;
free(self->m_poly);
free(self->m_state);
free(self->m_saved);
free(self);
*prng = NULL;
}

static struct slg *slg_global(int destroy) {
static struct slg *result = NULL;

if (destroy)
slg_destroy(&result);
else if (result == NULL)
result = slg_create();
return result;
}

/*
* Basically just a simplified "big integer" increment.
*/
static void slg_increment_poly(struct slg *prng) {
size_t index;

for (index = 0; index < prng->m_size; ++index)
if (++prng->m_poly[index])
break;
if (index == prng->m_size) {
slg_resize(prng, index + 1);
prng->m_poly[index] = 1;
}
slg_setup_mask(prng);
}

static void slg_shift(struct slg *prng) {
unsigned char mask = 1 << (CHAR_BIT - 1);
unsigned char test,
lsb = 0,
feedback = 0;
size_t index;
int save = 0;

/*
* If the current state equals the previous state then the LFSR
* has prngerated a complete cycle, so we increment the poly.
*/
if (memcmp(prng->m_state, prng->m_saved, prng->m_size) == 0) {
save = 1;
slg_increment_poly(prng);
}
/*
* For efficiency sake, this loop calculates the feedback
* bit *and* shifts the current state simultaneously.
*/
for (index = 0; index < prng->m_size; ++index) {
feedback ^= prng->m_parity[prng->m_state[index] &
prng->m_poly[index]];
test = ((prng->m_state[index] & mask) != 0);
prng->m_state[index] <<= 1;
prng->m_state[index] |= lsb;
lsb = test;
}
prng->m_state[0] |= feedback;
prng->m_state[prng->m_size - 1] &= prng->m_mask;
if (save)
memcpy(prng->m_saved, prng->m_state, prng->m_size);
}

/*
* The self-shrinking prng. The LFSR is cycled twice and the lower
* two bits are inspected. If the binary sequence encountered is 01 or 10,
* we output a 0 or 1, respectively. Otherwise, the process is repeated.
*/
unsigned long slg_bit(struct slg *prng) {
enum { ineligible = 2 };
unsigned char mask = 3,
map[] = { ineligible, 0, 1, ineligible };
unsigned char value;

for (;;) {
slg_shift(prng);
slg_shift(prng);
value = map[prng->m_state[0] & mask];
if (value != ineligible)
break;
}
return value;
}

void slg_fill(struct slg *prng, void *buffer, size_t size) {
size_t count;
unsigned char value,
*next = (unsigned char*)buffer,
*end = next + size;

while (next != end) {
value = 0;
count = CHAR_BIT;
while (count--) {
value <<= 1;
value |= slg_bit(prng);
}
*next++ = value;
}
}

void example(size_t iterations, unsigned long seed) {
size_t index;
unsigned long value;
struct slg *prng = slg_create();

slg_seed(prng, &seed, sizeof(seed));
printf("producing %u bits:\n", iterations);
for (index = 0; index < iterations; ++index)
printf("%lu", slg_bit(prng));
printf("\n");
printf("producing %u unsigned integers:\n", iterations);
for (index = 0; index < iterations; ++index) {
slg_fill(prng, &value, sizeof(value));
printf("%lu\n", value);
}
slg_destroy(&prng);
}

int main(int argc, char *argv[]) {
unsigned long seed = 0;
size_t iterations = 10;

printf("SLG Example Usage\n");
printf("usage: %s [iterations] [seed]\n", argv[0]);
if (argc > 1)
iterations = strtoul(argv[1], 0, 0);
else
printf("note: using default iterations of %u\n", iterations);
if (argc > 2)
seed = strtoul(argv[2], 0, 0);
else
printf("note: using default seed of %lu\n", seed);
example(iterations, seed);
return 0;
}
 
S

Sebastian Garth

My initial description of the algorithm was admittedly quite vague, so I'm going to go over it again in a little more detail, in hopes that it may clear up any undue confusion.

But first some terminology. "CP" refers to a "characteristic polynomial over the finite field GF(2)". "RN" refers to a "representation of a CP as a binary number". So for example, the CP x^11 + x^9 + x^4 + 1 has an RN counterpart of 10100001000 (ie: 1288 in decimal). "LS" refers to the RN of the LFSR's internal state. "SC" refers to a copy of some previous state of the LS..

So to recap, the entire system basically consists of a CP, an LS, and an SC.. Now here's how the algorithm works. We start with the input seed of arbitrary length and copy it to both the LS and SC. Note that if the seed is zero (which is a forbidden state for our LFSR) then it simply gets incrementedbefore the copy step. We then set our CP to LS + 1. For each cycle of the LFSR we then do the following:
(1) Compare LS with SC. If they are equal, set the boolean flag "SAVE" to "true" and increment the RN of our CP. If the increment overflows, increase the bit-width of the LFSR by one machine word and adjust the LFSR to account for the carry.
(2) "Feed" the LS into CP per standard LFSR operation.
(3) IF "SAVE" is set to "true" copy LS to SC.

So SC serves to detect that our LFSR has produced a maximum length sequencefor that particular CP (remember, much like a counter, an LFSR's CP never produces the same number twice unless it is about to repeat the entire sequence).

Anyway, several of these cycles (at least two) will run during the output-bit-determination step (ie: the "self-shrinking generator").

In conclusion, these very simple modifications yield a mechanism that demonstrates some truly remarkable properties indeed. Namely, an inexhaustible supply of high-quality random bits delivered at reasonably efficient output rates.
 
T

Tim Rentsch

Sebastian Garth said:
I'd like to present a new variation of the standard Shrinking LFSR
Generator (SLG) that, with just a few slight modifications, achieves
both non-periodicity and a significantly improved level security. An
SLG is of course currently considered impervious to cryptoanalysis
except for the case where the characteristic polynomial is known (ie:
public). So the first modification proposed is to have the polynomial
change somehow over time. In this case we'll simply increment the
polynomial's binary representation whenever the LFSR's internal state
has completed a complete cycle (which will be of course some length on
[2, (2^N)-1], where N is the degree of the polynomial). The next
modification is to dynamically increase the size of the LFSR whenever
an overflow of the polynomial's binary representation is imminent. As
an arbitrary convention (and better suggestions are certainly welcome
here), the internal state of the LFSR is set to the seed and the
binary representation of the polynomial is set to seed + 1. That's
basically it! [snip]

Doesn't seem like a good use of resources. Instead of storing a
starting point and the current value, one could just use a
conventional LFSR that's one and a half times as big. In
practical terms, this will provide just as much useful coding as
a growable one, because a growable one isn't going to grow often
enough to reach this limit, and this approach uses only 75% as
much space. Probably faster too, because it doesn't have to
compare against a starting point to see when to bump up to
the next polynomial.

Also, just for humor value, in theoretical terms the speed of a
growable LFSR goes to zero as the coding sequence gets
arbitrarily long. TANSTAAFL.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top