Lame Lame Loser

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:

1
from hashlib import sha256
2
from math import gcd
3
from Crypto.Cipher import AES
4
from Crypto.Util.Padding import pad
5
from secret import FLAG, x, y, a, b
6
out = open('out.txt', 'w')
7

8
assert FLAG.startswith('ping{')
9
assert FLAG.endswith('}')
10
assert x*a + y*b == 0
11
assert a > 0
12
assert b > 0
13
assert x.bit_length() >= 1023
14
assert y.bit_length() >= 1023
15
assert a.bit_length() == 512
16
assert b.bit_length() == 512
17
assert gcd(a, b) == 1
18

19
aes = AES.new(sha256(f'{a}||{b}'.encode()).digest(), AES.MODE_CBC, iv=bytes(16))
20
pt = pad(FLAG.encode(), 16)
21
ct = aes.encrypt(pt)
22

23
print(f'{x = }', file=out)
24
print(f'{y = }', file=out)
25
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):

1
cs = [8508903290440008966939565321248693758153261635170177499193552423579929500027826696702216711413627480472568726828904707392607240309148374882044455682656477650413559779578913981575195542381602155806438946382809049847521263107908111429547314575039079118614485792613461747911710760754291582134293099750060, 10234293217173095983648586990138462404689872504690765936890158736280331352728086141006820545673419953576281340699793983414878095413526583845311613647542879798224462254801103246845064675391113534349390649562211376117941776588135441368773636568930887968431002105334751994385414474789708434897717472259757, 6001064586644974650131784742218587067958465984737568290249286706923485137083921908971767187010824715217158349948368322929900720010489749231105336650564421771867089333709608235963711368415685056362117910529113580811922176651335662802405504434103542105450330213217418470901029864459362153866361049469621, 5859510800336462649673113647904370677448984650623412649303149431740483580968255760095323745895405406649271411277663981671465673293279417168147656423009231087547991428322779036740050269460373254323377738756038706795196225547099530503996157675637620918729310987613041873955654973230573780794437230183289, 8212120161226957435594246142362544687871307206030517377713172267061914524817671684448986080347503212333314134144272096534190656954277299391948626024244379808998220515649968150824587976113971840005858079163744362874678111323034234960076591622752217194796532407435861854992608669653483268713825154541681, 4292538496747452556903766205458518557016170261915268175117554973221631407580344459540989898488936014316805799620957521118332103032738032797936315597220903773140347787977387271254963436603728977128756213671653297994336981775219965231686927050793105808729293803455246360077380768093287937551667515822737, 8583458084429417950887051233123781099671792568724013361916924355046040863544385972858215904752358387759143712618915109914726815547284050405347634520790328222420443989299783668017365846692013464579110450651166600940834254189911732107856656458621485902792541383514622551498513045029193930072821693821256, 927938350277846540058170699346614173130036388369329189433895716040551556863284640834396837739290832786836335265440745786025530973467859153202044442045287145528583412999497854136387626360287750242048999254798532603013016406637079389023297629455299864761196574249382738851682248453939600976884575974199, 4606866838328488359534883828872534448488908284003992208192170511899852596906485417934690617926601159129473558885893097400239110669875450476234618534668886892219546199419412794765402627731086862572263105282498567494065303352715044800789544479262215220148659740517187562922289802434925672447697743660640, 5696622808956926263797513675882969816326582766528835713485415099018508834817057303528828064039948371652175876967703746446602159940653502950606513683435185458750394450192106019388424601807240033502531431423705043713657847236861816929000927218441444067742560786753091009546483807078198791541719979069795]
2
s = 605466527953516222016485516214431809590993588699320208021845670703468281059947406248463347211427615855012720451029976981068579151311047123161756448068506197424807516350675172131826275005312472029312861168498961728971558322943730466676859739724928104907194812943584226111451426124864722285484117269190235012612078303171378
3

4
n = len(cs)     # 10
5
M = Matrix(ZZ, n+1, n+1)    # Create a 11 x 11 matrix
6

7
for i in range(n+1):
8
    M[i, i] = 1
9
    if (i == n):
10
        M[i, n] = -s
11
    else:
12
        M[i, n] = cs[i]
13

14
print(M)
15

16
L = M.LLL()
17
print()
18
print(L)

Here’s the output:

Before LLL:

