HackZone VIII CTF : RootCrypto writeup

Published in

Hackzone

5 min readApr 15, 2020

In this post, I’ll present the writeup for HZVIII’s Cryptography challenge CryptoRoot. This challenge was solved by one team (yeah hopefully a proof of solvability), this is Likkrid, and this will be the author’s writeup, Let’s go ..

We start analyzing the description of the challenge, we will be facing some RSA and root problems, fair enough but why are we missing the public key (n, e) ? ..

Wait there is a netcat connection, let’s jump in and see what it will tell us

Cool spider there :33 Sounds pretty straightforward:

Typical encryption oracle,
Secret decryption challenge to get the flag

Since we are dealing with RSA and we are still missing the public key, let’s dig deeper and find it:

Retrieving the public key:

We know that RSA encryption follows the formula:

RSA encryption

Let’s try to encrypt some trivial small data values which encryption yields a lot of information about the exponent (e.g 0,1)

0 encrypted into 2304
1 encrypted into 2401

Obviously a transformation is made on data before the encryption, we have to figure it out. Let’s keep it simple and assume that we are transforming the data into corresponding ascii code.

Trying with 48 (ascii value of 0) we have that e=2. Great, so we have a Rabin Cryptosystem behind this service, you can read more about Rabin but we will mention few facts about it here:

Public key cryptosystem with n = p * q
p and q two large primes where we often choose p ≡ q ≡ 3 (mod 4) to simplify the computation of square roots (yeah our Roots from the description show up) modulo p and q (check this for algorithms solving square roots modulo primes)
Obviously e=2.

Some participants were surprised finding GCD(Euler_phi,e)=2 and thought that maybe the system was corrupted and unsolvable (referring to RSA). In fact, GCD(Euler_phi,e)=1 is simply a requirement for unicity of decryption. But choosing e=2 is a dead end for Euler’s theorem (whatever n is, either a prime or a composite integer Euler_phi will be an even number). It is well-known that we stick to padding and/or redundancy to solve this problem in Rabin cryptosystem.

Let’s find the value of n ..

We can encrypt two messages and calculate their powers of 2 ( value of e that we found), we end up with:

We calculate then GCD[(1),(2)], with some luck we will get the value of n, (but, of course we can get also unlucky finding a multiple of n, then we will have to encrypt more messages to find n deterministically).

Finally we get modulus:

n = 524401030912935840156368455492538779896072847975492539783953077216160596391396524596555889403478360635508941057096235808098982594382826760788658887864079605086232038075105222664675815063138005147439485782506259009624824296232296944425318333560850178684312526817439342734689738364582211830578544010699057807203320116245103219640909951081494988002319765382671236511814606458624467531074582596773431874694935213863065835130776570102528998539870037798875514772405725953152807827875644835063461362848276235279288494790662427109010174114288547210746780314409433490420740929029917660922177529383005755493606450968989600036591872139774563457291304714621382850306338318383694394023670273738741884285451728722809179581104268263353354410259122126897482066524944828581102573072424747254413355317992820025689435898822618357910829932309681708512761041680580326542636488901596400273092859496536665261209628771967676593298088438756584085850168390826492357591694530728927545159125688421720769504309135232994452965404788824145859903335144277993141641812228988356068335627075992515031511555465443000310271590499571469597897378149382128872926855327643021881658781065609514486670512314081487136875340579717886552369036342643166242383119050497955330177041

The first part is over, a new journey is about to begin to retrieve Rabin’s private key and get the Flag.

Rabin’s private key & Decryption

We use factordb to factorize n, Surprise !! It’s a Rabin with 3 Primes.

p = 169190849908171023288307339044530660251053691880472974308588587669108393339479218343467606959873557652028796331630894148101895749038501058026903394542693227061956193960988086687175451732633751931097670564771615055986238919767344273578222753486514961292954087400823074165260390884832213999754832198100883152817
q = 109428029649440430724985328440426800088095512795047844765497650150300167758617620285912074886715196546316654722962451425382958488866875211874405557040233022812316149661256784075369885622582466551711782792964231138949677143512586814879652448516728832311262378696530387109817059014697289977596289928808870560521
r = 28324228239363374596194831603892272765727935024801683641238831323425191843497399356113972653282785821445234526607381395724909846914957106058244321651826693574257510573656400163170422624552961721577807397112275802706888482667684303788820139172010927871675237895870362714635301376080466880238223417751435854652464694778418228850337952011455340246224617747303090930130568062616483524260986660013661622929386103302423390900287566404575267019924851268350001130408444267784904813657390464859088902327337540317280115899553958900970608889557148594099762075034121853284539269993839507653071747630042882785844835860744926287513

Okay let’s check if, at least, those primes verify the key generation recommendation to yield a solvable problem by one of the simplest algorithm for finding square roots.

Unfortunately we have :

p ≡ q ≡ r ≡ 1 (mod 4)

This is how we will proceed:

We will solve the system of congruences:

Use retrieved roots to get the 8 candidate plaintexts.

Solving Congruence System

We have a modular arithmetic problem to solve for z in a congruence of the form z² ≡ c(mod p), where p is a prime, so I choose the Tonelli–Shanks algorithm. After using the algorithm we end up with:

mₚ for z² ≡ c(mod p)
mᵩ for z² ≡ c(mod q)
mᵣ for z² ≡ c(mod r)

We have to note that if r is a root for x² = y, then so is -r (obviously) and since we are in modular arithmetic so is n-r (c + nℤ ∈ ℤ/nℤ) cool! now we have:

mₚ(mod p)   from z² ≡ c(mod p)
p-mₚ(mod p) from z² ≡ c(mod p)
mᵩ(mod q)   from z² ≡ c(mod q)
q-mᵩ(mod q) from z² ≡ c(mod q)
mᵣ(mod r)   from z² ≡ c(mod r)
r-mᵣ(mod r) from z² ≡ c(mod r)

Solving Congruence System

Some participants were so close to solve the challenge, but they tried to solve this system of congruences using the following system. Unfortunately, that will not work here because we didn’t satisfy p ≡ 3 (mod 4), it is not a requirement so I enjoyed designing the problem in a way that requires more effort..

Finding square roots modulo a prime where prime ≡ 3 (mod4)

Retrieving roots

We will use Chinese remainder theorem, to retrieve the 8 candidate plaintexts. You may ask “why 8 ??”

Applying CRT on a system requires pairwise coprime positive integers nᵢ, this has a solution, and the solution is unique modulo N =Πnᵢ , i=1..k.

In our case we have 2 congruences per prime (p,q and r), so the number of combinations having pairwise coprime factors is in a way to pick r=1 from each n=2 congruences related to one different prime.