<- CREWCTF

po1337nomial

7 minutos de lectura

Este reto fue creado por mí para CrewCTF 2025 como miembro de thehackerscrew. Se suponía que sería un reto fácil de Crypto, y terminó con 35 solves. Por tanto, aunque fuera fácil, los LLMs no pudieron resolver el reto directamente.

Se nos proporciona el código fuente en Python del servidor que contiene la flag:

#!/usr/bin/env python3

from os import getenv
from random import getrandbits, randbytes, randrange, shuffle


FLAG = getenv('FLAG', 'crew{fake_flag}')

a = [getrandbits(32) for _ in range(1337)]
options = {'1': 'Get coefficients', '2': 'Evaluate', '3': 'Unlock flag'}

while options:
    option = input(''.join(f'\n{k}. {v}' for k, v in options.items()) + '\n> ')

    if option not in options:
        break

    options.pop(option)

    if option == '1':
        shuffle(s := a.copy())
        print('s:', s)

    if option == '2':
        x = int(input('x: '))
        a[randrange(0, 1337)] = 1337
        print('y:', sum(a_i * x ** i for i, a_i in enumerate(a)))

    if option == '3':
        if input('k: ') == randbytes(1337).hex():
            print(FLAG)

Análisis del código fuente

El código es corto y fácil de seguir. En resumen, el servidor crea coeficientes para un polinomio:

Esos coeficientes son enteros de 32 bits generados con el módulo random de Python:

a = [getrandbits(32) for _ in range(1337)]

Se nos dan tres opciones:

  1. Get coefficients
  2. Evaluate
  3. Unlock flag

Para la tercera opción, necesitamos ser capaces de predecir un valor aleatorio:

    if option == '3':
        if input('k: ') == randbytes(1337).hex():
            print(FLAG)

Es decir, necesitamos encontrar el estado de random. Sabiendo que el módulo random de Python usa un Mersenne Twister como PRNG (MT19937), podemos romper completamente el PRNG con 624 salidas consecutivas de 32 bits. Por lo tanto, si conseguimos los coeficientes del polinomio, podremos hacerlo.

Para la opción 1, se nos dan los coeficientes del polinomio, pero están desordenados de antemano…

    if option == '1':
        shuffle(s := a.copy())
        print('s:', s)

La última opción que podemos usar es la 2, que nos permite evaluar el polinomio en un valor dado (pero una sola vez):

    if option == '2':
        x = int(input('x: '))
        a[randrange(0, 1337)] = 1337
        print('y:', sum(a_i * x ** i for i, a_i in enumerate(a)))

Bueno, no nos permite evaluar el polinomio original , sino un polinomio ligeramente distinto , que es con un coeficiente aleatorio reemplazado por .

Solución

Como idea inicial, podríamos simplemente enviar , de modo que obtenemos todos los coeficientes en el orden correcto codificados en 32 bits de salida. Como cada coeficiente es menor que , si tomamos el resultado como datos binarios, cada trozo de 32 bits será un coeficiente. De hecho, podríamos usar algún valor mayor que y obtener un resultado similar.

Al final, estaríamos encontrando la representación del resultado en base . Así podríamos encontrar usando módulos y divisiones enteras por . Algo así:

# y = P_r(x = 2 ** 32)

a = []

while y:
    a.append(y % 2 ** 32)
    y //= 2 ** 32

En realidad, esto funciona para cualquier valor . Sin embargo, no podemos usar este enfoque porque:

$ python3 server.py

1. Get coefficients
2. Evaluate
3. Unlock flag
> 2
x: 4294967296
y: Traceback (most recent call last):
  File "./server.py", line 27, in <module>
    print('y:', sum(a_i * x ** i for i, a_i in enumerate(a)))
    ~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ValueError: Exceeds the limit (4300 digits) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit

Con este error, el enfoque anterior no es posible, porque si , entonces , por lo que excede el límite de 4300 dígitos. De hecho, podemos estimar cómo de grande puede ser :

El valor anterior es solo una aproximación para una cota superior, pero podemos elegir cualquier valor más pequeño y en la práctica no importará demasiado. Por ejemplo, tomemos , porque sí. Vemos que funciona:

$ python3 server.py

