Timisoara CTF 2018 Quals Writeup

CTF writeup

この大会は2018/4/14 9:00(JST)～2018/4/21 18:00(JST)に開催されました。
今回もチームで参戦。結果は3181点で442チーム中7位でした。
自分で解けた問題をWriteupとして書いておきます。

Welcome (Misc 1)

問題にフラグが書いてある。

timctf{w3lcom3_t0_timctf_2018_quals}

Accord (Misc 5)

Accordの#generalチャネルの名前の横にフラグが書かれている。

timctf{fr33_v01c3_4nd_text_ch4t_f0r_ctfers}

History (Reverse 30)

バイナリエディタで見ると、UNICODEでフラグが記載されている。
f:id:satou-y:20180503214352p:plain

timctf{unic0d3_1s_mr_w0rldw1d3}

Picassor (Forensics 50)

XORキー1文字でjpgのフォーマットに復号する。

with open('unirii_square.jpg', 'rb') as f:
    data = f.read()

key = 0xff ^ ord(data[0])

flag = ''
for i in range(len(data)):
    flag += chr(ord(data[i]) ^ key)

with open('flag.jpg', 'wb') as f:
    f.write(flag)

f:id:satou-y:20180503214711j:plain

timctf{x0r_and_rul3_un1t3_and_l34d}

Strange behavior (Forensics 100)

FTK Imagerで開き、[root]-4_next_lecturesにある、削除済みのschedule.xlsxをエクスポートする。このExcelを開き、F10のセルを見ると、フラグが書いてある。

timctf{d0nt_f0rg3t_t0_h4v3_fun}

Those Are Rookie Numbers (Crypto 30)

nをfactordbで素因数分解する。

p = 176773485669509339371361332756951225661
q = 333197218785800427026869958933009188427

あとはそのまま復号する。

n = 58900433780152059829684181006276669633073820320761216330291745734792546625247
e = 65537
c = 56191946659070299323432594589209132754159316947267240359739328886944131258862
p = 176773485669509339371361332756951225661
q = 333197218785800427026869958933009188427

phi = (p - 1) * (q - 1)

x = 0
while True:
    if (phi * x + 1) % e == 0:
        d = (phi * x + 1) / e
        break
    x = x + 1

m = pow(c, d, n)

flag = ('%x' % m).decode('hex')
print flag

timctf{th0sE_rOoKIe_numB3rz}

Back in Time (Crypto 50)

以下の英小文字だけの換字式暗号を復号する。

hsijhk{Pc3nvO_R4NvwM_1S_Nwh_RArD0M}

timctf{}の形式なり、英文として意味がありそうなように変換する。

暗号	平文
h	t
s	i
i	m
j	c
k	f
c	s
n	u
v	d
w	o
r	n

timctf{Ps3udO_R4NdoM_1S_Not_RAnD0M}

SSS - Part 1 (Crypto 75)

差が同じなので、添付のグラフから考えると、同じ差で1つ目の値から引いたものがフラグになる。

c1 = '4612c90f5d8cd5d616193257336d92af1f66df92443b4ee69f5c885f0173ad80113844e393d194e3'
c2 = '8c25921e46b03e48b7cbe94c3267f41adf618abd16422f660b59df6fae81e8aff2242852be33db49'
c3 = 'd2385b2d2fd3a6bb597ea041316255869f5c35e7e8490fe5775736805b9023dfd3100bc1e89621af'

val1 = int(c1, 16)
val2 = int(c2, 16)
val3 = int(c3, 16)

diff1 = val2 - val1
diff2 = val3 - val2
assert diff1 == diff2

val_flag = val1 - diff1
flag = ('%x' % val_flag).decode('hex')
print flag

timctf{b4s1C_l4gr4ng3_1NTerP0LatioN}

Substitute Teacher (Crypto 100)

換字式暗号。ただし英小文字しか変換されない。小文字部分だけquipqiupを補助的に使って、対応付けをする。

暗号	平文
a	g
b	e
c	t
d	u
e	o
f	c
g	r
h	f
i	i
k	a
l	w
m	m
n	n
o	h
q	k
s	s
t	l
u	b
x	d
y	j
z	p

