Optimus Prime

4 minutes to read

We are given a remote instance to connect to. There are some options:

$ nc 167.99.202.193 31899
Your people must learn to be masters of their own fate.
1. View status of the Transformer.
2. View Serial ID's of the Transformer.
3. Register new Transformer.
4. Enter to the access panel.
Enter the option: 1
 Battery: 60%
 Mechanical damages: 14%
 Heat: 64.76 ºC


Ncat: Broken pipe.

$ nc 167.99.202.193 31899
Your volume, like any capability, is also a responsibility.
1. View status of the Transformer.
2. View Serial ID's of the Transformer.
3. Register new Transformer.
4. Enter to the access panel.
Enter the option: 2
 Processor ID: 5iG6i-u7gb5
 Engine ID: XVZYI_278
 Rotor ID: 788hdIVu
 Controller ID: 435b7
 UV RAY Laser: N-yg797
 Lens ID: eye-455
 Armor ID: 6fJKC-43efw
 E.L.F ID: Yon6.oiL
 Sensors ID: DGTX-486f


Ncat: Broken pipe.

$ nc 167.99.202.193 31899
Neither impossible, nor impassable!
1. View status of the Transformer.
2. View Serial ID's of the Transformer.
3. Register new Transformer.
4. Enter to the access panel.
Enter the option: 3
You can't register a new Transformer until you log in


Ncat: Broken pipe.

$ nc 167.99.202.193 31899
Neither impossible, nor impassable!
1. View status of the Transformer.
2. View Serial ID's of the Transformer.
3. Register new Transformer.
4. Enter to the access panel.
Enter the option: 4
PUBLIC KEY: 561530983183771644079081983133798886393315956842713837364876531649006798532220730114101411755795010319041295006801350917538756933499118617906317031195270077996926403624167003776056371107839368665181097764439194459189223899109973780067747737810092153902289460088036423880150476966442534774553341463189986208172232827051285526840902140313481364721901864123911011320463414816873164360267912578559507379639135636187433596948652766777666836886846836958378588268077971837472074268732874219872654681857716405976488231199626780398481640108544235249033287071829129695641174000782364626628385008069223240415794168792983331187517584059922896859393495222716472879930970681273918024127565161588448456637434626076495922878734813092660550806993569318588995667355672939047576853520827749232882520805817097901435167281301065520534686463750548527065004526512899978446933334931789991777691203140056028033711607116455127229004217741079025900939041650303633655036023592351427096299269324770012178470783507481318950193911934095464050789933973944959561340943805633191801390910919158965343251753924778364361992590415546653203022780846100722718253700076817407880515244228228331352925174426850015621965026601020231470421066275223297008742866239028201616549297
ENCRYPTED PASSWORD: 478433640659999909494191352317871798130455824918379548803426918434917846639343016566162840910865561178722256715981978209460254339146239711331342400226506789950101981589316626554270102018898421811117722378733550248600097683887697688604134869368517906548458208251021435357024461369811788365509479210707348656092869889564338136336543331671149450042893739237285802897073477565614570522656667036132585939975696784680815717851583346707640317324432358245031147929286213666773861704595122964859916902660079486583256859654560907207756060808745941468321485063015298630156644267999050346301234569247203357193989245850972352536744184424711523579547352961208825878553154832349587187344121773681413828873274598590409300089865600358498669459273494865441858894195460943962230569092193081568834701100790852366960295527607344882593597464702313029563578260916592447601774708819078699287065353277224184336953141401114989828012740785816597467134398795454332960168213069367520422690188330360363547402836335519018053996252884588054197617439636359408910390135159839471927018087222389985022566622381108776793949150510196977124060472434418599667191540426334403433398301838300639236441554597495553171237299370972025039094868074461193337336268675948069907974382  
The private key has been sent to your email. Please use it to proceed:


Ncat: Broken pipe.

It seems that the only interesting option is the fourth one. It uses a public key cryptosystem (probably RSA).

RSA background

RSA works as follows: We take two large primes $p$ and $q$ and set the modulus $n = p \cdot q$. Then we choose an exponent $e$ (typically $e = 65537$) and encrypt a message $m$ in decimal format:

$$ c = m^e \mod{n} $$

The public key is the tuple $(n, e)$, and the private key is composed of the two prime numbers. To decrypt, we need to compute $\phi(n) = (p - 1) (q - 1)$ in order to find the multiplicative inverse of $e$, which is $d = e^{-1} \mod{\phi(n)}$. Then the decryption of $c$ is:

$$ m = c^d \mod{n} $$

This works because

$$ c = m^e \mod{n} \iff c^d = (m^e)^d = m^{ed} = m \mod{n} $$

The security flaw

