Zombie Rolled

13 minutos de lectura

Se nos proporciona el código fuente en Python para cifrar la 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()

Y tenemos el resultado en output.txt:

pub = (-210460004064658545149323270027125585053769531535575407350548992758255183408956300581776562753733749147991850793425366295331667362050138873330003194124140770281180202423447393078536478578946868914766383656089736270769788751224790405249013826635560803115098339073827135185826800939385978982619079483041610504047360527984966942969476938139600034002723364891052748171817924407580597412822624685840388733150562475191261733959754302870066881457439368383797860179354173905065196438650796693994506662218070106433605252371699975224015082241530805008715676767375587161483265765928867425947585319697598716342929731654599546786312158055192372546719883973931468047435521481784391209900070757353943121542277996362196911350140936374803527008606311714911826664001861344148925432456604114027567871907313538504631322730338913938316266631382676518400709132275709208557215429334792606216034973795842808506218623336928645873355528451647090676781751760050107610570392509919226018971445825324823288871147536975132689880688845587543605955579179730900403874103993879894103493722630349071444752690194369435903192722227882789473747568915937633017628653003841969130850224276467088238242967030703252034634998838450149987830988170632158593090342822378422506206718162866788489383954424520400309687446396922689894702349422494539870822982165352296752757838249758847248954901520084148063833208536651742341062164244017879477206939664935238944946527073936644149311943102740610769083279706502997296755709766586056165002192995150546453376411375946735666151030041089735143874012598684485919998838606432520697668756217572519576983009160506152352207045277432241713427473866239668163675448604724328457217539264682046367317013329398485410857195615049823175203925245252476463981844247115175989610533376228024079063115447932497123000468533406318130678663522920114992487564435224227779829370167357854542102259851547210728204680236254781690752101737776286349310317871408511173261016327829488783128124238185622581734373566268247117224296866158777566843574447075623007306270893524221590605260716241323455401522724392760024858027770598653347708025277948266108534992117950744942247538387691821093590335831543492934619905845153938941387523633891920168775933273356246150913687287580005738308853842778146772472161206052698833816938811736333968533167868483246719752201140628448572481749697124587956816178331696810978096173224327142109508407599863959977452073108504801967731216012715964184501653322161959765640703181, 48092167959932577089665706598220165781675771390752790227245377485859485947881571546031811781823531847290145883570391381336778582646376615617889209041048861514625245618391721904143628115253008909601418469608473423398811492009174166243685961257740358835633188280095876080795489899534519571369848752371797579799946381022948625049501467395264530262180573337083241907562614192878574144739061761541532656064621319804504351482986554734034210707836134653811450482725467108642223588121505067372994985292445520001174499519401437153507541826140463290765362583187446831892904451524623790721268161001505010481230620204674812222356870636305377968155481717890541702589197283597439323265314022562812242179576784749209668144438109469457078988559669837452513366063950036113075144671910134836382726061473126596550646614146078443174581105422846476318083629216862717532462628808127510223310132293885710468097698984259717619848649531077210788062624065543549381024587940656696251443503084172682617980324949080794778369101476911695987538917170783888585139170905742797701946636143246389557327737817504828854418238552918710493680241317067229833001240440514379022640617590974019364950318928389827811099478122002451161835713755344612988172028689418803025998639828426011191461104344294996539829176323901970637792252523712675333669643021955732902568937344239074357264968149516161281055403110376979324305028602766172174883302154360855869543967352800198912263276004643959465449518606967096622877028244289928766147905890748205869026637227939534515251009369887727237698461495359469851241721149456159709360150623548149581359231657983430999420794121959127958134018098368856357393108801463187546862737776427868272569433029692425993859830526727241723993224189921729311066393181076960370979893551066586057187601990674487017141841203651494165412078824016216754534826975530662024505444138560368190331434252079819695526471547437779865513089729452268860789068729093350931932611352070995981169035623937574282154283574443761574061931582345766796531904501680567328867512168123101442032309382206953539164445916851695172111176960556792392084525760682929517743118401815662873213111364254472092662871664405216936355120399440412953512383116635297774548790160970019719792538575510949649801729271389813372049233273940011935172643734336578398019766131368283650306004979181140230735068877461269713653548413632936784854356608036728978669525070594086171522597576796441820273981883356320986465325910023468305252933853, 295680237318969834583481350558045576069593397434250114268436392515105169191935289027375497778723372682513840734207932618190330189517739831911523847702330549481897559170495540721652247420337613272507142470605966203844911067854272669874935602731760616153213014890133142801239192079947159594861361601316909850841003469924342012486894936276047149241609037499591917591895130811114625418446330611492030654343430138478099676751910050330177587495855685857580069837873749334025367386942484569200376276585839574077306764891344426845642147405113306157668890178540851789817824614402737945630733737882024042823084893907616969914474832694719037443444818465434680322725745534751292520813842900322357596056857411573205554845465657322776026906939671854071190622648044326841578658423897845211643831096140970428604677609426173111469986019593063904916756246862724809757031532573248196113934118167511345376202958349994847533599803302816875080995188540954333242472866288368356433000012641533588227196752255533968884901760351526179286226813116146805328519695058833653483175617155524796170315815030198082197252295143664620853012864343932707621691692301666805387191857665541247527691509939498006149235577928744988285274380407878815137597089985965284441453525606984850948169652950770654611407196062991198720683081845399004437598542824766225913256140462688017991149014643840857737669793609045002562156298085352771410764034902539507427824936008812792316353855076217474511027376324964324258381503327600240847068580184327069988899673860991472703503982213831152492161359690522185944809136541502229303028310970512499852428336274934693121000245417851454895814281309411653690987796653842598705383750863545849146632339464355340312413889619057550789920777741216497799023886731790428675508850191436528845210345233154209449815183440739968081125328477883943958120844772517543814408943265674355655325470607676318683037563323920211491222704859819893440021032032779436664971290722627579527689013107226911966671185548413889504849802792656272827006947483605480044492484117853415676118939728854488844585782571371102778347974774155341887561550811966344521652867740827641565526459587452560357733493573548740842552438280369419404671314951756797396105930460945603675920681705201005229355597434166687085158453441941920742876590640482018781974161883195654719122551742622613429276209109558416257393084810842677543509590116448722500988340213756485998183685287230874073206039147869000598425185218952661827499422115)
mix = [2757730114159077389149698432635923981837301729613836384821565970385413527287691303546550071418389460869153265388793288168218992857076782393276221793088140996712795952988234917553350760904749861274926130040479200999429727248629683885916287922239431512820824780777954623772876620507269441914094023673807162641852804725138549956405696699115992461751212100433365705709888998783961544036761746518152663764468503408338480433435667952025380728443297958328995861002595831477329613145876325119604318873183779731991800100149300453012374526367862223973666642160703278246134349210011935898797845233856417363897814513913560313373938031644170526217562189440749278611074828271277104045968930855308000341736235120452258250999462234119531102229181591002350278544442729901864691776115513351943684918165600813284119872912267330400545353503839148657803170834314260914120288293705317513662212847101683300574727947089599033219552668719815029040408, 504994496960270139574946670894069299431207241073364481107436674373406781743273696715057719201622004604281774275828786758698939566785199569446395919976297320011795400301194061227784647070778305874870978021644569959853017603794627523140118519605135041612547135975756808050442548006245570578440457971432120788018096254980159404343207191110068743936220169743056476599906402449120877843887111307810902465612716393076554531289608909139586938005968169706464844575482719379839259559227740024158017349642299710203478526165482299268838854867695568738299929667468342278771679001361343570395883313247212144180543867644990780207723987043462219435393004802347242735452985011336597806947860484258115007949848766287513407339843432999716727634381116327557264348049187312387308303580287236597542911203816391268299325974510924298072270564103660391793686666200192144475147526288929033464511058363590578958753909920404740300100217899387268556668]

