メモ的ななにか

@Maleic1618

SECCON Beginners CTF 2018 WriteUp && 感想

あらすじ

とある人に影響されて、初めてCTFの大会に参加してきました。↓

2017.seccon.jp

全部自分で解いてみたかったので、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スクリプトと暗号化ファイルが配られる。 スクリプトを読めば以下のアルゴリズムで暗号化されていることが分かる。

  1. 定数A, B, Cを16bitの整数で取る。(スクリプトに書いてある)
  2. seed値をランダムに1つ取る。
  3. 文字列を2byte取り出してseed値とXORを取る。
  4. (A * seed値 + B) + Cを新たなseed値とする。
  5. 文字列がなくなるまで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問解かないといけないらしい、まじか。 pythontcp通信する方法をぐぐって簡単に実装してみる。

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とかもたくさんあるみたいだし、ちょっとずつやってみようという気になりました。次回があればまた出たいですね。

運営の方ありがとうございました!