Zombie Rolled
13 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, n):
self.pub = pub
self.f = self.magic(pub)
self.n = n
self.nb = (self.n.bit_length() + 7) // 8
def encrypt(self, m):
return pow(m, self.f.numerator, self.n)
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.n) == r
@staticmethod
def magic(ar):
a, b, c = ar
return Fraction(a+b, b+c) + Fraction(b+c, a+c) + Fraction(a+c, a+b)
class PrivateKey(PublicKey):
def __init__(self, priv, pub, n):
super().__init__(pub, n)
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.n)
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.n)
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)
n = prod(priv)
return PrivateKey(priv, pub, n)
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 = (-210460004064658545149323270027125585053769531535575407350548992758255183408956300581776562753733749147991850793425366295331667362050138873330003194124140770281180202423447393078536478578946868914766383656089736270769788751224790405249013826635560803115098339073827135185826800939385978982619079483041610504047360527984966942969476938139600034002723364891052748171817924407580597412822624685840388733150562475191261733959754302870066881457439368383797860179354173905065196438650796693994506662218070106433605252371699975224015082241530805008715676767375587161483265765928867425947585319697598716342929731654599546786312158055192372546719883973931468047435521481784391209900070757353943121542277996362196911350140936374803527008606311714911826664001861344148925432456604114027567871907313538504631322730338913938316266631382676518400709132275709208557215429334792606216034973795842808506218623336928645873355528451647090676781751760050107610570392509919226018971445825324823288871147536975132689880688845587543605955579179730900403874103993879894103493722630349071444752690194369435903192722227882789473747568915937633017628653003841969130850224276467088238242967030703252034634998838450149987830988170632158593090342822378422506206718162866788489383954424520400309687446396922689894702349422494539870822982165352296752757838249758847248954901520084148063833208536651742341062164244017879477206939664935238944946527073936644149311943102740610769083279706502997296755709766586056165002192995150546453376411375946735666151030041089735143874012598684485919998838606432520697668756217572519576983009160506152352207045277432241713427473866239668163675448604724328457217539264682046367317013329398485410857195615049823175203925245252476463981844247115175989610533376228024079063115447932497123000468533406318130678663522920114992487564435224227779829370167357854542102259851547210728204680236254781690752101737776286349310317871408511173261016327829488783128124238185622581734373566268247117224296866158777566843574447075623007306270893524221590605260716241323455401522724392760024858027770598653347708025277948266108534992117950744942247538387691821093590335831543492934619905845153938941387523633891920168775933273356246150913687287580005738308853842778146772472161206052698833816938811736333968533167868483246719752201140628448572481749697124587956816178331696810978096173224327142109508407599863959977452073108504801967731216012715964184501653322161959765640703181, 48092167959932577089665706598220165781675771390752790227245377485859485947881571546031811781823531847290145883570391381336778582646376615617889209041048861514625245618391721904143628115253008909601418469608473423398811492009174166243685961257740358835633188280095876080795489899534519571369848752371797579799946381022948625049501467395264530262180573337083241907562614192878574144739061761541532656064621319804504351482986554734034210707836134653811450482725467108642223588121505067372994985292445520001174499519401437153507541826140463290765362583187446831892904451524623790721268161001505010481230620204674812222356870636305377968155481717890541702589197283597439323265314022562812242179576784749209668144438109469457078988559669837452513366063950036113075144671910134836382726061473126596550646614146078443174581105422846476318083629216862717532462628808127510223310132293885710468097698984259717619848649531077210788062624065543549381024587940656696251443503084172682617980324949080794778369101476911695987538917170783888585139170905742797701946636143246389557327737817504828854418238552918710493680241317067229833001240440514379022640617590974019364950318928389827811099478122002451161835713755344612988172028689418803025998639828426011191461104344294996539829176323901970637792252523712675333669643021955732902568937344239074357264968149516161281055403110376979324305028602766172174883302154360855869543967352800198912263276004643959465449518606967096622877028244289928766147905890748205869026637227939534515251009369887727237698461495359469851241721149456159709360150623548149581359231657983430999420794121959127958134018098368856357393108801463187546862737776427868272569433029692425993859830526727241723993224189921729311066393181076960370979893551066586057187601990674487017141841203651494165412078824016216754534826975530662024505444138560368190331434252079819695526471547437779865513089729452268860789068729093350931932611352070995981169035623937574282154283574443761574061931582345766796531904501680567328867512168123101442032309382206953539164445916851695172111176960556792392084525760682929517743118401815662873213111364254472092662871664405216936355120399440412953512383116635297774548790160970019719792538575510949649801729271389813372049233273940011935172643734336578398019766131368283650306004979181140230735068877461269713653548413632936784854356608036728978669525070594086171522597576796441820273981883356320986465325910023468305252933853, 295680237318969834583481350558045576069593397434250114268436392515105169191935289027375497778723372682513840734207932618190330189517739831911523847702330549481897559170495540721652247420337613272507142470605966203844911067854272669874935602731760616153213014890133142801239192079947159594861361601316909850841003469924342012486894936276047149241609037499591917591895130811114625418446330611492030654343430138478099676751910050330177587495855685857580069837873749334025367386942484569200376276585839574077306764891344426845642147405113306157668890178540851789817824614402737945630733737882024042823084893907616969914474832694719037443444818465434680322725745534751292520813842900322357596056857411573205554845465657322776026906939671854071190622648044326841578658423897845211643831096140970428604677609426173111469986019593063904916756246862724809757031532573248196113934118167511345376202958349994847533599803302816875080995188540954333242472866288368356433000012641533588227196752255533968884901760351526179286226813116146805328519695058833653483175617155524796170315815030198082197252295143664620853012864343932707621691692301666805387191857665541247527691509939498006149235577928744988285274380407878815137597089985965284441453525606984850948169652950770654611407196062991198720683081845399004437598542824766225913256140462688017991149014643840857737669793609045002562156298085352771410764034902539507427824936008812792316353855076217474511027376324964324258381503327600240847068580184327069988899673860991472703503982213831152492161359690522185944809136541502229303028310970512499852428336274934693121000245417851454895814281309411653690987796653842598705383750863545849146632339464355340312413889619057550789920777741216497799023886731790428675508850191436528845210345233154209449815183440739968081125328477883943958120844772517543814408943265674355655325470607676318683037563323920211491222704859819893440021032032779436664971290722627579527689013107226911966671185548413889504849802792656272827006947483605480044492484117853415676118939728854488844585782571371102778347974774155341887561550811966344521652867740827641565526459587452560357733493573548740842552438280369419404671314951756797396105930460945603675920681705201005229355597434166687085158453441941920742876590640482018781974161883195654719122551742622613429276209109558416257393084810842677543509590116448722500988340213756485998183685287230874073206039147869000598425185218952661827499422115)
mix = [2757730114159077389149698432635923981837301729613836384821565970385413527287691303546550071418389460869153265388793288168218992857076782393276221793088140996712795952988234917553350760904749861274926130040479200999429727248629683885916287922239431512820824780777954623772876620507269441914094023673807162641852804725138549956405696699115992461751212100433365705709888998783961544036761746518152663764468503408338480433435667952025380728443297958328995861002595831477329613145876325119604318873183779731991800100149300453012374526367862223973666642160703278246134349210011935898797845233856417363897814513913560313373938031644170526217562189440749278611074828271277104045968930855308000341736235120452258250999462234119531102229181591002350278544442729901864691776115513351943684918165600813284119872912267330400545353503839148657803170834314260914120288293705317513662212847101683300574727947089599033219552668719815029040408, 504994496960270139574946670894069299431207241073364481107436674373406781743273696715057719201622004604281774275828786758698939566785199569446395919976297320011795400301194061227784647070778305874870978021644569959853017603794627523140118519605135041612547135975756808050442548006245570578440457971432120788018096254980159404343207191110068743936220169743056476599906402449120877843887111307810902465612716393076554531289608909139586938005968169706464844575482719379839259559227740024158017349642299710203478526165482299268838854867695568738299929667468342278771679001361343570395883313247212144180543867644990780207723987043462219435393004802347242735452985011336597806947860484258115007949848766287513407339843432999716727634381116327557264348049187312387308303580287236597542911203816391268299325974510924298072270564103660391793686666200192144475147526288929033464511058363590578958753909920404740300100217899387268556668]
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:
$$ \begin{align} \mathrm{magic}(a, b, c) & = \frac{a + b}{b + c} + \frac{b + c}{c + a} + \frac{c + a}{a + b} = \\ \\ & = \frac{(a + b)^2 (c + a) + (b + c)^2 (a + b) + (c + a)^2 (b + c)}{(a + b) (b + c) (c + a)} \end{align} $$
def magic(ar):
a, b, c = ar
return Fraction(a+b, b+c) + Fraction(b+c, a+c) + Fraction(a+c, a+b)
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{n} $$
def encrypt(self, m):
return pow(m, self.f.numerator, self.n)
Where $n = p \cdot q \cdot r$, the product of the private prime numbers.
In order to decrypt, the server calculates
$$ m = \mathrm{ct}^d \mod{n} \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.n)
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{n}$ 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{n} $$
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.n)
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{n}$ and $c = s_2^N \mod{n}$, 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.n) == r
We are given some values that are related to the signature of the flag. Specifically, we have $(s_1 + s_2)^N \mod{n}$ and $(s_1 - s_2)^N \mod{n}$, 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 $n = p \cdot q \cdot r$ 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(n)}$, where $\phi(n) = (p - 1) (q - 1) (r - 1)$.
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)
n = prod(priv)
return PrivateKey(priv, pub, n)
except ValueError:
pass
The constructor does the following:
class PrivateKey(PublicKey):
def __init__(self, priv, pub, n):
super().__init__(pub, n)
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, n):
self.pub = pub
self.f = self.magic(pub)
self.n = n
self.nb = (self.n.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
$$ \begin{align} f = \mathrm{magic}(P, Q, R) = \frac{P + Q}{Q + R} + \frac{Q + R}{R + P} + \frac{R + P}{Q + R} = \frac{N}{D} \end{align} $$
So, we know that
$$ \frac{N}{D} = \frac{p + q}{q + r} + \frac{q + r}{r + p} + \frac{r + p}{q + r} = \frac{P + Q}{Q + R} + \frac{Q + R}{R + P} + \frac{R + P}{Q + R} $$
Rearranging the equations, we get that:
$$ \begin{cases} D\big((p + q)^2 (r + p) + (q + r)^2 (p + q) + (r + p)^2 (q + r)\big) = \\ \qquad \qquad = N (p + q) (q + r) (r + p) \\ \\ D\big((P + Q)^2 (R + P) + (Q + R)^2 (P + Q) + (R + P)^2 (Q + R)\big) = \\ \qquad \qquad = N (P + Q) (Q + R) (R + P) \end{cases} $$
Cubic diophantine equation
As a result, we have that both $(p, q, r)$ and $(P, Q, R)$ are solutions to this equation:
$$ D \big((x + y)^2 (z + x) + (y + z)^2 (x + y) + (z + x)^2 (y + z)\big) = N (x + y) (y + z) (z + x) $$
The above is a diophantine equation, because we are working with integer coefficients and we are interested in integer solutions. Usually, diophantine equations have more than one solution, so we need to find a way to solve the above to find $(p, q, r)$.
While reading about cubic diophantine equations, I found that if we interpret the above equation as a curve and its genus equals $1$, then it can be expressed as an elliptic curve (more information at math.stackexchange.com). Notice that we already have a rational point $(P, Q, R)$, which is a point in the cubic curve, so we can have a point in the elliptic curve using the conversion from the cubic equation to the elliptic curve.
In fact, rational points on curves with genus equal to $1$ form an abelian group (see Wikipedia). As a result, if we have a point $G$ on the elliptic curve, then any multiple of $G$ is also a rational point. Therefore, we can use the inverse mapping to get another solution to the cubic diophantine equation.
In SageMath, we can test it:
sage: P, Q, R = map(ZZ, pub)
sage: f = (P + Q) / (Q + R) + (Q + R) / (R + P) + (R + P) / (P + Q)
sage: x, y, z = PolynomialRing(QQ, 'x, y, z').gens()
sage: eq = (x + y) / (y + z) + (y + z) / (z + x) + (z + x) / (x + y) - f
sage: eq.subs({x: P, y: Q, z: R})
0
sage: Curve(eq.numerator()).genus()
1
So, we can now find the transformation function from the cubic curve (the numerator of the fraction) to the elliptic curve and its inverse:
sage: F = EllipticCurve_from_cubic(eq.numerator(), [1, -1, -1])
sage: Fi = F.inverse()
sage: G = F((P, Q, R))
Notice that SageMath requires a projection point. We have used $(1, -1, -1)$ because it lies on the curve:
$$ D \big((1 - 1)^2 (-1 + 1) + (-1 - 1)^2 (1 - 1) + (-1 + 1)^2 (-1 - 1)\big) = 0 $$
sage: eq.numerator().subs({x: 1, y: -1, z: -1})
0
Now, for any multiple of $G$ on the elliptic curve, we can find a solution to the cubic equation:
sage: a, b, c = Fi(2 * G)
sage: eq.subs({x: a, y: b, z: c})
0
sage: a, b, c = Fi(3 * G)
sage: eq.subs({x: a, y: b, z: c})
0
However, these solutions are huge:
sage: int(a.numerator()).bit_length()
73531
sage: int(a.denominator()).bit_length()
73533
As a result, we can think that $(p, q, r)$ must be mapped to some point $X$ on the elliptic curve such that $X = k \cdot G$ for a small $k$. In SageMath, we can use division_points to find such points if they exist:
sage: G.division_points(2)
[(-11216861528612357904709318323797825103611635554286577958475334550348151151315666856299468989376617096553244928065545313371458796206429540872813808955590930758338036843726243575048631869172869505334509221892197553131605119378635734438105878806588165687881032792115400021951252530130324532853758986296001408426368/144240654022460844172429641403725503935202209257643993096916929585756576585331767464119928794157332435912040969304785834742518075172676019046361048029554928484679994496146947766370303707634565325687643349850072021159085718920701209043206321178849924310301589611357140710066912578177437285803650655446529748287 : 13025263855694143849316460018134611063424114376924022869406842256509079187787970112740648354982930197289845019172843431795213791698268869552344636095321153037986829279656291314625645228516379214043756425299457441478454187446943681064922024219626948616945758958875179368572245547947707980817291490264173834656439383434474180289378565030173813558603834784914700901577031846579404068663972959222235284821658808277896926190730311909004974087764790044159213759404500513676018802196526804380853808127831330590164708887757994965342003758741891267444444533821773329653432617730860726098561837718556479371683384877446819819819008/20805366272827249706151170011055856031008300931172142563300452624354646479834064436244883908378307204303812733579985772386796413559281607979640796692496339119875121316310874909773572506782891631848197068090507105923516994542873369241645859808271821761596570861029848560655988120900215283281679689432956499158522032256993570482216817404857073042336432977419672853714663687843003938138924573855794226540958071093301775135873274494980760065542480586771434070965595924766036340903190019888152543154496669362391515363862128566934094733923177055027869577281761277952260620120681427190808286187194236165054172075251579434369 : 1)]
sage: G.division_points(3)
[]
sage: G.division_points(4)
[]
sage: G.division_points(5)
[]
So, we must have $X = 2 \cdot G$:
sage: X = G.division_points(2)[0]
sage: a, b, c = Fi(X)
sage: eq.subs({x: a, y: b, z: c})
0
sage: type(a)
<class 'sage.rings.rational.Rational'>
Alright, but although we have another solution to the cubic equation, a, b and c are rational numbers. We must find integer solutions. For this, we can simply find a common denominator and multiply each rational number by that:
sage: cd = lcm(lcm(a.denominator(), b.denominator()), c.denominator())
sage: a, b, c = ZZ(a * cd), ZZ(b * cd), ZZ(c * cd)
sage: eq.subs({x: a, y: b, z: c})
0
The values are now integers, and they are solutions to the cubic equation. But the important thing is that we have found $p$, $q$ and $r$:
sage: int(a).bit_length()
1024
sage: is_prime(a)
True
sage: int(b).bit_length()
1024
sage: is_prime(b)
True
sage: int(c).bit_length()
1024
sage: is_prime(c)
True
sage: p, q, r = a, b, c
RSA decryption
Once we have $p$, $q$ and $r$ we can compute $d = N^{-1} \mod{\phi(n)}$ and decrypt the mix we have. Moreover, we can easily find $s_1$ and $s_2$:
$$ \begin{cases} s_p = s_1 + s_2 \mod{n} \\ s_m = s_1 - s_2 \mod{n} \end{cases} \iff \begin{cases} s_1 = 2^{-1} \cdot (s_p + s_m) \mod{n} \\ s_2 = 2^{-1} \cdot (s_p - s_m) \mod{n} \end{cases} $$
Remember the values of $s_1$ and $s_2$:
$$ s_1 = R^d \mod{n} \qquad s_2 = c^d \mod{n} $$
At this point, we can have the signatures $R$ and $c$, and we can check that their bit lengths are correct:
sage: n = p * q * r
sage: N = f.numerator()
sage:
sage: nb = (int(n).bit_length() + 7) // 8
sage:
sage: d = pow(N, -1, (p - 1) * (q - 1) * (r - 1))
sage:
sage: sp = pow(mix[0], d, n)
sage: sm = pow(mix[1], d, n)
sage:
sage: s1 = (sp + sm) * pow(2, -1, n) % n
sage: s2 = (sp - sm) * pow(2, -1, n) % n
sage:
sage: R = pow(s1, N, n)
sage: c = pow(s2, N, n)
sage: assert c.bit_length() <= nb
Notice that $R = A \cdot B^{-1} \mod{n}$, where
$$ \frac{A}{B} = \mathrm{magic}(m, h, c) = \frac{m + h}{h + c} + \frac{h + c}{c + m} + \frac{c + m}{m + h} $$
LLL lattice reduction
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 $n$ is around 3072 bits.
However, instead of finding $m$ and $h$, let’s find $A$ and $B$. We know that both $A$ and $B$ are short compared to $n$, and it follows that
$$ R = A \cdot B^{-1} \mod{n} \iff A = R \cdot B \mod{n} \iff A = R \cdot B - k \, n $$
As a result, we can use the following lattice basis:
$$ L = \begin{pmatrix} R & n \\ 1 & 0 \end{pmatrix} $$
So that we can use LLL to find a short vector $(A, B)$, which belongs to the lattice because
$$ \begin{pmatrix} R & n \\ 1 & 0 \end{pmatrix} \cdot \begin{pmatrix} B \\ -k \end{pmatrix} = \begin{pmatrix} A \\ B \end{pmatrix} $$
sage: A, B = Matrix(ZZ, [[R, n], [1, 0]]).transpose().LLL()[0]
sage: assert R == A * pow(B, -1, n) % n
sage: A.bit_length()
1148
sage: B.bit_length()
1022
System of multivariate polynomials
At this point, we know that:
$$ \frac{A}{B} = \frac{m + h}{h + c} + \frac{h + c}{c + m} + \frac{c + m}{m + h} $$
Which is equivalent to:
$$ \begin{cases} g \cdot A = (m + h)^2 (c + m) + (h + c)^2 (m + h) + (c + m)^2 (h + c) \\ g \cdot B = (m + h) (c + m) (h + c) \end{cases} $$
For some positive integer $g$, probably small.
We might be tempted to try using multivariate Coppersmith method, but the above are 3-degree polynomials, so the variable values are not short enough to find small roots.
However, we can use Groebner basis to find a solution to the system of multivariate non-linear polynomials:
sage: m, h = PolynomialRing(QQ, 'm, h').gens()
sage:
sage: g = 1
sage:
sage: p1 = (m + h) ** 2 * (c + m) + (h + c) ** 2 * (m + h) + (c + m) ** 2 * (h + c) - g * A
sage: p2 = (m + h) * (c + m) * (h + c) - g * B
sage:
sage: Ideal([p1, p2]).variety()
[{h: 112505123084813325142525029007183899144558205055924378385155078283235959674654, m: 1949989741335361589319748039104353895461329509777569313050438882238845}]
And so we find both $m$ and $h$.
Flag
Here we have the flag:
sage: m = Ideal([p1, p2]).variety()[0].get(m)
sage: bytes.fromhex(hex(m)[2:])
b'HTB{3CC_1s_m4g1c___15nt_1t?!}'
The full script can be found in here: solve.py.