2018-12-12

WebAssembly解いてみる

CTF Advent Calendar 2018の12日目の記事です。

前回のWebAssemblyネタが書ききれなかったので続きを12日目に突っ込みました。
前回はこれ。 xrekkusu.hatenablog.jp

解説というか中身はただのWebAssembly問題のwriteupです。

2018-12-08

WORDを支える技術

この記事はWORDIAN Advent Calendar 2018の7日目の記事です。

記事を途中まで書いた状態で12月7日発売のスマブラをしていたらMacが死んでしまって書きかけの記事が蒸発しました。
ので手短にWORDを支えていた技術と支えていく予定の技術について紹介します。

WORD編集部では普段の記事の編集環境としてLaTeXを使用しています。少し前までは一太郎ユーザーもいましたが、ここ最近の数号はLaTeX率100%になっています。

さて、何故ここまでLaTeXユーザーが多いのかというと、編集部内での公式LaTeXテンプレートとLaTeXビルドサーバーが構築されているからです（多分）。一太郎は編集部内のPCに物理的にアクセスしないと編集することができませんが、LaTeXならお手元のPCで編集ができます。

2018-12-02

WebAssemblyちょっとやる

これはCTF Advent Calendar 2018の2日目の記事です。

ここ1年くらいで、いくつかのプログラミング言語がWebAssembly形式でのバイナリ出力に対応したり、ブラウザ側での対応も本格的になったりしていて、いよいよWebAssemblyが普及してきている感じがしますね。
CTFにも当然この流れは来ていてWebAssemblyに関する問題が出題されるようになっています。

というわけで、この記事はWebAssemblyの基本部分と取り組み方を適当に書きなぐることにします。

2018-06-06

SECCON Beginners CTF 2018 Crypto + Scoring

SECCON Beginners CTF 2018でCrypto4問とスコア周りの検討をした話を書きます。詳細なWriteupについては他で結構上がってるので、解き方の流れとか解説とかを書きます。

また、この記事は自分の担当部分について感想を書いているのであって、解くのに必要な知識等を丁寧に解説するものではありません。

[Warmup] Veni, vidi, vici (559 solves)

"Veni, vidi, vici"というのはシーザーが言った「来た、見た、勝った」のラテン語ということで、問題名からも何の暗号を使っているかは一目瞭然です。

実際の問題ではフラグを3つの部分に分割してそれぞれでちょっと異なる暗号化方法にしました。

Part1: ROT13

これは一番わかりやすいし最初に試すやつですね。

数字の取り扱いに困ってる人が見受けられましたが、ROTではアルファベット以外の文字は無視されることが多いです。一応 ctf4b が成立するように復号しないといけないので数字はそのままで問題ないことがわかります。

