Attack All Around

今やCTFと競プロばかりだが、トビタテ生のアメリカ留学やTOEFL奮闘記

TFC CTF 2022 crypto writeup

皆さんご無沙汰しております。


前回writeupを書いたのが去年というのに驚いており、つまり今年初めてのwriteupとなっております。あけましておめでとうございます(?)

本題に入る前にこの7ヶ月間についてざっとお話ししたいと思いますが、解法を早く見たい方はスルーしてください(笑)


本当にざっとという感じになるのですが、なんだかんだ研究活動に勤しんでいました。加えてボウリングの方にも力を注いでいたため、土日にCTFをやる気力がなかったです…。3,4月は体調を崩しやすく(発熱してコロナかと思ったのに違ったのが2回)、研究への不安から身体面でも精神面でも余裕がなかった時期でした。

年内で大学でのCTF勉強会は一回区切りがつくこともありCTFから少し離れていたのですが、4月から新入生などの初心者勉強会や通常勉強会が始まり、問題集めのためちょっとずつ問題を解いていました。学会参加や修論発表が7月にあったのでそんなには取り組んでいませんでしたが、9月の卒業まで頑張っていこうと思います。



ちょっとした前説がありましたが、本題に入ります!


Official URL : https://ctf.thefewchosen.com/




warmup

OBSCURE

問題文をよく見ると奥の方にうっすらflagが…。

これどう設定しているんだろう

TFCCTF{s3cur1ty_thr0ugh_0bscur1ty}



BASIC

This guy keeps insulting my girlfriend! His last message confused me, though! Can you help me decode it?
/Rn/X7n#bUc.rjzh,|eEsg,?&QI;@^ARm}UKOkICi#X.ixEmN]D

何の暗号文か分からなかったので、cipher identifierを使ってbase91 encodeだと突き止めました。

Decrypt a Message - Cipher Identifier - Online Code Recognizer

あとはCyberChefやdcodeなど使ってdecodeです。

