先週土日に開催されていたzer0pts CTF 2021に出たので自分が解いた問題と、解けなかったが、終了後に解けた問題についてそのWriteupを書きます。

ちなみに問題はここで全部公開されている上に公式Writeupもあるので是非覗いてみてください。

Table of Contents §

war(sa)mup §

問題のスクリプトは次の通り

from Crypto.Util.number import getStrongPrime, GCD
from random import randint
from flag import flag
import os

def pad(m: int, n: int):
  # PKCS#1 v1.5 maybe
  ms = m.to_bytes((m.bit_length() + 7) // 8, "big")
  ns = n.to_bytes((n.bit_length() + 7) // 8, "big")
  assert len(ms) <= len(ns) - 11

  ps = b""
  while len(ps) < len(ns) - len(ms) - 3:
    p = os.urandom(1)
    if p != b"\x00":
      ps += p
  return int.from_bytes(b"\x00\x02" + ps + b"\x00" + ms, "big")


while True:
  p = getStrongPrime(512)
  q = getStrongPrime(512)
  n = p * q
  phi = (p-1)*(q-1)
  e = 1337
  if GCD(phi, e) == 1:
    break

m = pad(int.from_bytes(flag, "big"), n)
c1 = pow(m, e, n)
c2 = pow(m // 2, e, n)

print("n =", n)
print("e =", e)
print("c1=", c1)
print("c2=", c2)

コメントからPKCS#1 v1.5らしきパディングをフラグに加えたもの(m)を暗号化している。問題の鍵となるのはmに加えてm // 2も暗号化した結果もくれることである。

ここでフラグの末尾が}で終わる事を考えるとmは奇数になる(}のASCIIコードは0x7d = 125である)。ということはm // 2(m-1) // 2である。

m // 2とおくと、の関係がある。線形の関係にある2つの平文を同一公開鍵で暗号化している場合はFranklin-Reiter Related Message Attackが有効なのでこれを使う。

使用コードは次の通り

from Crypto.Util.number import long_to_bytes


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a.monic()


def franklinreiter(c_1, c_2, e_1, e_2, N, a, b):
    P.<X> = PolynomialRing(Zmod(N))
    g_1 = X^e_1 - c_1
    g_2 = (a*X + b)^e_2 - c_2
    result = -gcd(g_1, g_2).coefficients()[0]

    return result


n = 113135121314210337963205879392132245927891839184264376753001919135175107917692925687745642532400388405294058068119159052072165971868084999879938794441059047830758789602416617241611903275905693635535414333219575299357763227902178212895661490423647330568988131820052060534245914478223222846644042189866538583089
e = 1337
c1= 89077537464844217317838714274752275745737299140754457809311043026310485657525465380612019060271624958745477080123105341040804682893638929826256518881725504468857309066477953222053834586118046524148078925441309323863670353080908506037906892365564379678072687516738199061826782744188465569562164042809701387515
c2= 18316499600532548540200088385321489533551929653850367414045951501351666430044325649693237350325761799191454032916563398349042002392547617043109953849020374952672554986583214658990393359680155263435896743098100256476711085394564818470798155739552647869415576747325109152123993105242982918456613831667423815762

m2 = franklinreiter(c2, c1, 1337, 1337, n, 2, 1)
m = m2 * 2 + 1
print(long_to_bytes(m))

フラグはzer0pts{y0u_g07_47_13457_0v3r_1_p0in7}であった。

なお、Franklin-Reiter Related Message Attackについては半年ぐらい前に書いた自分の記事でそこそこ解説しているので良かったら読んでください。

OT or NOT OT §

問題のスクリプトは次の通り

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
from flag import flag

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()))

signal.alarm(600)
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 = int(input("a = ")) % p
    b = int(input("b = ")) % p
    c = int(input("c = ")) % p
    d = int(input("d = ")) % p
    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

    key = key >> 2

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

AESの暗号文とIVと鍵の長さ、そして素数pが与えられ、以下のプロセスを鍵が0以上の間続けている。

  1. 3つの正整数が用意され、そのうちのみが開示される。
  2. 入力としての4つが要求される。どれもを法とした値にされる上に、1より大きく重複してはならないという制約がある。
  3. 次の5つの数が計算されが与えられる、ここではそれぞれ鍵の末尾bitとその1つ上のbitを表す
  4. 鍵を右に2bitシフトする

