[BCTF 2016] Hyper RSA

The Plaid Parliament of Pwning participated in (and won) BCTF 2016, hosted by Tsinghua University. Here’s a writeup of one of the problems, which was to decrypt a ciphertext encrypted with a variant of RSA. It was categorized as a cryptography problem and worth 500 points (a hard problem).

We are provided a zipfile containing a censored picture of one run of the program showing the encryption of two messages and their ciphertexts, as well as the server program which implements the Hyper RSA algorithm.

The first message is a random message m1, and the second message m2 is the flag (hidden). Both ciphertexts c1 and c2 are shown. The zipfile also contains the source code for the server.

A hint specifies that we can extract the digits from the picture without having to copy them down by hand. Opening the JPEG in a hex editor and scrolling to the bottom reveals that m1, c1, and c2, in plain text, have been appended to the end.

The “Hyper RSA” algorithm consists simply of encrypting a message twice in succession with different RSA keys, i.e.
$latex c = (m^{e_1} mod n_1) ^ {e_2} mod n_2$

where n1 < n2. The server outputs the d1 and d2 for a given e1 and e2, and thus we can trivially obtain the prime factors p1, q1, p2 and q2 (PyCrypto’s Crypto.PublicKey.RSA computes p and q automatically given n, e and d):

from Crypto.PublicKey import RSA

n1 = 15648839760729136857611980482709455780823249059433822421717774306890912422191494755459005142111607992828285551194094172211798962121953438089140493712726087426107589267481640653515380577953758668008397344082640238769913089651014044547964783609544160815580263066891992072813496322236255529332740322328153851312961936661859569054622011061087082284128807141569973069232563526976554397613026154984099426439128269723550458457280468287574830259658190319585969033124798862730603620119663542163404213185266003198150728644986436777489704208328734400642015199114476591920301342491956560907159473860286478358614493839228472359041
n2 = 27651436873059903761538209234805214287355683678982466405670882487591411436642516539341196342881585483549012954046212429788184908293604454771642818107648395738428697059696871430441866540519287523373879820608795756105878030307235272632107775558053732559632831099019813290110266640343749177716635424859416795786735047143696302657241912433915888805902148923106710885221002650355051396187383500174867165635719900881013089530132697822486081686748180965007087119379517849387088878883805428586240671351051269319387834355886582079118795891068466933583725489045111641949617725339393138570317367622108145858007000011779852522969

e1 = e2 = 65537L
d1 = 801341322260814246824630460655399752818145838891922243118922907272623130275640575542371809160116520803999669038976151516590587254242271361630155437385122135618308277487043746787274626846099365088975410634318638956800407843947741481956296653701423679708979093527160617610847210849213017935527664094073337580381435393973290534456518582972757046608969344358144168412979473661735534751582089315363317465134585473746496679748814555064082863346987139238598778896812527500338856153967668724198040388824191290206624717357686156052566833286119146484827004344810295922696833773843457620396590761038521683261440122811630416689
d2 = 6112369592444250206652792120246931342309257205203457448753438128045787531968813603085828027210972868763821210389054724359391408920906476284797740298236146132148504421988015570026264866754702204115498069199988161171641286983855187064121722759807809689051998476150877140147205896190852409136531995665629661421145487633863099571087668485030471815418539707337877086184665963496813415503578237691985252628347956725542260965108071256348393247267672508371278456781458278900243152599830219742880994068918547883063177015037779478763064694436867660864340069789075521188306329779784328758407937664440952020715843097541060377469

m1 = 5
c1 = 8148957383904486872437828423394164937538328715010815908123576452594275320666784525739878146313196804749598164516555556022796130174158806815977650057288420682101057911994435698789551418753532099866792794103336174859039809215065280033792539448692428913979724682589906786272695510606035436810953248855087491552441188016588591196283340505465679930375746901953008354883148151847641317044080506488273851897144518225216105202686360980631572592060500127238603945606195064022141933818855331043259736453831468578091145713709685544140187848965375739364164364508893499612921555255013961546838234986344590731606667403558040625997

m2 = 6
c2 = 27329182398211347522899299621621113679724446962789840876562317801394564111071637212019506119701609492788475262089552181420526961381419064457579903801235959637592232728341456521117490176148105725533459268071829049691129946006080272549563173732461269479077427460450913074453578152281632632054473142217920030060804696732297435050576686329939098304245739417728714301710598689242692778518299820705103997578604937875292660978826056357830177747872982479026583072444666566525631068826210835394802088986175053586772425867255572780854762523224511193257888117843294675036009361255570186337202498474539261702804344134624782089612


k1 = RSA.construct((n1, e1, d1))
print 'p1 =', k1.p
print 'q1 =', k1.q

k2 = RSA.construct((n2, e2, d2))
print 'p2 =', k2.p
print 'q2 =', k2.q

With this information we have the entire private key. However, the exponents e1 and e2 used to encrypt the flag are censored out, so we have to find them in order to decrypt the flag.