TFCCTF{sh3's_4_10..._but_0n_th3_ph_sc4l3}



MAFIOSO

A soldier was walking around the streets of Sicily, late at night, with THE Consigliere. Same soldier, the very next day, found in a ditch with a note in his breast pocket. It read:
f433c3e883a1389482c0b652660580f36ea037434fd4a67d193bc1cdc9b2cc34
Flag format: TFCCTF{secret_message}

この数値はなんだろう…。XORぽいが、だとするとflag formatからkeyのようなものを出しても、規則性は無い。"Consigliere", "Sicily" に関係する暗号も無い。

なんかあるかなと先ほどのcipher identifierを使ってみると、SHA-256の可能性があるとのこと。なるほど、数値の大きさをまず調べなかったのは反省。

ハッシュ値から元の値を特定するオンラインツールはいくつかありますが、中でもCrackStationは強い!

CrackStation - Online Password Hash Cracking - MD5, SHA1, Linux, Rainbow Tables, etc.

ここに投げて、出てきた文字列をTFCCTF{}で括って終わりです。この作業があるからflag formatをわざわざ出していたんですね。

TFCCTF{snitchesgetstitches}



easy

EXCLUSIVE ORACLE

"Hey! Let's keep all of our secrets together, in the same place!" "That's awesome, you're so friendly!"
Narrator: He wasn't friendly...

この問題が一番時間がかかりました…。easyと言えばそうかもしれませんが、エスパー要素が強め…?

今回のCTFは、ncする問題はCONTAINERを動かすよう指示する必要があり、その度にnc先が変わってしまいます。加えて、この問題ではnc先のサーバプログラムは公開していません。

とりあえずncしてみると、以下のようにdataを送ることができ、何かしらの暗号文が得られます。

サーバとのやり取り

何回かncして分かったこととして、

  • 返ってくるバイト列の長さは、40+len(送ったdata)

  • ただし、len(送ったdata)が40を越えると、一律で長さ80となる

の二つだけです。

なんか40がくさいなということで、flagの長さだと予想します。

次に問題名よりXORを使うだろうということで、flagとkeyのXORが暗号文の最初40バイトと予想(←この仮定に至るまでかなり時間がかかった)。そして、暗号文の残りは自分の送ったdataも同じkeyでXORしているはず。keyの長さも40だとして、使いまわしているだろう。

data = 'a'×40として送り、暗号文後半40バイトとXORすることによりkeyを導出し、keyと暗号文前半40バイトとXORするとflagとなりました!


この問題のサーバを公開すればエスパー要素は無くなるけど、その分難易度がぐっと下がってしまう…。作問は難しいですね。

TFCCTF{wh4t's_th3_w0rld_w1th0u7_3n1gm4?}



medium

TRAIN TO PADDINGTON

The train to Paddington is leaving soon! Will you be able to find your ticket ID in time? Why did you encrypt it without storing the password...?
添付ファイル:main.py, output.txt

#main.py
import os

BLOCK_SIZE = 16
FLAG = b'|||REDACTED|||'


def pad_pt(pt):
    amount_padding = 16 if (16 - len(pt) % 16) == 0 else 16 - len(pt) % 16
    return pt + (b'\x3f' * amount_padding)


pt = pad_pt(FLAG)
key = os.urandom(BLOCK_SIZE)

ct = b''

j = 0
for i in range(len(pt)):
    ct += (key[j] ^ pt[i]).to_bytes(1, 'big')
    j += 1
    j %= 16

with open('output.txt', 'w') as f:
    f.write(ct.hex())
b4b55c3ee34fac488ebeda573ab1f974bf9b2b0ee865e45a92d2f14b7bdabb6ed4872e4dd974e803d9b2ba1c77baf725

長さ16のkeyを使いまわして、flagをpaddingしたものとXORしています。ここでのpaddingはb"\x3f" = b"?"を後ろに追加して16の倍数長になるようにしています。

flag formatから先頭7バイトが b"TFCCTF{" であることと、最後x(x : 1~16)バイトが b"}" + b"?"×(x-1) であることが分かります。ここからkeyをできるだけ特定していきます。xをbrute forceしてflagを一番復元できているものを見てみます。

#solver.py
enc = "b4b55c3ee34fac488ebeda573ab1f974bf9b2b0ee865e45a92d2f14b7bdabb6ed4872e4dd974e803d9b2ba1c77baf725"
key = [-1 for i in range(16)]
flag_st = "TFCCTF{"
for i in range(len(flag_st)):
    key[i] = ord(flag_st[i])^int(enc[i*2:(i+1)*2],16)

for padlen in range(1,16):
    flag_ed = "}" + "?"*padlen
    tenc = enc[-32:]
    for j in range(16-len(flag_ed),16):
        key[j] = ord(flag_ed[j-16+len(flag_ed)])^int(tenc[j*2:(j+1)*2],16)
    print(f"pad length : {padlen}, ",end="")
    for i in range(len(enc)//2):
        if key[i%16] == -1: print("*",end="")
        else:
            c = key[i%16]^int(enc[i*2:(i+1)*2],16)
            print(chr(c),end="")
    print()
$ python3 solver.py 
pad length : 1, TFCCTF{*******sn_h4s_l3*******1t4t10n}?*******}?
pad length : 2, TFCCTF{******v1n_h4s_l3******st4t10n}?******}??
pad length : 3, TFCCTF{*****041n_h4s_l3*****q_st4t10n}?*****}???
pad length : 4, TFCCTF{****6r41n_h4s_l3*****3_st4t10n}?****}????
pad length : 5, TFCCTF{***tr41n_h4s_l3***6h3_st4t10n}?***}?????
pad length : 6, TFCCTF{**q_tr41n_h4s_l3**th3_st4t10n}?**}??????
pad length : 7, TFCCTF{**3_tr41n_h4s_l3*6_th3_st4t10n}?*}???????
pad length : 8, TFCCTF{6h3_tr41n_h4s_l3$t_th3_st4t10n}?}????????
pad length : 9, TFCCTF9th3_tr41n_h4s_lqft_th3_st4t10n}}?????????
pad length : 10, TFCCTF{th3_tr41n_h4s_l3ft_th3_st4t10n}??????????
pad length : 11, TFCCG{th3_tr41n_h4sL.3ft_th3_st4t10}???????????
pad length : 12, TFC{th3_tr41n_h4>.3ft_th3_st4t1}????????????
pad length : 13, TFL{th3_tr41n_hx|.3ft_th3_st4t}?????????????
pad length : 14, TOML{th3_tr41n_a:|.3ft_th3_st4}??????????????

