Plaid CTF 2021 XORSA writeup - Attack All Around

Plaid CTF お疲れ様でした！

問題数は多いわけではないのですが、難易度が高い…。XORSAをなんとか解けたのですが他の問題には全く歯が立たず、結局この一問のみのsolveです。

plaidctf.com

Result

f:id:partender810:20210419111339p:plain — 145位でした

XORSA Writeup

XOR + RSA = XORSA
ファイル：xorsa.29fb8e0ef0173eef5953d792373b7db98169018db6747f5e27d26c1c7cb98873.tgz

「linux tgz 解凍」でググります。どれ試しても上手くいきません。出てきたエラーをググるとこんな親切なサイトが！

tar.gzファイルの解凍 - ZDNet Japan

fileコマンドを叩いてみると

$ file test.tar
test.tar: POSIX tar archive (GNU)

と出るので、このサイトの通りmvコマンドでtest.tarなどにしておきます。そしてtar xvfで解凍できました！いやもう最初からtarファイルで配ってくれ。

$ tar xvf test.tar
dist/
dist/xorsa.sage
dist/public.pem
dist/flag.enc

xorsa.sageが問題プログラムということで覗いてみます。

xはpとqのxorした値です。 keyをRSA.constructに(n,e,d,p,q)を投げて生成し、それを用いてPKCS1_OAEPのインスタンスを作ります。 flagを暗号化したものや公開鍵などをファイルに出力します。

まずは公開鍵を知りたいのですが、public.pemを見るとn = 整数という形ではなくopenSSLを用いて解読する必要がありそうです。 openSSLは良くは知らないのですが、このサイトやpicoGymで出た問題から解読できました。

How to extract public key using OpenSSL? - Stack Overflow

picoCTF

openssl rsa -noout -text -inform PEM -in public.pem -pubin

これで以下の結果を得られました。

$ openssl rsa -noout -text -inform PEM -in public.pem -pubin
RSA Public-Key: (4096 bit)
Modulus:
    00:8c:6d:db:f9:a2:dd:53:a2:46:6f:f6:1b:b6:2c:
    f5:be:3a:f8:9d:e8:21:bb:75:a5:81:ab:c8:51:4a:
    84:39:2a:66:13:ea:a3:26:9c:15:98:43:ee:f7:81:
    df:55:22:a9:2d:2d:5a:dc:3c:95:a5:4c:5f:eb:42:
    7d:08:2c:15:7d:4f:2d:b6:90:14:11:c0:ce:29:f1:
    57:15:73:fb:48:88:85:ee:c8:d3:6f:8c:79:48:2b:
    51:23:a8:20:47:d7:95:88:a9:5f:b2:c1:a1:67:10:
    42:78:5f:5d:0c:14:69:eb:a2:18:58:d6:43:f6:64:
    65:9f:9e:63:03:39:5a:05:da:bb:05:03:f2:e8:80:
    a8:99:a6:7e:78:40:bd:20:fa:c2:83:16:93:62:09:
    28:d0:c9:0c:47:ab:d6:95:d0:0d:27:e4:8e:78:62:
    a3:15:01:59:ac:58:e5:0b:64:d1:c9:d4:6c:c7:c6:
    c1:95:df:61:ec:0f:ef:79:93:7f:55:45:b0:8a:53:
    51:73:82:c0:73:62:fc:8a:24:75:a9:9e:9c:b4:1e:
    4f:c5:44:a7:00:e1:1c:a2:3c:65:8a:df:ce:d9:ee:
    bb:79:5e:3a:a5:a3:32:d1:e3:9b:c7:28:d8:e0:39:
    f0:7d:2b:2b:f9:3c:4e:11:20:a3:d4:cb:1b:7a:e1:
    e0:d7:8c:ea:c3:75:95:f0:bd:99:4e:c7:8e:bf:8d:
    39:c5:fb:12:d8:03:cd:f9:bb:01:9a:6f:da:4d:20:
    bf:fd:e8:fe:f0:52:a6:18:94:33:ed:cf:94:f6:d7:
    bb:6a:8d:9c:c1:91:96:50:e0:13:9b:6f:28:4d:44:
    bf:1d:67:2e:5c:e8:a5:6f:2e:7b:d3:e2:eb:ee:6f:
    b7:f6:31:e0:03:9c:f5:07:9e:cf:74:b1:c7:56:5e:
    60:58:b8:1f:46:b5:b6:6e:af:7f:83:4e:94:2c:ce:
    5a:6c:c3:bd:47:ef:4b:d4:18:b1:79:c1:11:4a:a0:
    fb:68:ab:3f:aa:91:ed:bc:51:04:07:e1:05:24:b3:
    79:0f:04:e3:b2:7e:46:eb:c2:5e:5b:b2:b9:34:d4:
    e4:6b:f0:94:05:a5:67:f3:c7:e7:7c:e3:f0:ae:e3:
    83:bd:0c:8d:72:ec:b2:a3:99:73:7c:3f:d2:79:26:
    1b:f2:7b:7c:cf:ee:8b:b2:14:1e:20:2e:fb:78:68:
    7d:15:85:60:9a:af:7c:2c:6f:35:97:f8:4b:00:3b:
    55:a9:f2:ea:d1:ae:df:e0:00:56:cb:b5:50:99:42:
    c2:88:dd:d2:08:fc:05:da:80:33:35:b5:e0:62:b2:
    70:9e:f5:9f:d0:e3:d4:ea:21:7b:8f:29:5d:4a:c0:
    21:ff:37
