La revanche du lcg (The revenge of the lcg)
CTF challenge written by me for BreizhCTF 2023
La revanche du lcg
The problem
We are given the source code:
from Crypto.Util.number import getPrime, bytes_to_long
from random import randint
flag = b"REDACTED"
p = getPrime(512)
a = randint(1, p)
b = randint(1, p)
s = bytes_to_long(flag)
def get_random(l):
global a
global b
global s
global p
outs = []
for _ in range(l):
s = (a*s+b) % p
outs.append(s)
return outs
A = [randint(1, p) for _ in range(64)]
S = get_random(64)
print(f"a = {a}")
print(f"b = {b}")
print(f"p = {p}")
print(f"result = {sum([aa*ss % p for aa,ss in zip(A,S)])}")
print(f"A = {A}")
And the following output:
a = 862868879604131826169745055270037800889895077118741291732894229417204384699605050361183411938386849516741978931641117723053981633553714677955754462259622
b = 8017243919415941377873987010057710652148510294165790704820129197602160981783596777652260491373463553980325612358675869426306544737074652759134303989979465
p = 8400966167750377149047743090073687407125000051246680795573698156625676103144147030355064969794750965780110610613038698887256393838549588884846734755683061
result = 273324811664409941759431458175608808697441939503053986558368822531739430404811501915318971699346652650483595596102951195732612489610833267491423545080212735
A = [1844333539659129842412334954508395945066838140502384930240550126527604177624489605422574827393192262182758971715696809655388512605635777218708611870219866, 4008823540945911969235177692677896872089319501181442206887863437667774969797868572919178713495935138199336852316344634747798424110072818111478564630848107, 607731455112959980891762567216191140921144767027056675071901449444539701725186275458917886332968118656022795991241644846110905264238125190176377498873489, 5555176241468154333742651371457065938576807183941299388069465781289751772500804172586441313699657917932950650184044110486080913123464857053195773497834660, 779368670954666836158992495418725470357344297823169203417530054791197407578545859632883743957606399384019268444470982533060124720910867961613346990902914, 6436237163873156363116627199222494954036866615284003311153879696527174133787780051062336267539623719921177648575239217622261842021380431701823690735220046, 7515403165070447069017786289445541679312876684915438921587004433262479403236730413425818380345322376882358155807097601044781293036381104659545020749235474, 3505211257452507188415964931693841630812113629877968849553317052167241033025520974966457343564529824428034684502554663532992009422384817390996628144974941, 2873788588565785898050962966912246578112227950537066280279685611314439298312071309932962096593157275472709458259413681214183576689412724862291919253426754, 8300623922347761463229064406445126904087803984263429739362199625037312897678107261138245763625795450909791906555455000495738929740265708299515368339842623, 1514488759911699116214590493743791698618766088063627108213509338079178231553073184069985651011843979630309352464054647006578396010725939425610000834924351, 1394432164668379597576194213619796939989201503862147063985171777366659579631896673742288336943110407903164368811583948902506585052382548863277609727620526, 2596706979197303523553273716376706441425248680469278687771291843573691078138166956047516993787936048321121053565721687891104848833940313770352739005180446, 7785416268363947115348507856181921144372616996632168359914059299263303705518378644590615414594550787436295515030751855636122432069347243448911310074720684, 4385973805533493006758751373711441168198189245103588474699888987784640360733389416196626590388717352159475511637382087803602272686160982352465658708600642, 3254027433348792357396550731109449119202046394528270614939979764258580691344592179645092669356533679652545375598380710326360465000558006928866348873727931, 3764412699144502492486698662296198950192727611252705246170078401863550704545591114177197146965630759597828795672334040735163040639510077967917412201028246, 5627672152784015098570241358390517715457588660798216031534205788434528637422108318156743635874702667975453208772724914547525651265376607235827583080628224, 707651855759291829285672384070194982317209234119828816344216388395097834392287130940558994364858360367899206090346176710273686042235161208253244549822130, 5764997332985181348057189598064295779357112563965975888837370444536286992145339598962514484297318074557238033025045146579421797369412491268230306688179330, 6809841751342221824054085795412756731766576986406620670198383643102057652429594439092196972396795643810767696559105031704272281833960755810335682374005731, 585264356647655251985764850452387832381497105181328149584489851690474305212616503664503530634107644680077498856509520625263507068612925927162708241330591, 4324292640415274088081635195758885629531688248497023190633262146338948402499808509101915539639332956890652349554253311693771618810177662287659066118578870, 7466391663244007585802393340578179366202737884894045363748363935964239334177289061972416981676672239156331617276588665129268329290309914316561914386876210, 4815385756757696324994147647876685965998052035545919539135996863368343501612189364021602267724055791026992560679221998408190576417444186507448359602321331, 1452531947889334619647798065092823500877989939426441444625174635428931583478755663984661263072428075981643648132363148342311904891149406664355618224399405, 2686781049586209347999309081719112629309242462735337419637715864303073993895818428475990246034131046708907575993661808032606816334169787246178504346623075, 6948951102634062228054930833315147688615387910527786579377490632698587520242935670046510193047410925573785007025878245516194766968642338489250731978631530, 253339806758109559007499346960657909771371425433388315876141843825927506987178452474039882677872753300663312661124640804840114717177875657392479901399086, 3387008207569664629719264621047815709765354861599286167396490666162534861120473006105508082617907774091271688341821991087904278507404798854609041034712022, 2251642318175099708242588928012906253440804441236467227015324859033222275381484173848767995857868166751843350557774877095020933365468048689679034657040544, 7542121842039567019022038354205285036100204687811304613510277585092685787013165512104537924873801838584037610683172422521056925175991022966277774875453865, 1267761452192190077170583799836761442647634006387698253267447884102232708718476167634381488689053952489377695268354893932020607324045275106359774662738291, 2092131361025279611668953124168115425039163446122066417257140739247791766439222465608089517635600033422858659415896142552113543086593820893923379784249967, 5546337216619763718414026770854166501153149129524456122266498526659557299796202956009980059310018285150474710089626357130369848660494406015995748340715381, 1305348868041405678053230189421027912183239916630251073125987652860379985296859623812826508351665993980515688786363199961259530013054123481490508365558111, 8193664134717217497168661530406849166591203134906660080122184676201980536938385438034541731531658066207248787654792761446338520881451644012065923080539811, 2386796048124776387279791549839385615743432830137660234496200822669901691328928164566066744345193750148175005002685093815005880049360118011514427503261486, 135119166156472395873813779806528957860686252997211626678079224360922425248415358863199918199304554334734226594424027578197989001668238915257965089554333, 1303351713766959855193427586451806416095394581469428837540944867387555239644951576760453928153112447575320869478751889908256051744196690755148740333965943, 8299266656186572951922165574721970009556927525883891741599680391600383253379723772450104523033954197574319081461949405807739758726418789084938088369438215, 2801671011815785344902425816680680201252064332055027409844293489504323431304042064575947299013228267971950223522187580896068261152924719453746718368928018, 7798669493943806172409572646816130920404104147205713646824274437467589330460691039524014853497776378274627873167021990908285662060195416090723523266047779, 3996617892602719071574860944738789379527453835367745374887168539729593050510465846338439525126591421298828242417572713654758802804485749748724115913237853, 5054707591208703963366971917222743093130902121146067484847728461919403697245086036185050177749692790869371693058456730096573273704150702478710660411428864, 1204266924813545814409948829120892435912113121681311748807997574663550709031997650045618590045857663528921921091211404846790760340885537090672354276313708, 3760140045914066659077094720304771679600752085924904979136152672955411455331751180570918541443775574808981706774083746356015825791975883025871768722800802, 1155543816564589565362006258839807733627938031135059453579844073897109254098948243406662571767424674532068598342470433934130132751576326104227611055715352, 7964514680141874050854141272501445036348305790503139732147460036802161124269054368374556674186117260409749177284875734736621515844997339518106339099752634, 7459059845760837278170772213502255637949793564180723342206636856005423634782500130468630320019066008626341812774015096860388376388262924460604897109453923, 5711165796570875247162646759891614844808921584240851821323309456277094156044104957141636838752836149152200519144589242848595688992784391554517740402090117, 5833343726061465159371263969344288881346503346032098768788082812430870291851059186196757009580383804982368577326348425026949740591292465100619016381816718, 3233085178391198190724037874288443319514302206602337773175922166952656193596036377938108767748457982297247138198325547333993815507884206785425300084590074, 5683143316315314085401667944714734804523736841534601400764423485238643852288748772583664311034400591819811788984007078049321455711256937701318449795397146, 3431528437778782771530622658919149925810753585234510710343970430859674784992337604868069078988942612605515080384238560028558964091961579241646951862349924, 6180814982573448388647440902640003683386343492057074100254551998135821569422233051229344161528652628516865910333621707752192544576316153898088284360668052, 1674243238892218505755310003367660530203588947774751859280001433605413064796478745485864869582988309336132434921123540534155207538872313431586661925652761, 3577801540921271708175279540029340797401941788515413858569459002662906713674350063483498706040186294396390625394617774930210680062632082665584697970620934, 5795366045412023660451612914253337208266696081566518603015326279845230159681057069770035771293399556762896189587754323505626059931687724824701492255812269, 6762306962550147845195443129809694293118768101318158499355639070235641412417297562919293715150537771611625784456223304380535073490897239348735059920398727, 2861409408814399873845720365857132648952939701083069919922659251249629441529467230693728263199071730147240455723280642141876631863300685287934175407353181, 7489313553811535560734867088150875342425784309794088163874530709515207136332584932010759585061246694590853750786941310076269240142099656604627833606429858, 5806749504162775227384347195053735695150896022266277708163057528330217147979323881188389022350414511587363888566131185420670511026370135494854219025816561, 6558818192655940016001387664871783454852942233378566180212657129301521842186741962545219213885870110493080602133812652193297741631862364858356331137412791]
The solution
So the program is computing two random vector A and S and it gives us their product as well as A.
The vulnerability lies in the creation of S because it is the consecutive outputs of an lcg, which is really bad. Our goal is to recover the seed of this generator and we will do so.
Viewing this as an equation:
S = [a*s+b, a*(a*s+b)+b, a*(a*(a*s+b)+b)+b, ...]
We already know a and b so the only unknown is s, this means that the result if only composed of known values except s because we know A. So we can compute those values and then compute s.
Script:
from Crypto.Util.number import long_to_bytes
a = 862868879604131826169745055270037800889895077118741291732894229417204384699605050361183411938386849516741978931641117723053981633553714677955754462259622
b = 8017243919415941377873987010057710652148510294165790704820129197602160981783596777652260491373463553980325612358675869426306544737074652759134303989979465
p = 8400966167750377149047743090073687407125000051246680795573698156625676103144147030355064969794750965780110610613038698887256393838549588884846734755683061
result = 273324811664409941759431458175608808697441939503053986558368822531739430404811501915318971699346652650483595596102951195732612489610833267491423545080212735
A = [1844333539659129842412334954508395945066838140502384930240550126527604177624489605422574827393192262182758971715696809655388512605635777218708611870219866, 4008823540945911969235177692677896872089319501181442206887863437667774969797868572919178713495935138199336852316344634747798424110072818111478564630848107, 607731455112959980891762567216191140921144767027056675071901449444539701725186275458917886332968118656022795991241644846110905264238125190176377498873489, 5555176241468154333742651371457065938576807183941299388069465781289751772500804172586441313699657917932950650184044110486080913123464857053195773497834660, 779368670954666836158992495418725470357344297823169203417530054791197407578545859632883743957606399384019268444470982533060124720910867961613346990902914, 6436237163873156363116627199222494954036866615284003311153879696527174133787780051062336267539623719921177648575239217622261842021380431701823690735220046, 7515403165070447069017786289445541679312876684915438921587004433262479403236730413425818380345322376882358155807097601044781293036381104659545020749235474, 3505211257452507188415964931693841630812113629877968849553317052167241033025520974966457343564529824428034684502554663532992009422384817390996628144974941, 2873788588565785898050962966912246578112227950537066280279685611314439298312071309932962096593157275472709458259413681214183576689412724862291919253426754, 8300623922347761463229064406445126904087803984263429739362199625037312897678107261138245763625795450909791906555455000495738929740265708299515368339842623, 1514488759911699116214590493743791698618766088063627108213509338079178231553073184069985651011843979630309352464054647006578396010725939425610000834924351, 1394432164668379597576194213619796939989201503862147063985171777366659579631896673742288336943110407903164368811583948902506585052382548863277609727620526, 2596706979197303523553273716376706441425248680469278687771291843573691078138166956047516993787936048321121053565721687891104848833940313770352739005180446, 7785416268363947115348507856181921144372616996632168359914059299263303705518378644590615414594550787436295515030751855636122432069347243448911310074720684, 4385973805533493006758751373711441168198189245103588474699888987784640360733389416196626590388717352159475511637382087803602272686160982352465658708600642, 3254027433348792357396550731109449119202046394528270614939979764258580691344592179645092669356533679652545375598380710326360465000558006928866348873727931, 3764412699144502492486698662296198950192727611252705246170078401863550704545591114177197146965630759597828795672334040735163040639510077967917412201028246, 5627672152784015098570241358390517715457588660798216031534205788434528637422108318156743635874702667975453208772724914547525651265376607235827583080628224, 707651855759291829285672384070194982317209234119828816344216388395097834392287130940558994364858360367899206090346176710273686042235161208253244549822130, 5764997332985181348057189598064295779357112563965975888837370444536286992145339598962514484297318074557238033025045146579421797369412491268230306688179330, 6809841751342221824054085795412756731766576986406620670198383643102057652429594439092196972396795643810767696559105031704272281833960755810335682374005731, 585264356647655251985764850452387832381497105181328149584489851690474305212616503664503530634107644680077498856509520625263507068612925927162708241330591, 4324292640415274088081635195758885629531688248497023190633262146338948402499808509101915539639332956890652349554253311693771618810177662287659066118578870, 7466391663244007585802393340578179366202737884894045363748363935964239334177289061972416981676672239156331617276588665129268329290309914316561914386876210, 4815385756757696324994147647876685965998052035545919539135996863368343501612189364021602267724055791026992560679221998408190576417444186507448359602321331, 1452531947889334619647798065092823500877989939426441444625174635428931583478755663984661263072428075981643648132363148342311904891149406664355618224399405, 2686781049586209347999309081719112629309242462735337419637715864303073993895818428475990246034131046708907575993661808032606816334169787246178504346623075, 6948951102634062228054930833315147688615387910527786579377490632698587520242935670046510193047410925573785007025878245516194766968642338489250731978631530, 253339806758109559007499346960657909771371425433388315876141843825927506987178452474039882677872753300663312661124640804840114717177875657392479901399086, 3387008207569664629719264621047815709765354861599286167396490666162534861120473006105508082617907774091271688341821991087904278507404798854609041034712022, 2251642318175099708242588928012906253440804441236467227015324859033222275381484173848767995857868166751843350557774877095020933365468048689679034657040544, 7542121842039567019022038354205285036100204687811304613510277585092685787013165512104537924873801838584037610683172422521056925175991022966277774875453865, 1267761452192190077170583799836761442647634006387698253267447884102232708718476167634381488689053952489377695268354893932020607324045275106359774662738291, 2092131361025279611668953124168115425039163446122066417257140739247791766439222465608089517635600033422858659415896142552113543086593820893923379784249967, 5546337216619763718414026770854166501153149129524456122266498526659557299796202956009980059310018285150474710089626357130369848660494406015995748340715381, 1305348868041405678053230189421027912183239916630251073125987652860379985296859623812826508351665993980515688786363199961259530013054123481490508365558111, 8193664134717217497168661530406849166591203134906660080122184676201980536938385438034541731531658066207248787654792761446338520881451644012065923080539811, 2386796048124776387279791549839385615743432830137660234496200822669901691328928164566066744345193750148175005002685093815005880049360118011514427503261486, 135119166156472395873813779806528957860686252997211626678079224360922425248415358863199918199304554334734226594424027578197989001668238915257965089554333, 1303351713766959855193427586451806416095394581469428837540944867387555239644951576760453928153112447575320869478751889908256051744196690755148740333965943, 8299266656186572951922165574721970009556927525883891741599680391600383253379723772450104523033954197574319081461949405807739758726418789084938088369438215, 2801671011815785344902425816680680201252064332055027409844293489504323431304042064575947299013228267971950223522187580896068261152924719453746718368928018, 7798669493943806172409572646816130920404104147205713646824274437467589330460691039524014853497776378274627873167021990908285662060195416090723523266047779, 3996617892602719071574860944738789379527453835367745374887168539729593050510465846338439525126591421298828242417572713654758802804485749748724115913237853, 5054707591208703963366971917222743093130902121146067484847728461919403697245086036185050177749692790869371693058456730096573273704150702478710660411428864, 1204266924813545814409948829120892435912113121681311748807997574663550709031997650045618590045857663528921921091211404846790760340885537090672354276313708, 3760140045914066659077094720304771679600752085924904979136152672955411455331751180570918541443775574808981706774083746356015825791975883025871768722800802, 1155543816564589565362006258839807733627938031135059453579844073897109254098948243406662571767424674532068598342470433934130132751576326104227611055715352, 7964514680141874050854141272501445036348305790503139732147460036802161124269054368374556674186117260409749177284875734736621515844997339518106339099752634, 7459059845760837278170772213502255637949793564180723342206636856005423634782500130468630320019066008626341812774015096860388376388262924460604897109453923, 5711165796570875247162646759891614844808921584240851821323309456277094156044104957141636838752836149152200519144589242848595688992784391554517740402090117, 5833343726061465159371263969344288881346503346032098768788082812430870291851059186196757009580383804982368577326348425026949740591292465100619016381816718, 3233085178391198190724037874288443319514302206602337773175922166952656193596036377938108767748457982297247138198325547333993815507884206785425300084590074, 5683143316315314085401667944714734804523736841534601400764423485238643852288748772583664311034400591819811788984007078049321455711256937701318449795397146, 3431528437778782771530622658919149925810753585234510710343970430859674784992337604868069078988942612605515080384238560028558964091961579241646951862349924, 6180814982573448388647440902640003683386343492057074100254551998135821569422233051229344161528652628516865910333621707752192544576316153898088284360668052, 1674243238892218505755310003367660530203588947774751859280001433605413064796478745485864869582988309336132434921123540534155207538872313431586661925652761, 3577801540921271708175279540029340797401941788515413858569459002662906713674350063483498706040186294396390625394617774930210680062632082665584697970620934, 5795366045412023660451612914253337208266696081566518603015326279845230159681057069770035771293399556762896189587754323505626059931687724824701492255812269, 6762306962550147845195443129809694293118768101318158499355639070235641412417297562919293715150537771611625784456223304380535073490897239348735059920398727, 2861409408814399873845720365857132648952939701083069919922659251249629441529467230693728263199071730147240455723280642141876631863300685287934175407353181, 7489313553811535560734867088150875342425784309794088163874530709515207136332584932010759585061246694590853750786941310076269240142099656604627833606429858, 5806749504162775227384347195053735695150896022266277708163057528330217147979323881188389022350414511587363888566131185420670511026370135494854219025816561, 6558818192655940016001387664871783454852942233378566180212657129301521842186741962545219213885870110493080602133812652193297741631862364858356331137412791]
P.<x> = PolynomialRing(GF(p))
xs = [a*x + b]
for _ in range(63):
xs.append(a*xs[-1]+b)
poly = sum(c*d for c,d in zip(A,xs))
b,a = poly.coefficients()
a = int(a)
b = int(b)
print(long_to_bytes(int(((result-b)*pow(a,-1,p))%p)))
Alternatively in python you can compute the final a and b with this formula : $$ x_{n} = a^n*x_{0}+ \frac{a^n-1}{a−1} *b $$ mod p. You can see that $$a = a^n$$ and $$b = \frac{a^n-1}{a−1} *b $$, everything mod p, link for more informations.
Flag : BZHCTF{cryp70h4ck_b357_cryp70_c0mmun17y}