MAPNA CTF 2024 - What next II?

Description

Category: Cryptography

Again, in this task, we explore the realm of cryptographically secure random generators, where predicting the next output is deemed impossible. Are you ready to test your luck and skill this time?

Attachment:

• what_next_II.txz

1. Overview

#!/usr/bin/env python3

from random import *
from Crypto.Util.number import *
from flag import flag

def encrypt(msg, KEY):
	m = bytes_to_long(msg)
	c = KEY ^ m
	return c

n = 80
TMP = [getrandbits(256) * _ ** 2 for _ in range(n)]
KEY = sum([getrandbits(256 >> _) ** 2 for _ in range(8)]) 

enc = encrypt(flag, KEY)

print(f'TMP = {TMP}')
print(f'enc = {enc}')

This is a classic crypto challenge where we need to recover the internal state of a PRNG in order to generate the next numbers to recover the key which is used to decrypt the encoded flag (XOR).

The PRNG used by the module random from Python is Mersenne Twister.

It is well-known that if we have 624 32-bit random numbers we can recover it current state and generate the next numbers.

This is because Mersenne Twister (precisely MT19937) has a period of $2^{19937}-1$ and so we need at least $19937$ bits to recover its internal state ($624 * 32 = 19968 > 19937$).

However in this challenge, we do not have 624 32-bits random numbers but 79 256-bit random numbers.

Since $79 * 256 = 20224 > 19937$ we can recover its internal state.

2. Crack the PRNG

2.1 Processing the numbers

The numbers in the TMP list are not the real random numbers, they’ve been multiplied by index ** 2. We divide by the same value to get them:

real_random = TMP[i] / (i ** 2)

To crack the PRNG, we will use RandCrack - Github.

However, it only accepts 32-bit random numbers so we need to process our random numbers.

Each random number is 256-bit integer, we can split them to $256 / 32 = 8$ 32-bit numbers.

To do so, we apply a mask to only get the last 32 bits:

mask_32bits = (1 << 32) - 1
rand_32bits = rand_256bits & mask_32bits 

Once we got one of our 8 32-bit integer, we shift the 256-bit integer by 32 to the right as we already processed the last 32 bits:

rand_256bits >>= 32

And we repeat until we extract the 8 32-bit integers for each 256-bit integers.

2.2 Recover the PRNG

Now we have our 624 32-bit numbers, we can recover the PRNG:

rc = RandCrack()

for T in TMP_32bits[-624:]:
    rc.submit(T)

And generate the next numbers to recover the key and get the flag:

KEY = sum([rc.predict_getrandbits(256 >> _) ** 2 for _ in range(8)])
print(long_to_bytes(enc ^ KEY))

MAPNA{4Re_y0U_MT19937_PRNG_pr3d!cT0r_R3ven9E_4057950503c1e3992}

Full solution script

from randcrack import RandCrack
from Crypto.Util.number import *