Análisis del código fuente

El servidor genera 3 números primos , y , que forman la clave privada.

Generación de claves públicas

Hay una función desconocida llamada derive_public_key que se usa para obtener una clave pública a partir de la privada. El comentario sobre los principios de Kerckhoff es relevante aquí porque este enfoque es de seguridad a través de la oscuridad, lo que no siempre es seguro. Los principios de Kerckhoff establecen que la seguridad debe confiar en las claves, en lugar de los algoritmos.

El resultado de derive_public_key es una lista de 3 números, dados a nosotros.

Estos números de clave pública se transforman con magic:

    def magic(ar):
        a, b, c = ar
        return Fraction(a+b, b+c) + Fraction(b+c, a+c) + Fraction(a+c, a+b)

Podemos aplicar magic a los 3 números de la clave pública y obtener una fracción con numerator y denominador . Estos dos valores se utilizan en el resto del script.

Cifrado y descifrado

Para cifrar un mensaje, el servidor toma el mensaje en formato decimal y calcula :

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

Donde , el producto de los números primos privados.

Para descifrar, el servidor calcula

        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)

El código también nos muestra que ambas funciones tienen el comportamiento esperado, y que son inversas:

    # make sure it really works
    enc = key.encrypt(m)
    assert key.decrypt(enc) == m
    sig = key.sign(m)
    assert key.verify(m, sig)

Firma y proceso de verificación

Como se puede ver, también hay una firma y rutinas de verificación que funcionan como se esperaba.

Para firmar, el servidor toma el mensaje , su hash SHA256 y un valor aleatorio para calcular .

Los valores y se utilizan para calcular con fraction_mod:

def fraction_mod(f, n):
    return f.numerator * pow(f.denominator, -1, n) % n

La firma es solo un par de valores:

    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

La función de verificación toma el mensaje y los valores para realizar casi las mismas operaciones. Primero, encuentra y , luego lo compara con el valor esperado de usando , y :

    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

Se nos dan algunos valores relacionados con la firma de la flag. Específicamente, tenemos y , donde es la firma de la 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

