Midnightsun CTF 2021 writeup

Midnightsun CTFは毎年いくつか独自色の強い問題が出るな、という印象だったのですが、今年はBackupシリーズのcryptoがひどかった印象があります。その他AVRマイコンなどの組み込みに関連する問題が出るのはいつもどおりという感じ。

私は純粋cryptoを2問通しました。どちらもsolve数が二桁前半で、簡単というほどではないが難しい問題ではない、という感じでの面白い問題でした。なんとかチームメイトに怒られない程度の貢献はできたかな。

ocat_024
dbcsig_64434

ocat_024

u = getrandbits(512)
p = next_prime(1337 * u + getrandbits(300))
q = next_prime(2021 * u + getrandbits(300))
n = p * q

sage: n                                                                                                                                                       
376347864369130929314918003073529176189619811132906053032580291332225522349124770927556541528827257242440708492473086949335591022991715583608318595770643139658398940858358366788472884935226392323475683663699450192657590965945792699658618476121298301964814904817629813971114882401961638885452623305901569855693667669
sage: e                                                                                                                                                       
310766221758298615381202293330340201483059349618898159596286032329366528507960364515724537815587119639645241427449290559721282531962504187828968370246921804939126848756614691757878117709116273156365166616707032588454229002048939764035908902821773289938766897121298435864096976179239412103595971947786698704390414999
sage: round(log(d, 2))                                                                                                                                        
376
sage: Zmod(n)(int.from_bytes(flag, 'big'))^e                                                                                                                  
303959676149267585825046248298946771045524761540948385119310381022731003152171453295355624619013005255259014408962058282203132797411290952180380162699236575669681289832696809724483816916203823843359489329046259936011464869397208487809073597880729992617105037777911285154649450892121090200338517719744860831555514222

$p = 1337u + a, q = 2021u + b$ となっているRSAの問題です。加えて、 $d$ が比較的小さいことが分かっています。

まず第一に注目するのは素数が独特な構造になっていることです。これは過去にConfidence CTF 2019 TeaserでReally Suspicious Acronymとして出題されている形式で、 $u$ が共通しており、 $a, b$ のサイズが比較的小さいことから $\frac{p}{q} = \frac{1337u + a}{2021u + b} \simeq \frac{1337}{2021}$ と近似ができるので、 $n \times \frac{1337}{2021} \simeq n \times \frac{p}{q} = p^2$ という近似ができます。この近似により $p, q$ の上位210ビット程度を求めることができます。

しかしこれだけの情報では、Coppersmith's methodを用いた素因数分解には不足です。そこで $d$ が比較的小さいというヒントから、 $ed = 1 \mod \phi(N)$ を使って立式していきます。

$\phi(N) = N - (p + q) + 1$ ですから、 $p + q$ を先程近似した値 $p', q'$ と真の値との差 $r$ を用いて $p + q = p' + q' + r$ と表して以下の式が成り立ちます。

$ed = 1 + tN - t(p' + q' + r) + t$

さらに $\mod e$ をとります。

$0 \equiv 1 + tN - t(p' + q' + r) + t \mod e \tag{△}$

式(△)において、未知変数は $r, t$ であり、 $r$ は素因数 $p, q$ の未知の部分なので300bit程度、また $t = (ed - 1) / \phi(N) \simeq (2^{1045}\times 2^{376} - 1) / 2^{1045} \simeq 2^{376}$ であることから、 $t$ の大きさは最大でも376bit程度になります。一方 $e$ は1000bit以上ありますから、 $r, t$ は剰余多項式(△)の比較的小さな整数根になっていると言えそうです。したがってCoppersmith's methodによって $r, t$ の具体的な値を求められるかもしれません。多変数多項式の小さい根を求める実装としては、 defund/coppersmith が優れています。これを使って $r, t$ を求めることができれば、 $\phi(N)$ を計算しフラグを求められそうです。

# https://raw.githubusercontent.com/defund/coppersmith/master/coppersmith.sage
import itertools

from sage.rings.polynomial.multi_polynomial_sequence import PolynomialSequence

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()
    
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = PolynomialSequence([], f.parent())
    for i in range(m+1):
        power = N^(m-i) * f^i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = power
            for variable, shift in zip(f.variables(), shifts):
                g *= variable^shift
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1/factor)
    B = B.change_ring(ZZ)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in B*monomials:
        if h.is_zero():
            continue
        H.append(h.change_ring(QQ))
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            V = I.variety(ring=ZZ)
            if V:
                roots = []
                for root in V:
                    root = map(R, map(root.__getitem__, f.variables()))
                    roots.append(tuple(root))
                return roots

    return []


