<- CRYPTO

Lost Modulus Again

6 minutos de lectura

Se nos proporciona un código breve en Python para cifrar la flag:

#!/usr/bin/python3
from Crypto.Util.number import getPrime, long_to_bytes, inverse
from os import urandom

class RSA:
    def __init__(self):
        self.p = getPrime(1024)
        self.q = getPrime(1024)
        self.e = 3
        self.n = self.p * self.q
        self.d = inverse(self.e, (self.p-1)*(self.q-1))
    def encrypt(self, data: bytes) -> bytes:
        pt = int(data.hex(), 16)
        ct = pow(pt, self.e, self.n)
        return long_to_bytes(ct)
    def decrypt(self, data: bytes) -> bytes:
        ct = int(data.hex(), 16)
        pt = pow(ct, self.d, self.n)
        return long_to_bytes(pt)

def main():
    flag = open('flag.txt', 'r').read().strip().encode()
    #padding makes everything secure :lemonthink:
    def pad(data: bytes) -> bytes:
        return data+urandom(16)
    crypto = RSA()
    print ('Flag1 :', crypto.encrypt(pad(flag)).hex())
    print ('Flag2 :', crypto.encrypt(pad(flag)).hex())
    print( 'msg1 :', crypto.encrypt(b"Lost modulus had a serious falw in it , we fixed it in this version, This should be secure").hex())
    print( 'msg2 :', crypto.encrypt(b"If you can't see the modulus you cannot break the rsa , even my primes are 1024 bits , right ?").hex())
if __name__ == '__main__':
    main()

Y también se nos da la salida:

Flag1 : 685dba88de1ecf0b4ae5bc84b7ee87f63eb37f697ca9a5ab6af9359341a2fbbf53b9502477cabb1658fdf775a34a0712b04d0fd2679b47ec088e0ab3c0a9a866198077a496bb1de138cd165ca28722dee7c4cc81ac0a3a179095f11981e9c7bcd590576169ed877b5692f42a7d9845bdb7c0bffd4e97541b65321de83e4083c1c8cc93eec59933f42655d7c0ad170ed9a3ea418b582e09a2692fc1965d8372cac678f0dabe1b0cbda93ac9b484feb9d2e96f3ab7e2fc6430da1931281c1870c637866be7fcd69c1b067e001887bb17a57ccd77532ea9dfaa0be1390db5511771dc9e03593e344bf0647ddac395b1fe80a86ad4ea4606fdb8a82fdcf9c846114c
Flag2 : 356f7e82071f321361075ee85f9b42922662559ed64b253c64ff37b52fe8dcf3ab3163079bc9a12e951f84d2f7a911cbf1b1e8d7cd759a128f21a89b625b07ded33443a2888ca9a455198fd5b4a3fb307f34c704b7dcad88685263f4c3f4cf37f1099f2bd188de72533308c25fc18948dda220e3693b7f3edb689ee489c14e7624932ee8928370c9c1d59b06d1071a259d64c38735b1b586082099919713b669a79e43329f0c20508620982d95b774a57d009540c2ef2835887d229273223272f86fb0b1740937d3fc83d7556ffe634a16fb1faf6125878b06f5d537c21260014e2e67ae47636cbce899c463a3669954253aac3aa89a1c800d3251cf6a36badf
msg1 : 0241f53c0690e3faccc3753b6064aef27341b5bef3a10fcbb362251e1f5474a055a04e631af1bb4542351f6051438fc6dbf2011f79cbd85bc667d1097b57818d01d11aa09db0ef221ccf8d9eb16903423702b64a534d49153b49dc47fd5597a96f2a6480d296d36d08ba3438cc193bba6ee2c3ea81ab4dbb029a737c3f5597c8e4b8db8ab06605443eb35160828bc78b1d889814d8811e89efae3d741a481a7bd09483df8ee6d32b56a8d7eb20b275cf3ba5936838da2893f82cbc469f1497f785603e72df1ae1f619e08834588f2e64dd5f4cbbdbc7357dadcd89dbd9e18b0948f9b3f8f6b0df217bd7e8ae5c89a20878ffb127e3cf862baa78cc67ec1012af
msg2 : 7499a590fcb19dd0880b77a0dd57f66f6055976100b10053adadaeec18c382c5c3d095b4edd6ee2a5dfdc5790b18ff96e54f093fa62d4b518c1bbe65ad3588a81a1723ce72798ddd06d1eca7be9332a7b754f85582c4c5800d0c778ec320fa53806d122b4f4e436ead12bdf05031d4c181416184932517da985ff503759d128761bd96009c43bf11e45ba60f495235d29a863b7a64d9752868dd9896563fe2cc91df6f092f6d4d7d600b4fbf2b52579a0f2657223a1092c067584aad9997540b25921513f96f2da0c26ffb2ee7578540efc50bc8ab0feeeb24e0e96ebc1e6310dbed880ec5d9788a86bebe72c4b5d9b5c66716e6b84021591372c823c6d78c4e

