seed-sPRiNG picoCTF 2019 Solution

Description

1. Step 1Analyze the binary to find the seed

   Observation

   The challenge asks you to predict PRNG output. That means the program uses a seeded random number generator, and the seed has to be recoverable by examining the binary statically.

   Run the binary locally and examine it with Ghidra or strings. Find what value is used to seed the random number generator. The seed is likely based on time(NULL) (current Unix timestamp) or a fixed constant.

   bash

   strings seed-sPRiNG

   Copied!

   bash

   ghidra seed-sPRiNG &

   Copied!

   What didn't work first

   Tried: Running strings and seeing a number literal, then assuming it is the fixed seed value.

   A numeric string like '12345' in the binary might be a printf format, a version number, or unrelated data. Only decompiling in Ghidra and tracing the actual srand() argument confirms whether the seed is that constant or a runtime value like time(NULL). Guess wrong and every prediction fails.

   Tried: Using ltrace to watch the srand() call and recording the seed from a local run, then using that exact seed against the remote server.

   If the binary seeds with time(NULL), ltrace shows the seed from your local run, which reflects your own clock at that moment. The remote server seeds when you connect, a different timestamp. Note roughly when you connect and try a small range of timestamps centered on that moment.

   Learn more

   C's srand(seed) initializes the random number generator, and rand() produces deterministic pseudo-random numbers from that seed. If you know the seed, you can reproduce the exact sequence of outputs from any other machine.

   Common predictable seeds: time(NULL) returns the current Unix timestamp (seconds since 1970). If the server seeds with the current time, and you know (or can guess) the time within a few seconds, you can reproduce the sequence.

2. Step 2Reproduce the PRNG sequence

   Observation

   The binary seeds with time(NULL) and masks each rand() output with & 0xF. So a C program making the same srand()/rand() calls, tried against timestamps near the connection time, should reproduce the sequence.

   Once you know the seed formula (e.g., time-based), write a C program that seeds with the same value and produces the same sequence. Note the connection timestamp to estimate the server time. The binary masks each random value with & 0xF, so the actual number to guess is always in the range 0-15.

   c

   cat << 'EOF' > predict.c
   #include <stdio.h>
   #include <stdlib.h>
   #include <time.h>
   
   int main() {
       // Try seeds near the current time
       time_t t = time(NULL);
       for (int delta = -5; delta <= 5; delta++) {
           srand(t + delta);
           printf("Seed %ld: %d\n", t + delta, rand() & 0xF);
       }
       return 0;
   }
   EOF
   gcc predict.c -o predict && ./predict

   Copied!

   What didn't work first

   Tried: Reimplementing the PRNG in Python using random.seed(t) and random.randint() instead of writing a C clone.

   Python's random module uses a Mersenne Twister, which produces a completely different sequence from C's rand() even from the same seed. The server runs C's rand(), so only a C program with matching srand()/rand() calls reproduces its output. A Python prediction will never line up.

   Tried: Printing rand() directly without applying the & 0xF mask and submitting the full integer value.

   The binary masks each rand() output with a bitwise AND against 0xF, cutting it to the range 0-15. Submit the raw rand() value, typically a large integer, and the server always rejects it. The step detail notes the mask, and the Ghidra decompilation shows it in the guessing logic.

   Learn more

   The Linux C library rand() is a linear congruential generator (LCG): a simple mathematical formula that produces a sequence of numbers. LCGs are fast but not cryptographically secure - given the output sequence, the internal state can be recovered.

3. Step 3Submit the prediction and get the flag

   Observation

   predict.c outputs candidate values for the timestamps around the moment of connection. Submit each one until the server accepts a match and hands over the flag.

   Send the predicted value to the server. If correct, the server reveals the flag.

   Learn more

   Cryptographically secure pseudo-random number generators (CSPRNGs) like /dev/urandom, ChaCha20, or Fortuna use unpredictable entropy sources and are designed so that future outputs cannot be predicted from past ones. Always use CSPRNGs for security-sensitive applications, never time-seeded LCGs.

Flag

Find the PRNG seed (likely time-based), reproduce the rand() sequence in a C program, and submit the predicted value.