# 2021 AIS3 Pre-exam Write Up 今年第一次參加AIS3 Pre-exam,之前有先看過一些別人寫的Write Ups,發現今年的解題想法好像差蠻多的TAT,今年成績第71名,算在錄取邊緣,期待明年我能表現更好囉! 這裡就來整理一下我賽中跟賽後有解出的題目吧!如果覺得有問題的話可以在留言區告訴我喔XD P.S. 之前賽後交出去的那份Write Up覺得太爛了不想貼出來,決定重打一份w ![](https://i.imgur.com/B8OCOaR.png) # Welcome ## Cat Slayer ᶠᵃᵏᵉ | Nekogoroshi > Author: splitline feat. Hojo Satoko 題目給了一行command ```bash TERM=xterm-256color ssh -p 5566 h173@quiz.ais3.org ``` 把它拿到Terminal執行後可以發現他跳出了一個Python的執行畫面,用鍵盤可以輸入數字,輸入錯誤會鎖起來,因此可以用手動的輸入猜密碼,得到正確的密碼就可以解鎖flag。 ``` Password: 202583045529 ``` FLAG: ``` AIS3{H1n4m1z4w4_Sh0k0gun} ``` # MISC ## Microcheese > Author: toxicpie 這題一樣給了nc跟source code,但source code看了半天還是沒什麼想法,先去nc玩玩再說。 ``` $ nc quiz.ais3.org 10234 +-------------------- welcome --------------------+ | omg hi! | | | | welcome to microchess, the minimal online chess | | platform. | | i am a super powerful chess AI! | | can you win against me and get the flag? | +---+--------------- main menu -------------------+ | 0 | read the rules of the game | | 1 | start a new game against me | | 2 | load a saved game | | 3 | leave | +---+---------------------------------------------+ what would you like to do? 1 +---+-------------- stones info ------------------+ | 0 | ooooooooooooo | | 1 | ooooo | | 2 | ooooooooooo | | 3 | o | | 4 | oooooooooooooooooooooooooooooo | | 5 | ooooooo | | 6 | ooooooooooooooooooooooooooo | +---+--------------- game menu -------------------+ | 0 | make a move | | 1 | save the current game and leave | | 2 | resign the game | +---+---------------------------------------------+ it's your turn to move! what do you choose? 0 which pile do you choose? 3 how many stones do you remove? 1 +--------------------- moved ---------------------+ | you removed 1 stones from pile 3 | +---+-------------- stones info ------------------+ | 0 | ooooooooooooo | | 1 | ooooo | | 2 | ooooooooooo | | 3 | oooooooooooooooooooooooooooooo | | 4 | ooooooo | | 5 | ooooooooooooooooooooooooooo | +--------------------- moved ---------------------+ | i removed 1 stones from pile 0 | +---+-------------- stones info ------------------+ | 0 | oooooooooooo | | 1 | ooooo | | 2 | ooooooooooo | | 3 | oooooooooooooooooooooooooooooo | | 4 | ooooooo | | 5 | ooooooooooooooooooooooooooo | +---+--------------- game menu -------------------+ | 0 | make a move | | 1 | save the current game and leave | | 2 | resign the game | +---+---------------------------------------------+ it's your turn to move! what do you choose? ``` 看起來是個遊戲,但玩了幾輪之後發現怎麼玩都輸,回去看source code發現```game.py```裡面好像有些東西。 ```python import random from typing import Tuple class Game: ''' a simple Nim game with normal rules. grundy's theorem: if nim_sum() is zero, then the player to move has a winning strategy. otherwise, the other player has a winning strategy. ''' def __init__(self): self.stones = [] def generate_winning_game(self) -> None: '''generate a game such that the first player has a winning strategy''' self.stones = [] xor_sum = 0 piles = random.randint(6, 8) for i in range(piles): self.stones.append(count := random.randint(1, 31)) xor_sum ^= count if xor_sum == 0: self.stones.append(random.randint(1, 31)) def generate_losing_game(self) -> None: '''generate a game such that the second player has a winning strategy''' self.stones = [] xor_sum = 0 piles = random.randint(6, 8) for i in range(piles): self.stones.append(count := random.randint(1, 31)) xor_sum ^= count if xor_sum != 0: self.stones.append(xor_sum) def make_move(self, pile: int, count: int) -> bool: '''makes a move, returns whether the move is legal''' if pile not in range(0, len(self.stones)): return False if count not in range(1, self.stones[pile] + 1): return False self.stones[pile] -= count if self.stones[pile] == 0: self.stones.pop(pile) return True def nim_sum(self) -> int: xor_sum = 0 for count in self.stones: xor_sum ^= count return xor_sum def ended(self) -> bool: ''' checks if the game has ended, i.e., the player has no more moves. if True, the current player loses the game ''' return len(self.stones) == 0 def show(self) -> None: print('+---+-------------- stones info ------------------+') for pile, count in enumerate(self.stones): print(f'| {pile} | {"o" * count:<43} |') def load(self, game_str: str) -> None: '''loads a saved game from string''' self.stones = list(map(int, game_str.split(','))) def save(self) -> str: '''returns the current game as a string''' return ','.join(map(str, self.stones)) class AIPlayer: ''' a perfect Nim player. if there exists a winning strategy for a game, this player will always win. ''' def __init__(self): pass def get_move(self, game: Game) -> Tuple[int, int]: ''' if there is a winning strategy, returns a move that guarantees a win. otherwise, returns a random move. ''' nim_sum = game.nim_sum() if nim_sum == 0: # losing game, make a random move pile = random.randint(0, len(game.stones) - 1) count = random.randint(1, game.stones[pile]) else: # winning game, make a winning move for i, v in enumerate(game.stones): target = v ^ nim_sum if target < v: pile = i count = v - target break return (pile, count) ``` 從程式內容跟註解可以很明顯的看到,比賽的必勝關鍵便是盤面所有行棋數的xor為0。但是程式裡面的AIPlayer便是利用這個規則,讓自己下完時的盤面保持0的狀態,果然是必勝訣竅阿... 原本這題賽中我應該是解不出來的,但是因為有一次把號碼按錯之後發現一個超級大的bug,當我在選擇下一個步驟時,我按了```3```(不在按鈕內),結果他就直接跳過了我的回合,讓盤面不再保持xor為0的狀態,接著就只需要讓最後一顆棋是由我拿走的就可以拿到flag了。 P.S. 這應該是因為沒有過濾其他輸入的問題...總之我拿到flag了XD ``` +---+--------------- game menu -------------------+ | 0 | make a move | | 1 | save the current game and leave | | 2 | resign the game | +---+---------------------------------------------+ it's your turn to move! what do you choose? 3 +--------------------- moved ---------------------+ | you removed 3 stones from pile 1 | +---+-------------- stones info ------------------+ | 0 | o | | 1 | o | +--------------------- moved ---------------------+ | i removed 1 stones from pile 1 | +---+-------------- stones info ------------------+ | 0 | o | +---+--------------- game menu -------------------+ | 0 | make a move | | 1 | save the current game and leave | | 2 | resign the game | +---+---------------------------------------------+ it's your turn to move! what do you choose? 0 which pile do you choose? 0 how many stones do you remove? 1 +---------------- congratulations ----------------+ | you are a true grandmaster of chess! here is | | the flag for you: | | AIS3{5._e3_b5_6._a4_Bb4_7._Bd2_a5_8._axb5_Bxc3} | +-------------------------------------------------+ ``` FLAG: ``` AIS3{5._e3_b5_6._a4_Bb4_7._Bd2_a5_8._axb5_Bxc3} ``` # Web ## ⲩⲉⲧ ⲁⲛⲟⲧⲏⲉꞅ 𝓵ⲟ𝓰ⲓⲛ ⲣⲁ𝓰ⲉ > Author: splitline 這題給了一個很難按的題目,連進去之後發現是一個login畫面,還有一個sauce link,先點進去看原始碼,發現他是一個json資料庫,裡面存有登入的資訊: ![](https://i.imgur.com/zv1wxp9.png) 用了guest成功登入,但沒有flag。接著用admin試試,因為os.environ.get()的意思是如果key不存在就用後面的值來代替,但是還是登入失敗了。 接著觀察輸入後的行為: ![](https://i.imgur.com/etLTbQM.png) 他把我們的輸入塞進了```%s```的地方包裝成json格式,但他並沒有過濾```%s```的內容,所以可以從輸入動手腳。 從上面可以看出來,他把新輸入的使用者showflag參數一律設為$false$,所以我們拿不到flag。但如果我們在輸入中塞入json格式的文字,他就會被包到這個json裡面送進去執行。 但因為我們必須構造一個不存在於原database的使用者,而json找不到username會回傳$null$,因此我們將password也設為$null$即可。 構造payload: ``` username payload: M3t30r", "showflag": true, "username": "m3t30r password payload: M3T30r", "password": null, "username": "M3T30R ``` FLAG: ``` AIS3{/r/badUIbattles?!?!} ``` ## HaaS > Author: anonymous 連進這題的網址後會是/haas的分頁,但會顯示出405 Method Not Allowed Error ![](https://i.imgur.com/26qcGuM.png) 稍微在網頁中翻找一下會發現根目錄裡面是一個"HealthCheck as a Service"網站,有一個可以輸入網址的欄位,用F12翻一下還可以發現一個hidden的status code參數。 ![](https://i.imgur.com/1PiS3kH.png) 一開始試了一些Command Injection之類的東西,但發現好像不太行。後來打開Hint裡面寫了```SSRF```,就開始往localhost的方向走了,但是如果直接連進localhost的IP(https://127.0.0.1/)跟domain會發現他被過濾了: ![](https://i.imgur.com/t8TKijf.png) 於是開始嘗試SSRF的bypass方法,這裡嘗試了幾個發現```https://127.000000.000000.1/```(要注意它只吃絕對網址)這個bypass可以成功讓haas顯示```"Alive"```,但我們必須拿到裡面的內容,所以將status code改掉讓haas噴出Error後即可拿到flag。 FLAG: ``` QQ我忘了,然後題目機把localhost關掉了TAT ``` # Crypto ## Microchip > Author: toxicpie 這題給了一個microchip.cpp、output.txt與python.h檔,打開觀察後可以發現它利用匯入python.h的library進行python語法的混淆,所以應只需要觀察程式邏輯即可。 ```cpp #include "python.h" def track(name, id) -> str ?? { if len(name) % 4 == 0 ?? ){ padded = name + "4444" ;} elif len(name) % 4 == 1 ?? ){ padded = name + "333" ;} elif len(name) % 4 == 2 ?? ){ padded = name + "22" ;} elif len(name) % 4 == 3 ?? ){ padded = name + "1" ;} keys = list() ; temp = id ; for i in range(4) ?? ){ keys.append(temp % 96) ; temp = int(temp / 96) ;} result = "" ; for i in range(0, len(padded), 4) ?? ){ nums = list() ; for j in range(4) ?? ){ num = ord(padded[i + j]) - 32 ; num = (num + keys[j]) % 96 ; nums.append(num + 32) ;} result += chr(nums[3]) ; result += chr(nums[2]) ; result += chr(nums[1]) ; result += chr(nums[0]) ;} return result ;} def main() -> int ?? { name = open("flag.txt", "r").read().strip() ; id = int(input("key = ")) ; print("result is:", track(name, id)) ; return 0 ;} ``` 下面是output.txt的內容: ``` result is:=Js&;*A`odZHi'>D=Js&#i-DYf>Uy'yuyfyu<)Gu ``` 從程式中可以發現他先把flag長度補成4的倍數後,用一組四個key來對flag進行一次4字元的運算。但是,我們沒有key也沒有flag,要怎麼逆運算回去? 後來發現我們可以利用flag format```AIS3{...}```來解決這件事,先用前四個已知flag字元搭配output算出key之後,我們就能利用output推回flag了。 值得注意的是,他把output四個逆過來輸出,所以我們先把output逆回來比較容易計算。 ``` &sJ=`A*;HZdoD>'i&sJ=D-i#U>fYuy'yuyfyuG)< ``` 用```AIS3```與```&sJ=```可以算出四個key的值: ``` {69,42,87,10} ``` 有了output與key就能寫程式來逆推flag了。 ```cpp #include<bits/stdc++.h> using namespace std; string s="&sJ=`A*;HZdoD>'i&sJ=D-i#U>fYuy'yuyfyuG)<"; int k[4]={69,42,87,10}; int main(){ for(int i=0;i<40;i++){ for(int j=48;;j++){ if(char((((j-32)+k[i%4])%96)+32)==s[i]){ cout<<char(j); break; } } } cout<<endl; return 0; } ``` P.S. 從我們的結果可以發現flag一開始塞了"22"到後面喔~XD FLAG: ``` AIS3{w31c0me_t0_AIS3_cryptoO0O0o0Ooo0} ``` ## ReSident evil villAge > Author: Kuruwa 這題給了一個nc跟source code,打開source code看一下。 ```python import socketserver from Crypto.PublicKey import RSA from Crypto.Util.number import * from binascii import unhexlify class Task(socketserver.BaseRequestHandler): def recv(self): return self.request.recv(1024).strip() def send(self, msg): self.request.sendall(msg + b'\n') def handle(self): privkey = RSA.generate(1024) n = privkey.n e = privkey.e self.send(b'Welcome to ReSident evil villAge, sign the name "Ethan Winters" to get the flag.') self.send(b'n = ' + str(n).encode()) self.send(b'e = ' + str(e).encode()) while True: self.request.sendall(b'1) sign\n2) verify\n3) exit\n') option = self.recv() if option == b'1': self.request.sendall(b'Name (in hex): ') msg = unhexlify(self.recv()) if msg == b'Ethan Winters' or bytes_to_long(msg) >= n: # msg+k*n not allowed self.send(b'Nice try!') else: sig = pow(bytes_to_long(msg), privkey.d, n) # TODO: Apply hashing first to prevent forgery self.send(b'Signature: ' + str(sig).encode()) elif option == b'2': self.request.sendall(b'Signature: ') sig = int(self.recv()) verified = (pow(sig, e, n) == bytes_to_long(b'Ethan Winters')) if verified: self.send(b'AIS3{THIS_IS_A_FAKE_FLAG}') else: self.send(b'Well done!') else: break class ForkingServer(socketserver.ForkingTCPServer, socketserver.TCPServer): pass if __name__ == "__main__": HOST, PORT = '0.0.0.0', 42069 print(HOST, PORT) server = ForkingServer((HOST, PORT), Task) server.allow_reuse_address = True server.serve_forever() ``` 從裡面可以發現verify的部分會檢查計算的結果是否等於```bytes_to_long(b'Ethan Winters')```,而它有給定n與e,因此原本的想法是爆搜,但發現搜不到於是放棄這條路。 再來看看有沒有其他的後門可以繞。sign的部分,它會把你的註冊用d計算後存為signature。用RSA的小常識,用d再用e運算後會把原本的明文算回來,但它前面出現了一個限制-**要用16進位輸入而且不能註冊Ethan Winters的值**。 在這裡要怎麼繞過呢?直觀的想法便是在前面加00,因為這樣數字運算的時候會把00省略,但是字串比較時會與Ethan Winters的值不同,所以用Ethan Winters的16進位值再加上00前綴試試看。 ```bash >>> "Ethan Winters".encode().hex() '457468616e2057696e74657273' ``` 把```00457468616e2057696e74657273```丟進去註冊,再把跑出來的```Signature```verify即可拿到flag。 ``` $ nc quiz.ais3.org 42069 Welcome to ReSident evil villAge, sign the name "Ethan Winters" to get the flag. n = 116446349250477461211548564037305096646246352712613922877939621221682086442262006076658058243799666178199942844412251167013582517469698767681352409472676329468186602987766214457609857069612827869171818746620035374912701350547179213366848809313278051695960906542268549406826272373673111354786397335987091196949 e = 65537 1) sign 2) verify 3) exit 1 Name (in hex): 00457468616e2057696e74657273 Signature: 81461102639376645458445563890933604042666832496108067724180262424539703394619135196334363979456757148465714312599695970577392038142353089971541912561007212572874317390985050129115895139824645075534050013217923053352965259741321376550049801845665852962177362515169292380016928834541247529513691701369654301864 1) sign 2) verify 3) exit 2 Signature: 81461102639376645458445563890933604042666832496108067724180262424539703394619135196334363979456757148465714312599695970577392038142353089971541912561007212572874317390985050129115895139824645075534050013217923053352965259741321376550049801845665852962177362515169292380016928834541247529513691701369654301864 AIS3{R3M383R_70_HAsh_7h3_M3Ssa93_83F0r3_S19N1N9} ``` FLAG: ``` AIS3{R3M383R_70_HAsh_7h3_M3Ssa93_83F0r3_S19N1N9} ``` ## Republic of South Africa > Author: Kuruwa 這題給了一個chall.py與output.txt,先來看看他的chall.py裡面做了什麼事情。 ```python from Crypto.Util.number import * from secret import flag import random import gmpy2 gmpy2.get_context().precision = 1024 def collision(m1, v1, m2, v2): return v1*(m1-m2)/(m1+m2) + v2*(2*m2)/(m1+m2), v1*(2*m1)/(m1+m2) + v2*(m2-m1)/(m1+m2) def keygen(digits): # Warning: slow implementation m1 = 1 m2 = 10 ** (2*digits-2) v1 = gmpy2.mpfr(0) v2 = gmpy2.mpfr(-1) count = 0 # p+q while abs(v1) > v2 or v1 < 0: if v1 < 0: v1 = -v1 else: v1, v2 = collision(m1, v1, m2, v2) count += 1 while True: p = random.randint(count//3, count//2) q = count - p if isPrime(p) and isPrime(q): break return p, q p, q = keygen(153) n = p*q e = 65537 m = bytes_to_long(flag) print('n =', n) print('e =', e) print('c =', pow(m, e, n)) ``` 可以發現他用一種神奇的算法來產出RSA參數,那就來看看他是怎麼計算的吧。 一開始真的看不太出來上面的計算是什麼意思,卡了好一陣子。後來又回頭看看題目,collision是指碰撞,再回頭看看source code,發現他很好心的把變數設成m1跟v1這種型態,分別代表了質量和速度! 而collision function裡面傳回的便是一維碰撞後兩個物體分別的速度公式,從這裡可以確定碰撞的想法是正確的了。 其中```v1```<0時,程式會將它變成相反數,就像撞上了牆壁無能量損失的反彈。因此綜合起來,兩個物體在進行碰撞且m1方有一面牆壁,而這時候看看count變數,它每碰撞一次便會+1,因此是計算碰撞次數,從這裡直接聯想到物理碰撞的著名經典問題: [從物理碰撞得出圓周率$\pi$](https://www.youtube.com/watch?v=Un7mK05b9oA) 得到這個結論之後就容易許多了,它給定質量是$1:10^{(2\times153-2)}$,因此可以得到count便是圓周率的前154位(推論過程詳見影片),而從裡面可以得到count=p+q,所以我們便得到了```p+q=314159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848```這個條件。 那我們需要把p跟q解出來嗎?不需要!分別得到p,q是因為我們需要計算$\phi(n)$的值,但現在我們有$n=p\times q$與$p+q$兩個條件了,這樣$\phi(n)=(p-1)(q-1)=p\times q-(p+q)+1$便可以計算了。 接下來就是用簡單的RSA概念來解決它囉! ```python from Crypto.Util.number import * n = 23662270311503602529211462628663973377651035055221337186547659666520360329842954292759496973737109678655075242892199643594552737098393308599593056828393773327639809644570618472781338585802514939812387999523164606025662379300143159103239039862833152034195535186138249963826772564309026532268561022599227047 e = 65537 c = 11458615427536252698065643586706850515055080432343893818398610010478579108516179388166781637371605857508073447120074461777733767824330662610330121174203247272860627922171793234818603728793293847713278049996058754527159158251083995933600335482394024095666411743953262490304176144151437205651312338816540536 k = 314159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848 phi = n-k+1 d = inverse(e, phi) print(long_to_bytes(pow(c, d, n))) ``` FLAG: ``` AIS3{https://www.youtube.com/watch?v=jsYwFizhncE} ``` 原來flag裡面給了一個碰撞的影片啊~有趣的題目XD # Reverse ## Piano > Author: CSY54 這題給了一個zip,裡面包了一堆額外的設定檔之類的東西。先來執行piano.exe,但它跳出了一個alert要我先去下載.NET的framework,這為我在下一步解題時開了一道曙光。 打開之後,它是一個GUI琴面,但是...不知道要彈什麼。看起來應該不能從這裡下手,那應該就是要reverse了。 ![](https://i.imgur.com/4eYCFcw.png) 先用IDA Pro打開.exe看看,但沒有發現什麼可以用的東西。後來想到一開始顯示的```.NET```,於是上網查了一下關鍵字```.NET reverse```,在[這個網站](https://pelock.medium.com/reverse-engineering-tools-for-net-applications-a28275f185b4)裡面發現了一個叫```dnSpy```的工具,可以對.NET下的framework進行reverse。那就來用用它吧! 用dnSpy打開piano.exe沒有發現東西,但打開piano.dll之後翻找了一下,發現兩個特別可疑的function```isValid()```與```nya()```: ```csharp // piano.Piano // Token: 0x06000003 RID: 3 RVA: 0x00002220 File Offset: 0x00000420 private bool isValid() { List<int> list = new List<int> { 14, 17, 20, 21, 22, 21, 19, 18, 12, 6, 11, 16, 15, 14 }; List<int> list2 = new List<int> { 0, -3, 0, -1, 0, 1, 1, 0, 6, 0, -5, 0, 1, 0 }; for (int i = 0; i < 14; i++) { if (this.notes[i] + this.notes[(i + 1) % 14] != list[i]) { return false; } if (this.notes[i] - this.notes[(i + 1) % 14] != list2[i]) { return false; } } return true; } ``` ```csharp // piano.Piano // Token: 0x06000004 RID: 4 RVA: 0x0000236C File Offset: 0x0000056C private string nya() { List<int> list = new List<int> { 70, 78, 89, 57, 112, 60, 125, 96, 103, 104, 50, 109, 87, 115, 112, 54, 100, 97, 103, 56, 85, 101, 56, 119, 119, 100, 59, 88, 50, 48, 62, 120, 84, 58, 100, 86, 74, 92, 54, 96, 60, 117, 119, 122 }; List<char> list2 = new List<char>(); for (int i = 0; i < list.Count; i++) { list2.Add((char)(list[i] ^ this.notes[i % this.notes.Count])); } return new string(list2.ToArray()); } ``` 觀察一下兩個$function$的關係,發現利用```isValid()```的條件可以算出notes的值,然後送到```nya()```可以把flag計算出來,那就寫個程式來實作就完成了。 先手動算出notes的值(很簡單啦不需要程式XD): ``` {7,7,10,10,11,11,10,9,9,3,3,8,8,7,7} ``` 接著套入```nya()```邏輯: ```cpp #include<bits/stdc++.h> using namespace std; int k[100]={ 70, 78, 89, 57, 112, 60, 125, 96, 103, 104, 50, 109, 87, 115, 112, 54, 100, 97, 103, 56, 85, 101, 56, 119, 119, 100, 59, 88, 50, 48, 62, 120, 84, 58, 100, 86, 74, 92, 54, 96, 60, 117, 119, 122 }; int n[15]={7,7,10,10,11,11,10,9,9,3,3,8,8,7,7}; int main(){ for(int i=0;i<50;i++){ cout<<char(k[i]^n[i%14]); } cout<<endl; return 0; } ``` FLAG: ``` AIS3{7wink1e_tw1nkl3_l1ttl3_574r_1n_C_5h4rp} ``` P.S. 所以用C#調彈小星星真的可以拿到flag喔~XD ![](https://i.imgur.com/xU0s8Qn.png) ###### tags: `hexo`