1
[                                                                                                                                                                                                                                                                                                                                 1                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                      8508903290440008966939565321248693758153261635170177499193552423579929500027826696702216711413627480472568726828904707392607240309148374882044455682656477650413559779578913981575195542381602155806438946382809049847521263107908111429547314575039079118614485792613461747911710760754291582134293099750060]
2
[                                                                                                                                                                                                                                                                                                                                 0                                                                                                                                                                                                                                                                                                                                  1                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                     10234293217173095983648586990138462404689872504690765936890158736280331352728086141006820545673419953576281340699793983414878095413526583845311613647542879798224462254801103246845064675391113534349390649562211376117941776588135441368773636568930887968431002105334751994385414474789708434897717472259757]
3
[                                                                                                                                                                                                                                                                                                                                 0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  1                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                      6001064586644974650131784742218587067958465984737568290249286706923485137083921908971767187010824715217158349948368322929900720010489749231105336650564421771867089333709608235963711368415685056362117910529113580811922176651335662802405504434103542105450330213217418470901029864459362153866361049469621]
4
[                                                                                                                                                                                                                                                                                                                                 0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  1                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                      5859510800336462649673113647904370677448984650623412649303149431740483580968255760095323745895405406649271411277663981671465673293279417168147656423009231087547991428322779036740050269460373254323377738756038706795196225547099530503996157675637620918729310987613041873955654973230573780794437230183289]
5
[                                                                                                                                                                                                                                                                                                                                 0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  1                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                      8212120161226957435594246142362544687871307206030517377713172267061914524817671684448986080347503212333314134144272096534190656954277299391948626024244379808998220515649968150824587976113971840005858079163744362874678111323034234960076591622752217194796532407435861854992608669653483268713825154541681]
6
[                                                                                                                                                                                                                                                                                                                                 0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  1                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                      4292538496747452556903766205458518557016170261915268175117554973221631407580344459540989898488936014316805799620957521118332103032738032797936315597220903773140347787977387271254963436603728977128756213671653297994336981775219965231686927050793105808729293803455246360077380768093287937551667515822737]
7
[                                                                                                                                                                                                                                                                                                                                 0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  1                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                      8583458084429417950887051233123781099671792568724013361916924355046040863544385972858215904752358387759143712618915109914726815547284050405347634520790328222420443989299783668017365846692013464579110450651166600940834254189911732107856656458621485902792541383514622551498513045029193930072821693821256]
8
[                                                                                                                                                                                                                                                                                                                                 0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  1                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                       927938350277846540058170699346614173130036388369329189433895716040551556863284640834396837739290832786836335265440745786025530973467859153202044442045287145528583412999497854136387626360287750242048999254798532603013016406637079389023297629455299864761196574249382738851682248453939600976884575974199]
9
[                                                                                                                                                                                                                                                                                                                                 0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  1                                                                                                                                                                                                                                                                                                                                  0                      4606866838328488359534883828872534448488908284003992208192170511899852596906485417934690617926601159129473558885893097400239110669875450476234618534668886892219546199419412794765402627731086862572263105282498567494065303352715044800789544479262215220148659740517187562922289802434925672447697743660640]
10
[                                                                                                                                                                                                                                                                                                                                 0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  1                      5696622808956926263797513675882969816326582766528835713485415099018508834817057303528828064039948371652175876967703746446602159940653502950606513683435185458750394450192106019388424601807240033502531431423705043713657847236861816929000927218441444067742560786753091009546483807078198791541719979069795]
11
[                                                                                                                                                                                                                                                                                                                                 0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                  0 -605466527953516222016485516214431809590993588699320208021845670703468281059947406248463347211427615855012720451029976981068579151311047123161756448068506197424807516350675172131826275005312472029312861168498961728971558322943730466676859739724928104907194812943584226111451426124864722285484117269190235012612078303171378]

After LLL:

1
[            15576667888453777051              9334138755964181097             12957505159764460056             16898155541550355097              2519832916018179051             12017458128438555050              9301141344009800099              9598282471907324055              3841003313243362102              3845782042269268054                                0]
2
[  143234485166780842859046651367   234989931558716103347824799541    62730242319230426379500393811  -162429646043625451064258104233   680901177070828817123034065029  -132176952007449430540855651488   135106359653934382753717950541  -177715971726922509447414708035    27139233524714946174074697659  -591571225883926489532427857971  -280656063972964439004683758034]
3
[ -418205457754768360600177287824  -845371432025915026389570434606   398096059303976903282749153576   142554790876373083637452751623  -370205611713184095025244148999   331397018736178436905054408086   -50619135383891007139859698676   396313974128223351950362391590   268553561476840229112725237064  -149906927347277354018722159961  -498054743278234861339130867263]
4
[  626585610894981190674884084361   219004760017444726618752798033  -857373625198470876037336563507   328257581258548053603308661355   246540613532096504789437247931  -147828470581236265328164047490  -531987313903291697195160593136  -157042842794933333468168557041    13434218536678280038948755423   342518088417071812660252624060  -320767886680894833147336445139]
5
[  671772930251277587515726886808  -236280777229428231801281263433   156517458315829771301806051822   -56695236008151921074805378602   494992051719302953226242712970  -346058275342896815456868716343  -422513616577404360024928599440   162219328687518732911303602013  -755052902976732939312404091713  -297494999962007247533975151317   490060551876004584504320149648]
6
[  321209065509999633628737897395  -581681492241188032551232305748  -451595861005488058040039659037  -117643678501465876709086979122  -824859439193939712058045158875   686188015226904924679228786337   503022352415891847397542107516  -303812817820067406803864024453   160654430918013955231128897268   -73263910329123588789252242542  -726537681120324108498842683370]
7
[  218521799649335191138366531615   615426005367155391144342080712  -711269726079724056426684650969   502000698398487040721075252064   159570995188126873852779932298  -689624502908963929346448021152  -397566271712987294139105529753   393704128165047002475809482012   539323176990145777754012774991  -697408758424504892900628196582   289440162360880452403415746389]
8
[ -347301497766310282098293856598   687778474073470736517064915562  -506357217866762184258104278914  -593758668337742824049412367438  -224387617959780242617574774368   274001474337576975238016393393   867545338156829103026184899604   619437634286116135379228251344  -585810944799875230509317919987   284091402093988809651862729344   -59443562418326122471883353893]
9
[  215922993948481390676390519894   530637556707752462042524649550  -167667498000161994891204976185   265753167991172641231358869358   537988936296629176289322334639   476200527105072468296357277518 -1432397581065429746115449102106  -234529231860199053403657653898    60680919600862306499322503123  -616784514122604798687307294651   488767281712058662671983504875]
10
[ 1151294257627216284568461714933    -3652011249812476933461288001  -426043141253732161360527009157  -997723492812939439773002242751   -76283618575448909681435959373  -349633358114573244404358244138   107883930315460984535569679942   664847073805002707322303859539   518065531466680472736648276993  -129985486725299991042098265438  -320073600181962774921731797925]
11
[ -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:

1
x = -74337111560408261770627327061677963299443114676921962193623077431929781105956693046458392735870264364007813650987534298743547687856228598375660321312737669922256322002836807209358272704779543549572555337507638951640423224736617988565507790110400638507902597678361464029732843617458061469432050977431403357467
2
y = 80004460393622006505206154227738652408980554199718416840470313398850884843675954680175518476630032820510826586724696390191570583297462980502959681243903214031598679172479920755464717427554287271300097926852452366085494286842499533040579721141160507448286612025375713562688645031383081188938949474253051185921
3

4
m = matrix([[1, 0, x], [0, 1, y], [0, 0, 0]])
5
print(m.LLL())

Note that the bottom row is all 0’s because our sum is 0.

The result:

1
[                                                                                                                                                          0                                                                                                                                                           0                                                                                                                                                           0]
2
[ 5014526026192881989783190873271900350110917622867226073123096879853252155808388245894593890765436587655767519322163190226506893891526453579207444174709165  4659307478578882117119542330564525027110928001838949425296728038400291804851326604446285835872789263437836209451256282588436352861792769182920204819264654  7811189218064465966877286369963583255431267944671226393701662831241667880826922286897170699699611741477276138732194725892195206893294880565426452601651279]
3
[-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!

1
from Cryptodome.Cipher import AES
2
from hashlib import sha256
3

4
x = -74337111560408261770627327061677963299443114676921962193623077431929781105956693046458392735870264364007813650987534298743547687856228598375660321312737669922256322002836807209358272704779543549572555337507638951640423224736617988565507790110400638507902597678361464029732843617458061469432050977431403357467
5
y = 80004460393622006505206154227738652408980554199718416840470313398850884843675954680175518476630032820510826586724696390191570583297462980502959681243903214031598679172479920755464717427554287271300097926852452366085494286842499533040579721141160507448286612025375713562688645031383081188938949474253051185921
6
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'
7

8
a = 5014526026192881989783190873271900350110917622867226073123096879853252155808388245894593890765436587655767519322163190226506893891526453579207444174709165 + 5227763356402090684852663128511334196132940926614703928302130381731596313404060833458098883611797594122280571811024958605184275044782288437849336845957634
9
b = 4659307478578882117119542330564525027110928001838949425296728038400291804851326604446285835872789263437836209451256282588436352861792769182920204819264654 + 4857439521800177894241889800351396713557216567740046681106520000848526715883371668635361575785452911347319885174996561452890640848343471419596723390233319
10
print(a.bit_length())
11
print(b.bit_length())
12

13
print(a * x + b * y)
14

15
aes = AES.new(sha256(f'{a}||{b}'.encode()).digest(), AES.MODE_CBC, iv=bytes(16))
16

17
print(aes.decrypt(ct))

Run the script and get the flag!

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