Verilicious - HTB Cyber Apocalypse CTF 2025

Challenge filesPermalink

from Crypto.Cipher import PKCS1_v1_5
from Crypto.Random import get_random_bytes
from Crypto.PublicKey import RSA
from Crypto.Util.number import getPrime, long_to_bytes as l2b, bytes_to_long as b2l
from random import seed, randbytes
from data import R, s

seed(s)

class Verilicious:
    def __init__(self):
        self.key = RSA.import_key(open('privkey.pem', 'rb').read())
        self.cipher = PKCS1_v1_5.new(self.key, randbytes)

    def verify(self, c):
        c = b'\x00'*(self.key.n.bit_length()//8-len(c)) + c
        return int(self.cipher.decrypt(c, sen := get_random_bytes(self.key.n.bit_length()//8)) != sen)

    def encrypt(self, m):
        return self.cipher.encrypt(m)

orac = Verilicious()

enc_flag = orac.encrypt(open('flag.txt', 'rb').read()).hex()

assert all(orac.verify(l2b(pow(r, orac.key.e, orac.key.n) * int(enc_flag, 16) % orac.key.n)) for r in R)

import os ; os.system('openssl rsa -in privkey.pem -pubout -out pubkey.pem')

with open('output.txt', 'w') as f:
    f.write(f'{enc_flag = }\n')
    f.write(f'{R = }\n')

enc_flag = '723e808e262486bb05c39cef2a4ca2334e885ce90ebf318d6f0ab1d9e95fc9650cf95e7e4d5df2e3afef8aba4796240e958be4cc933cb944a0ec748619cdb9138b11ad0eb2e5f492c6280909e55def3db966cc96eb02f0212be4b33c04f5b4576d2d87a180649b6770dac45fd07d17d0a68bbbed87c0d18cd1610c1d52c25b52'
R = [134115821619995314496122564547916126947599980819405235082517192808507030501092656706168887309982033289987953471348763955476089416556147406160259955040757648917395767651179830169779066153799931136707924690852827516288300826437643041264226686893395744277118552895070277286649305077822610943759606681582403285622, 126686940482640273524125094354894225795941673993143643794156275578369198472583478553784929652753543884124774686804705186877104318595795254647323754005334399647982071651049942560477743142470231462889041407837267742625786144055962080350415361176206007614719875397296238162863188765950829446087586697209194992647, 137700382018057974172801996890791468140252370097114533331144882331394632683850942352930846213387255651807591056575151165151821404724765116419181774183159941114789572865774691939551028712774400221727830866466949861946298957357691615350511045647142347165504397341701652469388698714703335038415612851594768265730, 11345090943857551298893350047778290247351987888446929151460627421081288322850272396607499382644573641725079169399292658877661305665824106993961939805232014754354929634319667417844903300007441697088293004659522765108146476052721225986953530690715949616049873309178488075140659007114922264423613679921086297454, 8243033103849375366214077610986869692939255424651215481170249554422467022331691456032000509340702393808895926994440735368619062210434273430249282007185400714538771434327364503395892235103103470054162289662454139622742520100762493619371229895954298607540243061038326539706592728230347259691678868677152044994, 20029653153410965022543927121537891643867865766164870087036816407614708056735668015008498465803648399584208967487667576040889586285869017929227716584630382285304189051665141702936407032405322109610921680877120876429579695662879409801476723263900889285956477542843798176479967974998324710434490825972264869636, 149610206036302098686322006263598085270386864336505502127403243835517052049055163264650559483614217070959507372017216226825545802300948562468718276693274492673856583172616720483713318949102250123131010071297606983424640999754637694655804021800306455419495600882350654009343959077307817574837737187465795062091, 91316124559682343208074208813723209163052879008810554598159813236459719417838681357319178848139410053028511191000427830825441750628019383705685275921576966868125801154712692642258256964327250498375331724751861179769099892353590092490597048340408573796462539147836172513018084627735376367108859303865171511186, 112506957691013811301214275792258698352942897640919001808631327988034087051571618538019422776325033038514281959834586395709104591707580916848960336181887229024565726460519873518471809658546356679995872384052382047451030172958276881486514045486447051397012668658051735648437184272105045080671058672430832635379, 53820880539788068656111206060467418637589519198042590464142016200864569464624198007844978013900856408567314147011384775123406186021206685112387276895755328523218200924530032995302060388636977222303459285995558853900345978662322013601091050025177183937301743744434660621268655445812344264546392198625298243776, 112777748026052034887880732094789333080976863096436028491057183969297521302053766744199215574876237313919703290816273715007242523355217591831493406992836973703850350531947198182102964338695710967811842762719639173247511205341500439037269622259643929286450842942983016300078995690251964448961460800081578966321, 19405895457804838534429296125132000146361695227964879657208108616631611699055632071496824499230311041391304160621321491579889875273332229610087933645839800774688771509101004154531036166333410222574953502792903590517679509102754345819784146119502585836096551570965796785143666655131189761578357964410010048126, 129829766887698854518441173602138687228472398591016009480256302067700430768157163788383341528803480925941469069846111656499170016237114375259712468421520425648742515620074558477969099182669734836613256042665214047734243358438219467389230886071359701204787448954177322733963489708837416080630803131561927975866, 142753554762407317418064593088581485770994009035623759624745794450022154254410560044337398014884427071578477755753297732435636964687189179843392414923347995708556874636633545610170155200890185838212275526551777533403189160669690418461699954413163236961486096361746342352466426568187127773789991442923590687098, 31848485606403805660359010256458859933561680110753174294368170127902357093111090324815234108951386841730209973680764934067081739632412872174521545618218633998271500176896814510764824208363263774876451479981322635210991509586097341996524291566854664137801833119902516189909887554845632337233003618961931398265, 119427280513223394465671587936817129340474436986146679808299863745370773172322627283783972788929779720719874249124534251555207155305834085611708264351177098456941681016029887788115925439718919160482636038012687614032024024554741219581489481933689253951547348069278838091519972195418651202612643508290983082367, 71613131691072916431457333730256441527872084731798610502545924910967785743936683076937736145664513231970752324897210652713700428473246412782236894596174492215048479809179710135056236788305443077894242449646947942899482434893360025951016252048071480556484809927133240235939345574631121859269021670931249455209, 55931276480201064561212160109434903927810346508498965824503894607485088777712841792542635776657364286195994239425096077623617896778080481300148221454029594606776134206519787490888923195818849034615415097268866630101502072944285890452719057991427079368024154867455912885746643423308784013706621098854199287885, 45453250333134002159475105074532179391947577652902995324382950527219787059334126164115967471286216608409826301992907982500817432162376889522935088702163739521277183031777261274356467600845500177074921180458362288632330329726553320471675499966119909557386541316543593552318585426836032973427963350304728038604, 22776398347754436334415967090013538910856440120622875754087049715445583542472595862572076975543045738000913875085716067407777524276874252475043524397600636191688500978519071482403076242963636891862036284501789827172052247791747790416932142713797301824514401872748977034296564306894179907557348257091862993124, 72097855146097516517926404693372078544785753794489580738432244018681527163163614199417222494555050322436982483051228479962895248225688582214551806009082897486628311694983330042034927226767682224165949996068489652339573973367946983448877966036244884058330163270551297138048645654530781077109620908837241644595, 33788611695548710258786604004395492813515526838965903788325650989505464314142569035590326039907880431575689715404483012914664185323778200840622622570700346272660047419256049443191003377557570780061135695758384058022595117056839820894715875730866685287309641373350484299903079330455447446734521699546146327377, 71580831088514761998941611146487603717949222245552951283142350837097516300007890084635041563074829339295889477378430185881025793370223794951593688502196419684030393466364573653410386432354047707182043609454659960953300417654763813771754158051841424625722427431931617407780217916755274165289623648771602370321, 60154824588247300758317864479504213491013905086995914401697444268160958291594903315952654341551076811810347186811041286454798529944458304111653808222541907517321117598562056305697734814636848865846721431057739149164142040015392573000803031905751795437681622076570122357285500719017910643987658169015266995787, 133229027552304562350749113186352510066399952626204167507023336930418797081589577213205771140861708097123649571250123554060711526015132933191972453099412659799985558315445952578254719250702319346771263947954861229758660241521705934517585110128017151383952876129879702480319617002570041237659361034751018767962, 49424498448453418981780043749883850149685593575762680016632520578023066674934203120908342872085168879864126990622799380820875728860416097340242122251226847254418023995345167339727781435968479201144154055951254497456573277814432879248680059406564890858586206254428697761436801302716503940017785981258178889558, 137520851721938412994104141504416409928993113615331093761596065872170362960575675329502697032557559641951917864243392185857101174104772854400519718687029981631568877418764808100436893662916289450535512686490751204865173306011924652753579145605481999366391313397488160738436093692615278799128424376503701721057, 122660530441656704682291330890848436490287055655712331153816744613446460341613856194950091586820657944039914166008481346297505105696896223600167045517983194443697946922712750116194694524027835134883463877251055761080164584071319102302093221564564708938563135190217574911107179961848047138832431834616241874491, 71919458804584969138329772463937357894279465534733634554698162389428158842393640344014738343895556465936826828615128149256589067308629059007268877733539789591763975671236013556153681699401434955011748209286256339243848412808170126927390116006491288766190214307554068335543145426219007016337141615056893363096, 83981044266615346668992711332478965320549701990847032389271665887350440941009555054741832884242369336071488305332407737722160015596001076180472443559357858332588712551386607215636113327709020873912806189071716044244475129048406480735239052337937759658564664559822263134456251195122218309731156693009364246115, 113526245869492002386819808028719183495254441541322434616734339008157290605256204755443542940518440388866174601257899385042422417254001060594861162378537709040846287682886328951075705141106883748733357050763424482372544756470518285946112590063395573633925278995301071667950884287797276429413700260746814612724, 10778333149738296249606428743141036087673940932784928690833085912067765786592692842506725124432138421811889392620731247674932566342287765116316958486580959829638381269502585878029223347693390702371325011557750248519127550419000533782995064910385765375254438442047999482715797022447801460586631871714440811006, 82374844386696358215488030085215624454239597925277257621065695502366211880195906896916025387768061728962246360067193858893687343233778507670016763806686452400272373616383247477432277099682611510273856492829538758415868135926706256819954667874983489708509878920107769996464888662641088448484443994596068277031, 133851320478944782300829367538219394760069515617595912310203195387138353397907776296182918533923228937923740485069287342153872772296595783863153436798788341026864532634032790862018432749134695668891838779713877036507192627152535522015004403801543900107236319249202244118451881989324115120282404718028960752590, 86856971212723907962265522737132279286450867915429195107179329613980973574679256753848739991673641810544903457373127834785436886976887709517346465352392284874663419242105641801825840665436026285253360566625723214060796042113733453566405856103366905452513799525132359758555658191883574637456800568551279464096, 56261905097412379039475002608051608139924020193741602440873763653629946034171757730757567224412330044488990441318274893272720417297619329566497969125221818165619354502540568094713610078868260721850788589072318237879703008703671343754674565598605297145067643609585527578385726583120949563247470292431676707095, 17125941790404002706068303081270165379083470009417705715736395866453116457152593836336219590003464851830933631503824645839229957797670511797987360187513815469982464240704861326816218323851530295878510611758324523984037411437295422568750421467718530888459196113087268571403084702783647264338828719239632743485, 71838729667517395896398485835102850037185257605166619360904353940933046357095565237718225390275809541021942046806337810377489573659562253891545415817176698280682302979274542417750636084458188805073848282629096523363836619758188267751812075303984587938050814557370816755571321415628376955864524146999868252460, 127974746344151231383604948219131948022498918778022836762057280350019291640867437586581603755464286084968353980306950345300178495774575903110744418620637520621301196458897557324658381282022808591810198763373335605521988079663798490207190852439358537157445928427489652600555565173461541941923771011126087491992, 52142948073333942465300501391458180255258792137508707947185530370314233009187637715252131976886442793356262235532583951043256181865337343630400114254589537352162899476658691643501313542083612688103294406123493851631427583696573660464188034397230262705745175462855436843425765235959284281584793363560248220126, 57286497064011335982545504168325882682222763813397141869229285275629057407417157616290838681522612364631089271974594323265941744347737793843289362333253949624281708326301874036705865798151111845455218586209539254699064186589281512683745458302693597700806095927906734797923501852455654597532902245873000586219, 91486578095731795863641171891297179774171492166832871440693422020035468567861719969756198258955062108497547793110833299074053541512858279604213093819608920211718597710234336743964614459695701442993521151114199083965155147219250827072802002021214076136279023407247700596719184614932275412977995617945264115156, 44881695511720751253110051616032820323149197003129630046353832954247396427155584170406243595999531069365422542473518446473067764175826421576497946071256811071409089683859488766882949880556713166426791554064798608451704845110797788467750550555148504145102558334174589801924758678599325669333252775343731397755, 66577991951640377940305512154057696998882156706139658273893421926823842513383662884872498268329663056705670844376870647682208769180512858778535806856966291692871806179861992436876978634927300214651693807565332257199464920538307573454864668880794435167252931316653942833222200662647129739394289067732387329208, 75502747582374165111970117640891332633674595738633020635487107504413605685869993875922674661085976527416635036740854557484346436179747322108315826536596903169451399413997158393701670765865023422945142459829510837835133549305106390187739891071075475060080639753565121678226547764829885616698380964160353116926, 41046367212666707562561717415608546853908723744325483734052600386040692630774245588693948871576947918988417333356036608672260156954800480343778100751106264680628792230163199549017895038914879340044516568172656004408520178985041807201432843452616079664552587051509660770033863906055684703525487542443570302244, 83806472919569651054862978818601489707300185771944129184997298047993466205260786164924796178283728871665202176568703346056013399365769087180430344149320818697008299310797077762235941586068080902312021501896275779428242552059150587741617617936198056502807393974315658489642291638568782728198979644919299212715, 24739743209823951489766433199032092643057692214072547970498159971575156904118004617298171321356162636324732269206585237845975158750481379293371094043234869280085524697643627955125384244905339024763223228396490612144101032366274011273718275081508914231081038861751332977936286610898609589530264938001982293664, 82129440544669586934394114922355746567871927215884829311461059973225934947781996853360844797569871993698671847962080223217354395354845434409582271295616851866893448681562851690372159996010846264018986692956705621771189920816647897792978634393418192181564102817367849081255956343080899628584607298258004733996, 125552012717651183360247308070011890876729141918858460502143730636255125875830320044249689971762842597646559530452930361131164296263057198928027684040324524581416870766349465968499608482478060900125605854425109129815341209917995515282654173777769158657867700581181207068685404698725523669466797346730304285571, 83947870853689996471074310034092953984257663199720902983758486827948442558467300760429971433520453027300219532964447764337873932205766511101705648864277872050935086397861067376670962445643494427457298241410966409365051763099614769560931472859191107718079054735135217441034188201443530434650208283592266287165, 18959741741653643990117190647584745543855142883131602972595053314821122448381252215178556150503805159621724061571905444118692566059395769251946915157931438335410738423998178147440394291613476103786532027698320116860225814815079281129535421730856533130332542431987496875511309480445212503841162538047915143159, 107612465943150417029479755114658077125496770072550346231710797329519737195975009080497301598414721894604835627940895660997959987679303781196029634395813456213594175513956565520819104375564102891915189694581368847704002991793226380676124251760651958095132938649894353349009803875057192223276967439627426317987, 37277928756112443758963176833362881294624317669412376598425463541168921107044065296731945863091956067035176580720573588717534511688827137235224682665257997654261792262808604426109495114356161826432368833503726841924267897271631727460019120714217793961749710681385670939277424772565279964285608083425408927782, 129358305657534137928454639739943612931709250799892293835469448501711792548090049471856320994054615683148345585974909728453830662422225137158850651954869064685977121996084611116249600242286343950417812465580180711124697562827677882618346842687566844522792137789808797060303033049525269602607145198900296452103, 139352996059386986594788650162753175273432132369394202697887222092226087271755513301429168820885927379742435360091148126915838160417078681375860841419769004653460977569768459293315899065311751087433070535922954349715229069406553971250493219689429791988199395816825683930820736487870076660365525410910478862304, 61471323757508646826749758004672828688160061323635616553075261071717618215238241912395352164128544686094007324613055429323602892654739764311752763802241684984936204707538417929211336646976805729278604440593432155285350636246157201386000768129000583060688992675762378394131402888107770351367304925466626214048, 114962144783461983549669796975568112996782182228310402397172751754543428538678431793589522214144081333572080634006005528027039752176111524319614093598297031613731278988601336187958050272185591619394012246337102344443329379960925776166181024957229573848536349114811744640925979599779393985681838332717716441294, 48255023546265027347984580518215873856374173764765564394781014589560438381965149281418028032606158247650819534637673261692965824832487118862552330740599609519200786970397584046880858358279904356494193781235701393668370159040296435569977721648781017277266718645578361090468988813280418744887644824597038761492, 27598184226061722561421909420242685247530267321561341260982478729272457839064031236869824663285645138596475495467481730052973967387040285804661489807093920964019503119841013978403550910795469869312253299494569549678397930546758208225275376432671148573000655491059478679159805093370787242474438587116179835254, 9172189900725146147320014233819417944972736522906115085200626165643144611479158875456050521838059028176056950793248400405976760098708199644480431086019875730389796948309150399026924402724074200274808284364090021240334313769340314425941767599744464531858236835676814799788454350054408907682304413451856914763, 112454930650486243223444475466715721228514923804861107156569536455788574089671134754391692974340847164372159380731997341335446439428628496640949731117857223715415627146287801390475387414261934807529727408346775554306133971000750998882883801683358336218685876634166158867354123900398628093567259830236389527462, 57582665235477673234971900359941596367925201095652005203528383346250079352794727403160672349375805059941235961990823919061645434858708113960626569323021774157203119645075643479066566725319094388225611600779197537434550710085275048849233156790057851139338203553968886988611797056889749248067141450187538903838, 55453692904278762147507492837272344999608085498317687500857454405515852458462595599826271215060714248916849617734712728449463285666514490991698881180820426039695135344978645048718406553687688348907025271450489585481109307279406962524446184927577832621122127757458854796129869037917019082245682162460958450635, 37236040377767026836201014213343958728521337333276018082514478497599227101314052548574676401080933526160744922882581153787344008604377348564607972552056734182645782461245411089737311308245663057858048453076051575356238379292361138984177518218512142682871806330692758190061375016639307225178605658043424627686, 82769858937118339412083115982330899266613898643428579499591447230927840273521694287981670135340609656558076143968548344893960144314052926281153393616195093583624815422122194566479936563229764790582444716949479299011012103414346471261561637167364046829854784241512021448434797057172664081146824315765918302757, 105451159029524574579228316115495933452351075366509686689498625190934805740584327463649134964671345071741969583813669362212159963424032955211954007998592686593435736392885387705332547807919064670303589870312388845363462930208179658725667070862802833494919310558431676975890889343149337029006974551009418964964, 18259433849406921008492950543135544457281668954765127757131107440835592156871611795730237625053177221690052727063828023555912001111475461224352735224643966818941138857222639755892144008290148193980318425870696979587528014945132804078915631313452810048995379989122287598486654650279049661238555283401034949898, 78525167495322929975512457097464718088537184796626822533797724324800009438643227590499112423982363077008038335141900726960786973776021364251492894530883613770194189300674399811493557360751271747863845161064410829788475335386441069243327175469636135982092290795015294893327004240375664613283088410781761382830, 112485042460783721670013506716566790838592536945604536251812331499603059455502034125853493425571342502947335758387876092100908225091873211842790191638720723091456936203918340624730312732926779434533921586444948568019295848920312745076065483095223140554427640600809640024386062369665992074230368098717176592756, 95576919179139279079226574650282940474445688562801492652871566846892408224664427972493100781597873993344814045250438105833732687753293207127900065283011725451074598652442413698010373946991380013535996249926384138384529506156563149116933599866723965986261665726377117854987961618289727778796309500398661382917, 54219654948823318949353558134729647408528033078605450261710447248526931981389076366980791949387642433071065582792937355983620874421744623335979527846852740103404585916578675431375401166059525955613465106037568623523270836438448759386651661722151254807392308299836330059199007367174905836583286889987216815050, 35869172105073034975556096235258299638707891490235012188766841767244229723310917897401808054472607608792812969601559201602628580086657191952130787739893319004369902854653575666943324355363380637079930011912608863176644470479294749440933466533383738514721569349941257647158990358542979527511485933319882970785, 33585321284062015644628872525939167507033306689554250848095948952429865522047703119829617290091551521682239829250049756977570017816430059774096107954197232368207599300130661280510652420740089226343552474590403108229902871875586731165431796252447431312546948219290047499307018054290019358535681224393460998288, 34363063581955617713283358462977664682257832977620676364107767891095308255700558544765528275299946118597889167559960878802358804759430370206126814546909201603575606082043558255431021053488010978895093093984860049133918050324268289058598677973242974041658522222592016265462123282652487010520883927854399753032, 83303045014068598146239782836034572342661644739001378581085837509255968029431407176051614456594134112623953587188672599551029837808585911586762040880543248486616814921195820637197650347212641142881084135754833912810899047660641992645842889761973065877155412625476806148364533743554579144029169415470801026317, 113151374551030379905863439802781831613481971442242467973016594520046104484764387720297172281653500237890289948985294204511730848101104617294684815301705325430373479781345088617167985586923258569092520852815109295762192933273911091518345150383332084519963792546884769750659224626477438372213616603209047291257, 130829797409030268973352996767957779365311690002579378946982172341323743450377476516069574855855224485237210467599418067612712824380628946412878127911436900313997947604882192929110839317179000399541063224855604445875473626055054487308281408204582792705082064340692302772564869303002107776645416860156072622955]

(note: the enc_flag is actually not needed to solve it)

SolvePermalink

First, let’s just grab n. (e is the usual 65537 btw)

$ openssl rsa -pubin -in pubkey.pem -modulus
Modulus=D6995EC957DC3213D8B2DD404E38A951744954C2CFB4242CA6A0A240949EC6A09451A5101A6AAB0C0B7E303A0738A67225C78E10C111AEDA57582EA6F42F07952CB46FA29A540CC5052E3A0AC91A1A9B465F1998B91E3907BE29A2FD38268B8788DF6FB0D2C88B340DFEAC8163E25B500A67D7B4831F26DED81D544E74428D2B

Now, the challege itself is about Bleichenbacher’s attack.

Read section 5.4 from https://eprint.iacr.org/2023/032.pdf for a fantastic explanation.

To summarise:

In this chall, n is 1024 bits

We have B = 2**(1024-16)

Then we have to solve the following hidden number problem:

k_{i} - r_{i} \cdot m + 2 \cdot B \equiv 0 (\mod n)

Where all ki are some unknown < B, the ri are given in the output R, and m is the padded flag.

Solver:

from Crypto.Util.number import long_to_bytes
from output import R

def hnp_solver(rs, ts, n, k_low_bound, k_high_bound):
    # given ki - ri*m ≡ ti mod n, for small k, solves m
    l = len(rs)
    k_avg = (k_low_bound + k_high_bound)//2
    M = (
        diagonal_matrix(QQ, [n]*l)
        .stack(vector(rs))
        .stack(vector([t-k_avg for t in ts]))
        .augment(vector([0]*l + [1/n, 0]))
        .augment(vector([0]*l + [0,   1]))
    )
    W = diagonal_matrix([1]*l + [k_avg, k_avg])
    print('LLL...')
    M = (M*W).dense_matrix().LLL()/W
    print('done')
    for row in M:
        for row in [-row, row]:
            if row[-1] != 1:
                continue
            yield (row[-2]*n) % n

n = 0xD6995EC957DC3213D8B2DD404E38A951744954C2CFB4242CA6A0A240949EC6A09451A5101A6AAB0C0B7E303A0738A67225C78E10C111AEDA57582EA6F42F07952CB46FA29A540CC5052E3A0AC91A1A9B465F1998B91E3907BE29A2FD38268B8788DF6FB0D2C88B340DFEAC8163E25B500A67D7B4831F26DED81D544E74428D2B
B = 2**(1024-16)
for m in hnp_solver(rs=R, ts=[-2*B for _ in range(len(R))], n=n, k_low_bound=0, k_high_bound=B):
    flag = long_to_bytes(int(m))
    if b'HTB' in flag:
        print(flag)