Zombie Rolled
10 minutes to read
We are given the Python source code to encrypt the flag:
from Crypto.Util.number import getPrime, bytes_to_long
from fractions import Fraction
from math import prod
from hashlib import sha256
from secrets import randbelow
# I hope no one cares about Kerckhoff's principle :)
from secret import derive_public_key, FLAG
def fraction_mod(f, n):
return f.numerator * pow(f.denominator, -1, n) % n
class PublicKey:
def __init__(self, pub):
self.pub = pub
self.f = self.magic(pub)
self.nb = (self.f.denominator.bit_length() + 7) // 8
def encrypt(self, m):
return pow(m, self.f.numerator, self.f.denominator)
def verify(self, m, sig):
s1, s2 = sig
h = bytes_to_long(sha256(m.to_bytes(self.nb, "big")).digest())
a, b = m, h
r = self.encrypt(s1)
c = self.encrypt(s2)
return fraction_mod(self.magic((a, b, c)), self.f.denominator) == r
@staticmethod
def magic(ar):
a, b, c = ar
return Fraction(a, b) + Fraction(b, c) + Fraction(c, a)
class PrivateKey(PublicKey):
def __init__(self, priv, pub):
super().__init__(pub)
if self.magic(priv) != self.f:
raise ValueError("Invalid key pair")
self.priv = priv
self.d = pow(self.f.numerator, -1, prod([x - 1 for x in priv]))
def decrypt(self, c):
return pow(c, self.d, self.f.denominator)
def sign(self, m):
h = bytes_to_long(sha256(m.to_bytes(self.nb, "big")).digest())
a, b = m, h
c = randbelow(1 << self.nb)
r = fraction_mod(self.magic((a, b, c)), self.f.denominator)
s1 = self.decrypt(r)
s2 = self.decrypt(c)
return s1, s2
@staticmethod
def generate(nbits):
while True:
try:
priv = tuple([getPrime(nbits) for _ in range(3)])
pub = derive_public_key(priv)
return PrivateKey(priv, pub)
except ValueError:
pass
def main():
assert len(FLAG) <= 64
m = bytes_to_long(FLAG)
key = PrivateKey.generate(1024)
data = f"pub = {key.pub}\n"
# make sure it really works
enc = key.encrypt(m)
assert key.decrypt(enc) == m
sig = key.sign(m)
assert key.verify(m, sig)
# mixing them :)
mix = [sig[0] + sig[1], sig[0] - sig[1]]
mix = [key.encrypt(x) for x in mix]
data += f"mix = {mix}"
with open("output.txt", "w") as f:
f.write(data)
if __name__ == "__main__":
main()
And we have the result in output.txt:
pub = (-679149827688896546432684514781159016843208241259733038415608446794483893865137935606244643075224614588255514670703135466975466970913232919448971056463765967267932205245723609028669700790327888053737513173004906874791948794706164874163000233242663467112356684022940655151358257782991132383407917101800634477163967250047209128395271227452766580073122831277123102243705154267181506512402418039719173720827696442606604970528063168565779813124052546633103006687964589521475168208905582555230534709754318532234948569155566965251016769141273474050547777208930826949494111933369822606247918218189742785296490363879808413854798453415486721083351760540440727104905848109665720749305468099771944894375713469720303756620101486771358570935901473647573434771209918671576552610105681029288935780171889489032033021940200657122568137703155744190258342713712412791279147013204380608939099412456303268575877533613186703629403608506029153274825614231950222036769768440858686468414798013424323765200986740221652787739657510451377763752151261173701557996570807100005672113902309356835881522886670894124683065117547063607171455016275575226133973000898546626428525316423640294588059582425678225307973026140509236726222895277593502658123536454581741258241350319709620218946214665277722917625163484143287737560990362641167985157948128093478633332215687808673326510025966928820082371826010204772434810834908522239370003521927141674940923107924718589020116481655436804371698576313448620651274568714018039959665606305466508336068792512300330447079049391998121903628542300433666064229921580215835067999800174889123776199641564914760737600821953293714498453721075798275047009255942697608822458887368884228615671991262750899422262693397993810261279502497616420217291365257434988696383465213630804193810674969275499135895349396517300341694326130217329147937575188985044945549854453507141533817669145401648967346307076924815850188448842044898686784928539015228772201838211426957234107261809629639488140342429501192224120877838900600824055655563831019772958581350347081393942024086716044621385448218128870528968546874044728000006962970494893355352673283507468842799994294656025864551101856509528014985899203160260433154506345617010883888392862375738238905192516684056280710225432696655387350661830299769543107006018477779636761481812001885777307338070488998064732654317341303970152707374877928275562177058710127753099319277046999346991319018270073503529254012239006330090621492580837121246383935, -62076393535220713230211372773016154819776973272085279510651810925567779949353129946722665324346680014266486318715153201960740792449256110092242298637141869182191301801348471698842750492673269805386405258903922775271516275959471007270470783319809938344980989030858451767810558937769006054050097442784355926821230070379192555314422288851726919132047206078443630648828611342794053179031715333055698280449463491394083273880477510623203232349139229518535496279365263598613132079698328994631219260929529014155663831397189773051194410051588749692352737665469175569662944453505412436038259868251153299961933349760369897472364513246615362132669886696823052680175413762753451532554603896709930434997447861155715656069046149639262746319959746238179869888630675350046188185867904504017641487194302334327723755607524433514488406681046596968802669158589535873655500657057147028422069215178280598799698023523842357762349312690981167196137904038634376059163646848305423446194854985523208266633269733804799399607579721802215740994923964998077749276376011664190442983045021233328860583431325491398740404717916957583624416525249155775990424790364048060223994351310834002052812950138181225201366866314173709814344726454058400929651246654127831150461139153521780070432541564467256212600334416658092578286615407601260752708323965051595729545763555521745630970189873094019504197470499857463907805936270010647572788276449685684281797985033841971693243345694540270555091524839897049609610694927649006414175285808616559721550306026476105719357460921592355959150692653059587214522745084239909633381558412919917765258331958067109432311999676460754436818201240023311791169802096388297862219517745888298152485206376817292783209092101414045488990410966964411575840592166475524123368782667715013887175556663844953274929494297381264202051980047425186510319292378252632808136510156368067796082090881873863176619957188519245758562409606283750005034060349233190765189422774601110274372976258448740486162640303554541285690390642874100570657406690134508272681549727638076837266298852607372446728482637226932907561200761597573567176950238238261414346592107964949875193908993522612254840698757416962124520050724327233377985303460697496676181895430294259015494830416056429816116680627673230428123227550005209799526871524994673920145445281764352654447538983391735348123813851971146216997750793741632897137346289689048299843427272709114665386119324590006011517253390435055796456069897547662246663469050, 7830486145829508377558227408290134666403414818680891369176645894657730719560462345413647777035691365258303368067215176543275998927964954949936712360465415742305180023074796925974228987920346807337046972890048193675380148777690313974213732587383856306544481992804522271933234142582135631837143021763752036371144162337258022513117655962693146611295672219977744995976478481618309460588961678471875936477345228279163041888319063508894362501867902730894177063341454634424454782062634032617628985824505983759212857299828749995752235758280573881085074326788874659358083585790319249788052723728978677280818302159890013608215097544022503686764809254320162354127388898310054146477537454655331114752144580956313131601466170634129721047436217501010686515461442226299103956329529388095001070391385189826814864746360320333918929686149324974844514612649731799514398645742580625276435924292653289878873850265379360271050603859206438004883855432886650553014115919828422317294957226985270768975519537120458232477529774162488973095316791366021139626153997771391194348622350835846276300080551743631687665470499546808409919692234446116541139972549724015591941496221132694347053824568526998941915494190313922421141792712177850635304804853629529860738709134170021521102700328604628927875567294032063066171031633521264813050524393039049915547228949811888603458908961700972119089383547482638110428947454915597289453149684921808588155575892869551719408017163519505152564311034805403584244791464453674297092713220925531618514351406361895037695504970845118751396728421079695580995084470838685511076186640881628743480208128654755986540162228797182203097429878571055580982419910698271318560371375725624590383889293031827343721601921283218257563981664825233636121202430668321472633600201081855377049584327600961474706457007803948936824801776548939412019028877381656854352042881659133167174502453362966793813997989646037370005971535903722675701268453950616768210577721799262016472978512795971976360288455246627122308235526400041892494207712587655624310348101802715615388185255043745377008056152447575197765696754537890671347192620664952431667401070828663411172784617836559669320812607668877073449814900939924918858434664371233944816438544081459935797541138873496291375791704149531348074915907756350500006241339201669154574473335111528050064627331874217370202929428747238792910498913366471880111057711710182734506773946328772476941505432386559666283038340899500750365525879310436221464632932)
mix = [320097670159304209872309549471930993417143388077612479497520462342663934977666619462544724222917378443968580805422580825361629081490271425796180005007150747981294833573665302687843134857904098195466433204039058015530152552325684827139190765614362244643766711802006240778166882116884363374725459551909065104305033828828854239454604753713577854447476580313858442898211797176449603725270483947895282965175447381948570185109212852155846189091780576621552251326144055737198080348963003230356855332599698331598994549981281612662608348841085666739363070407550100107611043508427316142601784200258788876751333421411315222696828075445887895455540798110282831853710380354729703219505108629359197051336831375142595785378662848001960222878291497005997865756885831339332471275732796885611507451753622271015336628712225776167393560183733898486530850953580390452793438185371865569655507768389802668508433717577899938841236692983646823027361, 349362680724100439001784418744128033820777004106762219940030797663423035126842789961301765825984790980690057949860749399355278228450692377224412215897507215190015109832483673402204604232784701242900565985678019980900605960003183528535025133581067044874804468687010880739758605406077761031350401248992459970793003097988643424534679899913404629630391199540164124586883472387639995010304310446530364782969667797609685774685940403053235307671556459857310584515167273597080744839887558160920716970032955099943334650018552259294137522684003806871855045036984303040298988654317845297423677227040203951111165862748444474516781528350286768742283071330157900311167729282004019891879048809487509974878771126244472706852271120669147203065908414503160273025384004067262219422586521719641783916408458322110103608436662590492232330298616191719127365835397875038644290248233827642595125378514596518087399154247594983235918109876187387712452]
Source code analysis
The server generates 3 prime numbers $p$, $q$ and $r$, which form the private key.
Public key generation
There is an unknown function called derive_public_key that is used to get a public key from the private one. The comment about Kerckhoff’s principle is relevant here because this approach is security through obscurity, which is not always secure. Kerckhoff’s principle states that security must rely on the keys, rather than the algorithms.
The result of derive_public_key is a list of 3 numbers, given to us.
These public-key numbers are transformed with magic:
$$ \mathrm{magic}(a, b, c) = \frac{a}{b} + \frac{b}{c} + \frac{c}{a} = \frac{a^2 c + b^2 a + c^2 b}{abc} $$
def magic(ar):
a, b, c = ar
return Fraction(a, b) + Fraction(b, c) + Fraction(c, a)
We can apply magic to the 3 public-key numbers and get a fraction $f$ with numerator $N$ and denominator $D$. These two values are used in the rest of the script.
Encryption and decryption
In order to encrypt a message, the server takes the message $m$ in decimal format and computes $\mathrm{ct}$:
$$ \mathrm{ct} = m^N \mod{D} $$
def encrypt(self, m):
return pow(m, self.f.numerator, self.f.denominator)
In order to decrypt, the server calculates
$$ m = \mathrm{ct}^d \mod{D} \qquad d = N^{-1} \mod{(p - 1) (q - 1) (r - 1)} $$
self.d = pow(self.f.numerator, -1, prod([x - 1 for x in priv]))
def decrypt(self, c):
return pow(c, self.d, self.f.denominator)
The code also shows us that both functions work as expected, and they are inverses:
# make sure it really works
enc = key.encrypt(m)
assert key.decrypt(enc) == m
sig = key.sign(m)
assert key.verify(m, sig)
Signature and verification process
As can be seen, there are also signature and verification routines that work as expected.
In order to sign, the server takes the message $m$, its SHA256 hash $h$ and a random value $c$ to compute $\mathrm{magic}(m, h, c) = \frac{A}{B}$.
The values $A$ and $B$ are used to compute $R = A \cdot B^{-1} \mod{D}$ with fraction_mod:
def fraction_mod(f, n):
return f.numerator * pow(f.denominator, -1, n) % n
The signature is just a pair of values:
$$ (s_1, s_2) = (R^d, c^d) \mod{D} $$
def sign(self, m):
h = bytes_to_long(sha256(m.to_bytes(self.nb, "big")).digest())
a, b = m, h
c = randbelow(1 << self.nb)
r = fraction_mod(self.magic((a, b, c)), self.f.denominator)
s1 = self.decrypt(r)
s2 = self.decrypt(c)
return s1, s2
The verification function takes the message and the values $(s_1, s_2)$ to perform almost the same operations. First, it finds $R = s_1^N \mod{D}$ and $c = s_2^N \mod{D}$, then it compares it with the expected value of $R$ by using $m$, $h$ and $c$:
def verify(self, m, sig):
s1, s2 = sig
h = bytes_to_long(sha256(m.to_bytes(self.nb, "big")).digest())
a, b = m, h
r = self.encrypt(s1)
c = self.encrypt(s2)
return fraction_mod(self.magic((a, b, c)), self.f.denominator) == r
We are given some values that are related to the signature of the flag. Specifically, we have $(s_1 + s_2)^N \mod{D}$ and $(s_1 - s_2)^N \mod{D}$, where $(s_1, s_2)$ is the signature of the flag:
# mixing them :)
mix = [sig[0] + sig[1], sig[0] - sig[1]]
mix = [key.encrypt(x) for x in mix]
data += f"mix = {mix}"
Solution
Since we know that encrypt and decrypt are inverse functions and that work well, comparing with a classic RSA, we have $N$ as the public exponent and $D$ as the public modulus. Hence, in order to decrypt we need to find the private exponent, which needs to be $d = N^{-1} \mod{\phi(D)}$. The server actually computes $d = N^{-1} \mod{(p - 1) (q - 1) (r - 1)}$. This fact determines that $\phi(D) = (p - 1) (q - 1) (r - 1)$ and therefore $D = pqr$.
On the other hand, the static method generate_key of PrivateKey generates the private key and derives the public one. Then, it returns an instance of PrivateKey:
@staticmethod
def generate(nbits):
while True:
try:
priv = tuple([getPrime(nbits) for _ in range(3)])
pub = derive_public_key(priv)
return PrivateKey(priv, pub)
except ValueError:
pass
The constructor does the following:
class PrivateKey(PublicKey):
def __init__(self, priv, pub):
super().__init__(pub)
if self.magic(priv) != self.f:
raise ValueError("Invalid key pair")
self.priv = priv
self.d = pow(self.f.numerator, -1, prod([x - 1 for x in priv]))
Class PrivateKey extends from PublicKey, and its constructor is called with the public key:
class PublicKey:
def __init__(self, pub):
self.pub = pub
self.f = self.magic(pub)
self.nb = (self.f.denominator.bit_length() + 7) // 8
Here, the value of the fraction f is computed, which holds numerator $N$ and denominator $D$.
But look at this ckeck:
if self.magic(priv) != self.f:
raise ValueError("Invalid key pair")
This fact tells us that $N$ and $D$, which are the output of magic and the public key (let’s say $P$, $Q$, $R$) must satisfy that
$$ f = \mathrm{magic}(P, Q, R) = \frac{P}{Q} + \frac{Q}{R} + \frac{R}{Q} = \frac{P^2 R + Q^2 P + R^2 Q}{PQR} = \frac{N}{D} $$
But remember that $D = pqr$, which means that $PQR = k \cdot pqr$ for some $k \in \mathbb{Z}$. On the other hand,
$$ \mathrm{magic}(p, q, r) = \frac{p^2 r + q^2 p + r^2 q}{pqr} = \frac{N}{D} $$
As a result, we have that
$$ \begin{cases} N = p^2 r + q^2 p + r^2 q \\ D = pqr \end{cases} $$
While debugging in Python, I found that
$$ \begin{cases} PQR \equiv 0 \pmod{D} \\ PQR \equiv 0 \pmod{D^2} \\ PQR \not\equiv 0 \pmod{D^3} \end{cases} $$
Also, $P, Q, R \not\equiv 0 \pmod{D}$, but
$$ \begin{cases} PQ \equiv 0 \pmod{D} \\ QR \equiv 0 \pmod{D} \\ RP \equiv 0 \pmod{D} \end{cases} \qquad \begin{cases} PQ \not\equiv 0 \pmod{D^2} \\ QR \not\equiv 0 \pmod{D^2} \\ RP \not\equiv 0 \pmod{D^2} \end{cases} $$
This means that $PQR$ is a multiple of $(pqr)^2$, but in each pair $PQ$, $QR$, $RP$, we can only factor $(pqr)$. After some tries, we can come up with the following structure:
$$ P = \alpha \cdot p q \qquad Q = \beta \cdot q r \qquad R = \gamma \cdot r p $$
for some integers $\alpha$ $\beta$ and $\gamma$. The above relations work since
$$ \begin{cases} PQR = \alpha\beta\gamma \cdot p^2 q^2 r^2 \equiv 0 \pmod{D^2} \\ PQ = \alpha\beta \cdot p q^2 r \equiv 0 \pmod{D} \\ QR = \beta\gamma \cdot p q r^2 \equiv 0 \pmod{D} \\ RP = \gamma\alpha \cdot p^2 q r \equiv 0 \pmod{D} \end{cases} $$
Therefore, we have
$$ \begin{cases} \gcd{(Q, D)} = \gcd{(\beta \cdot q r, p q r)} = q r \\ \gcd{(R, D)} = \gcd{(\gamma \cdot r p, p q r)} = p r \end{cases} $$
And so, $r = \gcd{(\gcd{(Q, D)}, \gcd{(R, D)})}$. Trivially, we find $p$ and $q$.
Having $p$, $q$ and $r$ we can compute $d = N^{-1} \mod{\phi(D)}$ and decrypt the mix we have. Moreover, we can easily find $s_1$ and $s_2$. Remember the values of $s_1$ and $s_2$:
$$ s_1 = R^d \mod{D} \qquad s_2 = c^d \mod{D} $$
At this point, we can have the signatures $R$ and $c$, and we can check that their bit lengths are correct. Notice that $R = A \cdot B^{-1} \mod{D}$, where
$$ \frac{A}{B} = \mathrm{magic}(m, h, c) = \frac{m}{h} + \frac{h}{c} + \frac{c}{m} = \frac{m^2 c + m h^2 + h c^2}{m h c} $$
Here, we might need to apply Coppersmith method or a lattice-based technique, since the flag has at most 64 bytes (512 bits) and the SHA256 hash is a 256-bit integer, whereas $D$ is around 3072 bits.
Since we know $c$, we only need to find $m$ and $h$, which can be assumed to be short. We have
$$ \begin{align*} R & = A \cdot B^{-1} \mod{D} \\ & = (m^2 c + m h^2 + h c^2) \cdot (m h c)^{-1} \mod{D} \\ \end{align*} $$
Let’s get rid of inverses multiplying by $(m h c)$:
$$ (m h c) R = m^2 c + m h^2 + h c^2 \mod{D} $$
As a result, we can define a polynomial:
$$ P(x, y) = c \, x^2 + x y^2 + c^2 \, y - c R \, x y \pmod{D} $$
Where $P(m, h) \equiv 0 \pmod{D}$. Since $m$ and $h$ are short, we can try to find small roots of this bivariate polynomial using Coppersmith method.
SageMath implementation
First of all, we take the values from output.txt and find $N$ and $D$:
with open('output.txt') as fp:
pub = literal_eval(fp.readline().split(' = ')[1])
mix = literal_eval(fp.readline().split(' = ')[1])
P, Q, R = pub
f = magic(pub)
N, D = f.numerator, f.denominator
nb = (f.denominator.bit_length() + 7) // 8
Next, we find the private key $p$, $q$, $r$ and assert that the values are correct:
r = gcd(gcd(Q, D), gcd(R, D))
p = gcd(Q, D) // r
q = gcd(R, D) // r
assert is_prime(p) and int(p).bit_length() <= 1024
assert is_prime(q) and int(q).bit_length() <= 1024
assert is_prime(r) and int(r).bit_length() <= 1024
assert p^2 * r + q^2 * p + r^2 * q == N
assert p * q * r == D
Once we have the private key, we can decrypt the mix, find the signature $(s_1, s_2)$ and then compute $R$ and $c$. The length of $c$ is also verified:
d = pow(N, -1, (p - 1) * (q - 1) * (r - 1))
s1_p_s2 = pow(mix[0], d, D)
s1_m_s2 = pow(mix[1], d, D)
s1 = (s1_p_s2 + s1_m_s2) * pow(2, -1, D) % D
s2 = (s1_p_s2 - s1_m_s2) * pow(2, -1, D) % D
R = pow(s1, N, D)
c = pow(s2, N, D)
assert c.bit_length() <= nb
Finally, we need to define the bivariate polynomial and use Coppersmith method to find $m$ and $h$. A nice implementation of multivariate Coppersmith method is made by defund. We can download the script and load it into SageMath to use the small_roots function. Once found a solution, we can confirm that the SHA256 hash matches and then we simply print out the flag:
load('coppersmith.sage')
m, h = PolynomialRing(Zmod(D), 'm, h').gens()
PP = m^2 * c + m * h^2 + h * c^2 - c * m * h * R
roots = small_roots(PP, bounds=(2 ** 512, 2 ** 256))
for root in roots:
if root != (0, 0):
m, h = root
assert int(sha256(int(m).to_bytes(nb, 'big')).hexdigest(), 16) == h
print(bytes.fromhex(hex(m)[2:]).decode())
Flag
And here we have the flag:
$ sage solve.sage
HTB{4_s3cur3_crypt0syst3m_sh0u1d_n0t_c0nt41n_s3cr3t_c0mp0n3nts!}
The full script can be found in here: solve.sage.