BSides Delhi CTF 2018 Writeup - よっちんのブログ

この大会は2018/10/25 20:00(JST)～2018/10/26 20:00(JST)に開催されました。
今回もチームで参戦。結果は 1376点で426チーム中23位でした。
自分で解けた問題をWriteupとして書いておきます。

Sanity Check (Welcome 1)

freenodeで#bi0s-ctfチャネルに入る。

20:44 *topic :  Official channel for BSides CTF  | Flag for sanity check: flag{w3lc0m3}  | CTF starts at 11:30 UTC and runs for 24 hours

flag{w3lc0m3}

RSA-Baby (Crypto 100)

modulusのうちそれぞれペアで公約数を出してみる。1以外の公約数があったので、素因数分解できた。素因数分解できたnに対応するeは素数ではない。
例えば、1つ目は以下のようになる。

114194 = 2 * 57097

RSA暗号はm^e%n=cなので、m^(e1*e2)%n=c、(m^e1)^e2%n=cとなる。
一旦57097で復号する。その後2乗根で、フラグが得られるかどうか試してみる。

from Crypto.Util.number import *
import itertools
import gmpy

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    gcd = b
    return gcd, x, y

modulus_list = [143786356117385195355522728814418684024129402954309769186869633376407480449846714776247533950484109173163811708549269029920405450237443197994941951104068001708682945191370596050916441792714228818475059839352105948003874426539429621408867171203559281132589926504992702401428910240117807627890055235377744541913L,
 73988726804584255779346831019194873108586184186524793132656027600961771331094234332693404730437468912329694216269372797532334390363774803642809945268154324370355113538927414351037561899998734391507272602074924837440885467211134022878597523920836541794820777951492188067045604789153534513271406458984968338509L,
 95666403279611361071535593067846981517930129087906362381453835849857496766736720885263927273295086034390557353492037703154353541274448884795437287235560639118986397838850340017834752502157881329960725771502503917735194236743345777337851076649842634506339513864285786698870866229339372558162315435127197444193L, 
 119235191922699211973494433973985286182951917872084464216722572875998345005104112625024274855529546680909781406076412741844254205002739352725207590519921992295941563460138887173402493503653397592300336588721082590464192875253265214253650991510709511154297580284525736720396804660126786258245028204861220690641L]

e = [114194L, 130478L, 122694L, 79874L]

ciphertext = ['0c55bc89e3773d8e378121eced4f9300103a8696bc3f9a1542c5b1539442ca5de03a40ad564ab5c2e764b2f946058ec220abf20afc271896ff4ca1f4a2dd227405f221de51e097d6b9f270c4561cd25596e96efd7de1a0e65d37cbf6a73c62a7e323f48450b9dc75e3e738ec1c7e1ae9fc808da8c476e72aea9155125b815653', '67caf9720696b1d0d589f053bb00ebe42b7b26fed38acb4012d29ddc55cd53da8398f042f22987453bdfa2ee8fb35ff121f81e96137995a8ca4daa1fbd88af3fd29138853d5fe98f9b983f67d6fd2b7ff6650228479ca6cac1d49572d28f01a659892b0799ca8202031a1ab37656331470d3ea5f221cc948636c1027bb6dd10f', '65e1cffe93ebccd49a9d14c01b2583a5d5e3140bf38a768833aa494d2d879a2934dbc10a843ec834e9ade286824e68879cb09ac9bd67afd7318b74955e9aa66df5740e6dcc26ccc787f0b415bdc80c6468421c4d4ce615fa3d25350940c5004e9b480c86faebc31e809725a9a868c94e9f1eaac567b4672fe395a7b205775883', '23108bb7f35d12b69bbe5e649ff47fb802b68f22045c484805040a3f4f8669acde8b04daba71190154aef4be9a0eafdebe31b5f96e8b01b5085f502fc0e12a326cc4d867f5317ac12bf16607765d99708934c35c4b9404747f69988ea7d3f4d8022cdfd81ada3aedb22d110db4aa81038aa151c9a4dbb5651757dc092b70b84d']

for ns in list(itertools.combinations(modulus_list, 2)):
    gcd = egcd(ns[0], ns[1])
    if gcd[0] > 1:
        n = ns[0]
        p = gcd[0]
        q = n / p

idx = modulus_list.index(n)
print 'index =', idx

c = int(ciphertext[idx], 16)
phi = (p - 1) * (q - 1)
d = inverse(e[idx]/2, phi)
m_tmp = pow(c, d, n)

m = gmpy.root(m_tmp, 2)[0]
flag = long_to_bytes(m)
print flag

flag{Congratzzz_y0u_kn0w_ext3nded_GCD_WOw!!}

pyQueue (Crypto 150)

keyが少しずつ後ろにずれて、暗号化していて、以下のようなイメージになっている。

1ブロック目：key[1:] + ?
2ブロック目：key[2:] + ? + ?
3ブロック目：key[3:] + ? + ? + ?

MAC: C1 ^ C2 ^ C3 ^ (key[4:] + ? + ? + ? + ?)

最終的なMACがわかっているので、逆算して鍵を割り出していけば、復号できる。鍵の最初の1バイトに対して、ブルートフォース。

from Crypto.Util.number import *
from Crypto.Cipher import AES

def is_printable(s):
    for c in s:
        code = ord(c)
        if code > 126:
             return False
    return True

def unpad(s):
    return s[:-ord(s[-1])]

with open('ci.pher.text', 'r') as f:
    data = f.read().split(':')

MAC = int(data[0])
ct = data[1]

