HITCON CTF 2022 writeup

もう日が経ってしまったけど、HITCON CTF 2022のcrypto問題のwriteupです。難しい問題は解けなかったけど簡単な問題も楽しかったです。あらゆるところで言ってるけど、mapleとlyxがめちゃめちゃ信用できる。

Baby SSS
Secret
Superprime

Baby SSS

from random import SystemRandom
from Crypto.Cipher import AES
from hashlib import sha256
from secret import flag

rand = SystemRandom()


def polyeval(poly, x):
    return sum([a * x**i for i, a in enumerate(poly)])


DEGREE = 128
SHARES_FOR_YOU = 8  # I am really stingy :)

poly = [rand.getrandbits(64) for _ in range(DEGREE + 1)]
shares = []
for _ in range(SHARES_FOR_YOU):
    x = rand.getrandbits(16)
    y = polyeval(poly, x)
    shares.append((x, y))
print(shares)

secret = polyeval(poly, 0x48763)
key = sha256(str(secret).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CTR)
print(cipher.encrypt(flag))
print(cipher.nonce)

とりあえずひと目見てわかることを整理します。

一見Shamir's Secret Sharing
多項式を復元して $x = 0x48763$ を代入した値が得られればOK
128次の多項式なのに対して、8個しかシェアが与えられていないので、通常は解けなさそう
$\mod p$ とっていないのが怪しい

とりあえず一式から多項式全部を復元できないかを考えますが、多項式の係数は64bitであるのに対して、各シェアの $x$ は16bitなので、たとえばもらっている $y_1$ に対して $y_1 \mod x_1$ とかをとっても、0次の係数に関しては1/4しか復元できなさそうです。

しかし今回は8個のシェアが与えられているので、それぞれのシェアで $y_i \mod x_i$ を取ると、係数の定数項を中国剰余で復元できそうです。定数項（仮に $k_{i, 0}$ とします）がわかれば、 $y_i = k_0 + \sum_{j=1}^{N} k_0x_i^j$ なので $(y_i - k_0) / x_i \equiv k_1 \mod x_i$ となり、次々に係数が求まります。

実装するとこう

import ast
from hashlib import sha256
from Crypto.Cipher import AES

with open("output.txt") as f:
    shares = ast.literal_eval(f.readline())
    ciphertext = ast.literal_eval(f.readline())
    nonce = ast.literal_eval(f.readline())


def polyeval(poly, x):
    return sum([a * x**i for i, a in enumerate(poly)])


DEGREE = 128
SHARES_FOR_YOU = 8  # I am really stingy :)


