サイバーコロッセオ×SECCON 2016に行ってきました。

チームNaruseJunです。

いえーい pic.twitter.com/2S58IlKwSS

— 成瀬順＠技術書典お-18 (@N4RU5E) 2017年3月5日

メンバーは kaz, kriw, nari, phi16 です。
チームでオンサイトのCTFに出るのはコレが初めてです。

結果は3位でした。

サイバーコロッセオxSECCON 終了しました。優勝dodododo、準優勝urandom、3位NaruseJunという結果でした。参加した皆様お疲れ様でした！ #seccon pic.twitter.com/ekMDne43lh

— SECCON CTF (@secconctf) March 5, 2017

じゃーん！ pic.twitter.com/bUknwg1aWF

— 成瀬順＠技術書典お-18 (@N4RU5E) 2017年3月5日

所感

• NIRVANA改、めちゃかっこいい。
• SAOのBGMがずっとかかってて熱い。
• SECCONステッカーとか東京2020バッジとかもらいました。うれしい。
• 紹介文の「東都工業大学から来ました」が司会の人にスルーされてしまった。ポ。
• ステージにて、@takesakoさん「大丈夫ですか、成瀬順さん、しゃべってもお腹いたくなりませんか」

King of the Hill

KotH初めてで勝手がわからず……！
JeopardyみたいにFLAGを取る(attack point)けど、サーバにFLAGを書き込んだり(defence point)もする。

defenceとはいうものの、ほかチームが書いたのを消せない仕様だったり、ほかチームの書き込みをあまり妨害できなかったりで、守ってる感はあんまりなかった。

結局ウチはほとんどattack pointしか稼いでないので、うん。

壱

各チームは30分に一回素数ペアp,qが投げられる
pqの小さい順にランキングされて、5分おきに1番小さいpqペアを投げたチームがディフェンスポイントを得る
pqが小さければいいかというと、他のチームのpqを素因数分解するとランキングから除名できる
かと言って大きいとランキングで強くない

RSAは暗算で行けるといつも豪語してるnariにお願いしました。

以下、部内wikiから勝手に文章をパクってきました。

pqの生成方針

1位のsqrtより小さいpqペアを投げる
1位のpqを取ってきてmx = sqrt(pq)として[mx*7/10, mx]の範囲のランダム素数を2つ用意するだけ
ランダムは普通にランダム よほどのことが無い限り破られやすい素数ペアは出ない

魚類でも分かる簡単ランダムな素数生成

ランダムな素数を作る関数が無い！ → 乱数生成+素数判定で作れます

ランダム素数生成は一般に素数が出るまでランダム整数を続ければ良い(素数定理よりそこそこの回数で終わる)
乱数はrubyとかpythonなら0~aまでの乱数みたいなのが作れるのでrand(max-min)+minとするとよい
素数判定はミラーラビンで k=20で十分

pqの破壊方針

試し割り

王　道　を　征　く
2で割って後は3以上の奇数で順々に割っていく
大体これでは破壊できない(そんなので破壊できたら他の人がやってる)

ポラードロー法

http://mathtrain.jp/rhoalgorithm

未解決問題な確率的素因数発見アルゴリズムだけど実用的。まぁこれでも見つかることは多くない。

平方根

p=qの時はこれで。二分探索とかx + 1/xで収束させるやつとかで一瞬で求まる。

フェルマー法

pとqの差が小さいと一瞬で破壊できる
p=a+b, q=a-bと表現する 差は2bだけど、p,qどちらも奇数を仮定していいのでこれで一般性を失わない $n=pq=(a+b)(a-b)=a^2-b^2$ $b^2=a^2-n$ 右辺が正となるように $a\ge \sqrt{n}$ として、aを1つ1つ試して、 $a^2-n$ の平方根が整数になったらa,bからp,qが求まる
a,bを徐々に大きくしていくので、pとqの差が小さいなら一瞬で破壊できるということ
フェルマー法で一番時間がかかるのは差が非常に大きいときだけど、その場合は試し割りの方が速い

