0CTF 2017 writeup その2
その他writeup
0CTF 2017 writeup その3 - きゅうり。 (EasiestPrintf)
0CTF 2017 writeup - きゅうり。 (integrity, oneTimePad)
今更ですが、本番中には解けず、後から解いたもののwriteupシリーズです。
char
自明なbuffer over readがあり、offset=32で簡単にEIPが奪える。ただし入力はprintableなもの(asciiで0x20〜0x7e)しか受け付けないので、その範囲内でROPを組む必要がある。
libcが固定アドレスでprintableなアドレスに読み込まれるので、その中の使えるgadgetを組み合わせて頑張る。rp++の結果からprintableなものだけ抽出するスクリプトを適当に書いて、あとは泥臭く組み立てていっただけなので特に説明はないです。
ecxは{"/bin/sh",NULL}ってずっと思ってたものの、特になにもしなくてもシェルとれた。知見。
flag{Asc11_ea3y_d0_1t???}
Volga CTF 2017 Quals writeup
m1z0r3として参加して、450ptsで188位でした。
予定があってあまり時間がとれませんでしたが、cryptoを2問解いて250pts入れたのでそのwriteupを書きます。(今回はスクリプトは無し)
VC (crypto 50pts)
png画像が2枚渡される問題。B.pngはA.pngになんらかの情報が追加されてるように見えるので、2枚の差分をとるとフラグ。
Curved (crypto 200pts)
楕円曲線DSA(ECDSA)を用いた署名を使ってコマンド実行を行うサーバが動いており、そのスクリプトとexit、leaveコマンドの署名が渡される。
lsやcatなどを実行するには、正しい署名を生成する必要があるが、署名をするには秘密鍵が必要となる。
一般にECDSAでは署名を施す際にランダムな値kを用いる必要があり、これが固定値だと秘密鍵が逆算可能となってしまう。(詳しくは楕円曲線DSA - Wikipedia)
今回渡されたexitとleaveの署名を見ると、rの値が等しいことからkが同一であったことがわかる。したがって秘密鍵が逆算でき、得られた秘密鍵からcat flagを実行すればフラグが得られる。
実はこの問題、過去にチーム内CTFで出題したものとまったく同じコンセプトだったのでECDSAの処理を見た瞬間に見当がついたりもした。
所感
Oracleはやればできそうだったり、Casinoは面白そうな問題だなぁと思った。が、cryptoはどれもPoWがめんどくさすぎて途中で投げ出した。(予定があったのもあるけど)
ちゃんとPoW用のライブラリは用意しておくべきですね...
0CTF 2017 writeup
0CTF 2017にm1z0r3として参加しました。
266ptで111位でした。WelcomeとServeyを除いた222ptのうち189ptを入れました。
cryptoのintegrityとoneTimePadを解いたのでそのwriteupです。
その他writeup
0CTF 2017 writeup その3 - きゅうり。 (EasiestPrintf)
0CTF 2017 writeup その2 - きゅうり。 (char)
integrity (crypto 75pt)
・register
こちらからnameを送信すると、
md5(pad(name))+pad(name)
をAES-CBCで暗号化して、IVと暗号文が送られてくる。
ただしpad(name) == pad("admin")は弾かれる。
・login
こちらからIVと暗号文を送信すると、それを復号してmd5チェックをした後unpadして出てきたnameとしてログインする。
nameがadminならフラグ。
解法
name = md5(pad("admin")) + pad("admin")としてregisterして、返ってきた暗号文からIVを除いてそのままloginに送信すればフラグ。
flag{Easy_br0ken_scheme_cann0t_keep_y0ur_integrity}
oneTimePad (crypto 114pt)
keygenという自作PRNGから乱数を生成しOTPにより暗号化したもの。keygenでは乱数をseedとしてprocess関数から乱数を生成しているので、process関数が鍵になってくる。
process関数はの元でを返しているだけ。なお生成多項式はP。また、すべての演算は上で行われるのでxorと+は等価。
これを数式で表すと、
ただしとする。
これを利用して与えられた暗号文を変形していく。ただし、fake_secretからkey2,3は既に計算済みとする。
したがって、あとはの平方根をとればよい。
一般にの元で平方根をとるには、n-1回平方をとればよい。
flag{t0_B3_r4ndoM_en0Ugh_1s_nec3s5arY}
所感
oneTimePadは最初見たときに数学系の問題かな〜と思いつつxorこねくり回したり1bitずつ求めようとしたりして時間を浪費したのがもったいなかった。 さらに、平方根とるだけって気づいてからn-1回平方すればいいことを知るまでに無駄に時間を使った。
ので、この2問は瞬殺できるぐらいにはなりたい。ただ無駄に苦戦したおかげでoneTimePad解けたときはうれしかった(こなみ)。
oneTimePad2も解きたかったけど式がより複雑になってて断念しました。
今回はほぼソロ参加みたいな状況でpwnが手付かずで残ってたのに1問も解けてないので精進💪
ED CTF my_sandbox writeup
解いたのでwriteupです。
プログラムとlibcが渡されてます。
事前確認
$ ./my_sandbox Your name please: hoge Welcome to my echo program! This program has an bug. I couldn't fix this bug... :( But, I developed sandbox for this bug. Hackers will never be able to get shell, haha! :) Enter your message: 1 Entered: 1 (snip) Enter your message: 10 Entered: 10 It seems cracker couldn't crack my program, I'm winner! See you.
入力をそのまま返すのを10回繰り返すようなプログラム。バグがあるけどsandbox化してやったからシェルとれないやろ???みたいなやつ。
バグがあると言っている通り、FSBがあります。
続いてchecksec
CANARY : disabled FORTIFY : disabled NX : disabled PIE : disabled RELRO : FULL
方針
FSBがあるので、まずは素直にlibcのアドレスをリークします。この時点で最後はret2libcに帰着しそうなことがなんとなくわかります。
あとはreturnアドレスを書き換えるためにスタックのアドレスをリークする必要があります。しかし、sandbox化(?)により、FSBは通常のスタックではなくmallocによって確保された領域(擬似スタックと呼称)で発生します。なので、都合よくリークできそうなアドレスが積まれていません。
ここで擬似スタックがlibcの直前にあることに注目すると、libcのベースアドレスから、入力した値が積まれる擬似スタックのアドレスが計算できます。そして計算したアドレスからsnprintfの第一引数にあたるアドレスを計算しリークさせることでスタックのアドレスがリークできます。
これを図解すると、snprintf(buf,size,user_input);
が呼ばれる際の擬似スタックは、
addr_buf size addr_user_input xxx xxx xxx xxx xxx user_input
となっており、libcのベースアドレスからuser_inputのアドレスが計算できます。これが計算できるということは通常のスタックにあるbufのアドレス、つまりaddr_bufが計算できるためスタックのアドレスもリークできます。
ここまでできたら後はリークしたスタックのアドレスからreturnアドレスの場所を計算して書き換えてsystemを呼んで終了。
Codegate 2016 OldSchool writeup
いわゆるbataさんのリストのeasyの問題。
チーム内の勉強会で解いたのでそのwrituepです。
まずは挙動確認
$ ./oldschool YOUR INPUT :hoge RESPONSE :hoge $ ./oldschool YOUR INPUT :%08x RESPONSE :000003fc
どうやら入力をそのまま返してくるだけのプログラムで、FSBがあります。
ちなみにソースコードも渡される?っぽいので、そっちを見ればFSBは自明です。
続いてセキュリティ機構のチェック。
CANARY : ENABLED FORTIFY : disabled NX : ENABLED PIE : disabled RELRO : disabled
NX有効。
方針
FSBがあるので、適当に情報をリークしてやればlibcのアドレスやstackのアドレスはわかりそう。各種アドレスがリークできれば、ret2libcでsystemを呼び出せば終わり。
ただし、これを実現するには2回FSBをする必要があります。(1回目でリーク、2回目でreturnアドレスの書き換え)
ですがプログラム自体はprintf(buf)直後に終了してしまうので、.fini_arrayを書き換えてmainをもう一度呼び出します。TW CTF 2016のgreetingを解いたことがあったのでここの発想はわりとすんなり出てきました。
あとはこれらを実装するだけ。
from m1z0r3 import * はsocket通信部分をpack, unpackを定義してるだけなので適宜置き換えてください。全部ローカルでのアドレスです。
後半のアドレス指定が雑感ハンパないのは許して。
SECCON2016 Qual Alpha Complex1 writeup
SECCON2016予選のcrypto 300の問題、Alpha Complex1のwriteupです。
4月からに向けてm1z0r3用のcrypto for beginnersみたいな記事(チーム用なので公開予定なし。たぶん。)を書いてたんですが、執筆にあたって色々調べてたら「これAlpha Complex解けんじゃね?」みたいな感じになったのでやってみたら解けました。
12月の記憶を呼び戻して書いてるので、問題の説明とか間違ってたらすいません。
問題
問題文は省略します。Complex.pyとserver.pyという2つのファイルが渡されます。
実はやっていることは単純(?)で、RSA暗号を複素平面上で定義しています。フラグをx座標、こちらから送った値をy座標として、を計算した結果が返ってきます。Nとeはわかっていて、今回のeは0x1337です。
なお、便宜上x座標y座標と呼んでいますが正しいかは謎なのでそこは目を瞑ってください。
解法
暗号文Cの式を展開すると、以下のようになります。
この式には実部と虚部があるのでわけて式を定義してみます。
この2つの式は、xにフラグ(mと定義)が入るとき当然ながら0となります。つまり言い換えると、はmを根に持ちます。なので以下のように表現できます。
、
これを見ると、2式の最大公約式をとればx-mが出てきてフラグを得ることができそうです。
というわけで実際に試します、が、いきなり本番の値でやると大変なのでまずは自分で用意したフラグと暗号文でやります。なおここではe=5にして暗号化してます。
これを実行してみるとちゃんと平文を得ることができました。なので後は本番用の値でやるだけなのですが、21~26行目を見てわかる通り展開した式をベタ書きしてます。本番のeでこれをやると0x1337乗なのでとんでもないことになります。
苦肉の策として、
- expandしたものを一旦テキストとしてファイルに出力
- 出力したものを読み込み、文字列として実部虚部に分割(虚部のIは削除)
- z_real=`実部` z_imag=`虚部`みたいな形でまたファイルに出力(expとする)
- 先ほどのsolverの24行目まで書いたものを用意(solver.sage)
- cat exp >> solver.sage; echo 27行目 >> solver.sage; echo 28行目 >> solver.sage
としました。
solver.sageは63MBになりました。
そんなものを貼るつもりは起きないですが、先ほどのsolverのパラメータを書き換えただけでやってる処理は同じです。
というわけでこれを実行することで無事フラグを得ることができました。
SECCON{3907c554839a6462b920f55274c159eea1949086}
あとがき
Alpha Complex2のほうはまだ問題すら見てないです...
あとこれ解いてたからcrypto for beginnersも書いてないです。許して。
katagaitai勉強会#7 Cryptoパート writeup
2/25(土)のkatagaitai勉強会に参加してきました。感想文とか書くのは苦手なので、かわりにwriteupを書こうと思います。writeupと言いつつ自分が詰まったりしたところだけをまとめた自分用メモという説もあるけど。
※2017/2/28 22時頃追記:最初は密度が計算できないと書きましたが、できたので修正しました
はじめに
この記事は数学がまったくわからない人が書いています。なので、だいたいフィーリングで書きました。間違っている点が多々あるかもしれませんが、指摘していただけると幸いです。
また、あくまで勉強会に参加した前提で書いており、資料すら見てないとまったくわからないと思うので一応リンクを貼っておきます。
本日のkatagaitai勉強会 #7 暗号編のスライドです。ナップサック暗号の解読方法について解説しています。#katagaitaiCTF https://t.co/6m1yGOuKV6
— trmr (@trmr105) 2017年2月25日
Backpacker's cipher easy modeは以前に解いたことがあり特に疑問点もなかったので省略します。
「数学のお話」以降で、当日理解できなかったところ、後から疑問に思えてきたところをメインに取り扱います。内容は以下の通りです。
・ナップサック問題を最短ベクトル問題に帰着させる
・LO法、CLOS法とは?
・Lazyを解く
・Backpacker's cipher extra modeを解く
・都合の良い格子を思いつく都合の良い頭がほしい
あと、ナップサックなのかナップザックなのかよくわからなので、記事内ではナップサックで統一します。
ナップサック問題を最短ベクトル問題に帰着させる
まずは今回のキモになるところです。ここが脳内でしっくりくるとすごく解きやすくなる気がします。と言っても、スライドp.37〜にほぼ載っていますが、一応。
おそらくここで詰まる場合、以下のように考えていると思います(当日の自分がそうでした)
「ナップサック問題を最短ベクトル問題と見て、それを解いて出てきたものがなんか答え(平文)になってる」
しかし実際はそうではなく、
「求めたい答えが最短ベクトルになりそうな格子を設定して、最短ベクトル問題を解くと答え(平文)が出てくる」
答えから設定してるんだからちゃんと平文が出てくるのは当たり前ですね。ちゃんと資料を読めば書いてあるんですが、なぜか当日の自分はここで一回詰まったので一応書いておきました。
LO法、CLOS法とは?
都合の良い格子の設定方法、ぐらいの感覚で捉えています。具体的な格子の設定方法については下記論文の3--4ページ辺りに書いてありました。
http://www.osakac.ac.jp/labs/yasuyuki/members2004/nasako/tn_files/pdf_files/isec200507.pdf
CLOS法はLO法の改良版で上位互換と捉えているので、基本的にCLOS法を使えば問題ないのかな、と思います。ここで0-1ナップサック問題という言葉がありますが、要は平文が0-1、ビット列であるということです。後で出てきますが、平文がビット列でない場合そのまま適用するのは難しそうです。
また密度の話がありますが、資料に書いてある通りの値を導出することができませんでした。どなたか導出できたら教えてください。
資料通りの計算でちゃんと導出できました。以下の通りに計算できます。
import math
# Lazy
n = len(eval(open("pubkey.text","r").read())[0])
max_a = max(eval(open('pubkey.txt').read()))
a = math.log(max_a,2)
print n/a
# 0.900711404738
# extra mode
n = len(eval(open("pubkey","r").read())[0])
max_a = max(eval(open("pubkey","r").read())[0])
a = math.log(max_a,2)
print n/a
# 1.21176891884
Lazyを解く
当日もらったソルバをそのまま使ってもつまらないので、上のCLOS法に書いてあった行列からやってみました。理解のために必要以上にコメントを入れてます。
元のCLOS法の行列をそのまま再現してるだけなので説明はいらないかと思います。判定条件とかも資料そのままです。特に問題なく解くことができました。
FLAG:lenstra_and_lovasz_liked_lattices
Backpacker's cipher extra modeを解く
色々ごちゃごちゃやってるように見えますが、46--48行目がポイントで、公開鍵aと暗号文encrypted_keyから平文xを求めるだけの問題です。これもLazyのソルバを使い回して解こうと試みましたが、いくつか問題が発生してうまくいきませんでした。
一番の問題は、密度が1を超えるということです。上で密度の導出がわからないということを書きましたが、適当に計算すると1.17くらいになりました。資料とは異なる値でしたが1を超えることはわかります。(ちなみにLazyは0.88になりました) 密度は1.21になります。
密度が1を超えると1つの暗号文に対して複数の平文が存在しうるということが資料にも書いてあります。本来この問題の平文xは0,1のみですが、最短ベクトルとして本来の平文ではないものが出てくる可能性があり、その最短ベクトルは0,1だけではなく適当な値が入っているはずです。(資料p.52より)
つまり、密度が1を超えるということは平文xが0,1だけとは限らないという厄介な状況に帰着します。
まず1つめの厄介な点として、最短ベクトルの判定が難しくなります。Lazyのときは±1、0という値以外とらないため判定に使えましたが、今回はなんでもとりうるためn列目が0という条件しか使えず、最短ベクトル候補がたくさんでてきます。しかしこれだけなら全部確かめればいいのですが、まだ他に根本的な問題が発生します。
2つめの厄介かつ致命的な点として、求めたいベクトルが出てきません。そもそもなぜ求めたいものが最短であったかを振り返ると、0-1ナップサック問題であるためBx-tというベクトルの長さが高々√nであったためです。CLOS法では行列を作る際にrnという変数として√nをかけているため、他のベクトルはすべて長さが√n以上になることが期待でき、それ故に最短ベクトルして導出されていました。
しかし今回は平文が0,1でないため、2x-1という項がそのまま出てきてしまい、求めたいベクトルの長さが比較的長くなってしまうと思われます。そのため最短にならず、CLOS法をそのまま適用しても平文を求めることができません。
というわけでゴチャゴチャ書きましたが、CLOS法を使うのを諦めて、求めたいベクトルが短くなるように頑張ります。
まず、2x-1という項が問題なので2倍することをやめます。次に、1を引く必要もないので引くことをやめます。この時点でxだけになったのでこれ以上は短くできません。また、√nという値をかけていたところを適当に大きな値に変えます。最後に、最短ベクトルの判定条件を増やすために1だけの列を付け加えます。
というわけで以下のような行列を作ります。
1 0 0 0 ... 0 ca1 0 0 1 0 0 ... 0 ca2 0 ⋮ 0 0 0 0 ... 1 can 0 0 0 0 0 ... 0 -cS 1
結果的には資料p.53の基底とほぼ等しいですね。判定条件等も一緒です。以下ソルバです。
結局資料に沿って解く形になってるので解説はいらないかと思います。
FLAG:TWCTF{Hilarious_cruising}
都合の良い格子を思いつく都合の良い頭が欲しい
「都合の良い格子を使えば答えが出るのはわかった。問題は都合の良い格子をどう思いつくか。」
資料を読んでるときに思ったことです。
しかし、extra modeの方を解く際に色々格子をいじってたら、都合の良い格子に帰着することができました。現在の結論ですが、おそらくこんな感じと考えています。
・0-1ナップサック問題はCLOS法を使っておけばいい
・そうでない場合はなるべくベクトルの距離が短くなるように頑張る
今後それで解けなかったらまた考えます。
さいごに
数学がまったくわからず、格子理論という言葉を見ただけで逃げ出していた自分でもここに書いたぐらいのことは理解することができました。家でじっくり資料を読んだらちゃんと理解でき、改めて見てもわかりやすくまとまっていると感じました。本当にありがとうございました。
(SHA-1の宿題とか他のジャンルもこれからがんばります)