X-MAS CTF 2020 Writeup

Sat Dec 19 2020

12/11-12/18 に開催された X-MAS CTF に参加しました。長期開催でしたが、平日はほとんど着手できませんでした…結果としては 160/1409 でした。微妙… 例のごとく、備忘録のため解いた問題についての writeup を書きます。

!Sanity Check

フラグの形式を把握したり、 Discord へ参加したりしました。

Binary Exploitation

Cryptography

Santa's public key factory

RSA の問題。ある固定の message を、ランダムに生成した素数 $p, q$ (private key) を使って暗号化したものと、そのときの $n, e$ が返されます。ただ、素数 $p$ , $q$ が

0x80000000000000000000000000020000000000000000000040000000400040000000000000000000000000000400000000000200000000000000000000000000000000000000000000040000000000000000000000000100000000000000000000000040000000000000000000000000000000000000008000008000000003a7

のように一部の bit がたった値 (最大16bit) + $\alpha$ という形をしています。なので積で得られる $n$ もスパースな感じになります。

どこの bit が立つかは固定だが、立つかどうかはランダムなため、 255 回 $n$ を見ることでどの bit が立ちうるのかを統計的に推定することにします。

import binascii
from hashlib import sha256
from collections import Counter
from pwn import *
from Crypto.Util.number import long_to_bytes, inverse
from gmpy2 import next_prime


