picoCTF
Scrambled Rsa [140 pts]
Challenge Description:
Hmmm I wonder if you have learned your lesson… Let’s see if you understand RSA and how the encryption works. Connect with nc mercury.picoctf.net 6276.
Connect to the provided service. Here’s what is given (your values will differ):
flag: 481165007640192685925839082224424287117039446602202654875314953700819932949692634877481182861650707519395506809594451541694369294594734742339905940615189107761687155764219862155310609419774682608208705655402449119770595640052680163783693045566519070662380415578397395057249793034477232716525546428170447332558176890678672861374648919050533675705071222638342426519428465341995123881441659755433541244872290673566744470254558297971874899655358549971164188112887971305157022673888861188678514430886151104717369867472814554442545252264526145023376785441673762565628817473541726808180932824462857785689417425733415356974952900215532223498606326715057961206821464608536247491570125680612581507756771587436727584180976980327893227455779388808724253195787575659153477857396967545401562502552798082054661460584954135702906790940389148521194598531616861883618110118844085184193406402087608534219331648615206021704042330536727909102899848610438343846966086766979729003560813803898059842248148587469978758311682201795523719395432485352514856696656641218653840895267599333014448905443130615868453508865644751947836947325838822990635574270732253385911574418167358084141922114061525182164049551296996047554652461982925793980278587469064860792708936400608243029744880999594264102221623500802669194819290162471561289061487787523450924834546562190907749841060141948561096020114681550872647934530764889427214778736686178808493353925295636288964978691392726450539028819756157077548593452244128017796736519831342693797611711071878971094428203521754247260010397841158066687584715390384360638509718246077759969886580463449196254347246277432076872858869168659672369609504627762177082396985212580978903625555786382424665892776111444165312427345313386285093288777509863664184893361822842823347651476904841655199842585041734552118451713222754193491875296825733880913497191015871716200887200638236284281013449649527388772116002281401972656493509243992429509181961373596070257219866542547042705341026907600248134654958382844930351886867149407037136130587538830454392316856361651514389565717167337609390168051679564632815489782256590002947225434703691044748172104411639504862594879867011507025633104686648083635639352502670381116833407461772755608689552706600603759164237828653850801647595067887113967750154038183463966587225275687298137445058010537081069200391800601043124513529822560320965390948921607205358980305863401469878139334572214934125714863923235834875877170139412198149227430828688915913657977209993582542184574558696262571382989104827323650755235678119665874929333243553200113311319021030053260369677206653975798357629914203523132383676415853132353157702496302545370417465526763393462818113026698179846649163994608421876786044844380701660034277050588698961221442359110076053111160494985473345304608716370524485291943464597110190868115453881943643275036380795788853197936171920228867243851463178707396044169115686118047334832011970458930490824313805602660723501444402237891359724195437879575679538569141539921242249727748555121345123159849162867931285220640285414845438882682118852457711944551485384854771223398040448596962315250011223340668931467114911525578007564886109318122501111648383857782102029168812490248605928325240780325385746722852096847355846091959729096358251452377266248744536332598528306498148027595339488072625196292634572608702001048442515855298814155695560502294966257474148532519431843031425499308294753266190092291281918419517761984034979805242004384346799415299628594689342763682456308947104682816756599802657917394872291839475622444296826687628000005398968946127851495258381852134591034133015876258234111742543072279095569819585682425381984581613921052364711520443488561406684916736465880713355426951824402183444685620996156440828367702721351879778867080748654259435826175297055497634552557503082784381208564245929776196044105705061812645054546912102266370327017105520397864983634737426881895507047560280952174107383600682223184624614432616305921537892017426239752045100087264404227002810231565118768471775732127978353674540928581494351103292621829418765552132682039460897802706618885357020877396457809155797828252759799940465132888469160072041836379737666846060625767817149973094951613472914965666374135227588627695879804223985249726682353843612769693468626466663874995306536412923043104661214055615143180121849153753229687561527768737526703210660672305916368792603840731185669002776109586194284191330943033922270994734969000263289041538065480435270114884926354009239130598780184356681904307656241975796655679648434562882473336199895238446229492625612585943652288007430705989007758059238071908090499894751688058941272749392907941804651706519904343033394772918085895552216435674285652673849149640954474443209047346369157790797447627572682701596655127480598857714232985208428120653230432295487082856111170011634476370571129611042118360404052876436727530155204055608836884260390501317613609777815998050804598122420801159042991149523565274704851172128734572105987579319662597314404907680594942972211298561251639484176261502465656104824960386278032143441730110959347993781619924685790639083441508167586870354129007096856451210501307143853798131901487408176428221142956778450581694547598447626582913908625837258017383776974332607291218091074205538643647978073497135143949489245640006187367014986889414059305370603424320171034201188983093017301275536345961870066358644336694962549748327036360182284531792302228920850083895517994357966394759212279075211262454004108045547661681695037902256172208602518701083361229961525462715142137603423564977249901247498653791728271356511233647341752555011861699788293075916624978269364630299727584429585255491503105367247782175005847177370317718261574998499372843882401027309086160982323214640581823765428933529635233037015738868592335010132966894205625612090796574110712786148626077206852979380176312752976646980932480261588770284383981714042677672244055607476653749588949510350921075801510052532231478831177173398415766591193354383622680608040034014706171404362361166453358582650814985410045256632893660563060275105790877889447381580450142572489908307337947930513419771376853568511552748240532592446746871922039276732577639945710602577122057530840573903864684727867222300675728415296702549563037549976941996922841258374140922652997095958170687845869306012120624572610271406567590809275935791901459573147649492088924427532465752443370909014590214161795169283922365239916397514456868423022275420192567186016125094261451586220636385979444229169472310806713745888090359986593696458363392250553277389212532079409861113476980138015547206565658169548885003994903827886336775504667429788602965302479077058836766018163034654723563201039357906662664012954941867472683774318603600113459432458655888877799237643467386471306549992137230456546628991235038754742735165027987194635481915539844363129663077274470044003493232757056272365938674052191207120176659638968710794658396794158179900720302383886909470197049654137459033185781971623512021988894733270923968845379380049181355582099898535015232062549757406547155363927820902198377536619614541315360169483233685978111363789933810302007694431951942286350497293641037476562282777665095529206960319629609768265535820428698746240505573734468954994159756656685792771341933840894683213950576949962954469870852168282293969907958241518938311571799376098709298908838888246336715249413659915767014347597200639584867720865226902511742711361303344111452136017554835133449278365352286772728045165921038400058807768660237076168988786700682510536009737528511262295611611375888709879407418806044630958923764249927097104304307188062024137054530930758963123054688198475120888909935532721264289532532016387364549579601138498411259965382096688599021865395013534685951566263044128267630646757788587211028321909562596215560013192290876664018604580234834098590644145083889769549714888277215073379155940788377956362097314330218439756597938585889488767895117424966989240932955885309177863130959383369134068839412179791752477071496276814026719934830182610050457114003
n: 139563406662308725292816726377564259170547585733773979065867576401620211510458979169326108488749371060812588115525550755891128752854310292715210458767377150613316709104750192560881668059980075635109559101654926637468313323177582543663321739183049245964211743312514188284120517739895402556606480943192303896371
e: 65537
I will encrypt whatever you give me:
So we’re given a ciphertext, the modulus n, and public exponent e. We’re also given an encryption oracle for anything we want.
Huh… that ciphertext is really long. Way longer than n. Maybe there’s no modulo used? To test this, I tried taking the 65537th root of it, but it obviously didn’t work because it’s not large enough to be anything significantly larger than 1.
So… what’s happened here then? Well, the title of the challenge seems to be a hint. From what I can tell, it seems to be implying that the text was scrambled? So maybe scrambled the letters and encrypted each letter individually?
I tried sending the service some letters and then using Ctrl + F to search for the resulting ciphertext in the flag ciphertext. Nothing seemed to be working. Eventually, I decided to just skip to ‘p’ because I figured the string ‘picoCTF’ had to be encrypted in there somehow. Luckily, it worked! Then I tried ‘i’. That didn’t work… Then ‘c’. That didn’t work either…
So I then tried to encrypt “pico” to see if that would help. I searched for the ‘p’ ciphertext in the string. Still there! But the ‘i’ ciphertext once again was not. At this point, I figured that individual letters probably wouldn’t work.
It took me a while until I finally decided to test different prefixes of “pico”. I encrypted “pi” and “pic” as well. I checked if “p” was in the encryption for “pi”. That worked. Then, I checked if the ciphertext for “pi” was in “pic”. That didn’t work… but wait! I noticed that the ciphertexts for “pi” and “pic” contained the same starting string. Hmm… I removed the “p” ciphertext from the “pi” ciphertext and searched the remaining string in the “pic” ciphertext. That worked!
So what’s happening is that the ciphertext for “i” of “pic” is the same for the ciphertext for “i” of “pi”. Similarly, it’s likely that the ciphertext for “c” of “pic” is the same for the ciphertext for “c” of “pico”.
We’re almost done – there’s just one more thing to consider. This challenge is called “Scrambled: RSA” and we can observe that the order of the ciphertexts for individual letters seems to change between the encryptions of “pi”, “pic”, and “pico”. Therefore, we just need to make sure we keep in mind that this ciphertext is not in order while solving!
In order to solve this problem, we can now write an exploit program. This is the general idea:
- Get the flag, n, and e.
- Create a dictionary with a (key, value) pair of (ciphertext, individual flag letter). This will store the ciphertexts for each individual character of our flag. The point of this is so we can remove all of them at each step, as doing so will isolate the ciphertext for the next character.
- Create a string to keep track of our current flag string.
- Loop for some arbitrarily large range. We can just break the loop later when we find a ‘}’.
- Create another dictionary. This will record the ciphertext for each character we test as the next character of the flag.
- Now we’re going to check each character, including the numbers (0-9), uppercase and lowercase letters (a-zA-Z), and the special characters of ‘_’, ‘{‘, and ‘}’.
- For each character, we’re going to send the following: current_flag_string + character + ‘\n’
- As an example, if our current flag string is “pic” and our current character is “o”, this would just send the string “pico” to the service.
- The ‘\n’ is just to make the program actually sends it
- For each send, we will receive the ciphertext. Then, for every ciphertext in the dictionary storing the pair (ciphertext, individual flag letter), we will remove it from the received ciphertext. This will isolate the ciphertext for our individual character.
- Then, we will add the pair (ciphertext, character) to our current iteration’s dictionary that was described in step 5.
- Finally, after iterating through all possible characters, we will loop through the current iteration’s dictionary’s keys. For every ciphertext, we will check if it is in the flag ciphertext. If it is, that means we found our next character! Once we do, we will update our flag letters dictionary with the ciphertext of the current character and update our flag string with the new character.
See the below implementation. Run the program and get the flag!
picoCTF{bad_1d3a5_2268684}
from pwn import *
conn = remote('mercury.picoctf.net', 6276)
flag = conn.recvuntil('\n', drop=True)[6:].decode()
n = conn.recvuntil('\n', drop=True)[3:]
e = conn.recvuntil('\n', drop=True)[3:]
print(len(flag))
letters = dict()
s = ''
for j in range(0, 100):
print(j)
d = dict()
for i in range(0, 26):
send = s + chr(ord('a') + i) + '\n'
conn.send(send)
text = conn.recvuntil('\n', drop=True)[50:].decode()
#print("sent", send)
for key in letters.keys():
text = text.replace(key, '')
d[text] = send[:-1]
for i in range(0, 26):
send = s + chr(ord('A') + i) + '\n'
conn.send(send)
text = conn.recvuntil('\n', drop=True)[50:].decode()
for key in letters.keys():
text = text.replace(key, '')
d[text] = send[:-1]
for i in range(0, 10):
send = s + str(i) + '\n'
conn.send(send)
text = conn.recvuntil('\n', drop=True)[50:].decode()
for key in letters.keys():
text = text.replace(key, '')
d[text] = send[:-1]
a = ['_', '{', '}']
for i in a:
send = s + i + '\n'
conn.send(send)
text = conn.recvuntil('\n', drop=True)[50:].decode()
for key in letters.keys():
text = text.replace(key, '')
d[text] = send[:-1]
for k in d.keys():
if k in flag:
print(d[k])
#flag = flag.replace(k, '')
#print("Flag:", flag)
letters[k] = d[k]
s += d[k][-1]
if s[-1] == '}':
break
print('done!')