Writeup: RITSEC 2019 - Random

Information

• category : crypto
• points : 290

Description

nc ctfchallenges.ritsec.club 8001

Writeup

Let’s connect to the server:

$ nc ctfchallenges.ritsec.club 8001
1507311247
2119156802
583170381
Are you starting to 'C' a pattern?
1853555127
1006771040
Can you guess the next number?
45 # My input
Your answer is not correct. Try again!

$ nc ctfchallenges.ritsec.club 8001
1979535747
1498222975
1046292948
Are you starting to 'C' a pattern?
1583583707
788342924
Can you guess the next number?
959
Your answer is not correct. Try again!

The first thing I thought was that the random numbers were related by some
operations modulo 67 because ord('C') = 67.

After at least 10 minutes of trying different tricks on the modulo operation
I gave up and I started reading about random generator and possible attacks
on them.

The most used random generator (not cryptographically secure) is
MT19937.

This is not secure because there are two possible and relatively easy
attack on it:

1. If the time is used as the seed of the algorithm, then we can try to
   bruteforce the seed. Ex: Try to set as the seed :
   time + 1, time + 2,..., time + n until the output of the algorithm is
   the same as the one in the server.
2. We can clone the state of the PRNG if we have 624 sequencial input,
   because the algorithm is linear and can be
   reversed

I tried both of the attack but they didn’t work. The second was less probable
of working because we didn’t have 624 sequencial output, so I couldn’t clone it.

After some time I got the idea to see how the rand() function is implemented
in C.

Are you starting to ‘C’ a pattern?

I found various links on stackoverflow/stackexchange and I have seen
the actual implementation on my machine. It wasn’t in the end very useful,
however I learnt something new.

The only thing we have to do at this point, is to try the attack 1.
So I connected to the server and I save the random numbers in an array (seq),
then I tried to bruteforce the seed starting from time(0).

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

int main(int argc, char **argv)
{
	unsigned int seq[] = {1919216342, 633727481, 605763938,\
		1690753349, 1661250374};
	for(int i = 0; i < 1000000; i++)
	{
		srand(time(0) - i);
		for(int j = 0; j < 5; j++)
		{	
			// Not the correct seed 
			if(rand() != seq[j])
			{
				break;
			}
			// The seed is correct and I output the next number
			if(j == 4)
			{
				printf("i : %d\n", i);
				printf("Next number %d\n", rand());
				exit(0);
			}
		}
	}
	exit(1);
	return 0;
}

$ gcc finder.c -o finder

$ ./finder
i : 264
Next number 2049118850

Oh yeah we found it. We could do this operation manually and win the challenge,
but manual solutions are bad, so we can script an automatic
solution to the problem.

Exploit

finder.c:

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

int main(int argc, char **argv)
{
	unsigned int seq[] = {atoi(argv[1]), atoi(argv[2]), atoi(argv[3]),\
		atoi(argv[4]), atoi(argv[5])};
	for(int i = 0; i < 1000000; i++)
	{
		srand(time(0) - i);
		for(int j = 0; j < 5; j++)
		{	
			if(rand() != seq[j])
			{
				break;
			}
			if(j == 4)
			{
				printf("%d\n", rand());
				exit(0);
			}
		}
	}
	exit(1);
	return 0;
}

exploit.py:

#!/usr/bin/env python3

from pwn import remote, log, process
from os import system

def main():
    n = [0 for i in range(0, 6)]
    conn = remote('ctfchallenges.ritsec.club', 8001)
    for i in range(0, 5):
        if i == 3:
            conn.recvuntil('?\n')
        n[i] = conn.recvline().decode().rstrip('\n')
    log.info("Received : " + str(n[:-1]))
    
    # Find the next number
    system('gcc finder.c -o finder')
    p = process(['./finder'] + [str(n[i]) for i in range(0, 5)])
    n[5] = p.recv()
    log.info("Next number : " + str(n[5]))
    conn.recvuntil('?\n')
    conn.sendline(n[5])
    log.info(conn.recv())

if __name__ == '__main__':
    main()

Flag

RITSEC{404_RANDOMNESS_NOT_FOUND}