The Merkle–Hellman knapsack cryptosystem was one of the earliest public key cryptosystems. Can you break it?
Information
Challenge: Infinite Knapsack
Category: Crypto
Difficulty: Medium
Files: Infinite Knapsack.zip 13 Kb
source.py 2 KB
out.txt 24 KB
Environment: Remnux VM
My Recommendations
Download it from hackthebox and verify it with:
sha256sum /path/to/Infinite Knapsack.zipSHA256SUM:
eda1b771d1ec4cb1083556603c59dd9a98ba931051cec3ccf87e19035eedbcf2
Walkthrough
1. Code Analysis
source.py
from random import randint, seed, sample, getstate
import math
from secret import SEED, FLAG, INIT
class MH:
def __init__(self, size):
keys = self.generateKeys(size)
self.public_key = keys[0]
self.private_key = keys[1]
def generateKeys(self, n):
private_key = [INIT] + [0 for _ in range(n - 1)]
for i in range(1, n):
total = sum(private_key)
private_key[i] = randint(total * 2, total * 3)
total = sum(private_key)
modulo = randint(total * 2, total * 3)
while True:
multiplier = randint(modulo // 4, modulo - 1)
if math.gcd(multiplier, modulo) == 1:
break
public_key = [multiplier * private_key[i] % modulo for i in range(n)]
return public_key, private_key
def encrypt(self, plaintext):
ciphertext = []
for number in plaintext:
result = 0
bits = bin(number)[2:].zfill(32)
for bit, multiplier in zip(bits, self.public_key):
result += multiplier * int(bit)
ciphertext.append(result)
return ciphertext
def encrypt(plaintext):
random_number = randint(1, 2**8)
shuffled_flag = ''.join(sample(plaintext, len(plaintext)))
encrypted_flag = 0
for char in shuffled_flag:
char = ord(char)
encrypted_flag = encrypted_flag * pow(random_number, char)
encrypted_flag += char
return encrypted_flag
def main():
seed(SEED)
state = getstate()
encrypted_flag = encrypt(FLAG)
mh = MH(32)
encrypted_state_one = mh.encrypt(state[1])
encrypted_state = [state[0], encrypted_state_one, state[2]]
with open("out.txt", "w") as f:
out = f"{encrypted_flag}\n{encrypted_state}\n{mh.public_key}\n"
f.write(out)
if __name__ == "__main__":
main()
out.txt
43393159686808194715764984856705723839377233417192445948725431024836116915291830536963167994800894996748816401180546744336307813171281484520660485194050198290660969090739454738331806229140133767899399163462382863863437317637221107918067059862888924674353221492866242698696664106494464158394411736371117849142337116195358419963147970438421235456218527901800123370493497634796454152285260697480956782865377368221800430449476138334356874103779265002988334073482467063950364724938663708252596741004924962185081000717036567696157017273011832561613626339877632916777755461154336575741615197731463463803145240199739592755597723947091710370179662031993887314750603987550482917144821276000583707437442614112204876615859450720647081095891393611699005601814418907766037315024966682626874430481044518056200057680573608868009542440288343852473176532456459133611190549608967341163797388103376876610394506248959260745512501182275589601490725226488275699547881318780976163552736186698278592596881209571522860684953144600008791175188863505199853420384336596795833977708364248815712437330353462878760063354094689161519430302969650174934259518869422409506210801014843613827884539852188572599241188188221223066976905523199027278739461105814493834708990456491467091597914245372243932384881798497004115191836461883441858152389537472524362704974059063672672754685875976223288270662771123675432940118355799827685490511787019555141377605995682455048507272531761757996321372951259550400739585767218134723883135259253143444145695746455060764796866800759482298227135187034910805170950670237971046597633425436926113473756989640633218930580464608760721394087416853355934812245942041721460453584864791467812971900914808521997019500972756646542740210159778767104214228926803316112404570802133543971622607283882444716592366052307429281532381173995566038968620829369406325111310886990846024414777363726360164372769886886615856512122004449632516916878728468879020199974634824379788950604837545155440106987946151735705792512146468226607883570985910426775368871893362851278254495903992815165271827406309947794264013737341962383685335298510453818182058992000763661295071098742755092859972811034355728070698348364640700206796747663279496049073975183067016838184182269256401154760710082632195073726955288521293657903677249800455101921456525155817245488860551583070493074309210365728015154980995061970700833321907165424375043582424097271551417511295020832439629589811913275149609759505736716802990527067718771042907194805425680444934797799361757971507448694966096798449767182963237621533816208936067313851026399652426160897107803592881886385085124669323375035721961144779166764605390218121595632411636914006277721509917433446757944221354493880204974521481183965584531960254454144566089732093336508162762292163156458569005636819913343982017101484448184745575640739413077644524400602962585196435795070500944426228641047655121418626147395446659414886597530361724563114738861198550115704323354096257041023665918954163888994538147728465921894818816441237952438001112167031629603999095298588388743284267110986076813432579547942824996702084367352517892542611278574024772156178671427643435640451779710222582089982715645470670276336947031513728705301045436119475294387241364469693629798300986836047319499000875876512812917839994329271641271035177627344602059282277694001384980375565164070825284053741666808898403073704896126941509174066188382359545950104729634353678946896062632282151552667062495799343913670952599610499849345789591375640218756165537439416174454875449651896742389566677380562743953723913362159789331970273935190446414648563860484741878433223425279136189160984814542887095455297680480030170302972818492304622234665716265672595239104798391630268997818850802847367551566537640626720627291017559413302092141210212166834653049479291143047780615391102711858918500568199564252927929348385406789411471200749742616066858064479223673194985047146674595415988073327340558200259472429687911496499097566636671113925852278469872539322874315793278195448018997544873240109187974573076674310318258723759812700791540655514770514922932514521632021473499643043950496941790389144555999447158980071103637499871111189074380659429784937486738905907880282631897402261654340742575129885637414854988102131339511842928661465777357153793760454128314432749769767179957381439950518667950467772188155441076815329503675890667531791963970434789086774322948579445074161200118818825934705273097159310664745999482063449290450672394020027410380513078563565637858153848171063187231012048811765639704258084122555326770700078931868162184575983986503050139225395382805419872003043159953375563468522734718310729434674272528029290839599389513603632080423918641388400799737264275440138573656461082183988775691002369956869787014548259069666676695993991344701746208663017692887878515570374333779733265147998833927271150500665073186032249783426997030011312605579306932696157810321407606407720402068551139092794919481113041084585339102161654931119403178965440958142224099789068582957496294157950645770324105879160694559374558520136821103882981669501376665646540078529710251069614949566555483391342149822600475558552534063036611580179648936272788415051636829782414212579889270094
[3, [218398966962953734337505, 12979728176815833763163355, 24071419825465469065834690, 22439137413272739566817124, 19743544955392660932809351, 23837780789306209427151096, 18891840472641068528418305, 24908526844638297129102239, 19381852662082029797196662, 23446677575592643759567389, 18874553625788410522681800, 16749385538260227527630045, 16833162621175692326065043, 20079458636874446432671920, 14052200673032883579753246, 23564285387025909219943422, 19992919952523957341968398, 20072116566553699717368338, 18126190644443386325283277, 19549929588903533273405690, 14713660073322629799508923, 21027444218800637641935584, 22366006589233942551830175, 17281649508621686565392047, 17319705709131657048968258, 22781102771089414339622417, 21102901745886358883635851, 22909883673346618850698037, 22754653600657672328018122, 14971707015351175465477492, 10133497447594778104642426, 23208780514841901798857003, 14440826847817381765958117, 19221053128118806217479994, 17035257990198767014369673, 16892722568824238237154816, 22883030582692840074633332, 23777637845595858462579955, 24409663123355826345572106, 28338362536614152047226903, 20650295598950592783922616, 15953654769736610652913548, 13422346619566277417238867, 21317632099709744581413995, 22644186732279046309450594, 18659590065915626887161857, 12203292853610547219463386, 26639463774879094056087633, 22827149065987850854409465, 24768354658019588760467580, 21085601886547652121788058, 17656123329183120995890918, 19372769891962647883228686, 21139977956337417599201422, 13101132571538033948046484, 19851486118147501379885772, 15794346404918372565392965, 22067542181871127212090796, 16872037530158494983776975, 19518631759833319504624123, 22981620948906166610351556, 19854535567637677190445783, 21558507401198684471864871, 14170625611192656809592644, 15229759933744882091511148, 19070449983831864092537955, 23788746988080530565484928, 11843251543577533532313525, 13522183189733726607329945, 24744838960144203351047466, 21933079855591390180320035, 21292796701215650095762716, 15620663434396210637656743, 23570310820301246451600558, 18652851553298885330217903, 16075270260146298221645691, 19798911921331606565792053, 22982242390556788243590991, 18126868432768323238712746, 17283208085998184229081020, 16067859201541256736659167, 18923088669785210358790221, 19874424161188657030554912, 19647756474836465822516614, 23494221561451182266209625, 22338938937920938446749466, 16856677869310126196814378, 24494817155488307581537271, 9774923170118067699694992, 26720348907877091057040143, 19890537238570497197073622, 19849684660745881789220975, 25046065679933740521791739, 17563943435513642576193218, 17066778599557895446204888, 21718785640735589641143419, 14110331787894796144090689, 14160267178366799224323267, 14136114173021895753889518, 18908600278329014749423054, 10896496252179069222992253, 22633019861019983624521961, 17870922254710144210886106, 20780028014480526942717958, 21162019616375066610829085, 21930695903479068858808509, 23637157153862934004507844, 18326074191762329008394963, 14307948641274658302688098, 21236325567493192497292583, 16805865991307603672184354, 12648823521989707525816785, 13462451852339697615137849, 20264986323093975135807222, 14943119725543908967782689, 24412164438478993484793165, 16970580792693669857641741, 15198556089200258383541746, 19818834315501402947064713, 19286674645970889546257229, 20729904614073104117516084, 12906427664449309194420254, 18627658149120341065284333, 17155682376927508108491996, 19236697234264950413821897, 20205140634480871529183953, 23062697773071158134352764, 24914189324507856698372377, 22536611721650660685153409, 21333176855424878155762868, 24075485634041660937829974, 16210549769819964776693612, 18447114085754061671273462, 18320239773133375242216109, 25270560874030625745270667, 18060823004749303384706926, 7867349457202586536698483, 21151255457222184832893230, 29456299026020167334668189, 22095889257254668758563188, 20982739191904870474464056, 13101476413075947086927759, 15593061179983758135474036, 26402548820949522762765212, 18855844275794676337896800, 16161505077268666815973168, 15484159183072381423884729, 16951560023395921137943371, 19352547584454536223116417, 18099869230125142452566716, 15083039400084843317436275, 16246616378762534455858836, 15129158223027137314801018, 22205139605046710903442268, 18297490243866626566194001, 19168388766822962052110935, 17395286448323256842674073, 20594843839090947411911032, 16497909209618396928259548, 14024982785939534423778314, 17464637639546421888474996, 19581925257888696003818529, 25755798463481567545750258, 16245527968389108499676152, 22338240453458014358312101, 22243046989128232629098968, 15727015087123923388301244, 21053826276514046628637232, 20873542565495810753286144, 21664173500122849672588416, 19809322027528435159384209, 19740666277338593819434338, 13433002441809669416812388, 18351823192384451700495781, 15375514063568212139204389, 14819480269588079192915125, 16820617515775687788393817, 16476712118156599193849303, 24725698267822527183126752, 17759698165360268216398368, 23358973163372834538918224, 13705788753130763460391620, 17509969757487735944610450, 24205533935433840589145291, 13570978469651003723228756, 25250548428312660763731419, 16939958379959285143704563, 23477193706536618702329299, 24138284412858649944982001, 23836126633688792770496631, 18216372268790547231267645, 14000427466367469278984007, 25764223063962343166482644, 19505956952057428552138956, 22274047335462145400697189, 20666997303482579978375971, 20133965298100696356183165, 23274918111778183738373560, 19459697264127981214640290, 23835248868224357021361116, 26882087091157652134809098, 13025674642230134567265921, 16292669381709530438878045, 15456991725804907412601318, 15075912840072751445407520, 12229441791420113512080626, 13757157972936324724658526, 27680757204659359392819434, 21657407274354299551937837, 23762534529404585622858536, 20512499306180002844439015, 19661627530452293740014018, 18763819168028809318555100, 26173589645274966558321103, 14080629113478750944920719, 26955112713385149052833912, 18834715108398473210832944, 21297424864677566847204771, 15757450145237230661729400, 20671038517679306946820366, 23281830217270031115267010, 15968629939804154769786191, 19252527103242448037738690, 23005255326956697822175921, 26048317558337266520427026, 12715761399461766806378543, 21635825015958531867248720, 18258912152640178349243121, 17025889634459045795832260, 17206987805863655623193740, 23357099947109852556342126, 11513468363083324068407406, 13631867231782843067240265, 20273893568316343382081545, 22382511028207416234444620, 22396643874066756125165731, 18847610626121382888291164, 16579651140211395895859660, 19869184632704106614966536, 24959104224691838848762263, 11882475799374918078188146, 16729443720427818519565469, 23316360145967575006726943, 16088330045808318224169326, 15209462510472142781738816, 22119958489583898174806453, 25589259936681668462637291, 21552577238162822517186167, 23437945908946607609780628, 19390938731131016329622557, 15470020169077962043627404, 21748793193254550073748714, 24769579345117606909689207, 16932994704256479731614153, 23922186508929138602368098, 24328808163644707339904150, 16615747472159226878998371, 25099887841253345593353872, 22397661186191644263625020, 17973885625353190474531134, 23487695387375586947526328, 17673238135530847652596019, 16477089378103531948563576, 21794110301213720750053723, 25748321050518179514663143, 15978884496148055983982316, 21593022352983823673752764, 21119170364754892802925609, 20215729590341290181269097, 20811336195637797417631966, 18853029381560378440529558, 15900040811749888251499954, 19005935177323014034860123, 13259697713818677182671280, 20510987187133670374246901, 11903348204309530478549350, 25420258673689291847100782, 16813465117029088643770029, 17325888806573132327073871, 22064322817075264179283740, 16856117862926294388614115, 21245638480891120357838233, 23317467576649891450501609, 15842703025531063719218659, 17698573712911780103207282, 19996763019251299936910880, 17713552354859202522897025, 20474836687444714379571415, 18349246741416099958154197, 13864549182478497372083972, 25907974821937420071656383, 17241015031363923374503220, 14523917961185372091614437, 18269827278978905529035912, 26339377802171456377708374, 13880247282121743114768961, 16225492331604092904553591, 20114592290367687690222524, 18513178085139886944270868, 23617485248251447743590703, 14580423441706793354727812, 21119274337031767543476988, 15506498896262195193854923, 25165085502999278543314864, 24096936862418379674849853, 17134815003386128945012801, 21045476503333073504449386, 23559779922369050153041279, 24626341784887730937399372, 25159823578124199726997844, 19342949028145538150838127, 13330112583680509394931935, 21964422244423918425150268, 17169653517354182147053582, 13730206245084338988116794, 17589296720477993436997755, 10067651051018862522688559, 16943927921016548084441892, 20532249130578288373301852, 21341676861411071308893485, 22793529184122690430592212, 18473373563437809755771467, 13186099424338005776071334, 15500650981115454789327190, 13510954411632195254990007, 18477432389129866709737674, 17301890629802888134137428, 15286930748564727904910750, 24169907817805833061471060, 22819575158786097461154520, 16658816469003281251565685, 19016262015661282037459196, 27712924083893115834269747, 17800257366872845957959596, 21943380304051392292107927, 30976167136514014824503772, 18185876944306615906921793, 17617096394752123670277811, 18775393368448474849445035, 23264293063186885076394123, 18907927288702967365731180, 27188840415808501497710676, 19904605582900652531275554, 21283445958972086225114653, 21654105744026551915491727, 20697259898809082369019274, 18783350507797150536583505, 20630265134843854493096454, 21592719543772439107499438, 18946974167481889713062190, 16526976373604108216274902, 15964881084235331512649920, 24669645214918805659829468, 17322191011534191213730973, 24957768758394437041266096, 22797377180488827221451566, 24975701697619485589019860, 20788068233770615011459391, 28405345179099921927387633, 22834476617798204096779495, 17568396888374612651353969, 19439484825986324987918875, 21453076359473612387192669, 21334493023462450508709468, 21310393453902917046124274, 20341919057444006168058811, 19712313605411123949022657, 13190789250793323527359407, 20413104896840344931696987, 12628410579759680310166447, 23278701353930763868616234, 18841491596855143282008735, 19889030790431273621336182, 15387983029062087666358475, 18682437052364530781571155, 15279185668606604636911314, 21877877146249962812924497, 21218980934511636594160846, 25304316885348872099757590, 11980924525639602383730485, 23385811959553625369114106, 16952815697419790271671784, 21683220342139694835853282, 26894739742314433931756021, 26695435323898060908410894, 17934809358503564787803407, 21855064703533616977369253, 24738715175760011913667486, 28822498244363914447930477, 23448540355570614542935678, 14392123414704483459032608, 22704092672701638529571265, 14071432941157352812181034, 16939190405695394296286154, 20264364338136622362493105, 15030970611657082699921113, 17321621616534614143884818, 11349349843491515871584753, 18528285357823577122370452, 20874030538202629674560212, 20757172304435101501767958, 22877696948927169394202588, 24684198501543447824439722, 19567273688299053288493882, 23872373051877274687833722, 21376810040153232989304730, 15131147795097483769072439, 19918693250058965919751758, 21176132210256179434438568, 16188526646680511741861942, 15744051013056266730527724, 21646771093707559970001254, 19271772268451310966434005, 20990919892205435259214857, 14333000419694751644664865, 25338710919354068418869478, 16591842270510298426085352, 20485544622338155708653198, 26703329234147622958732990, 20727267368386514482362266, 21679192155940791720302642, 17776990817959116615878610, 19085911965260459352694094, 17051919732829555224350287, 22783764550807206285557502, 22189453567577782956962098, 23194843545112520947851250, 19495301320821230507875479, 13697868955674727847551331, 22968131855883474100442132, 16503028385658021580587165, 16362480238314098409049143, 19881528344158150369484927, 16548057464475418738875384, 12087834442443903562113351, 14244792833631904656348087, 15597200876555571111732154, 20613415360099110599285551, 18347448655734294071531730, 27013486849921274434610420, 19528237914018418091961151, 17350296701070260938976718, 24043224645434652250017290, 17993308413006226658026165, 21160298103461347713123288, 17150610772713287600710227, 16981345312642598476799774, 19630498489430342472849351, 18663307164206779711502291, 13734121583696835968986876, 25320660813647230440311348, 15324749087033928732504685, 19413730796296075382919987, 20145795770082333051905643, 18036282185274319862480447, 18634463798388074249582218, 20326022165463450470871488, 24786463671669371991840096, 16798927928786005071271604, 21261907547218881777284030, 21914302990889369932257554, 23072835162681180328613091, 23530549326610706491677870, 24207077570997358841679568, 13166645611996548968836624, 21857786661714590555829864, 18919430118207203572336993, 24498958570529862596238324, 19446435770994029631607385, 20400640911156010633260161, 16548564766021237531715121, 17551546202598076246544131, 15333102953955004292234097, 20941628304159259915372776, 20035899861195850604423569, 18030958234209084336801733, 15386344889123488553779687, 24912547076030549433685845, 19520593647048588027973327, 10569442843028413484966315, 13367515006424708588603880, 25365329131685404819912759, 15515056728719643049212869, 19659778201407212558941404, 14348328329187876381934933, 20495212206830956257828153, 23464223717116245633846265, 22083862810644479904412129, 17360815549621914699841573, 22411473385912069934211853, 15273972429524089457911594, 24175409060677798781799003, 24281262500446885876018371, 21909955500431232379856358, 19298233399911596140220640, 16554420175127047277740433, 15069877486019974783533755, 21389340416566062749069514, 17380383202830943841974361, 18727975842310056413820612, 23014214296479447804454716, 18473343923050264823739243, 16452874959244492984819070, 20505992180949080778717412, 20503469388332311979619846, 15475297839745548807692801, 18938074934326724522242528, 23718731519048212409575299, 13502670167108109029632080, 21671355660828069122128323, 15525228237545513933635621, 21743795827153576460303062, 24403294704830245665368190, 20101986152493530731526590, 23256094319236181940943076, 20621964661087222104170718, 15889268056724670536987008, 25990797340097509232751581, 14415273440146307415451485, 17412837924554476716422168, 20703259664666275768104265, 20649096506462953976759741, 19819747898168365740040752, 15735696218262951371244052, 17233204364751217276962493, 16768537828127815984105582, 21975496947871703249154131, 9315478495033013563832596, 22780788155054265317218744, 18916505754077533102996065, 26498414488386963592530719, 21799742126996447252648737, 21774445130766545591463871, 23650800533249053713648976, 14110958823263643082635708, 16075222243360600172678406, 21050680917925761565324871, 25480697151914392726585900, 16982490866512712286916470, 17106435455229877171118789, 20254640326734377433514755, 22285583372484606671058806, 18026529376207752746034395, 19071671905166441391898260, 13180084641222847151439026, 14259221034573542405842523, 15628094603545775798371068, 26668636049965171542746835, 18518918187914533345489574, 28228603310429589461270237, 16558757663481984779494214, 16690113008626333777433188, 14306987691679720968771866, 7237711728352857202119253, 17997242628072627352961768, 18260084395219534068116672, 18220240451465488314816300, 16135702106886306484964804, 11761356100147624234812015, 23266001369803679408564127, 23069416868587703183936410, 17118744820769009701686495, 18703670459431618121742359, 19429166000667381172412819, 12373208348410262936331621, 17193811719659533542240117, 17161496216801701214024538, 19655699649813277395444924, 19778609710310520228570888, 14582190045874988615894617, 14511905692456495567758759, 14890371046080926095159523, 15227862850297918810058421, 17088968246181093964576174, 22453468043494891241570055, 18541888132593814549160125, 18127213237804109800293415, 23069570566002559699708078, 21610797417339270893620528, 18819939760034952682877664, 13828046968663777635137941, 14210330977129041977423975, 16287061801517834969072519, 25166023293806380543099669, 24391634575344443550837524, 15296439962222142391547185, 13440552535669146122636109, 16061258820997839447443673, 16674463250450551955562812, 20263297497442043778960393, 13284709579928320621243879, 23323278187585646097326302, 20809138952555632784095244, 19666480011418756866262043, 20763470097956586757054247, 22939803860011930317401232, 19245193131155571627559201, 18663659709299407605134005, 20864426931569469408036854, 22978878441297657012223503, 20980644932593059026760812, 18979102876838842706538179, 16558296522072503123582021, 13496319108050311097256162, 15583879549370720397761586, 11143594100819100959013245, 25269562496246502283812554, 17565361782542590591926008, 12478428367111051675296278, 14476772724696677859883953, 22843228563713001208380308, 19773031157572500219279502, 12986146534607967804528162, 17759904176070300703774330, 19420489924440820317312081, 15425766020225066504207461, 23979794509736842217200040, 12230006385033016467492468, 19251805456568498614002395, 22801625805420289654401771, 24797528309399113457163618, 18852051373887391937963699, 23888251130572365490819331, 18980910419815204440663438, 3584080202550007514430516], None]
[218398966962953734337505, 1614879992022514626233776, 1015027822457247280921050, 629441468006239907723460, 1215928756239865238152077, 2113957852835710583898097, 306182744968850798544541, 1714115541989762959750172, 2196308629289174616151076, 1728056687414159374932010, 1980217461668914208899008, 2138295167164925198611200, 1061799712589829080858074, 2644261770002385233853502, 712105863660528712775355, 45114004864633695796074, 1403967996641811695436710, 501832683936827299784037, 669210007810278396038217, 747718010859746214022312, 2166627996546761245327430, 1084281301644012353001982, 780737732636786059761212, 1396705557120478017401501, 1893778795550610709861517, 373604903305312524446327, 993817336049612095411209, 1435920230558296834811768, 916492045291107443228693, 2100410863999170227092528, 470544989469347711145758, 283552280542950047427773]
I have (very embarassingly so) never heard of knapsack nor Merkle–Hellman …
But there are many writeups and code that can help. The flag is not really encrypted, it’s a function that relies on random integers. If we find the random_number defined in the first line of the encrypt function, then we can easily recover the flag.
To find this random_number, we are given the random.getstate() encrypted with the MH function. The first step is to decrypt the state, and then set it as our random state, then we can focus on the flag.
2. Knapsack Attack
In sage, I am using this attack that I CAN’T REMEMBER WHERE I GOT IT FROM :((((.
from random import randint, seed, sample, getstate,setstate
import math
import string
with open('out.txt','r') as inf:
line = inf.readlines()
encrypted_flag = int(line[0].strip())
encrypted_state = eval(line[1].strip())
pubKey = eval(line[2].strip())
def crack_em_all(cipher):
A = Matrix(ZZ, nbit + 1, nbit + 1)
for i in range(nbit):
A[i, i] = 1
for i in range(nbit):
A[i, nbit] = pubKey[i]
A[nbit, nbit] = -int(cipher)
res = A.LLL()
for i in range(0, nbit + 1):
# print solution
M = res.row(i).list()
flag = True
for m in M:
if m != 0 and m != 1:
flag = False
break
if flag:
M = ''.join(str(j) for j in M)
# remove the last bit
M = M[:-1]
M = int('0b'+M,2)
return M
nbit = len(pubKey)
attacked = []
for ct in enc_state[1]:
dectm = crack_em_all(ct)
attacked.append(dectm)
assert len(attacked) == len(enc_state[1])
decrypted_state = [enc_state[0], tuple(attacked), enc_state[2]]
Now that we have decrypted the random state, we can proceed to recovering the flag.
3. Flag Recovery
There are two random ‘things’ generated. First, a random_number, which is used as a constant exponent. Then a ‘sample’, basically, all characters in the flag are shuffled.
This is the part where I got stuck for DAYS. I still don’t understand the math behind it, so I just bruteforced the characters.
setstate(decrypted_state)
random_number = randint(1, 2**8)
def recover_xvals(y, random_number):
brute_x = [i for i in string.printable]
y = y
xvals = []
for _ in range(50):
for itm in brute_x:
x = ord(itm)
powed_x = pow(random_number, x)
if (((y-x))//powed_x) * powed_x == y-x:
y = ((y-x))//powed_x
xvals.append(x)
return xvals
xvals = recover_xvals(encrypted_flag, random_number)
So we found all the characters that are inside the flag. The way our recovery operated was backwards, so we need to reverse the list before attempting to re-sample it. We can double check that the list and order are correct by recreating the encrypt function.
xvals.reverse()
def check(xvals, random_number):
encrypted_flag = 0
for char in xvals:
encrypted_flag = encrypted_flag * pow(random_number, char)
encrypted_flag += char
return encrypted_flag
assert encrypted_flag == check(xvals)
At this point, we just need to find the way stuff was sampled originally. An easy way is to create a string of the same length as the flag, made of only unique characters and sample it. Then, we can compare the sampled output with the original output to find out the indexing order:
def recover_sampled(xvals):
shuffled_flag = [chr(i) for i in xvals]
test = [i for i in 'HTB{0123456789abcdefghijklmnopqrstuvwxyzACDEFG}']
shuffled_test = sample(test, len(test))
sample_id = [test.index(shuffled_test[i])for i in range(47)]
dec_flag = [shuffled_flag[sample_id.index(i)] for i in range(47)]
flag = ''.join(dec_flag)
print(flag)
recover_sampled(xvals)
#HTB{50_mUch_R4nd0m_3nCr1P710n_D79288C4D4D67DF8}