Ya que sabemos que encrypt y decrypt son funciones inversas y que funciona bien. En comparación con un RSA clásico, tenemos que como el exponente público y como el módulo público. Por lo tanto, para descifrar, necesitamos encontrar el exponente privado, que debe ser , donde .

Por otro lado, el método estático generate_key de PrivateKey genera la clave privada y deriva la pública. Luego, devuelve una instancia de 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

El constructor hace lo siguiente:

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]))

La clase PrivateKey hereda de PublicKey, y su constructor se llama con la clave pública:

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

Aquí, el valor de la fracción f se calcula, que contiene numerador y denominador .

Pero mira esta comprobación:

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

Este hecho nos dice que y , que son el resultado de magic y la clave pública (digamos , , ) debe satisfacer que

Entonces, sabemos que

Reorganizando las ecuaciones, tenemos que:

Ecuación cúbica diofántica

Como resultado, tenemos que ambos y son soluciones a esta ecuación:

Lo anterior es una ecuación diofántica, porque estamos trabajando con coeficientes enteros y estamos interesados en soluciones enteras. Por lo general, las ecuaciones diofánticas tienen más de una solución, por lo que necesitamos encontrar una manera de resolver lo anterior para encontrar .

Mientras leía sobre ecuaciones diofantinas cúbicas, descubrí que si interpretamos la ecuación anterior como una curva y su genus es , entonces se puede expresar como una curva elíptica (más información en math.stackexchange.com). Obsérvese que ya tenemos un punto racional , que es un punto en la curva cúbica, por lo que podemos tener un punto en la curva elíptica utilizando la conversión de la ecuación cúbica a la curva elíptica.

De hecho, los puntos racionales en curvas con genus igual a forman un grupo abeliano (véase Wikipedia). Como resultado, si tenemos un punto cualquiera en la curva elíptica, entonces cualquier múltiplo de también es un punto racional. Por lo tanto, podemos usar el mapeo inverso para obtener otra solución a la ecuación cúbica diofántica.

En SageMath, podemos probarlo:

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

Por lo tanto, ahora podemos encontrar la función de transformación desde la curva cúbica (el numerador de la fracción) a la curva elíptica y su inversa:

sage: F = EllipticCurve_from_cubic(eq.numerator(), [1, -1, -1])
sage: Fi = F.inverse()
sage: G = F((P, Q, R))

Nótese que SageMath requiere un punto de proyección. Hemos usado porque se encuentra en la curva:

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

Ahora, para cualquier múltiplo de en la curva elíptica, podemos encontrar una solución a la ecuación cúbica:

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

Sin embargo, estas soluciones son enormes:

sage: int(a.numerator()).bit_length()
73531
sage: int(a.denominator()).bit_length()
73533

Como resultado, podemos pensar que debe ser mapeado a algún punto en la curva elíptica de tal manera que para un pequeño. En SageMath, podemos usar division_points para encontrar tales puntos, si existen:

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)
[]

Entonces, tenemos que :

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'>

Muy bien, pero aunque tenemos otra solución a la ecuación cúbica, a, b y c son números racionales. Debemos encontrar soluciones enteras. Para esto, simplemente podemos encontrar un denominador común y multiplicar cada número racional por este:

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

Los valores ahora son enteros, y son soluciones a la ecuación cúbica. Pero lo importante es que hemos encontrado , y :

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

Descifrado RSA

Una vez que tenemos , y podemos calcular y descifrar el mix que tenemos. Además, podemos encontrar y :

Recordemos los valores de y :

En este punto, podemos tener las firmas y , y podemos verificar que sus longitudes en bits son correctas:

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

Démonos cuenta de que , donde

LLL lattice reduction

Aquí, podríamos intentar aplicar el método de Coppersmith o una técnica basada en retículos, ya que la flag tiene como máximo 64 bytes (512 bits) y el hash SHA256 es un número entero de 256 bits, mientras que es de alrededor de 3072 bits.

Sin embargo, en lugar de encontrar y , encontremos y . Sabemos que tanto como son pequeños en comparación con , y se deduce que

Como resultado, podemos usar la siguiente base de retículo:

Ahora podemos usar LLL para encontrar un vector corto , que pertenece al retículo porque

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

Sistema de polinomios multivariados

En este punto, sabemos que:

Que es equivalente a:

Para un entero positivo , probablemente pequeño.

Podríamos estar tentados a usar el método de Coppersmith multivariado, pero los anteriores son polinomios de tercer grado, por lo que las variables no son lo suficientemente pequeñas como para encontrar raíces.

Sin embargo, podemos usar la base de Groebner para encontrar una solución al sistema de polinomios no lineales multivariados:

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}]

Y con esto encontramos tanto como .

Flag

Aquí tenemos la flag:

sage: m = Ideal([p1, p2]).variety()[0].get(m)
sage: bytes.fromhex(hex(m)[2:])
b'HTB{3CC_1s_m4g1c___15nt_1t?!}'

El script completo se puede encontrar aquí: solve.py.