2

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?

  • Just to make sure I understand, you want to use this PRNG to generate secure values such as salt and nounces? – dFrancisco Feb 2 '18 at 15:20
  • I'm not using it. It's for fun. – h2kyeong Feb 2 '18 at 15:23
  • 1
    Might be better suited to crypto.stackexchange.com – AndrolGenhald Feb 2 '18 at 15:26
  • I'm wondering if this is "very easy to break," since people have discovered weaknesses in some extremely complex cipher, mine is pretty simple, and still to me it seems hard to break. – h2kyeong Feb 2 '18 at 15:31
3

@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.

  • Wow, thanks! This is almost like transparent LOL. But what if the lengths are at least partially unknown? The number of combinations of lengths is very large. – h2kyeong Feb 3 '18 at 7:46
  • 2
    I realized the attacker can find the identity even if he incorrectly selects lengths. Say the length is 2, 5 rather than 2, 3, 5, then it's like array B is all zero. So the difficulty would hinge on the longest salt, which is extremely weak indeed. – h2kyeong Feb 3 '18 at 8:13
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.

1

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.

  • Do you consider this crypto-random? XOR of 10,240 bits of raw output of laptop microphone to output one bit. Plotted as black-white pictures, 1000:1 ratio already seemd uniform to my eyes. – h2kyeong Feb 2 '18 at 15:44
  • I am not a cryptography expert by any means but I would argue using raw microphone data could be influenced by a non-random source. For example, if a song is playing, it is predictable what is coming next. – dFrancisco Feb 2 '18 at 15:48
  • 1
    I tried recording silence at maximum sensitivity to collect circuit noise. I guess a loud input may reduce the noisiness / randomness. – h2kyeong Feb 2 '18 at 15:50
  • 1
    This terminology is incorrect, what you call "crypto-random" comes from a CSPRNG (cryptographically secure pseudo-random number generator). It is still pseudo-random, it's just (hopefully) next to impossible to reproduce without the seed(s). – AndrolGenhald Feb 2 '18 at 16:04
  • @AndrolGenhald I updated the terminology. Looks better? – dFrancisco Feb 2 '18 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.