rev_sub_dict = {
    'a': 'g',
    'b': 'e',
    'c': 't',
    'd': 'u',
    'e': 'o',
    'f': 'c',
    'g': 'r',
    'h': 'f',
    'i': 'i',
    'j': 'x',
    'k': 'a',
    'l': 'w',
    'm': 'm',
    'n': 'n',
    'o': 'h',
    'p': 'v',
    'q': 'k',
    'r': 'y',
    's': 's',
    't': 'l',
    'u': 'b',
    'v': 'z',
    'w': 'q',
    'x': 'd',
    'y': 'j',
    'z': 'p'
}

with open('ciphertext.txt', 'r') as f:
    data = f.read()

plain = ''
for i in range(len(data)):
    if rev_sub_dict.has_key(data[i]):
        plain += rev_sub_dict[data[i]]
    else:
        plain += data[i]

with open('plaintext.txt', 'w') as f:
    f.write(plain)

復号すると、文中にフラグがある。

"She left." Fache glanced out at the darkened hallway. Apparently Sophie had been in no mood to
stop by and chat with the other officers on her way out.

For a moment, Fache considered radioing the guards in the entresol and telling them to stop Sophie
and drag her back up here before she could leave the premises. He thought better of it. That was
only his pride talking... wanting the last word. He'd had enough distractions tonight.

Deal with Agent Neveu later, he told himself, already looking forward to firing her.

Pushing Sophie from his mind, Fache stared for a moment at the miniature knight standing on
Sauniere's desk. Then he turned back to Collet. "Do you have him?"
timctf fr3quencyan4lyS1s1sc0ol
Collet gave a curt nod and spun the laptop toward Fache. The red dot was clearly visible on the
floor plan overlay, blinking methodically in a room marked TOILETTES PUBLIQUES.

"Good," Fache said, lighting a cigarette and stalking into the hall. I've got a phone call to make. Be
damned sure the rest room is the only place Langdon goes."

timctf{fr3quencyan4lyS1s1sc0ol}

Not Your Average RSA (Crypto 100)

nを素因数分解する。

$ python -m primefac 18086135173395641986123054725350673124644081001065528104355398467069161310728333370888782472390469310073117314933010148415971838393130403883412870626619053053672200815153337045022984003065791405742151350233540671714100052962945261324862393058079670757430356345222006961306738393548705354069502196752913415352527
18086135173395641986123054725350673124644081001065528104355398467069161310728333370888782472390469310073117314933010148415971838393130403883412870626619053053672200815153337045022984003065791405742151350233540671714100052962945261324862393058079670757430356345222006961306738393548705354069502196752913415352527: 19459483 18145913 20197313 27409927 22685197 16904777 31696261 18313601 31737131 31881917 18646361 17901463 29511773 21321539 25808239 24525821 20010041 21647243 27138691 33322589 22576643 17673199 27739163 30342329 23554169 21891889 33098557 31703933 17730961 22050221 24996157 25671797 27606707 27289543 28863719 25963459 20390129 24946057 33381329 29488469 20013121 30580789

この結果から、Muti-Prime RSAの復号プログラムを書く。eは通常の65537にした。

import gmpy

def chinese_remainder(n, a):
    sum = 0
    prod = reduce(lambda a, b: a*b, n)

    for n_i, a_i in zip(n, a):
        p = prod / n_i
        sum += a_i * gmpy.invert(p, n_i) * p
    return sum % prod

c = 9074407119435549226216306717104313210750146895081726439798095976354600576814818348656600684713830051655944443364224597709641982342039946659987121376590618828822446965847273448794324003758131816407702456966504389655568712152599077538994030379567217702587542326383955580601916478060973206347266442527564009737910
e = 65537
n = 18086135173395641986123054725350673124644081001065528104355398467069161310728333370888782472390469310073117314933010148415971838393130403883412870626619053053672200815153337045022984003065791405742151350233540671714100052962945261324862393058079670757430356345222006961306738393548705354069502196752913415352527

primes = [
    19459483, 18145913, 20197313, 27409927, 22685197, 16904777, 31696261,
    18313601, 31737131, 31881917, 18646361, 17901463, 29511773, 21321539,
    25808239, 24525821, 20010041, 21647243, 27138691, 33322589, 22576643,
    17673199, 27739163, 30342329, 23554169, 21891889, 33098557, 31703933,
    17730961, 22050221, 24996157, 25671797, 27606707, 27289543, 28863719,
    25963459, 20390129, 24946057, 33381329, 29488469, 20013121, 30580789]

