Is it possible to crack g++ rand()?

Question

So, I have this:

I know that some code was used to generate a random sequence, and it looked roughly like this:

#include <iostream>
#include <string>

int main() {
    const std::string alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    std::string temp = "1234567890";
    srand(MAGICNUMBER);
    for (int i = 0;; ++i) {
        for (int j = 0; j < 10; ++j) {
            temp[j] = alphabet[rand() % alphabet.size()];
        }
        std::cout << temp << std::endl;
    }
}

It was used to generate a sequence of 124660967 strings, the last of which was "2lwd9JjVnE", and then stopped. The compilator used was 64-bit g++ 4.8 for Linux. What I want is to find the 124660968th string – that is, the one that would have been printed next. The caveat, of course, is that I don't know the MAGICNUMBER. I'm pretty sure that it's possible to brute-force all possibilities, but it would take millennia, it seems. I've tried to snoop around in rand() source code, but I don't really understand it, much less exploit it. Is it possible to find that string in more or less reasonable time?

UPD Is it even possible to generate what is supposed to go after my string without finding out the seed?

Answer 1

The compiler itself is irrelevant; the rand() function is implemented in libc.

The glibc implementation uses a linear congruential generator (LCG) or a linear feedback shift register (LFSR) for its rand(). These can be quite easily cracked given some of the outputs (which it seems you have). The details can be found in the answer to another question already asked here, but the crux is that LCGs and LFSRs are not secure and some simple maths and probability can gain you the right answer pretty quickly.

You'll need to work out which version of glibc was used, but the compiler version should give you a rough idea of the patch state of the system, so you can infer it from that.

You can find more resources on Google, but here's a quick set of links to help:

• LCGs on Wikipedia
• LFSRs on Wikipedia
• Cracking PHP's rand() [PDF] - relevant because it uses the glibc function for rand(), and this is covered in the paper.
• Untwister - PRNG seed recovery tool with support for rand()
• Snowflake - Another PRNG seed recovery tool

Answer 2

Google says:

In order to generate random-like numbers, srand is usually initialized to some distinctive runtime value, like the value returned by function time (declared in header <ctime\>). This is distinctive enough for most trivial randomization needs.

If this technique is used and you know a more or less close estimate of the time (like, if you can narrow it down to a day), a brute force attack on the left input space will probably be feasible.

Other than that, if you follow google some more you find a series of blog entries that might lead you down the right track.