1. Get coefficients
2. Evaluate
3. Unlock flag
> 2
x: 1337
y: 8341833498164406851859511723485532492144044121890096123808371275842866143072981211564622585813085734806038617341091619431630821216144977429721087817320854596298998100242341854704975851643066272629398875973084729360714909915793291787511688807764431115950599657825740747114564842749623871907121416403272464061787801093029612032273153278612289938841264056839861480473195281413009286884084050454458297046332058978721451877325542918423798525512707286538591801958226795221755336331585404476833603390262814462215721893822018466103258278455295313753522997854802835424317936883130594094211800115846166648656826342221201595298542796335441301442028347613988957634133485821265194803105313122072849438384155036461313696334182769023310003400924067017252506427534973325543137621919337927051534434129198932977704594550587852098491618029373740017677641301484795258875811620328631402106635442712988144672490757063445441128870676061556375044914032940065975195876416976945664936182715147429290774415824944653578523951474494732618211388603878643719051545997190473173763400008245194261517901142751302725926932693384851151020410487711563698436899646144403790297969095138123026307706777063652997187416089284520828544858415118240868146421981543038597650832613586987960804884538120131805001769030493552124750021225975976470583940792117473632439130086658129206421412246678927384081084938677840225654776013753818937180102253155977646365003792131321004449082243986381400088405734307120222905399288939447920372422580893094892527527193000814930922051760864830526194048309324176460795555088279650639866424885345516677808733383967350679471352688119556059066734668307404106000196403342240555598340629253151044573487926952103444459176336011377011278121462073412988432250027076974985286126327294299836598698492325134304864571324671097532386010377716739347911007189765866560876438621497382188480889207251365704190817409289427569184995159824366986069565296937689170960033978015103434807183928851096321447217172884458089864195396963748636198311047057893851679433373337188458857268176193266995276297902241870380091491852118308008528947404555949818900271915001021928342539944748615991605870950452006140137016815606208864886682073698258401738216887391664304887820221975234502509484143258473977120662852998417719539611679426390315945520848824457976439675973000324446276390608310273404350065812685059720796210592391142465358808939862105957139438551194069775858886675871638141197556647807632736717019298001153016611658837985517232969418230706229290614126840879737886702257853724221371694754230985806129514063013755237556680818487970722341754345437021457310286097618207451449484654938331980046360026771036843847333355869772738575915508559742080214797029934441831302709194634231347382134610345060787653578816901543235609088712585492809286258779861400980842401356656325564465216166152562987920667604672312533785304449481557225676103423474460852502537417168297250841076791519979146607429108538407427128954435511270545032227820030826755863092297252930172378796994930881388388588555989108291314590645563243150431228405986955317734317173711624745663059861195514987810199555577182509540711942227272494335580064074776353491051025551605628332766781902083854803109750059152942960281455050900326607138973609456400063993965657553570355812939765450188914970753576304840336757233772131194256656656596896691994367042089595991676996219811563174283822635508873334186582769292776353793909265347654705895738236694948019527373248533843953025070861995163509100214912987404845408414561672295110084836442612725096963904794174973750939382844342124763718771189103214552632306985319462192232253882518933152701790602740619778342379157014565334749379478167692203993146135518379437591214717851376996684825120516202590340336644344772556415707329853580635329034419229496207638194296728999651127475079223357976499634465766071149081188240038619368733425939315710382255682392442183394686312938247867646167473630223824990879612913626115848020178768977599276803489208825941597987995086652000157502320551807433269832309412018924210307235116644795184406814103769327245675053222774264298145887213566897309506632838455584815367611896354647907425876811774527919126641808074

Este es el punto en el que los LLMs empiezan a fallar, porque no son conscientes inicialmente del error de los 4300 dígitos.

Backtracking

Nótese que la opción 1 devuelve los coeficientes, pero en distinto orden. Aún así podemos resolver el reto con esta información. Por el momento, olvidémonos del coeficiente aleatorio que se reemplaza por .

La idea es muy similar al enfoque anterior: haremos módulos y divisiones enteras por . Sin embargo, dado que los coeficientes probablemente sean mayores que , necesitaremos considerar más posibilidades. Como resultado, construiremos una solución basada en backtracking. Es decir, seguiremos todas las soluciones posibles hasta encontrar la que sea correcta.