n_ary = []
a_ary = []
for p in primes:
    phi = p - 1
    d = gmpy.invert(e, phi)
    mk = pow(c, d, p)
    n_ary.append(p)
    a_ary.append(mk)

m = chinese_remainder(n_ary, a_ary)
flag = ('%x' % m).decode('hex')
print flag

timctf{mUlt1_PriM3_rS4_c0ULD_B3_DAngEr0us}

Hush Hush (Crypto 150)

inputの2回目は、1回目に入力したものの前に\x00（いくつでもよい）を入力すればよい。
例えば、以下を指定する。

・\x00
・\x00\x00

import socket

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('89.38.210.129', 6665))

data = s.recv(256)
print data
data = s.recv(256)

input1 = '\x00'
print data + input1
s.sendall(input1 + '\n')
data = s.recv(256)
input2 = '\x00\x00'
print data + input2
s.sendall(input2 + '\n')
data = s.recv(256)
print data

timctf{d0UbT_3verYTH1nG}

SSS - Part 2 (Crypto 250)

10バイトごとに暗号化。暗号化は以下のような処理。

x = 1の場合
c1 * 1 + c2 * 1^2 + c3 * 1^3 + ... + c12 * 1^12 + flag = y1
x = 2の場合
c1 * 2 + c2 * 2^2 + c3 * 2^3 + ... + c12 * 2^12 + flag = y2
x = 3の場合
c1 * 3 + c2 * 3^2 + c3 * 3^3 + ... + c12 * 3^12 + flag = y3
　　　　　：
x = 16の場合
c1 * 16 + c2 * 16^2 + c3 * 16^3 + ... + c12 * 16^12 + flag = y16

10バイトの暗号化間では差はflagの差でしかない。同じxの値では、flag2 - flag1 = y21 - y11
timctf{で始まり}で終わることを条件にブルートフォースで求める。

import itertools

def is_printable(s):
    for i in range(len(s)):
        if ord(s[i]) < 32 or ord(s[i]) > 126:
            return False
    return True

val0_1 = 7714685804569579757659784
val1_1 = 7534756766114272409848924
val3_1 = 7164946524794170391755686

val0_2 = 3547087743966283680068135913
val1_2 = 3546907814927828372720325053
val2_2 = 3547059021367945143469206505

val0_7 = 3756478321347707411745123850684568
val2_7 = 3756478321318984813406587251755160
val3_7 = 3756478320797968131969714484780470

assert val1_1 - val0_1 == val1_2 - val0_2
diff1 = val1_1 - val0_1

assert val2_2 - val0_2 == val2_7 - val0_7
diff2 = val2_2 - val0_2

assert val3_1 - val0_1 == val3_7 - val0_7
diff3 = val3_1 - val0_1

flag_head = 'timctf{'

chars = ''
for code in range(32, 127):
    chars += chr(code)

for c in itertools.product(chars, repeat=3):
    flag0 = flag_head + ''.join(c)
    int_flag0 = int(flag0.encode('hex'), 16)
    int_flag1 = int_flag0 + diff1
    int_flag2 = int_flag0 + diff2
    int_flag3 = int_flag0 + diff3
    hex_flag1 = '%x' % int_flag1
    hex_flag2 = '%x' % int_flag2
    hex_flag3 = '%x' % int_flag3
    if len(hex_flag1) % 2 == 0:
        flag1 = hex_flag1.decode('hex')
        if is_printable(flag1) == False:
            continue
    if len(hex_flag2) % 2 == 0:
        flag2 = hex_flag2.decode('hex')
        if is_printable(flag2) == False:
            continue
    if len(hex_flag3) % 2 == 0:
        flag3 = hex_flag3.decode('hex')
        if is_printable(flag3) == False:
            continue
        if flag3[-1] != '}':
            continue
    flag = flag0 + flag1 + flag2 + flag3
    print flag

候補はたくさん出てくるので、英語の文章になるものをsubmitしていく。

timctf{d0_NOt_R3inV3nT_CrYpt0_Pl34sE}

Feedback (Misc 10)

アンケートに答えて、再度アンケートフォームにアクセスすると、フラグが表示されていた。

timctf{we_hope_it_was_fun_and_youll_be_back_next_year}