TokyoWesterns CTF 5th 2019 Writeup

TokyoWesterns CTF 5th 2019にチーム./Vespiaryとして参加して、正の点数を入れた53位/1005チーム、日本国内のチームに限れば4位/131チームでした。以下はそのWriteupになります。

Challenges

challenges	genre	score
real-baby-rsa	Crypto	40
Simple Logic	Crypto	95
Happy!	Crypto	242

見ての通りCryptoしか解いてません、CryptoジャンルでRevとの複合問題以外は全部解けたので満足しています。

real-baby-rsa

RSA暗号による暗号化をフラグに対し1文字ずつ施したものが与えられる。
もちろん公開鍵であるは与えられている。というわけでprintableな文字を片っ端から暗号化したものを辞書として持ち与えられた暗号文に対し照合を行って各文字を復元し、それをつなげればフラグとなる。

使用コード

import string


if __name__ == '__main__':
    # "pubkey"
    N = 36239973541558932215768154398027510542999295460598793991863043974317503405132258743580804101986195705838099875086956063357178601077684772324064096356684008573295186622116931603804539480260180369510754948354952843990891989516977978839158915835381010468654190434058825525303974958222956513586121683284362090515808508044283236502801777575604829177236616682941566165356433922623572630453807517714014758581695760621278985339321003215237271785789328502527807304614754314937458797885837846005142762002103727753034387997014140695908371141458803486809615038309524628617159265412467046813293232560959236865127539835290549091
    e = 65537

    flag = ""

    # list up
    with open("output") as f:
        c_list = [int(c.strip()) for c in f.readlines()]

    print(c_list)

    char_dic = {}
    for char in string.printable:
        c_char = pow(ord(char), e, N)
        char_dic[c_char] = char

    for c in c_list:
        flag += char_dic[c]

    print(flag)

Flag

TWCTF{padding_is_important}

Simple Logic

フラグを下記に示すアルゴリズムで暗号化したものと別の平文- 暗号文ペアが6つ与えられる。
また、暗号化のアルゴリズムは鍵と平文に対しを765回行うことである。
ここで、暗号化の処理の中では、平文の最下位のバイト(下位8ビット)は下の位からの繰り上がりが無いことから256通りの総当りを行って6つのペアで比較することで鍵の最下位バイトを推測(いくつか候補があるため確定ではない)することができる。
鍵の下位2バイト(下位16ビット)は鍵の下位バイト目をとおくとのようになる。これによって下位2バイトまでの鍵の候補は下位1バイトの鍵候補数(ちなみにこれは2通り) * 256通りである。これを下位2バイトに対して総当りすることでまた鍵の候補を手に入れることができる。
これを下位3バイト(下位24ビット)に対しても同様に行い、以下同様にして16バイト分の鍵の候補を導出したものを復号アルゴリズムに適用してフラグを導出することができる。

使用コード

def encrypt(msg, key, bits):
    mask = (1 << bits) - 1
    enc = msg
    for _ in range(765):
        enc = (enc + key) & mask
        enc = enc ^ key
    return enc


def decrypt(msg, key, bits):
    mask = (1 << bits) - 1
    enc = msg
    for _ in range(765):
        enc = enc ^ key
        enc = (enc - key) & mask
    return enc


def all_pairs_check(pairs, key, bits):
    mask = (1 << bits) - 1
    for pair in pairs:
        if encrypt(pair['plain'], key, bits) != (pair['enc'] & mask):
            return False

    return True


