Back to Posts

AIS3 EoF 心得 & Write-up

先來兩題 Write-up 吧,沒想到我竟然也會有全場唯一解出的時候,在 crypto 題目方面整個 自信++ 了呢 XD

BabyMT

結合了加密及錯誤修正,我們推出了跨時代高可用性的服務(?)。
在一次連線中,你可以送出最多 20,000 條指令,請想辦法解密 flag。
Defense 方面以單次連線解開的 flag 數量進行排名。
當你解開至少一個 flag 後,便可以獲得 Attack points。

解題思路

輸入大致為 AES(CRC32(paddingA + NUL + cmd + NUL + paddingB))

command 可以執行 getmd5 XXXgetcrc32 XXX,初始化時 get challenge 會輸出加密好的 getmd5 {3133731..}{FLAG} 作為 Example Command

假如原封不動送回去,拿到 padding + flag 的 hash 值,但並不能得到什麼幫助

[>] Team token: Sean
[*] Example command:
7fd9afd1e01c8fc1386fd3af966893da255b3ee9b2cb9ada5c32b7beed3572d247543c6a9f6d370f5c75f30b33cdaed8d80b2cdc9fc6b66ca9b228742a3934d6270ce13b7bfa96558a73e8c692fdc760738f8fd3c03d79026f7c28dd857ad7cc7724512088487d53808c8457d37c5780c818be80eae32bfbffccad0690af0c0ae5ca2a710f354d595090e9760a1389ee0639e1f54464542f19364d408cab20de7314da971a2d3b72063a000da10e6fab08e405804444fe5c8ab461f536a632ab189a14b12ce5705ad7151521370dde2a4e90e746f747b5d1c63dab5ecd57ac2a303905c96683932a9daeb89c87809739771eb78c948c212bdbf62cfb33c7fd909e37668449e0ac52527906904d6dc0914a9a6b5d1cedfdc55dee3c1199cc77f13c65cfda178e2f82df634b1b7dbd6160

[>] cmd: 7fd9afd1e01c8fc1386fd3af966893da255b3ee9b2cb9ada5c32b7beed3572d247543c6a9f6d370f5c75f30b33cdaed8d80b2cdc9fc6b66ca9b228742a3934d6270ce13b7bfa96558a73e8c692fdc760738f8fd3c03d79026f7c28dd857ad7cc7724512088487d53808c8457d37c5780c818be80eae32bfbffccad0690af0c0ae5ca2a710f354d595090e9760a1389ee0639e1f54464542f19364d408cab20de7314da971a2d3b72063a000da10e6fab08e405804444fe5c8ab461f536a632ab189a14b12ce5705ad7151521370dde2a4e90e746f747b5d1c63dab5ecd57ac2a303905c96683932a9daeb89c87809739771eb78c948c212bdbf62cfb33c7fd909e37668449e0ac52527906904d6dc0914a9a6b5d1cedfdc55dee3c1199cc77f13c65cfda178e2f82df634b1b7dbd6160
[+] MD5: 630eb8

為了方便理解,先開啟 God Mode 將 Example Command 還原成 AES 加密前的樣子,並照 4 + 32 個 bytes 隔開各 chunk

 C R C 3 2              p     l     a     i     n     t     e     x     t           b     o     d     y
00 01 02 03   00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
6f 1a 7b 8c   4d 2c 00 61 84 7f 6f 70 9f 6f 75 94 ad 09 35 84 c2 9d d7 d2 1c 7b e9 5d f4 5f 5e 40 01 c6 46 41
c0 fd 5f 5b   29 93 29 a9 a3 9b ed 6f 41 3f d5 91 bf 59 3d 43 4f 83 9d 95 15 33 bd cf 91 25 b3 89 93 35 27 59
c0 a2 b3 2a   ef 0d c3 27 a3 6f 8b c5 b7 a7 cf 7b 49 00 67 65 74 6d 64 35 20 33 31 33 33 37 33 31 33 33 37 33
84 84 a2 b7   31 33 33 37 33 31 33 33 37 33 31 33 33 37 33 31 33 33 37 33 31 64 33 39 32 33 38 32 37 66 66 35
1c ff 3b 13   36 61 65 66 66 63 63 62 33 31 63 34 35 36 35 64 31 63 30 64 61 00 7d 6f c7 59 13 0f 6b 1f 21 a3
cf 2f 27 ad   07 75 07 15 ab c5 3f cb 13 8b 83 43 4f 3f 7b e3 87 cb 4d 63 49 7d f9 0b 09 13 97 75 51 19 c3 a3
b1 f9 c6 6b   81 4b b7 5f 3f fb 21 5f 23 5d 31 d7 7f 73 0d 33 05 19 b1 4b f3 8d a1 05 01 c3 e7 53 a7 61 d7 a9
67 54 dc ad   d9 ed 0f 4b b3 23 23 9d c9 5f 9f df 15 7f 37 29 8b f9 c3 1f e1 b1 df e9 45 e3 f3 fd 9f d3 3b 0f
42 b4 84 42   d3 f3 af 73 08 08 08 08 08 08 08 08

