This page has been machine-translated from the original page.
I participated in Gracier CTF 2023, which began on November 25, 2023, as part of 0nePadding and placed 150th.
I did not have much time during the competition this time, but I will briefly write up the challenges.
Table of Contents
ARISAI(Crypto)
I heard that RSA with multiple primes is more secure. My N is very large, so there should not be a problem.
The challenge provided the following code and output.txt.
from Crypto.Util.number import bytes_to_long
from Crypto.Util.number import getPrime
PRIME_LENGTH = 24
NUM_PRIMES = 256
FLAG = b"gctf{redacted}"
N = 1
e = 65537
for i in range(NUM_PRIMES):
prime = getPrime(PRIME_LENGTH)
N *= prime
ct = pow(bytes_to_long(FLAG), e, N)
print(f"{N=}")
print(f"{e=}")
print(f"{ct=}")N=1184908748889071774788034737775985521200704101703442353533571651469039119038363889871690290631780514392998940707556520304994251661487952739548636064794593979743960985105714178256254882281217858250862223543439960706396290227277478129176832127123978750828494876903409727762030036738239667368905104438928911566884429794089785359693581516505306703816625771477479791983463382338322851370493663626725244651132237909443116453288042969721313548822734328099261670264015661317332067465328436010383015204012585652642998962413149192518150858822735406696105372552184840669950255731733251466001814530877075818908809387881715924209232067963931299295012877100632316050826276879774867425832387424978221636157426227764972761357957047150626791204295493153062565652892972581618176577163744310556692610510074992218502075083140232623713873241177386817247671528165164472947992350655138814891455499972562301161585763970067635688236798480514440398603568227283629452476242623289661524243073929894099518473939222881149459574426407208658860251686137960952889074096311126991477096465624470265619377139983649503903820480974951491378311837933293607705488991162022547957926530402988912221198282579794590930661493745233069145707902854299501706154802038942258911515981663207152069613126155243024789689987554767962281273345273757236723762684230158310314189489269922058062081424352003908442430243686562569467793068370441732743572240164014190275463904986105758545036928880621165599686076511511089276388190078187849622221351011692443859919384379432387437072419707649486293684966456033518855679391672980173280496419686363359529398834403906418139786395934302273747490127295066208248715874656180233559644161531014137838623558729789331274400542717269108353265885948166102045041669627782992845494987948783304254174326130201166965174477449798721151991240203641
e=65537
ct=268829805459609475588440899873097740407996768854076329496002425282199615879909227647380967635165606878898541606457683227761652305836586321855100255485305118037701500609605019785162541750877335573032359895573772603246111506991979320486028250721513277767642375361127152574528694298160906073442383962020636918610527024050576972769852306021296823499884948279413653216802756618690182635446020844210831886652986287932378470425746444631963933610367607515800649608436183004088441881238148504635598468243968695248287570279766119573944421327504565309861792437849662128566261080923059583840204287527201636471106753069738472306223410300379312983945939043519755909420737707495224846116170095923898104488099329762265149868062693687303917610957104520999978944379566136253252697346935036425206126213766976582551430726756840294537354912787885103742021813054656962241068550049435394355553796824094853195888610994254949530524531633088750916669188277025883371307926545593346345011181011886157628805587723572874545440223921942144548540109099572715194182349314576321627183804149379561322969725485272107142991680959335537127382716195040449341448266408777436145121388591741613272241408064729715121476227737259932422493622000014673154665474739974557976672498027364986075870354093242809763072555932073688776712239151696700128393589329790478951588551070833013708885416360627613835550721939073618725634813608997025047929327270234611128029339388251117036658410438813874667672407000490721438737857471847655487642835059784967516451098631494261100960513521722400650533821661854325599281416744189966724295645707952292786069145361070873245192529272080607536319284389065418040578100669665069777133031446812281199863684982910055858515634879595144557407925298026899908970790756383369461817536923660051327566555421265363733995050644914554395836353253513Reading the provided Python script, we can see that ct in output.txt is the RSA encryption of the flag, where N is the product of 256 24-bit primes.
Although N, the product of 256 primes, is very large, the primes used are only 24 bits, so factoring it is easy.
This time, I simply used a table of primes I found online and took N mod p from the beginning to identify all of the constituent primes.
After successfully factoring it, I struggled a bit with constructing phi.
For multi-prime RSA like this challenge, the Euler totient seems to be defined as follows.
When I looked at the frequency of the recovered primes, I found that the three primes (8725153,11369903,16177433) were each used twice.
So, by handling only the duplicated primes with a term like p * (p-1), I was able to compute phi and successfully decrypt the ciphertext.
I was able to recover the flag with the following solver.
from Crypto.Util.number import long_to_bytes, bytes_to_long
n=1184908748889071774788034737775985521200704101703442353533571651469039119038363889871690290631780514392998940707556520304994251661487952739548636064794593979743960985105714178256254882281217858250862223543439960706396290227277478129176832127123978750828494876903409727762030036738239667368905104438928911566884429794089785359693581516505306703816625771477479791983463382338322851370493663626725244651132237909443116453288042969721313548822734328099261670264015661317332067465328436010383015204012585652642998962413149192518150858822735406696105372552184840669950255731733251466001814530877075818908809387881715924209232067963931299295012877100632316050826276879774867425832387424978221636157426227764972761357957047150626791204295493153062565652892972581618176577163744310556692610510074992218502075083140232623713873241177386817247671528165164472947992350655138814891455499972562301161585763970067635688236798480514440398603568227283629452476242623289661524243073929894099518473939222881149459574426407208658860251686137960952889074096311126991477096465624470265619377139983649503903820480974951491378311837933293607705488991162022547957926530402988912221198282579794590930661493745233069145707902854299501706154802038942258911515981663207152069613126155243024789689987554767962281273345273757236723762684230158310314189489269922058062081424352003908442430243686562569467793068370441732743572240164014190275463904986105758545036928880621165599686076511511089276388190078187849622221351011692443859919384379432387437072419707649486293684966456033518855679391672980173280496419686363359529398834403906418139786395934302273747490127295066208248715874656180233559644161531014137838623558729789331274400542717269108353265885948166102045041669627782992845494987948783304254174326130201166965174477449798721151991240203641
e=65537
c=268829805459609475588440899873097740407996768854076329496002425282199615879909227647380967635165606878898541606457683227761652305836586321855100255485305118037701500609605019785162541750877335573032359895573772603246111506991979320486028250721513277767642375361127152574528694298160906073442383962020636918610527024050576972769852306021296823499884948279413653216802756618690182635446020844210831886652986287932378470425746444631963933610367607515800649608436183004088441881238148504635598468243968695248287570279766119573944421327504565309861792437849662128566261080923059583840204287527201636471106753069738472306223410300379312983945939043519755909420737707495224846116170095923898104488099329762265149868062693687303917610957104520999978944379566136253252697346935036425206126213766976582551430726756840294537354912787885103742021813054656962241068550049435394355553796824094853195888610994254949530524531633088750916669188277025883371307926545593346345011181011886157628805587723572874545440223921942144548540109099572715194182349314576321627183804149379561322969725485272107142991680959335537127382716195040449341448266408777436145121388591741613272241408064729715121476227737259932422493622000014673154665474739974557976672498027364986075870354093242809763072555932073688776712239151696700128393589329790478951588551070833013708885416360627613835550721939073618725634813608997025047929327270234611128029339388251117036658410438813874667672407000490721438737857471847655487642835059784967516451098631494261100960513521722400650533821661854325599281416744189966724295645707952292786069145361070873245192529272080607536319284389065418040578100669665069777133031446812281199863684982910055858515634879595144557407925298026899908970790756383369461817536923660051327566555421265363733995050644914554395836353253513
primes = [8441831, 8450987, 8452019, 8473027, 8476817, 8523661, 8525711, 8608673, 8633423, 8641453, 8725153, 8725153, 8786017, 8796721, 8824679, 8850601, 8913481, 8933437, 9016037, 9041551, 9075889, 9095939, 9126197, 9142547, 9163981, 9172531, 9196001, 9223867, 9253319, 9265309, 9277921, 9298747, 9300803, 9357883, 9368759, 9405353, 9444839, 9552029, 9569057, 9584371, 9663629, 9696719, 9720223, 9748049, 9770723, 9801269, 9828727, 9836483, 9838117, 9853043, 9873373, 9883469, 9884603, 9905167, 9989579, 10000759, 10064897, 10114409, 10122389, 10213001, 10214591, 10228861, 10235447, 10344643, 10428001, 10433911, 10438013, 10441523, 10476001, 10514083, 10523977, 10605817, 10650929, 10667479, 10699517, 10731407, 10732091, 10754837, 10773781, 10849837, 10861127, 10893173, 10918459, 10943417, 10944433, 11028001, 11049739, 11057621, 11073793, 11084419, 11113789, 11152859, 11156681, 11230451, 11239903, 11369903, 11369903, 11462177, 11470343, 11504419, 11519971, 11543971, 11559637, 11625619, 11633267, 11661121, 11768401, 11847721, 11909747, 11915809, 11925691, 11928173, 11945093, 11990089, 12010259, 12089663, 12109277, 12231853, 12240667, 12274813, 12319117, 12339689, 12350357, 12358079, 12387329, 12407609, 12407959, 12515033, 12550357, 12599803, 12621067, 12652597, 12705883, 12804707, 12808151, 12824027, 12932669, 12967831, 13046717, 13059269, 13076249, 13128433, 13170671, 13202297, 13227367, 13328803, 13366687, 13371181, 13415921, 13417357, 13424921, 13430423, 13534007, 13561657, 13566431, 13568981, 13587683, 13625263, 13653811, 13655797, 13669967, 13673927, 13755149, 13799299, 13823059, 13865617, 13870601, 13997617, 14013617, 14044937, 14046449, 14086979, 14103413, 14162843, 14217041, 14311291, 14339863, 14340289, 14377679, 14407667, 14423561, 14435203, 14465153, 14466281, 14475521, 14482381, 14535811, 14548939, 14549063, 14588369, 14624459, 14633851, 14650763, 14693927, 14713939, 14738869, 14797501, 14880347, 14910199, 14922409, 14982181, 15005579, 15020413, 15031937, 15103373, 15181499, 15185399, 15209617, 15232961, 15299831, 15365261, 15441739, 15459343, 15470893, 15475193, 15489707, 15501071, 15682181, 15689647, 15689981, 15707093, 15707143, 15748631, 15792169, 15793247, 15798877, 15922301, 15947639, 16032721, 16045049, 16071229, 16080319, 16175597, 16177433, 16177433, 16198717, 16199101, 16212913, 16225283, 16254883, 16312763, 16336267, 16359283, 16405027, 16432721, 16497373, 16593167, 16594681, 16629163, 16632713, 16643707, 16657153, 16679137, 16701907, 16738913, 16755269]
phi = 1
t = 1
# https://crypto.stackexchange.com/questions/74891/decrypting-multi-prime-rsa-with-e-n-and-factors-of-n-given
set(primes)
for p in primes:
t *= p
if p in (8725153,11369903,16177433):
phi = phi * p * (p-1)
else:
phi *= (p-1)
assert(t == n)
d = pow(e,-1,phi)
long_to_bytes(pow(c,d,n))
# gctf{maybe_I_should_have_used_bigger_primes}SOP(Rev)
I am sure you know OOP, but do you also know SOP?
When I decompiled the provided ELF file in Ghidra, I found the following main function.
bool main(void)
{
size_t sVar1;
ssize_t sVar2;
sVar1 = strlen(&DAT_000060f0);
DAT_000061c8 = (int)sVar1;
if (DAT_000061c8 == 0) {
sVar2 = read(0,&DAT_000060f0,0x44);
DAT_000061c8 = (int)sVar2;
}
return DAT_000061c8 != 0x44;
}However, this function just stores standard input into DAT_000060f0 and returns whether its length matched 0x44, so honestly it is hard to tell what it is doing.
As a first test, I ran the program with 0x44 bytes of input, and it printed the string FAIL.
So I backtracked from the string FAIL in Ghidra and found a function that performs the following processing.
I also found that this function itself is registered at the following location as the callback for the undefined signal 0x16 via signal(0x16,Check);.
Reference: signal.h
At the same point, signals 0xe and 0x15 are also registered.
In the callback for signal 0xe, 0x15 is raised, and in the callback for signal 0x15, 0x16 is raised.
In other words, it seemed likely that once SIGTERM is triggered somewhere, a chain of processing begins and the flag is checked at the end.
I could not follow this chain properly while attaching gdb, so I used ltrace instead.
That let me observe the behavior: it starts from SIGSEGV, passes through several signals, and finally prints FAIL, as shown below.
Now, even though I still did not understand the fine details of the implementation, I could see that the last line compares whether (&DAT_00406220)[local_170] == local_58[local_170].
local_58 stores the 0x44-byte sequence defined at DAT_00404050.
In other words, it appears that the flag is an input whose transformed result in DAT_00406220 matches the byte sequence in DAT_00404050.
Tracing the code back a little, we can see that the values written into the region containing DAT_00406220 are taken from the region starting at DAT_00406140.
Tracing accesses to that region back further, we can see that each byte is repeatedly XORed at the following location.
The initial contents of the region from DAT_00406140 onward appear to be empty.
So, although the details were still unclear at this point, I guessed that XORing the flag with some key would produce the byte sequence at DAT_00404050.
To confirm this, I decided to inspect the data that ends up stored in DAT_00406220 after the input is transformed.
Since gdb was not working well, I inspected the contents of DAT_00406220 by rewriting the arguments to the printf function that prints FAIL. (Using Frida might be easier.)
I made the actual patch as follows.
When I fed the patched program 0x44 bytes of A as input, it printed the byte sequence stored in DAT_00406220 as shown below.
I then XORed the recovered byte sequence with A to restore the key, and XORed that with the byte sequence hardcoded at DAT_00404050, which yielded the correct flag as shown below.
Summary
SOP was a very interesting challenge.
It is an easy challenge if you can analyze the binary dynamically, but perhaps because each step is invoked via signals, I could not analyze it well with debuggers such as gdb.
I suspect the intended solution was to continue the dynamic analysis while hooking the signals with something like Frida, so I would like to try that alternative approach as well.