Verilicious

10 minutos de lectura

Se nos proporciona el siguiente código fuente en Python que cifra la 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')

También tenemos pubkey.pem:

Y 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]

Análisis del código fuente

El código del reto es bastante corto. En resumen, define una clase Verilicious que importa una clave RSA de privkey.pem, la cual no tenemos, y utiliza PKCS #1 v1.5 como esquema criptográfico:

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)

La flag se cifra con este esquema:

orac = Verilicious()

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

Y se nos proporciona información adicional con esta línea:

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

El método verify intenta descifrar un texto cifrado dado y quitar su relleno usando el esquema PKCS #1 v1.5. Si el proceso falla, el método decrypt de PKCS1_v1_5 devuelve un valor centinela (sen), por lo que verify retornará False. En caso contrario, decrypt devolverá el valor descifrado y verify retornará True.

Obsérvese que se nos proporciona la clave pública, la flag cifrada y la lista 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')

Existen otros valores que permanecen secretos, como s, que se usa para inicializar seed en el módulo random de Python, pero no es relevante para la solución:

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

seed(s)

PKCS #1 v1.5

El esquema de cifrado/descifrado está definido en la Sección 7.2 de la RFC 8017. Básicamente, el formato del relleno es el siguiente:

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

Donde || denota concatenación de bytes, m es el mensaje en texto claro y PS es una cadena de bytes aleatorios que rellena el mensaje hasta alcanzar el tamaño máximo posible. Por ejemplo, en RSA-1024 (128 bytes), un mensaje de 30 bytes tendrá una cadena PS de 128 - 3 - 30 = 95 bytes.

Ataque de Bleichenbacher

La RFC menciona que este esquema es vulnerable al ataque de Bleichenbacher, que se presenta en este artículo. Este ataque aprovecha la propiedad de maleabilidad de RSA. Específicamente, sea

Podemos obtener un número arbitrario multiplicado por el texto claro al multiplicar el texto cifrado por antes de descifrarlo:

Por lo tanto, al descifrar , obtendremos exactamente .

El ataque en sí requiere de un oráculo de descifrado que pueda indicar si un texto cifrado dado se descifra correctamente o no. Esto significa que, dado un texto cifrado arbitrario , el oráculo indicará si el texto en claro descifrado comienza con 0x0002 en hexadecimal (y contiene un byte nulo adicional, aunque no es tan relevante).

La idea es incrementar el valor de progresivamente hasta encontrar uno que produzca un formato válido en PKCS #1 v1.5, de modo que el atacante sabe que

Donde es el tamaño en bytes de menos 2 bytes. En otras palabras,

Mediante ciertas técnicas y optimizaciones (descritas en el artículo), el atacante puede consultar al oráculo varias veces y reducir el tamaño del intervalo hasta obtener un único valor dentro de él, que es el valor de . Por lo tanto, este sutil fallo en PKCS #1 v1.5 da lugar a un ataque de oráculo de relleno que puede explotarse para descifrar un texto cifrado sin acceso a la clave privada.

Para más información sobre el ataque de Bleichenbacher, además del artículo original, recomiendo este video y su writeup asociado.

Solución

Volviendo al reto, los valores en R se elevan a la potencia y se multiplican por , y el assert implica que todos los textos cifrados modificados se descifran y correctamente en PKCS #1 v1.5. Por lo tanto, para cada tenemos

Podríamos intentar aplicar el ataque de Bleichenbacher aquí, pero estos valores no son suficientes:

$ 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]

El ataque de Bleichenbacher también se conoce como “million-message attack” porque es un ataque de texto cifrado elegido adaptativo que necesita que dos bytes sean exactamente 0x0002, lo que tiene una probabilidad baja. Por lo tanto, el número de consultas fallidas al Oráculo es mucho mayor que el número de consultas exitosas.

Aun así, 78 números enteros válidos tales que se descifra correctamente no son suficientes para aplicar el ataque de Bleichenbacher. Obsérvese que todos los son enteros de aproximadamente 1024 bits, y el ataque de Bleichenbacher comienza con valores pequeños y sigue aumentando y reduciendo el conjunto de intervalos donde se puede encontrar . Con un valor inicial de 1024 bits, tenemos un intervalo enorme que es inviable acortar sin un oráculo. Por lo tanto, debemos encontrar otro enfoque para resolver este reto.

Los retículos al rescate

Mientras investigaba otros enfoques para realizar el ataque de Bleichenbacher, encontré este artículo. En este, se asume que el atacante tiene consultas limitadas a los oráculos, por lo que comienzan el ataque en paralelo y, cuando alcanzan el límite, usan los valores intermedios de para encontrar utilizando un enfoque basado en retículos.

Traduzcamos esto a nuestra situación: tenemos 78 valores tales que para algunos valores y . Si consideramos solo el límite inferior y eliminamos el módulo, la expresión es equivalente a:

Si aplicamos esto a las 78 muestras, tenemos

Sin embargo, no nos gustan las desigualdades. Podemos transformar lo anterior para usar igualdades, pero necesitamos cambiar por , cada uno diferente:

¿Te resulta familiar? Bueno, es muy similar a un Hidden Number Problem (HNP). Normalmente, el HNP se define como:

Donde es el número oculto, está acotado, y tanto como son conocidos, dadas ecuaciones y un número primo .

En realidad, podemos restar de cada uno de los , y obtener un sistema de congruencias que encaja mejor con la forma del HNP:

El HNP se puede resolver definiendo un retículo que contenga la solución. Por ejemplo, podemos usar el retículo generado por las columnas de:

Donde es un límite superior para los valores de . Nótese que el vector está en el retículo porque:

Podemos definir la siguiente matriz base del retículo para resolver el reto:

Después de aplicar LLL, esperamos que el siguiente vector objetivo esté en la base reducida del retículo: .

Implementación

Tuve dificultades para implementar este ataque de retículos en SageMath. Si no funciona en un primer momento, es necesario retocar el retículo y hacer ajustes finos. Esto generalmente implica añadir pesos a filas relevantes de la matriz o usar una pequeña fuerza bruta.

De todos modos, este es el código en SageMath que define el retículo, llama a LLL y encuentra el vector objetivo:

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

Con esto, ahora podemos tomar cualquiera de los valores para obtener de una ecuación y, por lo tanto, obtener la 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

¡Y el valor enc_flag nunca se usa!

Flag

Si ejecutamos el script, capturaremos la flag:

$ python3 solve.py
HTB{Bleichenbacher_Lattice_Attack_and_The_Hidden_Number_Problem___Cool_Right?!}

El script completo se puede encontrar aquí: solve.py.