其中做了兩層的冗余校驗,前 4 bytes 是 CRC32 checksum,當 decrypt 時出現問題,會試著用前後 block 做修復,但本題問題就出在當 CRC32 正常時,就不管 chunk-wise checksum

AES CTR 特性

經過測試發現 AES 的 CTR 模式中更改密文,解出來的明文也只會在對應位置出現蠻有規律的變化,條列出來後看出根本就是 XOR

只要知道原文該 byte 是什麼,對密文相應位置 XOR,就能控制解密後的字元

例如:已知第 3 個 chunk 中第 17 byte (0x6d) 是字母 m,希望修改為 c,只要算出 m (6D) XOR c (63) = 0E 後,將密文 (3, 17) 位置 XOR 0E 即可

CRC32 特性

循環冗餘校驗:Cyclic Redundancy Check

當初設計是為了因應通訊時的不穩定,利用 XOR 來做出錯誤的檢測及修正,並不像 md5、sha1 等演算法是為了防範資料竄改,因此並不能作為安全性的檢測

其中有個特性是「void」變成「v@id」和「long」變成「l@ng」的 CRC32 的變化完全相同

且以下狀況成立,可經由實測證實

CRC32("bool") = 55813692
CRC32("b@ol") = 6690374f
55813692 ^ 6690374f = 331101dd

CRC32("goto") = 52605c80
CRC32("g@to") = 61715d5d
52605c80 ^ 61715d5d = 331101dd

CRC32("long") = 3b97a968
CRC32("l@ng") = 0886a8b5
3b97a968 ^ 0886a8b5 = 331101dd

CRC32("void") = d27bd9ee
CRC32("v@id") = e16ad833
d27bd9ee ^ e16ad833 = 331101dd

利用此特性不需要知道整個 chunk 的原文,只要字串長度固定、知道自己在改的 position、char,就能通過 CRC32 驗證

解題流程

由於 command 前後都有長度為 0 ~ 128 不等的 padding,要先確定 command 的實際位置在哪

我是利用將 getmd5 31337... 改為 getcrc32 337...,假如成功輸出 CRC32 值代表找對位置了

得到 command 確切位置後,就要開始猜 flag 了

其中 command 和前後 padding 以 NULL 字元 (_) 做分隔,因此只要將 XXX_getcrc32 31337flag_XXX 改為 XXX_getcrc32 31337_lag*XXX,command 就會從 getcrc32 31337flag 變為 getcrc32 31337

前面提到了 CRC32 的特性,我要知道自己在改什麼,前面 CRC32 header 才能修改成正確的值,因此只要從 0 ~ f 都猜一次,只有正確時會回傳 CRC32 值,其他時候都只有 Error

依此方法只要 32 個 byte 各猜 16 次,必能找到 flag

最差狀況下複雜度為 128 + 16*32,也才 640 次,平均次數則是一半 (320 次),在 MAX_REQ=20,000 的限制下,得分期望值為 62 分,但當時某些 case 沒有處理好,跑整天下來運氣最好也只拿到 21 分,好險跟利用 Padding Oracle 的 DoubleSigma 比起來還是小勝

完成作答

得到此 flag 後,只要發送過去,即可得到 Attack flag

[>] cmd: submit d3923827ff56aeffccb31c4565d1c0da
[+] OK
[>] cmd: exit
[+] Score: 1
[+] Attack flag: EOF{tw0_de4dline_iN_0n3_D4y_QAQQQ}

Flag: EOF{tw0_de4dline_iN_0n3_D4y_QAQQQ}

後記

從週四線上賽當天八點開始解題時,我就一直在想這題,到了中午想出上面解法後才去洗澡吃飯

回來後開始動手寫程式實作,還不熟練導致寫到 19:55 才壓線送 flag 出去,Rank 直接從 No.7 衝到 No.4

晚上為了穩定性修到半夜一點多,但還是沒做到完美解,雖然 Defence 第一還是覺得不舒服 QQ