keyが全て復元できておらずXORできないものは"*"で表現しています。

ここから、flagが意味ある文章になるように特定できていないものをごちゃごちゃ頑張っていくのかなと思ったら、paddingの長さが10の時に完全復元できていました。

TFCCTF{th3_tr41n_h4s_l3ft_th3_st4t10n}



hard

ADMIN PANEL

This admin panel has been bugging me for days! It even lets me change the password and I can't log in!
添付ファイル:main.py

#main.py
import os
import random

from Crypto.Cipher import AES

KEY = os.urandom(16)
PASSWORD = os.urandom(16)
FLAG = os.getenv('FLAG')

menu = """========================
1. Access Flag
2. Change Password
========================"""


def xor(byte, bytes_second):
    d = b''
    for i in range(len(bytes_second)):
        d += bytes([byte ^ bytes_second[i]])
    return d


def decrypt(ciphertext):
    iv = ciphertext[:16]
    ct = ciphertext[16:]
    cipher = AES.new(KEY, AES.MODE_ECB)
    pt = b''
    state = iv
    for i in range(len(ct)):
        b = cipher.encrypt(state)[0]
        c = b ^ ct[i]
        pt += bytes([c])
        state = state[1:] + bytes([ct[i]])
    return pt


if __name__ == "__main__":
    while True:
        print(menu)
        option = int(input("> "))
        if option == 1:
            password = bytes.fromhex(input("Password > "))
            if password == PASSWORD:
                print(FLAG)
                exit(0)
            else:
                print("Wrong password!")
                continue
        elif option == 2:
            token = input("Token > ")
            if len(token) != 64:
                print("Wrong length!")
                continue
            hex_token = bytes.fromhex(token)
            r_byte = random.randbytes(1)
            print(f"XORing with: {r_byte.hex()}")
            xorred = xor(r_byte[0], hex_token)
            PASSWORD = decrypt(xorred)

まずmain.pyの挙動についてです。

1. Access Flag

入力した16進数をbytes型に変換し、それがPASSWORDと一致していたらflagを貰えます。何回でも実行可能です。


2. Change Password

長さ64となる16進数値を送り、bytes型に変換したものをtokenとします。サーバはそこから1byteの乱数値r_byteを生成&公開し、tokenの1byteごとr_byteでXORしていきます。その値をdecrypt関数に引数として渡し、その返り値をPASSWORDに置き換えます。

次にdecrypt関数についてです。引数として渡されるのは16進数で長さ64、つまり32バイトのものです。その前半16バイトをiv, 後半16バイトをctとします。

まずstate = ivとし、stateをAESのECBモードで暗号化した先頭1バイトをbとします。bとct[i]をXORしたものをptに追加します。そして、stateを先頭1バイトを取り除いたものとct[i]をつなげたものに更新します。ctの長さが16であることから、これを16回行った後のptを返します。

こちらも1. と同様、何回でも実行可能です。


つまりptは、[ivをAES暗号化した先頭1バイトとct[0]をXORしたもの] + [iv[1:]+ct[:1]をAES暗号化した先頭1バイトとct[1]をXORしたもの] + ... + [iv[15:]+ct[:15]をAES暗号化した先頭1バイトとct[15]をXORしたもの] となります。

KEYは分かる要素無いのに、どうやってAESで暗号化したものを特定するのか…。絶対無理やろ…。

