4
$\begingroup$

Consider this random generator function.

A simplified version is provided below (this is C++, mind that "seed" is a reference):

uint32_t Rand(uint64_t& seed)
{
    seed = 1683268614LL * (seed & 0xffffffff) + (seed >> 32);
    return seed & 0xffffffff;
}

For those unfamiliar with C++: & denotes bit-wise AND, LL as a suffix denotes signed long long (signed 64-bit usually), >> denotes plain bit-shift, the uint64_t& in the header denotes that the input is a reference to an unsigned 64-bit integer, that is, updates also apply outside the function.

This is almost a linear congruential generator (LCG), the only difference is that the increment is not a constant, but a part of the seed itself.

My question is on the security of this algorithm, since LCGs are very easy to break.

Does using a non constant increment improve or decrease security? How could this be cracked other than by bruteforceing it?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ What this algorithm does: It takes the seed, takes the lower 32-bit, multiplies them by some constant and then adds the upper 32-bit of the seed, writes the full value back and returns the lower 32-bit, all in $\mathbb Z_{2^{64}}$ $\endgroup$
    – SEJPM
    Jul 2, 2017 at 12:41
  • 1
    $\begingroup$ Also note that neither seed nor the other intermediate values exceed the representable range of signed 64-bit integers. $\endgroup$
    – SEJPM
    Jul 2, 2017 at 13:08
  • $\begingroup$ Have you performed a randomness test on it using a reputable tool? If it fails, it's not really usable for cryptography in the first place... $\endgroup$
    – Paul Uszak
    Jul 2, 2017 at 15:18
  • 1
    $\begingroup$ @Paul Uszak: Having failed to exhibit a short cycle by Floyd's cycle finding after $>2^{42}$ evaluations from 6 haphazard seeds, and given its structure, I'm ready to bet this generator passes many existing randomness tests. Yet, as shown by poncho, it is not really usable for cryptography. This an example illustrating the fact that randomness tests are not a reliable mean to detect that a RNG is unsuitable for cryptography. $\endgroup$
    – fgrieu ♦
    Jul 2, 2017 at 20:29
  • $\begingroup$ @fgrieu Just thought I'd ask to save you having to do a test run. Frankly, I didn't think that it would pass Diehard(er) but if you say it does... $\endgroup$
    – Paul Uszak
    Jul 2, 2017 at 20:36

1 Answer 1

Reset to default
6
$\begingroup$

The state can be trivially recovered from two consecutive output (and hence all further outputs can be predicted).

For the first output, the system updates the seed to $\text{seed}_1$, and then outputs the lower 32 bits of $\text{seed_1}$, which we'll call $\text{output}_1$

For the second output, the system first computes:

$\text{seed}_2$ = 1683268614LL * $\text{output}_1$ + ($\text{seed}_1$ >> 32)

Then, the system outputs $\text{output}_2$, the lower 32 bits of $\text{seed}_2$.

Hence, if the attacker computes:

$\text{output}_2$ - 1683268614LL * $\text{output}_1$ $\bmod{2^{32}}$

That gives him the upper 32 bits of $\text{seed}_1$. With the entire value of $\text{seed}_1$, the rest of the sequence can be predicted.

With a standard LCG, you can also reconstruct internal states, but not this easily...

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.