TSGCTF 2020 Write-Up

2020年7月11日～7月12日にかけて開催された、TSGCTFのWrite-Upです。

今回はソロチームとして参加し、Sanity CheckとSurveyを除いてはMiscの2問のみを通し、512点を獲得して38位となりました。

ここでは、自分の通した問題についての解法を記したいと思います。

Beginner's Misc

eval(b64encode(input().encode('UTF_8')))==math.pi

となるようなinput()を作れ、という問題。

要するに、eval(s)==math.piで、b64decode(s)がUTF_8として正当であるようなsを作れば良いです。 

とりあえず、UTF_8の形式を見てみます。

Unicode code points   Range    Encoding  Binary value
-------------------  --------  --------------------------
 U+000000-U+00007f   0xxxxxxx  0xxxxxxx

 U+000080-U+0007ff   110yyyxx  00000yyy xxxxxxxx
                     10xxxxxx

 U+000800-U+00ffff   1110yyyy  yyyyyyyy xxxxxxxx
                     10yyyyxx
                     10xxxxxx

 U+010000-U+10ffff   11110zzz  000zzzzz yyyyyyyy xxxxxxxx
                     10zzyyyy
                     10yyyyxx
                     10xxxxxx
from: https://stackoverflow.com/questions/9356169/utf-8-continuation-bytes

この表より、上位3bitが110である場合は次に上位2bitが10のContinuation byteが続く、1110である場合は次の2つにContinuation bytesが続く、11110の場合は… と言ったことが分かります。

また、base64の4文字をデコードした際は3byteになるため、この3byteを一塊として考えることにします。

問題の趣旨に立ち戻ると`math.pi`と等価になるような小数を作れ、という問題でした。ただ、pythonの浮動小数点数のイコールは少々誤差があっても許容されるので、base64に存在する文字のうち整数と除算命令('/')、加算命令('+')を使って近似することを考えます。

ここで、これらの文字について、base64の4文字の塊のうち何文字目に使用した時にどの種類のbyte(0xxxxxx or 10xxxxxx or 110xxxxx or...)を生成するか、という表を作成しました。

これはbase64/UTF8問で書いた表(UTF8の形式を初めて知った) pic.twitter.com/XWrzC2TogT

— keymoon (@kymn_) 2020年7月12日

後は手作業で、ひたすら近づくような解を生成しました。正直全探索したほうがよかった。

できた解はこれで、

>> 379/140+1540274047210746040/3545344156695621040+0o00

3.141592653589793

>> math.pi

3.141592653589793

pythonで実行した際に等価となります。

最後の+0o00はpaddingが必要になってしまったために、適当に表を見て捻り出しました。

Self Host

未知の言語で書かれた言語自身のコンパイラが与えられるので、そのコンパイラのバイナリを作ってねという問題。そして、更にそのバイナリによってコンパイルしたコンパイラのバイナリ、によってコンパイルされたコンパイラのバイナリによってflagが入ったソースがコンパイルされるので、そのソースのコンパイル結果をflagを吐くようにしてねって話。

書いていて意味が分からなくなったんですが、以下の記事のhackと同じことを未知の言語でやってねって話です。

0x19f.hatenablog.com

で、とりあえず最初に未知の言語をコンパイルてきるようにしないことには話が始まりません。幸いC-likeな構文ではあったので、自分が書きなれているC#に手作業で直すことにしました。人力トランスパイラと申す。この言語は整数型とリスト型しかなく、文字列も整数のリストのシンタックスシュガーといった形になっています。また、動的型付けな言語であることも予想がついたので、C#の言語機能にあるdynamic型で動的型付けを実現します。1000行ほどにみっちりと出たエラーを気合で2時間かけてつぶし、とりあえずコンパイルが通るようなソースを完成させました。x.cs · GitHub

次に、Thompson hackを実装します。

hackする対象は関数をコンパイルする関数とします。その関数"compile_function"には、関数名と引数リスト、関数の中身の構文木が与えられます。アセンブリを吐かせるのはコード的にめんどくさいので、構文木にコードを追加することにします。

要件としては、「compile_function関数が来たら、書き換えた部分の構文木をそのまま追加し、1token目がflag変数である関数が来たらwrite(flag);の構文木を付け足す」が満たせれば嬉しいです。また、構文木をそのまま埋め込むのもめんどくさいのでコンパイラにあるparse関数を借りさせてもらうことにします。このparse関数は関数(とグローバル変数)しかパースできないので、一旦関数化してパースし、その中身から構文木を引き抜いてくることにします。

ここまでを踏まえて、そのコードを考えるとこうなります。(tokenize関数はないですが、tokenizeした結果をそのまま書くと冗長になってつらいので便宜的にこうしています。)

if (fn == "compile_function") { body = parse(y)[0][3] + body; }
if (body[0][1] == "flag") { body = body + parse(tokenize("f(){write(flag);}"))[0][3]; }

そして、一行目のparseに突っ込まれている変数'y'に、付け足した全体のコード(が入っている関数)が入っていると嬉しいです。なのでそうなるようなQuineを書きます。

とりあえず、このような構造になるようにしたいです。

y = /* ここ以下の字句解析結果 */;
x = /* yのリストを字句解析した結果になるようにがんばる */;
y = tokenize("f(){y = ") + x + y + tokenize("}") 
/* これでyには追加したコードの字句解析結果が入ってる */ 

このようになるように頑張ると、

y = /* ここ以下の字句解析結果 */; 
x = ["[", "\"" + y[0] + "\""];
i = 1;
while (i < len(y)) { 
  x = x + [","] + ["\"" + y[i] + "\""]; i = i + 1;
}
x = x + tokenize("];") /* xにはリストyの字句解析結果が入っている */
y = tokenize("f(){y = ") + x + y + tokenize("}");

となります。

 最後に、この言語にはエスケープがないため、全ての文字列を別の形式で表すようにします。 先程も述べた通り、この言語では文字列は整数リストのシンタックスシュガーにすぎないので、例えば"flag"は[102, 108, 97, 103]といった形で表せます。こうすることで、yに最初に入れておく字句解析結果にダブルクオーテーションが出てこなくなって嬉しいです。

このようにした結果がこうです。

gist.github.com

あとは、これを先程の移植したコンパイラでコンパイルすれば、Thompson hackが仕込まれたアセンブリを得ることができます。

 おわりに

Self Hostに半日かかってしまい、自分のプログラミング能力の微妙さに悲しくなってました。もう少し早く解いて他の問題にも手をつけられるようになりたかったです。