Zombie Rolled

10 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):
        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()

Y tenemos el resultado en output.txt:

pub = (-679149827688896546432684514781159016843208241259733038415608446794483893865137935606244643075224614588255514670703135466975466970913232919448971056463765967267932205245723609028669700790327888053737513173004906874791948794706164874163000233242663467112356684022940655151358257782991132383407917101800634477163967250047209128395271227452766580073122831277123102243705154267181506512402418039719173720827696442606604970528063168565779813124052546633103006687964589521475168208905582555230534709754318532234948569155566965251016769141273474050547777208930826949494111933369822606247918218189742785296490363879808413854798453415486721083351760540440727104905848109665720749305468099771944894375713469720303756620101486771358570935901473647573434771209918671576552610105681029288935780171889489032033021940200657122568137703155744190258342713712412791279147013204380608939099412456303268575877533613186703629403608506029153274825614231950222036769768440858686468414798013424323765200986740221652787739657510451377763752151261173701557996570807100005672113902309356835881522886670894124683065117547063607171455016275575226133973000898546626428525316423640294588059582425678225307973026140509236726222895277593502658123536454581741258241350319709620218946214665277722917625163484143287737560990362641167985157948128093478633332215687808673326510025966928820082371826010204772434810834908522239370003521927141674940923107924718589020116481655436804371698576313448620651274568714018039959665606305466508336068792512300330447079049391998121903628542300433666064229921580215835067999800174889123776199641564914760737600821953293714498453721075798275047009255942697608822458887368884228615671991262750899422262693397993810261279502497616420217291365257434988696383465213630804193810674969275499135895349396517300341694326130217329147937575188985044945549854453507141533817669145401648967346307076924815850188448842044898686784928539015228772201838211426957234107261809629639488140342429501192224120877838900600824055655563831019772958581350347081393942024086716044621385448218128870528968546874044728000006962970494893355352673283507468842799994294656025864551101856509528014985899203160260433154506345617010883888392862375738238905192516684056280710225432696655387350661830299769543107006018477779636761481812001885777307338070488998064732654317341303970152707374877928275562177058710127753099319277046999346991319018270073503529254012239006330090621492580837121246383935, -62076393535220713230211372773016154819776973272085279510651810925567779949353129946722665324346680014266486318715153201960740792449256110092242298637141869182191301801348471698842750492673269805386405258903922775271516275959471007270470783319809938344980989030858451767810558937769006054050097442784355926821230070379192555314422288851726919132047206078443630648828611342794053179031715333055698280449463491394083273880477510623203232349139229518535496279365263598613132079698328994631219260929529014155663831397189773051194410051588749692352737665469175569662944453505412436038259868251153299961933349760369897472364513246615362132669886696823052680175413762753451532554603896709930434997447861155715656069046149639262746319959746238179869888630675350046188185867904504017641487194302334327723755607524433514488406681046596968802669158589535873655500657057147028422069215178280598799698023523842357762349312690981167196137904038634376059163646848305423446194854985523208266633269733804799399607579721802215740994923964998077749276376011664190442983045021233328860583431325491398740404717916957583624416525249155775990424790364048060223994351310834002052812950138181225201366866314173709814344726454058400929651246654127831150461139153521780070432541564467256212600334416658092578286615407601260752708323965051595729545763555521745630970189873094019504197470499857463907805936270010647572788276449685684281797985033841971693243345694540270555091524839897049609610694927649006414175285808616559721550306026476105719357460921592355959150692653059587214522745084239909633381558412919917765258331958067109432311999676460754436818201240023311791169802096388297862219517745888298152485206376817292783209092101414045488990410966964411575840592166475524123368782667715013887175556663844953274929494297381264202051980047425186510319292378252632808136510156368067796082090881873863176619957188519245758562409606283750005034060349233190765189422774601110274372976258448740486162640303554541285690390642874100570657406690134508272681549727638076837266298852607372446728482637226932907561200761597573567176950238238261414346592107964949875193908993522612254840698757416962124520050724327233377985303460697496676181895430294259015494830416056429816116680627673230428123227550005209799526871524994673920145445281764352654447538983391735348123813851971146216997750793741632897137346289689048299843427272709114665386119324590006011517253390435055796456069897547662246663469050, 7830486145829508377558227408290134666403414818680891369176645894657730719560462345413647777035691365258303368067215176543275998927964954949936712360465415742305180023074796925974228987920346807337046972890048193675380148777690313974213732587383856306544481992804522271933234142582135631837143021763752036371144162337258022513117655962693146611295672219977744995976478481618309460588961678471875936477345228279163041888319063508894362501867902730894177063341454634424454782062634032617628985824505983759212857299828749995752235758280573881085074326788874659358083585790319249788052723728978677280818302159890013608215097544022503686764809254320162354127388898310054146477537454655331114752144580956313131601466170634129721047436217501010686515461442226299103956329529388095001070391385189826814864746360320333918929686149324974844514612649731799514398645742580625276435924292653289878873850265379360271050603859206438004883855432886650553014115919828422317294957226985270768975519537120458232477529774162488973095316791366021139626153997771391194348622350835846276300080551743631687665470499546808409919692234446116541139972549724015591941496221132694347053824568526998941915494190313922421141792712177850635304804853629529860738709134170021521102700328604628927875567294032063066171031633521264813050524393039049915547228949811888603458908961700972119089383547482638110428947454915597289453149684921808588155575892869551719408017163519505152564311034805403584244791464453674297092713220925531618514351406361895037695504970845118751396728421079695580995084470838685511076186640881628743480208128654755986540162228797182203097429878571055580982419910698271318560371375725624590383889293031827343721601921283218257563981664825233636121202430668321472633600201081855377049584327600961474706457007803948936824801776548939412019028877381656854352042881659133167174502453362966793813997989646037370005971535903722675701268453950616768210577721799262016472978512795971976360288455246627122308235526400041892494207712587655624310348101802715615388185255043745377008056152447575197765696754537890671347192620664952431667401070828663411172784617836559669320812607668877073449814900939924918858434664371233944816438544081459935797541138873496291375791704149531348074915907756350500006241339201669154574473335111528050064627331874217370202929428747238792910498913366471880111057711710182734506773946328772476941505432386559666283038340899500750365525879310436221464632932)
mix = [320097670159304209872309549471930993417143388077612479497520462342663934977666619462544724222917378443968580805422580825361629081490271425796180005007150747981294833573665302687843134857904098195466433204039058015530152552325684827139190765614362244643766711802006240778166882116884363374725459551909065104305033828828854239454604753713577854447476580313858442898211797176449603725270483947895282965175447381948570185109212852155846189091780576621552251326144055737198080348963003230356855332599698331598994549981281612662608348841085666739363070407550100107611043508427316142601784200258788876751333421411315222696828075445887895455540798110282831853710380354729703219505108629359197051336831375142595785378662848001960222878291497005997865756885831339332471275732796885611507451753622271015336628712225776167393560183733898486530850953580390452793438185371865569655507768389802668508433717577899938841236692983646823027361, 349362680724100439001784418744128033820777004106762219940030797663423035126842789961301765825984790980690057949860749399355278228450692377224412215897507215190015109832483673402204604232784701242900565985678019980900605960003183528535025133581067044874804468687010880739758605406077761031350401248992459970793003097988643424534679899913404629630391199540164124586883472387639995010304310446530364782969667797609685774685940403053235307671556459857310584515167273597080744839887558160920716970032955099943334650018552259294137522684003806871855045036984303040298988654317845297423677227040203951111165862748444474516781528350286768742283071330157900311167729282004019891879048809487509974878771126244472706852271120669147203065908414503160273025384004067262219422586521719641783916408458322110103608436662590492232330298616191719127365835397875038644290248233827642595125378514596518087399154247594983235918109876187387712452]

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) + Fraction(b, c) + Fraction(c, a)

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.f.denominator)

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.f.denominator)

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.f.denominator)
        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.f.denominator) == 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}"

