1
$\begingroup$

For example, one of the possible rand() implementations:

int rand_r (unsigned int *seed)
{
    unsigned int next = *seed;
    int result;
    next *= 1103515245;
    next += 12345;
    result = (unsigned int) (next / 65536) % 2048;
    next *= 1103515245;
    next += 12345;
    result <<= 10;
    result ^= (unsigned int) (next / 65536) % 1024;
    next *= 1103515245;
    next += 12345;
    result <<= 10;
    result ^= (unsigned int) (next / 65536) % 1024;
    *seed = next;
    return result;
  }

How to proof that it is not a pseudo-random generator?

$\endgroup$
  • $\begingroup$ @fgrieu the question seems to be about it not being PRG, which is a crypto definition that it certainly does not fulfill. $\endgroup$ – otus Mar 19 '18 at 8:07
  • $\begingroup$ @otus there's CSPRNGs and there's other PRNGs that are usually weak (which the above is), there's RNGs which include the two above and also TRNG hardware, and there are NGs which include the above and also possibly a box that constantly outputs a 5. Using PRG in a conversation seems confusing to me (and now I pretend no one calls them DRBG) $\endgroup$ – daniel Mar 19 '18 at 12:05
8
$\begingroup$

This is a Pseudo Random Number Generator, but not a Cryptographically Secure PRNG, which requires that the output is undistinguishable from random for one not knowing the initial *seed.

One problem is, the effective state is very small: 27 bits at most (or less, limited by the size of int), because only the 27 low-order bits of the input *seed ever have a chance to influence either result or the low-order 27 bits of the output *seed. That alone limits the generator to 27-bit security, which is not enough (40-bit was already low security down in the 1980's). Also, this small effective state limits the period to $2^{27}$ (about 134 million), which is not enough even for simulation purposes.

Worse, one 31 bit output result is (at least, most likely) enough to easily reconstruct the full state *seed on output and then trivially predict future output, a total disaster for a CSPRNG. One simple method for that is: enumerate the $2^{16}$ possible values of the low 16 bits of next in the line result = (unsigned int) (next / 65536) % 2048;, and deduce the other 11 meaningful bits of next as result>>20; then check that guess of next against the 20 lower bits of result by replicating what the code does. We are down to 16-bit security, and that could be brought further down.

Walking back and computing previous output is trivial, too. The low 27 bits of *seed are transformed by three iterations of the linear $x\mapsto a\;x+b\bmod2^{27}$ with $a=1103515245$ and $b=12345$, giving $x\mapsto y=c\;x+d\bmod2^{27}$ with $c=a^3\bmod2^{27}=8240309$ and $d=117712863$ determined from $x=0$. And that is inverted as $x=e\;y+f$ with $e=c^{-1}\bmod2^{27}=70668701$ and $f=80477501$ determined from $x=0$.

$\endgroup$
-2
$\begingroup$
  1. The problems are these are "linear" to be total period.. use nonlinear instead.
  2. A total period rng needs variable size 1, reversible rng needs variable size 2, nonreversible needs size 3 but must scramble all at once or be internally reversible.
  3. Entropy must move freely in one direction per the integer noerrortrap unsigned multiply but also the other direction. So to give you a specific function I need you to tell me the C language instruction for the machine language instruction to do that
  4. The a = a × b : b = b xor a obviously has trouble with a or b being 0, so either have both odd or a = a xor b × c etc

  5. The output function to produce result range 0 to n-1 should not be separate but use that as a rng.

  6. If 32b × 32b → 64b then xor upper half with lower, if float × with integer × I'd prefer 2 64 bit floats to one 32 bit integer and one 64 bit float so just xor lower half to upper half

? Entropy must move freely in one direction per the integer noerrortrap unsigned multiply but also the other direction. So to give you a specific function I need you to tell me the C language instruction for the machine language instruction to do that???

$\endgroup$

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.