Ark's Blog

数学とか競プロとか参加記とか備忘録とか

ようこそ

SECCON Beginners 2018東京 参加記

SECCON Beginners 2018東京 に参加してきました。

参考: 2018.seccon.jp

CTF経験歴は、先日行われたSECCON Beginners CTF 2018が初めてまともにやったCTFで、まだまだ初心者という感じです。特にPwnが苦手だったので、強くなりたいという気持ちで今回SECCON Beginnersに申し込みました。

スケジュール

  1. 開演、オリエンテーション(CTFとは?)
  2. 講義1(Crypto)
  3. 講義2(Pwn)
  4. CTF演習問題
  5. CTF解説
  6. 交流会

開演、オリエンテーション(CTFとは?)

まず、CTFとは何なのかについてざっくりとしたお話がありました。 環境構築してて、あまり真面目に聞いてなかったです(ごめんなさい)

講義1(Crypto)

前半はCryptoの講義でした。

「Cryptoとは?」からはじまって「暗号の種類」「modやextgcd」「RSA暗号」「線形合同法」などの解説が、演習を交えてありました。

競プロでmodやextgcdなどには慣れていたので比較的楽に聞けました。 脆弱性をパズルみたいに解く感覚が楽しいですね。

最後に「クラウドを支えるこれからの暗号技術」の本が紹介されていました。この本の存在は以前から知ってて気になってたけど、絶賛されてたので読みたい欲がいっそう高まりました。

講義2(Pwn)

後半はPwnの講義でした。

「Pwnとは?」からはじまって「アセンブリ」「gdb(gdb-peda)の使い方」「BOF」などの解説が、演習を交えてありました。

BOFの仕組みはわかるんだけど、実際に「アセンブリを読んで解析し、どのように入力を与えればいいか判断する」の流れがどうもまだ苦手です。

アセンブリの気持ちがわかるようになりたい。

付録資料にFormat String Bugの解説があったので復讐の意味も込めて読もう。

CTF演習問題

講義のあとは、実際にCTFがはじまりました。

問題はcryptoとpwnとmisc。

以下、writeup。

Misc: Welcome (100)

フラグがあるのでそれをコピペ

Misc: Tekeisan4b in Shinagawa (100)

Webページに「5 + 3 * 8」のような計算式とtextareaとbuttonがあり、計算してsubmitを100回繰り返す問題。

大真面目に手で計算すると時間が溶けるので適当にJS書いた。

let e = document.querySelector("body > div")
let x = eval(e.innerHTML.replace( /<a id="a">/g, "").replace( /<a id="b">/g, "").replace( /<a id="c">/g, "").replace( /<\/a>/g , ""));
let e2 = document.querySelector("body > form")
e2.children[0].value = x
e2.children[1].click()

これをコンソールで100回コピペするとフラグが降ってくる。 コピペする部分も自動化できるともっと良さそう。

Misc: Decremented (150)

実行ファイルが渡されるので実行すると

This FLAG was decremented! : csd1^vq^dZebYRf`Oc[PU_g

と出力される。フラグの形式はctf4b{...ではじまるのでそれと問題タイトルから察して、フラグの各文字のi番目(0-base)がiだけ減算してることが推測できるので、デコードするプログラムを書いた。

import std.stdio;

void main() {
  string str = "csd1^vq^dZebYRf`Oc[PU_g";
  string ans = "";
  foreach(char i, c; str) {
    ans ~= c+i;
  }
  ans.writeln;
}

実行すると、フラグが出てきた。

Crypto: Factoring (100)

 N=pq=6300099813268620937が与えられるので、これを素因数分解して p+qを求める問題。

factordbに投げたら終わった。

Crypto: Go Fast (100)

 2^{4805} \bmod 97を求める問題。

python

2**4805%97

を実行した。たぶんpow(2, 4805, 97)を実行するほうが想定解。

Crypt: Simple RSA (200)

RSAにおける p, q, e, Cが与えられるので、 Cを復号する問題。

RSAの復号手順に従って、 M=C^d \bmod pqで復号できる。

Crypt: Find primes (300)

RSA暗号によって計算された10個の (N_i := p_i q_i, C_i := M^e \bmod N_i)の組と、それを生成するpythonプログラムが与えられ、計算に使われた M = \text{FLAG}を特定する問題。