factordb

ランダム素数生成したら大抵載ってません。

msieve

上記の手法でも小さいやつは分解できるけど大きくなると通用しない
もっといろんな速い手法があるけど面倒なのでmsieveというツールを使って後半は素因数分解してた
GPUを使うことができるらしくTSUBAMEで動かしたりなどもしていた
普通にbrew install msieveでOSXでも動くのでそれで分解したりもしていた
大体10進で80桁を数分で破壊できる 強い

全体的な流れ

序盤 : 予め用意してあった数字は全部breakした(全部二乗数だった)
その二乗数で拾った素数を適当に掛け合わせてめっちゃ巨大なpqを投げた
割りと居座った気がする 他のチームが試しに2*3とか出してたので構わずbreakした
数回だけフェルマー法で破れるそこそこ大きい数があった

中盤 : 拾った素数がバレる(それはそう)
多分序盤からmsieveとか使ってたんだろうけど破壊屋がガンガン破壊していく
どれぐらいなら破壊されないかを模索しながら徐々に1位の数が小さくなっていく

終盤 : 10進で90桁前後が安定する
十数分は持ちこたえつつできるだけ小さい数の収束って感じ
それ未満はmsieveで破壊
2*2を5分刻みのタイミングで出してくるチームが現れてルールを恨む
最後は隣のnegainoidoと競ってた気がする(こっちのが破壊されて終了)

感想

これRSAじゃなくない？？？ディフェンスポイント入る瞬間にp=q=2をぶち込む輩もいて完全にゲームバランスが終了してたんだが(最初の方は誰もp,q入れて無くて美味しかった)

ちなみに1024bit RSAはスパコンでも確か破壊できないらしい

本当にCryptoというより数論アンドCPUGPUパワーって感じの問題だった……

なお量子コンピュータができれば素因数分解は一瞬になります(Shorのアルゴリズムで位数が一瞬で求まるため)

弐

わりと自明なPwn問。
シェルコードをぶん投げるだけみたいなやつと、BOFと、あと忘れた。

バイナリアンのkriwにお願いしました。

参

Web問(?)
解説の人はIoT問だよ！みたいな事を言ってた。

WebカメラのWebインタフェース(を模したもの)を攻撃する。
適当にPOSTパラメータいじるとカメラが制限範囲外を向いてFLAGをが見える。

で、そのあとnmapでデバッグポート見つけて、管理画面をあさると他２つのFLAGをが見つかる。
で、管理画面から難なくdefence keywordを書き込める。

kaz, phi16でいっしょに解きました。

四

Linuxのアクセス権限を制御するカーネルモジュールCaitSithで制限された環境でいろいろがんばってね！ってやつ。

flag.txtを削除すると次に進めそう？ってところでこのファイルが削除できなさそうなので、う～～ん、とかやってて結局無理でした。
なんか、実はファイルを作成しまくって妨害しているチームがいたっぽい？？

つらい。

伍

ファイルの所有者が他人だけど、頑張って読んでね！みたいなの。

nanoとかviとかがSUIDされてて、これを使うと読めます。
find / -user ****とかするといろいろ見つかる。

で、keyword書き込みなんですが、chattr +a（追記のみ）に設定されているのに気が付かず無限に時間が溶けました。
なので、viから:!echo po >> flag.txtみたいに書けば良いじゃん！ってことでした。

気がついたときには時すでにお寿司、ゾンビプロセスで溢れかえっていてcan't forkで何もできずに死にました。

六

クソデカpcapから怪しい通信先を見つけてね！ってやつです。
なんかボクの雑魚PCSだとWiresharkさんが落ちまくってつらかった。

phi16が**†カン†**で見つけました。エスパー怖い。
また、ICMPの通信間隔がモールス信号になってて……というトコロも解いてくれました。プロ。