#17 Math II (write-up)

問題

ksnctf.sweetduet.info

問題名の通り、数学の問題。

解法

xの値が3913桁もあるため、総当たりで解こうとすると無限に時間がかかる…。
ということで、今回は二分探索で解いてみた。
二分探索のアルゴリズムについてはwikiを参考にした。

最小値にはxが3913桁よりも小さい適当なyの値を設定し、最大値にはxが3913桁よりも大きい適当なyの値を設定する。今回はそれぞれMIN=10000000000000000000000000000000000000、MAX=10000000000000000000000000000000000000000と設定し、以下のようなプログラムを作成した。

X = 2748040023408750324411119450523386950660946398855386842074606380418316981389557916980086140301887947706700698930830779678048474531538039134089675000612962004189001422715316147779554460684462041893073445562829316520071658956471592707597247194589999870235577599858641217209525243986680999448565468816434633441308131788183291153809253610695081752296732033298647222814340913466738465892791206393936089466068684809286651197884210187525269355913763182559833600649423167126622527203197940618965341674710993871930168655984019611567024681974446413864111651893113475795042753452042221938667445789706741508160949598322950403760355305740757495122850819958219745478009476321531997688864567881328571570240278649150057863614800304034452842380274161491817926949213762740941829027657311016236224840157689532838274458699038989430527152474540367086746579688987076042252804910459873636444778218434530247647760637770881658596016745610672707638583665201858035977485748775481448417394363801163664632527695106599930657132405666766730530997168969743603771751166591137309462845077320233889570871715682231576283485837079838925927845291565664213349164253238166525895494203520538861102027123057706413048503799598270037162337386882901940037500301040636118696723417952777083334146545991127148023661461455142653367976629308434919237639329808504561590505864983890552051987234096577849288536293631380950881787840319976968198704697701966146561843819563765280293823120028941691560894722032503932540560461794190408016359786029679686957711035845785762377768203676919060935155382104877926736292611130243057909501332528103700463961697932230444978571571548190911155741113324573679444638703192583211952316173122745153529542339170631749363019742630339456502772150867703497326010832217054307087826776870481852284816747574983354077170761286175754243223519482572371717625453405597596790583499145036350302955327521461648262537855645876387858201576107385450844609238327605056916243564458120595540013872075267316304999752934829122583429168665162743589578036716137649553856654996867605565582594039606555708509284616434305172100068285925706963351193710675088846623856567419346569873886366829228933416064828304824833588800700991940600359503453201939139663042787644390810036292415117714919711827630953170559057272633043896443339064006637234499569232762828723613158050896065355005775876910820958296537497557737916521798848004761708690607167573807307291510879396794861418856342383200817566360552405183866698509354047737422523253071467100174078467454351746681775690022510266842064132386305358891086764558955802257688899610117102582837343655907837234028334304769930810792079059216436489942124896722072971246781926084943216581585837400274934104255861076781834022322597318553478829221018993823759479304536464719195824731739557957722610850860725276329731096193041588880149698625007746958307472328762247329346952956782896672291984502790479223886842985800649168009891087704339671376795754679245964575179873102014722210341771266309855717402003098724600141420936602986387680283404929020457247001371544838792904086327642729822000980710278752669990211765608002907900832262843253793831541691706704836397397798869236939393204666502455311086553874765248631328418556164635889080357612074921368044611251307530838475840480894307375072202500636365832958938363048173011687247738236161480446422712858040552310006617829659443118541556912488329721272939472554467384944920030182974546889304443711910957344160175437149714520561879951921970795705645045936350875827028675689840953101114431720413756855193291198455863087675930604549263160397353363504597829924339064422377323361781720524799661393081986371074530022532621955945720583925291264598924971169093688390536693144593482790588893095052569365154072722966434676949346037949263628957665599420417719951187489606010866702371368012263032537375401145460592536898818245350468847674995676417425737655723761467908866712060720593684978725896677308273
MAX = 10000000000000000000000000000000000000000
MIN = 10000000000000000000000000000000000000

imax = MAX
imin = MIN
while True:
    if imax < imin:
        print("答えが見つからない…！")
        break
    else:
        imid = imin+(imax-imin)//2
        p = pow(imid, 101)
        if p > X:
            imax = imid-1
        elif p < X:
            imin = imid+1
        else:
            print("FLAG_"+str(imid))
            break
print("完了")

このプログラムを実行すると一瞬でフラグを取得できた。

所感

二分探索のスゴさを実感。
本来は対数の計算をするのが正攻法？
だけど個人的にはこっちの解き方の方が楽だな(´_ゝ｀)

#13 Proverb (write-up)

問題

ksnctf.sweetduet.info

sshで指定されたサーバに接続する。
「Proverb」は日本語で「ことわざ」という意味らしい。

解法

早速サーバにアクセスし、ホームディレクトリを確認すると以下のようなファイルが用意されている。

flag.txtが用意されているが、直接アクセスはできない。
proverb.txtは読み取り権限があり、確認してみると中身は以下のようになっていた。

どうやら英語のことわざが記述されているっぽい。

残りのproverbは実行権限があるため、とりあえず実行してみると以下のような結果になった。

中身のコードを読むことはできないが、どうやらproverb.txtからランダムで1行取得して出力しているっぽい。

