InterKosenCTF 2020 Write-up - s4tt01237’s diary

はじめに
Misc
- No pressure [335pts, 16solves]
Crypto
まとめ

はじめに

2020/09/05 ~ 2020/09/06に開催されたInterKosenCTF 2020にチームで参加しました。
チームとしては22問解いて5位でした (191チーム中)。
今回は自分がコンテスト中に解いた4問と終了後に解いた1問のWrite-upを書きます。

Misc

No pressure [335pts, 16solves]

nc misc.kosenctf.com 10002

> nc misc.kosenctf.com 10002
message: KosenCTF
encrypted! : qc4CwzFIKN9yLB7t1HeLXFYHFyz/H0eeWB08VryfxnsueLy4Nj8fCh575jQ0A2Ix0dSHDYZSY0saeOehV9Tgn7xwT3rez1znfP8DnDCWxa9B
message: ABCDEFGH
encrypted! : M0MHUBRRP28gNeygAGA+C/JmzeNsB+PxMRnPjfN8wfmYz85RXJKQ+P8KGOR24JiEhFe812zsOiujSb+H4LIVIFgVwDGSFPFB65A1TrovAgY98lme6w==
[snip]

chall.py

from Crypto.Cipher import ARC4
from hashlib import sha256
from base64 import b64encode
import zlib
import os

flag = open("./flag.txt", "rb").read()

nonce = os.urandom(32)
while True:
    m = input("message: ")
    arc4 = ARC4.new(sha256(nonce + m.encode()).digest())
    c = arc4.encrypt(zlib.compress(flag + m.encode()))
    print("encrypted! :", b64encode(c).decode())

アプローチ：zlibで利用されているデータ圧縮アルゴリズム(Deflate)の性質を利用する

この問題で注目すべき処理は下記です。

c = arc4.encrypt(zlib.compress(flag + m.encode()))

flagと入力文字列を連結し、zlibで圧縮した値をRC4で暗号化しています。

zlibとRC4には以下ような特徴があります。

zlibは入力文字列がflagに内包されていれば、データ圧縮効率が上がる（圧縮結果が小さくなる）
RC4は平文と暗号文の長さが一致する

つまり、入力文字列がflagに内包されている場合は暗号文が短くなります。

以下は簡単なテストスクリプトです。

from pwn import *
from base64 import *

r = remote('misc.kosenctf.com', 10002)

def send_message(msg):
    recv = r.recvuntil('message: ')
    r.sendline(msg.encode())
    recv = r.recvline()
    enc = base64.b64decode(recv.decode().split(' ')[-1].strip())
    enc_length = len(enc)
    print(f'msg: {msg}')
    print(f'len(enc(msg)): {enc_length}')

send_message('Kosen')
send_message('KosenCTF{')
send_message('KosenCTF*')
send_message('NITctf')