ソースコードをよく見ると、  \left|\{p_0, p_1, \cdots, p_9\} \cap  \{q_0, q_1, \cdots, q_9\}\right|  = 1 となっていて、重複する素数がちょうど1組存在する。

例えば p_1 = q_3だった場合、 \gcd(N_1, N_3) = \gcd(p_1q_1, p_3q_3) = p_1 (=q_3)となり、 p_1ユークリッドの互除法を用いると高速に計算できる。

あとは q_1 := \frac{N_1}{p_1}がわかるのでSimple RSAと同様に復号する。

重複する素数の組の探索は、全探索でも O(10^2)なので問題ない。

import std.stdio, std.format, std.string, std.algorithm, std.bigint, std.numeric;

void main() {
  long num = 10;
  auto ns = new BigInt[num];
  auto cs = new BigInt[num];
  foreach(i; 0..num) {
    string str = readln.chomp;
    ns[i] = BigInt(str.split(", ")[0][1..$-1]);
    cs[i] = BigInt(str.split(", ")[1][0..$-2]);
  }
  foreach(i; 0..num) foreach(j; i+1..num) {
    BigInt x = gcd(ns[i], ns[j]);
    if (x != 1) {
      BigInt n = ns[i];
      BigInt p = x;
      BigInt q = n / x;
      BigInt e = 65537;
      BigInt c = cs[i];
      format!"n: %s"(n).writeln;
      format!"p: %s"(p).writeln;
      format!"q: %s"(q).writeln;
      format!"e: %s"(e).writeln;
      format!"c: %s"(c).writeln;
    }
  }
}
n: 23203514436239386141884720808951888606243429254418529685411124599189790670515750636981772606252925469026142674382148624921977894267006031492038153725489876962403180371473102530102732599653989201101910451173626525262021510742483000431313391431411389217949450701194799706943650674879814926160972152842487844095947738084961383398977224634488523329920497781757661425124260607004266320389214826410788340421934149343160673898878401828315023436893415970661781909813540223355786068382291673103798099913917541672200530219362247882103018247007666297106535132966052056660371881554314640924323417090740930552878117330055763533961
p: 143802624736675216342710404915754614842873419168686658279427585653414623436476419989672612385229699476258452229067253811269198304208169401618654685988811740091976850467779283580159792957474789300280741195862884532321298588199611478270406356671560047246118715145407014239153093512641561015616750259554042960111
q: 161356682318758782081550196426209598124358181081940657376060286118222449755911139612848464281699995463698160370588936389298714369957803109222333347181782718976637588411504381920911773072370649627611622012028833124525874414893403443500618948696647685158525274931214589176898025127628996093027261890032424185351
e: 65537
c: 10641876953514494363551365488914263576588859578224118582010329856969670782205947350332340630609455117095461657997138155352385701347202338478420098239900105535084531626029893016140334363672567686504771708982888684340529755427706617414673068132495859361216975564167820421835597772595449178648016931188305573541002413800977713752784586950267879696000170572444615986634865896739814073627224781642998021099369930740049800949061107309656150548892166959729071353329416262316064864847178125325367790081174657678979091199289266270020110158559403638369050036498811722833582681635181135436986622103598208970781207235420837980907

ここで、時間切れとなって本番は間に合わなかった(悲しい)。 一応、この結果を使って復号したら

ctf4b{GCD_IS_GOD}

でフラグが取れた。

結果

f:id:ark4rk:20181006221408p:plain f:id:ark4rk:20181006221417p:plain

Score: 750で4位でした。あと少し時間があればfind primesも解けて3位圏内だったのでくやしい。

ただ、今回はpwnに強くなろうと来たのに、一問も解かなかったのは反省。一問あたりにかかってしまう時間が長くなりそうで逃げてしまった・・・

ちゃんと帰って復習しよう・・・

CTF解説

出題された問題の解説がありました。

pwnの解説のときに「ここはジャンプがあるのでfor文っぽいので〜〜」みたいな表現が出てきすごいなあと思いました。絶対アセンブリ感覚を、ぼくも身につけたい。勉強します。

交流会

最後は交流会でした。普段は学生しか集まらないような空間で交流会をする経験が多かったので、今回は社会人の方も混ざってて色々な話ができてよかったです。

感想

やっぱりCTFたのしいです。今学部4年生なのですが、もっと前からやっておくべきでした。 あまり時間が取れないけど、気長に続けられたらいいなと思います。

運営の方々、講師の方々、問題出題者の方々、たのしい機会をありがとうございました。