The first part of the flag is: ctf4b{n0more

Part2: ROT18

ROT13では復号にもROT13すれば終わってしまうので、Part2は鍵を変えたバージョンです。

ここで復号後の文字列が読めない場合どの鍵が正解かわからなくなってしまうのですが、今回は The second part of ... という文を入れて鍵がわかるようにしています。復号には 26 - 18 = 6 ということでROT6すれば終わりです。

The second part of the flag is: _cLass!cal_c

Part3: ROT180

まさかのPart3で人間が読める文字が登場。文字を180度させてROT180、みたいな感じです。

人間の目ではRがどう見ても大文字だと思うんですが、なぜか小文字でのsubmitが多かったです。環境によって小文字に見えるということは無いはずですが……。こういう部分を無意識でしっかり合わせられると強いと思います。

ちなみに180度回転はこのサイトでやりました: Lunicode

{ʎɥdɐɹɓ0ʇdʎᴚ :sı ɓɐlɟ ǝɥʇ ɟo ʇɹɐd pɹıɥʇ ǝɥ⊥

The third part of the flag is: Rypt0graphy}

Flag: ctf4b{n0more_cLass!cal_cRypt0gr4phy}

RSA is Power (143 solves)

N = 97139961312384239075080721131188244842051515305572003521287545456189235939577
E = 65537
C = 77361455127455996572404451221401510145575776233122006907198858022042920987316

RSAをちゃんと見たことがあればN, E, Cが何を示しているか、またNが明らかに小さいことがわかるはず。

鍵長は256bitで、この程度であれば最近のラップトップ環境でも数分で素因数分解を終えることができます。

使うツールとしてはyafuを想定していましたが、Writeupを見る感じmsieveの人が多かったみたいです。最終的に素因数分解するアルゴリズムは多分同じなので変わらないと思います。

……がしかし。 factordbを使って解いたというWriteupがいくつか上がっていてびっくり。

factordbでは解けないものと思っていましたが、factordbは投稿された合成数を勝手に素因数分解してキャッシュするようで、コンテスト後半はそれで解けてしまう状態になっていたみたいです。

FactorDBやっぱ256bitくらいだと投げたあとに勝手に計算してキャッシュしてしまうらしい。 pic.twitter.com/V0sw4HwAfP
— れっくす (@xrekkusu) 2018年5月29日

factordbお前……。

なんだかんだでツールを使って素因数分解するとp, qとして2つの素数が出ます。素因数分解にかかる時間はスペックによりますがyafu+MBP(2017)で2分くらいだったかな？

299681192390656691733849646142066664329
324144336644773773047359441106332937713

Flag: ctf4b{5imple_rs4_1s_3asy_f0r_u}

Streaming (113 solves)

暗号問題では往々にして謎のコードが配布され、そこで実装されている更に謎の暗号アルゴリズムを読み解き、復号コードを実装するといった問題が出題されます。 Streamingではそれを模して作問しました。

内容としては線形合同法(16bit)による予測可能な乱数と何故か2バイト単位のリトルエンディアン？っぽい形式で出力されていることの2点がメインになっています。

後者は引っかかる人がいるかなと思って付け足したんですがあんまり引っかかっている様子がなく残念。

Flag: ctf4b{lcg-is-easily-predictable}

Well Known (17 solves)

ここまでの3問さすがに簡単すぎたなーと思って易しめのガチ問を投入。

Signerというクラス名から署名アルゴリズムっぽいことは想像できますが、実際に何のアルゴリズムなのかはわかりません。

コード内に出てくる文字(p, q, g, x, y, r, s)あたりからElGamal, DSAあたりまで絞っていく必要があります。この辺は日本語Wikipediaにも載ってるので常識の範囲。今回はDSAでした。

次に from flag import FLAG からxにフラグが入っていることを確認します。 xは秘密鍵なのでこの問題はKey recovery attackをしろと言っていることになります。

またWikipediaを見ると、「kに2度同じ値が使われている」とDSAを破ることができると書いてあります。 kは入力のSHA1から生成されているので、SHA1が同じになるデータを用意するとこの攻撃が使えます。

しかしSHA1が同じになるということはSHA256の入力も同じになるわけで、kに2度同じ値が使われていても得られる情報は増えず解くことができません。

勘のいいひとはここでピンとくるはず。SHA1が同じになるといえばSHAtteredですね。

入力としては2KBまでしか受け付けないので適当なところで切ったSHAtteredの組を入れると、

kに同じ値を使っている
出力sが異なる

という条件を満たすことができます。

\begin{align*} s_1 = k^{-1}(H(m_1) + xr) \pmod q \\ s_2 = k^{-1}(H(m_2) + xr) \pmod q \end{align*}

から、x, k以外の値はすべてわかっているので連立させて解くとxの値を入手できます。

ctf4b{be_c4reful_w1th_k}

余談

裏話としてはWell Knownを作ったあとにDEFCONでSHAttered問とDSA問が出てしまうという事件がありました
— れっくす (@xrekkusu) 2018年5月27日

Scoring

今回のBeginners CTFでは問題が少々簡単なこと以外は普通のCTFと同じように運営したいという思いがあり、流行の動的スコアを導入しました。

動的スコアでは解いた人数によって問題の点数が決定されるため、参加者の感じる難易度と実際の点数が剥離しにくいという大きなメリットがあります。デメリットとしては時間が経って点数が落ち着くまで問題の難易度が読めないという点くらいだと思います。

DEFCONなどではかなり急激に点数が下がるアルゴリズムを採用していますが、Beginners CTFではそれよりも減少が穏やかになるようにしました。結果として最終的な点数配分はいい感じだったように見えます。

早く解かないと点数が少なくなってしまうという誤解を生む懸念がありましたが、百聞は一見に如かずということで今回はこのルールを導入してみました。これで今後動的スコアのCTFに出ても安心ですね！

2018-04-09

SECCON 2017 国際決勝 Writeup

遅くなってほとんど忘れてるけど毎年書いてるし今回もやります。

12月に開催されたオンライン予選で11位だったので国際決勝にチームdodododoで出場してきました。

結果は3位とまずまずでしたが、国内決勝と違ってスポンサー賞がなかったので残念でした。点数的には4位と12ポイント差しかなかったので何か1つでもミスっていたら逆転されてたでしょう。

2017.seccon.jp

自分は主にサーバ1とサーバ5のhangulを解いたのと、問題以外ではNIRVANAを見まくって他のチームの得点状況の把握をしました。

SECCONでは問題に集中してようがなんだろうがNIRVANAをちゃんと見るというのが超重要です。これをしないとそもそもDefense pointが加算されたのかどうかすらわかりません。

また、Defense pointの獲得状況はログとしてどこかで見られるわけではないので、「問題hogeで時々Defenseに失敗している」といった状況では対処が遅れる可能性があります。

King of the Hillでは状況が刻一刻と変化していくため、得点状況が把握できたのは戦略を立てる上でかなり有効でした。

サーバ1: brainhack

Webページにアクセスし、Brainf*ckで "Hello, World!" を出力しろという問題。バイナリが配布されていてなんかヤバそうな空気。

Brainf*ckの実行結果は確認することができ、これを使っていくつかのAttack flagを入手することになります。

フラグ1

"Hello, World!" と出力するだけ。

Flag: SECCON{Congraturations! Also find other attack flags.}

フラグ2

配布されたバイナリをstringsすると出るらしいです。

バイナリでマップされる領域外？か何かにフラグが置いてあったらしく、ディスアセンブラで読んでたので一切気づいてませんでした。チームメンバーが拾ってくれていて非常に助かりました。

Flag: SECCON{This must be　 too easy for you.}

It was too hard.

フラグ3

配布されたバイナリをよく読むと通常の8つの命令の他に、
', ", %, {, }, :, ;
とかの謎の命令が登場します。

そのうち'の実装を読むと、attack3.txtからポインタ位置に応じて1文字読み出せる実装になっています。これを使って以下のようにするとattack3.txtの内容を読み出せます。

'.>'.>'.>'.>'.>'.>'.>'.>'.>'.>'.>'.>'.>'.>'.>'.>'.>'.>'.>'.>'.>'.>...

Flag: SECCON{Don't forget to update your score with updated your team keyword.}

フラグ4

フラグ3同様にサーバ上のファイルが読み込まれているタイプの問題です。読み込んでいるファイルはYXR0YWNrNC50eHQ=という名前だったんですが、これはattack4.txtのbase64でした。こういう謎の小細工は正直要らなかった。

attack4.txtはBrainf*ckでアクセスできる範囲外のメモリに読み込まれているため、普通ではない方法で読み出す必要があります。

ここで謎の命令の実装をよく読んでいくと、{, } を使うと境界チェックをせずにポインターの位置を動かすことができるようになっていました。

というわけで、

{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{...(snip)...{{{{{{{.}.}.}.}.}.}.}.}

みたいな感じでattack4.txtの内容を読み出せます。

ファイル内にフラグがあったので終了。

Flag: SECCON{If you find all 4 flags in this tower, please challenge the other towers.}

Defense

ページ内に文字数と提出者の名前が書かれたランキングが置いてあっていかにも怪しい感じ。ランキングには短い文字数順で並んでいたので、短いコードを提出したチームにDefense pointが与えられるということらしいです。

Brainf*ck単体での最短コードはググると78bytesのものが見つかるものの、最初から存在するSECCONユーザ(78bytes)を超えることができず、Defense pointを獲得できません。

codegolf.stackexchange.com

ここで、配布されているバイナリの機能を使って78bytesより短くHello Worldを表現する必要がありそうだということに気づく。 ……が時すでに遅しという状態で、他のチームが12bytes解を提出していてかなり絶望的です。とはいえDefense pointで差を開けられないようにする必要があったので気合でいろいろ探していると、なんと9bytesで通る解を発見します。

驚異の9bytes解はこれ。もはやHello, World!より短い。

{[{]{[.{]

Attackのフラグ4で登場したファイル内に

[NUL]!dlroW ,olleH[NUL].....(snip)

みたいな内容が偶然にも埋まっていたため、この部分のHello, World!が出力されます。

「ここにHello, World!を置くからには簡単に出力できるんだろう」という予想を持ってコードを書いてはいましたが、実際に[NUL]を確認していたわけではないので試しに入れたやつが通ってしまったときは悲鳴を上げました。

コードの説明をすると、{[{] の部分でHの右隣の[NUL]に到達して{で1文字左に移動したあと、[.{]で次の[NUL]まで文字を出力しています。

この9bytes解でdodododoはしばらく単独Defenseを続けていましたが、すこし後にbinjaも9bytes解を発見してポイントが山分けになります。

さらに2日目になると、いくつかのチームがBrainf*ckの実行バイナリ自体をPwnしてランキングサーバに対して直接攻撃し始めたためランキングが荒れました。

ちなみにランキングが荒れすぎたせいでサーバがダウンするという事件が発生したのでPwnできてなかったdodododo的には非常においしかったです。

サーバ5

サーバ1が思ってたより長くなったのでまた今度。説明するのしんどいし書かないかも。

2017-12-05

OK, Google. しりとり

WORDIAN Advent Calendar 2017 - Adventarの5日目らしいです。

WORD部屋にGoogle Homeが設置されてからもうすぐ2ヶ月になります。

Google Homeを使い始めてすぐに「OK, Google. しりとりをして」と話しかけ、出てくる単語を当てるゲームが流行しました。

当たった当たらないのどうでもいいことで一喜一憂する編集部員達でしたが、なんと単語ごとにしりとりの始まり方も違っていて、そのため確定ポイントが存在します。

というわけで投稿時点でのしりとりで出るワード一覧を紹介します。

それはいいですね→風鈴
しりとり対決ですね→JAPAN
わかりました→メロン
はい、やりましょう→サボテン
ぜひやりましょう→おでん
面白そうですね→食パン
しりとりは大好きなんです→富士山
はい、それでは私からいきますね→ドラゴン

また、しりとりで出て来る言葉は時々変わるらしく、Google Homeの日本発売時は「風鈴」「メロン」「おでん」「ドラゴン」の4種類だったはずが最近は8種類に増えたみたいです。

この他にもあったら教えてください。

2017-09-20

きららフォワードCTF Writeup

発端はこれ。

きららフォワード読んでたらめちゃめちゃ不自然な半分のQRコード出てきたんですが、CTFか？ pic.twitter.com/FIbeTeepew
— 本格手打ち麺 (@tyage) 2017年9月20日

QRコードといえばSECCONですが、このタイプの欠け方は今まで見たことがなかったのでチャレンジしてみました。ちなみに今までCTFで出たQRコード問題は、

データ部分が完璧に残っている
エラー訂正部分がほぼ完璧に残っている
フォーマットデータが壊れている

の大体3種類です。

今回のQRコードはデータがちょっと欠けつつエラー部分はほぼ全滅、になっています。

まずはテキストに書き起こさないと始まらないので書き起こします。

XXXXXXX   X XXX X XXXXXXX
X     X X X    X  X     X
X XXX X     X  X  X XXX X
X XXX X XXX XX  X X XXX X
X XXX X  X    X X X XXX X
X     X XX XXX XX X     X
XXXXXXX X X X X X XXXXXXX
         XXX  X X
????????XX X  XX X X X X
????????? X X  XX  X   X
??????????X  XXXXX XXX XX
??????????? X   XX X    X
????????????X X  XX X XXX
????????????? X    X X X
??????????????XX X XXX XX
???????????????XXX XX   X
????????????????XXXXX X
????????????????X   XX
????????????????X X X XXX
????????????????X   XX XX
????????????????XXXXX XXX
?????????????????????XXXX
??????????????????????X X
??????????????????????? X
????????????????????????X

フォーマット部

フォーマットデータも半分くらい死んでますね。でもフォーマットデータは32パターンくらいしかないので適当に復元できます。

エラー訂正部

今回はエラーデータ部分がかなり欠落していてエラー訂正は無理でした。

エラー訂正も最大まで適用して30%ですが、今回はL(7%)なので到底ムリです。

データ部

今回のQRコードで一番残ってるエリアになります。自作のツールに掛けてみるとこんなデータが出力されました。

[{'decoded': '', 'length_raw': '', 'raw': '0001010101101000011101000111010001110000011100110011101?????????????1111011001110110111101101111?????????????????????100001011110100011101111000011110000011001101000110010101?????????????????????????????????????????????0?00100011110110000010001111011000001000111??????', 'length': 268, 'mode': 'UNKNOWN', 'mode_raw': '0?00'}]

QRコードのデータで用いる符号化モードの属性が壊れてしまっています。

1ビットしか壊れていないので0か1になるはずですが、モード0000はデータの終了を意味するので1を入れることになります。

XXXXXXX   X XXX X XXXXXXX
X     X X X    X  X     X
X XXX X     X  X  X XXX X
X XXX X XXX XX  X X XXX X
X XXX X  X    X X X XXX X
X     X XX XXX XX X     X
XXXXXXX X X X X X XXXXXXX
         XXX  X X
????????XX X  XX X X X X
????????? X X  XX  X   X
??????????X  XXXXX XXX XX
??????????? X   XX X    X
????????????X X  XX X XXX
????????????? X    X X X
??????????????XX X XXX XX
???????????????XXX XX   X
????????????????XXXXX X
????????????????X   XX
????????????????X X X XXX
????????????????X   XX XX
????????????????XXXXX XXX
?????????????????????XXXX
??????????????????????X X
??????????????????????? X
???????????????????????XX

?に1を入れたときのデータはこうなりました。

再びツールに掛けるとURLっぽい文字列が出てきます。

[{'decoded': 'https???goo???/Gxx3F?', 'length_raw': '00010101', 'raw': '01101000011101000111010001110000011100110011101?????????????1111011001110110111101101111?????????????????????100001011110100011101111000011110000011001101000110010101??', 'length': 21, 'mode': '8BIT', 'mode_raw': '0100'}, {'decoded': '', 'length_raw': '', 'raw': '???????????????????????????????????????0?00100011110110000010001111011000001000111??????', 'length': 88, 'mode': 'UNKNOWN', 'mode_raw': '????'}]

https???goo???/Gxx3F?

このギリギリわかるようにURLが出てくる感じ、CTFみたいでテンションが上がりますね。

出てきたURLを見ると短縮URLでgoo.glを使っているだろうと推測できますが、肝心な最後の1文字が不明なので52通りの総当りが必要です。

もう一度ツールの出力を読むと、符号化モードは8BIT、rawデータの欠けている部分は2ビットです。この部分を総当りすると4通りしかありません。

というわけで4通り総当りしてそれっぽいURLを救出すると、「空の隙間 -SKY BLUE DROP-」という漫画のカラーイラストを入手することができます。

まとめ

本編読んでないひとがこういうことすると急に文脈のわからないイラストが手に入ってしまって虚しい気持ちになります。好奇心は罪ですね。

大ヒント

解いた後にtyageさんがこんなツイートをRTしていましたが、これがあれば最後のguessingは必要なかったですね。

#きらら #空の隙間 -SKY BLUE DROP- （著： #ピナケス @PinaxPinakes ）のあのQRコードはなんだ？　答えは作者さんのサイトへのURLリンクです。今回の読み切りゲスト作品のカラーイラストです。とても綺麗なのでぜひゲットしましょう Gxx[ ]FV
— winiah (@winiah) 2017年9月3日

バランスを取りたい

よくCTFの記事を書きます

WebAssembly解いてみる

WORDを支える技術

WebAssemblyちょっとやる

SECCON Beginners CTF 2018 Crypto + Scoring

[Warmup] Veni, vidi, vici (559 solves)

Part1: ROT13

Part2: ROT18

Part3: ROT180

RSA is Power (143 solves)

Streaming (113 solves)

Well Known (17 solves)

Scoring

SECCON 2017 国際決勝 Writeup

サーバ1: brainhack

フラグ1

フラグ2

フラグ3

フラグ4

Defense

サーバ5

OK, Google. しりとり

きららフォワードCTF Writeup

フォーマット部

エラー訂正部

データ部

まとめ

大ヒント