はじめに

もう1週間以上前になりますが、Pwn2Win CTF 2020に出ていました。当日は自明なブロック暗号問題を1つ通して残りの時間をRSA問題に費やして解けずに終わりましたが、昨日復習をようやく終えたので解けなかったRSA問題の復習Writeupを生成してこちらに上げようと思います。遅れたのはサボっていたとかでは無くHSCTFとかDefenit CTFに出ていたからです...嘘です、面倒くささと後回し癖が発動しました。

ところで宣伝ですが、このCTFからWriteupをチームのリポジトリにpushするようにしたので良ければそっちも覗いてみてください↓。Pwn2Winの分は日本語で書いていますが、以降に出たCTFの一部の問題はグローバル志向なので英語で書いています。

github.com

Omni Cryptoの問題概要

通常のRSA問題のように公開鍵と暗号文が与えられます。指数 $e$ は例によって65537で特に異常は見られません。 $N$ の生成用のコードが与えられ次のようになっています。

def getPrimes(size):
    # [16, 504]
    half = random.randint(16, size // 2 - 8)
    # [8, 503]
    rand = random.randint(8, half - 1)
    # [17, 1000]
    sizes = [rand, half, size - half - rand]

    while True:
        p, q = 0, 0
        for s in sizes:
            p <<= s
            q <<= s
            chunk = random.getrandbits(s)
            p += chunk 
            if s == sizes[1]:
                chunk = random.getrandbits(s)
            q += chunk
        p |= 2**(size - 1) | 2**(size - 2) | 1
        q |= 2**(size - 1) | 2**(size - 2) | 1
        if gmpy2.is_prime(p) and gmpy2.is_prime(q):
            return p, q

コード中ではsize=1024として2つの素数を生成しその積を公開鍵 $N$ としています。

ここから $p,q$ に関して次のような関係があることがわかります。
$p = c_{top} 2^{l_0 + l_1} + x_p 2^{l_0} + c_{bottom}$
$q = c_{top} 2^{l_0 + l_1} + x_q 2^{l_0} + c_{bottom}$
ここでは $l_0$ がsize - half - randに、 $l_1$ がhalfに対応します。

Writeup

今回使うのは鍵の一部が判明している際のCopperamith's Attackです。SageMathのsmall_roots()は引数betaを適当に指定することで与えられた合同方程式を法 $N$ の約数の下で解くことが出来ます。一般的なRSA問題では $N=pq$ と2つの素因数に分解できるので $\mod p, \mod q$ の下での解を求める事が出来ます。したがって $x + p_{known} \equiv 0 \mod p$ のような方程式を $p$ を知らない状態でも解くことが出来、この解と $p_{known}$ の和によって $p$ を求めることが出来ます。なお、この攻撃が成功するのは $p$ の半分+α以上がわかっている場合だそうです。例によってももいろテクノロジーさんの記事を貼っておきますので詳しくはそちらを参照してください。

inaz2.hatenablog.com

ではこの $p_{known}$ をどうやって求めるかですが、実際に $N$ を先程の $p,q$ から計算し、bit数を考慮すると $N$ の下位 $l_0$ bitは $c_{bottom}^2$ のそれと一致し、上位 $1024 - l_0 - l_1$ bit(なお、これはrandに一致する)は $c_{top}^2$ のそれと一致することがわかることから求まります。

前者を求める方法ですが $c_{bottom}^2 \equiv N \mod 2^{l_0}$ という方程式が成り立つことからSageMathのnth_root()を使って求めることが出来ます。詳細は公式Docsを読んでください↓

doc.sagemath.org

後者に関しては単に $N$ の平方根を取って上位randbit分を得るだけで済みます。

ここで問題になるのはrandとhalfがいくつになるのかです。どちらもわかっていれば共通部分が上位下位でそれぞれ幾つであるかも判明するので前述の手法で簡単に解けることが期待できます。また、片方しかわかっていなくても1024bitの内、残りのbitを全探索することで解けることが期待できます。しかし今回はどちらもわかっていません。そこでrandとhalfで2重ループを回すということが考えられます。

おそらくそれでも何時間か回せば解けるのですが(たぶん)、当日は計算量を気にしてその方針は却下しました。ここで再びget_primes()関数を見るとhalfが最大でも504bitであることがわかります。したがって共通部分は上位下位合わせて1024 - 504 = 520bitは確実に確保されていることがわかります。そこでhalfに対応するbit数である $l_1$ を504に固定し、残りの520bitの内幾つが上位で幾つが下位であるかを総当りします。この方針ですと正しいhalfは求まりませんが、 $p$ のhalfの部分に対応する値が求まってしまえば、その内の上位と下位はそれぞれ $p,q$ 共通部分の一部であることが期待できます。図に示すと下記のようになります。

|--- common ---|--- unknown (fixed: 504 bit) ---|--- common ---|: 立てた方程式

|--- common ---|--- root ---|--- common ---|: 解いた後、rootが解

|--- common ---|(--- common of root ---|--- root ---|--- common of root---)|--- common ---|: 解を上下共通部分と未知だった部分に分解

これを動かすとrand、つまり上位の共通部分が150bitを過ぎたあたりぐらいで解が求まりました。後はRSAの復号手順に $p,q$ を放り込んで終わりです。

Code

SageMathを使用して解きました。

N = 0xf7e6ddd1f49d9f875904d1280c675e0e03f4a02e2bec6ca62a2819d521441b727d313ec1b5f855e3f2a69516a3fea4e953435cbf7ac64062dd97157b6342912b7667b190fad36d54e378fede2a7a6d4cc801f1bc93159e405dd6d496bf6a11f04fdc04b842a84238cc3f677af67fa307b2b064a06d60f5a3d440c4cfffa4189e843602ba6f440a70668e071a9f18badffb11ed5cdfa6b49413cf4fa88b114f018eb0bba118f19dea2c08f4393b153bcbaf03ec86e2bab8f06e3c45acb6cd8d497062f5fdf19f73084a3a793fa20757178a546de902541dde7ff6f81de61a9e692145a793896a8726da7955dab9fc0668d3cfc55cd7a2d1d8b631f88cf5259ba1

size = 1024

top_raw = isqrt(N)

bottom_dict = {}
bottom_bit_range = range(17, size - 16 - 8 + 1)
for bottom_bit in bottom_bit_range:
    bottom_dict[bottom_bit] = []
    xs = mod(N & (2^bottom_bit - 1), 2^bottom_bit).nth_root(2, all=True)
    for x in xs:
        if x >= 2^(bottom_bit-1):
            bottom_dict[bottom_bit].append(x)

unknown_bits = 504
known_bits = size - unknown_bits
end = False
for rand_bits in range(8, 504):
    print(rand_bits)
    rand = (top_raw >> (size - rand_bits)) << (size - rand_bits)
    bottom_bits = known_bits - rand_bits
    bottoms = bottom_dict[bottom_bits]
    for bottom in bottoms:
        PR.<x> = PolynomialRing(Zmod(N))
        f = ZZ(rand) + 2^bottom_bits * x + ZZ(bottom)
        f = f.monic()
        roots = f.small_roots(X=2^unknown_bits, beta=0.3)
        if roots:
                p = ZZ(rand) + roots[0] * 2^bottom_bits + ZZ(bottom)
                q = ZZ(rand) + roots[1] * 2^bottom_bits + ZZ(bottom)
                print(p, q)
                if p*q == N:
                    print("[+]: found")
                    end = True
                    break
    if end:
        break

Flag

CTF-BR{w3_n33d_more_resources_for_th3_0mni_pr0j3ct}

反省点

実はこの問題で使われているget_primes()では、下位共通部分であるsize - rand - halfが512を超える確率が2/3ぐらいあり、当初はその仮定で考えていました。前述のように下位共通部分はnth_root()で簡単に求めることが出来るのでこれを $p_{common}$ とおいて $2^{l_0} x + p_{common} \mod p$ を求める問題だと思っていました。しかし、実際は下位共通部分はそこまで大きくなく、この方法だと求めることが出来ません。上位bitも $N$ の平方である程度推定できることも気付いていましたが両者を組み合わせると計算量が2重ループでひどいことになると思っていたのでそんな問題を出すわけ無いだろうと思い、下位共通部分が大きいことに固執していたのが大きな敗因の1つです。