The challenge came with the description:

These damn hackers have hit our NTP server with something called crypto clock... 
Our sysadmin found these suspicious packets just before our systems went down. 
Can you get back in??? nc 1230

and a downloadable pcap. The network traffic in the pcap contained a base64 string that contained the following Python program:

#!/usr/bin/env python
import sys
import random
import arrow


flag = "THEFLAG"
keys = {
    "e": 3

#now to get some randomness in here!
with open('/dev/urandom', 'rb') as f:
    rand =

rand_int = int(rand.encode('hex'),16)

#now lets use something easier.

offset = random.randint(big_1,big_2)

while True:
    sys.stdout.write( '''Welcome to the ntp server
What would you like to do?
    1) get current time
    2) enter admin area
    3) exit
    response = raw_input('')
    if response == '1':
        time = arrow.utcnow().timestamp + offset
        enc_time = pow(time,keys['e'],keys['n'])
        sys.stdout.write('HAHAHAHAHAHA, this NTP server has been taken over by hackers!!!\n')
        sys.stdout.write('here is the time encrypted with sweet RSA!\n')
    elif response == '2':
        # lets get even more random!
        time = arrow.utcnow().timestamp + offset
        guessing_int = random.randint(0,999999999999)
        sys.stdout.write('''ACCESS IS ONLY FOR TRUE HACKERS!
to prove you are a true hacker, predict the future:''')
        response = raw_input('')
        if response == str(guessing_int):
            sys.stdout.write('''Wow, guess you are a hacker.\n''')
            sys.stdout.write('''I knew you weren't a hacker''')
        print 'Good by.'

This service gives us the flag once we input the next random number from random.randint(0,999999999999). The PRNG is seeded with the UTC time and a fairly large offset

rand_int = int(rand.encode('hex'),16)

#now lets use something easier.

offset = random.randint(big_1,big_2)

The service also offers us the RSA encrypted seed enc_time = pow(time,keys['e'],keys['n']). Important here ist that we can request as many enc_time’s with the same secret offset as we want. Because of that we could probably request a couple of cipher texts and then calculate the seed.

More interesting though: this is a pitch perfect example of a related cipher text vulnerablility. Since the point of CTFs is to learn, we decided to go into that direction.

A practical attack for this scenario is the Franklin Reiter Related Message Attack.

Franklin and Reiter stated that, given an RSA public key N,e \langle N, e \rangle with low exponent (such as 3 in this case) and two related plain texts M1M2ZNM_1 \neq M_2 \in Z_{N}^{\ast} that satisfy M1f(M2)(modN)M_1 \equiv f(M_2) \pmod{N} with linear f=ax+b,b0f = ax + b, b \neq 0 we can recover the plaintext in logNlog N.

This is obviously given here, since we can wait one second between requesting the cipher texts, so in our case it is f=x+1f = x + 1.

Given all this we can create the two polynomials g1(x)=f(x)eC1ZNg_1(x) = f(x)^e - C_1 \in \mathbb{Z}_N and g2(x)=xeC2ZNg_2(x) = x^e - C_2 \in \mathbb{Z}_N. M2 M_2 is a root of both polynomials, so xM2 x-M_2 divides them both.

This means, to find M2 M_2 we have to compute the gcd(g1,g2)gcd(g_1, g_2) giving us the common factor xM2 x-M_2 . To see why this always works for the exponent 3 (and mostly for other small exponents) see the mentioned paper.

Unfortunately I didn’t find any Python code for calculating the GCD for a ring over a composite modulus. I was half way through writing the eea for polynomials with modulus myself when I stumpled upon the nifty Poly.set_modulus method in sympy’s polynomials implementation that does exactly what is needed here.

Using that, the exploit is rather short. We can use sympy’s gcd function:

f1 = poly(x**e - c1).set_modulus(n)
f2 = poly((x + 1)**e - c2).set_modulus(n)

-gcd(f1, f2).coeffs()[-1]  # sympy is awesome!

We take the negated last coefficient of the resulting term (xM2 x-M_2 ), which is our plain text string M2 M_2 .

After receiving the plain text, which is used as seed, we can compute the next random number.

After way too much time of running the exploit locally and failing remotely, I realized that the server side is using Python 2. The PRNG implementations between Python 2 (LCG) and Python 3 (Mersenne-Twister) do not have much in common.

The final exploit looks like this:

import pexpect
import subprocess
import re
from sympy import poly, symbols, gcd
from time import sleep

n = 142592923782837889588057810280074407737423643916040668869726059762141765501708356840348112967723017380491537652089235085114921790608646587431612689308433796755742900776477504777927984318043841155548537514797656674327871309567995961808817111092091178333559727506289043092271411929507972666960139142195351097141
e = 3

x = symbols('x')
num_re = re.compile("RSA!\r\n([0-9]+)\r\nWelcome")

def get_plain(c1, c2, offset):
    f1 = poly(x**e - c1).set_modulus(n)
    f2 = poly((x + 1)**e - c2).set_modulus(n)

    return -gcd(f1, f2).coeffs()[-1]  # sympy is awesome!

def next_rand(offset):
    out = subprocess.check_output(["python2", "-c",  'import random; random.seed({}); print(random.randint(0,999999999999))'.format(offset)], stderr=subprocess.STDOUT)
    return int(out.decode().strip()) 

def extract_num(s):
    return int(num_re.findall(s)[0])

while True:
    cmd = pexpect.spawn("nc 1230")
    c1 = extract_num(cmd.before.decode())



    c2 = extract_num(cmd.before.decode())

    if c1 == c2:
        continue  # Didnt get different seconds, skipping.
    plain_text = get_plain(c1, c2, 1)

    n_rand = next_rand(plain_text + 1)
    print("Next random number: {}".format(n_rand))

    print(cmd.before.decode() + "}")

Running it gives us:

Next random number: 70906011219
Wow, guess you are a hacker.