X-MAS CTF 2018 Writeup

この大会は2018/12/15 3:00(JST)～2018/12/22 3:00(JST)に開催されました。
今回もチームで参戦。結果は 2768点で1378チーム中62位でした。
自分で解けた問題をWriteupとして書いておきます。

Merry Christmas (Sanity Check 1)

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

X-MAS{HTSP_w1$h3s_y0u_4_m3rRy_Christmas}

Santa's Private Talks Room (Sanity Check 5)

Discordに入ると、generalチャネルにフラグが書いてあった。

X-MAS{d15c0rd_50_c00l_7h47_54n74_u535_17_700}

Santa The Weaver (Misc)

$ strings flag.png | grep X-MAS
X-MAS{S4n7a_l1k3s_h1di()g_gif7$}

X-MAS{S4n7a_l1k3s_h1di()g_gif7$}

Oh Christmas Tree (Forensics)

$ strings Merry\ Christmas.jpg | grep X-MAS
Copyright (c) 1998 Hewlett-X-MAS{0_Chr15tm

フラグが分離しているようだ。

$ strings Merry\ Christmas.jpg | grep as_
IEC as_tr33_1s_th1s_a
$ strings Merry\ Christmas.jpg | grep _ | grep }
IEC _flag_i_wond3r}..
    :

X-MAS{0_Chr15tmas_tr33_1s_th1s_a_flag_i_wond3r}

Santa's Security Levels (Forensics)

Audacityで開き、スペクトグラムを見る。

モールス信号のようだ。

--. .. - .... ..- -...  -.-. --- --  --. --- --- --- --. .- .-..  -..- -- .- ...

GITHUBCOMGOOOGALXMAS

これはURLを表しているのかも。https://github.com/gooogal/xmasにアクセスしてみる。special message.txtに以下のように書いてある。

anta doesn't like people searching for his flags, but you look like a nice person. 
Anyway here's your flag:

vF ur uNq nAlguvat pbasvqraGvNy gb fnl, ur jebgr Vg ia pvcure, gung vF, ol FB punaTvat gur beqre bs gur Yrggref bs gur nycuNorg, gung abg n jbeQ pbhyq or ZnQR bHg.

https://quipqiup.com/で復号する。

iS he hAd aNything confidenTiAl to say, he wrote It ?n cipher, that iS, by SO chanGing the order of the Letters of the alphAbet, that not a worD could be MaDE oUt.

大文字を並べる。

SANTAISSGLADMDEU

X-MAS{santaissogladmdeu}

Message from Santa (Forensics)

FTK Imagerで開き、[root]-[.Trash-0]-[files]のファイル群をエクスポートする。
パズルを解くように画像を結合していくと、フラグが現れた。

X-MAS{1t_l00k5_l1k3_s4nta_m4de_4_m1stak3_sorry}

Hanukkah (Crypto)

暗号のパラメータは以下の通り。

r: 256bit, 偶数
p =  3 * r**2 +  2 * r + 7331
q = 17 * r**2 + 18 * r + 1339
n = p * q

privekey = (p, q)
pubkey = n

rの高次方程式を解くことによって、p, qを求める。eが2になっているため、RSA暗号ではなく、Rabin暗号。
Rabin暗号を解くと、4パターン復号できるが、その中でフラグの条件にあてはまるものを選択する。