Análisis del código fuente

Lo anterior son 4 textos cifrados de un cifrado RSA-2048. Sabemos que el exponente es , pero no tenemos el módulo :

class RSA:
    def __init__(self):
        self.p = getPrime(1024)
        self.q = getPrime(1024)
        self.e = 3
        self.n = self.p * self.q
        self.d = inverse(self.e, (self.p-1)*(self.q-1))
    def encrypt(self, data: bytes) -> bytes:
        pt = int(data.hex(), 16)
        ct = pow(pt, self.e, self.n)
        return long_to_bytes(ct)
    def decrypt(self, data: bytes) -> bytes:
        ct = int(data.hex(), 16)
        pt = pow(ct, self.d, self.n)
        return long_to_bytes(pt)

Para los primeros 2 textos cifrados (digamos y ), la flag se rellena primero con una cadena aleatoria de 16 bytes y luego se cifra con RSA. Los últimos 2 textos cifrados (digamos y ) corresponden a mensajes conocidos codificados en el código fuente (digamos y ).

def main():
    flag = open('flag.txt', 'r').read().strip().encode()
    #padding makes everything secure :lemonthink:
    def pad(data: bytes) -> bytes:
        return data+urandom(16)
    crypto = RSA()
    print ('Flag1 :', crypto.encrypt(pad(flag)).hex())
    print ('Flag2 :', crypto.encrypt(pad(flag)).hex())
    print( 'msg1 :', crypto.encrypt(b"Lost modulus had a serious falw in it , we fixed it in this version, This should be secure").hex())
    print( 'msg2 :', crypto.encrypt(b"If you can't see the modulus you cannot break the rsa , even my primes are 1024 bits , right ?").hex())

Solución

En primer lugar, necesitamos obtener . Observa que usando los mensajes conocidos y , obtenemos:

Por lo tanto, y son ambos múltiplos de , así que podemos encontrar usando el máximo común divisor (GCD):

Ahora, para encontrar la flag, el punto clave es que los textos planos, antes de cifrar, están muy relacionados. De hecho, podemos denotar los textos cifrados como:

Donde y son las cadenas aleatorias de 16 bytes. También ten en cuenta que, dado que el relleno es concatenación de bytes, podemos expresarlo en términos numéricos con una multiplicación por .

Dado que el relleno es corto y , podemos aplicar el ataque de Coppersmith (de hecho, variantes llamadas ataque de Franklin–Reiter de mensajes relacionados y ataque de Coppersmith de relleno corto). Para ello, definimos dos polinomios:

Digamos que . Estos polinomios satisfacen que

Así, el punto es una raíz común de los polinomios y . Nos interesa hallar , pero necesitaremos encontrar primero. Para esto, tomemos el resultante de estos polinomios en la variable (algo así como eliminar esta variable):