n = 376347864369130929314918003073529176189619811132906053032580291332225522349124770927556541528827257242440708492473086949335591022991715583608318595770643139658398940858358366788472884935226392323475683663699450192657590965945792699658618476121298301964814904817629813971114882401961638885452623305901569855693667669
e = 310766221758298615381202293330340201483059349618898159596286032329366528507960364515724537815587119639645241427449290559721282531962504187828968370246921804939126848756614691757878117709116273156365166616707032588454229002048939764035908902821773289938766897121298435864096976179239412103595971947786698704390414999
c =  303959676149267585825046248298946771045524761540948385119310381022731003152171453295355624619013005255259014408962058282203132797411290952180380162699236575669681289832696809724483816916203823843359489329046259936011464869397208487809073597880729992617105037777911285154649450892121090200338517719744860831555514222

p_ = int(sqrt(n * 1337/2021))
q_ = int(sqrt(n * 2021/1337))

PR.<r, t_> = PolynomialRing(Zmod(e))
f = 1 + k_*n - t_*(p_ + q_ + r) + t_
for ans in small_roots(f, [2^300, 2^377]):
    r = int(ans[0])
    phi = n - (p_ + q_ + r) + 1

    d = int(pow(e, -1, phi))

    m = pow(c, d, n)
    print(m)

求まりました。

dbcsig_64434

from hashlib import sha256


def keygen(password):
    while True:
        p = 2 * random_prime(2 ^ 521) + 1
        if p.is_prime(proof=False):
            break
    base, h = 3, password
    for i in range(256):
        h = sha256(h).digest()
    x = int.from_bytes(h * 2, "big")
    return base, p, pow(base, x, p), x


def sign(message, priv):
    h = int(sha256(message).hexdigest(), 16)
    k = next_prime(int.from_bytes(
        sha256(message + priv.to_bytes(128, "big")).digest() + sha256(message).digest(),
        "big"
    ))
    r = int(pow(g, (k - 1) / 2, p))
    s = int(Zmod((p - 1) / 2)(-r * priv + h) / k)
    return r, s


g, p, pub, priv = keygen(b"[redacted]")
r, s = sign(b"blockchain-ready deterministic signatures", priv)

（配布ソースコード中に存在した、問題と直接関係ないコメントを省略しています）

独自のデジタル署名アルゴリズムのようですが、プログラムはいわゆるDSAのそれと似通っています。目的は $d = priv$ を求めることで、 $g, p, pub, r, s$ に加えて、平文から求められる $h$ が分かっています。

このアルゴリズムを観察すると、2つ特徴的な部分が見つかります。まず1つ目は秘密鍵 $d$ の構造で、int.from_bytes(h * 2, "big") のように、256bitの値を2回繰り返して並べることで512bitの値を作っています。値の大きさは512bitありますが、情報量としては256bitのものと等価と考えられます。2つめは $k$ の値で、こちらも256bitの値を2つ並べて作られていますが、上位256bitが全くわからない一方、下位256bitは $h + \alpha$ でありおよその値が分かっています。

式をたてて整理してみます。そもそものDSAアルゴリズムでは $ks \equiv -rd + h \mod q$ （ただしここで $q = (p - 1) / 2$ です）がなりたち、それは今回も同様です。ここで $k = 2^{256}k' + h + \alpha$ , $d = 2^{256}d' + d'$ と表しつつ、移項して式を整理すると次のような形になります。

$s(2^{256}k' + h + \alpha) + r(2^{256}d' + d') - h \equiv 0 \mod q$

ここで未知数は $k', d', \alpha$ で、 $k', d'$ はそれぞれ256bitの値です。 $\alpha$ はどのくらいかわかりませんが、だいたい1000を超えることはないでしょう。他方、 $q$ は521bit程度の値であり未知数と比較して大きいですから先ほどと同様にCoppersmith's methodが適用できそうです。

# https://raw.githubusercontent.com/defund/coppersmith/master/coppersmith.sage
...

from hashlib import sha256

g = 3
p = 403564885370838178925695432427367491470237155186244212153913898686763710896400971013343861778118177227348808022449550091155336980246939657874541422921996385839128510463
pub = 246412225456431779180824199385732957003440696667152337864522703662113001727131541828819072458270449510317065822513378769528087093456569455854781212817817126406744124198
r = 195569213557534062135883086442918136431967939088647809625293990874404630325238896363416607124844217333997865971186768485716700133773423095190740751263071126576205643521
s = 156909661984338007650026461825579179936003525790982707621071330974873615448305401425316804780001319386278769029432437834130771981383408535426433066382954348912235133967
message = b"blockchain-ready deterministic signatures"
h = int(sha256(message).hexdigest(), 16)

q = (p-1) // 2
# assert q.is_prime ????????

PR.<d_, k_, a> = PolynomialRing(Zmod(q))

f = 2^256 * s * k_ + s * (h + a) + r * (d_ + 2^256 * d_) - h
roots = small_roots(f, [2^256, 2^256, 1000], d=4, m=4)

for root in roots:
    dval = Integer(root[0])
    dval = dval * 2^256 + dval
    if pow(g, dval, p) == pub:
        print("[+] found: {}".format(dval))
        break
    else:
        print("[-] wrong: {}".format(dval))