Simple nonlinear pseudorandom number generator

Just don't mistake passing the tests from actually being there.

In other words, don't tailor yourself to pass the tests. For example, very late in the game I found I'd always needed to round towards zero in order to get consistent results. That did worse in the tests, but it was the right thing to do. __outer

For S-function, I tried to get maximum nonlinearity wrt XOR and ADD operations (not implying best way to do that). As for statistics, it is interesting to check every Nth output word, where N is the period of the "priming" state machine. With small state such as 2 x 32 hash and 1 x 32 for priming, it is easy to find short loops with period about 2^37 or so. That is regardless of particular S-function. Need larger priming and larger hash.

VLV

ADD + XOR + ROL/ROR makes for decent non-linearity, but using constants for the ADD and the XOR is not a good idea I think. And the initial multiply by a constant in particular had patterns similar to the carries of the add that followed it, I think. Not that this stuff has anything resembling a solid theory behind it, that I know of.

I don't see any possible advantage to checking every Nth output word from your N-word LFIB. You've already walking the entire LFIB just to produce a single output, so I don't think there would be anything tied to an N-output cycle. There is, in theory, a rather limited diffusion rate across the cyclic buffer, but since your output is a function of the entire buffer not just a part of it that is not a short term issue, and since two calls is sufficient for bidirectional diffusion it's not really a long term issue either. One of the tests in the PractRand battery was concentrating for the kinds of issues that I think you're talking about (though it of course has no prior knowledge of the size of cyclic buffer that might be involved and has to check all possible scales), and it found nothing.

Actually... I not 100% sure what you mean by priming, state machine, or hash in this context. From context I'm guessing that your "priming state machine" is the top level LFIB (lagged fibonacci style PRNG based upon a cyclic buffer) structure considered independently from the unary function, and its "period" is the size of the cyclic buffer involved, and your hash is the unary function (plus maybe the "x" variable used, which I would call an accumulator), and your "S-function" is your unary function that by calling an "S-function" you are implying is similar in purpose to an S-box.

I have not tried reducing the size to 2 or 1 words since you said minimum was 3, though I did note that 2 looked doable at first glance. I have not tried widening the accumulator/hasher/whatever-you-call-it, though that sounds like a good idea.

Here is new revision (16 bit words, 128 bit state). The first 64 bits of state make a 64-bit LCG to guarantee minimum period, the other 64 bits are u16[4] stages of hash function (or LFIB if you like). S-function was optimized. Shifts like

Demonstrate

Minor technicalities skipped for clarity. The problem is not in unpacking 64bit operation into 16bit words.

LCGs with 2^n + 1 multiplier are almost as deterministic as simple counter. Properly chosen constant and adding words do improvement.

VLV

Below is 32 bit variant of the same structure; with 256 bits of state. Intended for PC x86 or ARM software implementation. Using stronger quadratic S-function and 5 hash stages. Added state initialization procedure. Period: 2^96 guaranteed. Speed: if my numbers are correct, about 6 cyc/byte without special optimization.

//---------------- // (c) Vladimir L. Vassilevsky // vlv{@}abvolt{.}com // Sep 8 2013 // static inline u32 vrnd_32_s(u32 x) { const u32 A=379309142u, B=3913891203u, C=3302675334u;

x += C; x ^= x >> 16;

//using Horner rule for CPUs without parallel multiplication // x = x*(A*x + B);

// using parallel operations on PC

u32 ax = A*x; u32 bx = B*x; x = x*ax + bx;

x ^= x >> 16;

return x; }

//========================================== // State initialization procedure // initialize state u32[8] // using (key concatenated with IV) of arbitrary length // u32[6] + u32[2] recommended // void vrnd_32_init(u32 *state, const u32 *key, const u32 key_size_dwords) { for(u32 ci = 0; ci < 8; ci++) state[ci] = ci;

u32 cntr = 0; u32 iter = 4;