e1 and e2 are each 9 digits long, and we are given (in a second hint) the first digits of each. Thus, we’re looking at testing 10⁸ possibilities for each. We can’t bruteforce both simultaneously – that would be 10¹⁶. However, we can apply a meet-in-the-middle attack – encrypt m1 with all possible e1 to get all possible intermediate values, then decrypt c1 with all possible e2 to find a matching intermediate value (thus “meeting in the middle” of the encryption algorithm). This will only require 2*10⁸ operations. One snag is that RSA decryption is very slow – on the order of O(k³) where k is the number of bits in the key. Thus, we have to optimize our attack carefully, and use a lot of CPU power to achieve bruteforce.

We ended up making three major optimizations:

1. When building the table, we use an incremental approach – instead of computing pow(m1, e1, n1) for each e1, we just multiply in one power of m1 per iteration, making building the e1 lookup table extremely fast.
2. Because computing decryptions mod n2 is slow (because n2 is long), we do decryptions and checking mod p2 instead, which is half as long (and thus saves us a factor of 8 on decryption).
3. We use gmp instead of Python’s built-in pow operators, resulting in approximately a 3x speedup. Note that the bottleneck is in the math operations, so using Python incurs only a very small overhead.

Here’s the bruteforce script:

from gmpy2 import mpz, powmod, invert

# meet in the middle attack
n1 = mpz(15648839760729136857611980482709455780823249059433822421717774306890912422191494755459005142111607992828285551194094172211798962121953438089140493712726087426107589267481640653515380577953758668008397344082640238769913089651014044547964783609544160815580263066891992072813496322236255529332740322328153851312961936661859569054622011061087082284128807141569973069232563526976554397613026154984099426439128269723550458457280468287574830259658190319585969033124798862730603620119663542163404213185266003198150728644986436777489704208328734400642015199114476591920301342491956560907159473860286478358614493839228472359041)
n2 = mpz(27651436873059903761538209234805214287355683678982466405670882487591411436642516539341196342881585483549012954046212429788184908293604454771642818107648395738428697059696871430441866540519287523373879820608795756105878030307235272632107775558053732559632831099019813290110266640343749177716635424859416795786735047143696302657241912433915888805902148923106710885221002650355051396187383500174867165635719900881013089530132697822486081686748180965007087119379517849387088878883805428586240671351051269319387834355886582079118795891068466933583725489045111641949617725339393138570317367622108145858007000011779852522969)
p1 = mpz(115828295588509413765657818406867516713730517750406039982953961273698342446377470065543059874105959316059071676627111613027995982755516722160046640303691478999889733390879707640738371507340736543076237714407338833975162482946492306016288364033279369606285818202050898542042181475127562843844261502082049451227)
q1 = mpz(135103773056655064969327506003939867649872833235629494898764581981413343302990941336623787091683416428670125487239155394679492615647758178987290636992620311385747374284630346686620855693905295085863655381869122493807428330545415365431415934084226911263424822550817854835936312436952242226359922048497488873683)
p2 = mpz(163285832687189913045952152660621786604149906417402530050953092553171258537152762832184438186860672227164970561277480748279613378334451380709795952602873533444456320203007264412590461372740523801471983692035577494148110307472755151546109784012759812974741115311165842719401610463185434834345546986734727953667)
q2 = mpz(169343760067858061351166362331954299819512318283672226414306253481409314715323098520315259960487582355659180136088759841701142965265979658078717533720357215488070848738430999730412016543181673065902912717103510024351166643904333588480201806104579175415269242403617262452711780440867442673992494021555894641907)

m1 = mpz(1291575311227647404937745977674300102552159140130724372672273512124326901689475940631797723907388299601908770592275163938119318483657985194901345321320)
c1 = mpz(3612783941217721669487918278209911521323696929552012175100130528144953435277957012327876297909487756767163399469731122537754642368918321895211682844060051902226307200945658526452184995263241224610748656158064831467711457662659609765597325107742484418555573571733455873166185394833773943367518472411975358177757721075900099526140241289604501293079211412322023186020382617546224962628798465635111775435684570876736680218992899063074934853328180993221927800114698375815660980849891750946707282694641977171200300901905249566807230865872745785916874656741470951342227797544099362706484433003094851882722308369118455538479)
c2 = mpz(13554020299054897579091249483707073724753575878577890667835151695153327166821147325776948828180031343971239625502353717032241825522884776444516550436927491420615799010177208450427000928631877919824890289537268758084609024561404818087048530732153137144763446412469130412144867577343408806134871838870680552607734311806612058857668100766723847349927926306865890803886354120634869482202437175237946453446209830904959307383604085169656048730378082783123213285644191038076249938111121280355516863102198358773908064076460289440391523937387728878878040531689192081196613749284337216979844083031586740238692461049241310327972)

# test: e1=e2=65537
# m1 = mpz(5)
# c1 = mpz(8148957383904486872437828423394164937538328715010815908123576452594275320666784525739878146313196804749598164516555556022796130174158806815977650057288420682101057911994435698789551418753532099866792794103336174859039809215065280033792539448692428913979724682589906786272695510606035436810953248855087491552441188016588591196283340505465679930375746901953008354883148151847641317044080506488273851897144518225216105202686360980631572592060500127238603945606195064022141933818855331043259736453831468578091145713709685544140187848965375739364164364508893499612921555255013961546838234986344590731606667403558040625997)