Como resultado, , así que sabemos que es una raíz de . Observa que los polinomios , , están definidos sobre , que no es un cuerpo y no podemos encontrar fácilmente y tales que . Esto significa que encontrar esta raíz es difícil.

Sin embargo, esta raíz (16 bytes) es pequeña comparada con (2048 bits, 256 bytes). Así que podemos usar el método de Coppersmith para encontrar .

Una vez tenemos , podemos actualizar nuestros polinomios anteriores y a:

Por lo tanto, tenemos que , por lo que es una raíz tanto de como de . En consecuencia, podemos aplicar el ataque de mensajes relacionados de Franklin-Reiter, que consiste básicamente en calcular el GCD polinomial de estos polinomios, para encontrar el factor compartido , y así obtener la flag.

Implementación

Todos estos pasos se pueden realizar en SageMath. Primero, escribamos la salida dada del reto y la información conocida:

sage: c1 = 0x685dba88de1ecf0b4ae5bc84b7ee87f63eb37f697ca9a5ab6af9359341a2fbbf53b9502477cabb1658fdf775a34a0712b04d0fd2679b47ec088e0ab3c0a9a866198077a496bb1de138cd165ca28722dee7c4cc81ac0a3a179095f11981e9c7bcd590576169ed877b5692f42a7d9845bdb7c0bffd4e97541b65321de83e4083c1c8cc93eec59933f42655d7c0ad170ed9a3ea418b582e09a2692fc1965d8372cac678f0dabe1b0cbda93ac9b484feb9d2e96f3ab7e2fc6430da1931281c1870c637866be7fcd69c1b067e001887bb17a57ccd77532ea9dfaa0be1390db5511771dc9e03593e344bf0647ddac395b1fe80a86ad4ea4606fdb8a82fdcf9c846114c
sage: c2 = 0x356f7e82071f321361075ee85f9b42922662559ed64b253c64ff37b52fe8dcf3ab3163079bc9a12e951f84d2f7a911cbf1b1e8d7cd759a128f21a89b625b07ded33443a2888ca9a455198fd5b4a3fb307f34c704b7dcad88685263f4c3f4cf37f1099f2bd188de72533308c25fc18948dda220e3693b7f3edb689ee489c14e7624932ee8928370c9c1d59b06d1071a259d64c38735b1b586082099919713b669a79e43329f0c20508620982d95b774a57d009540c2ef2835887d229273223272f86fb0b1740937d3fc83d7556ffe634a16fb1faf6125878b06f5d537c21260014e2e67ae47636cbce899c463a3669954253aac3aa89a1c800d3251cf6a36badf
sage: c3 = 0x0241f53c0690e3faccc3753b6064aef27341b5bef3a10fcbb362251e1f5474a055a04e631af1bb4542351f6051438fc6dbf2011f79cbd85bc667d1097b57818d01d11aa09db0ef221ccf8d9eb16903423702b64a534d49153b49dc47fd5597a96f2a6480d296d36d08ba3438cc193bba6ee2c3ea81ab4dbb029a737c3f5597c8e4b8db8ab06605443eb35160828bc78b1d889814d8811e89efae3d741a481a7bd09483df8ee6d32b56a8d7eb20b275cf3ba5936838da2893f82cbc469f1497f785603e72df1ae1f619e08834588f2e64dd5f4cbbdbc7357dadcd89dbd9e18b0948f9b3f8f6b0df217bd7e8ae5c89a20878ffb127e3cf862baa78cc67ec1012af
sage: c4 = 0x7499a590fcb19dd0880b77a0dd57f66f6055976100b10053adadaeec18c382c5c3d095b4edd6ee2a5dfdc5790b18ff96e54f093fa62d4b518c1bbe65ad3588a81a1723ce72798ddd06d1eca7be9332a7b754f85582c4c5800d0c778ec320fa53806d122b4f4e436ead12bdf05031d4c181416184932517da985ff503759d128761bd96009c43bf11e45ba60f495235d29a863b7a64d9752868dd9896563fe2cc91df6f092f6d4d7d600b4fbf2b52579a0f2657223a1092c067584aad9997540b25921513f96f2da0c26ffb2ee7578540efc50bc8ab0feeeb24e0e96ebc1e6310dbed880ec5d9788a86bebe72c4b5d9b5c66716e6b84021591372c823c6d78c4e
sage: 
sage: e = 3
sage: 
sage: m3 = int(b"Lost modulus had a serious falw in it , we fixed it in this version, This should be secure".hex(), 16)
sage: m4 = int(b"If you can't see the modulus you cannot break the rsa , even my primes are 1024 bits , right ?".hex(), 16)