if(key_size_dwords < 8) iter = (32/key_size_dwords) + ((32%key_size_dwords) ? 1 : 0);

// Feed key into the state

for(u32 ck = 0; ck < iter; ck++) { for(u32 ci = 0; ci < key_size_dwords; ci++) { u32 x = key[ci] + cntr; cntr++;

u32 tmp = state[0] ^ x; x += vrnd_32_s(state[0]);

for(u32 cj = 1; cj < 8; cj++) { state[cj-1] = state[cj] ^ x; x += vrnd_32_s(state[cj]); } state[7] = tmp; } } }

//=================================== // CPRNG (guaranteed period of 2^96) // Generate random u32 using 256-bit state u32[8] // u32 vrnd_32_256(u32 *state) { const u32 D = 2476441943u;

// LCG (period = 2^96)

u32 tmp32 = state[0]; u64 tmp64 = D + (u64)tmp32; state[0] = (u32)tmp64; tmp64 = (tmp64 >> 32) + tmp32; tmp64 += tmp32 = state[1]; state[1] = (u32)tmp64; tmp32 += (u32)(tmp64 >> 32); u32 x = state[2] += tmp32;

// Hash (5 stages)

tmp32 = state[3] ^ x; x += vrnd_32_s(state[3]);

for(u32 ci = 4; ci < 8; ci++) { state[ci - 1] = state[ci] ^ x; x += vrnd_32_s(state[ci]); }

state[7] = tmp32;

return x; } //======================

Vladimir Vassilevsky DSP and Mixed Signal Designs

I haven't tried running it yet, but by eye:

Your period is guaranteed to be a *minimum* of 2^96 - it is not guaranteed to be exactly 2^96. Average period is likely to be about

vrng_32_s() looks good. Slow on platforms that lack fast multiplication, and not as fast as a good equivalent could be even on platforms with fast multiplication, but it looks like it does a lot of mixing and is likely extremely non-linear. I *think* it's reversible, but I'd have to analyze it a bit to be sure - I don't deal with quadratic functions like that enough to tell by eye.

Overall quality is likely to be at levels comparable to a modern CSPRNG (say, ChaCha at 12 rounds). This is heavily dependent upon the quality of vrnd_32_s() though, so I'd have to examine that more closely to be confident on that.

I have not looked at the seeding/initialization function yet.

Security... let's go deeper on this subject. Assuming that vrnd_32_s() is good (which I think it is), there as still some issues here. Lets take a look at that LFIB loop: state[cj-1] = state[cj] ^ x; x += vrnd_32_s(state[cj]);

So... effectively the cyclic buffer gets rotated one position per pass, and there's an accumulator of some sort. Looking at it without the rotation: u32 new_x = x + vrnd_32_s(state[cj]); state[cj] = x ^ state[cj]; x = new_x;

Hm... suddenly the accumulator value looks like it contains information more closely related to the prior value in the cyclic buffer than I had been thinking. Is this a problem? Well... it means the per-call diffusion of information has a somewhat different structure than I thought, but not too different. But then look what happens when we reach the end. x contains similar information to the last element of the buffer (actually the second to last, once the buffers rotation is considered). Since vrnd_32_s is a stateless unary function of just 32 bits, an attacker can go from the output to at least a small but significant part of the contents of state[6] no matter how complex vrnd_32_s is. Not immediately fatal, but distinctly bad news. And that's assuming vrnd_32_s() is perfect - if it's merely good (as I suspect) then the information leaked about state[6] might be fatally large.

The obvious answer is to return something a little wider, and a little more obfuscated. Changing return x; to return vrnd_32_s(x + tmp) + tmp; ought to fix that. Assuming that vrnd_32_s is good, an attacker no longer can tell anything too important, I think. I'm not sure it's secure at that point, but I sure wouldn't want to have to try to crack it using reasonable amounts of resources.

Changing the accumulator path to carry more total information or just more distinct information might also help.