seed-sPRiNG picoCTF 2019 Solution

Description

1. Step 1

   Analyze the binary to find the seed

   Observation

   I noticed the challenge name references a 'spring' seed and asks us to predict PRNG output, which suggested the program uses a seeded random number generator whose seed value must be recoverable by examining the binary with static analysis tools.

   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 could be a printf format string, a version number, or unrelated data. Only decompiling in Ghidra and tracing the actual srand() call argument confirms whether the seed is that constant or a runtime value like time(NULL). Treating an unrelated number as the seed will cause every prediction to be wrong.

   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 will show the seed value from your local run, which corresponds to your local clock at that moment. The remote server seeds at the moment you connect, which is a different timestamp. The correct approach is to note the approximate time you connect to the server 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 2

   Reproduce the PRNG sequence

   Observation

   I noticed that the binary seeds with time(NULL) and masks each rand() output with & 0xF, which suggested writing a C program using the same srand()/rand() calls and trying timestamps near the connection time to produce a matching prediction.

   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 algorithm, which produces a completely different sequence from C's LCG-based rand() even when seeded with the same value. The server is running C's rand(), so only a C program using the same srand()/rand() calls will reproduce its output. The prediction will never match the server output when using Python's random.

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

   The binary masks each rand() output with bitwise AND 0xF, reducing it to the range 0-15. Submitting the raw rand() value - which is typically a large positive integer - will always be rejected by the server. The context in the step detail explicitly notes the mask, and Ghidra decompilation will show the masking operation 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 3

   Submit the prediction and get the flag

   Observation

   I noticed the predict.c program outputs a set of candidate values for timestamps near the connection moment, which suggested submitting each until one matches and the server reveals 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.