From: boucher@csl.sri.com (Peter K. Boucher)
Newsgroups: sci.crypt
Subject: Re: Yet Another Secure? RNG

In article , jktaber@netcom.com (John K. Taber) writes:

The best I could think of was to iterate the prng at least 17 times for every byte returned to guarantee massive changes to v. This is something like the 16 rounds of DES. It is a very simple change, and I hope effective.

This works, but it's overkill. You don't need to change every value in v. Simply change the 4 values that you just used to generate the output.

I think this is the best I can do to make this prng "secure". Does anybody see any weaknesses?

I'm not sure this is a ``weakness,'' but you're generating 17 ``random'' bytes and throwing away the first 16. You could output the sum of all 17, or find another way to use them to enhance the randomness of the output.

There were suggestions to lengthen the rotors. I disagree. Lengthening the rotors makes it that much harder to diffuse changes throughout the random number generator. It's not the period that is the problem. It's not the shortness of the rotors that is the problem. The problem is making the rng complexely dependent on a small change to itself.

If you change the 4 values that were just used to generate the output, instead of trying to change every value in v, then large rotor-sizes are not a hindrance.

for(i = 0; i < 17; i++)
{ /* ensure all v[i] are changed */
a = prng.rotor.R2[(i + *ndx) % 2] +
prng.rotor.R3[(i + *ndx) % 3] +
prng.rotor.R5[(i + *ndx) % 5] +
prng.rotor.R7[(i + *ndx) % 7];
v[(i + *ndx) % 17] = a + ROTATE(v[(i + *ndx) % 17]);
}


You've got 17*7 = 119 divisions (modulo operators) per byte of output. This will be REALLY SLOW... There's simply no reason to index the rotors or v this way, unless you mean this as pseudo-code.

Here's a version that addresses your concerns and is only a little slow (it's almost as fast as my version of M). I added 2 more rotors, but, still, only 4 of them go into the output. The other two are used to mangle the output, and to update the state.

In this case, making the rotors bigger has two costs: memory and initalization-time. However, making the rotors bigger has to benefits: run-time speed (less wrap-arounds for indexing) and period-length.

Also, I use unsigned longs instead of bytes. You get 4 times the output for the same amount of processor-time. Is it weaker this way?

/* These must be PRIMES !!! */
#define R0_SIZE 313
#define R1_SIZE 761
#define R2_SIZE 127
#define R3_SIZE 541
#define R4_SIZE 257
#define R5_SIZE 691

#define vSIZE (R0_SIZE+R1_SIZE+R2_SIZE+R3_SIZE+R4_SIZE+R5_SIZE)

static union
{
   unsigned long v[vSIZE];		/* vector of vSIZE random longs */
   struct
     {
       unsigned long R0[R0_SIZE],		/* ..redefined as rotors*/
		     R1[R1_SIZE],
		     R2[R2_SIZE],
		     R3[R3_SIZE],
		     R4[R4_SIZE],
		     R5[R5_SIZE];
     } rotor;
} prng; /* end union */

static unsigned long *rotor0, *rotor1, *rotor2, *rotor3, *rotor4, *rotor5;

#define SPINDLE_1(X,n) ( ((~(X))<<(n)) ^ (  (X) >>(32-(n))) )
#define SPINDLE_2(X,n) ( (  (X) >>(n)) ^ ((~(X))<<(32-(n))) )
#define SPINDLE_3(X,n) ( (  (X) <<(n)) ^ ((~(X))>>(32-(n))) )
#define SPINDLE_4(X,n) ( ((~(X))>>(n)) ^ (  (X) <<(32-(n))) )

void f2(qty, *dest)
   int		    qty;	/* quantity of random longs to return	*/
   unsigned long   *dest;	/* ->receiving buffer			*/
{
   register unsigned long a, b, c, d, e, f;

   while (qty--) {

        a = *rotor0, /* read out six values from v */
	b = *rotor1,
	c = *rotor2,
	d = *rotor3,
	e = *rotor4,
	f = *rotor5;

        *rotor0 += f; /* update six values in v */
	*rotor1 += a;
	*rotor2 += b;
	*rotor3 += c;
        *rotor4 += d;
        *rotor5 += e;

	/* index the rotors, without those darn divisions */
	if (++rotor0 >= &(prng.rotor.R0[R0_SIZE])) rotor0 = prng.rotor.R0;
	if (++rotor1 >= &(prng.rotor.R1[R1_SIZE])) rotor1 = prng.rotor.R1;
	if (++rotor2 >= &(prng.rotor.R2[R2_SIZE])) rotor2 = prng.rotor.R2;
	if (++rotor3 >= &(prng.rotor.R3[R3_SIZE])) rotor3 = prng.rotor.R3;
	if (++rotor4 >= &(prng.rotor.R4[R4_SIZE])) rotor4 = prng.rotor.R4;
	if (++rotor5 >= &(prng.rotor.R5[R5_SIZE])) rotor5 = prng.rotor.R5;

        /* use the values from rotors 4 and 5 to fold, spindle, and */
	/* mutilate the values from rotors 0 thru 3.                */
	*(dest++) = (   (SPINDLE_1(a,e&31) - SPINDLE_2(b,f>>27))
		      ^ (SPINDLE_3(c,f&31) + SPINDLE_4(d,e>>27)) );
    }
}