この記事について

本記事は，HarekazeCTF2018に私が出題した問題 [Misc 127]Unnormalized-form Data の想定解法について解説を行うものである．HarekazeCTF2018の期間中に43チームが本問題のフラグを獲得した． harekaze.com

問題文

Unnormalized-form data is troublesome.

解法

配布された unf.zip を展開して，2つのファイルを得る．

operation.txt
unf.sql

`operation.txt` の観察

operation.txt は次のような内容である．

$ sudo nano postgresql.conf
$ sudo /etc/init.d/postgresql reload
[ ok ] Reloading postgresql configuration (via systemctl): postgresql.service.
$ psql -U postgres -c "CREATE DATABASE unf"
CREATE DATABASE
$ psql -U postgres -d unf < unf.sql >> /dev/null
$ psql -U postgres -d unf -c "SELECT FLAG()"
             flag
-------------------------------
 HarekazeCTF{****************}
(1 row)

$

この記述はフラグの取得までの手順を示している．

postgresql.conf を書き換える．
PostgreSQLをリロードする．
PostgreSQLにデータベース unf を作成し， unf.sql の内容を入力する．
データベースから FLAG() 関数でフラグを取得する．

`unf.sql` の観察

unf.sql は次のような内容である．このファイルには，テーブル定義，FLAG() 関数の定義などが記述されている．

CREATE TABLE dic (a TEXT[], c TEXT);
ALTER TABLE dic OWNER TO postgres;

CREATE TABLE rel (s TEXT[], d TEXT[]);
ALTER TABLE rel OWNER TO postgres;

INSERT INTO dic(a, c) VALUES('{d,B,7}','H');
INSERT INTO dic(a, c) VALUES('{b,A,4}','.');
INSERT INTO dic(a, c) VALUES('{b,H,1}','=');
INSERT INTO dic(a, c) VALUES('{d,A,5}','p');
...

INSERT INTO rel(s, d) VALUES('{b,C,5}','{c,A,6}');
INSERT INTO rel(s, d) VALUES('{d,D,3}','{a,D,2}');
INSERT INTO rel(s, d) VALUES('{b,D,7}','{b,E,7}');
INSERT INTO rel(s, d) VALUES('{a,F,5}','{d,D,3}');
...

CREATE FUNCTION flag() RETURNS text
    LANGUAGE sql IMMUTABLE SECURITY DEFINER
    AS $$WITH RECURSIVE r(i, j, a) AS ( ... WHERE i = 40 AND r.a::TEXT[] @> dic.a ORDER BY j) AS t $$;

REVOKE ALL ON SCHEMA public FROM PUBLIC;
REVOKE ALL ON SCHEMA public FROM postgres;
GRANT ALL ON SCHEMA public TO postgres;
GRANT ALL ON SCHEMA public TO PUBLIC;

operation.txt の観察の項で確認したフラグの取得までの手順における手順1を飛ばして，手順2, 3, 4を行うと，次のような結果になり，フラグを得ることができない．

$ sudo /etc/init.d/postgresql reload
[ ok ] Reloading postgresql configuration (via systemctl): postgresql.service.
$ psql -U postgres -c "CREATE DATABASE unf"
CREATE DATABASE
$ psql -U postgres -d unf < unf.sql >> /dev/null
$ psql -U postgres -d unf -c "SELECT FLAG()"
     flag
---------------
 HarekazeCTF{} 
(1 row)

$

よって，手順1の postgresql.conf の書き換えが FLAG() 関数の結果に影響していると考えられる．ファイルの書き換え直後に手順2でPostgreSQLがリロードされていることから，このリロードが設定の反映のために行われていると考えて postgresql.conf の設定の変更を検討する．

postgresql.conf で行える設定には，PostgreSQLへの最大同時接続数，タイムアウト，実行計画最適化パラメータの変更などがあるが，SQL文の結果に直接影響を及ぼすような設定はそれほど多くない．そのような設定の多くはPostgreSQLの過去のバージョンやPostgreSQL以外のSQL製品との互換性に関わるオプションである．

