ping CTF 2023
Lame Lame Loser [50 pts]
In this challenge, your school teacher dismissed your abilities by calling you a lame loser. Now, you have the chance to prove her wrong by showcasing your skills in solving equations of the form ax + by = 0. You already know x,y! If you get a,b you can decrypt ct.
3db3d601436d200a1696e3bbac06cca9.zip
We’re provided main.py and out.txt. Here’s main.py:
from hashlib import sha256
from math import gcd
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secret import FLAG, x, y, a, b
out = open('out.txt', 'w')
assert FLAG.startswith('ping{')
assert FLAG.endswith('}')
assert x*a + y*b == 0
assert a > 0
assert b > 0
assert x.bit_length() >= 1023
assert y.bit_length() >= 1023
assert a.bit_length() == 512
assert b.bit_length() == 512
assert gcd(a, b) == 1
aes = AES.new(sha256(f'{a}||{b}'.encode()).digest(), AES.MODE_CBC, iv=bytes(16))
pt = pad(FLAG.encode(), 16)
ct = aes.encrypt(pt)
print(f'{x = }', file=out)
print(f'{y = }', file=out)
print(f'{ct = }', file=out)
So, essentially, we are provided x and y and tasked to find numbers a and b of bit length 512 such that \(a*x + b*y = 0\).
For those familiar with the Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL), it is clear that the name of the challenge is a direct hint about this algorithm.
Personally, I had never used LLL before – I had only seen it in various CTF writeups and on sites like Cryptohack. Thankfully, though, I had recently participated in a CTF that included a Knapsack cryptography problem, 1337UP LIVE CTF 2023’s crypto/1-10. Team Weak But Leet published a writeup for it that I gladly utilized as a reference to solve the problem.
I will not try to explain LLL as this is quite literally the first LLL problem I have ever solved and I really don’t know what I am doing with LLL. If you want to know more, check out Wikipedia or sites like this for more info.
Instead, I will try my best to explain what I learned from the 1-10 solution and how I used that to solve the problem.
To run the sage code, I went to https://sagecell.sagemath.org/. Here, I ran the following (copied from the 1-10 writeup):
cs = [8508903290440008966939565321248693758153261635170177499193552423579929500027826696702216711413627480472568726828904707392607240309148374882044455682656477650413559779578913981575195542381602155806438946382809049847521263107908111429547314575039079118614485792613461747911710760754291582134293099750060, 10234293217173095983648586990138462404689872504690765936890158736280331352728086141006820545673419953576281340699793983414878095413526583845311613647542879798224462254801103246845064675391113534349390649562211376117941776588135441368773636568930887968431002105334751994385414474789708434897717472259757, 6001064586644974650131784742218587067958465984737568290249286706923485137083921908971767187010824715217158349948368322929900720010489749231105336650564421771867089333709608235963711368415685056362117910529113580811922176651335662802405504434103542105450330213217418470901029864459362153866361049469621, 5859510800336462649673113647904370677448984650623412649303149431740483580968255760095323745895405406649271411277663981671465673293279417168147656423009231087547991428322779036740050269460373254323377738756038706795196225547099530503996157675637620918729310987613041873955654973230573780794437230183289, 8212120161226957435594246142362544687871307206030517377713172267061914524817671684448986080347503212333314134144272096534190656954277299391948626024244379808998220515649968150824587976113971840005858079163744362874678111323034234960076591622752217194796532407435861854992608669653483268713825154541681, 4292538496747452556903766205458518557016170261915268175117554973221631407580344459540989898488936014316805799620957521118332103032738032797936315597220903773140347787977387271254963436603728977128756213671653297994336981775219965231686927050793105808729293803455246360077380768093287937551667515822737, 8583458084429417950887051233123781099671792568724013361916924355046040863544385972858215904752358387759143712618915109914726815547284050405347634520790328222420443989299783668017365846692013464579110450651166600940834254189911732107856656458621485902792541383514622551498513045029193930072821693821256, 927938350277846540058170699346614173130036388369329189433895716040551556863284640834396837739290832786836335265440745786025530973467859153202044442045287145528583412999497854136387626360287750242048999254798532603013016406637079389023297629455299864761196574249382738851682248453939600976884575974199, 4606866838328488359534883828872534448488908284003992208192170511899852596906485417934690617926601159129473558885893097400239110669875450476234618534668886892219546199419412794765402627731086862572263105282498567494065303352715044800789544479262215220148659740517187562922289802434925672447697743660640, 5696622808956926263797513675882969816326582766528835713485415099018508834817057303528828064039948371652175876967703746446602159940653502950606513683435185458750394450192106019388424601807240033502531431423705043713657847236861816929000927218441444067742560786753091009546483807078198791541719979069795]
s = 605466527953516222016485516214431809590993588699320208021845670703468281059947406248463347211427615855012720451029976981068579151311047123161756448068506197424807516350675172131826275005312472029312861168498961728971558322943730466676859739724928104907194812943584226111451426124864722285484117269190235012612078303171378
n = len(cs) # 10
M = Matrix(ZZ, n+1, n+1) # Create a 11 x 11 matrix
for i in range(n+1):
M[i, i] = 1
if (i == n):
M[i, n] = -s
else:
M[i, n] = cs[i]
print(M)
L = M.LLL()
print()
print(L)
Here’s the output:
Before LLL:
[ 1 0 0 0 0 0 0 0 0 0 8508903290440008966939565321248693758153261635170177499193552423579929500027826696702216711413627480472568726828904707392607240309148374882044455682656477650413559779578913981575195542381602155806438946382809049847521263107908111429547314575039079118614485792613461747911710760754291582134293099750060]
[ 0 1 0 0 0 0 0 0 0 0 10234293217173095983648586990138462404689872504690765936890158736280331352728086141006820545673419953576281340699793983414878095413526583845311613647542879798224462254801103246845064675391113534349390649562211376117941776588135441368773636568930887968431002105334751994385414474789708434897717472259757]
[ 0 0 1 0 0 0 0 0 0 0 6001064586644974650131784742218587067958465984737568290249286706923485137083921908971767187010824715217158349948368322929900720010489749231105336650564421771867089333709608235963711368415685056362117910529113580811922176651335662802405504434103542105450330213217418470901029864459362153866361049469621]
[ 0 0 0 1 0 0 0 0 0 0 5859510800336462649673113647904370677448984650623412649303149431740483580968255760095323745895405406649271411277663981671465673293279417168147656423009231087547991428322779036740050269460373254323377738756038706795196225547099530503996157675637620918729310987613041873955654973230573780794437230183289]
[ 0 0 0 0 1 0 0 0 0 0 8212120161226957435594246142362544687871307206030517377713172267061914524817671684448986080347503212333314134144272096534190656954277299391948626024244379808998220515649968150824587976113971840005858079163744362874678111323034234960076591622752217194796532407435861854992608669653483268713825154541681]
[ 0 0 0 0 0 1 0 0 0 0 4292538496747452556903766205458518557016170261915268175117554973221631407580344459540989898488936014316805799620957521118332103032738032797936315597220903773140347787977387271254963436603728977128756213671653297994336981775219965231686927050793105808729293803455246360077380768093287937551667515822737]
[ 0 0 0 0 0 0 1 0 0 0 8583458084429417950887051233123781099671792568724013361916924355046040863544385972858215904752358387759143712618915109914726815547284050405347634520790328222420443989299783668017365846692013464579110450651166600940834254189911732107856656458621485902792541383514622551498513045029193930072821693821256]
[ 0 0 0 0 0 0 0 1 0 0 927938350277846540058170699346614173130036388369329189433895716040551556863284640834396837739290832786836335265440745786025530973467859153202044442045287145528583412999497854136387626360287750242048999254798532603013016406637079389023297629455299864761196574249382738851682248453939600976884575974199]
[ 0 0 0 0 0 0 0 0 1 0 4606866838328488359534883828872534448488908284003992208192170511899852596906485417934690617926601159129473558885893097400239110669875450476234618534668886892219546199419412794765402627731086862572263105282498567494065303352715044800789544479262215220148659740517187562922289802434925672447697743660640]
[ 0 0 0 0 0 0 0 0 0 1 5696622808956926263797513675882969816326582766528835713485415099018508834817057303528828064039948371652175876967703746446602159940653502950606513683435185458750394450192106019388424601807240033502531431423705043713657847236861816929000927218441444067742560786753091009546483807078198791541719979069795]
[ 0 0 0 0 0 0 0 0 0 0 -605466527953516222016485516214431809590993588699320208021845670703468281059947406248463347211427615855012720451029976981068579151311047123161756448068506197424807516350675172131826275005312472029312861168498961728971558322943730466676859739724928104907194812943584226111451426124864722285484117269190235012612078303171378]
After LLL:
[ 15576667888453777051 9334138755964181097 12957505159764460056 16898155541550355097 2519832916018179051 12017458128438555050 9301141344009800099 9598282471907324055 3841003313243362102 3845782042269268054 0]
[ 143234485166780842859046651367 234989931558716103347824799541 62730242319230426379500393811 -162429646043625451064258104233 680901177070828817123034065029 -132176952007449430540855651488 135106359653934382753717950541 -177715971726922509447414708035 27139233524714946174074697659 -591571225883926489532427857971 -280656063972964439004683758034]
[ -418205457754768360600177287824 -845371432025915026389570434606 398096059303976903282749153576 142554790876373083637452751623 -370205611713184095025244148999 331397018736178436905054408086 -50619135383891007139859698676 396313974128223351950362391590 268553561476840229112725237064 -149906927347277354018722159961 -498054743278234861339130867263]
[ 626585610894981190674884084361 219004760017444726618752798033 -857373625198470876037336563507 328257581258548053603308661355 246540613532096504789437247931 -147828470581236265328164047490 -531987313903291697195160593136 -157042842794933333468168557041 13434218536678280038948755423 342518088417071812660252624060 -320767886680894833147336445139]
[ 671772930251277587515726886808 -236280777229428231801281263433 156517458315829771301806051822 -56695236008151921074805378602 494992051719302953226242712970 -346058275342896815456868716343 -422513616577404360024928599440 162219328687518732911303602013 -755052902976732939312404091713 -297494999962007247533975151317 490060551876004584504320149648]
[ 321209065509999633628737897395 -581681492241188032551232305748 -451595861005488058040039659037 -117643678501465876709086979122 -824859439193939712058045158875 686188015226904924679228786337 503022352415891847397542107516 -303812817820067406803864024453 160654430918013955231128897268 -73263910329123588789252242542 -726537681120324108498842683370]
[ 218521799649335191138366531615 615426005367155391144342080712 -711269726079724056426684650969 502000698398487040721075252064 159570995188126873852779932298 -689624502908963929346448021152 -397566271712987294139105529753 393704128165047002475809482012 539323176990145777754012774991 -697408758424504892900628196582 289440162360880452403415746389]
[ -347301497766310282098293856598 687778474073470736517064915562 -506357217866762184258104278914 -593758668337742824049412367438 -224387617959780242617574774368 274001474337576975238016393393 867545338156829103026184899604 619437634286116135379228251344 -585810944799875230509317919987 284091402093988809651862729344 -59443562418326122471883353893]
[ 215922993948481390676390519894 530637556707752462042524649550 -167667498000161994891204976185 265753167991172641231358869358 537988936296629176289322334639 476200527105072468296357277518 -1432397581065429746115449102106 -234529231860199053403657653898 60680919600862306499322503123 -616784514122604798687307294651 488767281712058662671983504875]
[ 1151294257627216284568461714933 -3652011249812476933461288001 -426043141253732161360527009157 -997723492812939439773002242751 -76283618575448909681435959373 -349633358114573244404358244138 107883930315460984535569679942 664847073805002707322303859539 518065531466680472736648276993 -129985486725299991042098265438 -320073600181962774921731797925]
[ -123596687842001840102860713529 1125761075740867887835617224150 778098823773443144803655712000 27124097772591850618521761375 -499599678894029486352160200828 -502505876378710923283238156423 -530857036839219816913456241820 -228028871873954873088605554897 -806474650731425732983393337552 -416473827950919075030505465108 -266073459941462707613321165719]
So, in short, the 1-10 problem asked us to find ten numbers \(x_1, x_2, ... x_10\) such that \(x_1*a_1 + x_2*a_2 + ... + x_10*a_10=sum\). And it is solved by creating an \(n+1\) x \(n+1\) matrix. This matrix has an \(n\) x \(n\) identity matrix beginning from the top left. The right column is filled with \(a_1\)-\(a_10\) except for the last row. The last row is filled with 0’s except for the last column. And the bottom right cell is filled with \(sum\).
At the end, our answer is the first row of numbers.
So, how can we translate 1-10 to this CTF’s problem? Well, first of all, I set up my matrix and did the same process as in 1-10 to get my matrix after LLL:
x = -74337111560408261770627327061677963299443114676921962193623077431929781105956693046458392735870264364007813650987534298743547687856228598375660321312737669922256322002836807209358272704779543549572555337507638951640423224736617988565507790110400638507902597678361464029732843617458061469432050977431403357467
y = 80004460393622006505206154227738652408980554199718416840470313398850884843675954680175518476630032820510826586724696390191570583297462980502959681243903214031598679172479920755464717427554287271300097926852452366085494286842499533040579721141160507448286612025375713562688645031383081188938949474253051185921
m = matrix([[1, 0, x], [0, 1, y], [0, 0, 0]])
print(m.LLL())
Note that the bottom row is all 0’s because our sum is 0.
The result:
[ 0 0 0]
[ 5014526026192881989783190873271900350110917622867226073123096879853252155808388245894593890765436587655767519322163190226506893891526453579207444174709165 4659307478578882117119542330564525027110928001838949425296728038400291804851326604446285835872789263437836209451256282588436352861792769182920204819264654 7811189218064465966877286369963583255431267944671226393701662831241667880826922286897170699699611741477276138732194725892195206893294880565426452601651279]
[-5227763356402090684852663128511334196132940926614703928302130381731596313404060833458098883611797594122280571811024958605184275044782288437849336845957634 -4857439521800177894241889800351396713557216567740046681106520000848526715883371668635361575785452911347319885174996561452890640848343471419596723390233319 7811189218064465966877286369963583255431267944671226393701662831241667880826922286897170699699611741477276138732194725892195206893294880565426452601651279]
Our first row is all 0’s, which makes sense, as \(0*x+0*y=0\). But that’s not what we want at all. \(a\) and \(b\) must be 512 bits each. Maybe row 2 or 3 works?
I tried doing \(a*x+b*y\) on row 2 and 3, but no luck. Each just produced the value in their final column, which is the same for both, i.e. 7811189218064465966877286369963583255431267944671226393701662831241667880826922286897170699699611741477276138732194725892195206893294880565426452601651279.
After thinking a little bit longer, I realized something. Without loss of generality, let row 2 have values \(a_2\) and \(b_2\), and similarly for row 3. Let the value in their final column be \(s\). Then the following is true:
\[a_2*x+b_2*y=s\;\;\;(1)\] \[a_3*x+b_3*y=s\;\;\;(2)\]Then,
\[(1)-(2)=(a_2-a_3)*x+(b_2-b_3)*x=s-s=0\]There it is – that’s how we can get 0!
Thus, \(a=a_2-a_3\) and \(b=b_2-b_3\). I quickly confirmed that my \(a\) and \(b\) values were correct, and created a script to decrypt the flag!
from Cryptodome.Cipher import AES
from hashlib import sha256
x = -74337111560408261770627327061677963299443114676921962193623077431929781105956693046458392735870264364007813650987534298743547687856228598375660321312737669922256322002836807209358272704779543549572555337507638951640423224736617988565507790110400638507902597678361464029732843617458061469432050977431403357467
y = 80004460393622006505206154227738652408980554199718416840470313398850884843675954680175518476630032820510826586724696390191570583297462980502959681243903214031598679172479920755464717427554287271300097926852452366085494286842499533040579721141160507448286612025375713562688645031383081188938949474253051185921
ct = b'\x9e\xae\\|\x80\xe9\x0br\xa9\xc1o8\x08\xdcy\xbf\x94\x97\x85\xdc\xbf\x94\xe2\xd7\x82\x8f\x81>\xf2\x1fl@+\x85\xe6\xd2}N\xcb\x12Ak\xfb\xc1\xbf\x88\'i</"\xf5\x01+4\x1aF\xb6\xf6\xdce!L\x9a'
a = 5014526026192881989783190873271900350110917622867226073123096879853252155808388245894593890765436587655767519322163190226506893891526453579207444174709165 + 5227763356402090684852663128511334196132940926614703928302130381731596313404060833458098883611797594122280571811024958605184275044782288437849336845957634
b = 4659307478578882117119542330564525027110928001838949425296728038400291804851326604446285835872789263437836209451256282588436352861792769182920204819264654 + 4857439521800177894241889800351396713557216567740046681106520000848526715883371668635361575785452911347319885174996561452890640848343471419596723390233319
print(a.bit_length())
print(b.bit_length())
print(a * x + b * y)
aes = AES.new(sha256(f'{a}||{b}'.encode()).digest(), AES.MODE_CBC, iv=bytes(16))
print(aes.decrypt(ct))
Run the script and get the flag!
ping{135str4_135str4_107v4sz_41g0r1thm_r0cks_sc41ing}
Thoughts
Was pretty excited to be able to solve my first LLL problem. Though I honestly had very little idea of what I was doing, I do at least feel like I could replicate a problem like this or 1-10 in another CTF. Hopefully I’ll soon learn LLL for real :)