↓Ir al contenido
Loaxert

Baby Time Capsule

Autor
Santiago Chavarro

Código fuente
#

from Crypto.Util.number import bytes_to_long, getPrime
import socketserver
import json

FLAG = b'HTB{--REDACTED--}'

class TimeCapsule():
    def __init__(self, msg):
        self.msg = msg
        self.bit_size = 1024
        self.e = 5
    def _get_new_pubkey(self):
        while True:
            p = getPrime(self.bit_size // 2)
            q = getPrime(self.bit_size // 2)
            n = p * q
            phi = (p - 1) * (q - 1)
            try:
                pow(self.e, -1, phi)
                break
            except ValueError:
                pass
        return n, self.e
    def get_new_time_capsule(self):
        n, e = self._get_new_pubkey()
        m = bytes_to_long(self.msg)
        m = pow(m, e, n)
        return {"time_capsule": f"{m:X}", "pubkey": [f"{n:X}", f"{e:X}"]}

def challenge(req):
    time_capsule = TimeCapsule(FLAG)
    while True:
        try:
            req.sendall(
                b'Welcome to Qubit Enterprises. Would you like your own time capsule? (Y/n) '
            )
            msg = req.recv(4096).decode().strip().upper()
            if msg == 'Y' or msg == 'YES':
                capsule = time_capsule.get_new_time_capsule()
                req.sendall(json.dumps(capsule).encode() + b'\n')
            elif msg == 'N' or msg == "NO":
                req.sendall(b'Thank you, take care\n')
                break
            else:
                req.sendall(b'I\'m sorry I don\'t understand\n')
        except:
            # Socket closed, bail
            return

class MyTCPRequestHandler(socketserver.BaseRequestHandler):
    def handle(self):
        req = self.request
        challenge(req)

class ThreadingTCPServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass

def main():
    socketserver.TCPServer.allow_reuse_address = True
    server = ThreadingTCPServer(("0.0.0.0", 1337), MyTCPRequestHandler)
    server.serve_forever()

if __name__ == '__main__':
    main()

Vulnerabilidad
#

El problema del código son dos esta usando como exponente 5 además de que podemos generar tantas veces como queramos el mensaje cifrado.

El Ataque de Difusión de Håstad nos dice lo siguiente, si podemos interceptar K mensajes de modo que K sea mayor al exponente usado (en este caso 5) podemos recuperar el mensaje sin necesidad de la clave, haciendo uso del Teorema del resto chino.

Exploit
#

Cada vez que pedimos el mensaje de nuevo cifrado nos da lo siguiente:

  • El mensaje cifrado que usaremos como resto mas adelante
  • La llave publica
  • El número de exponente

Para lograr romper el cifrado tenemos que seguir los siguientes pasos:

  1. Calcular el modulo total multiplicando las 5 llaves publicas que debimos generar
  2. Calcular los factores parciales para esto dividimos el modulo total entre cada llave publica dando 5 factores parciales
  3. Encontrar los inversos multiplicativos para esto usamos la función pow de python que usael algoritmo de Euclides tenemos que encontrar el inverso de cada factor parcial modulo su llave publica
  4. Encontramos la suma total multiplicando cada factor parcial con su llave publica y su inverso y luego sumando todos los resultados
  5. Sacamos el modulo entre la suma total y el modulo total
  6. Finalmente hallamos la raíz quinta del resultado anterior
from sympy import factorint

factor1 = int("0x6133FE46AB8D769AF3240863E738E653B9B8DAFFE5FC66FD1C8934CA3B836B996C9F50CE9DE6F9B4E186F1C0870088299C138C035419C3DB46AFAEFEB8760A9C39CF97A7FFA04DF27C7B7A6AD97004E19E622594AE3E119F22DF8925615C277E1C3AD358D0824202ED4869213F249A49EEFD8BDCF0295EE67DD54422276156B1", 16)
factor2 = int("0xA4466FC1E0B658CC2D0FD65D95FEF665F190B54F6E618B314991709A8C2D355C0CA0720319FC32D9FA981397BB39E7E6350F01ED8E402A02CC75B1F24091E06033BDE2AAEE92D684FA3F93CF6AE0967346B4FBDF541B6E2E917705B145E159641C58B785BB831A3911FB3F610C22ADED90B162814480607CFCE8656A8D6294E5", 16)
factor3 = int("0x8A9D9F89ED124D80FE4FD5700AAD4895135AF503A8EDE3F147D09DF11291F0C40E4E0E35BE8E3EF869C179874C48BFA2F18ABE98EABED94A842913AC81D5E83DB61195FB049F97C740A30DACA3CC30A92DC390C1040DEC659E1D75B5050182A5715677D0A229880BDFEAE768C42959196DEBD68EC307F2D850CD7532436F307F", 16)
factor4 = int("0x8A0934A7F4AE83771B8DDC8BF68D88ABD52E7A34D39C71879D96078A42861E2756DEA873A9E737FBE7B283F8C0930A14AF64441D855C50232A1251BE862055AB8F0396F731CAF10704D1F670BE3E6AAC100E0533BD003F3730977EA0CA9B23A59086316E5412D238517C2CF4029E20DCBA6279F6DFF0D2B66FC1142ED26B0043", 16)
factor5 = int("0x7B236E040721A508E3EE2DA52E74059153264EE15D1D2F715EB4A8307F2713D85C45915174957A52DF9890925C639FB796230BB914FB4E49D8C739AFB8150BD5839F4A14D402855A2FBA9BC275FA6468E11D1578A83BDFF5321E08568BE9E6A22B398614AF830C5A0D88CF12FE4133D51888C80D3178607D8BD8E88594C30D69", 16)

modulo_total = factor1 * factor2 * factor3 * factor4 * factor5

modulo1 = modulo_total // factor1
modulo2 = modulo_total // factor2
modulo3 = modulo_total // factor3
modulo4 = modulo_total // factor4
modulo5 = modulo_total // factor5

inverso1 = pow(modulo1, -1, factor1)
inverso2 = pow(modulo2, -1, factor2)
inverso3 = pow(modulo3, -1, factor3)
inverso4 = pow(modulo4, -1, factor4)
inverso5 = pow(modulo5, -1, factor5)

resto1 = int("0x39BF978193DE4C6311E7189B96F280AF4C58990E7C862BD39C7E72AFA6C8BCED6E0A39FD4D9FC165EC86A5ED7F0A09FA6CB15B589B9B2305306C957BDBBB0E68610BFBBAC7E8839211ED1E523B75BED26FB154F78A5CEC3D25EDE15C815D37E5EFA9D5BD8C732E52B0A181F2E5174A0495CC75F84FB4869467B6815D62A946C3", 16)
resto2 = int("0x311B4C3321CEB87154B4B803041304CFA9BF5BADAE1B61412D8FC9FDAC3FB8DE1AFA9C3EF2909DC57E35068F1BCC6B03940C786B69C9E21EA792377A862EC3F714A05098513FDFDE98D5B439ADDD399F175A4C7520D22338BAE6F4EB202E4A20DE0E7A2738E7CA92D666F415306C4786B03A6523A40ABF12EB2F840A542E1412", 16)
resto3 = int("0x2D167B46D75469596919105E907D378269723F68328C9BA0AD936E2E442F8074120CF1B127ADB30E8ADFC52D1F7309F191F788802A39D6EC8E180C58C362813DB50F9F249507890593872128BB7026B0A8070EF05A99B397CAF686686338DD64FA949E59301D29F6F47B688E6102608BAAE19F5BCEEEDC6B63F508BE19FCE59", 16)
resto4 = int("0x55261A9DE05253D5C4E868B85B3C507C511AB54D2F55F9D7DDEAD5568089CE6E73C32775E75DA73E66E079E15739684CF19D858ED44527C76A40574F947790C9696EFC8082DDB9810400AB5219FBD0215755AD773EE38890746F566EDCD62BBDF66F57BF4D452E03BDDB171A93DBACA3EF9D87F7CA772957C5764ADD2F86B887", 16)
resto5 = int("0x12AC2F94F47114574B72B70F1259BAAB4069F7FA890AA4D11A80FA07409DE9AD652EDA93A01A8D263ADAD83C877B0AFF901F7FF1211D397F26BB512CFD1D05F2D26E656B1F2FF032A453D2724B72A8F177929C6B7E98336C7995BF75CCE04D5D8DC55BD4DDF207FB2FAD7C9ED1A8A70B5F67A8B70A513D0392A3D39454616882", 16)

suma_total = (resto1 * inverso1 * modulo1) + (resto2 * inverso2 * modulo2) + (resto3 * inverso3 * modulo3) + (resto4 * inverso4 * modulo4) + (resto5 * inverso5 * modulo5)

def raiz_quinta_entera(n):
    if n < 0:
        raise ValueError("No se admiten raíces quintas reales de números negativos en este script.")
    if n == 0:
        return 0
    
    # Estimación inicial
    x = 1 << ((n.bit_length() + 4) // 5)
    while True:
        # Fórmula de Newton para raíz quinta: x = (4*x + n // x^4) // 5
        siguiente_x = (4 * x + n // (x ** 4)) // 5
        if siguiente_x >= x:
            return x
        x = siguiente_x

resultado = raiz_quinta_entera(suma_total % modulo_total)
flag_bytes = resultado.to_bytes((resultado.bit_length() + 7) // 8, byteorder='big')
flag = flag_bytes.decode('utf-8')

print(flag)