TL;DR

This challenge underlines an aspect of pseudo-random number generators, i.e. that we can use them lightly only when implementing some game without too many pretenses, and that any usage for cryptographic reasons MUST take into account a lot more.

The idea behind using a pseudo-random generator for cryptographic reasons - in particular, for encrypting stuff - is simple: if our sequence is sufficiently â€śrandomâ€ť, we can XOR it with our plaintext and obtain a ciphertext that is virtually indistinguishable from randomness.

In this case, the shared secret between the two parties would be the seed to get the pseudo-random sequence started. Otherwise, the ciphertext would not be recoverable!

When implementing a simple game with an element of randomness, itâ€™s very tempting to seed the generator with the current epoch. Assuming that a game will last more than one second, this provides a fair source of randomness for e.g. moving adversaries or rolling dice.

Doing the same for cryptographic reasons is, too, very tempting, but at the cost of disastrous results. Letâ€™s make some calculations (without taking into account leap seconds):

• there are 3600 second in one hour
• there are 24 hours in a day, i.e. 86400 seconds
• there are (about) 365 days in a year, i.e. about 31.5 million seconds.

If we think about it, itâ€™s not that much to try all the different epochs in the last year to find out the one that might apply to a naive usage of pseudo-random sequences!

The specific challenge requires us to invest a lot less time, i.e. surely below one hour, by picking a random epoch in a random time range and then requiring us to guess the right seed by just taking the first value emitted by the pseudo-random sequence. As you might have guessed so far, itâ€™s just a matter of trying out all of them.

``````#!/usr/bin/env perl
use v5.24;
use warnings;
use experimental 'signatures';
no warnings 'experimental::signatures';
use Time::HiRes ();

use CryptoPals 'mt19937_factory';

use constant WMIN => \$ENV{WAIT_MIN} // 40;
use constant WMAX => \$ENV{WAIT_MAX} // 1000;

say q{OK, let's begin...};

my (\$t, \$r) = random_int();

say "got \$r, let's see...";
my \$start = Time::HiRes::time();
my \$guessed = find_seed(\$r);
say sprintf 'took %.2f s', Time::HiRes::time() - \$start;

die "no guess worked!\n" unless defined \$guessed;
die "sorry, wrong guess <\$guessed> against <\$t>!\n" unless \$guessed == \$t;
say "seed was: \$guessed";

sub find_seed (\$reference) {
my \$start = int(time());
for (0 .. 100_000_000) {
my \$seed = \$start - \$_;
my \$first = mt19937_factory(\$seed)->();
return \$seed if \$first eq \$reference;
}
return;
}

sub random_int {
random_wait();
my \$r = mt19937_factory(my \$t = int(time()))->();
random_wait();
return (\$t, \$r);
}

sub random_wait { sleep WMIN + rand(WMAX + 1 - WMIN) }
``````

The `random_wait` function does the sleeping as requested; itâ€™s possible to override the `WMIN` and `WMAX` constant values by setting the respective environment variables `WAIT_MIN` and `WAIT_MAX`.

The `random_int` function takes one output from the MT19937 generator and gives it back, together with the seed. This is returned just to allow for comparison with the one weâ€™re going to search, in a real scenario we would not get it!

After we got our random number, itâ€™s time to call `find_seed`, which starts looking â€śin the pastâ€ť to find the right seed. Which it invariably finds, of course.

For cryptographic reasons, itâ€™s better to stick with what is considered up to date at the time of need (as we will see, itâ€™s possible to â€śeasilyâ€ť reconstruct a clone of the generator by doing enough queries to the generator itself) and itâ€™s also better to rely on a less predictable source of randomness, e.g. a hash calculated from a passphrase (although itâ€™s probably better to gather quality random data from the computer, if possible).

Stay safe and secure!

Comments? Octodon, , GitHub, Reddit, or drop me a line!