CPCTF2019 writeup

CPCTF 2019に参加していました。最終的に8100点で3位でした。嬉しいです。全ての問題のwriteupを書くのは大変なので、面白かった問題や回答数の少ない問題についてのwriteupをします。

こうしてみると僕の解いた問題は回答数の多い、誰でも解ける問題ばかりで挑戦をしてこなかったことがよくわかります。深く反省

[Crypto 300]worm_eaten

フラグ 虫に 食べられて 穴が 空いた

$ ruby encrypt.rb > output.txt

http://files.problem.cpctf.space/worm_eaten/encrypt.rb
http://files.problem.cpctf.space/worm_eaten/output.txt

500の方は解けませんでした。Coppersmith's methodを使うんだろうという推測はたちましたが、知識も実装の経験もなく、短時間のCTFでこれに挑戦するリスクはとれませんでした。

300点の方は一般的なRSAですが、平文の殆どがみえています。というわけで3文字分をブルートフォースしてeとnを用いて暗号化、cと同じ暗号文が生成されるものを探します。

from Crypto.Util.number import bytes_to_long
from binascii import unhexlify, hexlify
from ptrlib import *


n = 143683020644322299318564543310032550731362229816998143115532955396082143235946288551633953435584612777128870426064762700722474983419557070478193865039092489162972540442193198467681495674219822666567094248226655965731005254314292588896865658797569039580229607586511231175110747375426393447205505697507722501469
e = 3


c = 0x4bbd08e630c706c6d9e5757d3392f4aef603ed7e34f649666b8796afe772bcee84ca6882fec351dac1003861fc3a8f306a232d381f36714f41119f8df37fab0e07e02965898913bc349ca4aa4a275498ab85444664480d3ff72b707844d57a1b40658529d375ada1df10a1f867527f2686ea27392af83cdbf8f4bd9ebc46604a

for password in brute_force_attack(3):
    x = brute_force_pattern(password)
    m = "FLAG_300{{{}0513a1db877145db49b38f80f8fe7a6c6c9912b67d6a9a6d2c8dada7e15e}}".format(x)
    m2 = int(hexlify(m.encode()), 16)

    if pow(m2, e, n) == c:
        print(m)
        exit()

[Crypto 300]SHAII_we_collide?

HEY can you find SHA-256 collision?

http://shaii_we_collide.problem.cpctf.space/

問題文に示されたページへいくと、次のようなソースコードが示されています。

from wsgiref.simple_server import make_server
import cgi
import hashlib

def app(env, start_response):
    method = env['REQUEST_METHOD']
    path = env['PATH_INFO']
    if method == 'GET' and path == '/':
        # index
        headers = [('Content-Type', 'text/html; charset=utf-8')]
        start_response('200 OK', headers)
        with open('./index.html') as f:
            return [bytes(f.read(), encoding='utf-8')]
    elif method == 'POST' and path == '/collide':
        # collide query
        headers = [('Content-Type', 'text/plain; charset=utf-8')]
        start_response('200 OK', headers)
        # post data
        form = cgi.FieldStorage(fp=env["wsgi.input"], environ=env, keep_blank_values=True)
        x = form["x"].value
        y = form["y"].value

        # !!! collision check !!!
        if x == y: return [bytes('not collide!', encoding='utf-8')]
        ## get sha256
        shax = hashlib.sha256(x.encode()).hexdigest()
        shay = hashlib.sha256(y.encode()).hexdigest()
        ## assert shax and shay is 32byte
        shax = int(shax,16) & ((1<<32)-1)
        shay = int(shay,16) & ((1<<32)-1)
        ## check
        if shax != shay: return [bytes('not collide!', encoding='utf-8')]

        # congrats!
        flag = 'Flag is Here: ***CENSORED***'
        return [bytes(flag, encoding='utf-8')]

    # doesn't match
    headers = [('Content-Type', 'text/plain; charset=utf-8')]
    start_response('400 Bad Request', headers)
    return [bytes('Error', encoding='utf-8')]

PORT = 8383
httpd = make_server('', PORT, app)
httpd.serve_forever()

どうやらsha256をとって衝突する異なる2つの文字列を入力すれば良いようですが、それぞれ int(shax,16) & ((1<<32)-1) のように切り詰められていて簡単に衝突させることが出来ます。

書くだけです。すぐに衝突する組み合わせ 01@[, 09xtが見つかります。

from ptrlib import *
import hashlib

table = {}

for password in brute_force_attack(4):
    x = brute_force_pattern(password)
    shax = hashlib.sha256(x.encode()).hexdigest()
    shax = int(shax,16) & ((1<<32)-1)
    if shax in table:
        print(table[shax])
        print(x)
        exit()
    else:
        table[shax] = x

[Binary 300]fast_fibonacci

fib(1)=fib(2)=1
binary

注：そのまま実行するとSegmentation fault (core dumped)と表示されるか、何も表示されず実行が終了もしない、のどちらかになると思いますが、それが正常です。

問題名を見ると、フィボナッチ数列の第n項の計算が遅いのでその後のフラグ出力パートが実行できていないことがわかります。オーバーフローするように注意しながら早いフィボナッチを書いて fib(0x53e691) の結果が f0bbeb3d になることを突き止め、 gdbでステップ実行しながら fib関数の呼び出しを飛ばして、 eaxに f0bbeb3dを代入した状態で decode関数を呼び出すとフラグが手に入ります。（b main r set $pc=0x565557b8 set $eax=0xf0bbeb3d)

[Crypto 300] [input]

stage7だけ解法を書いておきます。

def f(s):
    m = 0
    for c in s:
        m += (ord(c) - ord('a')) + 1

    return "".join([chr((ord(c) - ord('a') + m) % 26 + ord('a')) for c in s])

from ptrlib import *
import string

for password in brute_force_attack(5, table_len=26):
    x = brute_force_pattern(password, table=string.ascii_lowercase)

    if f(x) == "input":
        print(x)
        exit()