Verilicious

10 minutes to read

We are given the following Python source code that encrypts the flag:

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')

We also have pubkey.pem:

And output.txt:

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]

Source code analysis

The challenge’s code is pretty short. In brief, it defines a class Verilicious that imports an RSA key from privkey.pem which we do not have and uses PKCS #1 v1.5 as a cryptographic scheme:

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)

The flag is encrypted with this scheme:

orac = Verilicious()

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

And we are given additional information with this line:

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

The verify method tries to decrypt a given ciphertext and unpads it using the PKCS #1 v1.5 scheme. If the process fails, the decrypt method from PKCS1_v1_5 returns the sentinel value (sen), so verify will return False. Otherwise, decrypt returns the decrypted value and verify will return True.

Notice that we are given the public key, the encrypted flag and the list 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')

There are other values that are kept secret, such as s, used to initialize the seed in Python’s random module, but it’s not relevant for the solution:

from random import seed, randbytes
from data import R, s

seed(s)

PKCS #1 v1.5

The encryption/decryption scheme is defined in Section 7.2 of RFC 8017. Basically, the padding format is as follows:

0x00 || 0x02 || PS || 0x00 || m

Where || denotes byte concatenation, m is the plaintext message and PS is a string of random bytes to fill the whole padded message until it has the maximum possible size. For example, using RSA-1024 (128 bytes), a 30-byte plaintext message will have a PS string consisting og 128 - 3 - 30 = 95 bytes.

Bleichenbacher’s attack

The RFC mentions that this scheme is vulnerable to Bleichenbacher’s attack, which is presented in this paper. This attack takes advantage of the malleability property of RSA. Namely, let

We can get an arbitrary integer times by the plaintext by multiplying times the ciphertext prior decryption:

So, when decrypting , we will get exactly .

The attack itself requires a decryption oracle that is able to tell if a given ciphertext decrypts correctly or not. This means that given an arbitrary ciphertext , the oracle will say if the decrypted plaintext starts with 0x0002 in hexadecimal (and also contains an additional null byte, but it is not that relevant).

The idea is to increase the value of until getting one that results in a valid PKCS #1 v1.5 format, so the attackers knows that

Where , the byte-size of minus 2 bytes. In other words,

Using some techniques an optimizations (described in the paper), the attacker is able to query the oracle several times, and successfully narrow down the interval until getting a single value inside, which is the value of . Thus, this subtle nuance in PKCS #1 v1.5 results in a Padding Oracle Attack that can be exploited to decrypt a ciphertext with no access to the private key.

For more information about Bleichenbacher’s attack, and if the original paper is not enough, I recommend this video and the analogous writeup.

Solution

Going back to the challenge, the values in R are raised to the power of and multiplied by , and the assert implies that all of the modified ciphertexts decrypt and unpad correctly in PKCS #1 v1.5. Therefore, for each we have

We might want to apply Bleichenbacher’s attack here, but these values are not enough:

$ python3 -q
>>> with open('output.txt') as f:
...     exec(f.read())
... 
>>> len(R)
78
>>> sorted({r.bit_length() for r in R})
[1020, 1021, 1022, 1023, 1024]

Bleichenbacher’s attack is also called “million-message” attack because it is an adaptive chosen-ciphertext attack that needs two bytes to be exactly 0x0002, which has a low probability. Thus, the number of unsuccessful queries to the oracle is much greater than the number of successful queries.

Still, 78 valid integers such that unpads correctly are not enough to apply Bleichenbacher’s attack. Notice that all are around 1024-bit integers, and Bleichenbacher’s attack starts with small values and keeps increasing and narrowing down the set of intervals where can be found. With a starting value of 1024 bits, we have a huge interval that is unfeasible to shorten without an oracle. Therefore, we must find another approach to solve this challenge.

Lattices to the rescue

While doing research about other approaches to perform Bleichenbacher’s attack, I saw this paper. This one assumes that the attacker has limited queries to the oracles, so they start the attack in parallel and when they reach the limit, they use the intermediate values to find using a lattice approach.

Let’s translate this to our situation: we have 78 values such that for some values and . If we consider only the lower bound and get rid of the modulus, the expression is equivalent to:

If we apply this to all 78 samples, we have

However, we don’t like inequalities. We can transform the above to use equalities, but we need to update the by , each of them different:

Does it look familiar? Well, it is very similar to a Hidden Number Problem (HNP). The HNP is usually defined as:

Where is the hidden number, is bounded, and both and are known, given equations and a prime number .

Actually, we can take from each of the , and get a system of congruences that fits better with the HNP instance:

The HNP can be solved by defining a lattice that contains the solution. For instance, we can use the lattice spanned by the columns of:

Where is an upper bound for the values. Notice that the vector is in the lattice because:

Observe that are just arbitrary integer numbers, they are irrelevant because we are working . The target vector is supposed to be short, so that it can be found in the reduced lattice after applying LLL.

Therefore, we can define the following lattice basis matrix to solve the challenge:

After applying LLL, we will expect the following target vector to be in the reduced lattice basis: .

Implementation

I had a hard time implementing this lattice attack in SageMath. If it doesn’t work at the very beginning, then you need to adjust the lattice and do a bit of fine-tuning to make it work. Normally, this involves adding weights to relevant rows of the matrix, or helping with a small brute force.

This time, I changed the value by , which is kind of brute force, because I am helping LLL to find a shorter vector. Also, I needed to sort the values in R, which is totally weird to me and I can’t explain why. Maybe these issues have something to do with the fact that the HNP is defined modulo a prime number and here we are considering , which is not prime.

Anyways, this is the SageMath code that defines the lattice, calls LLL and finds the target vector:

n = key.n

k = -(-n.bit_length() // 8)
B = 2 ** (8 * (k - 2))

W = 3 * B - 1
H = 2 * B + B // 4

a = [H] * len(R)
t = list(sorted(R))

M = Matrix(QQ, [
    *[
        [0] * i + [n] + [0] * (len(R) - i + 1) for i in range(len(R))
    ],
    t + [W / n, 0],
    a + [0, W],
])

L = M.LLL()
row = L[-1]
assert abs(row[-1]) == W

With this, we can now take any of the values to get from one equation and hence get the flag:

for i in range(len(R) - 1):
    m = int(abs(row[i]) + a[i]) * pow(R[i], -1, n) % n
    M = m.to_bytes(128, 'big')

    if M.startswith(b'\0\x02') and b'HTB' in M:
        print(M.split(b'\0')[-1].decode())
        break

Notice that the value enc_flag is never used!

Flag

If we run the script, we will capture the flag:

$ python3 solve.py
HTB{Bleichenbacher_Lattice_Attack_and_The_Hidden_Number_Problem___Cool_Right?!}

The full script can be found in here: solve.py.