Para empezar, construiremos un mapa que relacione residuos módulo y coeficientes que tengan ese residuo. Sea , a continuación tomamos el valor y buscamos posibles coeficientes con ese residuo . Para cada , lo quitamos del mapa, lo colocamos en su posición de la lista de coeficientes, y continuamos recursivamente con .

Llevaremos la cuenta de la profundidad de la recursión como . En la profundidad , el resultado será correcto si en ese punto. De lo contrario, es incorrecto. Si el procedimiento devuelve falso en algún punto, debemos añadir el coeficiente de nuevo al mapa.

Ahora que tenemos el esquema de la solución para encontrar los coeficientes de teniendo y el conjunto de posibles coeficientes, podemos pensar cómo resolver el reto original, que es casi lo mismo. Podemos obtener y el conjunto de posibles coeficientes de . Un enfoque rápido es probar cada coeficiente, lo que significa ejecutar el procedimiento anterior fijando para .

Implementación

Antes que nada, tomemos los coeficientes desordenados y el valor de :

n = 1337
x = 1337  # Up to 1630 is OK

io = get_process()

io.sendlineafter(b'> ', b'1')
io.recvuntil(b's: ')
s = literal_eval(io.recvline().decode())

io.sendlineafter(b'> ', b'2')
io.sendlineafter(b'x: ', str(x).encode())
io.recvuntil(b'y: ')
y = literal_eval(io.recvline().decode())

a = [1337] * n

Ahora, fijamos los coeficientes barajados de , inicializados a algún valor (¿por qué no ?) y el mapa de residuos:

a = [1337] * n
m = {i: set() for i in range(x)}

Esta será la función para el proceso de backtracking:

def backtracking(i, v):
    if i == n:
        return v == 0

    r = v % x

    for c in m[r]:
        m[r].remove(c)
        a[i] = c

        if backtracking(i + 1, (v - c) // x):
            return True

        m[r].add(c)

Es muy probable que necesitemos aumentar el límite máximo de recursión. Por ejemplo, podemos usar esta línea:

sys.setrecursionlimit(1337 * 1337)

En este punto, podemos iterar sobre todos los posibles y fijar :

for r in trange(n):
    si, s[r] = s[r], 1337

    for b in s:
        m[b % x].add(b)

    if backtracking(0, y) and sorted(a) == sorted(s):
        s[r] = si
        break

    s[r] = si
else:
    exit(1)

Nótese que guardamos el valor original , con , e intentamos resolver con backtracking. Si no hay solución, restauramos y probamos con el siguiente índice . Es raro, pero puede haber situaciones donde no hay solución, porque no estamos considerando coeficientes repetidos. Si eso ocurre, usamos exit(1) y lo intentamos de nuevo.

Una vez que se encuentran los coeficientes de , es solo cuestión de romper random para encontrar el estado correcto (hay varias opciones, randcrack funciona bien), y algunas comprobaciones para asegurar que todo está correcto:

index = a.index(1337)
a[index] = list(set(s).difference(set(a) - {1337}))[0]

rc = RandCrack()
list(map(rc.submit, a[:624]))

setstate((3, (*[int(''.join(map(str, rc.mt[i])), 2) for i in range(len(rc.mt))], 0), None))

assert all(a_i == getrandbits(32) for a_i in a[624:])

shuffled = a.copy()
shuffle(shuffled)
assert shuffled == s

assert index == randrange(0, n)

En este punto, podemos usar la opción 3 y entregar el valor esperado de randbytes(1337) para obtener la flag:

io.sendlineafter(b'> ', b'3')
io.sendlineafter(b'k: ', randbytes(1337).hex().encode())
io.success(io.recvline().decode())

Flag

Con todo esto, podemos encontrar la flag:

$ python3 solve.py po1337nomial.chal.crewc.tf 1337
[+] Opening connection to po1337nomial.chal.crewc.tf on port 1337: Done
 85%|███████████████████████████████████████████████████████▏         | 1135/1337 [00:30<00:05, 37.17it/s]
[+] crew{t0o_much_1337_in_h3r3_bu7_n0_ch33se_a1l0w3d}
[*] Closed connection to po1337nomial.chal.crewc.tf port 1337

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