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 $p$, $q$ y $r$, 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:
$$ \mathrm{magic}(a, b, c) = \frac{a}{b} + \frac{b}{c} + \frac{c}{a} = \frac{a^2 c + b^2 a + c^2 b}{abc} $$
def magic(ar):
a, b, c = ar
return Fraction(a, b) + Fraction(b, c) + Fraction(c, a)
Podemos aplicar magic a los 3 números de la clave pública y obtener una fracción $f$ con numerator $N$ y denominador $D$. Estos dos valores se utilizan en el resto del script.
Cifrado y descifrado
Para cifrar un mensaje, el servidor toma el mensaje $m$ en formato decimal y calcula $\mathrm{ct}$:
$$ \mathrm{ct} = m^N \mod{D} $$
def encrypt(self, m):
return pow(m, self.f.numerator, self.f.denominator)
Para descifrar, el servidor calcula
$$ m = \mathrm{ct}^d \mod{D} \qquad d = N^{-1} \mod{(p - 1) (q - 1) (r - 1)} $$
self.d = pow(self.f.numerator, -1, prod([x - 1 for x in priv]))
def decrypt(self, c):
return pow(c, self.d, self.f.denominator)
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 $m$, su hash SHA256 $h$ y un valor aleatorio $c$ para calcular $\mathrm{magic}(m, h, c) = \frac{A}{B}$.
Los valores $A$ y $B$ se utilizan para calcular $R = A \cdot B^{-1} \mod{D}$ 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:
$$ (s_1, s_2) = (R^d, c^d) \mod{D} $$
def sign(self, m):
h = bytes_to_long(sha256(m.to_bytes(self.nb, "big")).digest())
a, b = m, h
c = randbelow(1 << self.nb)
r = fraction_mod(self.magic((a, b, c)), self.f.denominator)
s1 = self.decrypt(r)
s2 = self.decrypt(c)
return s1, s2
La función de verificación toma el mensaje y los valores $(s_1, s_2)$ para realizar casi las mismas operaciones. Primero, encuentra $R = s_1^N \mod{D}$ y $c = s_2^N \mod{D}$, luego lo compara con el valor esperado de $R$ usando $m$, $h$ y $c$:
def verify(self, m, sig):
s1, s2 = sig
h = bytes_to_long(sha256(m.to_bytes(self.nb, "big")).digest())
a, b = m, h
r = self.encrypt(s1)
c = self.encrypt(s2)
return fraction_mod(self.magic((a, b, c)), self.f.denominator) == r
Se nos dan algunos valores relacionados con la firma de la flag. Específicamente, tenemos $(s_1 + s_2)^N \mod{D}$ y $(s_1 - s_2)^N \mod{D}$, donde $(s_1, s_2)$ 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 $N$ como el exponente público y $D$ como el módulo público. Por lo tanto, para descifrar, necesitamos encontrar el exponente privado, que debe ser $d = N^{-1} \mod{\phi(D)}$. El servidor realmente calcula $d = N^{-1} \mod{(p - 1) (q - 1) (r - 1)}$. Este hecho determina que $\phi(D) = (p - 1) (q - 1) (r - 1)$ y por tanto $D = pqr$.
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 $N$ y denominador $D$.
Pero mira esta comprobación:
if self.magic(priv) != self.f:
raise ValueError("Invalid key pair")
Este hecho nos dice que $N$ y $D$, que son el resultado de magic y la clave pública (digamos $P$, $Q$, $R$) debe satisfacer que
$$ f = \mathrm{magic}(P, Q, R) = \frac{P}{Q} + \frac{Q}{R} + \frac{R}{Q} = \frac{P^2 R + Q^2 P + R^2 Q}{PQR} = \frac{N}{D} $$
Pero recordemos que $D = pqr$, que significa que $PQR = k \cdot pqr$ para algún $k \in \mathbb{Z}$. Por otro lado,
$$ \mathrm{magic}(p, q, r) = \frac{p^2 r + q^2 p + r^2 q}{pqr} = \frac{N}{D} $$
Como resultado, tenemos eso
$$ \begin{cases} N = p^2 r + q^2 p + r^2 q \\ D = pqr \end{cases} $$
Mientras hacía pruebas en en Python, descubrí que
$$ \begin{cases} PQR \equiv 0 \pmod{D} \\ PQR \equiv 0 \pmod{D^2} \\ PQR \not\equiv 0 \pmod{D^3} \end{cases} $$
También, $P, Q, R \not\equiv 0 \pmod{D}$, pero
$$ \begin{cases} PQ \equiv 0 \pmod{D} \\ QR \equiv 0 \pmod{D} \\ RP \equiv 0 \pmod{D} \end{cases} \qquad \begin{cases} PQ \not\equiv 0 \pmod{D^2} \\ QR \not\equiv 0 \pmod{D^2} \\ RP \not\equiv 0 \pmod{D^2} \end{cases} $$
Esto significa que $PQR$ es un múltiplo de $(pqr)^2$, pero en cada par $PQ$, $QR$, $RP$, solo podemos factorizar $(pqr)$. Después de algunos intentos, podemos encontrar la siguiente estructura:
$$ P = \alpha \cdot p q \qquad Q = \beta \cdot q r \qquad R = \gamma \cdot r p $$
para algunos enteros $\alpha$ $\beta$ y $\gamma$. Las relaciones anteriores funcionan ya que
$$ \begin{cases} PQR = \alpha\beta\gamma \cdot p^2 q^2 r^2 \equiv 0 \pmod{D^2} \\ PQ = \alpha\beta \cdot p q^2 r \equiv 0 \pmod{D} \\ QR = \beta\gamma \cdot p q r^2 \equiv 0 \pmod{D} \\ RP = \gamma\alpha \cdot p^2 q r \equiv 0 \pmod{D} \end{cases} $$
Por lo tanto, tenemos
$$ \begin{cases} \gcd{(Q, D)} = \gcd{(\beta \cdot q r, p q r)} = q r \\ \gcd{(R, D)} = \gcd{(\gamma \cdot r p, p q r)} = p r \end{cases} $$
Y así, $r = \gcd{(\gcd{(Q, D)}, \gcd{(R, D)})}$. Trivialmente, encontramos $p$ y $q$.
Una vez que tenemos $p$, $q$ y $r$ podemos calcular $d = N^{-1} \mod{\phi(D)}$ y descifrar el mix que tenemos. Además, podemos encontrar $s_1$ y $s_2$. Recordemos los valores de $s_1$ y $s_2$:
$$ s_1 = R^d \mod{D} \qquad s_2 = c^d \mod{D} $$
En este punto, podemos tener las firmas $R$ y $c$, y podemos verificar que sus longitudes en bits son correctas. Démonos cuenta de que $R = A \cdot B^{-1} \mod{D}$, donde
$$ \frac{A}{B} = \mathrm{magic}(m, h, c) = \frac{m}{h} + \frac{h}{c} + \frac{c}{m} = \frac{m^2 c + m h^2 + h c^2}{m h c} $$
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 $D$ es de alrededor de 3072 bits.
Como sabemos $c$, solo tenemos que encontrar $m$ y $h$, que se pueden suponer que son valores pequeños. Tenemos
$$ \begin{align*} R & = A \cdot B^{-1} \mod{D} \\ & = (m^2 c + m h^2 + h c^2) \cdot (m h c)^{-1} \mod{D} \\ \end{align*} $$
Vamos a deshacernos de los inversos multiplicando por $(m h c)$:
$$ (m h c) R = m^2 c + m h^2 + h c^2 \mod{D} $$
Como resultado, podemos definir un polinomio:
$$ P(x, y) = c \, x^2 + x y^2 + c^2 \, y - c R \, x y \pmod{D} $$
Donde $P(m, h) \equiv 0 \pmod{D}$. Como $m$ y $h$ 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 $N$ y $D$:
with open('output.txt') as fp:
pub = literal_eval(fp.readline().split(' = ')[1])
mix = literal_eval(fp.readline().split(' = ')[1])
P, Q, R = pub
f = magic(pub)
N, D = f.numerator, f.denominator
nb = (f.denominator.bit_length() + 7) // 8
A continuación, encontramos la clave privada $p$, $q$, $r$ 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 $(s_1, s_2)$ y calcular $R$ y $c$. La longitud de $c$ 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 $m$ y $h$. 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.