if __name__ == '__main__':
    enc_flag = 0x43713622de24d04b9c05395bb753d437
    _list = [
        {'plain': 0x29abc13947b5373b86a1dc1d423807a, 'enc': 0xb36b6b62a7e685bd1158744662c5d04a},
        {'plain': 0xeeb83b72d3336a80a853bf9c61d6f254, 'enc': 0x614d86b5b6653cdc8f33368c41e99254},
        {'plain': 0x7a0e5ffc7208f978b81475201fbeb3a0, 'enc': 0x292a7ff7f12b4e21db00e593246be5a0},
        {'plain': 0xc464714f5cdce458f32608f8b5e2002e, 'enc': 0x64f930da37d494c634fa22a609342ffe},
        {'plain': 0xf944aaccf6779a65e8ba74795da3c41d, 'enc': 0xaa3825e62d053fb0eb8e7e2621dabfe7},
        {'plain': 0x552682756304d662fa18e624b09b2ac5, 'enc': 0xf2ffdf4beb933681844c70190ecf60bf}
    ]

    bits = 128
    key = 0
    candidate_keys = [0]

    for _bytes in range(bits // 8):
        _bits = _bytes * 8
        current_candidate_keys = []
        for byte_key in range(256):
            for candidate_key in candidate_keys:
                _key = candidate_key + byte_key * (2 ** _bits)
                if all_pairs_check(_list, _key, (_bytes + 1) * 8):
                    current_candidate_keys.append(_key)

        candidate_keys = [x for x in current_candidate_keys]

    print("[+]: candidate_keys -> {}".format(list(map(lambda x: hex(x), candidate_keys))))

    for key in candidate_keys:
        print("[+]: flag is here -> TWCTF{{{}}}".format(hex(decrypt(enc_flag, key, bits))[2:]))

Flag

TWCTF{ade4850ad48b8d21fa7dae86b842466d}

Happy!

CRT-RSAの問題。普通のCRT-RSAと違うのは公開鍵の生成に外部から与えたパラメータを用いてとしているところである。
また、ソースコードによればのビット数は700以上であり、のビット数が2295bitであったことからのビット数は765bitであると推測され、同時にであることも推測される。以下ではこの推測に基づいて考える。
この問題では公開鍵の保存方法に問題があり、秘密鍵であるが漏れてしまっている。これを利用してからを求めることを考える。
であるから両辺にを掛けるとである。これを合同式を使わずに表すと整数を用いて。
これに更に両辺にを掛け、を用いるとである。これを合同式にすると。
上でのはEuclid互除法を用いることで求めることができるのでこれを求め、先程の合同式の両辺に掛けるととなる。
を解とするモニック合同方程式の形に持ち込むことができたのでCoppersmith's Theoremを利用することを考える。この方程式は2次なのでであれば良く、のビット数よりこれは満たされている。
SageMathを用いてが求まるので後はを求め、与えられたソースコードのを上書きし復号すればフラグが出現する。使用するコマンドは

> ruby happy keygen 765 2 prikey pubkey
> ruby happy decrypt prikey flag.enc output

使用コード

sage: n = 5452318773620154613572502669913080727339917760196646730652258556145398937256752632887555812737783373177353194432136071770417979324393263857781686277601413222025718171529583036919918011865659343346014570936822522629937049429335236497295742667600448744568785484756006127827416640477334307947919462834229613581880109765730148235236895292544500644206990455843770003104212381715712438639535055758354549980537386992998458659247267900481624843632733660905364361623292713318244751154245275273626636275353542053068704371642619745495065026372136566314951936609049754720223393857083115230045986813313700617859091898623345607326632849260775745046701800076472162843326078037832455202509171395600120638911
sage: cf = 25895436290109491245101531425889639027975222438101136560069483392652360882638128551753089068088836092997653443539010850513513345731351755050869585867372758989503310550889044437562615852831901962404615732967948739458458871809980240507942550191679140865230350818204637158480970417486015745968144497190368319745738055768539323638032585508830680271618024843807412695197298088154193030964621282487334463994562290990124211491040392961841681386221639304429670174693151
sage: K = Zmod(n)
sage: PR.<x> = Polynomialring(K)
sage: cf_inv = xgcd(cf, n)[1]
sage: cf_inv  -2249345702092523066854742350215149116416859677618194270409191492480933128500527239002357382040286220628542908633760619718020318862762179160313205310065653124053891797903672229971967453188884376088470963333006057687741241573722015848262880741528030132669466984038867943213123080605122134845253150074165551805580583789437805883858045929618356220833327713859151787929015040819461870240823640707071318502251137747082685885265753285753429622655389962762875765839373176940943904189083878886577385177994761666798781194931165369158189904098832117847743192922856376144912379516797927684252737181470545077929510269532122946061866421139568441244990499842647843345736439336484949373015531153085847596295
sage: cf_inv += n
sage: f = x^2 - cf_inv * x
# ここsmall_rootsのパラメータいじれば(確かbetaっていう名前だった気が)0を検出せずに済みそう
sage: f.small_roots(X=2^765)
[0,  166878663790065040663149504970052368124427462024107500159158464138407657299730521908976684364578086644682045134207945137293534705688910696520830729908263578233018529387676221035298300775812585471932551347478303730822844748034186479]
sage: p = 166878663790065040663149504970052368124427462024107500159158464138407657299730521908976684364578086644682045134207945137293534705688910696520830729908263578233018529387676221035298300775812585471932551347478303730822844748034186479

以下、qを求めて復号するだけなので略

Flag

TWCTF{I_m_not_sad__I_m_happy_always}

感想

難易度が高い問題が多く、最近の学生向けCTFに出ていた時とは違った感覚で楽しむことができました。特にHappy!はRSAの既存の攻撃方法に加えて数学的な側面も求められる問題で非常に楽しかったです。
反省点としてはHappy!を解いた時点で解ける問題が無く(pwnもrevも苦手、というかチームメイトに任せきりで触ったことが無い)長い時間手持ち無沙汰になってしまったことです。これを機に低レイヤーに触れていきたいと思っています(これ毎回言ってる気がする)。
最後になりますが、このような楽しいCTFを開いてくださったTokyoWesternsの皆様、本当にありがとうございました。