cache = {}

cur = powmod(m1, 10000000, n1)
for e1 in xrange(10000000, 20000000):
    if e1 % 100000 == 0:
        print "build progress:", e1
    cache[cur % p2] = e1
    cur = (cur * m1) % n1

p2a = p2-1
c1p = c1 % p2

def doit(e2):
    if e2 % 100000 == 0:
        print "check progress:", e2

    try:
        dp = invert(e2, p2a)
    except Exception:
        return None

    mp = powmod(c1p, dp, p2)
    if mp in cache:
        print "FOUND IT!!!", cache[mp], e2
        return cache[mp], e2

    return None

import multiprocessing
p = multiprocessing.Pool()
results = p.map(doit, xrange(20000000, 30000000))
for r in results:
    if r is not None:
        print r

We were able to obtain a solution in approximately 15 minutes after running it on a 48-core machine. The values were e1 = 134217757, e2 = 251658263.

We plugged these in to the HyperRSA decryption algorithm:

e1 = 134217757
e2 = 251658263

n1 = 15648839760729136857611980482709455780823249059433822421717774306890912422191494755459005142111607992828285551194094172211798962121953438089140493712726087426107589267481640653515380577953758668008397344082640238769913089651014044547964783609544160815580263066891992072813496322236255529332740322328153851312961936661859569054622011061087082284128807141569973069232563526976554397613026154984099426439128269723550458457280468287574830259658190319585969033124798862730603620119663542163404213185266003198150728644986436777489704208328734400642015199114476591920301342491956560907159473860286478358614493839228472359041
n2 = 27651436873059903761538209234805214287355683678982466405670882487591411436642516539341196342881585483549012954046212429788184908293604454771642818107648395738428697059696871430441866540519287523373879820608795756105878030307235272632107775558053732559632831099019813290110266640343749177716635424859416795786735047143696302657241912433915888805902148923106710885221002650355051396187383500174867165635719900881013089530132697822486081686748180965007087119379517849387088878883805428586240671351051269319387834355886582079118795891068466933583725489045111641949617725339393138570317367622108145858007000011779852522969
p1 = 115828295588509413765657818406867516713730517750406039982953961273698342446377470065543059874105959316059071676627111613027995982755516722160046640303691478999889733390879707640738371507340736543076237714407338833975162482946492306016288364033279369606285818202050898542042181475127562843844261502082049451227
q1 = 135103773056655064969327506003939867649872833235629494898764581981413343302990941336623787091683416428670125487239155394679492615647758178987290636992620311385747374284630346686620855693905295085863655381869122493807428330545415365431415934084226911263424822550817854835936312436952242226359922048497488873683
p2 = 163285832687189913045952152660621786604149906417402530050953092553171258537152762832184438186860672227164970561277480748279613378334451380709795952602873533444456320203007264412590461372740523801471983692035577494148110307472755151546109784012759812974741115311165842719401610463185434834345546986734727953667
q2 = 169343760067858061351166362331954299819512318283672226414306253481409314715323098520315259960487582355659180136088759841701142965265979658078717533720357215488070848738430999730412016543181673065902912717103510024351166643904333588480201806104579175415269242403617262452711780440867442673992494021555894641907

m1 = 1291575311227647404937745977674300102552159140130724372672273512124326901689475940631797723907388299601908770592275163938119318483657985194901345321320
c1 = 3612783941217721669487918278209911521323696929552012175100130528144953435277957012327876297909487756767163399469731122537754642368918321895211682844060051902226307200945658526452184995263241224610748656158064831467711457662659609765597325107742484418555573571733455873166185394833773943367518472411975358177757721075900099526140241289604501293079211412322023186020382617546224962628798465635111775435684570876736680218992899063074934853328180993221927800114698375815660980849891750946707282694641977171200300901905249566807230865872745785916874656741470951342227797544099362706484433003094851882722308369118455538479
c2 = 13554020299054897579091249483707073724753575878577890667835151695153327166821147325776948828180031343971239625502353717032241825522884776444516550436927491420615799010177208450427000928631877919824890289537268758084609024561404818087048530732153137144763446412469130412144867577343408806134871838870680552607734311806612058857668100766723847349927926306865890803886354120634869482202437175237946453446209830904959307383604085169656048730378082783123213285644191038076249938111121280355516863102198358773908064076460289440391523937387728878878040531689192081196613749284337216979844083031586740238692461049241310327972

from Crypto.Util.number import inverse

d1 = inverse(e1, (p1-1)*(q1-1))
d2 = inverse(e2, (p2-1)*(q2-1))
m = pow(pow(c2, d2, n2), d1, n1)
print format(m, 'x').decode('hex')

to get the flag: BCTF{learn-y0u-A_haske11-f0r_9rea7-g00d}