WhiteHat GP 2018 - misc04
問題文
nc misc04.grandprix.whitehatvn.com 1337
実行結果
root@kali:~# nc misc04.grandprix.whitehatvn.com 1337
Wellcom to Friendly face challenge
According to experts, the formula for measuring the friendliness of a face is
(lip point**nose point)**(eyes point**forehead point) mod Face_index
Now play!
------------------------------Stage 1--------------------------------------
Face_index: 5084259
Face Lip point Nose point Eyes point Forehead point
:-) 67715980 537000274 149560563 213164859
(';') 901788023 138656583 905595776 701116315
(=^..^=) 141249414 274846937 652756525 48411044
(snip)
>;-> 210166562 437911136 981859202 199865833
:^o 726338740 777939971 953247197 669559312
:-9 701746818 902736102 217167318 297885596
So, what is the most friendly face?
writeup
各顔文字に、Lip、Nose、Eyes、Foreheadのポイントが割り当てられている。
(lip point**nose point)**(eyes point**forehead point) mod Face_index
が、最大となる顔文字を答える問題のようだ。
(lip point**nose point)**(eyes point**forehead point) mod Face_indexをそのまま計算していては、とんでもない計算量になるため、計算式の変形やアルゴリズムの効率化をしていく必要がある。
こちらの記事の離散対数定理の箇所を参考にさせて頂いた。
(lip point**nose point)をg、(eyes point**forehead point)をxと置くと、
g**x mod Face_indexとなる。
このとき、xは、離散対数定理より、
(eyes point**forehead point) mod phi(Face_index)となる。
gを戻し、指数法則を適用すると、
(lip point**(nose point*x) mod Face_indexと変形できる。
これらの計算式なら、mod関数とオイラー関数で実現できるため、計算できそうだ。
コードにする。
import re import sympy from pwn import * def euler(n): factors = sympy.factorint(n) rst = 1 for i,j in factors.iteritems(): rst *= (pow(i,j) - pow(i,j-1)) return rst if __name__ == '__main__': io = remote('misc04.grandprix.whitehatvn.com', 1337) receivedata = io.recvrepeat(1) print("[+]receivedata=" + receivedata) while True: pattern = 'Face_index: (.*)\n' m = re.search(pattern, receivedata) if m: face_index = int(m.group(1)) face_index_euler = euler(face_index) else: break friendly_point = 0 friendly_face = "" for line in receivedata.split("\n"): pattern = '(.{15})([0-9]+) +([0-9]+) +([0-9]+) +([0-9]+)' m = re.search(pattern, line) if m: face = m.group(1).strip() lip_point = int(m.group(2).strip()) nose_point = int(m.group(3).strip()) eyes_point = int(m.group(4).strip()) forehead_point = int(m.group(5).strip()) x = pow(eyes_point, forehead_point, face_index_euler) point = pow(lip_point, nose_point*x, face_index) if friendly_point < point: friendly_point = point friendly_face = face senddata = str(friendly_face) print("[+]senddata=" + senddata) io.sendline(senddata) receivedata = io.recvrepeat(1) print("[+]receivedata=" + receivedata) senddata = str(friendly_point) print("[+]senddata='" + senddata) io.sendline(senddata) receivedata = io.recvrepeat(1) print("[+]receivedata=" + receivedata)
オイラー関数はこちらを参考にさせて頂いた。
sympyで素因数分解ができるからオイラー関数と約数関数を書いてみた - 技術メモ
実行結果は以下の通り。
Stage 5まであった。
(venv2) root@kali:WhiteHat2018# python Misc04.py
[+] Opening connection to misc04.grandprix.whitehatvn.com on port 1337: Done
[+]receivedata= Wellcom to Friendly face challenge
According to experts, the formula for measuring the friendliness of a face is
(lip point**nose point)**(eyes point**forehead point) mod Face_index
Now play!
------------------------------Stage 1--------------------------------------
Face_index: 2264310
Face Lip point Nose point Eyes point Forehead point
:-) 519553424 902837079 577717458 566100603
(';') 959113224 454530720 565109982 15222442
(snip)
:^o 330858143 358402082 462399714 882466428
:-9 79862158 136049749 647871861 157061161
So, what is the most friendly face?
[+]senddata=<(*.*<)
[+]receivedata=It's friendly point
[+]senddata='2260269
(snip)
[+]receivedata=------------------------------Stage 5--------------------------------------
Face_index: 5666578
Face Lip point Nose point Eyes point Forehead point
:-) 479217513 102616880 934328557 559677503
(';') 977629839 748573245 496092793 13737674
(snip)
:^o 35865841 989382090 927163173 186069876
:-9 954913979 162762921 336135449 704807989
So, what is the most friendly face?
[+]senddata=|___|
[+]receivedata=It's friendly point
[+]senddata='5587041
[+]receivedata=Congrats! Flag, flag, flag!: WhiteHat{^.^_M4th_Math_Chin3se_Rema1nder_The0rem_&_Euler's_ThEorem_M@th_MAth_^/^}
[*] Closed connection to misc04.grandprix.whitehatvn.com port 1337
WhiteHat{^.^_M4th_Math_Chin3se_Rema1nder_The0rem_&_Euler's_ThEorem_M@th_MAth_^/^}
フラグゲット。
と思いきや、sha1の計算結果がフラグというルールのため、以下がフラグ。
root@kali:~# echo -n "^.^_M4th_Math_Chin3se_Rema1nder_The0rem_&_Euler's_ThEorem_M@th_MAth_^/^" | sha1sum 883e8e59798f1884c3873ff5f47aaeea089097f9 -
WhiteHat{883e8e59798f1884c3873ff5f47aaeea089097f9}
フラグゲット。
補足
離散対数定理を適用するには、べき乗の底と法が互いに素という条件を満たす必要あるようで、今回の問題でいうと(lip point**nose point)とFace_indexが互いに素であることが条件となるが、それを確認していなかった。
しかし、解けてしまった。
何度か実行しても失敗することは無かった。
出題の仕様だろうか？
条件を満たさない場合は、中国人剰余定理を使う必要があるようだ。
フラグ文字列上もChin3se_Rema1nder_The0remというメッセージもあるのだが・・・。