結論から言うとを入力した。この場合のはそれぞれ次のようになる。

$$ \begin{aligned} u &\equiv \frac{a^r}{t^s} \bmod p \cr v & \equiv \frac{(-a)^r}{t^s} \bmod p \cr z & \equiv \frac{t^s}{a^r} \bmod p \end{aligned} $$

これからわかるようにが成立する。

まず前者の関係からである。よってを2通り試してこの式の左辺に代入し、成り立てばが決定出来る。

これでが決定された事になるので、この値を用いて先程同様にが成り立つようなを選択する。

これで鍵の下位2bitが決定されたので鍵全体を復元するようなスクリプトを書けば良い。

使用コードは次の通り

from Crypto.Util.number import long_to_bytes
from pwn import remote
from base64 import b64decode
from Crypto.Cipher import AES
from math import ceil


if __name__ == "__main__":
    sc = remote("crypto.ctf.zer0pts.com", 10130)
    sc.recvuntil(": ")
    encrypted_flag = b64decode(sc.recvline().strip())
    iv, encrypted_flag = encrypted_flag[:AES.block_size], encrypted_flag[AES.block_size:]
    print(iv, encrypted_flag)
    sc.recvuntil("p = ")
    p = int(sc.recvline())
    print("p =", p)
    sc.recvuntil("() = ")
    key_length = int(sc.recvline())
    iteration = ceil(key_length / 2)
    key = ""
    for i in range(iteration):
        print(i)
        sc.recvuntil("t = ")
        t = int(sc.recvline())
        a = 2
        b = -2
        c = pow(t, -1, p)
        d = pow(2, -1, p)
        sc.recvuntil("a = ")
        sc.sendline(str(a))
        sc.recvuntil("b = ")
        sc.sendline(str(b))
        sc.recvuntil("c = ")
        sc.sendline(str(c))
        sc.recvuntil("d = ")
        sc.sendline(str(d))

        sc.recvuntil("x = ")
        x = int(sc.recvline())
        sc.recvuntil("y = ")
        y = int(sc.recvline())
        sc.recvuntil("z = ")
        z = int(sc.recvline())

        for key_u in range(2):
            _u = x ^ key_u
            lhs = _u * z % p
            if lhs == 1:
                break

        assert lhs == 1

        for key_v in range(2):
            _v = y ^ key_v
            lhs = _u * pow(_v, -1, p) % p
            if lhs == 1 or lhs == p - 1:
                break

        assert lhs == 1 or lhs == p-1

        key = (str(key_v) + str(key_u)) + key

    key = long_to_bytes(int(key,2))
    print(len(key))
    cipher = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)
    flag = cipher.decrypt(encrypted_flag)
    print(flag)

フラグはzer0pts{H41131uj4h_H41131uj4h}になった。

janken vs yoshiking §

問題のスクリプトは次の通り

import random
import signal
from flag import flag
from Crypto.Util.number import getStrongPrime, inverse

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

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)


signal.alarm(3600)
key = keygen(1024)
(g, p), _ = key
print("[yoshiking]: Hello! Let's play Janken(RPS)")
print("[yoshiking]: Here is g: {}, and p: {}".format(g, p))

round = 0
wins = 0
while True:
    round += 1
    print("[system]: ROUND {}".format(round))

    yoshiking_hand = random.randint(1, 3)
    c = commit(yoshiking_hand, key)
    print("[yoshiking]: my commitment is={}".format(c))

    hand = input("[system]: your hand(1-3): ")
    print("")
    try:
        hand = int(hand)
        if not (1 <= hand <= 3):
            raise ValueError()
    except ValueError:
        print("[yoshiking]: Ohhhhhhhhhhhhhhhh no! :(")
        exit()

    yoshiking_hand = decrypt(c, key)
    print("[yoshiking]: My hand is ... {}".format(HANDNAMES[yoshiking_hand]))
    print("[yoshiking]: Your hand is ... {}".format(HANDNAMES[hand]))
    result = (yoshiking_hand - hand + 3) % 3
    if result == 0:
        print("[yoshiking]: Draw, draw, draw!!!")
    elif result == 1:
        print("[yoshiking]: Yo! You win!!! Ho!")
        wins += 1
        print("[system]: wins: {}".format(wins))

        if wins >= 100:
            break
    elif result == 2:
        print("[yoshiking]: Ahahahaha! I'm the winnnnnnner!!!!")
        print("[yoshiking]: You, good loser!")
        print("[system]: you can check that yoshiking doesn't cheat")
        print("[system]: here's the private key: {}".format(key[1][0]))
        exit()