coeffs = []
for d in range(DEGREE + 1):
    pairs = []
    values = []
    mods = []
    for i in range(len(shares)):
        x, y = shares[i]
        s = y - polyeval(coeffs, x)
        values.append(s // x**d)
        mods.append(x)

    c = CRT(values, mods)
    coeffs.append(c)


secret = polyeval(coeffs, int(0x48763))
key = sha256(str(secret).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CTR, nonce=nonce)
print(cipher.decrypt(ciphertext))

ptrlibのCRTメソッドは各 $x_i$ が厳密に互いに素であることを要求してきたので今回はSagemathを使いました。そのうち治したい。

Secret

問題はこう

import random, os
from Crypto.Util.number import getPrime, bytes_to_long

p = getPrime(1024)
q = getPrime(1024)
n = p * q

flag = open('flag','rb').read()
pad_length = 256 - len(flag)
m = bytes_to_long(os.urandom(pad_length) + flag)
assert(m < n)
es = [random.randint(1, 2**512) for _ in range(64)]
cs = [pow(m, p + e, n) for e in es]
print(es)
print(cs)

唯一の $n$ のもとで、64個の ${ e_i }$ を用いて $c_i = m^{e_i + p} \mod n$ という暗号化をしているRSAです。一見Common Moudulus Attack典型のような形をしていますが、 $n$ が不明なので、まず $n$ を求める必要がありそうです。

これについては最近N1CTF 2022で出題されたBrand new checkinという問題で似たような要求があったことを思い出し、出題者であるmapleさんのwriteupを見に行ったところ、さらに過去にmapleさんが出題した問題の解説がありました。

github.com

これによれば、以下のような理屈で $c$ と $e$ の複数の組から $n$ が求まります。

複数の数の組 ${a_i}$ を仮定して、 $a_0e_0 + a_1e_1 + \dots = 0 \mod \phi(n)$ となるとき、 $\prod m^{a_ie_i} \equiv m^{1} \equiv 1 \mod n$ なので、 $\prod c_i^{a_i} -1 = kn$ となり、このような ${a_i}$ と同様の ${b_i}$ を用意して、 $\gcd(\prod c_i^{a_i} - 1, \prod c_i^{b_i} - 1) = n$ となることが期待できます*1。

さて、 ${e_i}$ からそのような ${a_i}$ を求めるのはLLLの得意とするところで、

$\begin{pmatrix} e_0 & 1 \\ e_1 & & 1 \\ \vdots & & & \ddots \end{pmatrix}$

という行列のLLLでそのような係数が複数求まります*2。

今回は少し発展して $\sum a_i (p + e_i) \equiv 1 \mod \phi(n)$ の場合について考える必要があるので一筋縄ではいかない、というかこれをLLLで解くのは無理じゃないか……？　と思っていましたが、なんか実験していたら適当なスケーリングでなんとかなりました……。なんで……？ LLLのこと何もわかりません*3。

下のプログラムで $n$ が求まります。あとはCommon Modulus Attackをやるだけなので省略。ptrlibでできます。

import ast

f = open("output.txt")
es = ast.literal_eval(f.readline())
cs = ast.literal_eval(f.readline())


K = 2**1024
M = matrix(QQ, len(es), len(es)+1)
M.set_block(0, 0, matrix(QQ, len(es), 1, [e + K for e in es]) * K)
M.set_block(0, 1, matrix.identity(len(es)))

L = M.LLL()
S = product(int(c)**r for c, r in zip(cs, L[0][1:]))
T = product(int(c)**r for c, r in zip(cs, L[1][1:]))
t2 = cputime()

r = gcd(S.numerator() - S.denominator(), T.numerator() - T.denominator()) 
print(r)

Superprime

from Crypto.Util.number import getPrime, isPrime, bytes_to_long


def getSuperPrime(nbits):
    while True:
        p = getPrime(nbits)
        pp = bytes_to_long(str(p).encode())
        if isPrime(pp):
            return p, pp


p1, q1 = getSuperPrime(512)
p2, q2 = getSuperPrime(512)
p3, q3 = getSuperPrime(512)
p4, q4 = getSuperPrime(512)
p5, q5 = getSuperPrime(512)

n1 = p1 * q1
n2 = p2 * p3
n3 = q2 * q3
n4 = p4 * q5
n5 = p5 * q4

e = 65537
c = bytes_to_long(open("flag.txt", "rb").read().strip())
for n in sorted([n1, n2, n3, n4, n5]):
    c = pow(c, e, n)

print(f"{n1 = }")
print(f"{n2 = }")
print(f"{n3 = }")
print(f"{n4 = }")
print(f"{n5 = }")
print(f"{e = }")
print(f"{c = }")

5重のRSAですが素数の生成が特殊で、素数 $p_i$ と対になる $q_i$ は「 $p_i$ の文字列をバイト列だと思って解釈し直したときの数値」です。つまり、 $p_i$ が $123\dots$ なら $q_i = 0x313233\dots$ です。これらの $p_i, q_i$ が様々に組み合わされて $n_1 \dots n_5$ ができています。

結論から言えば、これらの合成数はその成り立ちが特異なので全てDFSやBFSで枝刈りをしながら素数の候補を狭めていく方法で素因数分解できますが、今回はケースによって少しずつ違う解き方をしたのでそれらを紹介します。勘が良ければ一気呵成に全部を素因数分解する方法も思いつけるのかも。

まず第一に $n_3$ は、以前SECCON 2020 Qualsで出題されたThis is RSAという問題と同じネタなので、この方法で解けます。素因数のどちらも $0x3a3b3c\dots$ という形になっているので4bitを全探索しながら、上位の $0x30$ と合わせつつ、 $p, q$ の下位bitの探索結果の積と素因数分解の対象の $n$ の下位bitとが一致するかを確認します。

こういう感じ

def dfs(N, p, q, depth):
    for x in range(10):
        for y in range(10):
            if depth == 0 and y < x:
                continue
            ps = str(x).encode().hex() + p
            qs = str(y).encode().hex() + q
            pp = int(ps, 16)
            qq = int(qs, 16)

            if (pp*qq) % (2**((depth+1) * 8)) == N % (2**((depth + 1) * 8)):
                if N % pp == 0:
                    return [pp, N // pp]
                r = dfs(N, ps, qs, depth + 1)
                if r is not None:
                    return r

q2, q3 = dfs(n3, "", "", 0)
assert n3 == q2 * q3

続いて $n_1$ は $p$ と $q$ の間に関連性があるので、 $p$ のある桁を決めると自動的に対応する $q$ の桁が決まります。これを使って、今度は上位から探索する方法をとります。だいたい $p$ と同じ大きさの $p'$ を用意すれば $n / p' \approx q$ で、上位の桁は一致することが期待できるので、 $p$ の上位を決めながら $n / p$ の結果の上位の桁が $q$ と一致しているかを確認しました。

こう

def dfs2(N, s, l):
    if l == 0 and N % int(s, 16) == 0:
        return int(s, 16), N // int(s, 16)

    for x in range(10):
        prefix = s + str(x).encode().hex()
        d = bytes.fromhex(prefix).decode()
        q_ = int(prefix + "0" * (l-2), 16)
        p_ = N // q_

        if str(p_).startswith(d):
            r = dfs2(N, prefix, l-2)
            if r:
                return r

L = ((n1.bit_length() - 512) + 3) // 4
p1, q1 = dfs2(n1, "", L)
assert n1 == p1 * q1

そして最後に $n_4, n_5$ ですが、今度は $n_4$ の素因数である $p_4$ を決めると $n_5$ の素因数である $q_4$ が決まる、といった具合で２つの合成数にまたがった関係があります。とはいえ $n_1$ の場合と同様にやって、 $p_4$ と $p_5$ を同時に探索しながら、対応する $n_4 / p_4, n_5 / p_5$ がそれぞれ $q_5, q_4$ と上位の桁で一致するかを確認しながら決めていけばなんとかなりました。今回は上位から決めていった関係で桁数の見積もりをミスっていると素因数分解できないため、桁数は探索してます。

def dfs3(N1, N2, s1, s2, l1, l2):
    if l1 == 0:
        q1 = int(s1, 16)
        if N1 % q1 == 0:
            return (q1, N1 // q1)
        if N2 % q1 == 0:
            return (q1, N2 // q1)
    if l2 == 0:
        q2 = int(s2, 16)
        if N1 % q2 == 0:
            return (q2, N1 // q2)
        if N2 % q2 == 0:
            return (q2, N2 // q2)
    for x in range(10):
        for y in range(10):
            s1_ = s1 + str(x).encode().hex()
            s2_ = s2 + str(y).encode().hex()

            d1 = bytes.fromhex(s1).decode()
            d2 = bytes.fromhex(s2).decode()

            q1_ = int(s1_ + "0" * (l1-2), 16)
            q2_ = int(s2_ + "0" * (l2-2), 16)

            p1_ = N1 // q2_
            p2_ = N2 // q1_

            if str(p1_).startswith(d1) and str(p2_).startswith(d2):
                r = dfs3(N1, N2, s1_, s2_, l1-2, l2-2)
                if r:
                    return r

found = False
for d1 in range(0, 5, 2):
    for d2 in range(0, 5, 2):
        r = dfs3(n4, n5, "", "", L + d1, L+d2)
        if r:
            q4, p5 = r
            p4 = int(bytes.fromhex(hex(q4)[2:]))
            q5 = n4 // p4
            found = True
            break
    if found:
        break
assert n4 == p4 * q5
assert n5 == p5 * q4

素因数分解できたらあとはRSAを復号しておわりです。This is RSAを見たときには $n_1$ や $n_4, n_5$ を思いつかなかったのが悔しいですね*4。

*1:実際にはLLLで整数解ではなく有理数解が得られるので分母を払った形のgcdをとることになるとおもいます。詳しくはmapleさんの解説にあります

*2:実践的にはスケーリングをすることになります

*3:まあなんか $a_ip + a_jp = 0$ となるようにうまく選んで打ち消してるんだと思う

*4:それどころか当時は $n_3$ すら解けてませんでしたが…

ふるつき

v('=')v かに

HITCON CTF 2022 writeup

Baby SSS

Secret

Superprime