🙆

zer0pts CTF 2021 write up

2021/03/09に公開

CTF

tech

動画リンク

よかったらチャンネル登録してね！

成績

正の点数獲得者951チーム中62位
Crpytoが難しい問題が多く、楽しめました。

war(sa)mup

動画リンク

YouTubeのvideoIDが不正ですhttps://youtu.be/oVBp1npprqk?t=256

$m, e, n, c1, c2$ が与えられて、それぞれの関係式が以下のとおりになる。

\begin{aligned} c_1 &= m^e \mod n \\ c_2 &= \lfloor m/2 \rfloor ^e \mod n \end{aligned}

ここで $m$ を奇数、二つの暗号文を $m_1, m_2$ とすると、以下の式になる。

\begin{aligned} m_1 &= 2 m_2 + 1 \\ c_1 &= m_1^e \mod n \\ c_2 &= m_2 ^e \mod n \end{aligned}

このように2つの暗号文があり、 $m_1, m_2$ の関係が $m_1 = a m_2 + b\ \mathrm{where}\ b \neq 0$ の場合、 franklin-reiter related message attack という攻撃手法が有効。

具体的には、 $m_1 = 2 m_2 +1$ を代入して整理すると、

\begin{aligned} g_1(x) &= c_1 - (2 x + 1)^e &= 0 \mod n \\ g_2(x) &= c_2 - m_2^e &= 0 \mod n \end{aligned}

となり、 $x = m_2$ なので、

\begin{aligned} g_1(x) &= c_1 - (2 x + 1)^e &= (x-m_2)h_1(x) &= 0 \mod n \\ g_2(x) &= c_2 - m_2^e &= (x-m_2)h_2(x) &= 0 \mod n \end{aligned}

のように２つの式は $x-m_2$ を含む多項式になる。
この式のgcdを取ると、 $x-m_2$ が取れそうっぽい見た目をしているのですが、実際取ることができる。 sagemathを使うと便利。

あとは $x - m_2$ から $m_2$ を取り出し、平文を復元する。

def gcd(g1, g2):
    while g2:
        g1, g2 = g2, g1 % g2
    return g1.monic()

PRx.<x> = PolynomialRing(Zmod(n))
g1 = x^e - c2
g2 = (x*2 + 1)^e - c1

result = -gcd(g1, g2).coefficients()[0]
print(long_to_bytes(result*2 + 1))

3-AES

動画リンク

YouTubeのvideoIDが不正ですhttps://youtu.be/oVBp1npprqk?t=1649

以下の3つの鍵、3つの暗号化手法で順番に暗号化し、逆順番に復号を行う。

keys = [md5(os.urandom(3)).digest() for _ in range(3)]
AES.new(keys[0], mode=AES.MODE_ECB),
AES.new(keys[1], mode=AES.MODE_CBC, iv=iv1),
AES.new(keys[2], mode=AES.MODE_CFB, iv=iv2, segment_size=8*16),

任意の平分 $m$ を暗号化することができ、任意の $m, iv_1, iv_2$ で復号することができる。

暗号化時は $iv1, iv2$ がランダムに抽選されるので、 $iv1, iv2$ を任意に挿入することができる複合時のほうが色々便利。

3つの復号化手法を連結すると、以下のようになる。(詳細は動画を参照) Dが複合、Eが暗号、数字は3種類の鍵を表している。

m = D0(D1(E2(iv2) ^ c) ^ iv1)