ここからどう解いていけばいいか分からなくなると思うが、ここで注目するポイントはproverbのパーミッションにs（SUID）が設定されていることである。

SUID（Set User ID）が設定されていると、そのファイルの所有者の権限で実行されるらしい。つまり、proverbを実行する際はその所有者（q13a）として実行される。
ということで、proverbファイル経由だとflag.txtに所有者（q13a）の権限としてアクセスすることができるため、フラグを取得することができそう。

proverbはproverb.txtの内容を読み出しているため、flag.txtのファイル名を「proverb.txt」に変更することでフラグを取得できる。
ただし、cpやmvコマンドなど、普通の方法ではファイル名を変更することができない（権限がないため）。
そこで、ここからはシンボリックリンクの悪用（シンボリックリンク攻撃）を試みる。

まず、ホームディレクトリでシンボリックリンクを設定しようとしても権限がないため、以下のようなエラーが出力される。

そのため自由に作業ができそうな権限のゆるいディレクトリを探す必要がある。
ルートディレクトリから探してみると、/tmpディレクトリの権限がゆるいことが分かるため、ここで作業を行うことにする。

ただし、/tmp直下だとシンボリックリンクの設定はできるが、なぜかファイルを実行する際に失敗してしまう（Linuxの仕様？）ため、/tmpに任意のサブディレクトリを作成し、そこで作業を行う。

/tmp直下だと失敗する

ここでは/tmp/q13というディレクトリを作成後、そのディレクトリ上でlnコマンドを使用してシンボリックリンクを作成した。この際、flag.txtのリンク名はproverb.txtに設定する。
proverbのシンボリックリンクも作成後、そのディレクトリ上でproverbを実行することでフラグが出力された。

フラグ取得までの流れ

所感

proverb経由でflag.txtを出力させる必要がある。というところまでは分かったが、その方法までは思いつかなかった…。（ほかの人のwrite-upを少しだけ見て、シンボリックリンクを利用する方法を知る）
今回はシンボリックリンク攻撃というものを初めて知れたので、とても良い勉強になった。

#9 Digest is secure!

問題

ksnctf.sweetduet.info

pcapファイルが渡されるだけ。
問題名からして、パケットファイルを解析してDigest認証を突破しろという問題だと予想。

解法

pcapを見ると、まず ctfq.sweetduet.info:10080/~q9/ にアクセスしていることが分かる。
その際のリクエストではDigest認証を行っており、レスポンスでは <p>The flag is <a href="flag.html">here</a>.</p> という文章が書いてあった。
どうやら /~q9/flag.html にアクセスすることがゴールらしい。しかし、このサイトにアクセスするにはDigest認証を通過する必要がある。

ここでDigest認証について勉強　→　Digest認証 - Wikipedia

Digest認証

Digest認証とは、パスワード等の情報をMD5でハッシュ化して送信することで、Basic認証よりも少しだけセキュアになった認証方式らしい。
ちなみに、#8の問題はBasic認証を扱っていて、盗聴に弱いことが分かる。

swime.hatenablog.jp

それで、Digest認証のアルゴリズムは以下の通り。

A1 = ユーザ名 ":" realm ":" パスワード
A2 = HTTPのメソッド ":" コンテンツのURI
response = MD5( MD5(A1) ":" nonce ":" nc ":" cnonce ":" qop ":" MD5(A2) )

A1とA2を作成し、それぞれハッシュ化する。その後、ハッシュ化したA1, A2とnonce等の値を用いてresponseを作成する。
このresponseの値が正しければ認証成功になるらしい。

解法の続き

ここで問題の方に戻る。
パケットを見てみると、実はパスワード以外の情報が分かっている。

username = q9
realm = secret
となっており、nonce, nc, cnonce, qop はアクセスする際にサーバから教えられるので知っていなくても大丈夫。
また、今回の場合、A2はGET:/~q9/flag.htmlとなる。

しかし、このままではパスワードが分からないのでA1を作成できない・・・と思いきや、pcapファイル内の/~q9/htdigestにアクセスした際の通信データにヒントがあった。
このサイトにアクセスした際のレスポンスに、q9:secret:c627e19450db746b739f41b64097d449と記述されていた。
どうやらc627e19450db746b739f41b64097d449がA1の値になると考えられる。（さすがにパスワードがこんなに長いとは思わないし…）
よく調べていないが、htdigestというLinuxのコマンドや、digest認証用の.htdigestファイルがあるみたいで、それと関係があると思う。

さて、これで必要な情報が揃ったので、あとはFiddler等を使って認証を突破するだけ。
まずはブラウザでflag.htmlにアクセスし、401エラーが返ってくる。
そのレスポンス内にnonce等の情報がある。

それらを利用してresponse値を計算し、認証情報を含めたリクエストを作成する。

これで認証に成功してflag.htmlにアクセスでき、FLAGをゲットできる。

感想

まさかパスワードを知らなくても認証を突破できるとは思わなかったな…。
実際はA1の値を取得するのは簡単ではないと思うので、ここまでアッサリと不正に認証が通ることはないと思うけど、Digest認証が完全に安全だとは言えないね…（そもそも使ってるハッシュ関数がMD5だし）
いやー面白かったし勉強になった！