ct1 = ct[:32]
ct2 = ct[32:64]
ct3 = ct[64:]
ct = [ct1, ct2, ct3]
key = int(ct1, 16) ^ int(ct2, 16) ^ int(ct3, 16) ^ MAC
key = long_to_bytes(key)

flag = ''
for i in range(len(ct)):
    for code in range(256):
        try_key = chr(code) + key[:-1]
        cipher = AES.new(try_key, AES.MODE_ECB)
        pt = cipher.decrypt(ct[2-i].decode('hex'))
        if is_printable(pt):
            flag = pt + flag
            key = try_key
            break

flag = unpad(flag)
print flag

flag{H4il_bUggi3s!_qu3u3_k3y_2_h0t_4_w4rmUp}

RSA-reloaded (Crypto 200)

rとsは比較的近い素数と考えられるため、Fermat法で素因数分解する。さらにx+f1の次の素数がrになることからxの範囲を探し、2次方程式を解くことによって、p,qを求め復号する。

q%p = x
q = p*k+x

まずはk=1で考える。
⇒p * (p+x) = N1 ⇒ p**2 + x*p = N1
⇒該当するpが見つかる。

最終的なコードは以下の通り。

from Crypto.PublicKey import RSA
from Crypto.Util.number import *
import gmpy
from z3 import *

def isqrt(n):
    x = n
    y = (x + n // x) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

def fermat(n):
    x = isqrt(n) + 1
    y = isqrt(x * x - n)
    while True:
        w = x * x - n - y * y
        if w == 0:
            break
        elif w > 0:
            y += 1
        else:
            x += 1
    return x - y, x + y

with open('publickey2.pem', 'r') as f:
    pub_data2 = f.read()

pubkey2 = RSA.importKey(pub_data2)
N2 = pubkey2.n
e = pubkey2.e

r, s = fermat(N2)

with open('ciphertext2.txt', 'r') as f:
    enc_f2 = int(f.read())

phi2 = (r - 1) * (s - 1)
d2 = inverse(e, phi2)
f1 = pow(enc_f2, d2, N2)

flag1 = long_to_bytes(f1)

x = r - f1 - 1

with open('publickey1.pem', 'r') as f:
    pub_data1 = f.read()

pubkey1 = RSA.importKey(pub_data1)
N1 = pubkey1.n
e = pubkey1.e

p = Int('p')
while True:
    np = gmpy.next_prime(x + f1)
    if np != r:
        break
    s = Solver()
    s.add(p**2 + x*p == N1, p > 0)
    if s.check() == sat:
        p = s.model()[p].as_long()
        q = p + x
        break
    x -= 1

with open('ciphertext1.txt', 'r') as f:
    enc_f1 = int(f.read())

phi1 = (p - 1) * (q - 1)
d1 = inverse(e, phi1)
f2 = pow(enc_f1, d1, N1)

flag2 = long_to_bytes(f2)

flag = flag1 + flag2
print flag

flag{F3rm@t_&_s0me_t1nk3r1ng_can_d0_w0nd3rs!!!!}

FuzzY (Forensics 200)

httpでフィルタリングし、success.txtを取得すると、PGP MESSAGEが含まれていた。

これをsuccess.gpgとして保存する。秘密鍵もどこかにあるはずなので、探してみる。DNSの通信の中にPNGが含まれていたが、分散していたので、スクリプトで抽出する。

from scapy.all import *

packets = rdpcap('final_fuzz.pcap')

png = ''
for p in packets:
    if p.haslayer(IP) and p.haslayer(UDP):
        if p[IP].src == '192.168.42.129' and p[UDP].sport == 53:
            pad = p[Padding].load.lstrip('\x00')
            png += pad

with open('out.png', 'wb') as f:
    f.write(png)

この結果、QRコードの画像が抽出できる。
f:id:satou-y:20181028202214p:plain
このQRコードを読み取ると、以下の秘密鍵が取得できる。

これをprivate.ascとして保存する。
復号してみる。

$ gpg --import private.asc
gpg: 鍵F67F2BE2: 秘密鍵をインポートしました
gpg: /home/ctf/.gnupg/trustdb.gpg: 信用データベースができました
gpg: 鍵F67F2BE2: 公開鍵"kartik997@gmail.com"をインポートしました
gpg: 処理数の合計: 1
gpg:               インポート: 1  (RSA: 1)
gpg:       秘密鍵の読み込み: 1
gpg:   秘密鍵のインポート: 1
$ gpg success.gpg

次のユーザの秘密鍵のロックを解除するには
パスフレーズがいります

パスフレーズが必要なので、探してみる。先ほどのQRコードのPNGファイルのzTXtチャンクに怪しいデータがある。

4578696600004d4d002a000000080003010e00020000000b000000320128000300000001
000200000213000300000001000100000000000068656c6c6f776f726c640000

末尾のデータをhexデコードする。

$ echo 68656c6c6f776f726c64 | xxd -r -p
helloworld

これをパスフレーズにして復号する。

$ gpg success.gpg

次のユーザの秘密鍵のロックを解除するには
パスフレーズがいります:"kartik997@gmail.com"
2048ビットRSA鍵, ID F67F2BE2作成日付は2018-10-23

gpg: *警告*: 暗号アルゴリズムAES256は受取人の優先指定に入っていません
gpg: 2048-ビットRSA鍵, ID F67F2BE2, 日付2018-10-23に暗号化されました
      "kartik997@gmail.com"
$ cat success
flag{eNcryP7!ng_t0_PgP_1s_r34LLy_Pre3tY_g00D_pr1V4cY}

flag{eNcryP7!ng_t0_PgP_1s_r34LLy_Pre3tY_g00D_pr1V4cY}