print("[yoshiking]: Wow! You are the king of roshambo!")
print("[yoshiking]: suge- flag ageru")
print(flag)

じゃんけんのスクリプトが動いていて、自分の手を出す前に相手の手をElGamal暗号を用いて暗号化したものが与えられる。これで100回勝てばフラグが開示される。

当たり前だが、じゃんけんの手は3つしか存在しないため今回は平文の空間が非常に狭い事になる。平文の空間が狭くてElGamal暗号と言えばTokyoWesterns CTF 6th 2020 - The Melancholy of Aliceを思い出す。ここで使った手法が今回も有効そうである。

getStrongPrime()は必ずしも安全素数を生成するわけではなく、と素因数分解した際に、素因数の中で非常に大きなものがある、程度の生成をする。ということはある程度小さい素数は素因数として抱えている事になる。今回は10000までの数で雑に素因数分解を試してとなったとする(は大きな数)。

The Melancoly of Aliceでも使った方法を用いるには秘密鍵を指数とした値が必要である。今回はElGamal暗号の公開鍵が与えられていないが、の関係があり、は3通りしか無いのでこれを全部試す。

これでとなるを求めることが出来る。これを用いるととなるので(詳細は前述のWriteupを参照してください)、事前にこの値をキー値を出す手とする辞書を作成しておけば、照合する事で出す手の特定が出来る。

使用コードは以下の通り(但し、結構な確率で失敗するので成功するまで連発した)

from pwn import remote
from xcrypto.dlp import pohlig_hellman
from xcrypto.num_util import prod


def small_factorize(n):
    ret = []
    for i in range(2, 10000):
        factor = [i, 0]
        while n % i == 0:
            print(i)
            n //= i
            factor[1] += 1

        if factor[1] > 0:
            ret.append(factor)

    return ret


win_hand = {
    1: 3,
    2: 1,
    3: 2
}


if __name__ == "__main__":
    sc = remote("crypto.ctf.zer0pts.com", 10463)
    sc.recvuntil("g: ")
    g = int(sc.recvuntil(",")[:-1])
    sc.recvuntil("p: ")
    p = int(sc.recvuntil("\n")[:-1])
    order = p - 1
    factors = small_factorize(order)
    C = order
    for factor, exponent in factors:
        C //= pow(factor, exponent)
    print(factors, C)
    if len(factors) == 1:
        print("[+] p is fxxkin super hyper safe...")
        exit()

    hands_to_power = {}
    for hand in range(1, 4):
        hands_to_power[pow(hand, C, p)] = hand

    while True:
        sc.recvuntil("is=(")
        c1 = int(sc.recvuntil(",")[:-1])
        c2 = int(sc.recvuntil(")")[:-1])
        hand = None
        for y_hand in range(1, 4):
            lhs = c2 * pow(y_hand, -1, p) % p
            try:
                _x = pohlig_hellman(c1, lhs, p, factors)
                res = pow(c2 * pow(c1, -_x, p) % p, C, p)
                if res in hands_to_power:
                    hand = hands_to_power[res]
                    break
            except:
                pass

        if hand is not None:
            print(hand)
            win = win_hand[hand]
            sc.recvuntil("(1-3): ")
            sc.sendline(str(win))
            sc.recvuntil("[system]: ")
            res = sc.recvline()
            print(res)
            if b"100" in res:
                sc.interactive()
                break
        else:
            exit()

フラグはzer0pts{jank3n-jank3n-0ne-m0r3-batt13}であった。

easy pseudo random(解き直し) §

当日解けませんでしたが、同じ考え方をしているWriteupがあり、そちらでは解けていたのでもう一度解いてみたら、普通に解けたのでWriteupを書きます。古いコードは別の解法での復習の際に上書きしたので何故解けなかったかはわかりませんが、多分Typoか致命的な凡ミスをしていたんだと思います。

問題のスクリプトは次の通り

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