$iv2, c$ を固定し、 $iv1$ を２つ変えて暗号化すると、以下のような式が出てくる。
2021/03/11 rkm0959さん(https://twitter.com/rkm0959) にtypoを見つけていただきました！ Thanks!

m_1 = D0(D1(E2(\mathrm{iv2}) \oplus c) \oplus \mathrm{iv1}) \\ m_2 = D0(D1(E2(iv2) \oplus c) \oplus \mathrm{iv1'}) \\ \therefore E0(m_1) \oplus E0(m_2) = \mathrm{iv1} \oplus \mathrm{iv1'}

ここで、鍵は 2^24 通り程度しかないので、 $E0$ の鍵を総当りすれば、いつか↑の式が成立する。

あとは同じ要領で残り２つの鍵を漏洩させればOK(詳細は動画参照)

from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.number import *
from binascii import hexlify, unhexlify
from hashlib import md5
import os
import signal
from pwn import *
flag = b"kurenaif{123456}"

keys = [md5(os.urandom(3)).digest() for _ in range(3)]

def get_ciphers(iv1, iv2):
    return [
        AES.new(keys[0], mode=AES.MODE_ECB),
        AES.new(keys[1], mode=AES.MODE_CBC, iv=iv1),
        AES.new(keys[2], mode=AES.MODE_CFB, iv=iv2, segment_size=8*16),
    ]

def encrypt(m: bytes) -> bytes:
    iv1, iv2 = get_random_bytes(16), get_random_bytes(16)
    assert len(m) % 16 == 0
    ciphers = get_ciphers(iv1, iv2)
    c = m
    for cipher in ciphers:
        c = cipher.encrypt(c)
    return c, iv1, iv2

io = remote('crypto.ctf.zer0pts.com',  10929)
# io = remote('localhost', 2000)

def decrypt(c: bytes, iv1: bytes, iv2: bytes) -> bytes:
    print(io.recvuntil('>'))
    io.sendline("2")
    ciphertext = b":".join([hexlify(x) for x in [iv1, iv2, c]]).decode()
    io.sendline(ciphertext)
    hoge = io.recvline().split(b':')[-1]
    return long_to_bytes(eval(b'0x' + hoge.strip()))

### key0 ###

c = long_to_bytes(0x11223344556677889900112233445566)
iv1, iv1_dash, iv2 = get_random_bytes(16), get_random_bytes(16), get_random_bytes(16)
m = decrypt(c, iv1, iv2)
m_dash = decrypt(c, iv1_dash, iv2)

key0 = 0
for i in range((1<<24)):
    if i % 10000 == 0:
        print(i / (1<<24))

    key = md5(long_to_bytes(i)).digest()
    key = AES.new(key, mode=AES.MODE_ECB)
    key.encrypt(m)

    if bytes_to_long(key.encrypt(m)) ^ bytes_to_long(key.encrypt(m_dash)) == bytes_to_long(iv1) ^ bytes_to_long(iv1_dash):
        key0 = md5(long_to_bytes(i)).digest()
        break

### key1 ###

c = long_to_bytes(0x11223344556677889900112233445566)
c_dash = long_to_bytes(0x11223344556677889900112233445577)
iv1, iv2 = get_random_bytes(16), get_random_bytes(16)
cipher = AES.new(key0, mode=AES.MODE_ECB)

m = decrypt(c, iv1, iv2)
m = cipher.encrypt(m)
m_dash = decrypt(c_dash, iv1, iv2)
m_dash = cipher.encrypt(m_dash)

key1 = 0
for i in range((1<<24)):
    if i % 10000 == 0:
        print(i / (1<<24))

    key = md5(long_to_bytes(i)).digest()
    key = AES.new(key, mode=AES.MODE_ECB)
    key.encrypt(m)

    left = key.encrypt(long_to_bytes(bytes_to_long(m) ^ bytes_to_long(iv1)))
    right = key.encrypt(long_to_bytes(bytes_to_long(m_dash) ^ bytes_to_long(iv1)))

    if bytes_to_long(left) ^ bytes_to_long(right) == bytes_to_long(c) ^ bytes_to_long(c_dash):
        key1 = md5(long_to_bytes(i)).digest()
        break

### key2 ###

c = long_to_bytes(0x11223344556677889900112233445566)
iv1, iv2, iv2_dash = get_random_bytes(16), get_random_bytes(16), get_random_bytes(16)
cipher0 = AES.new(key0, mode=AES.MODE_ECB)
cipher1 = AES.new(key1, mode=AES.MODE_CBC, iv=iv1)

m = decrypt(c, iv1, iv2)
m = cipher0.encrypt(m)
m = cipher1.encrypt(m)

key2 = 0
for i in range((1<<24)):
    if i % 10000 == 0:
        print(i / (1<<24))

    key = md5(long_to_bytes(i)).digest()
    key = AES.new(key, mode=AES.MODE_ECB)
    if bytes_to_long(key.encrypt(iv2)) == bytes_to_long(c) ^ bytes_to_long(m):
        key2 = md5(long_to_bytes(i)).digest()
        break

print("key0= ", key0)
print("key1= ", key1)
print("key2= ", key2)

def local_decrypt(c: bytes, iv1: bytes, iv2: bytes) -> bytes:
    assert len(c) % 16 == 0
    ciphers = get_ciphers(iv1, iv2)
    m = c
    for cipher in ciphers[::-1]:
        m = cipher.decrypt(m)
    return m

print(io.recvuntil('>'))
io.sendline("3")
hoge = io.recvline()
print(hoge)

OT or NOT OT

動画リンク

YouTubeのvideoIDが不正ですhttps://youtu.be/oVBp1npprqk?t=4005

入力: $a,b,c,d$
出力: $u$ (の1bit目をランダムに変更), $v$ (の1bit目をランダムに変更), $t$ (乱数), $p$ (乱数かつ素数)
未知数: $r$ , $s$ (乱数)

が与えられる。これらの変数の関係は以下の通り。

u = a^r c^s \mod p v = b^r c^s \mod p z = d^r t^s \mod p

うまく $a,b,c,d$ を与えて、ランダムに変更された $u, v$ の1bit目を特定するという問題。

ここで、

\begin{aligned} a &= -1 &\mod p \\ b &= 2^{-1} &\mod p \\ c &= t^{-2} &\mod p \\ d &= 2 &\mod p \end{aligned}

とすると、

\begin{aligned} u &= -1^r t^{-2s} \\ v &= 2^{-r} t^{-2s} \\ z &= 2^r t^s \\ \end{aligned}

となり、

u/(vz)^2 = -1^r t^{-2s} t^{2s} = -1^r

となるので、この出力結果が 1,p-1のどちらかが出てくる。
$u$ か $v$ が嘘をついていると、この結果にならないので、それで判定ができる。
あり得る4通りでこれを試せば良い。

import os
import signal
import random
from base64 import b64encode
from Crypto.Util.number import getStrongPrime, bytes_to_long
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
flag = b"kurenaifCTF{hogehoge}"

p = getStrongPrime(1024)

key = os.urandom(32)
iv = os.urandom(AES.block_size)
aes = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)
c = aes.encrypt(pad(flag, AES.block_size))

key = bytes_to_long(key)
print("Encrypted flag: {}".format(b64encode(iv + c).decode()))
print("p = {}".format(p))
print("key.bit_length() = {}".format(key.bit_length()))

def check(x,y,z,p):
    invts = z*y % p
    ts = pow(invts, -1, p)

    return (pow(ts,2,p) * x % p) == 1 or (pow(ts,2,p) * x * -1 % p) == 1

def solve(x,y,z,p):
    count = []
    for i in range(2):
        for j in range(2):
            if check(x ^ i,y ^ j,z,p):
                count.append((i,j))
    assert(len(count) == 1)
    return count[0]

# signal.alarm(600)

memo = 0
ans = 0
key_expect = key
ans2 = []
while key > 0:
    r = random.randint(2, p-1)
    s = random.randint(2, p-1)
    t = random.randint(2, p-1)
    print("t = {}".format(t))

    a = -1 % p
    b = pow(2, -1, p) % p
    c = pow(t,-2,p) % p
    d = 2

    assert all([a > 1 , b > 1 , c > 1 , d > 1])
    assert len(set([a,b,c,d])) == 4

    u = pow(a, r, p) * pow(c, s, p) % p
    v = pow(b, r, p) * pow(c, s, p) % p
    x = u ^ (key & 1)
    y = v ^ ((key >> 1) & 1)
    z = pow(d, r, p) * pow(t, s, p) % p

    print("x = {}".format(x))
    print("y = {}".format(y))
    print("z = {}".format(z))

    res = solve(x,y,z,p)
    assert(res == ((key&1), (key>>1)&1))
    ans2.append(res[0])
    ans2.append(res[1])
    ans += (res[0] << memo)
    memo += 1
    ans += (res[1] << memo)
    memo += 1

    key = key >> 2

janken vs yoshiking

動画リンク

YouTubeのvideoIDが不正ですhttps://youtu.be/oVBp1npprqk?t=5293

$p$ が弱いElgamal暗号が与えられるので、

出力: $g$ , $p$ (strongPrime), $c_1$ , $c_2$
未知数: $r, x, m$

\begin{aligned} c1 &= g^r \\ c2 &= m g^{rx} \end{aligned}

から $m$ を求めてくださいという問題。一見できそうに見えるけどこれはできない。

ここで、フェルマーの小定理より、

x^{(p-1)} = 1 \mod p

なので、この $(p-1)$ に何かをかけた以下の式も1になる。

x^{(p-1)y} = 1

ここでもし、 $p-1$ が2で割り切れ、 $rx$ が2の倍数の場合 $(p-1)/2$ 乗することで、

\begin{aligned} c2^{(p-1)/2} &= m g^{2rx (p-1)/2} = m g^{rx(p-1)} = m^{(p-1)/2} \\ \end{aligned}

となる。 $c2$ は既知なので、 $m$ を1~3の3通りで試せば良い。

import random
import signal
# from flag import flag
from Crypto.Util.number import getStrongPrime, inverse
import statistics
from ptrlib import *


HANDNAMES = {
    1: "Rock",
    2: "Scissors",
    3: "Paper"
}

# https://tex2e.github.io/blog/crypto/DLP
# https://ctftime.org/writeup/23567

# Baby-step Giant-step法
def babystep_giantstep(g, y, p, q=None):
    if q is None:
        q = p - 1
    m = int(q**0.5 + 0.5)
    # Baby step
    table = {}
    gr = 1  # g^r
    for r in range(m):
        table[gr] = r
        gr = (gr * g) % p
    # Giant step
    try:
        gm = pow(g, -m, p)  # gm = g^{-m}
    except:
        return None
    ygqm = y                # ygqm = y * g^{-qm}
    for q in range(m):
        if ygqm in table:   # 左辺と右辺が一致するとき
            return q * m + table[ygqm]
        ygqm = (ygqm * gm) % p
    return None

# Pohlig–Hellman法
def pohlig_hellman_DLP(g, y, p):
    crt_moduli = []
    crt_remain = []
    for q, memo in (p-1).factor(limit=2^30):
        if q > 2^30:
            break
        for q, memo in factor(q^memo):
            q = q ^ memo
            x = babystep_giantstep(pow(g,(p-1)//q,p), pow(y,(p-1)//q,p), p, q)
            if (x is None) or (x <= 1):
                continue
            crt_moduli.append(q)
            crt_remain.append(x)
    x = crt(crt_remain, crt_moduli)
    return x

# g = 123123123123
# y = 1094511311619717224471473901707
# p = 2 * 32803 * 196159 * 1981991353 * 47814426923 + 1  # 素数p
# x = pohlig_hellman_DLP(g, y, p)
# print(x)
# print(pow(g, x, p) == y)

def commit(m, key):
    (g, p), (x, _) = key
    r = random.randint(2, p-1)
    c1 = pow(g, r, p)
    c2 = m * pow(g, r*x, p) % p
    return (c1, c2)


def decrypt(c, key):
    c1, c2 = c
    _, (x, p)= key

    m = c2 * inverse(pow(c1, x, p), p) % p
    return m


def keygen(size):
    p = getStrongPrime(size)
    g = random.randint(2, p-1)
    x = random.randint(2, p-1)

    return (g, p), (x, p)


def judge(you,me):
    result = (you - me + 3) % 3
    if result == 0:
        return 1
    elif result == 1:
        return 2
    elif result == 2:
        return 0


def solve(factor_list, c, p):
    c1 = c[0]
    c2 = c[1]
    res = {}
    res[1] = 0
    res[2] = 0
    res[3] = 0

    for q in factor_list:
        power = (p-1)//q
        if(pow(c1, power, p) == 1):
            for j in range(1, 4):
                # print(pow(c2, power, p))
                # print(pow(j, power, p))
                # print("~~~")
                if pow(c2, power, p) == pow(j, power, p):
                    res[j] += 1

    res = sorted(res.items(), key=lambda x:-x[1])

    return res

def janken(res):
    # 確定
    if res[0][1] != res[1][1]:
        yoshiking_hand = res[0][0]
        for x in range(1,4):
            if judge(yoshiking_hand, x) == 2:
                return x
    # わからん
    if res[0][1] == res[1][1] == res[2][1]:
        print("random sorry")
        return 1
    
    # 二通りありえる場合は負けない手を出す
    x = res[0][0]
    y = res[1][0]
    for ans in range(1,4):
        if judge(x, ans) != 0 and judge(y, ans) != 0:
            return ans

# local poc
# key = keygen(1024)
# (g, p), _ = key
# 
# factor_list = []
# for qq, memo in (p-1).factor(limit=2**30):
#     q = qq ^ memo
#     print(q)
#     factor_list.append(q)
# factor_list = factor_list[:-1]
# 
# for _ in range(100):
#     yoshiking_hand = random.randint(1, 3)
#     c = commit(yoshiking_hand, key)
#     res = solve(factor_list, c, p)
#     janken(res)

io = remote('crypto.ctf.zer0pts.com',  10463)
# io = remote('localhost', 2000)
print(io.recvline()) # hello let's play...
temp = io.recvline()
print(temp)
g = int(temp.split(b':')[2].split(b',')[0])
print(g)
p = int(temp.split(b':')[-1])

factor_list = []
for qq, memo in (p-1).factor(limit=2**30):
    q = qq ^ memo
    print(q)
    factor_list.append(q)
factor_list = factor_list[:-1]
print(io.recvline()) # ROUND...

win = 0
while True:
    temp = io.recvline().split(b'=')[-1] # m)commitment is...
    print(temp)
    c = eval(temp) 

    res = solve(factor_list, c, p)
    print(res)
    hand = str(janken(res))
    print("hand: ", hand)
    io.sendline(hand)
    io.recvline()
    io.recvline()
    io.recvline() 
    temp = io.recvline() 
    print(temp)
    if b'win' in temp:
        win += 1
    print("wincount: ", win)
    if win == 100:
        break
    print(io.recvuntil(b'[yoshiking]: my commitment'))

print(io.recvline())
print(io.recvline())
print(io.recvline())
print(io.recvline())
print(io.recvline())
print(io.recvline())
print(io.recvline())
print(io.recvline())
print(io.recvline())

動画リンク

成績

war(sa)mup

動画リンク

3-AES

動画リンク

OT or NOT OT

動画リンク

janken vs yoshiking

動画リンク

Discussion