Fast Carmichael

2 minutos de lectura

Se nos proporciona el código fuente en Python del servidor:

from secret import FLAG
from Crypto.Util.number import isPrime
import socketserver
import signal


class Handler(socketserver.BaseRequestHandler):

    def handle(self):
        signal.alarm(0)
        main(self.request)


class ReusableTCPServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass


def sendMessage(s, msg):
    s.send(msg.encode())


def receiveMessage(s, msg):
    sendMessage(s, msg)
    return s.recv(4096).decode().strip()


def generate_basis(n):
    basis = [True] * n

    for i in range(3, int(n**0.5) + 1, 2):
        if basis[i]:
            basis[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)  

    return [2] + [i for i in range(3, n, 2) if basis[i]]


def millerRabin(n, b):
    basis = generate_basis(300)
    if n == 2 or n == 3:
        return True

    if n % 2 == 0:
        return False

    r, s = 0, n - 1
    while s % 2 == 0:
        r += 1
        s //= 2
    for b in basis:
        x = pow(b, s, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True


def _isPrime(p):
    if p < 1:
        return False
    if (p.bit_length() <= 600) and (p.bit_length() > 1500):
        return False
    if not millerRabin(p, 300):
        return False

    return True


def main(s):
    p = receiveMessage(s, "Give p: ")

    try:
        p = int(p)
    except:
        sendMessage(s, "Error!")

    if _isPrime(p) and not isPrime(p):
        sendMessage(s, FLAG)
    else:
        sendMessage(s, "Conditions not satisfied!")


if __name__ == '__main__':
    socketserver.TCPServer.allow_reuse_address = True
    server = ReusableTCPServer(("0.0.0.0", 1337), Handler)
    server.serve_forever()

Interactuando con el servidor

El servidor nos pide un número:

$ nc 178.62.85.130 30337
Give p: 1337
Conditions not satisfied!  

Ncat: Broken pipe.

Básicamente, el servidor nos mostrará la flag al pasar esta verificación:

    if _isPrime(p) and not isPrime(p):
        sendMessage(s, FLAG)
    else:
        sendMessage(s, "Conditions not satisfied!")

En otras palabras, p tiene que clasificarse como número primo mediante la prueba de primalidad de Miller-Rabin, aunque realmente no es un número primo. Entonces, tenemos que encontrar un número que haga que la prueba de Miller-Rabin falle.

Después de buscar un poco en Internet, encontramos este Gist de GitHub, que utiliza un script en SageMath para encontrar dicho valor.

Flag

En este punto, introducimos este número especial y capturamos la flag:

$ nc 178.62.85.130 30337
Give p: 99597527340020670697596886062721977401836948352586238797499761849061796816245727295797460642211895009946326533856101876592304488359235447755504083536903673408562244316363452203072868521183142694959128745107323188995740668134018742165409361423628304730379121574707411453909999845745038957688998441109092021094925758212635651445626620045726265831347783805945477368631216031783484978212374792517000073275125176790602508815912876763504846656547041590967709195413101791490627310943998497788944526663960420235802025853374061708569334400472016398343229556656720912631463470998180176325607452843441554359644313713952036867  
HTB{c42m1ch431_15_f457_8u7_50m371m35_f457_15_n07_7h3_8357}

Ncat: Broken pipe.