Understanding the challenge
In this challenge we are given this sage code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#!/usr/bin/sage
import hashlib
import re
with open("flag.txt", "rb") as f:
FLAG = f.read()
assert re.match(rb"Hero{[0-9a-zA-Z_]{90}}", FLAG)
F = FiniteField(2**256 - 189)
R = PolynomialRing(F, "x")
H = lambda n: int(hashlib.sha256(n).hexdigest(), 16)
C = lambda x: [H(x[i : i + 4]) for i in range(0, len(FLAG), 4)]
f = R(C(FLAG))
points = []
for _ in range(f.degree()):
r = F.random_element()
points.append([r, f(r)])
print(points)
flag = input(">").encode().ljust(len(FLAG))
g = R(C(flag))
for p in points:
if g(p[0]) != p[1]:
print("Wrong flag!")
break
else:
print("Congrats!")
Let’s try to explain it.
1
2
3
with open("flag.txt", "rb") as f:
FLAG = f.read()
assert re.match(rb"Hero{[0-9a-zA-Z_]{90}}", FLAG)
First it opens the flag.txt file and retrieve the flag. Then it validates its format. So we know that the flag is composed of Hero{…} with 90 alphanumeric values inside.
Then it defines a finite field of value 2**256 - 189.
1
F = FiniteField(2**256 - 189)
I will not go too much into details about the finite field. What is important to remember is that all results made in this finite field has to stay in this finite field so it will be modulo 2**256 - 189.
Then a polynomial ring over the finite field is defined.
1
R = PolynomialRing(F, "x")
This polynomial ring will allow us to perform polynomial operations in the finite field F (modulo 2**256 - 189).
We define two lambda functions H and C:
1
2
H = lambda n: int(hashlib.sha256(n).hexdigest(), 16)
C = lambda x: [H(x[i : i + 4]) for i in range(0, len(FLAG), 4)]
The first function, H, calculates the SHA-256 hash of the input and converts it to an integer. The second function, C, takes an input string x, splits it into chunks of 4 bytes, and applies the hash function H to each chunk.
Finally we create our function:
1
f = R(C(FLAG))
We cut the Flag into 24 times 4 bytes. Then we calculate the sha256 hash of each piece of flag. Then we create a polynomial ring over the finite field created before. The coefficients of the polynomial are the hash of the pieces of flag. Since we split the flag into 24 chunks of 4 bytes each, we get 24 coefficients. Therefore, the polynomial has a degree of 23 (since the degree is one less than the number of coefficients).
1
polynomial = hash23 * x**23 + hash22 * x**22 + ... + hash1 * x + hash0
Now we calculate some points using the polynomial ring and return the results to the user.
1
2
3
4
5
points = []
for _ in range(f.degree()):
r = F.random_element()
points.append([r, f(r)])
print(points)
Solution
The idea is to use the points given to find the polynomial. Since the coefficients are the sha256 of only 4 bytes, we can brute force it to find the flag.
To retrieve the polynomial, we can use the Lagrange interpolating polynomial.
Step 1: Retrieve points
First we retrieve some points (At least 24 because we have a 23 degree polynomial).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from pwn import *
from tqdm import tqdm
context.log_level = 'critical' # Set to 'error' or 'critical' for quiet mode
def get_points_with_pwntools(host, port):
# Connexion au serveur
conn = remote(host, port)
# Lecture de toutes les données jusqu'au prompt '>'
data = conn.recvuntil(b'>').decode()
conn.close()
points = []
# Analyse des données pour extraire les points
for line in data.splitlines():
if line.startswith("["):
# Extraction des points en interprétant la chaîne comme une liste Python
points = eval(line) # Attention : Utiliser eval seulement si on fait confiance aux données !
break
return points
def gather_multiple_points(host, port, attempts=10):
all_points = []
for _ in tqdm(range(attempts)):
points = get_points_with_pwntools(host, port)
all_points.extend(points) # Ajoute les points de chaque tentative à la liste globale
return all_points
host = "crypto.heroctf.fr"
port = 9000
all_points = gather_multiple_points(host, port, attempts=2)
print("Points récupérés :", all_points)
with open('points.txt', 'w') as f:
f.write(str(all_points))
We get lots of points.
1
python get_points.py
1
Points récupérés : [[55361619050337373485334130558400312430139828913546101193721322616921549270592, 60459136230272697951319089507478684862723034071104645127149359374359714526868], [113513182871456145987257376498953879500259089849957244863431766355410929017688, 77088970405835611488054255487830361411650679974749003283269275963268988794563], [7675604436237254524147368259051775268028770330676975906489112873885258984774, 88202387666526328341668639270250094561947715971978224140441640632437204237492], [110647041453248341646122618660635208154004737142235068824212258613464323451297, 66890474188249515191060875799508993001490845028308290484780923808199344992900], [81471932851117260515074185394747166702901951903614644011741350519187361177641, 14219946126689514429291357009824564086486334120924720766151841217593508296853], [4350689840210487817942617929437324151098407060375246275512122559074363301222, 94142555077823312039905047019930620431566680283098378091085355654289271791575], [48460088634291497580372355464370161752484931365422300439434672590541993523020, 40872223599375606866306921234664721115914259995806653562924712676303581482787], [109743686064908075863137017692366596453928752753356854008373143618689226607765, 74412349244015678958621850670023025195914079586361806435978670581340664254915], [24154932717080459762802526665199897205637140271267733495556098650682464669335, 37865673089566789614761730883136594020244141473587796855351752685580850401107], [13126575697570085230622233319087972883099047012219956376434244417492718316232, 37209781070654285467127390078798999662408754132152305201452969909254212790072], [31744610063382875205679385751526141292037945522854184154668689748894245954822, 87472182277812250987699377697407598953254455239794138107381018297648026814483], [1442243778481128100385961337568513546954101916792189547573009615769489028109, 47023434988547153391814346516589642745870771224211379040127144021728518334447], [66224139444155648811049285795549351506544805810700053953984909402990896416366, 66404139535976063102640224241434471036665060592976158501399784980757534806114], [41461439613182772683012253295518628291515993709977054701286554068323534846012, 16330295345990736061514805879985347724272646618483594137046111575785970540833], [8124994071570040621229734817566774228784989167162205019618045527667502324007, 1174082109426394102730518553738813773417275575837947918633451526616375197167], [83113692806264696128134116275687348658183450705344835091143639214574822398174, 83421476058663195961650418002891751586836805889359636938922399552090992683204], [28549062372277010041830991620696184488733215028558487496898837291534457531255, 13862927826461560316439595239868835252479650083464344687830155997824206631276], [114541320096289446908092493313176644001493683370922610360910636611095616542135, 64263229271156792025562233883505261636307785827532445676019858162264426666860], [79212865431533533868263801407027824992329043668273173480645325260721492731132, 61765127366965148150628608780992069562912113390598619687060896605551714316614], [6798017878387417925629596479481982297549303328241672350012240787969831772167, 109025232046222777761751333963163133032127278273708152023387340236420044291906], [80487095604823741726531878909195066076724875760829609692066386002501035616651, 62264651607349362655973013244234114751436161721457181588960328546974017484400], [65245026594390116986342410775469939362649372196658717747018551701193166269379, 14146945547298032855977696797081113293961954473383200383619147025786955149147], [73133775860970628781448735251727713792321221549076305609823432389613318089780, 74259615229361298539668304479033365459518382561223200504307724445426025169411], [51291768727881444876901917074968403494731116529820173791904958750677515283671, 64204534720769021970866896533925489335278629743558372203822081530683399005798], [45499897046323593037978952467622006120320704683088367201021967000380763607181, 69571756380007774922668595838554418823215999134574589774840810316832719712978], [48198115884592158947336723948021332032098842339362631533117916829751876011352, 22500174263981691763865142524040235569531911790136740771935526314528282822778], [820672690295088195142022914935130831188660541645931911726394536487858188578, 81309358849274739104577531740652066756488802136195289435550597834613791823297], [93061210273863876343088376623199210055518550220347263220318303371600431308403, 58692783180418387338300133634662574892956621438255132724233767549110253048608], [40450609934438957688362437115278189726137232927610540747485588186657526142790, 89099031285624614753074398803552636846933106937839233694862556304263090354291], [64481140482014752265276689687633350561369017215192248497694249208794690660402, 16976567205669892486187639190833253393035752711850214493674732419007226833264], [47630215123252978823477350207409662022685843857723242111053509079761509793040, 22933456515851416638225620685048682518111706497209913423483653399017740421080], [28144384171633362019447425756568080120294433932404650239591897348830986718000, 85821204339087662915020211768245601216883301411260711641591222603344267089168], [87456957058570678891531244520766332157534715836750778857314175671320015274041, 17286638395604028756906348031805427618051543083962895740548658183158773792373], [87156546338551952946625193161395626354250314098983160966042105585772978726631, 1895716255633054076639826964977444276440980444855005257397268878676914651660], [89494369172505043117721786905747139204211278701311849270455624395433718743688, 74560657083643534110441238026319798797394657571804654494266969864917309323991], [111412853037874820188980373351552469849948432208013412126301404827062624043495, 39280748780352166978393978207738720047733993727467520483093075105997953810753], [83317887276225178669959717366484861828075759895983548068821890394885934967753, 74009104937269263400067277182852586066654988395469124244758383872869547435321], [92221762793277709169750385194639538355575565218286258581367642555210073608700, 17072214279833981797068284601533961555976133125156212217718862543315093006763], [1282850252461400288182247698737685554639273196587966925258261344400287588513, 84114078153740145051584218453071009330351535163884055487340528826393878432364], [50212904159368671056486669100980742670584755925485128093092259125319114411902, 85010909665755060128100927206230886284091392881945467868969800903638547067011], [100626361830225095358779001609417810640983439162808228983903144819006424218941, 114068225673043059329358127041926695430293291429087188831396530541915798398628], [71011664947357150195805234526057824900054367408710871523302237961838815793474, 47356424433933517952105568107301789985079258466876850764049727921682798026163], [102649267875612009562550049843187170048673490081328797702217239006341842452681, 44263965868835237924053802657488783993673018987136487030700050256547888345394], [23252791113155259750701732467588417432864890872068084744435372938070779834861, 50245748246392014348288065043120262007243131665199447408625996679236013683332], [32610831830736173663868293748154509352679934983141253057182768743877757234111, 29724639170834629529011233283985855331941259080651281363796374722472440226177], [47808833375673454234307754438909167034041246126040078202292284870371899417883, 11374823219991361712717962802587951731035448911716915903966262174705688042985]]
Step 2: Find the polynomial
I used Lagrange interpolation polynomial, in sage, to find the polynomial.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Utiliser SageMath pour exécuter ce code
import ast
# Spécifie le corps fini de taille 2^256 - 189
field_size = 2**256 - 189
F = FiniteField(field_size)
# Points récupérés du serveur
with open('points.txt', 'r') as f:
data = f.read()
points = ast.literal_eval(data)
# Calcul de l'interpolation de Lagrange
R = PolynomialRing(F, 'x')
L = R.lagrange_polynomial(points)
print("Polynôme obtenu :", L)
with open('polynomial.txt', 'w') as f:
f.write(str(L))
1
sage interpolation.sage
1
2
sage interpolation.sage
Polynôme obtenu : 91356407137791927144958613770622174607926961061379368852376771002781151613901*x^23 + 58688474918974956495962699109478986243962548972465028067725936901754910032197*x^22 + 71177914266346294875020009514904614231152252028035180341047573071890295627281*x^21 + 9286536496641678624961072298289256247776902880262474453231051084428770229931*x^20 + 48478433129988933656911497337570454952912987663301800112434018755270886790086*x^19 + 105484582062398143020926667398250530293520625898492636870365251172877956081489*x^18 + 91842050171741174464568525719602040646922469791657773826919079592778110767648*x^17 + 43594818259201189283635356607462328520192502107771693650896092861477784342431*x^16 + 66681440692524165569992671994842901187406728987456386756946647843877275534778*x^15 + 7092396080272228853132842491037895182885372693653833621714864119915575351959*x^14 + 115533839068795212658451397535765278473898133068309149603041276877934373391258*x^13 + 32403908412257070302225532346590438994349383666861558172214850130936584778364*x^12 + 15596341609452054024790211046165535925702287406391095849367220616094959319247*x^11 + 98676420105970876355731743378079563095438931888109560800924537433679751968410*x^10 + 4587316730151077745530345853110346550953429707066041958662730783235705675823*x^9 + 4244268215373067710299345981438357655695365045434952475766578691548900068884*x^8 + 78645989056858155953548111309497253790838184388240819797824701948971210482613*x^7 + 10009681240064642703458239750230614173777134131788316383198404412696086812123*x^6 + 16605552275238206773988750913306730384585706182539455749829662274657349564685*x^5 + 42828444749577646348433379946210116268681295505955485156998041972023283883825*x^4 + 78252810134582863205690878209501272813895928209727562041762503202357420752872*x^3 + 54922548012150305957596790093591596584466927559339793497872781061995644787934*x^2 + 37382279584575671665412736907293996338695993273870192478675632069138612724862*x + 51862623363251592162508517414206794722184767070638202339849823866691337237984
Step 3: Brute force each coefficient to find the flag.
- The character set includes digits, uppercase and lowercase letters, underscores, and braces {}.
- Total characters: 10+26+26+1+2=65.
- Total combinations per segment: 65**4=17,826,5625654=17,850,625, which is feasible for brute-forcing.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import hashlib
from itertools import product
import re
# Ensemble de caractères possibles
charset = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_{}".encode()
#print(charset)
# Exemple de chaîne contenant le polynôme
with open('polynomial.txt', "r") as f:
polynomial_str = f.read()
# Expression régulière pour capturer les coefficients uniquement
pattern = r'(\d+)(?=\*x|\s*$)'
# Extraction des coefficients
coefficients = re.findall(pattern, polynomial_str)
# Conversion des coefficients en entiers pour un usage ultérieur
coefficients = [int(coef) for coef in coefficients]
print("Coefficients extraits :", coefficients)
def bruteforce_segment(coefficient):
# Génère toutes les combinaisons de 4 caractères possibles dans le charset
for candidate in product(charset, repeat=4):
segment = bytes(candidate)
#print(segment)
# Calcul du hachage SHA-256 du segment
if int(hashlib.sha256(segment).hexdigest(), 16) == coefficient:
print(segment)
return segment
return None
# Reconstruction du flag
flag_segments = []
for coef in reversed(coefficients):
segment = bruteforce_segment(coef)
if segment:
flag_segments.append(segment)
else:
print("Segment introuvable pour un coefficient.")
break
# Assemble le flag final en concaténant les segments et ajout du préfixe
flag = b''.join(flag_segments)
try:
print("Reconstructed flag:", flag.decode('utf-8'))
except UnicodeDecodeError:
print("Reconstructed flag contains invalid UTF-8 characters.")
print("Flag (raw bytes):", flag)
1
python brute_force_flag.py
1
Flag reconstitué : Hero{th3r3_4r3_tw0_typ35_0f_p30pl3_1n_th15_w0rld_th053_wh0_c4n_3xtr4p0l4t3_fr0m_1nc0mpl3t3_d474}