<- CREWCTF

po1337nomial

7 minutes to read

This challenge was made by me for CrewCTF 2025 as a member of thehackerscrew. It was supposed to be an easy Crypto challenge, and ended with 35 solves. Therefore, even if easy, LLMs were not able to solve the challenge directly.

We are provided with the Python source code of the server that contains the 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)

Source code analysis

The code is short and easy to follow. In brief, the server creates coefficients for a polynomial:

These coefficients are 32-bit integers generated with Python’s random module:

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

We are given three options:

  1. Get coefficients
  2. Evaluate
  3. Unlock flag

For the third option, we need to be able to predict a random value:

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

That is, we need to find the state of random. Knowing that Python’s random module uses a Mersenne Twister PRNG (MT19937), we are able to fully crack the PRNG with 624 consecutive 32-bit outputs. Therefore, if we get the polynomial coefficients, we will be able to do so.

For option 1, we are given the coefficients of the polynomial, but they are shuffled beforehand…

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

The last option we can use is 2, which allows us to evaluate the polynomial at a given value (but only once):

    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)))

Well, it doesn’t allow us to evaluate the original polynomial , but a slightly different polynomial , which is with a random coefficient replaced by .

Solution

As an initial idea, we could just send , so that we get all the coefficients in the good ordering encoded in 32 bits of output. Since every coefficient is smaller than , if we take the result as binary data, every 32-bit chunk will be a coefficient. Actually, we could use some value larger than and have a similar result.

In the end, we would be finding the representation of the result in base . So we could find using modulo and integer division by . Something like this:

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

a = []

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

Actually, this works for any value . However, we can’t use this approach because:

$ 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

With this error, the previous straight-forward approach is not possible, because if , then , so it exceeds the 4300-digit limit. Actually, we can estimate how large can be:

The above value is just an approximation for an upper bound, but we can choose any smaller value and it won’t actually matter that much. For instance, let’s take , just because. We see that it works:

$ python3 server.py

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

At this point, LLMs start to fail, because they were not aware of the 4300-digit error.

Backtracking

Notice that option 1 returns the coefficients, but in a different order. We still can solve the challenge with this information. For the moment, let’s forget about the random coefficient that gets replaced to .

The idea is very similar to the straight-forward approach, we will be doing modulo and integer division by . However, since the coefficients are likely to be bigger than , we will need to consider more possibilities. As a result, we will construct a solution based on backtracking. That is, we will follow all possible solutions until finding the one that is correct.

To begin with, we will construct a map that relates residues modulo and coefficients that have such residue. Let , next, we take the value and look for possible coefficients with that residue . For each , we remove it from the map, place it at its position on the coefficients list, and recursively continue with .

We will keep track of the recursion depth as . At depth , the result will be correct if at that point. Otherwise, it is false. If the procedure returns false at some point, we must add the coefficient back to the mapping.

Now that we have the solution outline to find the coefficients of having and the set of possible coefficients, we can think of how to solve the original challenge, which is mostly the same. We can get and the set of possible coefficients of . A naïve approach is to test every coefficient, which means running the above procedure fixing for .

Implementation

First of all, let’s take the shuffled coefficients and the value of :

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

Now, we set the shuffled coefficients of , initialized to some value (why not ?) and the mapping of residues:

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

This will be the function for 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)

It is very likely that we need to increase the maximum recursion limit. For instance, we can use this line:

sys.setrecursionlimit(1337 * 1337)

At this point, we can iterate over all possible and fix :

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)

Notice that we keep track of the original value , with and try to solve with backtracking. If there is no solution, we set back and try with next index . It is rare, but there might be situations where there is no solution, because we are not considering repetitions among coefficients. If so happens, we use exit(1) and try again.

Once the coefficients of are found, it is just a matter of random cracking to find the correct state (there are several options, randcrack works fine), and some assertions to ensure that everything is correct:

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)

At this point, we can use option 3 and give the expected value of randbytes(1337) to get the flag:

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

Flag

With all this, we can find the 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

The full script can be found in here: solve.py.