Exponent: 65537 (0x10001)

この16進数をsplit(":")などで強引に整数型として入れます。

次に、暗号化されたflagについてみていきます。
とりあえずbytes_to_longしてみると、なんとnより大きい値に…。これじゃ復号できないじゃないか！
わざわざPKCS1_OAEPを使っているということはここに復号の方法があるのではないかと手元で動かしてみたら、key = RSA.construct( (n,e,d,p,q) )で暗号化時と同じパラメータを投げて生成したkeyによるインスタンスでdecryptすればOKです。

>>> key = RSA.construct((n,e,d,p,q))
>>> flag = b"m1z0r3{test_flag_yeah}"
>>> cipher = PKCS1_OAEP.new(key)
>>> enc = cipher.encrypt(flag)
>>> cipher.decrypt(enc)
b'm1z0r3{test_flag_yeah}'

まあ、普段のRSAと同様(n,e,d,p,q)の全てを求めたらOKですね。頑張って求めていきましょう。

nは当然素因数分解出来ませんし、情報としてもp xor qのみ公開されています。これを使ってp,qを求めるのだろうとなりますね。
とりあえずいつもの「RSAでやってはいけないnのこと」を見て、pの上位ビット(1/2程度)知られるとダメとなるcoppersmithかなぁと目星を付けます(違った)。「xor multiple」でググっても複数入力のxorしか出てきません。
数学的な問題なのでm1z0r3の黄coderに聞いてみました。「bit毎に見ていけばいけるのでは？」なるほど。

p,qを2進数でのかけ算の筆算を頭に浮かべると、例えばp,qの下位3bitsが決まればnの下位3bitsが決まります(p,qの下位3bits以外はnの下位3bitsに影響しません)。 pを01どちらかを最上位に追加するbrute forceを行ってどんどんbits数増やしていき、増やしたpの01とxor結果よりqの最上位に追加する01が決まります。増やす途中のp*qの下位bitsとnの下位bitsが一致しなかったら、そのp,qは違うとなり一致していたbitまで戻り01の違う方を最上位に追加する再帰で考えます。

最初これを考えた時は直感的にO(2²⁰⁴⁸)では？となり無理だなと思っていたのですが、最悪計算量を考えたらO(2048²)程度かなと思っています(紙に書いたらそうなりました、頭の良い人証明して)。すぐさま実行に移りました。
pの候補が2048bitsの時にnで割り切れるかどうかでチェックして余りが0なら終わりです。

p,q,xorの値からtp="11", tq="01"(temp_p(q)の略)であることが分かるので、後は再帰で解きます。pythonは再帰回数上限を設定しないと怒られるのでsysライブラリから設定します。とりあえず3000に設定しておきました

ciphertextについては、最後の改行があるとincorrect lengthと怒られるのでそれを抜いてdecryptすると上手く復号されました。

pを仮に置くとqが一意的に決まってしまうことが素因数分解(?)の計算量削減となる脆弱性出したという感じですね。

今回からmarkdown記法で書いているので、solverを張り付けますね(最初からやれ)。githubには完全版と問題ファイルも添付してます。

GitHub - ksbowler/PlaidCTF_2021

import sys
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

n = (省略)
x = (省略)

M = 2048

binn = str(bin(n))[2:]
binx = str(bin(x))[2:]
binx = "0" + binx
sys.setrecursionlimit(3000)
def recur(tp,tq):
    #再帰でpを求める。tp,tqはp,qの候補の値
    #求めたらpを返し、現在のtp,tqでは求められないのであればFalseを返す
    bits = len(tp)
    if bits == M:
        #tpが2048bitsになった場合
        p = int(tp,2)
        if n%p == 0:
            print("Find!")
            print(p)
            return p
        #nで割った余りが0でないから、tpはpではない
        return False
    tn = int(tp,2)*int(tq,2)
    if str(bin(tn))[-bits:] != binn[-bits:]:
        #tp,tqの積の下位x bits (xはtpの長さ。変数bitsと同義)がnの下位x bitsと異なるのであれば、tp,tqはp,qの候補値から外れる。
        return False

    #xの値より、tp,tqに追加すべき候補は２通りに絞られる
    if binx[-(bits+1)] == "1":
        p = recur("1"+tp,"0"+tq)
        if p: return p

        p = recur("0"+tp,"1"+tq)
        if p: return p
    else:
        p = recur("1"+tp,"1"+tq)
        if p: return p

        p = recur("0"+tp,"0"+tq)
        if p: return p

    return False

p = recur("11","01")
q = n//p
e = 65537
phi = (p-1)*(q-1)
d = inverse(e,phi)
f = open("./dist/flag.enc","rb")
a = f.readlines()
key = RSA.construct((n,e,d,p,q))
cipher = PKCS1_OAEP.new(key)
ciphertext = a[0] + a[1][:-1] #最後の改行が入ると悪さをするのでそれを抜く
flag = cipher.decrypt(ciphertext)
print(flag)