賽後在沒有時間壓力的狀況下,終於完成改到 100% 成功率啦~

Crypto 4 babyCrypt

被隊友指派此題時覺得在場還沒人解出來,輪不到我,但還是靜下心來看題目

打開 output 發現給了 Version: GCC 8.2.1 這個系統參數,還沒看 code 就直覺想到肯定跟 random generator 有關

題目利用一連串的 array shuffle、XOR、bitwise shift 等複雜運算將 flag 加密

#!/usr/bin/python3
import sys
import random


with open('flag.txt', 'rb') as f:
    flag = f.read().strip()
flag = list(flag.ljust(64, b'\0'))
key = 31337

assert(len(flag) == 64)
random.seed(key)

for _ in range(64):
    sub = list(range(256))
    random.shuffle(sub)

    idx = list(range(len(flag)))
    random.shuffle(idx)
    idx = [idx[i:i+2] for i in range(0, len(idx), 2)]

    nxt = flag[:]

    for i, (ia, ib) in enumerate(idx):
        dest = random.sample(idx[:i] + idx[i+1:], len(idx) // 2)
        dest = [k for p in dest for k in p]
        x = sub[flag[ia] ^ flag[ib]]
        x = sub[(x * 13 + 37) & 0xff]
        x = sub[(x + random.randrange(256)) & 0xff]
        x = sub[((x >> 3) | (x << 5)) & 0xff]
        for d in dest:
            nxt[d] ^= x

    flag = nxt

flag = bytes(flag).hex()

print('Version:')
print(sys.version) #  3.7.1 (default, Oct 22 2018, 10:41:28)   [GCC 8.2.1 20180831]
print('')
print('Flag:')
print(flag) # 326dcb14a795600ddc50e4c211f26f9f87730dc2f9e340e9c305ed70f55b4d52f99b9a31d99ef5bdfbac66c455577efce09b1a8774875a688dca260881149dcb

解題思路

測試時發現只要 flag 相同,在筆電 (macOS, Clang 10.0.0) 跟 VPS (Ubuntu, GCC 8.2.0) 上輸出完全相同,推斷是 random.seed(31337) 手動初始化 random seed 的關係,就想到既然能知道 random generator state 在過程中怎麼變化,那在加密過程中把所有 state 存下來,不就能倒轉著回去了

因此先正向跑一次,在每次 call random function 前用 getstate() 將內部狀態記錄到 array 中

逆向跑回來時,再用 setstate() 到著還原亂數狀態,並將兩個 for loop 倒轉過來,就能拿到 flag 了

Flag: EOF{-\A1l_RlgHt_w3_n33D_A_N3W_ID3A/-}

後記

雖然是 Crypto 最後一題,但看懂後發現意外地簡單,12:25 載回來邊吃飯邊看,13:45 就解出來了,讓整個 team 在 Game 的 rank 馬上爬到第一,每個 round 加 100 分

送完 flag 後五分鐘才發現放在 HTML 註解的隱藏版 misc 0,當時決定先留著不送,沒想到就這樣被用 misc 0 擠下來了 QQ

那段時間從 No.5 爬上了 No.3 ,也算值得了 XD

參賽心得

先上個記分板

上次一個人參加金盾獎,整天下來只解了一個水題,雖然很沮喪,但主辦單位還是頒了 直搗黃龍獎 鼓勵以高中身份參賽的勇氣

這次可以跨校組隊,雖然我們四個沒有為了得名特別找能力互補的戰友,直接朋友揪一揪就上場了,但意外發現各領域都有人專精,可以放心做自己專長的題目

當天中午雖然 BabyMT 大概只會對八成測資,拿到第一後一方面開心,另一方面想把它做到完美解,但怕浪費太多時間在上面,就被隊友制止了,先出去吃 Buffet
拿到 Crypto 4 的 First Blood 時更是興奮到坐不住,但比賽會場又不能吵鬧,只能揪隊友到場外聊聊天、來回走走讓內心雀躍平靜下來

整天都在疲憊狀況,還是撐完八小時後覺得終於解脫了,拿到第四名算是比參賽前預料的好一些,感謝隊友在背後互相支持,互相激盪出不同思路,跟之前參加的 CDX 、踢貓盃比起來,比完賽後覺得自己比較有貢獻感了
這場 AIS3 EoF 的題目很有趣,對於不常打 CTF 的我來說,幾乎都是用新觀念,多數題目不刻意刁難,在解題的過程中也學習到了不少,未來有機會還想繼續參賽

PHP 開發者,目前就讀高中

Read Previous

學科能力競賽 - 全國賽心得