from Crypto.Util.number import long_to_bytes
from sympy import *

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        gcd, y, x = egcd(b % a, a)
        return gcd, x - (b // a) * y, y

pubkey = 577080346122592746450960451960811644036616146551114466727848435471345510503600476295033089858879506008659314011731832530327234404538741244932419600335200164601269385608667547863884257092161720382751699219503255979447796158029804610763137212345011761551677964560842758022253563721669200186956359020683979540809

var('r')
eq = Eq((3 * r**2 +  2 * r + 7331) * (17 * r**2 + 18 * r + 1339) - pubkey)
ans = solve(eq)
r = ans[0]

p = 3 * r**2 +  2 * r + 7331
q = 17 * r**2 + 18 * r + 1339

assert pubkey == p * q
assert p % 4 == 3
assert q % 4 == 3

with open('flag.enc', 'r') as f:
    ct = int(f.read().split(' = ')[1])

r = pow(ct, long((p+1)/4), long(p))
s = pow(ct, long((q+1)/4), long(q))

gcd, c, d = egcd(p, q)
x = (r * d * q + s * c * p) % pubkey
y = (r * d * q - s * c * p) % pubkey
plains = [x, pubkey - x, y, pubkey - y]

for plain in plains:
    flag = long_to_bytes(plain)
    if flag[-1] == 'X':
        print flag.rstrip('X')
        break

X-MAS{H4nukk4h_Rabb1_and_Rab1n_l0ok_4nd_s0und_v3ry_much_alik3_H4nukk4h}

Special Christmas Wishlist (Crypto)

図形を文字に置き換えてみる。

ABCDCEFG AHIJDCEFG KHELG LDJI
JDMBNNG NBODAP QHHRGIFL
KCOA QGGM JABLLGL LGC HN CSH
QBF FHJ SDLFHO CEOQAGML
BFTGICEMGM OEACDCHHA UADV SBCUK
CSDJ OBMLKOBAAHS LRGSGM

途中でquipqiupで復号する。

LATITUDE LONGITUDE HOUSE SIGN
GIRAFFE FAMILY BOOKENDS
HTML BEER GLASSES SET OF TWO
BAD DOG WISDOM TUMBLERS
ADVENTURER MULTITOOL CLIP WATCH
TWIG MARSHMALLOW SKEWER

結構長いので、FLAGの文字を探すことにする。対応付けたNABJがFLAGになる。
すると最後の方にFLAGの文字があることがわかる。

CKG NABJ DL
ZOBLYHEBMGLHJHHFBCLEQLCDCECDHIUDVKGML

この最後の二行だけ復号してみる。

LATITUDE LONGITUDE HOUSE SIGN
GIRAFFE FAMILY BOOKENDS
HTML BEER GLASSES SET OF TWO
BAD DOG WISDOM TUMBLERS
ADVENTURER MULTITOOL CLIP WATCH
TWIG MARSHMALLOW SKEWER
            :
THE FLAG IS
XMASYOUARESOGOODATSUBSTITUTIONCIPHERS

xmasyouaresogoodatsubstitutionciphers

Santa's list (Crypto)

$ nc 95.179.163.167 16001
Ho, ho, ho and welcome back!
Your list for this year:

Sarah - Nice
Bob - Nice
Eve - Naughty
Galf - 9bb1ea1bc3fd26da23bcc981ee043c2882c72521121dc4b2fd1be39ea2bd22887902950b7c6a3c2d58463da517383a2831d00c1b4efac7e157e3a70185bfbf5d606565a4cc7d1d806cb5274353df350852a18f7b78a18d01eb0900e03a5cec37a950027168ed70dea21f84089b67c67b8a9c6e77f65173f6d5e0378e522164be
Alice - Nice
Johnny - Naughty

[1] Encrypt
[2] Decrypt
[3] Exit

スクリプトの概要は以下の通り。

・encrypt
平文(数値)を指定すると、暗号化して表示する。
平文(数値)が使用済みリストに入る。

・decrypt
フラグの暗号文と同じだと復号しない。
encryptで暗号化したものは復号しない。
それ以外は復号結果を表示する。

以下の方針で解く。

encryptでnを算出する。
decrypt側でLSB Decryption Oracle Attackで復号する。

import socket
import re
from fractions import Fraction
from Crypto.Util.number import long_to_bytes

def recvuntil(s, tail):
    data = ''
    while True:
        if tail in data:
            return data
        data += s.recv(1)

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

def lsb_oracle(s, enc):
    print '2'
    s.sendall('2\n')
    data = recvuntil(s, '> ')
    print data + enc
    s.sendall(enc + '\n')
    data = recvuntil(s, '\n').strip()
    data += recvuntil(s, '\n').strip()
    print data
    if 'Ho, ho, no...' in data:
        dec = 0
    else:
        dec = data.split('Decrypted: ')[1]
    data = recvuntil(s, 'Exit\n').strip()
    print data

    return int(dec) % 2

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('95.179.163.167', 16001))

