Plaid CTF 2021 XORSA writeup
Plaid CTF お疲れ様でした!
問題数は多いわけではないのですが、難易度が高い…。XORSAをなんとか解けたのですが他の問題には全く歯が立たず、結局この一問のみのsolveです。
Result
XORSA Writeup
XOR + RSA = XORSA
ファイル:xorsa.29fb8e0ef0173eef5953d792373b7db98169018db6747f5e27d26c1c7cb98873.tgz
「linux tgz 解凍」でググります。どれ試しても上手くいきません。出てきたエラーをググるとこんな親切なサイトが!
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
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(22048)では?となり無理だなと思っていたのですが、最悪計算量を考えたらO(20482)程度かなと思っています(紙に書いたらそうなりました、頭の良い人証明して)。すぐさま実行に移りました。
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に追加すべき候補は2通りに絞られる 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)
PCTF{who_needs_xor_when_you_can_add_and_subtract}
おわりに
leaky block cipherの途中経過だけでも供養します。
hashcashの突破について、以下の文字列を投げる必要があります。
- ":" でsplitされる
- split後、0番目には"1" とする
- 1番目は"21"より大きい値にすべきだが、大きくし過ぎると後のPoWがきついので"22"とする。
- 3番目は最初に貰った16進数
- 2番目は"100", 4,5番目は"0"とテキトーに決める。
- 全体のSHA-1ハッシュ値を16進数にした時上位5桁が"0"になるようPoWする。
これで突破できます。
しかし、それから自作のクラスのインスタンスのencryptが予測できず終了です。
関係ない話ですが、Markdownで目次が上手くいかないのなんでだろう。