変更するオプションの決定

unf.sql の特徴から， FLAG() 関数の結果に影響を及ぼすようなオプションを探す．

FLAG() 関数の定義には2つの配列間の包含関係を調べる二項演算子 <@ , @> が使われている．これらの二項演算子は，オペランドとなっている2つの配列のいずれかがNULL(空)を要素に含む場合は常にFALSEを返す．

また，次のタイミングで「文字列」から「文字列の配列」へのキャストが行われている．

FLAG() 関数内で明示的なキャスト r.a::TEXT[] が行われる．
INSERT 文内で暗黙的なキャストが行われる．

「文字列」から「文字列の配列」へのキャスト

「文字列」から「文字列の配列」へのキャストは，カンマ区切りの要素を {} で囲んだもの(例： {a,b,c} )を「文字列の配列」に変換するものである．このとき，キャストする前の文字列に NULL という文字列がカンマ区切りの要素として含まれる場合(例： {a,b,NULL} )，キャスト後にNULL(空)要素となる．

しかし，これはバージョン8.2以降の仕様で，バージョン8.1以前はキャストする前の文字列に NULL という文字列が含まれていてもキャスト後にNULL(空)要素にはならず，NULL という文字列がそのまま配列の要素として格納されていた．(文字列から配列へのキャストでNULL要素をキャスト後の配列に格納する手段が存在していなかった．)

そこで，現在のPostgreSQLにはバージョン8.1以前のPostgreSQLとの互換性を維持するため， array_nulls というオプションが用意されている．このオプションの切り替えによって，NULL という文字列をカンマ区切りの要素として含む文字列を「文字列の配列」へキャストする場合，その取り扱いを選択できる．

array_nulls = on：NULL(空)要素として配列に格納される．(デフォルト)
array_nulls = off：NULL という文字列のまま配列に格納される．

unf.sql の特徴から，変更すべきオプションは array_nulls であると判断する．array_nulls = on から array_nulls = off に変更する．

フラグの取得

フラグの取得までの手順における手順1から手順4をやり直す． INSERT 文内で「文字列」から「文字列の配列」への暗黙的なキャストが行われているので，array_nulls = on の状態で行った unf.sql の流し込みもやり直す必要があることに注意．

$ sudo nano /etc/postgresql/9.5/main/postgresql.conf # array_nulls = on -> off
$ sudo /etc/init.d/postgresql reload
[ ok ] Reloading postgresql configuration (via systemctl): postgresql.service.
$ psql -U postgres -c "CREATE DATABASE unf"
CREATE DATABASE
$ psql -U postgres -d unf < unf.sql >> /dev/null
$ psql -U postgres -d unf -c "SELECT FLAG()"
             flag
-------------------------------
 HarekazeCTF{Th1rteen_0rphans}
(1 row)

$

フラグ HarekazeCTF{Th1rteen_0rphans} を得る．

備考

設定ファイルの書き込み権限がない場合や設定ファイルの書き換えが面倒な場合には，PostgreSQLに接続してすぐに SET array_nulls TO off を実行すると，同一接続内に限りこのオプションを off にできる．

題意

「バージョンの異なるデータベース間のデータの移行」「コレクションをカンマ区切りの文字列としてデータベースに格納することの危うさ」をテーマに出題した．

データベースのバージョンアップ時には，新たな機能が追加されるだけでなく，既存の機能の削除や変更が行われることがある．NULL値の取り扱いはバージョン間で大きく異なっている場合があるので，データの移行時に特に注意すべきである．また，カンマ区切りの文字列によるコレクションの表現はデータベースの(第1)正規化を行った場合の恩恵を受けられないばかりでなく，時として意図しない挙動を引き起こすので，本当にそれが必要かをよく検討する必要がある．