# 2021 AIS3 Pre-exam Write Up
今年第一次參加AIS3 Pre-exam,之前有先看過一些別人寫的Write Ups,發現今年的解題想法好像差蠻多的TAT,今年成績第71名,算在錄取邊緣,期待明年我能表現更好囉!
這裡就來整理一下我賽中跟賽後有解出的題目吧!如果覺得有問題的話可以在留言區告訴我喔XD
P.S. 之前賽後交出去的那份Write Up覺得太爛了不想貼出來,決定重打一份w

# 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資料庫,裡面存有登入的資訊:

用了guest成功登入,但沒有flag。接著用admin試試,因為os.environ.get()的意思是如果key不存在就用後面的值來代替,但是還是登入失敗了。
接著觀察輸入後的行為:

他把我們的輸入塞進了```%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

稍微在網頁中翻找一下會發現根目錄裡面是一個"HealthCheck as a Service"網站,有一個可以輸入網址的欄位,用F12翻一下還可以發現一個hidden的status code參數。

一開始試了一些Command Injection之類的東西,但發現好像不太行。後來打開Hint裡面寫了```SSRF```,就開始往localhost的方向走了,但是如果直接連進localhost的IP(https://127.0.0.1/)跟domain會發現他被過濾了:

於是開始嘗試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了。

先用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

###### tags: `hexo`