TUCTF 2017: Crypto Clock (300)

Mon 27 November 2017 · 4 min read

We are given a network dump file, network_dump and a service that we can connect to. After we open the file, we find two file was transmitted. The first one is the keys file which contains the following:

{
"n":142592923782837889588057810280074407737423643916040668869726059762141765501708356840348112967723017380491537652089235085114921790608646587431612689308433796755742900776477504777927984318043841155548537514797656674327871309567995961808817111092091178333559727506289043092271411929507972666960139142195351097141,
"e": 3
}

The second one is a python script file which contains the following

import sys
import random
import json
import arrow

big_1=44125640252420890531874960299151489144331823129767199713521591380666658119888039423611193245874268914543544757701212460841500066756559202618153643704131510144412854121922874915334989288095965983299150884589072558175944926880089918837606946144787884895502736057098445881755704071137014578861355153558L
big_2=66696868460135246134548422790675846019514082280010222055190431834695902320690870624800896599876321653748703472303898494328735060007496463688173184134683195070014971393479052888965363156438222430598115999221042866547813179681064777805881205219874282594291769479529691352248899548787766385840180279125343043041L


with open('flag') as f:
    flag = f.read()


with open('keys') as f:
    keys = json.load(f)

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

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

#now lets use something easier.
random.seed(rand_int)

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
:''')
    sys.stdout.flush()
    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')
        sys.stdout.write(str(enc_time))
        sys.stdout.write('\n')
        sys.stdout.flush()
    elif response == '2':
        # lets get even more random!
        time = arrow.utcnow().timestamp + offset
        random.seed(time)
        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:''')
        sys.stdout.flush()
        response = raw_input('')
        if response == str(guessing_int):
            sys.stdout.write('''Wow, guess you are a hacker.\n''')
            sys.stdout.write(flag)
            sys.stdout.write('\n')
            break
        else:
            sys.stdout.write('''I knew you weren't a hacker''')
            sys.stdout.write('\n')
            break
    else:
        print 'Good by.'
        break

It seems that the python script is actually what the service given from the challenge execute when we connect to it. Since there's read flag and write flag line, lets try figure this script out!

When we connect to the service, the service compute some random number named offset and then give two choices: one is to get the (time+offset) encrypted like RSA with public key, and the other is to guess a random number generated with (time+offset) as the seed. The flag is printed on the second menu, but we don't know the seed since the offset is basically calculated with /dev/urandom. We see that the offset is also used in the first menu, so lets take a look at the first menu.

Let $msg$ as the value of (time+offset) that we seek. In the first menu, the service encrypt $msg$ and then dump it to us. So we need to decrypt it. Factoring n with yafu and msieve seems not feasible, so finding decryption key will be hard. But, there's a catch with the public key. The e that is used for the encryption is 3, which is quite small. We can also request for menu 1 repeatedly, we can get the service to dump consecutive numbers for the original number. This means we can kind of pick multiple plaintexts that are pair-wise related and could be represented in one variable. The small e means the representation of the ciphertext will be a low degree polynomial so we can try to solve the system of linear equations by hand.

Let $a$, $a+1$, and $a+2$ be the original messages with $a = msg$. When encrypted, these messages will be:

$$ e_1 \equiv a^3 \pmod n $$

$$ e_2 \equiv a^3+3a^2+3a+1 \pmod n $$

$$ e_3 \equiv a^3+6a^2+12a+8 \pmod n $$

with $e_i$ is the $i$-th encrypted message. To solve for $a$, let's eliminate all the term except for $a$ with exponent of $1$.

$$ r \equiv (e_3-e_1)-2(e_2-e_1)-6 \equiv 6*a \pmod n $$

then solving for $a$:

$$a \equiv r*6^{-1} \pmod n$$

Thus, we got $a$ or $msg$, which is the value that we seek for.

Once we got $msg$, we calculate the offset, then mimic the server algorithm to generate the number that we need to guess. After we guessed it right, the service will give us the flag. Yay! Here's the script for getting the flag:

import gmpy2
import random
import arrow
from pwn import *

'''
we search three consecutive timestamp so we can use the following formula:
    a_1 = a^3 % n
    a_2 = a^3 + 3a^2 + 3a + 1 % n
    a_3 = a^3 + 6a^2 + 12a + 8 % n

    p_2 = 6a^2 + 12a + 8 % n
    p_1 = 3a^2 + 3a + 1 % n

    r = 6 * a % n
then, we can solve a = r * 6^(-1) % n, with a as the encrypted message.

after we got a, we can calculate offset and mimic how the server generate the number in menu 2.
'''
def get_clock():
    p.recvuntil(':')
    p.sendline('1')
    p.recvuntil('RSA!\n')
    return p.recvline().strip()

n = 142592923782837889588057810280074407737423643916040668869726059762141765501708356840348112967723017380491537652089235085114921790608646587431612689308433796755742900776477504777927984318043841155548537514797656674327871309567995961808817111092091178333559727506289043092271411929507972666960139142195351097141
inv = long(gmpy2.invert(6, n))
p = remote('cryptoclock.tuctf.com', 1230)
# p = remote('localhost', 13337)

interval = 0.5 # mind with the ping
while True: # retry if we don't get three different results
    curtime = arrow.utcnow().timestamp
    a_1 = int(get_clock())
    sleep(interval)
    a_2 = int(get_clock())
    sleep(interval)
    a_3 = int(get_clock())
    if a_1 != a_2 and a_1 != a_3 and a_2 != a_3:
        break

p_1 = (a_2 - a_1 + n) % n
p_2 = (a_3 - a_1 + n) % n
r = (p_2-2*p_1-6)
a = (r * inv) % n
offset = a - curtime

p.recvuntil(':')
p.sendline('2')

curtime = arrow.utcnow().timestamp + offset
random.seed(curtime)
guessing_int = random.randint(0,999999999999)
p.sendline(str(guessing_int))

p.interactive()

Flag is: TUCTF{g00d_th1ng_th3_futur3_i5_r3lated!}

Related Posts