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?

$\endgroup$
  • 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 '17 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 '17 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 '17 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 '17 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 '17 at 20:36
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...

$\endgroup$

Your Answer

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