Solución

Ya que sabemos que encrypt y decrypt son funciones inversas y que funciona bien. En comparación con un RSA clásico, tenemos 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 . El servidor realmente calcula . Este hecho determina que y por tanto .

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)
                return PrivateKey(priv, pub)
            except ValueError:
                pass

El constructor hace lo siguiente:

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

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

class PublicKey:

    def __init__(self, pub):
        self.pub = pub
        self.f = self.magic(pub)
        self.nb = (self.f.denominator.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

Pero recordemos que , que significa que para algún . Por otro lado,

Como resultado, tenemos eso

Mientras hacía pruebas en en Python, descubrí que

También, , pero

Esto significa que es un múltiplo de , pero en cada par , , , solo podemos factorizar . Después de algunos intentos, podemos encontrar la siguiente estructura:

para algunos enteros y . Las relaciones anteriores funcionan ya que

Por lo tanto, tenemos

Y así, . Trivialmente, encontramos y .

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. Démonos cuenta de que , donde

Aquí, es posible que necesitemos 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.

Como sabemos , solo tenemos que encontrar y , que se pueden suponer que son valores pequeños. Tenemos

Vamos a deshacernos de los inversos multiplicando por :

Como resultado, podemos definir un polinomio:

Donde . Como y son valores pequeños, podemos tratar de encontrar raíces pequeñas de este polinomio bivariado utilizando el método de Coppersmith.

Implementación en SageMath

En primer lugar, tomamos los valores de output.txt y encontramos y :

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

A continuación, encontramos la clave privada , , y afirmamos que los valores son correctos:

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

Una vez que tenemos la clave privada, podemos descifrar el mix, hallar la firma y calcular y . La longitud de también la verificamos:

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

Finalmente, necesitamos definir el polinomio de dos variables y usar el método de Coppersmith para encontrar y . Una buena implementación del método de Coppersmith multivariado es la de defund. Podemos descargar el script y cargarlo en SageMath para usar la función small_roots. Una vez encontrada una solución, podemos confirmar que el hash SHA256 coincide y luego simplemente imprimimos la 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

Y aquí tenemos la flag:

$ sage solve.sage
HTB{4_s3cur3_crypt0syst3m_sh0u1d_n0t_c0nt41n_s3cr3t_c0mp0n3nts!}

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