<- CRYPTO

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 , and , 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:

    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 with numerator and denominator . 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 in decimal format and computes :

    def encrypt(self, m):
        return pow(m, self.f.numerator, self.n)

Where , the product of the private prime numbers.

In order to decrypt, the server calculates

        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 , its SHA256 hash and a random value to compute .

The values and are used to compute 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:

    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 to perform almost the same operations. First, it finds and , then it compares it with the expected value of by using , and :

    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 and , where 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 as the public exponent and as the public modulus. Hence, in order to decrypt we need to find the private exponent, which needs to be , where .

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 and denominator .

But look at this ckeck:

        if self.magic(priv) != self.f:
            raise ValueError("Invalid key pair")

This fact tells us that and , which are the output of magic and the public key (let’s say , , ) must satisfy that

So, we know that

Rearranging the equations, we get that:

Cubic diophantine equation

As a result, we have that both and are solutions to this equation:

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 .

While reading about cubic diophantine equations, I found that if we interpret the above equation as a curve and its genus equals , then it can be expressed as an elliptic curve (more information at math.stackexchange.com). Notice that we already have a rational point , 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 form an abelian group (see Wikipedia). As a result, if we have a point on the elliptic curve, then any multiple of 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 because it lies on the curve:

sage: eq.numerator().subs({x: 1, y: -1, z: -1})
0

Now, for any multiple of 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 must be mapped to some point on the elliptic curve such that for a small . 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 :

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 , and :

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 , and we can compute and decrypt the mix we have. Moreover, we can easily find and :

Remember the values of and :

At this point, we can have the signatures and , 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 , where

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 is around 3072 bits.

However, instead of finding and , let’s find and . We know that both and are short compared to , and it follows that

As a result, we can use the following lattice basis:

So that we can use LLL to find a short vector , which belongs to the lattice because

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:

Which is equivalent to:

For some positive integer , 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 and .

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.