Since the challenge is called “Optimus Prime”, we can guess that the server uses a fix prime number to build $n$ (let’s call $p_x$ such prime). Then, we can request two different public keys ($n_1$ and $n_2$), so that $n_1 = p_x \cdot p_1$ and $n_2 = p_x \cdot p_2$ (where $p_1$ and $p_2$ are two different prime numbers).

In order to get $p_x$ we can apply the Greatest Common Divisor (GCD) between $n_1$ and $n_2$. Let’s try it:

$ python3 -q
>>> n1 = 561530983183771644079081983133798886393315956842713837364876531649006798532220730114101411755795010319041295006801350917538756933499118617906317031195270077996926403624167003776056371107839368665181097764439194459189223899109973780067747737810092153902289460088036423880150476966442534774553341463189986208172232827051285526840902140313481364721901864123911011320463414816873164360267912578559507379639135636187433596948652766777666836886846836958378588268077971837472074268732874219872654681857716405976488231199626780398481640108544235249033287071829129695641174000782364626628385008069223240415794168792983331187517584059922896859393495222716472879930970681273918024127565161588448456637434626076495922878734813092660550806993569318588995667355672939047576853520827749232882520805817097901435167281301065520534686463750548527065004526512899978446933334931789991777691203140056028033711607116455127229004217741079025900939041650303633655036023592351427096299269324770012178470783507481318950193911934095464050789933973944959561340943805633191801390910919158965343251753924778364361992590415546653203022780846100722718253700076817407880515244228228331352925174426850015621965026601020231470421066275223297008742866239028201616549297  
>>> n2 = 453473442250176875887884408494220813255318673548591420930808729711094153852669604421072095147310535852894196497701194495763934656918609242180114413009407095537822822748643497472849565895597043585990519691637441008444521268699797671965200208092597532516403402190454917233181150763224005871254278889048272186835605224243556324477564249866430027847480350925849946864753434500537411434272377354967175199633700713666315246294534992637512422841359051759213575691108707708370754825888159259774053850736224767423679354716176586323223030008253463691575953103663417515811761767764175251537126181846166669552092900829212085164322801334699759213430309486363444549508842349294988879068005189767324109391528329543985407116444501230761784856233364104610311903991726395798820046856030660523463227914493442647668650499386551929507449774406611125430990377567739666050143337985208270998972824314753324371044553546822349213844258163058860685053178159783903879568864036793018848540186772536917354390604909493147042812091520636469519583251810079508546092492522575089517856699654431120435334917909033314645473050982459170263445473946283036131237144416259114422589056262458804839224321263904326617355529086163074030618050603883415427312184962264005049090229
>>> import math
>>> px = math.gcd(n1, n2)
>>> from Crypto.Util.number import isPrime
>>> isPrime(px)
1

And there we see that we get such prime number $p_x$. Once we have this, we can find $p_2$ (for example), compute $\phi(n_2)$, $d_2$ and decrypt the ciphertext $c_2$. We can assume that $e = 65537$:

>>> c2 = 343845506025778530795718670598666171710030663159821861076070623117224684551860690631782987313834807370036911786095234337597419898461321063261995350759485297249486660913049139886412600212877009756892583998498669904341883112438581954400464063594377774021723284323552120385379343484829380561610088720516935305926692406948937248751510032745753230120037423164658296389616587276180568248089558247676815598468834040711325058721414948264455314035303701042721613668068907350330619412586217479631982116371749767359269424273722566832487848362060917263112202535860565888767090305511288178082790987268616489182855115557905286226273617078447915074472302468279345661674845390745475541712501117665472557682177794539758420404949640140854189394151698888319404643070036167056321938905981038847592990485309538582614141417479562739031032638166131529167960622106245588847474016925660498629715572522834239181453232014679322906670345921157689374407549621116678227570482589299811459042126157149361175419596601660478163655408416055881341992948247566820045423428109130315763948267507723930247493194336446361745042850763049750188560485546096422316090260110018037330823331595681210532701821560508235962726792443805820567222233675381894097871026348225462856434914  
>>> p2 = n2 // px
>>> phi_n2 = (px - 1) * (p2 - 1)
>>> e = 65537
>>> d2 = pow(e, -1, phi_n2)
>>> m = pow(c2, d2, n2)
>>> bytes.fromhex(hex(m)[2:])
b'zrevmbwrunv'

Flag

Ok, this message seems to be the key we need to send to the server. At this point, we can wrap the above calculations inside a script that handles the connection and sends the key back to get the flag:

$ python3 solve.py 167.99.202.193:31899
[+] Opening connection to 167.99.202.193 on port 31899: Done  
[*] Closed connection to 167.99.202.193 port 31899
[+] Opening connection to 167.99.202.193 on port 31899: Done
HTB{3uc1id_w4z_th3_pr1me_h4x0r}

[*] Closed connection to 167.99.202.193 port 31899

The full script can be found in here: solve.py.