how to know the secret number from srand(time(0))

Question

I had a network security class in my university. And there is a challenge for finding a secret number. Here is the code

#include <stdlib.h>
#include <time.h>
#include <stdio.h>

void init() {
    setbuf(stdin, NULL);
    setbuf(stdout, NULL);
}

int main() {
    init();
    srand(time(0));
    int secret  = 0;
    puts("Your secret: ");
    scanf("%d", &secret);
    if(secret == rand()) {
        system("/bin/sh");
    } else {
        puts("failed");
    }
}

I actually could not understand my professor's explanation. Anyone can explain the meaning of this code, and how can i find the secret number?

Answer 1

Pseudo random number generators rely on a seed to generate their random numbers: if you use the same seed, you'll get the same sequence of "random" numbers.

See here:

Consider this code:

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    srand(0);

    printf("random number 1: %d\n", rand());
    printf("random number 2: %d\n", rand());
    printf("random number 3: %d\n", rand());
    printf("random number 4: %d\n", rand());

    return 0;
}

Running the program (a.out) multiple times always generates the same numbers:

marco@Marcos-MacBook-Pro-16 Desktop % ./a.out
random number 1: 520932930
random number 2: 28925691
random number 3: 822784415
random number 4: 890459872
marco@Marcos-MacBook-Pro-16 Desktop % ./a.out
random number 1: 520932930
random number 2: 28925691
random number 3: 822784415
random number 4: 890459872
marco@Marcos-MacBook-Pro-16 Desktop % ./a.out
random number 1: 520932930
random number 2: 28925691
random number 3: 822784415
random number 4: 890459872
marco@Marcos-MacBook-Pro-16 Desktop % ./a.out
random number 1: 520932930
random number 2: 28925691
random number 3: 822784415
random number 4: 890459872

Of course the exact numbers will differ on the exact implementation used to generate the numbers. So the sequence of numbers probably will be different on your system. Nevertheless, using the same seed will always result in the same sequence.

Real systems use a combination of "real" (based on physical randomness) random numbers + a pseudo random number generator simply because its way more efficient to generate random numbers that way.

These are usually cryptographically secure pseudorandom number generators because the numbers are used for cryptographic operations (cryptography heavily relies on randomness to work).

The basic idea is as long as the initial seed is "secret" (unknown) you can't work it back and determine the pre-defined sequence of numbers generated.

It is possible (and has been done) to work back the initial seed simply by looking at the numbers generated by a pseudorandom number generator.

Now on how to solve the exercise given by your professor:

The easiest way would be to "freeze" time to have a fixed seed value for the random numbers (as shown in my code example above).

Since there isn't an easy way to do that, you can print the current seed by running another program to just output the first random number generated (since that's the "secret"):

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void) {
    srand(time(0));

    printf("the secret number is %d\n", rand());

    return 0;
}

You can then use that number to "unlock" the program given by your professor.

However you have to do that within a second or less, since time() returns a new value every second.

The more reliable way would be to have your program input the "random" number as soon as you generated it.

Here's an example code of how you could do that:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

// where to put the "random" number on disk
const char *tmp_file = "/tmp/input";
// where the executable of your professor is
const char *executable = "/path/to/your/professors/executable";

void writeRandomNumberToDisk(const char *path, int number) {
    char buf[128];

    // convert int to string
    memset(buf, 0, sizeof(buf));
    snprintf(buf, sizeof(buf), "%d\n", number);

    FILE *fp = fopen(path, "w+");
    fwrite(buf, strlen(buf), 1, fp);
    fclose(fp);
}

int main(void) {
    srand(time(0));

    int secret = rand();

    printf("the secret number is %d\n", secret);

    writeRandomNumberToDisk(tmp_file, secret);

    char buf[512];

    memset(buf, 0, sizeof(buf));
    snprintf(buf, sizeof(buf), "/bin/sh -c 'cat %s | %s'", tmp_file, executable);

    printf("Now executing %s\n", buf);
    system(buf);

    return 0;
}

Essentially, it writes the first "random" number to disk, then invokes the shell that will feed the "random" number into the program.

You can also bypass the file system entirely by using something like:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

// where the executable of your professor is
const char *executable = "/path/to/your/professors/executable";

int main(void) {
    srand(time(0));

    int secret = rand();

    printf("the secret number is %d\n", secret);

    char buf[512];

    memset(buf, 0, sizeof(buf));
    snprintf(buf, sizeof(buf), "/bin/sh -c 'printf \"%d\\n\" | %s'", secret, executable);

    printf("Now executing %s\n", buf);
    system(buf);

    return 0;
}

Answer 2

Technically you shouldn't be able to find the "secret" number - that's the whole point of the exercise: the "secret number" is generated using a strong PRNG seeded with a more-or-less random set of bits coming from the system clock.

Theoretically, if you have complete knowledge about the system - i.e. you both know the specific PRNG implementation used and the exact value used to seed it (the result of the time() call) - you should be able to guess the number simply by seeding another instance of the same PRNG and getting the next random int from it.

In this specific case, as the attacker you have complete control of the execution of the code and you should be able to predict the value returned from time() with very good accuracy (it is only a second resolution), so if you can build a program on the same system, that takes the predicted time value, seeds it to the same srand() implementation and returns the first random int - you can guess the "secret number".

So maybe the point of the exercise is to show that PRNG security trivially depends on knowing to start when no one is looking - otherwise you aren't secure, and possibly to not use time() to seed srand() and instead rely on something actually robust, like /dev/urandom .