nbits = 256
p = random_prime(1 << nbits)
Fp = Zmod(p)
P.<v> = PolynomialRing(Fp)

b = randrange(p)
d = 2
F = v^2 + b

v0 = randrange(p)
v1 = F(v0)

k = ceil(nbits * (d / (d + 1)))
w0 = (v0 >> (nbits - k))
w1 = (v1 >> (nbits - k))

# encrypt
m = bytes_to_long(flag)
v = v1
for i in range(5):
    v = F(v)
    m ^^= int(v)

print(f"p = {p}")
print(f"b = {b}")
print(f"m = {m}")
print(f"w0 = {w0}")
print(f"w1 = {w1}")

2乗を利用した乱数生成機を利用してフラグと5回排他的論理和を取っている。乱数の生成にはを利用しており、この内開示されるのはの上位171bitのみである。XORに使用する乱数はからである。

ビットシフトによって最初2つの乱数が削られているのでこれを復元する事を考える。の未知部分をとおくと次のような関係がある。

$$ \begin{aligned} v_0 &= w_0 \times 2^{85} + \alpha \cr v_1 &= w_1 \times 2^{85} + \beta \end{aligned} $$

これと乱数生成機の式からが成り立つので、適当に移項して整数を用いると次のようになる。

$$ kp - 2\alpha w_0\times 2^{85} + w_1\times 2^{85} - w_0^2 \times 2^{170} - b = \alpha^2 - \beta $$

左辺がおよそ512bitの項からなる式なのに対して、右辺が170bitぐらいなのでSVPに落とし込めばいい感じになりそうである。そこで次のような格子を用意する。

$$ \left( \begin{matrix} p & -2w_0\times 2^{85} & w_1 - w_0^2 \times 2^{170} - b \cr 0 & 2^{n_2} & 0 \cr 0 & 0 & 2^{n_1} \end{matrix} \right) $$

これに右からベクトルを掛ける事でベクトルが現れる。LLLで現れる基底の中にこれが含まれるそうなスケーリングを設定する。今回はを利用した。これでのサイズはだいたい170bitぐらいになり、また、この格子にLLLを施した時に現れる基底のサイズはだいたい以下になる事から特に問題無さそうである。

使用コードは次の通り

from Crypto.Util.number import long_to_bytes


nbits = 256
d = 2
k = ceil(nbits * (d / (d + 1)))
print(k)
print(nbits - k)

p = 86160765871200393116432211865381287556448879131923154695356172713106176601077
b = 71198163834256441900788553646474983932569411761091772746766420811695841423780
m = 88219145192729480056743197897921789558305761774733086829638493717397473234815
w0 = 401052873479535541023317092941219339820731562526505
w1 = 994046339364774179650447057905749575131331863844814

w0 <<= (nbits - k)
w1 <<= (nbits - k)

Fp = Zmod(p)
P.<v> = PolynomialRing(Fp)
F = v^2 + b

n1 = 170
print("[+] vector size:", n1)
n2 = n1 - (nbits - k)

l_list = [
    [p, 0, 0],
    [-2 * w0, 2^n2, 0],
    [(-w0^2 + w1 - b), 0, 2^n1]
]

llled = Matrix(ZZ, l_list).LLL()
for basis in llled:
    if basis[1] < 0:
        basis = -basis

    x0 = basis[1] // (2^n2)
    x1 = -(basis[0] - x0^2)
    v0 = w0 + x0
    v1 = w1 + x1

    if F(v0) == v1:
        print("[+] Found!!")
        v = v1
        for i in range(5):
            v = F(v)
            m ^^= int(v)

        print(long_to_bytes(m))

フラグはzer0pts{is_blum_blum_shub_safe?}であった。

ちなみに想定解や多くの人が解いている解法はdefund氏の多変数Coppersmith's Attackのスクリプトを利用しており、以前から存在は知っていたものの出てこなかったのが反省点です(これを使っても解き直しましたが割愛します)。

感想 §

面白かったです。チームメイトのWeb勢とPwn勢がSolvesの少ない問題を通している中、easy~mediumレベルのCryptoしか解けなかったのが残念でしたが、自分が触って復習した範囲内ではno Guessingで楽しく、考えさせられる問題が多かったです。

このような楽しいCTFを運営してくださったzer0ptsの皆様、本当にありがとうございました。来年も出ます。