p = remote("challs.xmas.htsp.ro", 1000)
p.recvuntil("=")
check = p.recvline().strip().decode()
for i in range(10000000):
    tmp = sha256(long_to_bytes(i)).hexdigest()[-5:]
    if tmp == check:
        print("found")
        p.sendline(hex(i)[2:].rjust((len(hex(i)[2:]) + 1) // 2 * 2, "0"))
        break


# こからが本題

def find_sparse_one(n):
    s = bin(n)[2:]
    ans = []
    last_i = 31
    for i, c in enumerate(reversed(s)):
        if i < 31:
            continue
        if len(ans) > 0 and i - last_i < 13 and c == "1":
            ans[-1][1] = 1
            continue
        if c == "1":
            ans.append([i, 0])
            last_i = i
    return ans


enc_list = []
n_list = []
cnt0 = Counter()
cnt1 = Counter()
for i in range(255):
    print(i)
    p.recvuntil("3. exit\n")
    p.recvline()
    p.sendline("1")
    p.recvuntil("Here is the encrypted secret message: ")
    enc = int(p.recvline().strip()[:-1], 16)
    p.recvuntil("n: ")
    n = int(p.recvline().strip())
    e = 65537
    enc_list.append(enc)
    n_list.append(n)

    tmp = find_sparse_one(n)
    tmp0 = [t[0] for t in tmp if t[1] == 0 and t[0] < 1024]
    tmp1 = [t[0] for t in tmp if t[1] == 1 and t[0] < 1024]
    cnt0 += Counter(tmp0)
    cnt1 += Counter(tmp1)

# 最頻値の上位8は正解のビットを見つけられていると仮定し、総当り
idx = None
found_p = None
found_q = None
for i in range(2 ** 8):
    tmp = i
    index_of_one = []
    j = 0
    while tmp > 0:
        if tmp % 2 == 1:
            index_of_one.append(j)
        tmp //= 2
        j += 1
    res = 2 ** 1023
    for j in index_of_one:
        k = cnt1.most_common(16)[j][0]
        res += 2 ** k
    tmp_p = next_prime(res)
    for j, n in enumerate(n_list):
        if n % tmp_p == 0:
            q = n // tmp_p
            found_p = tmp_p
            found_q = q
            idx = j
            print(tmp_p, q)
assert idx is not None
enc = enc_list[idx]
n = n_list[idx]
phi = (found_p - 1) * (found_q - 1)
e = 65537
d = inverse(e, phi)
plaintext = long_to_bytes(pow(enc, d, n))
plaintext = binascii.hexlify(plaintext)
print(plaintext)
p.interactive()

X-MAS{M4yb3_50m3__m0re_r4nd0mn3s5_w0u1d_b3_n1ce_eb0b0506}

Help a Santa helper?

ハッシュを衝突させる問題。

入力を $M$ として、 $M$ をブロックごとに区切ったものを $m_0, m_1, ... m_n$ とします。すると hash の計算は、

\begin{aligned} hash_0 &= 0 \\ hash_{i+1} &= m_{i} \oplus enc(hash_{i} \oplus m_{i}) \end{aligned}

と表されます。ここで enc は AES の encrypt 関数を意味します。 $hash_{n+1}$ が最終的な hash です。

最初に一回だけ好きな数を hash 化できます。これを試しに0としてみましょう。すると、

hash_1 = enc(0)

が返ってきます。

2ブロックの入力を考え、 $m_0 = 0$ のとき、 $m_1$ によって hash はどうなるかを見てみます。

hash_2 = m_1 \oplus enc(enc(0) \oplus m_1)

ここで、 $m_1 = enc(0)$ としてあげると $hash_2 = 0$ となります。

hash の方法が再帰的なことを考えると、 $m_2 = m_0 = 0$ , $m_3 = m_1 = enc(0)$ とすることで、 $hash_4 = 0$ になることがわかります。なので2入力を 0|enc(0) と 0|enc(0)|0|enc(0) にしてあげると hash が衝突します。

from hashlib import sha256
from pwn import *
from Crypto.Util.number import long_to_bytes


p = remote("challs.xmas.htsp.ro", 1004)
p.recvuntil("=")
check = p.recvline().strip().decode()
for i in range(10000000):
    tmp = sha256(long_to_bytes(i)).hexdigest()[-5:]
    if tmp == check:
        print("found")
        p.sendline(hex(i)[2:].rjust((len(hex(i)[2:]) + 1) // 2 * 2, "0"))
        break

p.sendlineafter("1. hash a message\n2. provide a collision\n3. exit\n\n", "1")
p.sendlineafter("Give me a message.\n", "00" * 16)
p.recvuntil("Here is your hash: b'")
e = p.recvline().strip()[:-2].decode()

p.sendlineafter("1. hash a message\n2. provide a collision\n3. exit\n\n", "2")
p.sendlineafter("Give me a message.\n", "00" * 16 + e)
p.sendlineafter("Give me a message.\n", ("00" * 16 + e) * 2)

p.interactive()

X-MAS{C0l1i5ion_4t7ack5_4r3_c0o1!_4ls0_ch3ck_0u7_NSUCRYPTO_fda233}

Forensics

Conversation

strings を叩いたら JP1ADIA7DJ5hLI9zpz9gK21upzgyqTyhM19bLKAsLI9hMKqsLz95MaWcMJ5xYJEuBQR3LmpkZwx5ZGL3AGS9Pt== という怪しげな文字列が出てきたので、 base64 decode してみますが、よくわからず… wireshark で開いてこの文字列を検索すると、会話が見れました。

Hello there, yakuhito
Hello, John! Nice to hear from you again. It's been a while.
I'm sorry about that... the folks at my company restrict our access to chat apps.
Do you have it?
Have what?
The thing.
Oh, sure. Here it comes:
JP1ADIA7DJ5hLI9zpz9gK21upzgyqTyhM19bLKAsLI9hMKqsLz95MaWcMJ5xYJEuBQR3LmpkZwx5ZGL3AGS9Pt==
Doesn't look like the thing
A guy like you should know what to do with it.
May I get a hint? :)
rot13
Got it. Thanks.

なるほど rot13 か。

X-MAS{Anna_from_marketing_has_a_new_boyfriend-da817c7129916751}

Misc

Complaint

よくわからなかったので適当なコマンドをいろいろ試した。

>&1 や >&2
- 特に何もなし
;echo a
- 空白行が表示される。よくわからない
;echo a;echo b
- a と表示される
- echo (入力値) >/dev/null みたいになっている？
;ls;ls
- ls の結果が表示される。 flag.txt が存在している
;cat flag.txt;echo a
- sh: 1: cat: not found
;tee <flag.txt;ls
- フラグ表示

X-MAS{h3ll0_k4r3n-8819d787dd38a397}

PMB

4回利率の計算をして金額が増えるが、途中で何かしらのロジックで0になってしまいます。入力は any number とのことなので、試しに -99 を入れたところ特にエラーが起きることなく動いた。しかし2回目で0になってしまいました。

そもそも絶対値のことを abs でなく modulus と呼んでいることに違和感を覚え、試しに虚数をいれたらそれでも動きました。 99j を入力することでフラグが得られました。

X-MAS{th4t_1s_4n_1nt3r3st1ng_1nt3r3st_r4t3-0116c512b7615456}

Bobi's Whacked

問題となるコードやホスト名なども存在せず、何をするかわからなかったため、問題名でググりました。 youtube チャンネルを見つけました。 HackTheBox の解法を紹介しているっぽい？です。

それはそれとして、まず字幕のついた動画が2つあったので、文字起こしを見てみると、

X-MAS{nice_thisisjustthefirstpart

_congrats}

の2つが見つかりました。しかしこれらを結合させてもフラグにならず…

チャンネルの概要を見てみると 6D6964646C6570617274 という文字列があり、これを文字に変換すると middlepart となりました。 3つを組み合わせたものがフラグとなりました。 (ちょっとこの問題は不親切だと思う)

X-MAS{nice_thisisjustthefirstpartmiddlepart_congrats}

Whisper of Ascalon

よくわからない文字を読む問題。問題文中の単語をググると、この文字は GW2 というゲーム？に関連していそうということがわかりました。さらに調べると、アルファベットとの対応関係を見つけました。 https://www.pinterest.jp/pin/75505731229136004/

これをもとに文字を読むと、フラグが得られました。

GW2MYFAVORITEGAME

Programming

Biggest Lowest

与えられた配列をソートして、小さい方から k1 個、大きい方から k2 個出力するだけです。

import time
from pwn import *

now = time.time()
p = remote("challs.xmas.htsp.ro", 6051)
for i in range(50):
    print(i, time.time() - now)
    p.recvuntil("array = ")
    array = eval(p.recvline())
    p.recvuntil("k1 = ")
    k1 = int(p.recvline())
    p.recvuntil("k2 = ")
    k2 = int(p.recvline())
    array.sort()
    ans = str(array[:k1])[1:-1] + "; " + str(array[-k2:][::-1])[1:-1]
    p.sendline(ans)
print(p.recvall())

X-MAS{th15_i5_4_h34p_pr0bl3m_bu7_17'5_n0t_4_pwn_ch41l}

Least Greatest

gcd と lcm が与えられたときに、それを満たす $(x, y)$ の組がいくつあるかを答える問題。

$x, y$ の gcd, lcm をそれぞれ $g, l$ とすると、 $gx_0 = x, gy_0 = y$ ( $x_0, y_0$ は互いに素) という $x_0, y_0$ が存在します。 $gl = xy$ より、 $l/g = x_0 y_0$ ということがわかります。

なのでこの問題を言い換えると、 $g, l$ が与えられたときに、 $l/g = x_0 y_0$ となる互いに素な $x_0, y_0$ はいくつあるか、ということになります。この問題に出てくる範囲では、 $l/g$ の値は factor で素因数分解可能でした。

$n = l/g$ として、 $n = p_1^{c_1} p_2^{c_2} \cdots p_m^{c_m}$ と素因数分解されたとき、 $n = x_0 y_0$ となる互いに素な $x_0, y_0$ は $2^m$ 個ということが示せます。これは素因数 $p_1, p_2, \cdots, p_m$ を $x_0, y_0$ のどちらかに配分していくことを考えたときに、それぞれの素因数はどちらか片方に全部配分する必要があるからです ( $\because$ $x_0, y_0$ は互いに素)。

import time
from collections import Counter
from itertools import product
import subprocess
import math
from pwn import *

now = time.time()
context.log_level = "DEBUG"
p = remote("challs.xmas.htsp.ro", 6050)

p.recvuntil("1/100")
for i in range(100):
    print(i, time.time() - now)
    p.recvuntil("gcd(x, y) = ")
    g = int(p.recvline().strip())
    p.recvuntil("lcm(x, y) = ")
    l = int(p.recvline().strip())
    assert l % g == 0
    num = l // g
    print(num)
    cmd = f"factor {num}"
    proc = subprocess.run(cmd.split(), stdout=subprocess.PIPE)
    factor = Counter(map(int, proc.stdout.split()[1:]))
    print(factor)

    ans = 2 ** len(factor)
    p.sendline(str(ans))
print(p.recvall())

(それにしても gcd などの大きさの制約が与えられないので解きづらかった…)

X-MAS{gr347es7_c0mm0n_d1v1s0r_4nd_l345t_c0mmon_mult1pl3_4r3_1n73rc0nn3ct3d}

Web Exploitation

PHP Master

<?php

include('flag.php');

$p1 = $_GET['param1'];
$p2 = $_GET['param2'];

if(!isset($p1) || !isset($p2)) {
    highlight_file(__FILE__);
    die();
}

if(strpos($p1, 'e') === false && strpos($p2, 'e') === false  && strlen($p1) === strlen($p2) && $p1 !== $p2 && $p1[0] != '0' && $p1 == $p2) {
    die($flag);
}

?>

つまり、

strpos($p1, 'e') === false && strpos($p2, 'e') === false  && strlen($p1) === strlen($p2) && $p1 !== $p2 && $p1[0] != '0' && $p1 == $p2

を満たす p1, p2 を見つけろ、という問題のようです。

最後の $p1 == $p2 が暗黙な型変換をされることを利用したいです。

p1=4.
p2=04

で通すことができました。

X-MAS{s0_php_m4ny_skillz-69acb43810ed4c42}

Santa's consolation

console.log("%c██████╗░██╗░░░░░██╗░░░██╗██╗░░░██╗██╗░░██╗\n\██╔══██╗██║░░░░░██║░░░██║██║░░░██║██║░██╔╝\n██████╦╝██║░░░░░██║░░░██║██║░░░██║█████═╝░\n██╔══██╗██║░░░░░██║░░░██║██║░░░██║██╔═██╗░\n██████╦╝███████╗╚██████╔╝╚██████╔╝██║░╚██╗\n╚═════╝░╚══════╝░╚═════╝░░╚═════╝░╚═╝░░╚═╝\n","color: #5cdb95");console.log("🐢 Javascript Challenge 🐢");console.log("Call win(<string>) with the correct parameter to get the flag");console.log("And don't forget to subscribe to our newsletter :D");
function check(s) {const k="MkVUTThoak44TlROOGR6TThaak44TlROOGR6TThWRE14d0hPMnczTTF3M056d25OMnczTTF3M056d1hPNXdITzJ3M00xdzNOenduTjJ3M00xdzNOendYTndFRGY0WURmelVEZjNNRGYyWURmelVEZjNNRGYwRVRNOGhqTjhOVE44ZHpNOFpqTjhOVE44ZHpNOEZETXh3SE8ydzNNMXczTnp3bk4ydzNNMXczTnp3bk13RURmNFlEZnpVRGYzTURmMllEZnpVRGYzTURmeUlUTThoak44TlROOGR6TThaak44TlROOGR6TThCVE14d0hPMnczTTF3M056d25OMnczTTF3M056dzNOeEVEZjRZRGZ6VURmM01EZjJZRGZ6VURmM01EZjFBVE04aGpOOE5UTjhkek04WmpOOE5UTjhkek04bFRPOGhqTjhOVE44ZHpNOFpqTjhOVE44ZHpNOGRUTzhoak44TlROOGR6TThaak44TlROOGR6TThSVE14d0hPMnczTTF3M056d25OMnczTTF3M056d1hPNXdITzJ3M00xdzNOenduTjJ3M00xdzNOenduTXlFRGY0WURmelVEZjNNRGYyWURmelVEZjNNRGYzRVRNOGhqTjhOVE44ZHpNOFpqTjhOVE44ZHpNOGhETjhoak44TlROOGR6TThaak44TlROOGR6TThGak14d0hPMnczTTF3M056d25OMnczTTF3M056d25NeUVEZjRZRGZ6VURmM01EZjJZRGZ6VURmM01EZjFFVE04aGpOOE5UTjhkek04WmpOOE5UTjhkek04RkRNeHdITzJ3M00xdzNOenduTjJ3M00xdzNOendITndFRGY0WURmelVEZjNNRGYyWURmelVEZjNNRGYxRVRNOGhqTjhOVE44ZHpNOFpqTjhOVE44ZHpNOFZETXh3SE8ydzNNMXczTnp3bk4ydzNNMXczTnp3WE94RURmNFlEZnpVRGYzTURmMllEZnpVRGYzTURmeUlUTThoak44TlROOGR6TThaak44TlROOGR6TThkVE84aGpOOE5UTjhkek04WmpOOE5UTjhkek04WlRNeHdITzJ3M00xdzNOenduTjJ3M00xdzNOendITXhFRGY0WURmelVEZjNNRGYyWURmelVEZjNNRGYza0RmNFlEZnpVRGYzTURmMllEZnpVRGYzTURmMUVUTTAwMDBERVRDQURFUg==";const k1=atob(k).split('').reverse().join('');return bobify(s)===k1;}
function bobify(s) {if (~s.indexOf('a') || ~s.indexOf('t') || ~s.indexOf('e') || ~s.indexOf('i') || ~s.indexOf('z')) return "[REDACTED]";const s1 = s.replace(/4/g, 'a').replace(/3/g, 'e').replace(/1/g, 'i').replace(/7/g, 't').replace(/_/g, 'z').split('').join('[]'); const s2 = encodeURI(s1).split('').map(c => c.charCodeAt(0)).join('|');const s3 = btoa("D@\xc0\t1\x03\xd3M4" + s2);return s3;}
function win(x){return check(x) ? "X-MAS{"+x+"}" : "[REDACTED]";}

というコードが走っています。これを実行してみると、

Call win(<string>) with the correct parameter to get the flag

と言われます。

check 関数を見ると、

k1 = "REDACTED0000MTE1fDM3fDUzfDY2fDM3fDUzfDY4fDk3fDM3fDUzfDY2fDM3fDUzfDY4fDExMHwzN3w1M3w2NnwzN3w1M3w2OHwxMTZ8Mzd8NTN8NjZ8Mzd8NTN8Njh8OTd8Mzd8NTN8NjZ8Mzd8NTN8Njh8MTIyfDM3fDUzfDY2fDM3fDUzfDY4fDExOXwzN3w1M3w2NnwzN3w1M3w2OHwxMDV8Mzd8NTN8NjZ8Mzd8NTN8Njh8MTE1fDM3fDUzfDY2fDM3fDUzfDY4fDEwNHwzN3w1M3w2NnwzN3w1M3w2OHwxMDF8Mzd8NTN8NjZ8Mzd8NTN8Njh8MTE1fDM3fDUzfDY2fDM3fDUzfDY4fDEyMnwzN3w1M3w2NnwzN3w1M3w2OHwxMjF8Mzd8NTN8NjZ8Mzd8NTN8Njh8NDh8Mzd8NTN8NjZ8Mzd8NTN8Njh8MTE3fDM3fDUzfDY2fDM3fDUzfDY4fDEyMnwzN3w1M3w2NnwzN3w1M3w2OHw5OXwzN3w1M3w2NnwzN3w1M3w2OHwxMTR8Mzd8NTN8NjZ8Mzd8NTN8Njh8OTd8Mzd8NTN8NjZ8Mzd8NTN8Njh8OTl8Mzd8NTN8NjZ8Mzd8NTN8Njh8MTA1fDM3fDUzfDY2fDM3fDUzfDY4fDExN3wzN3w1M3w2NnwzN3w1M3w2OHwxMTB8Mzd8NTN8NjZ8Mzd8NTN8Njh8MTIyfDM3fDUzfDY2fDM3fDUzfDY4fDEwMnwzN3w1M3w2NnwzN3w1M3w2OHwxMDF8Mzd8NTN8NjZ8Mzd8NTN8Njh8MTE0fDM3fDUzfDY2fDM3fDUzfDY4fDEwNXwzN3w1M3w2NnwzN3w1M3w2OHw5OXwzN3w1M3w2NnwzN3w1M3w2OHwxMDV8Mzd8NTN8NjZ8Mzd8NTN8Njh8MTE2"

と bobify(s) を比較しています。

bobify 関数は、4, 3, 1, 7, _ をそれぞれ a, e, i, t, z に変換したあと、 URI encode などの処理をして、 D@\xc0\t1\x03\xd3M4 という文字列を先頭につけた後に btoa しています。 k1 をもう一度 atob してみますと、

"D@À	1ÓM4115|37|53|66|37|53|68|97|37|53|66|37|53|68|110|37|53|66|37|53|68|116|37|53|66|37|53|68|97|37|53|66|37|53|68|122|37|53|66|37|53|68|119|37|53|66|37|53|68|105|37|53|66|37|53|68|115|37|53|66|37|53|68|104|37|53|66|37|53|68|101|37|53|66|37|53|68|115|37|53|66|37|53|68|122|37|53|66|37|53|68|121|37|53|66|37|53|68|48|37|53|66|37|53|68|117|37|53|66|37|53|68|122|37|53|66|37|53|68|99|37|53|66|37|53|68|114|37|53|66|37|53|68|97|37|53|66|37|53|68|99|37|53|66|37|53|68|105|37|53|66|37|53|68|117|37|53|66|37|53|68|110|37|53|66|37|53|68|122|37|53|66|37|53|68|102|37|53|66|37|53|68|101|37|53|66|37|53|68|114|37|53|66|37|53|68|105|37|53|66|37|53|68|99|37|53|66|37|53|68|105|37|53|66|37|53|68|116"

となっていることがわかり、あとはこの | で区切られた数字を文字に変換してあげればいいだけです (最後のa→4等の変換を忘れずに)。

s = "115|37|53|66|37|53|68|97|37|53|66|37|53|68|110|37|53|66|37|53|68|116|37|53|66|37|53|68|97|37|53|66|37|53|68|122|37|53|66|37|53|68|119|37|53|66|37|53|68|105|37|53|66|37|53|68|115|37|53|66|37|53|68|104|37|53|66|37|53|68|101|37|53|66|37|53|68|115|37|53|66|37|53|68|122|37|53|66|37|53|68|121|37|53|66|37|53|68|48|37|53|66|37|53|68|117|37|53|66|37|53|68|122|37|53|66|37|53|68|99|37|53|66|37|53|68|114|37|53|66|37|53|68|97|37|53|66|37|53|68|99|37|53|66|37|53|68|105|37|53|66|37|53|68|117|37|53|66|37|53|68|110|37|53|66|37|53|68|122|37|53|66|37|53|68|102|37|53|66|37|53|68|101|37|53|66|37|53|68|114|37|53|66|37|53|68|105|37|53|66|37|53|68|99|37|53|66|37|53|68|105|37|53|66|37|53|68|116"
tmp = "".join(list(map(lambda x: chr(int(x)), s.split("|"))))
tmp = tmp.replace("%5B%5D", "")
tmp = tmp.replace("a", "4")
tmp = tmp.replace("e", "3")
tmp = tmp.replace("i", "1")
tmp = tmp.replace("t", "7")
tmp = tmp.replace("z", "_")
print(tmp)

X-MAS{s4n74_w1sh3s_y0u_cr4c1un_f3r1c17}