HousePlant CTF 2020: Returning Stolen Archives

Reading time ~2 minutes

Cool RSA crypto challenge in a CTF that I had a lot of fun with. I especially liked the beginner section which had a nice gradual ramp up with challenge difficulty. The final beginner challenge in each category was like a combo of what you had done until that point.

This challenge reads:

So I was trying to return the stolen archives securely, but it seems that I had
to return them one at a time, and now it seems the thieves stole them back! Can 
you help recover them once and for all? It seems they had to steal them one at 
a time...

Hint! Well you sure as hell ain't going to solve this one through factorization.

With the challenge we get these files:

  • intercepted.txt
  • returningstolenarchives.py

The intercepted.txt contains long integers that look like an RSA key and some ciphertext:

n = 54749648884874001108038301329774150258791219273879249601123423751292261798269586163458351220727718910448330440812899799 
e = 65537
ct = [52052531108833646741308670070505961165002560985048445381912028939564989677616205955826911335832917245744890104862186090,24922951057478302364724559167904980705887738247412638765127966502743153757232333552037075100099370197070290632101808468,31333127727137796897042309238173536507191002247724391776525004646835609286736822503824661004274731843794662964916495223,37689731986801363765434552977964842847326744893755747412237221863834417045591676371189948428149435230583786704331100191,10128169466676555996026197991703355150176544836970137898778443834308512822737963589912865084777642915684970180060271437,31333127727137796897042309238173536507191002247724391776525004646835609286736822503824661004274731843794662964916495223,32812400903438770915197382692214538476619741855721568752778494391450400789199013823710431516615200277044713539798778715,48025916179002039543667066543229077043664743885236966440148037177519549014220494347050632249422811334833955153322952673,52052531108833646741308670070505961165002560985048445381912028939564989677616205955826911335832917245744890104862186090,32361547617137901317806379693272240413733790836009458796321421127203474492226452174262060699920809988522470389903614273,4363489969092225528080759459787310678757906094535883427177575648271159671231893743333971538008898236171319923600913595,47547012183185969621160796219188218632479553350320144243910899620916340486530260137942078177950196822162601265598970316,32361547617137901317806379693272240413733790836009458796321421127203474492226452174262060699920809988522470389903614273,33230176060697422282963041481787429356625466151312645509735017885677065049255922834285581184333929676004385794200287512,32315367490632724156951918599011490591675821430702993102310587414983799536144448443422803347161835581835150218650491476,6693321814134847191589970230119476337298868688019145564978701711983917711748098646193404262988591606678067236821423683,32710099976003111674253316918478650203401654878438242131530874012644296546811017566357720665458366371664393857312271236,49634925172985572829440801211650861229901370508351528081966542823154634901317953867012392769315424444802884795745057309,50837960186490992399835102776517955354761635070927126755411572132063618791417763562399134862015458682285563340315570436]

The python script looks to be how the encryption was performed minus some of the important bits like the primes:

p = [redacted]
q = [redacted]
e = 65537
flag = "[redacted]"

def encrypt(n, e, plaintext):
  print("encrypting with " + str(n) + str(e))
  encrypted = []
  for char in plaintext:
    cipher = (ord(char) ** int(e)) % int(n)
    encrypted.append(cipher)
  return(encrypted)

n = p * q
ct = encrypt(n, e, flag)
print(ct)

So I spent a while messing around and ignoring the ciphertext. The modulus (N) in the RSA key is 394 bits long. A bit too long to factor within the time we had. I tried some common attacks I’m used to seeing in CTFs but nothing worked right away.

I refocused back onto the ciphertext. There sure were a lot of them. I started wondering what kinds of attacks we can use when we’ve got a single modulus with multiple ciphertexts. This ran me around in circles for a while.

Finally I decided to re-read the clue and re-read the Python code and it became obvious. They were actually encrypting the flag one single byte at a time. RSA is deterministic and when I encrypt the letter r with a public key I always get the same output.

So all I needed to do was run a brute force for each ASCII printable character that might appear in a plaintext through this public key and see if the encrypted output match the ciphertexts we have.

I reused the given code to come up with:

import string

cts = [52052531108833646741308670070505961165002560985048445381912028939564989677616205955826911335832917245744890104862186090,24922951057478302364724559167904980705887738247412638765127966502743153757232333552037075100099370197070290632101808468,31333127727137796897042309238173536507191002247724391776525004646835609286736822503824661004274731843794662964916495223,37689731986801363765434552977964842847326744893755747412237221863834417045591676371189948428149435230583786704331100191,10128169466676555996026197991703355150176544836970137898778443834308512822737963589912865084777642915684970180060271437,31333127727137796897042309238173536507191002247724391776525004646835609286736822503824661004274731843794662964916495223,32812400903438770915197382692214538476619741855721568752778494391450400789199013823710431516615200277044713539798778715,48025916179002039543667066543229077043664743885236966440148037177519549014220494347050632249422811334833955153322952673,52052531108833646741308670070505961165002560985048445381912028939564989677616205955826911335832917245744890104862186090,32361547617137901317806379693272240413733790836009458796321421127203474492226452174262060699920809988522470389903614273,4363489969092225528080759459787310678757906094535883427177575648271159671231893743333971538008898236171319923600913595,47547012183185969621160796219188218632479553350320144243910899620916340486530260137942078177950196822162601265598970316,32361547617137901317806379693272240413733790836009458796321421127203474492226452174262060699920809988522470389903614273,33230176060697422282963041481787429356625466151312645509735017885677065049255922834285581184333929676004385794200287512,32315367490632724156951918599011490591675821430702993102310587414983799536144448443422803347161835581835150218650491476,6693321814134847191589970230119476337298868688019145564978701711983917711748098646193404262988591606678067236821423683,32710099976003111674253316918478650203401654878438242131530874012644296546811017566357720665458366371664393857312271236,49634925172985572829440801211650861229901370508351528081966542823154634901317953867012392769315424444802884795745057309,50837960186490992399835102776517955354761635070927126755411572132063618791417763562399134862015458682285563340315570436]
n = 54749648884874001108038301329774150258791219273879249601123423751292261798269586163458351220727718910448330440812899799
e = 65537

def encrypt(n, e, plaintext):
  encrypted = []
  for char in plaintext:
    cipher = pow(ord(char), e, n)
    encrypted.append(cipher)
  return(encrypted)

flag = ""
for c in cts:
    for p in string.printable:
        candidate = encrypt(n, e, p)[0]
        if candidate == c:
            flag += p
            break
    
print flag

Which worked first go for the flag:

$ python returningstolenarchives.py 
rtcp{cH4r_bY_Ch@R!}

WPI CTF 2020: Notwannasigh

Fairly straightforward reversing challenge with a malware / ransomware flavor. The challenge text reads:Please help! An evil script-kiddi...… Continue reading

RITSEC CTF 2018: Cictrohash

Published on November 18, 2018

Square CTF 2018: Dot-n-dash

Published on November 15, 2018