SECCON Beginners CTF 2018 WriteUp && 感想
あらすじ
とある人に影響されて、初めてCTFの大会に参加してきました。↓
全部自分で解いてみたかったので、1人チームでやりました。他の人の参考になればと思い、いろいろ書いてみます。
解いたのは以下の5問。
- Crypto
- RSA is Power
- Streaming
- Misc
- [Warmup]plain mail
- [Warmup]Welcome
- てけいさんえくすとりーむず
問いた順に書いていきます。
WriteUp
[Warmup]Welcome
公式のルール欄にあるIRCチャンネルのトピックにそのままflagが置いてある。ゲット。
お前らIRC使え??という運営のメッセージなんでしょうか。 ともかく初ポイントもらえてラッキー。
RSA is Power
3つの数字が与えられるのみ。 RSAのアルゴリズムを調べると、おそらくそのうちの2つが公開鍵で残りの1つが暗号化された文章っぽい。 (CはCiphertextの略?)
どのくらいの大きさの合成数なら素因数分解出来るのか分からないけど、とりあえず適当に調べて出てきたmsieveというソフトにかけてみる。
…素因数分解できた!
$ tail msieve.log Sat May 26 15:33:09 2018 matrix includes 64 packed rows Sat May 26 15:33:09 2018 matrix is 25717 x 25829 (2.6 MB) with weight 619170 (23.97/col) Sat May 26 15:33:10 2018 sparse part has weight 422115 (16.34/col) Sat May 26 15:33:10 2018 commencing Lanczos iteration Sat May 26 15:33:10 2018 memory use: 2.6 MB Sat May 26 15:33:19 2018 lanczos halted after 408 iterations (dim = 25716) Sat May 26 15:33:19 2018 recovered 17 nontrivial dependencies Sat May 26 15:33:19 2018 p39 factor: 299681192390656691733849646142066664329 Sat May 26 15:33:19 2018 p39 factor: 324144336644773773047359441106332937713 Sat May 26 15:33:19 2018 elapsed time 00:03:33
あとはRSAに従って復号すればOK。 でもこれを入力してもincorrectになる。flagはsec4b{...}の形なのでそりゃそうだ。
16進数に直してasciiでデコードすればflagになった。よかった。
[Warmup] plain mail
与えられたファイルはパケットキャプチャのログらしい。とりあえずwiresharkで開いてみる。 SMTPの文字が見えるので、メール送信時のキャプチャっぽい。
中見を見ると
I will send secret information. First, I will send encrypted file. Second, I wll send you the password.
とのこと。2通目のメールは添付ファイルが、3通目はpassっぽい文字列がある。base64の文字列を適当なファイルにコピーしておいて、
$ cat base64.txt | base64 -d > file.zip $ unzip file.zip
とするとパスワードを聞かれるので3通目のpassを打ち込めばflagが手に入る。やったぜ。
Streaming
pythonのスクリプトと暗号化ファイルが配られる。 スクリプトを読めば以下のアルゴリズムで暗号化されていることが分かる。
- 定数A, B, Cを16bitの整数で取る。(スクリプトに書いてある)
- seed値をランダムに1つ取る。
- 文字列を2byte取り出してseed値とXORを取る。
- (A * seed値 + B) + Cを新たなseed値とする。
- 文字列がなくなるまで3, 4を繰り返す。
つまり最初のseed値が正しければ以降は4のアルゴリズムで次以降の正しいseed値が分かる。 flagの形式が"ctf4b"から始まるので、暗号文の先頭2byteと"ct"のXORを取ったものが最初のseed値と予想。
というわけで適当にスクリプトを書いて見る。
import os class Stream: A = 37423 # A-C = 2816 B = 61781 # B-C = 27174 C = 34607 def __init__(self, seed): self.seed = seed % self.C def __iter__(self): return self def next(self): #最初に使われるseedがずれないようにちょっと書き換える tmp = self.seed self.seed = (self.A * self.seed + self.B) % self.C return tmp g = Stream(32186) f = open('encrypted', 'rb') encrypted = ['1ece', '0c65', '5f06', '3a94', '4957', '171d', '17f5', '3f59', '409c', '4a9d', '3119', '268d', '513e', '03fd', '52ce', '1656'] decrypted = '' a = 0 for data in encrypted: rand = g.next() a = int(data, 16) ^ rand decrypted += chr(a / 256) decrypted += chr(a % 256) print decrypted
binaryファイルの読み書きやったことないからencryptedファイルの中見をバイナリエディタで呼んで手打ちしました。恥ずかしい…。
でも無事flagをゲット。やったー
てけいさんえくすとりーむず
指定されたホスト、ポートにアクセスすると3桁くらいの計算問題が出される。300秒で100問解かないといけないらしい、まじか。 pythonでtcp通信する方法をぐぐって簡単に実装してみる。
import socket def parse(str): token = str.split(" ") token[0] = int(token[0]) token[2] = int(token[2]) if token[1] == '+': return token[0] + token[2] elif token[1] == '-': return token[0] - token[2] elif token[1] == '*': return token[0] * token[2] elif token[1] == '/': return token[0] / token[2] host = "tekeisan-ekusutoriim.chall.beginners.seccon.jp" port = 8690 client = socket.socket(socket.AF_INET, socket.SOCK_STREAM) client.connect((host, port)) for i in range(0,100): res = client.recv(4096).decode() print(res) ans = str(parse(res.split("\n")[-1])) + "\n" print(ans) client.send(ans.encode()) print(client.recv(4096).decode())
sendする時に改行も送らないと次の問題に進まないので注意。
実行するとだだだーーっと問題と回答のやり取りが流れてflagをゲット。気持ちいい。
$ python3 calc.py Welcome to TEKEISAN for Beginners -extreme edition- --------------------------------------------------------------- Please calculate. You need to answered 100 times. e.g. (Stage.1) 4 + 5 = 9 ... (Stage.99) 4 * 4 = 869 [!!] Wrong, see you. --------------------------------------------------------------- (Stage.1) 543 * 649 = 352407 (Stage.2) 948 - 639 = 309 (中略) (Stage.99) 551 * 536 = 295336 (Stage.100) 980 + 502 = 1482 Congrats. Flag is: "ctf4b{ekusutori-mu>tekeisann>bigina-zu>2018}"
[未回答] Well Known
サーバーのURLとポートに加え、サーバーで動いてるPythonスクリプトが配られる。 数字を入れると数字が帰ってくる。わからん。
Signerというclassがあるので、電子署名かなあと思ってぐぐるとヒット。DSA署名らしい。 アルゴリズムをググって手計算でなんか出来ないかなあと考えるけど乱数が入力ごとに固定されないので計算できずうまくいかずにタイムアップになってしまった。ぐぬぬ…。
後で他の人にWriteUpを見た所、乱数の生成は
k = pow(int(hashlib.sha1(data).hexdigest(), 16), rnd, key.q)
なので、SHA-1 hashが衝突するものを2つinputで持ってくればよいらしい。hashは衝突しないものだという先入観があってわからなかった。 惜しいところまでいけてたのかも。解説読むとなお悔しい。
感想
最終スコアは393ptで234位でした。思ってたより解けたのでうれしい。 でもRSAとかStreamingは私が解いたときは200-300点くらいあったのに、最終的に100点くらいになってしまったのはちょっと悲しかった。
知らないことたくさんあったけど、ぐぐったら問題へのアクセス方法がいろいろ出てきたので問いてる間はずっと手を動かして考えられた。面白かった。 常設CTFとかもたくさんあるみたいだし、ちょっとずつやってみようという気になりました。次回があればまた出たいですね。
運営の方ありがとうございました!