Asian Cyber Security Challenge 2021 - Pickle Rick
TL;DR
- PickleのRev
- Pickle中でPythonバイトコードによって関数を構成したりしているのでこちらもRevする必要がある
- 人力デコンパイルで処理を把握し、条件を満たすバイト列の逆算コードを書く
Prerequisite
(※どちらも公式ドキュメントが一番役に立つ上ので参考文献に載せています)
- Pickle
- Pythonバイトコード
Writeup
次のスクリプトとそこで読み込んでいるrick.pickleが渡される。
# /usr/bin/env python3
import pickle
import sys
# Check version >= 3.9
if sys.version_info[0] != 3 or sys.version_info[1] < 9:
print("Check your Python version!")
exit(0)
# This function is truly amazing, so do not fix it!
def amazing_function(a, b, c=None):
if type(b) == int:
return a[b]
else:
return (
f"CORRECT! The flag is: ACSC{{{c.decode('ascii')}}}" if a == b else "WRONG!"
)
with open("rick.pickle", "rb") as f:
pickle_rick = f.read()
rick_says = b"Wubba lubba dub-dub!!" # What is the right input here?
assert type(rick_says) == bytes and len(rick_says) == 21
pickle.loads(pickle_rick)
rick_saysをvalidな値に書き換えるとフラグが開示される予感がする。実際、このまま実行してみるとWRONG!が表示される。
Pickleの事を何も知らない1のでとりあえず他のPickleが出てくるWriteupやPickleのドキュメントを読んでみると、Pythonのシリアライゼーション方法の1つで、スタックマシンでデータを構築するらしい(この時点で「は?」って言ってる)。
標準ライブラリに入っているpickletoolsモジュールのdis()関数を使えば、どのような命令でデータが作られているのかがわかる。使われている命令は(参考文献にも載せている)ここに載っているのでpickletools.disの出力とこれを眺めながら動作を把握する。最初の17000バイトぐらいはバナーやメッセージの表示だけなので無視し、17245バイトから読み始める。
と言っても、最初はネストが深い入れ子タプルを作っているのようなのでこの処理が終わるところまで飛ばす。また、おそらくPickleは読み込み終了時(オペコードはSTOP)に、スタックトップにあるものがデータ構造としてロードされるので、このタプルがスタックトップに来ている場所までPickleのファイルを切り出し、それにSTOPのオペコードを表す.を末尾に付与してロードすることで取り出すことが出来る。今後もこの手法でPickleを切り出してオブジェクトを解析することが多いので次のような関数を用意した。
def extract_pickle(pickle_bytes, start, end):
return pickle_bytes[start:end+1] + b"."
ここで作られたタプルは19036バイトにあるMEMOIZE 0命令によってmemoという領域の0番目に格納される。実際に取り出して見てみると二分木のような構造になっているので以下、このタプルをtuple_treeとおく。
続きを読むと次のようになっている。
19038: c GLOBAL 'builtins type'
19053: c GLOBAL '__main__ amazing_function'
19080: \x85 TUPLE1
19081: R REDUCE
--- stack ---
type(amazing_function)
19082: c GLOBAL 'builtins type'
19097: c GLOBAL 'builtins getattr'
19115: c GLOBAL '__main__ amazing_function'
19142: S STRING '__code__'
19154: \x86 TUPLE2
19155: R REDUCE
19156: \x85 TUPLE1
19157: R REDUCE
19158: ( MARK
19159: J BININT 2
19164: J BININT 0
19169: J BININT 0
19174: J BININT 5
19179: J BININT 6
19184: J BININT 67
19189: B BINBYTES b'd\x01}\x02zB|\x00\\\x02}\x03}\x04|\x01d\x02\x16\x00|\x02k\x02r0|\x04}\x00|\x01d\x02\x1c\x00}\x01d\x03|\x02\x18\x00}\x02n\x14|\x03}\x00|\x01d\x02\x1c\x00}\x01d\x03|\x02\x18\x00}\x02W\x00q\x04\x01\x00\x01\x00\x01\x00|\x00d\x01\x19\x00\x06\x00Y\x00S\x000\x00q\x04d\x00S\x00'
19292: ( MARK
19293: N NONE
19294: J BININT 0
19299: J BININT 2
19304: J BININT 1
19309: t TUPLE (MARK at 19292)
19310: ( MARK
19311: t TUPLE (MARK at 19310)
19312: ( MARK
19313: S STRING 'a'
19318: S STRING 'b'
19323: S STRING 'c'
19328: S STRING 'a0'
19334: S STRING 'a1'
19340: t TUPLE (MARK at 19312)
19341: S STRING 'something_suspicious.py'
19368: S STRING 'search'
19378: J BININT 45
19383: B BINBYTES b'\x00\x01\x04\x02\x02\x01\x08\x01\x0c\x01\x04\x01\x08\x01\n\x02\x04\x01\x08\x01\x0c\x01\x06\x01'
19412: ( MARK
19413: t TUPLE (MARK at 19412)
19414: ( MARK
19415: t TUPLE (MARK at 19414)
19416: t TUPLE (MARK at 19158)
19417: R REDUCE
19418: } EMPTY_DICT
19419: \x86 TUPLE2
19420: R REDUCE
19421: \x94 MEMOIZE (as 1)
19082バイトから始まる処理を読むとtype(getattr(amazing_function.__code__))に大量の引数を渡してから、その結果をtype(amazing_function)の第一引数に渡している。
type(getattr(amazing_function.__code__))は<class 'code'>となり、ドキュメントを読んでみると、引数を渡すことで実行コードを構築することが出来る、みたいなことが書いてある。
ただ、これだけだと使えないらしく、そのあとtype(amazing_function)である<class 'function'>の第一引数に渡して関数を構成する必要があるらしい。最終的にtype(amazing_function)(type(getattr(amazing_function.__code__)(...)))を実行する事になる。これで生成されたものを先程のextract_pickleで取り出してみると<function search at 0x7f3632d68550>という関数が得られた。
問題は現状だと、これが何をしている関数かはわからない。おそらく19189バイトからの命令で積まれたバイト列がPythonのバイトコードになっていると思われる。というわけでdisモジュールのdis()関数を使ってこの関数をディスアセンブルし、その結果をdisのドキュメントを見ながら人力デコンパイルするとだいたい次のような関数になることがわかる。
def test_search(a,b):
c = 0
while True:
if len(a) == 1:
return a[0]
a0, a1 = a
if b % 2 == c:
a = a1
b = b // 2
c = 1 - c
else:
a = a0
b = b // 2
c = 1 - c
これと、抽出した関数に同じ引数を与えると同じ結果が得られるので特に問題は無さそうである。
この関数もまたMEMOIZE 1によって送られる。
19423バイトから19872バイトまでの処理もだいたい似たような事をしている。同じ手法で関数を取り出し、ディスアセンブルし、人力デコンパイルするとだいたい次のような関数になる。
def test_mix(a):
ln = len(a)
arr = []
i = 0
while i < ln:
s,j = 0, 0
while j < ln:
s = s + a[(i+j) % ln] * (j+1)
j += 1
s = s % 257 # ???
assert s < 256, i
arr.append(s)
i += 1
return arr
この関数はメモに入るわけではなく、この関数の引数にrick_saysを渡した結果がメモに入る。19895バイトの処理が終わった時点でのメモの状況は次の通り。
--- memo ---
0: tuple_tree
1: search
2: mix(rick_says)
続いて、19941バイトから20030バイトまでの処理を読むとsearch(tuple_tree, mix(rick_says)[0])のようになっている。ここでamazing_function(a,b)がこの場合はa[b]という処理になる事を用いた。
同様の処理が(これを含めて)21回続き、20886バイトのTUPLEによってタプルにまとめられる。後続を読むと、長さ21のタプルが即値によって構成されており、最後にこれらのタプルが等しいかどうかをamazing_function(a,b,c)によって判定して一致していればフラグ: ACSC{{{c}}}が出力される。
これでPickle部分のRevとPythonバイトコードのRevは終わったのでフラグを出力するrick_saysを逆算する。
最後に比較される即値のタプルをamazing_targetとおくと、目標は任意の添字iに対して、search(tuple_tree, mix(rick_says))[i] == amazing_target[i]となる。
searchは、第1引数が同じなら第2引数と出力結果は一対一になる予感がするので逆算用のテーブルを書けば良い。するとmix(rick_says) == (53, 158, 33, 115, 5, 17, 103, 3, 67, 240, 39, 27, 19, 68, 81, 107, 245, 82, 130, 159, 227)となるrick_saysを求める問題になる2。
mixの処理はややこしいように見えるが、よく読んでみると各成分の$\mathbb F_{257}$における線形結合のベクトルを構成しているだけである。具体的には次の21x21行列によって次のようになる。ここでmix(rick_says)と比較されるベクトルを$(s_1, \dots, s_{21})$とおいた。
$$ \begin{pmatrix} 1 & 2 & 3 & \dots & 21 \cr 21 & 1 & 2 & \dots & 20 \cr &&\vdots \cr 3 & 4 & 5 & \dots & 2 \cr 2 & 3 & 4 & \dots & 1 \cr \end{pmatrix} \begin{pmatrix} a_1 \cr a_2 \cr \vdots \cr a_{20} \cr a_{21} \end{pmatrix} = \begin{pmatrix} s_1 \cr s_2 \cr \vdots \cr s_{20} \cr s_{21} \end{pmatrix} $$
よって、この21x21行列の逆行列を両辺に掛ければ$(a_1, \dots, a_{21})$が求められ、これを文字列にすればフラグが現れる。
実際に与えられたファイルのrick_saysを書き換えて実行すると次のようになる。
...
Pickle Rick says:
b"YEAH!I'm_pickle-RICK!"
The flag machine says:
CORRECT! The flag is: ACSC{YEAH!I'm_pickle-RICK!}
Code
search()の逆算
import pickle
import dis
def test_search(a,b):
c = 0
while True:
if len(a) == 1:
return a[0]
a0, a1 = a
if b % 2 == c:
a = a1
b = b // 2
c = 1 - c
else:
a = a0
b = b // 2
c = 1 - c
def test_mix(a):
ln = len(a)
arr = []
i = 0
while i < ln:
s,j = 0, 0
while j < ln:
s = s + a[(i+j) % ln] * (j+1)
j += 1
s = s % 257 # ???
assert s < 256, i
arr.append(s)
i += 1
return arr
def extract_pickle(pickle_bytes, start, end):
return pickle_bytes[start:end+1] + b"."
def amazing_function(a, b, c=None):
if type(b) == int:
return a[b]
else:
return (
f"CORRECT! The flag is: ACSC{{{c.decode('ascii')}}}" if a == b else "WRONG!"
)
rick_says = b"aaaaaaaaaabbbbbbbbbb"
with open("./rick.pickle", "rb") as f:
p = f.read()
start = 17245
end = 19035
t = pickle.loads(extract_pickle(p, start, end))
start = 20887
end = 20993
target_tuple = pickle.loads(extract_pickle(p, start, end))
start = 19038
end = 19420
f_search = pickle.loads(extract_pickle(p, start, end))
start = 19423
end = 19872
f_mix = pickle.loads(extract_pickle(p, start, end))
d = {}
inv_d = {}
for i in range(256):
x = f_search(t, i)
d[i] = x
inv_d[x] = i
_x = test_search(t, i)
assert x == _x, i
amazing_targets = []
for x in target_tuple:
amazing_targets.append(inv_d[x])
print(target_tuple)
for i in range(21):
x = f_search(t, amazing_targets[i])
assert target_tuple[i] == x
mixの逆算 (SageMath)
p = 257
assert is_prime(p)
F = GF(p)
amazing_target = [98, 59, 114, 85, 203, 16, 155, 94, 218, 48, 235, 18, 189, 14, 117, 73, 138, 209, 91, 104, 28]
target = vector(F, amazing_target)
l = []
for i in range(21):
row = [-1 for _ in range(21)]
for j in range(21):
row[(i+j) % 21] = j + 1
l.append(row)
A = matrix(F, l)
A_inv = A^(-1)
xs = A_inv * target
print(xs)
flag = ""
for x in xs:
flag += chr(int(x))
print(flag)
Flag
ACSC{YEAH!I'm_pickle-RICK!}
Resources
- acsc-challenges-2021-public/rev/Pickle_Rick/distfiles at main · acsc-org/acsc-challenges-2021-public: 問題ファイル
- cpython/pickle.py at main · python/cpython: オペコード一覧
- pickletools --- pickle 開発者のためのツール群 — Python 3.10.4 ドキュメント: pickleのディスアセンブルを行うライブラリ
- コードオブジェクト — Python 3.10.4 ドキュメント
- dis --- Python バイトコードの逆アセンブラ — Python 3.10.4 ドキュメント: Pythonバイトコードの仕様と命令
これは嘘で__reduce__を使って任意コード実行に持っていく時に使われたりするのは耳に挟んだ
重箱の隅をつつくことになるが、mixの返り値はリストなので==ではない