SECCON CTF 2022 Quals Writeup
SECCON CTF 2022 オンライン予選にチーム yharima で参加しました（およそ3年ぶりのCTF）。
全体では49位、domestic では14位でした。二日目に入って地蔵と化してしまったのが反省点です。鍛錬が足りませんでした。
web: skipinx, crypto: pqpq, crypto: this_is_not_lsb だけ解けたので、その writeup を書きます。
web: skipinx
8080番ポートをリッスンしているnginxにリクエストを送ると、リクエストパラメータに proxy=nginx を append した上で web サーバにリクエストが転送される。
web サーバ側では proxy=nginx の指定がなければフラグを表示されるよう実装されているが、web サーバがリッスンしている 3000 番ポートは外からは繋げないので、リクエストパラメータをいじって突破した。
結論から書くと下記のように1000個リクエストパラメータを指定した。
#!/usr/bin/env python3 import requests url ='http://skipinx.seccon.games:8080/?' + 'a=1&' * 999 + 'proxy=foo' res = requests.get(url) print(res.text)
フラグ SECCON{sometimes_deFault_options_are_useful_to_bypa55} でした。
web サーバは express のデフォルトの設定で動いており、マニュアルによると query parser は qs のデフォルト設定が利用されるとありました。 そこで qs のドキュメントを読むと 1000 個までしかパラメータをパースしないと書いてあったので、1000 個パラメータを送り付けることにしました。
For similar reasons, by default qs will only parse up to 1000 parameters
適当なパラメータ 1000 個だと req.query.proxy.includes のところで includes が見つからずエラーとなってしまったので、proxy=foo の指定をそっと忍ばせてフラグを得ました。
crypto: pqpq
RSA 暗号的な p, q, r 3つの素数を使った暗号を解く問題。
この記事を書いていて途中でいろいろ計算を間違えていたことに気づいたが運よく解けていた。。。
次の5つの数字が与えられ、 を復元するとフラグが得られる。
まず と
を求める。
とすると、次のように計算できる。簡単のため
は省略する。
ただし、 と
は適当な整数。
つまり、 を計算すると
の倍数が得られる。
と
の最大公約数をとると
が求められるので、
で
も得られる
次に と
を求める。
なので、 と
の最大公約数をとると
が求められ、
で
が得られる。
（ここまで書いていて気付いたが、ごちゃごちゃやって を求めずに
と
の最大公約数をとって
を求めたほうが良かった）
オイラーの定理より、 なので、
となる
を求めると、次のようにして
を得られる。
最後に、,
,
それぞれを modulus とした
を求めた後、中国の剰余定理を利用して
を復元できる。
modulus が素数であれば、Modular square root - Prime-Wiki にあるような方法で平方根を求めることができるので、これを利用した。
平方根はそれぞれの modulus に対して二つ出てくるので、計8パターン全て試してフラグが出るものを探した。
▶ 最終的なソースコード（クリックで展開）
#!/usr/bin/env python3 from Crypto.Util.number import * import random e = 131074 n = 587926815910957928506680558951380405698765957736660571041732511939308424899531125274073420353104933723578377320050609109973567093301465914201779673281463229043539776071848986139657349676692718889679333084650490543298408820393827884588301690661795023628407437321580294262453190086595632660415087049509707898690300735866307908684649384093580089579066927072306239235691848372795522705863097316041992762430583002647242874432616919707048872023450089003861892443175057 c1 = 92883677608593259107779614675340187389627152895287502713709168556367680044547229499881430201334665342299031232736527233576918819872441595012586353493994687554993850861284698771856524058389658082754805340430113793873484033099148690745409478343585721548477862484321261504696340989152768048722100452380071775092776100545951118812510485258151625980480449364841902275382168289834835592610827304151460005023283820809211181376463308232832041617730995269229706500778999 c2 = 46236476834113109832988500718245623668321130659753618396968458085371710919173095425312826538494027621684566936459628333712619089451210986870323342712049966508077935506288610960911880157875515961210931283604254773154117519276154872411593688579702575956948337592659599321668773003355325067112181265438366718228446448254354388848428310614023369655106639341893255469632846938342940907002778575355566044700049191772800859575284398246115317686284789740336401764665472 cm = 357982930129036534232652210898740711702843117900101310390536835935714799577440705618646343456679847613022604725158389766496649223820165598357113877892553200702943562674928769780834623569501835458020870291541041964954580145140283927441757571859062193670500697241155641475887438532923910772758985332976303801843564388289302751743334888885607686066607804176327367188812325636165858751339661015759861175537925741744142766298156196248822715533235458083173713289585866 # 2 * t = e t = e // 2 # p^2e + q^2e - 2p^eq^e c1s = (c1 * c1) % n # p^2e + q^2e + pqX c2s = (c2 * c2) % n # pqX + 2p^eq^e y = c2s - c1s pq = GCD(y, n) r = n // pq # c1 = p^e + q^e + pqX # c2 = p^e - q^e # c1 + c2 = 2p^e + pqX w = c1 + c2 p = GCD(c1 + c2, n) q = pq // p phi = (p - 1) * (q - 1) * (r - 1) d = inverse(t, phi) m2 = pow(cm, d, n) def shanks_sqrt(a, p): s = p - 1 e = 0 while s % 2 == 0: e += 1 s //= 2 q = s x = 1 while True: x += 1 z = pow(x, q, p) if pow(z, 2 ** (e - 1), p) != 1: break y = z r = e x = pow(a, (q - 1) // 2, p) v = (a * x) % p w = (v * x) % p while w != 1: k = 0 ww = w while ww != 1: ww = pow(ww, 2, p) k += 1 d = pow(y, 2 ** (r - k - 1), p) y = pow(d, 2, p) r = k v = (d * v) % p w = (w * y) % p return v, p - v rps = shanks_sqrt(m2, p) rqs = shanks_sqrt(m2, q) rrs = shanks_sqrt(m2, r) ip = inverse(q * r, p) iq = inverse(r * p, q) ir = inverse(p * q, r) kp = ip * q * r kq = iq * r * p kr = ir * p * q for rp in rps: for rq in rqs: for rr in rrs: rcm = (kp * rp + kq * rq + kr * rr) % n flag = print(long_to_bytes(rcm))
フラグは SECCON{being_able_to_s0lve_this_1s_great!} でした
crypto: this_is_not_lsb
RSA暗号の ,
とフラグ
を暗号化した暗号文
、フラグ
のビット数が与えられる。
くわえて、
のビット数を
としたときに、上位
ビット目から見て 0b0011111111 となっているかの真偽値だけを返してくれる。
自体は分からないが、
に任意の数値
を掛けることはできるのでこれを利用する。
復号したときに、パディングがついているかどうかの判定を通る最も大きい値 (0b0011111111111..., 末尾は不明) となるようにすることを考える。
つまり、 となる
を求める。
この解を
とすると、
となりフラグが得られる。
を見つける際は、
のビット数が分かっているのでまず大まかに判定が true になる
を探し、その後は二部探索で判定が切り替わる直前の
を求めればよい。
▶ 最終的なソースコード（クリックで展開）
#!/usr/bin/env python3 from Crypto.Util.number import * import socket import random import re s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('this-is-not-lsb.seccon.games', 8080)) conf = s.recv(1024).decode('utf-8') print(conf) def parse_conf(conf): m = re.search(r'n = (\d+)', conf) n = int(m.group(1)) m = re.search(r'e = (\d+)', conf) e = int(m.group(1)) m = re.search(r'flag_length = (\d+)', conf) flag_length = int(m.group(1)) m = re.search(r'c = (\d+)', conf) c = int(m.group(1)) return n, e, flag_length, c n, e, flag_length, c = parse_conf(conf) def my_judge(x): y = (c * pow(x, e, n)) % n s.send(f'{y}\n'.encode('utf-8')) d = s.recv(1024).decode('utf-8') return d.startswith('True') def calc_bounds(): b = 1024 - flag_length - 10 found = False for i in range(1, 1024): x = i * (2 ** b) print(f'iter {i}: {x}') judge = my_judge(x) if not found and judge: print(i) found = True elif found and not judge: print(i) break l = (i - 1) * (2 ** b) r = i * (2 ** b) return l, r def binary_search(l, r): while l + 1 < r: mid = (l + r) // 2 print(f'binary search: {mid}') judge = my_judge(mid) if judge: l = mid else: r = mid return l l, r = calc_bounds() x = binary_search(l, r) padding_pos = n.bit_length() - 2 flag = long_to_bytes((0x100 << (padding_pos - 8)) // x) print(flag)
フラグは SECCON{WeLC0me_t0_tHe_MirRoR_LaNd!_tHIs_is_lSb_orAcLe!} でした
SECCON 2019 国内決勝 writeup
12/21 ~ 22 で開催された SECCON 2019 の国際決勝にチーム yharima として参加してきました。結果は7位でした。上位のチームは基本的に defense point を多く獲得しているところばかりだったので、defense 大事だなとおもいました。
何問か解くことはできたので writeup を書いておきます。
弐
サーバに画像を投げつけて一致度の高い画像を探すという問題。一致度 50%, 60%, 70% 以上でそれぞれ一個ずつフラグが出る。 4時間おきに一致度の計算用のパラメータが変わるということだったが、最序盤は全ピクセルで色が同じ白黒画像を投げつけただけで 89% 程度の一致度が出てフラグが全部そろってしまった。一応白黒以外の色も探索していくコードも書いてしばらく走らせたが、defense point が入ってるのかよくわからずすぐ放置してしまった。今考えるともう少し遊んでおくべきだったかもしれない。。。
↓白黒画像を生成してPOSTし、点を見るだけのソースコード
gen_uniform_image.py
#!/usr/bin/env python from PIL import Image import sys if len(sys.argv) < 4: print 'input R G B' sys.exit(1) r = int(sys.argv[1]) g = int(sys.argv[2]) b = int(sys.argv[3]) H = 400 W = 640 im = Image.new('RGB', (W, H)) for x in xrange(0, W): for y in xrange(0, H): im.putpixel((x, y), (r, g, b)) im.save('generated.png')
uniform.sh
#!/bin/sh
RESULT_DIR=uniform_result
for num in `seq 0 255`; do
mkdir -p ${RESULT_DIR}
./gen_uniform_image.py ${num} ${num} ${num}
result_file="${RESULT_DIR}/${num}.out"
curl -s -c my.cookie -L -F photo=@generated.png http://10.1.2.1 > ${result_file}
echo "[${num}]"
fgrep "Statistics for each color" ${result_file}
fgrep "Recognition rate" ${result_file}
sleep 3
done
四
ジャンプしたときのtrue/falseと関数呼び出しの履歴から、それに沿った入力をこたえるという問題。予選でも同じ形式の問題が出ており、自分がその問題を解いていたので流れでやることになった。defenseは一瞬で解かれて太刀打ちできなかったのであきらめた
box1
予選と同じく、逆ポーランド記法の数式を受け取って計算するというプログラムだった。
基本的には1文字ずつパースして処理を進めるプログラムになっている。
a ~ f までの演算子もしうは数字が入力となるが、1文字パースする処理の最初の分岐（0x557a93890ddc）を起点として、後続の分岐の true / false の列を確認することで数字か a ~ f の演算子のどれかかということは判別できる。
実際使われていた演算子は a, b, c, e のみで、それぞれ加算、減算、乗算、min に対応していた。
入力によって分岐の仕方が変わるのは加算と乗算の2つで、加算の場合は第二引数（後からスタックに push した方）の数だけループを回して1ずつ足していく関係で、0x557a93890a31 の分岐が第二引数と同じ回数だけ true になる。
乗算の場合は第二引数の数だけループを回して第一引数を足し合わせていく実装になっているので、同じように 0x557a93890a94 の分岐が第二引数と同じ回数だけ true になる。
最終的には次のスクリプトを書いて、入力となった数式を特定した。
#!/usr/bin/env python import json HINTS = { 'D': [True, False, True, True, True, True, True, True, False], 'a': [True, False, False], 'b': [True, False, True, False], 'c': [True, False, True, True, False], 'e': [True, False, True, True, True, True, False] } def get_chr(jump): p = None for c, a in HINTS.items(): if len(jump) < len(a): continue success = True for i, b in enumerate(a): if jump[i][1] != a[i]: success = False break if success: p = c break return p with open('box.trace') as f: traces = json.load(f) first_found = False jumps = [] formula = [] all_jumps = [] for i, trace in enumerate(traces): if trace["event"] == "image_load" or trace["event"] == "exit": continue if not first_found and trace["inst_addr"][-3:] != "ddc": continue jump = trace["branch_taken"] if trace["inst_addr"][-3:] == "ddc": if first_found: all_jumps.append(jumps) jumps = [] else: first_found = True if jump == False: break jumps.append((trace["inst_addr"][-3:], trace["branch_taken"])) formula = [] for i, jump in enumerate(all_jumps): c = get_chr(jump) formula.append(c) if c == 'a': t = 0 for j in jump: if j[0] == 'a31' and j[1]: t = t + 1 print i + 1, c, t elif c == 'c': t = 0 for j in jump: if j[0] == 'a94' and j[1]: t = t + 1 print i + 1, c, t else: print i + 1, c if c is None: print "Fail..." break print ''.join(formula)
実行結果はこちらで入力となった数式を1文字ずつ出している。
加算 (a)、乗算 (c) の場合は第二引数の値も合わせて出力している。
D は 0~9 の数字を表す。
1 D 2 D 3 D 4 D 5 D 6 D 7 D 8 D 9 D 10 D 11 D 12 D 13 c 12 14 e 15 D 16 D 17 D 18 D 19 a 10 20 D 21 D 22 D 23 D 24 b DDDDDDDDDDDDceDDDDaDDDDb
あとは、加算・乗算の引数に気をつけて適当に D の部分の数字を埋めれば良い。 次のような数式になるようにしてみた。
min(0, 0 * 12) + 10 - 0
APIへ数式を送りつけたところフラグが出た（input の部分が与えた入力）
[*] API /attack/1/submit with input = 000000000012ce0010a0000b
{'message': 'Good! Submit this flag :)', 'flag': 'SECCON{Good! Go on next :hugging-face: oUedlavRDOMzUhzu}', 'error': False}
box2
与えた入力を暗号化して出力するプログラムだった模様（CBCだったのかな？）。
鍵は入力によって変化することはないようで、実は入力によって分岐が変わる部分はごく僅かだった。
先頭から16byteずつごちゃごちゃと変換していくのだが、この16byteずつ読み込むためのループ以外は入力によって分岐が変化しない。
0x5579b80c8c61 の分岐が true になっている回数が、このループを回っている回数に対応し、これが12回だった。
つまり、16 * 12 = 192 byte の入力を与えてやれば良い
[*] API /attack/2/submit with input = 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
{'message': 'Good! Submit this flag :)', 'flag': 'SECCON{Brilliant! You know crypto function depends on input length :relaxed: gVtDHSPrBkoHdxiw}', 'error': False}
供養
挑戦したが解けなかった問題たち
- 四 box3
命令セットが x86 であることに気付いて適当にループを組めばいいところまでは分かったものの時間切れで終了。律儀に各命令の処理内容をバイナリから全て読み取ろうとして時間を浪費したのが痛かった… - 六 Hardware
STM32 CubeMX Programmer なる開発環境をインストールして接続を試みるもDEV_UNKNOWN_MCU_TARGETなど出てそもそも読み込みができず何もできなかった。つなぎ直すと出るエラーが変わったりしたのでそもそも物理的な接続がまずかったのかもしれない…
戦友
チーム yharima のメンバーの writeup
SECCON 2017 Online writeup
yharima チームで参加。
84th、1900点でした。
自分がフラグを提出した問題だけまとめる。
Vigenere3d
vigenere 暗号だけれど、表が二次元ではなく三次元になっているという問題。
三次元になってはいるが、s として定義されている文字列上で何文字ずらしたかさえ結局分かればいい。
鍵は14文字だが、その鍵で暗号化したあとに、反転した文字列を鍵として暗号化するのと同じことをやっている。
つまり、最初7文字で何文字ずらせばよいかわかれば、それを反転させて次の7文字に適用すればよい。
最初7文字が SECCON{ になることを利用すれば、最初の7文字何文字ずらせばいいかわかる。
テキストでうまく説明できなかったので、ソースコードをそのまま貼り付けておく。
#!/usr/bin/env python
s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghijklmnopqrstuvwxyz_{}"
e = "POR4dnyTLHBfwbxAAZhe}}ocZR3Cxcftw9"
hint = "SECCON{"
key_half = []
for i in range(len(hint)):
c1 = hint[i]
c2 = e[i]
k1 = s.find(c1)
k2 = s.find(c2)
d = (k2 - k1) % len(s)
key_half.append(d)
key = key_half + key_half[::-1]
text = ''
for i in range(len(e)):
c2 = e[i]
d = key[i % len(key)]
k2 = s.find(c2)
k1 = (k2 - d) % len(s)
c1 = s[k1]
text += c1
print text
フラグは SECCON{Welc0me_to_SECCON_CTF_2017}
Qubic Rube
QR コードの問題は毎年担当しているので、勇んで解いた。
ブラウザ上でQRコードが各面に貼られたルービックキューブが回転する様が描画されるので、QRコードを読み込んで次のURLを見つけてフラグまでたどり着くという問題。 50問ある上、ルービックキューブなので回転を加えられてQRコード部分がぐちゃぐちゃになるので、人手で解くのは厳しい。 はじめルービックキューブ的に回転するとは思っていなくて2問目に飛んだ時にショックを受けたのはいい思い出。
手順としては次のように解いた。
ブラウザ上で描画しており、各面のテクスチャはページのソースの中で見つかるので、まずはそれをダウンロードしてくる。
画像を3x3の9領域に相当するピースに分割し、各面の色ごとに角4つ、辺4つ、中心1つの9つのピースをまとめる。
次のことを考慮して、ありえる組み合わせを列挙していく
- 角にあったピースが辺や中心にいったり、中心にあったピースが角や辺にいくことはありえない
- 角のピースでもともと画像の角に位置していた点は、復元時も画像の角に位置していなければならない
- 辺のピースでもともと画像の辺に位置していた辺は、復元時も画像の辺に位置しなければならない
中心のピース以外は位置が決まれば向きが決まることになる。 そこで、中心のピースは固定し、角と辺のピースの位置を適当に決める。 1面当たり 4! * 4! = 576 通りの候補が出てくる。
あとは適当な QR コード解読用のライブラリに画像を食わせて、QRコードとして読み取れるまで走らせるだけ。
まじめに回転とかを考慮するともっと速くできたのだろうけど、1時間近く走らせれば終わるペースだったのでそのまま放置した。
フラグは SECCON{Thanks to Denso Wave for inventing the QR code}
SHA-1 is dead
sha1 が一致する 2017KB ~ 2018KB のサイズのファイルをアップロードすればよいという問題。 かの有名な SHAttered の pdf を https://shattered.it/ からお借りした。 ファイルの最初の方でハッシュ値を計算に用いられる状態が一致して、あとは同じバイト列が続いているので、必要なサイズになるまで適当な文字列をつなげればよい。
$ python -c 'print "A" * 1643000' > tail.txt $ cat shattered-1.pdf tail.txt > hoge1.bin $ cat shattered-2.pdf tail.txt > hoge2.bin $ sha1sum hoge1.bin d05003cacf7e3c4f4dc01997f57cae7d5efb8485 hoge1.bin $ sha1sum hoge2.bin d05003cacf7e3c4f4dc01997f57cae7d5efb8485 hoge2.bin
フラグは SECCON{SHA-1_1995-2017?}
Log Search
ログを検索するページが与えられて、フラグを探す問題。
最初SQLインジェクションでもするのかと思ったが、クエリをいろいろ投げているうちに、Lucene ベースの検索エンジンであることに気づく。 フィールド名はテーブルにそのまま書いてあったので、フィールド指定したり、OR/AND 検索などもできた。
問題公開前のログを見ればいいかと思い、次のようなクエリを投げた。
timestamp:"09/Dec/2017" AND -(timestamp:"09/Dec/2017:15" OR timestamp:"09/Dec/2017:16" OR timestamp:"09/Dec/2017:17" OR timestamp:"09/Dec/2017:18" OR timestamp:"09/Dec/2017:19") AND request:flag AND response:200
12/08以前のログはなさそうだったので、12/09 に絞っている（必要なかった気もする）。
このクエリをなげたとき19時代だったので、15~19時のログがヒットしないようにした。
さらに、flag もどきのページにアクセスして 404 が返ってきているようだったので、それを除くために response:200 を付けた。
ちなみに timestamp が日付型だと思ってレンジクエリを投げてうまくいかずはまった。
このクエリで検索するとログが一件だけひっかかり、そこにアクセスするとフラグが見える。
フラグは SECCON{N0SQL_1njection_for_Elasticsearch!}
Ps and Qs
RSA の公開鍵二つと暗号文が渡されるので、それを解読する問題。
公開鍵が二つあったので、とりあえず modulus の gcd をとったら素因数分解できた。 あとは rsatool に秘密鍵を作ってもらって openssl で解読。
フラグは SECCON{1234567890ABCDEF}
Man-in-the-middle on SECP384R1
楕円曲線暗号を使ったやりとりに、中間者攻撃をしかける問題。
これで後半の時間をすべて溶かした。
解けたからよかったものの他の問題に手を出すべきだったかもしれない。
何もしないと dev0 と dev1 の間のやり取りを模したデータが送られてくるだけ。 ただし、データを受信してから一定時間内にペイロードを送ると、中間者としてデータをすりかえたことになるらしい。
初めは 楕円曲線暗号用の公開鍵（DER形式）をやりとりしているので、適当に鍵ペアを作って公開鍵を dev0 と dev1 に送り付ける。
秘密鍵と公開鍵は次のようにして openssl で作成した。
楕円曲線としては SECP384R1 を選択する。
$ openssl ecparam -name secp384r1 -genkey > my.key $ openssl ec -pubout < my.key > my.pub
正しい形式で送ると OK とレスポンスが返ってくるので、これで公開鍵は正しく受け渡せた。
次に、共通鍵を作成する。
ECDH で鍵共有が行われているようだったので、まず共有する秘密（楕円曲線上の座標）を作成する。
楕円曲線暗号では、秘密鍵は適当な整数値が1つであり、公開鍵はベースポイントG * 秘密鍵の整数値に相当する座標となっている。
相手からもらった公開鍵中の座標に自分の秘密鍵に相当する値をかけることで、共有する秘密であるところの楕円曲線上の座標が求められる。
楕円曲線上でのスカラー倍算の実行には python の fastecdsa パッケージを利用した。
さらに、[KBKDF: SHA256, Encryption: AES] と送られてくるので、SHA256 でハッシュ化して鍵を作成して AES で暗号化/復号化を行えばいいらしい。
SHA256 に得られた楕円曲線上の座標のx座標を食わせてdev0, dev1 それぞれの共通鍵を作成した。
そして、dev0 用の共通鍵でAES-CBC で dev0 から送られてきた暗号文を復号すると 0000....0000 と出てきた。 このとき、先頭16バイトが iv だと思って復号したが、これが大きな過ちだった。 適当な iv で 0000...0000 (240文字) を暗号化して送っても、dev1 から返答はなかった。
dev0 から送られてくるデータ 256 byte は全て暗号文で、iv は送られてくるデータに入ってきていなかった。
後半 240 バイトは iv にかかわらず復号できるので、その 240 バイト (0000....0000) をもとに暗号文の最初 16 バイトから本当の iv が復元できた。
ちなみに test message0000 だった。
これを iv として、0000...0000(256バイト) を dev1 用の共通鍵で暗号化し、dev1 に送ると無事レスポンスが得られた。
さらに、得られたデータを dev1 用の共通鍵で復号すると、だいたいうまく復号できたが、iv がわからないので最初16バイトが不明となった。
復号文の最後の文字が } だったのでこれがフラグだろうということで、初め7バイトがSECCON{ になるよう iv を予想したところ、iv の先頭7バイトは '0000000' となった。
残りも 0 だろうということで iv を 0000...0000(16バイト)にしたところ、フラグが出た。
フラグは SECCON{FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFCB3312FA7E23EE7E4988E056BE3F82D19181D9C6EFE8141120314088F5013875AC656398D8A2ED19D2A85C8EDD3EC2AEF00000000000000000000000000000000000000000000000000000000}
（長い）
反省
man in the middle で時間を溶かしすぎた。
z80 と Very smooth は面白そうだったのでやりたかった。
pwn に手が出なかったので基礎力をつけたい。
関連
チーム yharima のメンバの writeup
0ctf 2017 writeup
チーム yharima として参戦。 Welcome を除くと、onetimepad と integrity の二問だけしか解けず。
onetimepad
暗号化に使われたスクリプトと暗号文が渡されるので、それを復号する、そんな問題。
16byteの鍵と平文(16byte)をXORにかけて暗号化するが、鍵の生成法は次の通り（問題より抜粋）
def process(m, k): tmp = m ^ k res = 0 for i in bin(tmp)[2:]: res = res << 1; if (int(i)): res = res ^ tmp if (res >> 256): res = res ^ P return res def keygen(seed): key = str2num(urandom(32)) while True: yield key key = process(key, seed)
暗号文が三つ(16byte×3)、平文が二つ与えられるので、二つ分の鍵がわかる。 フラグの暗号用の鍵は一番最初に作られていて、その後生成された二つの鍵が既知。
結局のところ、process(m, k) の中の res が与えられたときに tmp を求めることができればよい。
これができれば既知の鍵二つから seed が求められ、seedと既知の鍵が分かっていれば一つ前に生成された鍵が求められる。
ここで、次の部分の処理にだけ注目する。
for i in bin(tmp)[2:]: res = res << 1; if (int(i)): res = res ^ tmp
この処理を行うと元のビット列の間に 0 を挟んだものが結果となる。
tmp == 0b101 であれば res == 0b10001 になり、tmp == 0b1111 であれば res == 0b1010101 になる。
つまり、下から偶数番目のビットが必ず 0 になる。
この tmp * tmp 的な値を復元していく。
実際は if (res >> 256): res = res ^ P の処理が入るため、そうはならない。
しかし、ここで P の下位12bit に着目すると 0b0010000100101 となっており、下から偶数番目のビットが 1 となっているのは、6ビット目だけ。
基本的には、res の偶数番目のビットが立っていればそれは res = res ^ P の影響であることになる。
このことから、下位 bit から少しずつ復元が可能になる。
ただし、res = res ^ P で立ったビットがシフトされることにより再度 res = res ^ P されることも考慮すると、このやり方では6ビットは一意に特定できない。
6ビットだけ全探索して、tmp * tmp 的な値を気合で復元し、奇数番目のビットだけ抜き出すと res の候補がでる。
コードは下のようになった。
#!/usr/bin/env python # coding=utf-8 def encode(tmp): res = 0 for i in bin(tmp)[2:]: res = res << 1; if (int(i)): res = res ^ tmp if (res >> 256): res = res ^ P return res def str2num(s): return int(s.encode('hex'), 16) def decode(k): for x in range(1 << 6): t = k for i in range(6): if x & (1 << i): t ^= 0x425 << i if t & 0b10101010: continue bh = x t = x << 256 | t for i in range(6, 256): if i % 2 == 0 and t & (1 << (i + 5)): bh ^= 1 << i m = 0x425 << i t ^= m if m >= (1 << 256): bh ^= m >> 256 y = bh << 256 | t b = 0 for i in range(0, 512, 2): if y & (1 << i): b |= 1 << (i/2) if encode(b) == k: return b P = 0x10000000000000000000000000000000000000000000000000000000000000425L ctxt1 = 0xaf3fcc28377e7e983355096fd4f635856df82bbab61d2c50892d9ee5d913a07f ctxt2 = 0x630eb4dce274d29a16f86940f2f35253477665949170ed9e8c9e828794b5543c ctxt3 = 0xe913db07cbe4f433c7cdeaac549757d23651ebdccf69d7fbdfd5dc2829334d1b fake_secret1 = "I_am_not_a_secret_so_you_know_me" fake_secret2 = "feeddeadbeefcafefeeddeadbeefcafe" f1 = str2num(fake_secret1) f2 = str2num(fake_secret2) k2 = ctxt2 ^ f1 k3 = ctxt3 ^ f2 d2 = decode(k2) d3 = decode(k3) seed = k2 ^ d3 k1 = seed ^ d2 f = k1 ^ ctxt1 print hex(f)[2:-1].decode('hex')
復号すると t0_B3_r4ndoM_en0Ugh_1s_nec3s5arY が出る。
フラグの形式で提出しておわり。
他の方の writeup を見るとこれはガロア体における平方根を出す問題だったらしい。。。 ガロア体を知らずに解けたのは運がよかっただけっぽい。 ガロア体を勉強するいい機会になりました。
integrity
サーバに繋ぐと AES-CBC をもとにした暗号化と復号化ができる。adminだけ暗号化できないのだが、復号化して admin となる文字列を与えることができればフラグが出る。そんな問題。
暗号化は AES-CBC そのままではなく、以下のようになっている（問題より抜粋）。pad は16byteの倍数になるよう後ろにパディングするだけの関数。
def encrypt(self,raw):
raw = pad(raw)
raw = md5(raw).digest() + raw
iv = Random.new().read(BS)
cipher = AES.new(self.key,AES.MODE_CBC,iv)
return ( iv + cipher.encrypt(raw) ).encode("hex")
入力文字列に対して md5 を付け加えているのがミソ。
まず、適当な16文字の後に admin と付け足した文字列 (0123456789012345admin) を暗号化してやる。
CBC モードでの解凍は後ろのブロックから順に行われ、iv は最初のブロックに影響を与えるだけなので、iv を除いた暗号文の最初16byteを削っても admin のブロックは正しく復号化される。
後は先頭のブロックの復号結果が md5(pad('admin')) になるよう iv を調整するだけ。
変数名がとても雑だが下のようなコードで、復号結果が admin の文字列を生成できる。
t = '0123456789012345' a = 'admin' p = t + a c = scheme.encrypt(p) d = int(c[32:64],16) e = int(t.encode('hex'), 16) f = int(md5(pad(a)).hexdigest(), 16) x = d ^ e ^ f y = hex(x)[2:-1] + c[64:128] print scheme.decrypt(y)
あとはこれの暗号/復号部分をソケット通信でやるように置き換えるなどして終わり。
フラグは flag{Easy_br0ken_scheme_cann0t_keep_y0ur_integrity}
志半ばで終わった問題たち
- simplesqlin
- WAF が破れなかったのでスキーマやテーブルを漁れず死亡
- Temmo’s tiny shop
- ほぼお買い物しただけ
- onetimepad2
- 式を弄って
A^Nを出せたっぽいが、そこからNを求めることができずに結局復号できず - Discrete logarithm?
- 式を弄って
AlexCTF 2017 write up
チーム yharima で参加したので、write up を書いておく。 暗号ばっかり解いていた。
CR2
問題文を読むと、one time pad を使ったけど one time と呼ばれる意味が分かっていない、的なことが書いてあったので、鍵が使いまわされているんだろうなあと予想。
one time pad といっても色々あるらしいのだが、XORで暗号文を作ると予想して、次のリンクにある通り解読を試みた。
http://crypto.stackexchange.com/questions/59/taking-advantage-of-one-time-pad-key-reuse/64
鍵をK、平文をTとしたときに、暗号文Cは鍵と平文の XOR をとったもの。
C = K ⊕ T
同じ鍵の暗号文が複数用意されている (C1, C2) とき、暗号文どうしの XOR をとると、鍵の影響を排除できる。
C1 = K ⊕ T1
C2 = K ⊕ T2
C1 ⊕ C2 = (K ⊕ T1) ⊕ (K ⊕ T2)
= T1 ⊕ T2
C1 ⊕ C2に対し、平文に入っていそうな単語で適当な位置のXORをとってみて、結果が読める文になるところを探す。見つかった場合、その部分の平文が明らかになったことになる。ただし、元の単語と XOR の結果のどちらが C1 に含まれるのかはわからない。
問題のテキストは 11 行になっていたので、hex から byte に変換してから、適当な2行を選んで思いついた単語が入っているか確認していった。
結果、どうやら3行目に crypt という文字列が含まれているらしいことがわかった。 これで、次のような感じの平文になっていることが判明したので、あとは左右にそれっぽい文字がくるよう適当に伸ばしていけば全部解読できた。
___________________ime I__ ___________________e and__ ___________________crypt__ ___________________hat i__ ___________________ion m__ ___________________tical__ ___________________racke__ ___________________kept __ ___________________f you__ ___________________ this__ ___________________ways.
解読結果はこちら。
Dear Friend, This time I u nderstood my mistake and u sed One time pad encryptio n scheme, I heard that it is the only encryption met hod that is mathematically proven to be not cracked ever if the key is kept se cure, Let me know if you a gree with me to use this e ncryption scheme always.
結局、鍵がフラグだった。
ALEXCTF{HERE_GOES_THE_KEY}
（初めからALEXCTF{とXORとっていけばよかった）
CR4
RSAの問題。 とりあえず modulus を見てみる。
$ openssl rsa -noout -text -in key.pub -pubin
Public-Key: (399 bit)
Modulus:
52:a9:9e:24:9e:e7:cf:3c:0c:bf:96:3a:00:96:61:
77:2b:c9:cd:f6:e1:e3:fb:fc:6e:44:a0:7a:5e:0f:
89:44:57:a9:f8:1c:3a:e1:32:ac:56:83:d3:5b:28:
ba:5c:32:42:43
Exponent: 65537 (0x10001)
399 bit の RSA コンテストはなかったが、factordb に聞いたら素因数分解してもらえた。
あとは Wikipedia にある通り、例の式に従って復号。
フラグは ALEXCTF{SMALL_PRIMES_ARE_BAD}
CR5
nc でつなぐと、次の数字を教えてもらうか、予想の入力をすることができる。 教えてもらうと乱数列が返ってくるので、これを予想すればいいっぽい
線形合同法では？、と思い次のリンクの通り乱数列の予測を試みた。
security.stackexchange.com
リンク先に書いてある通りだが、ここにもまとめておく。
x[n + 1] = a * x[n] + b (mod m)
より
x[n + 1] - x[n] = a * (x[n] - x[n - 1]) (mod m)
となるので、
y[n] = x[n + 1] - x[n] (mod m)
とおくと、
y[n + 1] = a * y[n] (mod m)
よって
y[n + 2] * y[n] - (y[n + 1])^2 = 0 (mod m)
これにより、y[n + 2] * y[n] - (y[n + 1])^2 を十分な数の n について集め、最大公約数をとれば、m が求められる。
あとは、y[1] = a * y[0] (mod m) を解いて a を出して、x[1] = a * x[0] + b (mod m) を解いて b を出すだけ。
最初の10回くらいは聞いて、それをもとに m, a, b を求め、乱数列を出す。
10回連続で正解すると、フラグを出してくれた。
flag is ALEXCTF{f0cfad89693ec6787a75fa4e53d8bdb5}
書いたスクリプトはこんな感じ。
#!/usr/bin/env python def gcd(a, b): if a < b: return gcd(b, a) while b: a, b = b, a%b return a def egcd(a, b): x, lx = 0, 1 y, ly = 1, 0 while b != 0: q = a // b a, b = b, a % b x, lx = lx - q * x, x y, ly = ly - q * y, y return lx, ly x = [ 4251151823, 2502705517, 4101273005, 1396379746, 4159332548, 3671236567, 433240385, 465003001, 2767252763, 952274152 ] # x[i + 1] = a * x[i] + b (mod m) # y[i + 1] = a * y[i] (mod m) y = [] for i in range(len(x) - 1): y.append(x[i + 1] - x[i]) # z[i] = y[i + 2] * y[i] - (y[i + 1])^2 = 0 (mod m) z = [] for i in range(len(y) - 2): zz = y[i + 2] * y[i] - y[i + 1] * y[i + 1] if zz < 0: zz = -zz z.append(zz) m = z[0] for i in range(len(z)): m = gcd(m, z[i]) for i in range(len(y)): while y[i] < 0: y[i] += m # p * y[0] + q * m = r (mod m) # p * y[0] = r (mod m) p, q = egcd(y[0], m) r = (p * y[0]) % m # y[1] = a * y[0] # p * y[1] = a * p * y[0] = a * r a = ((y[1] / r) * p) % m # a * x[0] + b = x[1] (mod m) # b = x[1] - a * x[0] (mod m) b = (x[1] - a * x[0]) % m print "check y" yy = [] yy.append(y[0]) for i in range(len(y) - 1): t = (a * yy[i]) % m yy.append(t) print y[i + 1], yy[i + 1], (y[i + 1] - yy[i + 1]) print print "check x" xx = [] xx.append(x[0]) for i in range(len(x) - 1): t = (a * xx[i] + b) % m xx.append(t) print x[i + 1], xx[i + 1], (x[i + 1] - xx[i + 1]) print print "show x" xx = [] xx.append(x[0]) for i in range(29): t = (a * xx[i] + b) % m xx.append(t) for i in range(len(xx)): print '{0}\t{1}'.format(i, xx[i])
次CTFに参加するときは暗号以外も解きたい。
2017年書き初め
正月を過ぎてしまったが、新年ということで初心者ながら短歌を詠んだので記事にする。
55 31 db eb 13 2d 80 33 e1 01 78 08 2d f0 c7 67 58 79 f2 43 89 d8 5d c3 6a 0d 58 cd 80 eb ed
ソースは次の通り。
.intel_syntax noprefix
.section .text
.global main
.type main, @function
main:
push ebp /* 1 */
xor ebx, ebx /* 2 */
jmp 4f /* 2 */
1: sub eax, 0x01E13380 /* 5 */ # 365 * 24 * 60 * 60
js 3f /* 2 */
2: sub eax, 0x5867c7f0 /* 5 */ # 2017-01-01 00:00:00 JST
jns 1b /* 2 */
inc ebx /* 1 */
3: mov eax, ebx /* 2 */
pop ebp /* 1 */
ret /* 1 */
4: push 0x0d /* 2 */
pop eax /* 1 */
int 0x80 /* 2 */
jmp 2b /* 2 */
現在時刻を取得し、2017年であれば終了ステータス0で正常終了し、そうでなければ終了ステータス1で終了する。
上のソースを in2017.S というファイル名で保存し、動作確認をしてみる。
$ gcc in2017.S -o in2017 -masm=intel -m32 $ ./in2017 && echo 2017 2017
今は 2017 年のようだ。 時刻を変えて確認する。
$ sudo date -s "2016-12-31 23:59:59"; ./in2017 || echo "not 2017" 2016年 12月 31日 土曜日 23:59:59 JST not 2017 $ sudo date -s "2017-01-01 00:00:00"; ./in2017 && echo "2017" 2017年 1月 1日 日曜日 00:00:00 JST 2017 $ sudo date -s "2017-12-31 23:59:59"; ./in2017 && echo "2017" 2017年 12月 31日 日曜日 23:59:59 JST 2017 $ sudo date -s "2018-01-01 00:00:00"; ./in2017 || echo "not 2017" 2018年 1月 1日 月曜日 00:00:00 JST not 2017
確かに2017年かどうかを判別できている。
初めは2017年であれば「🐓」とでも表示する短歌を作ろうと思ったのだが、力不足で完成させられなかった。「🐓」と表示する代わりに、ジャンプ系の命令を多く配してみた。5句中4句にジャンプ命令が含まれている。
書き初め風に言えば、「飛躍の年」だ。
幸多き年になりますように。
場阿忍愚CTF writeup (1)
少し前まで開催されていた場阿忍愚CTFの writeup を淡々と書いていく。 結果としては craSH2 の一問だけ解けなかった。頑張ったが悔しい。 しかし無知な状態で始めたので一通りどのジャンルにも手が付けられるようになったのは収穫だった。 世界一楽しい和風CTFを運営してくださった方に感謝したい。
量が多くて一度に書ききれなかったので、ひとまず芸術、二進術、暗号術、攻撃術までを記事にする。 練習と兵法術に関しては省略する予定。
芸術
ワットイズディス？
なんとなく読めるが篆書。
大和世幾由利天伊と書いてある。
ちなみに大和以降の文字はちゃんと平仮名の字源に沿った漢字が選ばれている模様。
「大和セキュリティ」と提出して正解。
cole nanee?
それっぽかったので特に調べることもなく「忍」と入れたら当たった。
Lines and Boxes
はじめはパーツを並び替えて漢字を作るのかと思ったが違う。
よくよく見ると A とか L とかアルファベットが見えて、英単語だと気づく。
「WORD PLAY」と提出して正解。
Why want something more?
この辺りから書について真剣に調べる必要が出てくる。
日本インターネット書道協会の早見表で草書のいろはを頭に叩き込む。
右の字は奴、如、妃など女偏の字にあたりをつけ、左の字は疋に近いので是を疑う。
問題タイトルからして哲学・宗教感が滲み出ているので、如や是などに絞って検索をかけてみると画像検索で同じ内容の作品を発見（第三十五回何有展）。
フラグは「如是」。
和の心が足りずに右から読むことにしばらく気付けなかったのは痛恨だった。
毎日使う
画像検索にかけるもダメ。 "goku tatoo" などと無駄に検索してもダメ。 草書一覧などと画像検索の海をさまよっている間に気の文字が一致することに気付く。 しかし「気」を提出しても正解にはならない。 よくよく見ると下半分が米の字になっていたので、旧字体の方の「氣」を提出したら正解できた。
Extreme Shodo POWER!!
見るからに五文字なので一文字ずつ特定していく。
結論から行くと左から氣、之、呼、波、和。
「氣」は文字を切り取って色を反転させて画像検索にかけると似た漢字が入ったロゴを発見。
悦氏という会社？のロゴに入っていたのでその会社のサイトを調べた結果特定した。
「呼」と「波」は篆書のようだったので、判子屋さんのサイトを軽く使わせてもらって部首、旁の順で特定した。
「和」に関しては右から筆が入っており不自然ということに気付いたため（大和魂で気付ける）、左右に反転させると「和」に見えた（和の心）。
残った「之」は確証はないが筆の並びからそれにしか見えなかった。
漢字のまま提出しても正解にならない。
タイトルの "POWER"、問題文の "get bigger"、そして "きのこ（氣之呼）"から「きのこパワー」が連想されたのでこれを提出したところフラグだった。
二進術
壱萬回
64bit ELF なので実行してみると、簡単な四則演算をさせられる。
タイトルから察するに一万回しないとフラグが出なさそうなので、とりあえず gdb で逆アセンブルしてみる。
showFlag という如何にもな関数を呼び出しているので、これの中身を見てみると一文字ずつ putchar で出力している。
putchar の引数を並べてやればフラグが出てくる。
DxLib遊戯如何様
オセロの Windows バイナリなのでとりあえず遊んでみる。 AI はそれほど強くないので普通に勝てるが、勝ってももう一回初めからになる。
OllyDbg でステップ実行しながら、勝利判定をしている気配がある箇所とオセロの盤面を記録している領域を特定。 盤面のデータは4バイトにつき1マスになっており、値は 0, 1, 2 がそれぞれ駒無し、黒、白に対応している。 勝利判定の直前にオセロの盤面を黒く塗りつぶすと完全勝利できた。 ただし一回勝っただけではフラグは出てこない。 何回かいじっていて盤面の領域の隣に勝利回数を記録する4バイトがあることに気付いたので、ここに0x7FFFFFEを入れた上で盤面を黒く塗りつぶす。 すると次の勝負から背景にフラグが表示された。
↓ 記念写真
Unity遊戯如何様
自分が手を付けたときには既にヒントが出ていたので、ヒントに従って Assembly-CSharp.dll を逆コンパイルする。
さらにヒント通り GUIManager を見ると、フラグは its_3DGame_Tutorial に見える。
しかしこれを提出しても正解にならない。
ふと同梱されていたゲームのキャプチャー画像を見ると、"Hint" という文字列を渡されたラベルのところが "HINT" と表示されている。
どうやら大文字にどこかで変換しているようなので、先ほどのフラグを全て大文字にしたところ正解した。
解読術
image level 5
一文字ずつ画像になっているので並び替える。
更新時間順にソートすると "KOBE-GYU" になる。これがフラグ。
自力で並べ替えて "KOBEGYU-" と提出してダメだったのはいい思い出。
Ninjya Crypto
神代文字と言われる忍者の暗号らしい。
やまといえば、と書いてあるので「川」と答える。
Decrypt RSA
640bit の公開鍵と、それで暗号化されたであろうファイルが与えられる。
片方の素数が小さい値であることを祈り素因数分解を試みたがダメだった。
途中で素因数分解の結果が公知であることに気付く。
https://en.wikipedia.org/wiki/RSA_numbers#RSA-640
後は復号するだけなので自力で復号を試みた。
#!/usr/bin/env python
def extended_euclidean(a, b):
r0 = a
r1 = b
s0 = 1
s1 = 0
t0 = 0
t1 = 1
while r1 > 0:
q = r0 / r1
r2 = r0 % r1
s2 = s0 - q * s1
t2 = t0 - q * t1
r0 = r1
r1 = r2
s0 = s1
s1 = s2
t0 = t1
t1 = t2
return (s0, t0)
def main():
n = 0xae5bb4f266003259cf9a6f521c3c03410176cf16df53953476eae3b21ede6c3c7b03bdca20b31c0067ffa797e4e910597873eef113a60feccd95deb5b2bf10066be2224ace29d532dc0b5a74d2d006f1
p = 1634733645809253848443133883865090859841783670033092312181110852389333100104508151212118167511579
q = 1900871281664822113126851573935413975471896789968515493666638539088027103802104498957191261465571
e = 65537
m = (p - 1) * (q - 1)
st = extended_euclidean(m, e)
d = (st[1] + m) % m
f = open("flag.txt")
data = f.read()
c = 0
for i in range(len(data)):
c = c * 0x100 + ord(data[i])
a = pow(c, d, n)
flag = ""
while a > 0:
flag = chr(a % 0x100) + flag
a = a / 0x100
print flag
if __name__ == '__main__':
main()
復号した結果謎のバイト列のあとに FLAG_IS_WeAK_rSA と出てきた。 バイト列を無視して提出したら正解した。 （他の方の writeup 見ると真面目に秘密鍵作るのが正解だったらしい）
Zach! Take a nap!
gen.py の中を見ると次のようなコードがあるので、与えられた b, c から bits を復元する問題になっている。
c = 0
for i in xrange(n):
if bits[i] == "1":
c += b[i]
初めは動的計画法あたりでいくのかと考えもしたが、あまりに数字が大きすぎて解ける気がしなかった。
調べているうちに、subset sum problem などと言われる類の問題であり、さらに具体的に言うと Merkle Hellman knapsack という暗号であることが分かった。
gen.py に書かれているとおり、w_i > w_1 + ... + w_{i-1} となるような数字列を暗号化したい情報のビット数分だけ求めておく（このような性質を super-increasing というらしい）。これを q > w_1 + ... + w_n を満たす適当な数 q と適当な数 r を使って公開情報となる b[i] = r * w[i] % q に変換する。暗号化ははじめに引用した通りビットが1の部分だけ b[i] を足し合わせていく。
r と q が既知の場合は d = c * r^(-1) % q として b[i] の和から w[i] の和に変換できる。w[i] は super-increasing なため、iが大きい順に d >= w[i] かどうかを調べていく。
このとき、もしそうであれば bit[i] が 1, そうでなければ bit[i] が 0 であることが分かるため、元のビット列が復元できる。
r, q が未知の場合は上記の手順をとることができないため、復号は容易ではないが幾つか破る方法が存在する。
この辺りの話は格子の数学と関わりが深いらしい。
初めはこちらの解説に沿って復号を試みた。
ざっくり言ってしまえば、{[1, 0, 0, ..., 0, b_1], [0, 1, 0, ..., 0, b_2], ..., [0, 0, 0, ..., 1, b_n], [0, 0, 0, ...,0, -c]} という基底からなる格子のうち原点から最も近い点を探せば、その点の座標が復元したいビット列に対応することを利用する。
格子のうち原点から最も近い点を探す問題は Shortest vector problem (SVP) として知られており、LLL Algorithm を使って近似解を求めることができる。
ちなみに厳密解を求める問題は NP 困難らしい。
初めは LLL Algorithm を自力で実装して N=10 くらいであれば解けることを確認したが、いざ問題を解こうとするとあまりの遅さに絶望した。
諦めてライブラリなど探し回った結果、sagemathというツールがあったのでそれを使った。
LLL() という関数がいて高速に LLL Algorithm を終わらせてくれるので胸躍らせたが、実行してみると厳密解にまではたどり着いてくれず答えを出すことはできなかった。
考えてみればあくまでも近似解法なので解ける保証はない。
試した感覚だと次元が小さいうちは答えを出せる確率が高いが、次元が 100 を超えてくると基本的に答えは出ない。
ここで一回心が折れた。
しかしそれでも諦めきれなかったので、Shamir Attack という攻撃方法を試してみることにした。
何個か文献を読んだので参考にしたものを貼り付けておく。
http://arxiv.org/ftp/arxiv/papers/1210/1210.8375.pdf
https://www.ifor.math.ethz.ch/teaching/lectures/integer_prog_ss10/chapter06
http://cacr.uwaterloo.ca/techreports/2004/cacr2004-08.pdf
先の方法では bit[i] を直接求めようとしたが、Shamir Attack では r, q に相当する数を見つけることで暗号を破る。
r, q と完全に一致しなくても、掛けて剰余をとることで superincreasing な配列を復元できれば、復号することは可能になる。
詳細は省くが、|b[i]/b[0] - k[i]/k[0]| が極めて小さくなるような k[i] を求め、(k[0] * b[i]) % b[0] として b を superincreasing な配列に変換することができる。
|b[i]/b[0] - k[i]/k[0]| が極めて小さくなるような k[i] を求める問題（有理数が複数与えられたとき、同一の分母で極めて近い値の有理数を求める問題）は simultaneous diophantine problem と呼ばれており、これも LLL アルゴリズムによって解くことができる。
simulatenous diophantine problem を解くため、次のような sage スクリプトを書いた。
LLL アルゴリズムでは近似解しかでないので、精度が高くなるように a[0, n-1] の部分は調整してある。
f = open('b.txt')
t = f.readline().rstrip().split(', ')
t = [ long(x) for x in t ]
f.close()
f = open('c.txt')
s = long(f.readline().rstrip())
f.close()
n = len(t)
a = Matrix(ZZ, n, n)
for i in xrange(n-1):
a[0, i] = t[i+1]
for i in xrange(n-1):
a[i+1, i] = -t[0]
# smaller, more precise approximation
# a[0, n-1] = int(floor(pow(t[0], 1.0/n)))
a[0, n-1] = int(floor(pow(t[0], 1.0/n))/2)
f = open('m.txt', 'wb')
f.write(a.str())
f.close()
b = a.LLL()
# find the shortest vector
m = -1
r = -1
for i in xrange(n):
s = 0
for j in xrange(n):
s += b[i, j] * b[i, j]
if m == -1 or m > s:
m = s
r = i
# check if simultaneous diophantine problem is correctly solved
k = [0] * n
k[0] = b[r, n-1] / a[0, n-1]
for i in range(1, n):
k[i] = (k[0] * t[i] - b[r, i-1]) / t[0]
for i in range(1, n):
print float(t[i])/t[0], float(k[i])/k[0]
無事 simulatenous diophantine problem が解けたので、
上記スクリプトの k[0], t[0] を U.txt, M.txt として保存して次のスクリプトで superincreasing な配列を作成し、フラグを出した。
#!/usr/bin/env python
# -*- encoding: utf-8 -*-
import sys
def input_b():
f = open('b.txt')
line = f.readline()
bstr = line.split(', ')
b = [long(s) for s in bstr]
f.close()
return b
def input_c():
f = open('c.txt')
line = f.readline()
cstr = line.rstrip()
c = long(cstr)
return c
def input_U():
f = open('U.txt')
line = f.readline()
cstr = line.rstrip()
U = long(cstr)
return U
def input_M():
f = open('M.txt')
line = f.readline()
cstr = line.rstrip()
M = long(cstr)
return M
def main():
b = input_b()
c = input_c()
U = input_U()
M = input_M()
b2 = [0] * len(b)
for i in range(0, len(b)):
b2[i] = (b[i] * U) % M
c2 = (c * U) % M
used = [0] * len(b)
p = c2
for i in range(len(b)-1, 0, -1):
if p >= b2[i]:
used[i] = 1
p -= b2[i]
else:
used[i] = 0
q = c
for i in range(1, len(b)):
if used[i]:
q -= b[i]
if q > 0:
used[0] = 1
q -= b[0]
flag = hex(int(''.join([str(bit) for bit in used]), 2))[2:-1].decode('hex')
print flag
if __name__ == '__main__':
main()
実行すると flag={AdiShamirSpoiled} と出てきた。
とても疲れた。
攻撃術
craSH
スタックを壊した。
与えられたシェルでは、入出力のリダイレクトを読み込むときに、'>' もしくは '<' を見つけ、その後ろのスペース以外の文字列を読み込んだ後、読み込みが終わった箇所をスペースで塗りつぶす (get_redirect)。
スペース以外の文字列を読み込む関数 (extract_str) は、左から見ていって ' ', '>', '<', '\0' のいずれかが見つかったところを文字列の終端として読み込む。
そして、終端の次の位置を返す。
get_redirect で塗りつぶすスペースの箇所は '>' または '<' から extract_str の返り値の直前までとなっている。
つまり、状況によっては本来消されるべきではない '>', '<', '\0' がスペースに変換されてしまう。
試しに次のようにコマンドを打ってみる。
$ echo foo > a $ echo bar > b $ cat < a>b bar
3つ目のコマンドは本来何も標準出力されないはずだが、入力のリダイレクトを読み込んだ後、'>' が ' ' に変換されて
cat b
が残り、bar が標準出力される。
幸運なことに文字列の終端文字 '\0' も消すことができるので、これを利用して入力用のバッファ (input) のところでオーバーフローを狙う。
その一連の流れがこれ。
$ echo foo > a $ echo aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa > < a $ $ ls `�.�� a
なんでもいいが、あらかじめ入力リダイレクト用のファイルを作っておく。
fgets で最大127バイト読み込まれるので、改行は input の中に入らず、input の最後6バイトは > < a\0 となる。
入力リダイレクトを読み込んだ時点で、終端の '\0' が ' ' に変わる。
次に出力リダイレクトを読み込むと、input の128バイトの領域を超えた先の ' ' 以外の連続する文字列がリダイレクト先として読み込まれてスペースで塗りつぶされる。
ls でファイルを確認すると、怪しげなバイト列がファイル名になったファイルが存在する。
一回投げただけではシェルが落ちないので、このコマンドを何度も投げ続けると最終的にスタックの領域外に書き込もうとするのかエラーで落ちる。 python で適当な間隔で投げ続けるようにしてしばらく待ったらフラグが出てきた。
flag={NoMoreBashdoor}
これで解けたのは良かったが、結局ヒープオーバーフローの方法がわからず craSH 2 に歯が立たなかったのは残念。
Ninja no Aikotoba
合言葉を一個ずつ答えていく。
一つ目と二つ目はアスキーコード表など参照して文字におこすだけ。 それぞれ 'Yama' と 'too'。
三つ目は encrypt 関数が微妙に難読化されているが、配列の添字演算子[] のオペランドが交換可能なことに注意すると、やっているのはこれだけ。
for x in range(6):
result[x + 6] = ((ans[x] & ans[x+6]) << 1) + (ans[x] ^ ans[x+6])
result[x] = ans[x] - ans[x + 6]
表示される最初の6つの数字から、ans[x], ans[x+6] の差分がわかるので、アルファベットの中から虱潰しに合うものを探す。 答えは 'KansaiTanaka'。
四つ目は MD4 でハッシュにされているが、四文字だとわかっているので全探索する。 答えは 'Zach'。
最後はノーヒントだが、is_matched のバグで潜り抜けられる。
strcmp の返り値は負か0か正かで判定すべきところが、-1 か 1 なら一致しないと判定されている。
いろいろと試したところ、24文字以内であれば異なる文字列の場合1か-1が返ってくるが、24文字目まで同じで25文字目以降が異なる場合は、最初に異なった文字のアスキーコードの差が返ってくる。
YamatooKansaiTanakaZachまでで23文字あるので、24文字目をa~z, A~Zとして、25文字目はa,Aの2種類で試し後ろに適当に8文字以上付け加えればOK。
自動で流し込んだところ、'xaaaaaaaaaaaaaaaaaaaaaaa' を入力したところでフラグが出た。
flag={GetsuFumaDen}