TMP = [0, 22330693840234311255135949029444484409546667648719176405826663892267656641027, 127168478027482847709328807841325386271927515479937061237117195618823278578116, 182258311374053859620888699680212168010665323374548870180038645090147843867373, 1120044041165490856498692287111236626472260308631093314161690677868431277653536, 1983473421395194676263973602935227753154638099492341714205203280778040675593450, 1574768551732085861078069762534699936995654652684634077104498873387111232412816, 4988773041677976257517254491234335651753610239922582254283447205154548743632904, 869738033317159039287197189670964123964466628318970710545560734535418094431872, 716771557072892076589368879721160406613516964478389692662921907034616035095047, 2841054733362182186252458286741823726277405165099408732758691872324732479956600, 6200268989316199565071790593244237980113705529543497656127585449937778556282311, 10670728743047162087774896911955052588177734200772863764402582886370432879158720, 7713906922622752752151916696524419287963819641354815269293605765422900017233866, 13689077681405838115291939958594572280593102467042881661528817316126253635857444, 23677404931618939684375357302211056316481456538100460743428412550112769975941300, 22334702277647520331031971258896634990832479997228972554803329027443498276011264, 24695994670269108821474844143270568317378271123560130717104045624895774803117988, 10726839246587772223823222881528936091917884797218227418638385365176143122217812, 1312747277711228023681888222399668996816715931126782050057534166588569071642948, 14829434912751138825019062212374862054511849430113519894438429231649766515851600, 4917180643387964007287001238070594020985844865025196727991425387470641537875518, 50772176246766546694026388399540445347088279634906123947563600159509306535585300, 20680598744337311676861190641592800456437920078216405214477640693225317242487078, 57560623230262776939750106414721715686651269149245752162663251361023294801081600, 63941301709699592129851769466238327968731332723117779339939586823464299930335000, 30248094445348087425063737332624900285689080519537666953907462011122884602991780, 9774708715683840095021685805936771586028623975773332766526807054152590972465402, 61228751294246951869891671407294469506401133460669313068369993608651062307301536, 41981261972157910420555352577742115252749734931422260886610665615142932761250238, 92332289648534120255700799585162857690611895814212622902006472593032842219422300, 102090694836612045964656351247645673041342905792690679450732518780700786595757872, 8465306744686231379969736050689382339949995071265316552433666241539252681451520, 114072153081233359084524715014825650254537286682603109151986752844288607088786066, 39946361462751138749261511325777846481011288953117931061771127396007551287911208, 51243479474799144289518571031495536096625532453885999576052634625243425716758700, 132356504405092579871543186323238530972479261975470487510352508943760068475015440, 109077835346013498228568867183016137777644328620298812835459712256002833220195417, 52635267919343130972014005273289555808336337947193348140410148289978267235415648, 9568343438735227407132147420705807168258684366618511035784505242511446472528193, 136103745592722122037143341370556407561964415802887285393102934361453911394982400, 15501324115571167305412632833471884183641743683875758176471163573103721210677697, 124579054262159655532164017523017564697199759561416452868759873217906475930663652, 69331433672201876294056448428159828327113921951663941374636039203754564050923557, 134825790087045765574290263555594553874136924161813224135475519279020442040026864, 127098236196925756090074171499128508507461799729629969599917408442298996799214250, 120716315173788627251671396349879537684221828425501013413665864262612928100844788, 246230945837378885729579613348413794121875158206606559652651668292953179058653508, 182436930868427241575608788617950343128628563937798409868187047670441481734494464, 2216307326510769061988701188806623458793041637834505792592287312459658319545700, 217778196427604121810125555838576095983026719310491477185297193068203986197977500, 200042153662024093707446037685450040433674498805614787040971237961725493946807124, 55096521527758008435839474651130444687406648424301616531387151625485823586357376, 315911207494925949742212443025101639383551363855632617410391325922132118052280432, 160608721274889447938606989650810386105243008009388938737103600719751998405695052, 80485718020426913778898398898436382386718914865993732581279132006386834763843750, 175256027423949464821148437330609889703365513530429385704635213979205690543187968, 312494592697141143680238564093947039458907138790072672218576868913190841311490441, 12551558878313236197845748627693664902436846005140074555532691630477757920400492, 368163678666609325358026149200535116090648801749210267074911311082497122727619418, 132244486142872991925346591101049195464960273281071718729683433268064480383763200, 187524820546739515326467479985404725103464284941528452333038247179114024353648176, 283320427018968981710753682470612392210145925235229015984823155988278867852342424, 273076274412276025537791810337835157311632197268182698230310819989050497776963263, 327014096802403962955714851262399814244813548393488285833127238998882721132883968, 206832690482752439833856322955815020186765387390104398292271480795930880106073325, 104167288428075991079921385804154376915444422785935287020330329091692992364020356, 468442878028756757484855000070722747267796721762231179211069666438706434848755245, 13006681553773847728990900149289800641720551387610802780788594468812438984199760, 199716185379958028413200192962692404940513822154864483463050473557869065589649168, 412558417168152436059170177108518481504104909389966119467224740980715361039084900, 379013360598848524426838307544021120793535763669172279637583374247930017257612752, 79510803625960975136293110699095743477640774841480691165531320726532279504009152, 119246467719878286004186703543298639812649580965124121805161153548472942538790653, 44235048729597559877492812430806736314711896199059487848598597142896457753232432, 453319033816285234767354843915966019736243075972507643199351036007057824008570000, 300975897791737470999557383409844137620736489995632513055593286593028252152372832, 488688724028459389993054497130088474659149461722402520817247390457263798063265080, 98311703485802819685121101139900586756957739352203591545958914778011243453808576, 503894794312461918204750180188338003935699664049776370432270755067603639622480931]
enc = 1954128229670403595826293823451515985816812578139791173172421160740653397416251058891670696398940725266238000104900728729829302299509397650740333416176077

rc = RandCrack()
TMP_32bits = []
mask_32bits = (1 << 32) - 1

i = 1
for T in TMP[1:]:
    T = T // (i ** 2)
    for _ in range(8):
        TMP_32bits.append(T & mask_32bits)
        T >>= 32
    i += 1

for T in TMP_32bits[-624:]:
    rc.submit(T)

KEY = sum([rc.predict_getrandbits(256 >> _) ** 2 for _ in range(8)])
print(long_to_bytes(enc ^ KEY))