XOR of many prime sized cycles: secure?

Question

I thought of a PRNG which is dependent on a large amount of good salt. The method is to use the salt to fill many arrays whose lengths are prime numbers, and cycle through each array, and ouput the XOR of all pointed bit. This way, a very long period can be easily guaranteed, and this PRNG did well in dieharder tests.

But I wonder if an adversary can infer from a partial output the internal state or the next output. To clarify my question, let's assume the attacker knows the lengths of the arrays. How much consecutive output (relative to the state size) will make it feasible for the attacker to narrow down the possibilities of the following output?

Answer 1

@Mark is on the right track, but not quite right. You can consider the array elements and RNG output as a system of linear equations, but they're not linearly independent. In fact, you can never fully recover the array elements, because xoring the same value into all values in two of the arrays will give the same RNG output -- the xored value is included twice in each element of the RNG output, so it cancels itself.

This actually makes the attacker's job easier, because they don't have to infer the entire array to predict all future output, so they don't need as many equations (/outputs). It's possible to predict all output from just (sum of primes) - (number of primes) + 1 consecutive outputs.

Here's an example, using arrays of lengths 2, 3, and 5. Call the arrays A (length 2), B (length 3), and C (length 5), and the output R. Then we have:

R0 = A0 ⊕ B0 ⊕ C0
R1 = A1 ⊕ B1 ⊕ C1
R2 = A0 ⊕ B2 ⊕ C2
R3 = A1 ⊕ B0 ⊕ C3
R4 = A0 ⊕ B1 ⊕ C4
R5 = A1 ⊕ B2 ⊕ C0
R6 = A0 ⊕ B0 ⊕ C1
R7 = A1 ⊕ B1 ⊕ C2
R8 = A0 ⊕ B2 ⊕ C3
R9 = A1 ⊕ B0 ⊕ C4

Consider:

R0 ⊕ R3 ⊕ R5 = (A0 ⊕ B0 ⊕ C0) ⊕ (A1 ⊕ B0 ⊕ C3) ⊕ (A1 ⊕ B2 ⊕ C0)
= A0 ⊕ B2 ⊕ C3
= R8

So xoring the zeroth, third, and fifth outputs predicts the eighth. And xoring the first, fourth, and sixth would give the ninth, etc.

Net result: this is completely useless as a cryptographic RNG.

Answer 2

I can put an upper bound on the strength: an attacker who can observe a number of consecutive outputs equal to the sum of the lengths of the individual arrays can deduce the values of the arrays and all subsequent output.

Consider the simple case of three arrays, with lengths 2, 3, and 5: the first ten values (the a variables), and the hidden values that generate them (the x variables), are shown below. Each column is the three hidden values that are xored to produce the visible output.

x1 x2 x1 x2 x1 x2 x1 x2 x1 x2
x3 x4 x5 x3 x4 x5 x3 x4 x5 x3
x6 x7 x8 x9 x0 x6 x7 x8 x9 x0
-----------------------------
a0 a1 a2 a3 a4 a5 a6 a7 a8 a9

If you turn it sideways, this looks an awful lot like a system of ten equations in ten unknowns -- the sort of thing people learn to solve in introductory algebra. Although the cycle length is 30, only 10 consecutive values are needed to completely characterize the generator and predict the next value.

As the number of arrays grows, so does the disparity between cycle length and ease of breaking it: ten arrays of length 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 gives a cycle length of 6,469,693,230, but only requires 129 values to break.

It may be possible for an attacker who already knows the contents of the arrays to break security with fewer values, but I'm not sure how it would be done.

Answer 3

NEVER ROLL YOUR OWN CRYPTO. Ok now that is out of the way.

Hello,

You already answered your question when you asked it, this is a PRNG. PRNG is not the same as CSPRNG (cryptographically secure pseudo-random number generator) which means a pseudo-random number generator for which it is believed to be impossible to predict its output without knowing the seeds. Even if your solution is as good as default PRNGs in built-in libraries, it does not matter. Pseudo-random implies some level of predictability that would let attackers predict future salt and nonce values (among other things, such as session cookies) and allow them to circumvent many of your defense mechanisms such as anti-CSRF tokens, session IDs in cookies, and salted password in your DB.

Therefore, nothing that is ever referred to as pseudo-random is secure. Furthermore, I can almost guarantee that any CSPRNG solution you, I or almost anybody comes up with has some level of predictability and a mathematician would laugh at us.

So no, it would not actually be secure. Interesting idea though and based on your comment you weren't planning on using it in real world applications anyways so I will end my rant short.

EDIT: Following AndrolGenhald comment on my poor terminology of "crypto-random" I updated the language to rely on the accurate term, CSPRNG. Apologies.