msg: Kosen
len(enc(msg)): 81
msg: KosenCTF{
len(enc(msg)): 81
msg: KosenCTF*
len(enc(msg)): 82
msg: NITctf
len(enc(msg)): 84

入力文字列がflagに内包されている場合、暗号文が短くなっていることが分かります。そのため、flagを1文字ずつ求めていくことが可能です。

以下はソルバになります。

from pwn import *
from base64 import *
import string

flag = 'KosenCTF{'

r = remote('misc.kosenctf.com', 10002)
while True:
    for c in string.printable:
        recv = r.recvuntil('message: ')
        r.sendline(flag.encode() + c.encode())
        recv = r.recvline()
        enc = base64.b64decode(recv.decode().split(' ')[-1].strip())
        enc_length = len(enc)
        if enc_length == 81:
            flag += c
            print(flag)
            break

KosenCTF{D
KosenCTF{DE
KosenCTF{DEF
KosenCTF{DEFL
KosenCTF{DEFLA
KosenCTF{DEFLAT
KosenCTF{DEFLATE
KosenCTF{DEFLATE_
KosenCTF{DEFLATE_i
KosenCTF{DEFLATE_is
KosenCTF{DEFLATE_is_
KosenCTF{DEFLATE_is_a
KosenCTF{DEFLATE_is_an
[snip]
KosenCTF{DEFLATE_is_an_algorithm_that_combines_LZ77_and_Huffman_coding}

KosenCTF{DEFLATE_is_an_algorithm_that_combines_LZ77_and_Huffman_coding}

Crypto

ciphertexts [201pts, 33solves]

Since there are two ciphertexts, it is easy to solve, isn't it?

n1 = 112027309284322736696115076630869358886830492611271994068413296220031576824816689091198353617581184917157891542298780983841631012944437383240190256425846911754031739579394796766027697768621362079507428010157604918397365947923851153697186775709920404789709337797321337456802732146832010787682176518192133746223
n2 = 1473529742325407185540416487537612465189869383161838138383863033575293817135218553055973325857269118219041602971813973919025686562460789946104526983373925508272707933534592189732683735440805478222783605568274241084963090744480360993656587771778757461612919160894779254758334452854066521288673310419198851991819627662981573667076225459404009857983025927477176966111790347594575351184875653395185719233949213450894170078845932168528522589013379762955294754168074749
e1 = 745699
e2 = 745709

c1 = 23144512980313393199971544624329972186721085732480740903664101556117858633662296801717263237129746648060819811930636439097159566583505473503864453388951643914137969553861677535238877960113785606971825385842502989341317320369632728661117044930921328060672528860828028757389655254527181940980759142590884230818
c2 = 546013011162734662559915184213713993843903501723233626580722400821009012692777901667117697074744918447814864397339744069644165515483680946835825703647523401795417620543127115324648561766122111899196061720746026651004752859257192521244112089034703744265008136670806656381726132870556901919053331051306216646512080226785745719900361548565919274291246327457874683359783654084480603820243148644175296922326518199664119806889995281514238365234514624096689374009704546

main.py

from Crypto.Util.number import *
import gmpy2
from flag import flag

p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
n1 = p * q
n2 = p * q * r

e1 = getPrime(20)
e2 = int(gmpy2.next_prime(e1))

m = bytes_to_long(flag)
c1 = pow(m, e1, n1)
c2 = pow(m, e2, n2)

print("n1 = {}".format(n1))
print("n2 = {}".format(n2))
print("e1 = {}".format(e1))
print("e2 = {}".format(e2))
print()
print("c1 = {}".format(c1))
print("c2 = {}".format(c2))

アプローチ：合同式を変形してCommon Modulus Attack

main.pyを読むと $e_1, e_2$ が互いに素であり、同一の $m$ を暗号化しているため、 $c_1$ を $\bmod n_2$ 上で表現できればCommon Modulus Attackに持ち込めることが分かります。

ここで、 $n_2$ は $n_2 = r \times n_1 = r \times p \times q$ であるため、 $c_1$ は $\bmod n_2$ 上で $rc_1$ と表現できます。
そのため、 $c_1, c_2$ にそれぞれ $r^{e_1}, r^{e_2}$ をかけることで、 $(rm)^{e_1} \bmod n_2, (rm)^{e_2} \bmod n_2$ となるので、 $rm$ をCommon Modulus Attackによって求めることが可能になります。

以下はソルバになります。

from Crypto.Util.number import *
import gmpy2

def decrypt(n1, n2, e1, e2, c1, c2):
    r = n2 // n1
    new_c1 = (c1 * pow(r, e1, n2)) % n2
    new_c2 = (c2 * pow(r, e2, n2)) % n2
    
    g, x, y = gmpy2.gcdext(e1,e2)

    if x < 0:
        x = abs(x)
        new_c1_inv = inverse(new_c1, n1)
        rm = (pow(new_c1_inv, x, n1) * pow(new_c2, y, n1)) % n1
    else:
        y = abs(y)
        new_c2_inv = inverse(new_c2, n1)
        rm = (pow(new_c1, x, n1) * pow(new_c2_inv, y, n1)) % n1

    return rm, r

n1 = 112027309284322736696115076630869358886830492611271994068413296220031576824816689091198353617581184917157891542298780983841631012944437383240190256425846911754031739579394796766027697768621362079507428010157604918397365947923851153697186775709920404789709337797321337456802732146832010787682176518192133746223
n2 = 1473529742325407185540416487537612465189869383161838138383863033575293817135218553055973325857269118219041602971813973919025686562460789946104526983373925508272707933534592189732683735440805478222783605568274241084963090744480360993656587771778757461612919160894779254758334452854066521288673310419198851991819627662981573667076225459404009857983025927477176966111790347594575351184875653395185719233949213450894170078845932168528522589013379762955294754168074749
e1 = 745699
e2 = 745709
c1 = 23144512980313393199971544624329972186721085732480740903664101556117858633662296801717263237129746648060819811930636439097159566583505473503864453388951643914137969553861677535238877960113785606971825385842502989341317320369632728661117044930921328060672528860828028757389655254527181940980759142590884230818
c2 = 546013011162734662559915184213713993843903501723233626580722400821009012692777901667117697074744918447814864397339744069644165515483680946835825703647523401795417620543127115324648561766122111899196061720746026651004752859257192521244112089034703744265008136670806656381726132870556901919053331051306216646512080226785745719900361548565919274291246327457874683359783654084480603820243148644175296922326518199664119806889995281514238365234514624096689374009704546

rm, r = decrypt(n1, n2, e1, e2, c1, c2)
print(rm)
print(long_to_bytes(rm//r))

1450137700311703879663236107307914645851657803708681805893924798730674006177116062897188857467248320975095348348900554537405990687078193743342999747402279742651073686647363070591701007576551983207170287559
b'KosenCTF{HALDYN_D0M3}'

KosenCTF{HALDYN_D0M3}

bitcrypto [326pts, 17solves]

Yoshiking, the master of bit crypto, has the flag. Ask him for the flag.
nc crypto.kosenctf.com 13003

server.py

from Crypto.Util.number import *
from secret import flag

def legendre_symbol(x, p):
    a = pow(x, (p-1) // 2, p)
    if a == 0:
        return 0
    elif a == 1:
        return 1
    else:
        return -1

def key_gen(bits):
    p = getPrime(bits)
    q = getPrime(bits)
    n = p * q

    while True:
        z = getRandomRange(2, n)
        a, b = legendre_symbol(z, p), legendre_symbol(z, q)
        if a == -1 and b == -1:
            break

    return (n, z), (p, q)

def enc(pubkey, m):
    n, z = pubkey
    bits = [int(b) for b in "{:b}".format(m)]

    c = []
    for b in bits:
        while True:
            x = getRandomRange(2, n)
            if GCD(x, n) == 1:
                break
        c.append( ((z**b) * (x**2)) % n )
    return c

def dec(privkey, c):
    p, q = privkey
    m = ""
    for b in c:
        if legendre_symbol(b, p) == 1 and legendre_symbol(b, q) == 1:
            m += "0"
        else:
            m += "1"
    return int(m, 2)

def main():
    pubkey, privkey = key_gen(256)

    keyword = "yoshiking, give me ur flag"
    m = input("your query: ")
    if any([c in keyword for c in m]):
        print("yoshiking: forbidden!")
        exit()

    if len(m) > 8:
        print("yoshiking: too long!")
        exit()

    c = enc(pubkey, bytes_to_long(m.encode()))
    print("token to order yoshiking: ", c)

    c = [int(x) for x in input("your token: ")[1:-1].split(",")]
    if len(c) != len(set(c)):
        print("yoshiking: invalid!")
        exit()

    if any([x < 0 for x in c]):
        print("yoshiking: wow good unintended-solution!")
        exit()

    m = long_to_bytes(dec(privkey, c))
    if m == keyword.encode():
        print("yoshiking: hi!!!! flag!!!! here!!! wowowowowo~~~~~~")
        print(flag)
    else:
        print(m)
        print("yoshiking: ...?")


if __name__ == '__main__':
    main()

アプローチ：入力クエリをもとに平方剰余、平方非剰余となるトークンを生成

server.pyを読むと以下のことが分かります。

入力トークンが $\bmod p, \bmod q$ 上で平方剰余であれば0、平方非剰余であれば1といった復号処理を行っている
復号してkeywordと一致するトークンを入力すればflagを取得できる
入力トークンは重複してはならない
入力クエリは8文字以内
入力クエリの各ビットごとにトークンを生成している（ビットが0ならば $x^{2} \bmod n$ 、ビットが1ならば $zx^{2} \bmod n$ ）

したがって、トークン化された入力クエリをもとに平方剰余、平方非剰余となる数値を生成し、復号時にkeywordとなるトークン列を送ればいいことが分かります。

平方剰余となるトークンは入力クエリのビット0に対応するトークンを2乗、4乗、8乗…としていけば生成できます。また、平方非剰余となるトークンは入力クエリのビット1に対応するトークンを整数倍すれば雑に生成できます（たまに失敗しますが）。

以下はソルバになります。

from pwn import *
from Crypto.Util.number import *

r = remote('crypto.kosenctf.com', 13003)
m = 'xxxxxxxx'
recv = r.recvuntil('your query: ')
r.sendline(m.encode())
recv = r.recvline() 
c = eval(recv.decode().strip().split(':  ')[-1])

target = 'yoshiking, give me ur flag'
target_bin = bin(bytes_to_long(target.encode()))[2:]
base_0 = []
base_1 = []
attack = []
base_0_index = 0
base_1_index = 0
base_0_exp = 1
base_1_coeff = 1

for i,bit in enumerate(bin(bytes_to_long(m.encode()))[2:]):
    if bit == '1':
        base_1.append(c[i])
    else:
        base_0.append(c[i])

for x in target_bin:
    if x == '1':
        attack.append(base_1[base_1_index] * base_1_coeff)
        base_1_index += 1
        if base_1_index == len(base_1):
            base_1_index = 0
            base_1_coeff += 1
    else:
        attack.append(base_0[base_0_index] ** base_0_exp)
        base_0_index += 1
        if base_0_index == len(base_0):
            base_0_index = 0
            base_0_exp *= 2
recv = r.recvuntil('your token: ')
r.sendline(str(attack).encode())
result = r.recvline()
print(result.decode())
flag = r.recvline()
print(flag.decode())

yoshiking: hi!!!! flag!!!! here!!! wowowowowo~~~~~~

KosenCTF{yoshiking_is_clever_and_wild_god_of_crypt}

KosenCTF{yoshiking_is_clever_and_wild_god_of_crypt}

padding oracle [326pts, 17solves]

As you know, AES-CBC is vulnerable to the oracle attack by padding. Today I resolved the security issue.
nc padding-oracle.kosenctf.com 13004

server.py

from Crypto.Cipher import AES
from binascii import hexlify, unhexlify
from flag import flag
import os
import signal

def pad(m: bytes) -> bytes:
    l = 16 - len(m) % 16
    return bytes([l]) * l + m

def unpad(m: bytes) -> bytes:
    l = m[0]
    assert 1 <= l <= 16
    assert bytes([l]) * l == m[:l]
    return m[l:]

def main():
    key = os.urandom(16)
    iv = os.urandom(16)
    aes = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)
    cipher = aes.encrypt(pad(flag))
    print(hexlify(iv + cipher).decode())

    signal.alarm(300)
    while True:
        c = unhexlify(input())
        try:
            iv, c = c[:16], c[16:]
            m = AES.new(key=key, mode=AES.MODE_CBC, iv=iv).decrypt(c)
            u = unpad(m)
            print(True)
        except:
            print(False)


if __name__ == '__main__':
    main()

アプローチ：Padding Oracle Attackのソルバを $enc(IV)$ から改ざんするように修正し、独自Padding方式に対応する

まずPadding Oracle Attackに関しては、下記の記事が理解しやすいかと思います。

rintaro.hateblo.jp

この問題で通常のPadding Oracle Attackとの相違点として注目すべき処理は下記です。

def pad(m: bytes) -> bytes:
    l = 16 - len(m) % 16
    return bytes([l]) * l + m

PKCS #7パディングに見えてしまいますが、よく読むとパディングがサフィックスとしてではなく、プレフィックスとして付与されていることに気づくかと思います。
~~そのため、ptrlibを使うだけでは解けません~~

通常のPadding Oracle Attackでは、平文 $m$ を暗号化した暗号文 $c$ が $n$ 個に分割できる場合、 $c_{n-1}$ を改ざんした値である $c_{n-1}^{\prime}$ を求めることによって、 $m_n$ を特定します。
ですが、今回の問題の場合はパディングがプレフィックスとして付与されるので、 $enc(IV)=c_0$ を改ざんした値である $c_0^{\prime}$ を求めることによって、 $m_1$ を特定します。
~~後ろからやるか前からやるかの違いしかありません~~

以下はソルバになります。

from pwn import *
from binascii import hexlify, unhexlify

BLOCK_SIZE = 16
r = remote('padding-oracle.kosenctf.com', 13004)

def padding_is_valid(x, pad_num, dec, target_cipher):
    attempt_bytes = bytes([x]) + bytes(BLOCK_SIZE - pad_num)
    adjust_bytes = b''
    for c in dec:
        adjust_bytes += bytes([c ^ pad_num])
    send_code = hexlify(adjust_bytes + attempt_bytes) + target_cipher
    r.sendline(send_code)
    result = r.recvline()
    if b'True' in result:
        return True
    else:
        return False

flag = b''
enc = unhexlify(r.recvline().decode().strip())
cipher_blocks = [enc[i:i+BLOCK_SIZE] for i in range(0, len(enc), BLOCK_SIZE)]

for i in range(len(cipher_blocks) - 1):
    prev_cipher = cipher_blocks[i]
    target_cipher = hexlify(cipher_blocks[i + 1])
    x = 0
    pad_num = 1
    m = b''
    dec = b''

    while True:
        if padding_is_valid(x, pad_num, dec, target_cipher):
            print(f'{bytes([x])}: {bytes([pad_num]) * pad_num}')
            m += bytes([x ^ pad_num ^ prev_cipher[pad_num - 1]])
            dec += bytes([x ^ pad_num])
            pad_num += 1
            x = 0
            if pad_num <= BLOCK_SIZE:
                continue
            break
        x += 1
        if x > 0xFF:
            print('Byte Not Found')
            break
    flag += m
    print(flag)
    print('-'*50)

b'\xda': b'\x01'
b'$': b'\x02\x02'
b' ': b'\x03\x03\x03'
b'\xce': b'\x04\x04\x04\x04'
b'\x84': b'\x05\x05\x05\x05\x05'
b'\xc5': b'\x06\x06\x06\x06\x06\x06'
b'n': b'\x07\x07\x07\x07\x07\x07\x07'
b'\xa5': b'\x08\x08\x08\x08\x08\x08\x08\x08'
b'\xa4': b'\t\t\t\t\t\t\t\t\t'
b'2': b'\n\n\n\n\n\n\n\n\n\n'
b'g': b'\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b'
b't': b'\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c'
b'\xea': b'\r\r\r\r\r\r\r\r\r\r\r\r\r'
b'\x9e': b'\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e'
b'\x86': b'\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f'
b'\xe4': b'\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10'
b'\x03\x03\x03Turkey in de '
--------------------------------------------------
[snip]
--------------------------------------------------
b'D': b'\x01'
b'\x11': b'\x02\x02'
b'\xc3': b'\x03\x03\x03'
b'J': b'\x04\x04\x04\x04'
b'\xcf': b'\x05\x05\x05\x05\x05'
b'D': b'\x06\x06\x06\x06\x06\x06'
b'\xc1': b'\x07\x07\x07\x07\x07\x07\x07'
b'\xb4': b'\x08\x08\x08\x08\x08\x08\x08\x08'
b'\xff': b'\t\t\t\t\t\t\t\t\t'
b'u': b'\n\n\n\n\n\n\n\n\n\n'
b'\xa9': b'\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b'
b'v': b'\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c'
b'o': b'\r\r\r\r\r\r\r\r\r\r\r\r\r'
b'r': b'\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e'
b'\xfe': b'\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f'
b'a': b'\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10'
b'\x03\x03\x03Turkey in de straw, turkey in de hay KosenCTF{0r4c13_5urviv35_57i11_n0w} Turk'
--------------------------------------------------
[snip]

KosenCTF{0r4c13_5urviv35_57i11_n0w}

padrsa [426pts, 7solves]

Textbook-RSA is sometimes weak. I padded it to improve the security.
nc crypto.kosenctf.com 13001

server.py

import os
import signal
from binascii import unhexlify, hexlify
from Crypto.Util.number import *
from flag import flag

r = os.urandom(8)
nonce = 1

p = getPrime(256)
q = getPrime(256)
n = p * q
es = set()

def pad(x: bytes) -> bytes:
    global r, nonce
    y = long_to_bytes(r[0] | nonce) + x + r

    nonce += 1
    r = long_to_bytes(((bytes_to_long(r) << 1) ^ nonce) & (2**64 - 1))
    return y

def encrypt(m: bytes, e: int) -> bytes:
    m_ = bytes_to_long(pad(m))
    return long_to_bytes(pow(m_, e, n))

MENU = """
1. Encrypt the flag
2. Encrypt your message
3. EXIT
"""

signal.alarm(30)
print("n: {}".format(n))

while True:
    print(MENU)
    choice = input("> ")
    if choice not in ["1", "2"]:
        break

    e = int(input("e: "))
    if not(3 <= e <= 65537):
        print("[-] invalid e")
        break

    if e in es:
        print("[-] e already used")
        break

    if choice == "1":
        m = flag
    if choice == "2":
        m = unhexlify(input("m: "))

    c = encrypt(m, e)
    print("c: {}".format(hexlify(c).decode()))

    es.add(e)

アプローチ：paddingの不備をついて、Hastad's Broadcast Attack

furutsuki.hatenablog.com

非想定解法っぽいので、雑に書きます。

この問題で注目すべき処理は下記です。

def pad(x: bytes) -> bytes:
    global r, nonce
    y = long_to_bytes(r[0] | nonce) + x + r

    nonce += 1
    r = long_to_bytes(((bytes_to_long(r) << 1) ^ nonce) & (2**64 - 1))
    return y

rは64bitの乱数ですが、nonceの初期値が固定のため、64回程度padding(rを64回左シフト)することでrが固定されます。
したがって、同一の平文mを異なるnで暗号化する処理に持ち込めるため、Hastad's Broadcast Attackが可能になります。

以下はnとcを集めるスクリプトです。

from pwn import *

ns = []
cs = []
for _ in range(71):
    nonce = 1
    e = 3
    r = remote('crypto.kosenctf.com', 13001)
    n = int(r.recvline().decode().strip().split(' ')[-1])
    while e <= 71:
        print(f'{nonce=}')
        recv = r.recvuntil('> ')
        r.sendline(b'1')
        recv = r.recvuntil('e: ')
        r.sendline(str(e).encode())
        c = int(r.recvline().decode().strip().split(' ')[-1],16)
        nonce += 1
        e += 1
    ns.append(n)
    cs.append(c)