Challenge
This problem was called seed-sPRiNG and involved guessing random numbers computed by the server each time the binary
is executed.
The challenge value was 350 points and it was solved by 570 teams only.
You can download the original linux executable here.
The Program
This time no source code was given. Because of this, we fired up IDA Pro to reverse engineer the binary file provided. This part was easy as Hex-Rays managed to give some pseudocode. I edited the important variables with meaningful names in the code below:
int __cdecl main(int argc, const char **argv, const char **envp)
{
int user_input; // [sp+0h] [bp-18h]@2
int computed_random_number; // [sp+4h] [bp-14h]@2
unsigned int seed; // [sp+8h] [bp-10h]@1
int i; // [sp+Ch] [bp-Ch]@1
int *v8; // [sp+14h] [bp-4h]@1
v8 = &argc;
puts((const char *)&unk_A40);
puts((const char *)&unk_A40);
puts(" ");
puts(" # mmmmm mmmmm \" mm m mmm ");
puts(" mmm mmm mmm mmm# mmm # \"# # \"# mmm #\"m # m\" \"");
puts(" # \" #\" # #\" # #\" \"# # \" #mmm#\" #mmmm\" # # #m # # mm");
puts(" \"\"\"m #\"\"\"\" #\"\"\"\" # # \"\"\"m # # \"m # # # # # #");
puts(" \"mmm\" \"#mm\" \"#mm\" \"#m## \"mmm\" # # \" mm#mm # ## \"mmm\"");
puts(" ");
puts((const char *)&unk_A40);
puts((const char *)&unk_A40);
puts("Welcome! The game is easy: you jump on a sPRiNG.");
puts("How high will you fly?");
puts((const char *)&unk_A40);
fflush(stdout);
seed = time(0);
srand(seed);
for ( i = 1; i <= 30; ++i )
{
printf("LEVEL (%d/30)\n", i);
puts((const char *)&unk_A40);
LOBYTE(computed_random_number) = rand() & 0xF;
computed_random_number = (unsigned __int8)computed_random_number;
printf("Guess the height: ");
fflush(stdout);
__isoc99_scanf("%d", &user_input);
fflush(stdin);
if ( computed_random_number != user_input )
{
puts("WRONG! Sorry, better luck next time!");
fflush(stdout);
exit(-1);
}
}
puts("Congratulation! You've won! Here is your flag:\n");
get_flag();
fflush(stdout);
return 0;
}The program iterates 30 times asking to the user for an ANDed rand() number in each iteration.
Given that the number is ANDed with 0xF, the probability for getting the right number on one attempt is 1/16. During each one of these 30 iterations, the program requests you to guess a new random number and you cannot fail once. In a way, you must be very lucky to guess the right number 30 times in a row, and if you can manage to do
that you should drop everything you are doing inmediatly and run very fast to your nearest Lotto agency.
If you fail to guess the number, then the program exits. Otherwise it continues execution and calls get_flag() which
prints the flag.
The Problem About glibc rand()
The glibc implementation of rand() gives a deterministic list of random numbers depending on the initial
state of the Pseudo Random Number Generator or PRNG which can be configured by passing a integer value to the seed() function.
In this program, the seed value is defined like this:
seed = time(0);
time() when NULL is passed as a parameter, returns the number of seconds since the Epoch. For this, the
seed parameter is an integer which is a timestamp corresponding to the time when the program was executed.
In order to get the list of integers generated by rand() we must sync up our seed with the seed
of the remote server.
Here is a C implementation that returns glibc random numbers with the current timestamp plus a parameter
that allows to adjust it secondswise:
/* get_next_random.c */
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<unistd.h>
void press_enter(void) {
char c;
while ((c = getchar()) != '\n' && c != EOF) {};
}
int main(int argc, char ** argv) {
time_t t = time(NULL);
int i;
int ch;
int secs = atoi(argv[1]);
srand(t + secs);
while(1) {
printf("%d\n", rand());
press_enter();
}
return 0;
}After compiling this program, we have access to the glibc PRNG values for a given timestamp,
and we can use this program to be called by the following python script:
# solver.py
from pwn import *
import subprocess
import sys
print "Adjusting %s seconds" % sys.argv[1]
r = process(['./get_next_random', sys.argv[1]])
#p = process('./seed_spring')
p = remote("2019shell1.picoctf.com", 47241)
first_itr = True
def get_next_rand():
global first_itr
"""if first_itr == True:
rand = r.recvuntil("\n")
first_itr = False"""
rand = int(r.recvuntil("\n"))
print "[+] rand res: %s" % (rand)
r.sendline("\n") # "keypress"
return str(rand & 0x0f)
def answer_next_rand():
print p.recvuntil('Guess the height: ')
gnr = get_next_rand()
print "[+] recv rand: %s" % (gnr)
p.sendline(gnr)
#p.interactive()
for n in range(30):
print "iter %d" % (n)
answer_next_rand()
p.interactive()For obtaining the difference in seconds between your host machine and the server, you need to compare the server time with your own time and calculate the difference. After obtaining this, you pass the difference as a parameter to solver.py:
$ python2 solver.py -67
Adjusting -67 seconds
[+] Starting local process './get_next_random': pid 10364
[+] Opening connection to 2019shell1.picoctf.com on port 47241: Done
iter 0
# mmmmm mmmmm " mm m mmm
mmm mmm mmm mmm# mmm # "# # "# mmm #"m # m" "
# " #" # #" # #" "# # " #mmm#" #mmmm" # # #m # # mm
"""m #"""" #"""" # # """m # # "m # # # # # #
"mmm" "#mm" "#mm" "#m## "mmm" # # " mm#mm # ## "mmm"
Welcome! The game is easy: you jump on a sPRiNG.
How high will you fly?
LEVEL (1/30)
Guess the height:
[+] rand res: 1364322132
[+] recv rand: 4
iter 1
LEVEL (2/30)
Guess the height:
[+] rand res: 434722439
[+] recv rand: 7
iter 2
LEVEL (3/30)
Guess the height:
[+] rand res: 1377180127
[+] recv rand: 15
iter 3
LEVEL (4/30)
Guess the height:
[+] rand res: 1808225694
[+] recv rand: 14
iter 4
LEVEL (5/30)
Guess the height:
[+] rand res: 62382340
[+] recv rand: 4
iter 5
LEVEL (6/30)
Guess the height:
[+] rand res: 1963374791
[+] recv rand: 7
iter 6
LEVEL (7/30)
Guess the height:
[+] rand res: 816707196
[+] recv rand: 12
iter 7
LEVEL (8/30)
Guess the height:
[+] rand res: 334874815
[+] recv rand: 15
iter 8
LEVEL (9/30)
Guess the height:
[+] rand res: 655806567
[+] recv rand: 7
iter 9
LEVEL (10/30)
Guess the height:
[+] rand res: 1941163045
[+] recv rand: 5
iter 10
LEVEL (11/30)
Guess the height:
[+] rand res: 775403268
[+] recv rand: 4
iter 11
LEVEL (12/30)
Guess the height:
[+] rand res: 563953700
[+] recv rand: 4
iter 12
LEVEL (13/30)
Guess the height:
[+] rand res: 1952106428
[+] recv rand: 12
iter 13
LEVEL (14/30)
Guess the height:
[+] rand res: 196293750
[+] recv rand: 6
iter 14
LEVEL (15/30)
Guess the height:
[+] rand res: 483817835
[+] recv rand: 11
iter 15
LEVEL (16/30)
Guess the height:
[+] rand res: 1247250654
[+] recv rand: 14
iter 16
LEVEL (17/30)
Guess the height:
[+] rand res: 1628034898
[+] recv rand: 2
iter 17
LEVEL (18/30)
Guess the height:
[+] rand res: 1460030885
[+] recv rand: 5
iter 18
LEVEL (19/30)
Guess the height:
[+] rand res: 770895491
[+] recv rand: 3
iter 19
LEVEL (20/30)
Guess the height:
[+] rand res: 170966322
[+] recv rand: 2
iter 20
LEVEL (21/30)
Guess the height:
[+] rand res: 886536535
[+] recv rand: 7
iter 21
LEVEL (22/30)
Guess the height:
[+] rand res: 1486928445
[+] recv rand: 13
iter 22
LEVEL (23/30)
Guess the height:
[+] rand res: 1407125890
[+] recv rand: 2
iter 23
LEVEL (24/30)
Guess the height:
[+] rand res: 577782631
[+] recv rand: 7
iter 24
LEVEL (25/30)
Guess the height:
[+] rand res: 1280166156
[+] recv rand: 12
iter 25
LEVEL (26/30)
Guess the height:
[+] rand res: 1013599537
[+] recv rand: 1
iter 26
LEVEL (27/30)
Guess the height:
[+] rand res: 1767382994
[+] recv rand: 2
iter 27
LEVEL (28/30)
Guess the height:
[+] rand res: 319363720
[+] recv rand: 8
iter 28
LEVEL (29/30)
Guess the height:
[+] rand res: 1139885298
[+] recv rand: 2
iter 29
LEVEL (30/30)
Guess the height:
[+] rand res: 1321823519
[+] recv rand: 15
[*] Switching to interactive mode
picoCTF{pseudo_random_number_generator_not_so_random_1e980471db65a9f446af481d75490127}
Congratulation! You've won! Here is your flag:And we got our flag: picoCTF{pseudo_random_number_generator_not_so_random_1e980471db65a9f446af481d75490127}