data = recvuntil(s, 'Exit\n').strip()
print data

#### get c ####
pattern = 'Galf - (.+)'
m = re.search(pattern, data)
c = int(m.group(1), 16)
print 'c =', c

#### calculate n ####
try_rsa_enc = []
for pt in [2, 4, 16]:
    print '1'
    s.sendall('1\n')
    data = recvuntil(s, '> ')
    print data + chr(pt)
    s.sendall(chr(pt) + '\n')
    data = recvuntil(s, '\n').strip()
    data += recvuntil(s, '\n').strip()
    print data
    enc = data.split('Encrypted: ')[1]
    try_rsa_enc.append(int(enc))
    data = recvuntil(s, 'Exit\n').strip()
    print data

diff1 = (try_rsa_enc[0]) ** 2 - try_rsa_enc[1]
diff2 = (try_rsa_enc[1]) ** 2 - try_rsa_enc[2]

n, _, _ = egcd(diff1, diff2)
e = 65537

for i in range(100, 1, -1):
    if n % i == 0:
        n /= i
        break

#### get flag ####
bounds = [0, Fraction(n)]

i = 0
while True:
    print 'Round %d' % (i+1)
    i += 1

    c2 = (c * pow(2, e, n)) % n
    lsb = lsb_oracle(s, str(c2))
    if lsb == 1:
        bounds[0] = sum(bounds)/2
    else:
        bounds[1] = sum(bounds)/2
    diff = bounds[1] - bounds[0]
    diff = diff.numerator / diff.denominator

    if diff == 0:
        m = bounds[1].numerator / bounds[1].denominator
        break
    c = c2

flag = long_to_bytes(m)
print flag

X-MAS{N1c3_bu7_chr1s7m4s_is_n0t_ab0u7_g1f7s_17_1s_ab0u7_fl4gs}

Xⁿ-Mas (Crypto)

最大49乗まで考慮し、xが0～49に対して、以下の値がいくつになるかを確認する。
a0 * x^49 + a1 * x^48 + ... + a48 * x + a49 (mod n)

49元方程式として行列にし、逆元から計算し、係数を求める。その係数がASCIIコードになっているので、文字にするとフラグになった。

# solve.sage
import socket

def recvuntil(s, tail):
    data = ''
    while True:
        if tail in data:
            return data
        data += s.recv(1)


s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('95.179.163.167', 16000))

data = recvuntil(s, 'luck!\n').strip()
print data
n = int(data.split('\n')[2].split(' ')[3][:-1])

coeff = []
for x in range(50):
    row = []
    for i in range(49, -1, -1):
        row.append(pow(x, i))
    coeff.append(row)

A = matrix(Zmod(n), coeff)

B = []
for x in range(50):
    data = recvuntil(s, 'integer:')
    print data + str(x)
    s.sendall(str(x) + '\n')
    data = recvuntil(s, '\n').strip()
    print data
    val = int(data.split(': ')[1])
    B.append(val)

X = A.inverse()

flag = ''
for row in range(50):
    sum = 0
    for col in range(50):
        sum += X[row][col] * B[col]
    if sum % n != 0:
        flag += chr(sum % n)

print flag

X-MAS{W3_w1sh_you_4_m3rry_Christmas}

Santa's lucky number (Web)

どこかのページにフラグが隠されているらしい。
0ページ目から順に確認していくスクリプトを作成し実行する。

import requests
import string

def check_hexstr(s):
    for c in s:
        if c not in string.hexdigits:
            return False
    return True

for p in range(10000):
    print p
    url = 'http://199.247.6.180:12005/?page=%d' % p
    r = requests.get(url)
    t = r.text
    m = t.rfind('">')
    if check_hexstr(t[m+3:-5]) == False:
        print(r.text)
        break

1327ページ目にフラグが書いてあった。

X-MAS{W00pS_S0m30n3_73l1_S4n7a_h1s_c00k1eS_Ar3_BuRn1ng}

BoJack Horseman's Sad Christmas (Misc / Forensics)

