zer0pts CTF 2021 writeup (Baby SQLi, 3-AES, janken vs yoshiking, war(sa)mup, Kantan Calc) writeup
先週末に zer0pts CTF 2021 があり、TSGは7位でした。
いずれも解きごたえのある難問ばかりでめちゃくちゃ楽しかったです。web warmup で温まらなかったことを除いて完璧なCTFでした。開催していただいてありがとうございます。
kczは以下の問題を解きました (ほぼ完全に一人でといたもの)。
- Baby SQLi (web)
- 3-AES (crypto)
- janken vs yoshiking (crypto)
- war(sa)mup (crypto)
- Kantan Calc (web)
Writeupを書こうかと思ったけどめんどくさいのでチーム内のメモをだいたいそのまま公開します。
Harekaze mini CTF 2020 WASM BF writeup
これはTSG Advent Calendar 8日目の記事ということにします。
adventar.org
とりあえず11月中にAdvent Calendarへ登録をするだけして、11月12月に大量に開催されるCTFで何らかの非自明な問題でも解いたらwriteupを書いて埋めるかーと思っていたのですが、それほど非自明な問題は解けないわAdvent Calendarを書く気が出ないわでこのまま踏み倒そうかと思っていたところ、ちょうど手頃に解説しやすく、解説しがいがあり、いい感じにインスタ映えのしそうな問題があったものですから、もう年始に向けてカウントダウンを始めても差し支えなさそうな12月29日に投稿しています。
12/26-27にHarekaze mini CTF 2020が開催されました。
github.com
mini CTFという名前にふさわしく、特別長時間悩みこむ問題という感じではなかったですが、しっかり面白い問題が揃っていて、面白かったです（面白い問題なので）*1。
その中でWebジャンルのWASM BFという問題を解いたので、それのwriteupをしていこうと思います。方法の説明というよりは、問題を解くときの試行過程をそのままメモしています。
*1:まあ、そこまで全体感想を言えるほど全問題を見たわけでもないんですが。
CTFZone 2019 Quals writeup - M394Dr1V3 cr4cKM3
TSGアドベントカレンダー 2019 3日目です。
adventar.org
こないだ11/30 18:00 JST - 12/2 06:00 JST、TSGでCTFZone 2019 Qualsに参加しました。
わりとみんなでまじめに参加して、結果はなんとか10位となりました。
アドベントカレンダー登録時の予定では、Web問あたりがいくつか解けて、ここでwriteupを書くはずだったんですが、かなりエスパー要素があるわ1問あたりの段階数がおおいやらで、全体的にいいところまでは進めても解ききれませんでした。悲しいね。全体的にこれ〇〇〇CONか？
初心に戻って唯一解けたRevering: M394Dr1V3 cr4cKM3のwriteupを書きます。
続きを読む高速整数乗算アルゴリズムSchönhage Strassen Algorithmを雑に実装した話
そういえばIS Advent Calendarに投稿しようと思ってずっと放置していたのがあったのに、登録するのを忘れていたことを思い出したので、雑に供養します。
だいぶ昔の話なんですが、大学の演習IIIとかいう授業で、なんかSchönhage Strassen Algorithmというのを実装したくなったので実装させてもらいました。
当時のスライドから面白くないものを削除したスライドです。それなりにイメージは伝わると思っています。
実装は公開しています。見るに堪えないかもわかりませんが。
github.com
Schönhage Strassen Algorithmは、整数乗算アルゴリズムで、まあもちろん速いわけなんですが、速いと言っても定数倍がかなり重くて日常的な乗算にはむしろ不利なやつです。
日本語WikipediaにはGMPでは「10進法で33 000 - 150 000桁の大きさ」でSSAを初めて用いるようになるとあります。
ソースに当たると、MUL_FFT_THRESHOLDというのが関係してくるらしくって、その値はx86_64で11520らしいんですが、limbってなんだかわからないしこれがなんなのかはわかりません。
実装するときは、スライドにもありますが、「Multiplying large numbers and the Schönhage-Strassen Algorithm - Theo Kortekaas」とか参考にするといいです。オンラインで見つかるPDFです。
今終わってみるとGMP manualとかも参考になったのかもしれないと思いますが、当時は見つけられなかったのでしかたない。
今回の実装では、スライドのpage 22を見ると、10^6 bit同士の乗算あたりからKaratsuba法を上回ったようです。
まあ圧倒的にGMPには劣るわけですが（スライドpage 23）。
そんなちゃんと実装したわけじゃないので、同じbit数同士の乗算しかできなかったり（当然0埋めすれば違ってもできるが、計算量的に劣る）、詳しくは書きませんが計算途中に特別な条件を満たすと続行不可能になってエラー返したりします*1。
以上、供養でした。
*1:参考PDFでも触れられているのと、「続行不可能」でスライド検索すればなんとなく分かります。
min-caml compiler pwn （ISer advent calendar 12/2出題）writeup
この記事はISer Advent Calendar 2018 16日目の記事です。
adventar.org
昨日はMisterプロによる「簡潔ビットベクトル(完備辞書)」でした。
misteer.hatenablog.com
17erのこおしいずです。CPU実験は1年前です。
同アドベントカレンダー2日目の記事に、moratoriumプロによる「min-camlのプログラムからシェルが取れるか？」というのがあって、そこでpwn問題が出されていました。
もう2週間経ちますので、writeupをやっていこうと思います。
とはいえ、出題者からはもっと良質な想定解が提示される予定なので、12/23のアドベントカレンダー記事も読みましょう。
moraprogramming.hateblo.jp
問題概要
ISのCPU実験でのコンパイラ開発のベースとして使われる、min-camlというOCaml subsetコンパイラがあるのですが、この問題では、min-camlソースコードを与えると、そのコンパイラ（に制限を加えたもの）でコンパイルした結果を実行してくれるので、シェルをとれという問題です。
CTFでコンパイラへの入力を与えるタイプはあんまり見ない気がしますが、OCamlはめっちゃ型つける系だし、今回glibcも外されて*1、自明ではない、ということです。
コンパイラはなぜかArrayのPUT構文を潰されています。ふむ。
*1:ゆーてこれヒントかもしれない、外す理由あんまりなくないですか？
