TUCTF - Crypto Clock (300 pts)
Deskripsi soal
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 cryptoclock.tuctf.com 1230
MD5 (network_dump) = bdfcfee713b6ad53f4923f96863e385c
UPDATE: The server side code is running Python 2
Solusi
Diberikan koneksi socat dan sebuah file pcap. Ketika file pcap diekstrak didapatkan string base64 encode yang sepertinya merupakan source dari program socat tersebut.
Berikut adalah source code dari program tersebut
#!/usr/bin/env python
import sys
import random
import arrow
big_1=44125640252420890531874960299151489144331823129767199713521591380666658119888039423611193245874268914543544757701212460841500066756559202618153643704131510144412854121922874915334989288095965983299150884589072558175944926880089918837606946144787884895502736057098445881755704071137014578861355153558L
big_2=66696868460135246134548422790675846019514082280010222055190431834695902320690870624800896599876321653748703472303898494328735060007496463688173184134683195070014971393479052888965363156438222430598115999221042866547813179681064777805881205219874282594291769479529691352248899548787766385840180279125343043041L
flag = "THEFLAG"
keys = {
"n":142592923782837889588057810280074407737423643916040668869726059762141765501708356840348112967723017380491537652089235085114921790608646587431612689308433796755742900776477504777927984318043841155548537514797656674327871309567995961808817111092091178333559727506289043092271411929507972666960139142195351097141,
"e": 3
}
#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
Kita coba jalankan program tersebut di lokal.
Welcome to the ntp server
What would you like to do?
1) get current time
2) enter admin area
3) exit
:1
HAHAHAHAHAHA, this NTP server has been taken over by hackers!!!
here is the time encrypted with sweet RSA!
65591483448351902802226912239888261427877913051459257537112647909433135321660465779739007818787246507102769966318792178070355998594386277071706789962602338898599051561589547815383532059656459033598538670267245423729643879149408096186929277608549861896324902862127612063620348480277444341149873394682980975464
Welcome to the ntp server
What would you like to do?
1) get current time
2) enter admin area
3) exit
:2
ACCESS IS ONLY FOR TRUE HACKERS!
to prove you are a true hacker, predict the future:1337
I knew you weren't a hacker
Sebelum program tersebut dijalankan, program akan menggenerate variabel random antara byte1 dan byte2 dengan 8 byte seed dari urandom.
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)
Terdapat 3 pilihan. Jika kita memilih 1, program akan mengoutput nilai enc_time yang merupakan hasil RSA encyript dengan plain = utcnow + offset
, dengan e = 3
, dan n = 142592923782837889588057810280074407737423643916040668869726059762141765501708356840348112967723017380491537652089235085114921790608646587431612689308433796755742900776477504777927984318043841155548537514797656674327871309567995961808817111092091178333559727506289043092271411929507972666960139142195351097141;
Karena bilangan n yang besar, n tidak dapat difaktorkan dengan menggunakan faktor db.
if response == '1':
time = arrow.utcnow().timestamp + offset
enc_time = pow(time,keys['e'],keys['n'])
sys.stdout.write(str(enc_time))
Pada pilihan kedua nilai enctime saat ini, dijadikan randomseed. Lalu program menggenerate nilai random yang harus kita tebak. Jika kita berhasil menebak angka random tersebut kita akan mendapatkan flag.
elif response == '2':
# lets get even more random!
time = arrow.utcnow().timestamp + offset
random.seed(time)
guessing_int = random.randint(0,999999999999)
response = raw_input('')
if response == str(guessing_int):
sys.stdout.write(flag)
Inti dari challange ini adalah kita harus menebak berapa offset random yang di generate oleh program. Kita coba analisis dari sistem enkripsi RSA pada pilihan 1.
Jika kita lihat time yang diencrypt
time = arrow.utcnow().timestamp + offset
time akan bertambah satu setiap detik.
Kita misalkan time stamp saat ini adalah ts
time0 = ts + offset
time1 = ts + offset + 1
time2 = ts + offset + 2
time3 = ts + offset + 3
.
.
.
Kita coba ringkas lagi. ts + offset menjadi tso
time0 = tso
time1 = tso + 1
time2 = tso + 2
time3 = tso + 3
.
.
Dapat diliat pola dari plaintext linier. Sehingga kita dapat mendapatkan nilai tso tanpa mencari private key, yaitu dengan menggunakan Franklin Reiter Attack
Kita coba buat enkripsi RSA menjadi sebuah persamaan polinomial dengan derajat 3 karena e = 3.
enctime0 = RSA(time0, 3, n) = (tso)**3 % n
enctime1 = RSA(time1, 3, n) = (tso + 1)**3 % n =( tso**3 + 3 * tso**2 + 3 * tso + 1 ) % n
enctime2 = RSA(time2, 3, n) = (tso + 2)**3 % n =( tso**3 + 6 * tso**2 + 12 * tso + 4 ) % n
enctime3 = RSA(time3, 3, n) = (tso + 3)**3 % n =( tso**3 + 9 * tso**2 + 27 * tso + 9 ) % n
Jika kita manipulasi keempat persamaan tersebut secara manual. Dapat diperoleh persamaan dengan derajat 1. Contohnya seperti berikut.
enctime3 + enctime0 - enctime1 - enctime2 = (12 * tso + 18 ) % n
Karena persamaan sudah terlihat linier, maka kita dapat mencari nilai tso dengan mudah. Bisa dengan gmpy atau kita coba manual.
Jika kita mengetahui nilai tso, kita dapat menggenerate nilai offset dan menggenerate nilai random yang sama dengan yang dibuat oleh program.
Berikut script untuk mendapatkan flag
import random
import arrow
import time
from pwn import *
from sys import *
keys = {
"n":142592923782837889588057810280074407737423643916040668869726059762141765501708356840348112967723017380491537652089235085114921790608646587431612689308433796755742900776477504777927984318043841155548537514797656674327871309567995961808817111092091178333559727506289043092271411929507972666960139142195351097141,
"e": 3
}
def getcur():
p.sendline('1')
p.recvuntil('RSA!\n')
return eval(p.recvline().strip())
def getdata():
for i in range(4):
if i == 0:
firsttime.append(arrow.utcnow().timestamp)
# ambil time awal
enctime.append(getcur())
# print enctime[i]
# print
sleep(1)
def compute():
# enctime3 + enctime0 - enctime1 - enctime2 = (12 * tso + 18 ) % n
totalenc = enctime[3] + enctime[0] - enctime[1] - enctime[2] - 18
totalenc = totalenc % keys['n']
while totalenc % 12 != 0:
totalenc += keys['n']
# bruteforce manual mencari kelipatan 12
tso = (totalenc/12) % keys['n']
offset = tso - firsttime[0]
assert enctime[0] == pow(firsttime[0]+offset, 3, keys['n'])
# print enctime[0], pow(firsttime+offset, 3, keys['n'])
# cek manual enc time dengan enc sistem
return offset
def attack(offset):
time = arrow.utcnow().timestamp + offset
print offset
p.sendline('2')
random.seed(time)
guessing_int = random.randint(0,999999999999)
p.sendline(str(guessing_int))
p.interactive()
# print anything
enctime = []
p = process('./soal.py')
firsttime = []
getdata()
offset = compute()
attack(offset)
Mati kita coba jalankan dengan semangat
a@a-l ~/CTF/tuctf/crypto/cryptoclock $ python solve.py
[+] Starting local process './soal.py': pid 8101
55969035464709264574317945966340530441212223514033774913384027420606040108552999045539910802429093186897367580038431282346833841212343691474112849644573699358976007547301899048552330679832668433949084639764634834550486404163431865278602312818657312396033813763706085140312567944945436838398692227407066593980
[*] Switching to interactive mode
Welcome to the ntp server
What would you like to do?
1) get current time
2) enter admin area
3) exit
:ACCESS IS ONLY FOR TRUE HACKERS!
to prove you are a true hacker, predict the future:Wow, guess you are a hacker.
THEFLAG
[*] Got EOF while reading in interactive
$
[*] Process './soal.py' stopped with exit code 0 (pid 8101)
Bahan referensi : RSA Paper
Tidak ada komentar:
Posting Komentar