$ zsteg bojack.png 
b1,g,lsb,xy         .. file: JPEG image data, JFIF standard 1.01, resolution (DPI), density 300x300, segment length 16, baseline, precision 8, 182x268, frames 3
b1,g,msb,xy         .. text: ["\r" repeated 50 times]
b2,b,lsb,xy         .. text: "u}UUUWUWUWUW]"
b2,rgb,lsb,xy       .. file: AIX core file fulldump
b2,bgr,lsb,xy       .. file: AIX core file fulldump
b3,g,lsb,xy         .. text: "rG#nG#n8"
b4,r,lsb,xy         .. text: ["w" repeated 9 times]
b4,g,lsb,xy         .. text: "DDDDDDDKDDKD"
b4,g,msb,xy         .. text: "-\"\"\"\"\"\"\""

StegSolveのData Extractで、Blue 1のみチェックを入れて、保存する。保存したJPGファイルにフラグが書いてあった。

X-MAS{1_L0V3_B0J4ckH0rs3m4n}

Unown Gift (Misc / Crypto)

0xffをXORキーとして復号する。TrID にかけてみると GBA だと分かる。GBAのエミュレータでゲームを進める。

I see! You got yout first part.
n=0x919988e16d5192c24b43f1c7b5
1856b5e56789aa3fc0d3b820500dde
307e414b1dd3525e19340cbc895a34
b0cae3db

Hm! you got your second part.
It's one worth nothing.
e=0x9ed98456b3387cafe143978372
4eb683b2434c4cdf387a3267f84217
19e12fd1ccdb7fdca650afea6a42de
ebe21e1

Ah! A third part!
You shiould note it patiently.
c=0x3731a737c24e83be7ca2256ed8
c1794be4aab34947441b92407420d2
5c6ad5b4966ab3b6ae0afbf0a2be20
87e3cb

RSA暗号のパラメータを見つけた。eが非常に大きいので、Wiener's attackで復号する。

from fractions import Fraction

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

def decrypt(p, q, e, c):
    n = p * q
    phi = (p - 1) * (q - 1)
    gcd, a, b = egcd(e, phi)
    d = a
    pt = pow(c, d, n)
    return hex(pt)[2:-1].decode('hex')

def continued_fractions(n,e):
    cf = [0]
    while e != 0:
        cf.append(int(n/e))
        N = n
        n = e
        e = N%e
    return cf

def calcKD(cf):
    kd = list()
    for i in range(1,len(cf)+1):
        tmp = Fraction(0)
        for j in cf[1:i][::-1]:
            tmp = 1/(tmp+j)
        kd.append((tmp.numerator,tmp.denominator))
    return kd

def int_sqrt(n):
    def f(prev):
        while True:
            m = (prev + n/prev)/2
            if m >= prev:
                return prev
            prev = m
    return f(n)

def calcPQ(a,b):
    if a*a < 4*b or a < 0:
        return None
    c = int_sqrt(a*a-4*b)
    p = (a + c) /2
    q = (a - c) /2
    if p + q == a and p * q == b:
        return (p,q)
    else:
        return None

def wiener(n,e):
    kd = calcKD(continued_fractions(n,e))
    for (k,d) in kd:
        if k == 0:
            continue
        if (e*d-1) % k != 0:
            continue
        phin = (e*d-1) / k
        if phin >= n:
            continue
        ans = calcPQ(n-phin+1,n)
        if ans is None:
            continue
        return (ans[0],ans[1])

n = 0x919988e16d5192c24b43f1c7b51856b5e56789aa3fc0d3b820500dde307e414b1dd3525e19340cbc895a34b0cae3db
e = 0x9ed98456b3387cafe1439783724eb683b2434c4cdf387a3267f8421719e12fd1ccdb7fdca650afea6a42deebe21e1
c = 0x3731a737c24e83be7ca2256ed8c1794be4aab34947441b92407420d25c6ad5b4966ab3b6ae0afbf0a2be2087e3cb

p, q = wiener(n, e)

flag = decrypt(p, q, e, c)
print flag

X-MAS{Wh4t_4n_un3xp3ct3d_chr1stm45_pr3s3nt}