ivとctが全部同じ1バイトで構成されていたら(ex. 464646...46)、stateをAES暗号化した先頭1バイトもct[i]もそれらをXORしたものも、この3つは必ず同じ値になります。つまり、ptは16進数で7b7b7b...7bというような形となります。送るtokenは1バイトごとr_byteでXORするので、全て同じ1バイトで構成すればこのようになります。

tokenをどのように設定してもptを完全に予測することはできませんが、上のようにすることでptを256通り("00"~"ff"×16)にまで絞ることができます。あとは、1. Access Flag で256通り全て試します(何回でも1. ができるのもミソ)。

#solver.py
from Crypto.Util.number import *
import socket

# --- common funcs ---
def sock(remoteip, remoteport):
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect((remoteip, remoteport))
    return s, s.makefile('rw')

def read_until(f, delim='\n'):
    data = ''
    while not data.endswith(delim):
        data += f.read(1)
    return data

    
#HOSTはIPアドレスでも可
HOST, PORT = "01.linux.challenges.ctf.thefewchosen.com", 59490
s, f = sock(HOST, PORT)
for _ in range(4): read_until(f)
read_until(f,"> ")
s.send(b"2\n")
read_until(f,"Token > ")
s.send(b"35"*32+b"\n")
read_until(f)

for i in range(256):
    for _ in range(4): read_until(f)
    read_until(f,"> ")
    s.send(b"1\n")
    read_until(f,"Password > ")
    ans = hex(i)[2:]
    if len(ans) == 1: ans = "0"+ans
    s.send(ans.encode()*16+b"\n")
    flag = read_until(f).strip()
    print(i,flag)
    if "TFCCTF" in flag: break

TFCCTF{l0g0n_z3r0_w1th_3xtr4_st3ps!}



insane

ADMIN PANEL BUT HARDER (AND FIXED)

"This admin panel has been bugging me for days! It even lets me change the password and I can't log in!" But harder
添付ファイル:main.py

#main.py
import os
import random

from Crypto.Cipher import AES

KEY = os.urandom(16)
PASSWORD = os.urandom(16)
FLAG = os.getenv('FLAG')

menu = """========================
1. Access Flag
2. Change Password
========================"""


def xor(bytes_first, bytes_second):
    d = b''
    for i in range(len(bytes_second)):
        d += bytes([bytes_first[i] ^ bytes_second[i]])
    return d


def decrypt(ciphertext):
    iv = ciphertext[:16]
    ct = ciphertext[16:]
    cipher = AES.new(KEY, AES.MODE_ECB)
    pt = b''
    state = iv
    for i in range(len(ct)):
        b = cipher.encrypt(state)[0]
        c = b ^ ct[i]
        pt += bytes([c])
        state = state[1:] + bytes([ct[i]])
    return pt


if __name__ == "__main__":
    while True:
        print(menu)
        option = int(input("> "))
        if option == 1:
            password = bytes.fromhex(input("Password > "))
            if password == PASSWORD:
                print(FLAG)
                exit(0)
            else:
                print("Wrong password!")
                continue
        elif option == 2:
            token = input("Token > ")
            if len(token) != 64:
                print("Wrong length!")
                continue
            hex_token = bytes.fromhex(token)
            r_bytes = random.randbytes(32)
            print(f"XORing with: {r_bytes.hex()}")
            xorred = xor(r_bytes, hex_token)
            PASSWORD = decrypt(xorred)

先ほどのADMIN PANELの改良版ということで、サーバが生成する1バイトの乱数r_byteが、32バイトの乱数r_bytesと変更されています。同じようにやっても、全て同じバイトで構成されていないバイト列をdecrypt関数に送ることになり、ptを256通りに絞ることができません。


だったら、r_bytesを予想すればいいじゃないか!!!

r_bytesはrandom.randbytes()を利用しているので、その仕様を確認します。

