きゅうり。

主にCTF関係のことを書いていく気がします

Codegate 2016 OldSchool writeup

pwn CTF

いわゆる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

CTF crypto

SECCON2016予選のcrypto 300の問題、Alpha Complex1のwriteupです。

4月からに向けてm1z0r3用のcrypto for beginnersみたいな記事（チーム用なので公開予定なし。たぶん。）を書いてたんですが、執筆にあたって色々調べてたら「これAlpha Complex解けんじゃね？」みたいな感じになったのでやってみたら解けました。 

12月の記憶を呼び戻して書いてるので、問題の説明とか間違ってたらすいません。

 

問題

問題文は省略します。Complex.pyとserver.pyという2つのファイルが渡されます。

実はやっていることは単純(?)で、RSA暗号を複素平面上で定義しています。フラグをx座標、こちらから送った値をy座標として、{\displaystyle C \equiv (x+y*I)^e \pmod{N} }を計算した結果が返ってきます。Nとeはわかっていて、今回のeは0x1337です。

なお、便宜上x座標y座標と呼んでいますが正しいかは謎なのでそこは目を瞑ってください。

 

解法

暗号文Cの式を展開すると、以下のようになります。

{\displaystyle (x^e + a_{e-1}Ix^{e-1} + a_{e-2}(-1)x^{e-2} + ... - C)  mod  N = 0 }

この式には実部と虚部があるのでわけて式を定義してみます。

{\displaystyle g_r(x) = (x^e + a_{e-2}(-1)x^{e-2} + ... - C_x)  mod  N }

{\displaystyle g_y(x) = (a_{e-1}Ix^{e-1} +  ... - C_y)  mod  N }

この2つの式は、xにフラグ(mと定義)が入るとき当然ながら0となります。つまり言い換えると、{\displaystyle g_r(x),g_i(x)=0}はmを根に持ちます。なので以下のように表現できます。

{\displaystyle g_r(x)=(x-m)G_r(x)}、{\displaystyle g_i(x)=(x-m)G_i(x)}

これを見ると、2式の最大公約式をとればx-mが出てきてフラグを得ることができそうです。

 

というわけで実際に試します、が、いきなり本番の値でやると大変なのでまずは自分で用意したフラグと暗号文でやります。なおここではe=5にして暗号化してます。

これを実行してみるとちゃんと平文を得ることができました。なので後は本番用の値でやるだけなのですが、21~26行目を見てわかる通り展開した式をベタ書きしてます。本番のeでこれをやると0x1337乗なのでとんでもないことになります。

苦肉の策として、

  1. expandしたものを一旦テキストとしてファイルに出力
  2. 出力したものを読み込み、文字列として実部虚部に分割（虚部のIは削除）
  3. z_real=`実部` z_imag=`虚部`みたいな形でまたファイルに出力（expとする）
  4. 先ほどのsolverの24行目まで書いたものを用意（solver.sage）
  5. 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

CTF crypto

2/25(土)のkatagaitai勉強会に参加してきました。感想文とか書くのは苦手なので、かわりにwriteupを書こうと思います。writeupと言いつつ自分が詰まったりしたところだけをまとめた自分用メモという説もあるけど。

 

※2017/2/28 22時頃追記：最初は密度が計算できないと書きましたが、できたので修正しました

はじめに

この記事は数学がまったくわからない人が書いています。なので、だいたいフィーリングで書きました。間違っている点が多々あるかもしれませんが、指摘していただけると幸いです。

また、あくまで勉強会に参加した前提で書いており、資料すら見てないとまったくわからないと思うので一応リンクを貼っておきます。

 

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の宿題とか他のジャンルもこれからがんばります）

はじめまして

はじめまして、Kyuriです。学生のCTFチーム、m1z0r3に所属してます。（2017年3月現在)

CTF関連のことに取り組んでいく中で、ブログがあったほうが便利そうな気がしたのでなんとなく作りました。飽きるまで書きます。

 

CTFを知ったのはちょうど2年くらい前、まともに取り組むようになったのは1年半くらい前です。チームでは主にcryptoを解いており、最近はpwnが楽しくて勉強してます。

 

そんな感じで、よろしくお願いします。