Ahora, encontremos usando el GCD:

sage: n = gcd(m3 ** e - c3, m4 ** e - c4)
sage: n
17239653555729308464049438184920371089879081148402291800380594759517665804698359052648921465219887554469533537465122062104900480567488997794605293481770139146098702102563250193298500864238250949982552595159802814788612573898410252974926866757617491510437384709301937357695288829868010397984533999482461397333141208905813094732501385628605554793978927603376904138986551086256407424185029648833489655496424708493511895902919181646372064531235987733921846952446773365611469842532440322381367711369625814351911101284458643213930109512205598526068165522864217435748337932540742524768583448250580752519750464577065964352977

Una vez tenemos , podemos definir los polinomios y como se indicó anteriormente y encontrar su resultante:

sage: P.<x, y> = PolynomialRing(Zmod(n))
sage: 
sage: f = x ** e - c1
sage: g = (x + y) ** e - c2
sage: 
sage: h = g.sylvester_matrix(f).det().univariate_polynomial()

Aunque SageMath tiene un método resultant, a veces es más fácil calcular el determinante de la matriz de Sylvester, que es esencialmente lo mismo que la resultante en este contexto y no lanza ningún error de tipo.

Después de eso, aplicamos el método de Coppersmith en para encontrar la raíz pequeña :

sage: R = h.monic().small_roots(X=256 ** 16, beta=16 / 256)[0]
sage: R
17239653555729308464049438184920371089879081148402291800380594759517665804698359052648921465219887554469533537465122062104900480567488997794605293481770139146098702102563250193298500864238250949982552595159802814788612573898410252974926866757617491510437384709301937357695288829868010397984533999482461397333141208905813094732501385628605554793978927603376904138986551086256407424185029648833489655496424708493511895902919181646372064531235987733921846952446773365611469842532440322381367711369625814351911101284458643213930109512205598526068165522864217435748337932540742524768288846483820791076371295960930657614594

Aunque el valor obtenido para no parece pequeño, de hecho es pequeño, pero en forma negativa (y obviamente una raíz de ):

sage: -R % n
294601766759961443379168616135306738383
sage: h(R)
0

Una vez tenemos , podemos definir los polinomios y y aplicar el GCD polinómico para encontrar la flag con relleno:

sage: P.<t> = PolynomialRing(Zmod(n))
sage: 
sage: F = t ** e - c1
sage: G = (t + R) ** e - c2
sage: 
sage: def polynomial_gcd(f, g):
....:     return polynomial_gcd(g, f % g) if g else f.monic()
....: 
sage: flag_p1 = -polynomial_gcd(F, G).coefficients()[0] % n

Flag

En este punto, simplemente eliminamos el relleno y hemos terminado:

sage: flag = int(flag_p1) // 256 ** 16
sage: print(bytes.fromhex(hex(flag)[2:]).decode())
HTB{Fr4nk1ln_r3t1t3r_sh0rt_p4d_4tt4ck!4nyw4ys_n3v3r_us3_sm0l_3xr_f0r_rs4!1s_th1s_Msg_g01ng_l4rg3r?_0h_y3s_cuz_1_h4v3_t0_Pr3v3nt_Cub3_r00t_4tt4ck}