def randbytes(self, n):
    """Generate n random bytes."""
    return self.getrandbits(n * 8).to_bytes(n, 'little')

random.randbytes()はrandom.getrandbits()で得た数値をlittle endianでバイト列に変換し返します。

kurenaifさんがSECCON Beginners CTF 2022 "Unpredictable Pad" についての解法を掲載してくださっているので、そちらを参考にさせていただきました。

www.youtube.com

簡単に言うと、random.getrandbits()はメルセンヌ・ツイスターを利用しています。メルセンヌ・ツイスター連続した624個の32ビット数値を得られるとその後の数値が予測できます。連続した312個の64ビット数値でも、[2個目の32ビット]+[1個目の32ビット] とすることで同様に予測できます。


kurenaifさんの解法より、randcrackを利用します。

GitHub - tna0y/Python-random-module-cracker: Predict python's random module generated values.

ここで、random.randbytes()はlittle endianで変換していることに注意します。kurenaifさんはおそらくbig endianの数値をrandcrackに投げているので、一度little endianからbig endianに戻します。そして、randcrackが予想した値をlittle endianに変換して、それを使って全て同じバイトで構成されているバイト列になるようtokenを調整すれば、後はADMIN PANELと同じです。

ADMIN PANEL BUT HARDER AND FIXEDも同じ解法です。

#solver.py
from Crypto.Util.number import *
import socket
from randcrack import RandCrack


# --- common funcs ---
def sock(remoteip, remoteport):
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect((remoteip, remoteport))
    return s, s.makefile('rw')

def read_until(f, delim='\n'):
    data = ''
    while not data.endswith(delim):
        data += f.read(1)
    return data

    
#HOSTはIPアドレスでも可
HOST, PORT = "01.linux.challenges.ctf.thefewchosen.com", 60051
s, f = sock(HOST, PORT)
rc = RandCrack()

for i in range(624//8):
    print(f"i = {i}")
    for _ in range(4): read_until(f)
    read_until(f,"> ")
    s.send(b"2\n")
    read_until(f,"Token > ")
    s.send(b"35"*32+b"\n")
    ret = read_until(f).strip()
    ret = ret.split(": ")[1]
    rb = int.from_bytes(bytes.fromhex(ret),byteorder='little')
    while rb > 0:
        rc.submit(rb&((1<<32)-1))
        rb >>= 32

pre_rb = hex(rc.predict_randrange(0, pow(2,256)-1))[2:]
pre_rb = int.from_bytes(bytes.fromhex(pre_rb),byteorder='little')
print(f"our prediction = {hex(pre_rb)[2:]}")
val = int("35"*32,16)
ret = val^pre_rb
ret = hex(ret)[2:]
while len(ret) < 32:
    ret = "0"+ret
for _ in range(4): read_until(f)
read_until(f,"> ")
s.send(b"2\n")
read_until(f,"Token > ")
s.send(ret.encode()+b"\n")
recv = read_until(f).split(": ")[1]
print(f"result         = {recv}")

for i in range(256):
    for _ in range(4): read_until(f)
    read_until(f,"> ")
    s.send(b"1\n")
    read_until(f,"Password > ")
    ans = hex(i)[2:]
    if len(ans) == 1: ans = "0"+ans
    s.send(ans.encode()*16+b"\n")
    flag = read_until(f).strip()
    print(i,flag)
    if "TFCCTF" in flag: break

(HARDER) TFCCTF{n0_th3_fl4g_1s_n0t_th3_0ld_0n3_plus-Th3-w0rd_h4rd3r!}
(FIXED) TFCCTF{4pp4r3ntly_sp4ces_br34ks_th3_0ld_0ne}



おわりに

crypto全完ということもあり久しぶりにwriteupを書いてみました。前回からかなり間が空いたので、文章力が不安ではありますが、皆さんに伝わる内容だと幸いです。手ごたえのある問題があっての全完だったので結構嬉しかったです! これからも面白い問題の解きに書いていこうと思うので、読んでいただけると嬉しいです!