Hello readers! Welcome to the fourth installment of this series. It’s been a while since I posted. A lot has been happening, which kept me busy and caused delays. My biggest enemy, procrastination, has also played a significant role in the delay of this post.
Along with another cute anime detective girl, this post will cover a few crypto challenges from Hackthebox — Cyber Apocalypse 2023 and PicoCTF 2023, which coincidentally were happening at the same time.
1. HackTheBox: Cyber Apocalypse — 2023
1.1 Ancient Encodings
After extracting the compressed file named crypto_ancient_encodings.zip, a folder was obtained. This folder contained two files: source.py and output.txt.
Contents of source.py:
from Crypto.Util.number import bytes_to_long
from base64 import b64encode
FLAG = b"HTB{??????????}"
def encode(message):
return hex(bytes_to_long(b64encode(message)))
def main():
encoded_flag = encode(FLAG)
with open("output.txt", "w") as f:
f.write(encoded_flag)
if __name__ == "__main__":
main()Contents of output.txt:
0x53465243657a467558336b7764584a66616a4231636d347a655639354d48566664326b786246397a5a544e66644767784e56396c626d4d775a4446755a334e665a58597a636e6c33614756794d33303dAnalysis:
The code performs Base64 encoding on the flag, then converts the resulting encoding into a long integer, and finally converts it to hexadecimal before saving it in the output.txt file.
Solution:
To retrieve the original flag, we can reverse the process by performing the steps in the reverse order. The following code snippet can automate this task.
from base64 import b64decode
enc = open("output.txt").read()
print(b64decode(bytes.fromhex(enc[2:])).decode())
Flag: HTB{1n_y0ur_j0urn3y_y0u_wi1l_se3_th15_enc0d1ngs_ev3rywher3}
1.2 Small StEps
The challenge offers a compressed file for download, as well as a server that can be accessed through the IP address and port number provided after launching the challenge instance.
Once the compressed file is unzipped, the server.py file for the challenge can be accessed.
Here is the source code of this file:
from Crypto.Util.number import getPrime, bytes_to_long
FLAG = b"HTB{???????????????}"
assert len(FLAG) == 20
class RSA:
def __init__(self):
self.q = getPrime(256)
self.p = getPrime(256)
self.n = self.q * self.p
self.e = 3
def encrypt(self, plaintext):
plaintext = bytes_to_long(plaintext)
return pow(plaintext, self.e, self.n)
def menu():
print('[E]ncrypt the flag.')
print('[A]bort training.\n')
return input('> ').upper()[0]
def main():
print('This is the second level of training.\n')
while True:
rsa = RSA()
choice = menu()
if choice == 'E':
encrypted_flag = rsa.encrypt(FLAG)
print(f'\nThe public key is:\n\nN: {rsa.n}\ne: {rsa.e}\n')
print(f'The encrypted flag is: {encrypted_flag}\n')
elif choice == 'A':
print('\nGoodbye\n')
exit(-1)
else:
print('\nInvalid choice!\n')
exit(-1)
if __name__ == '__main__':
main()At the time if writing this writeup, the access to the server is not available. Thankfully, I already copied the output at the time of solving.
Connecting to the server outputs the modulo-N, public exponent e and the ciphertext c.
N: 9001100467552486969553229765203658410516172280078199709205226979005433439647792509243329495101889932329462050137390960223836162647640453330906371967229537
e: 3
The encrypted flag is: 70407336670535933819674104208890254240063781538460394662998902860952366439176467447947737680952277637330523818962104685553250402512989897886053Analysis:
The challenge source code implements RSA algorithm. Upon a closer inspection, an unusual thing to notice is that the size of the redacted flag is significantly small. This builds up an assumption that this challenge can be solved using small exponent or Direct Root Attack. Considering the difficulty of the challenge this assumption turned out to be true.
Explanation:
Lets first discuss that how this attack works, what causes this attack to work in the first place. This is not an RSA vulnerability as RSA is mathematically secure. The way its being implemented in the above source code raise concerns.
It often happens that m(message) to be sent isn’t larger than n after exponentiating with e. This makes the whole RSA encryption pointless as m can be retrieved easily by getting the e-th root of the ct. To counter, m goes through padding first.
Following is a simple mathematical representation of the above explanation:
You can read further about it here.
Solution:
To solve, we can write a small python snippet to recover the flag.
import gmpy2
N = 9001100467552486969553229765203658410516172280078199709205226979005433439647792509243329495101889932329462050137390960223836162647640453330906371967229537
e = 3
ct = 70407336670535933819674104208890254240063781538460394662998902860952366439176467447947737680952277637330523818962104685553250402512989897886053
pt = gmpy2.iroot(ct,e)[0] #pt = ᵉ√ct
print(bytes.fromhex(hex(pt)[2:]).decode())Script execution:
Flag: HTB{5ma1l_E-xp0n3nt}
1.3 Perfect Synchronization
The challenge provides a zip file containing the challenge script source.py and output.txt.
Contents of source.py:
from os import urandom
from Crypto.Cipher import AES
from secret import MESSAGE
assert all([x.isupper() or x in '{_} ' for x in MESSAGE])
class Cipher:
def __init__(self):
self.salt = urandom(15)
key = urandom(16)
self.cipher = AES.new(key, AES.MODE_ECB)
def encrypt(self, message):
return [self.cipher.encrypt(c.encode() + self.salt) for c in message]
def main():
cipher = Cipher()
encrypted = cipher.encrypt(MESSAGE)
encrypted = "\n".join([c.hex() for c in encrypted])
with open("output.txt", 'w+') as f:
f.write(encrypted)
if __name__ == "__main__":
main()Partial contents of output.txt:
.
.
.
68d763bc4c7a9b0da3828e0b77b08b64
e9b131ab270c54bbf67fb4bd9c8e3177
200ecd2657df0197f202f258b45038d8
68d763bc4c7a9b0da3828e0b77b08b64
e9b131ab270c54bbf67fb4bd9c8e3177
457165130940ceac01160ac0ff924d86
200ecd2657df0197f202f258b45038d8
61331054d82aeec9a20416759766d9d5
8cbd4cfebc9ddf583a108de1a69df088
dfc8a2232dc2487a5455bda9fa2d45a1
61331054d82aeec9a20416759766d9d5
68d763bc4c7a9b0da3828e0b77b08b64
3a17ebebf2bad9aa0dd75b37a58fe6ea
.
.
.Analysis:
The code initially make sures that all characters of the MESSAGE are either uppercase(A-Z), curly brackets( '{' , '}' ) or underscore (_).
The code then uses the Cipher class to create an object cipher which during initialization, generates 16 bytes key and 15 bytes of random data stored as an attribute of the object named salt.
The code then iterates through all the characters of MESSAGE, concatenate it with the 15 bytes salt random data and AES encrypts using the the key. The encrypted data is first converted into hexadecimal format and saved in a file called output.txt.
Approach:
Each character in the MESSAGE is combined with a common random salt, and whenever a character is repeated in the MESSAGE, the same encrypted output is repeated.
We can use Frequency Analysis after substituting every repeating encrypted data with a random character.
Here is a small snippet from Wikipedia:
In cryptanalysis, frequency analysis (also known as counting letters) is the study of the frequency of letters or groups of letters in a ciphertext. The method is used as an aid to breaking classical ciphers.
Frequency analysis is based on the fact that, in any given stretch of written language, certain letters and combinations of letters occur with varying frequencies.
But here is the problem, there are to two curly brackets, spaces and underscores which are inside the MESSAGE and needed to be figured out before random substitution.
Here is the list of instructions for the special case which I followed:
- The cipher output with both open(“{“) and close(“}”) curly brackets as an input won’t repeat.
- The first cipher is with opening bracket as its plaintext while the latter is with closing.
- The format of the flag is
HTB{.....}. If the encrypted output of one step after the closing bracket's cipher and four steps before the opening bracket's cipher matches, that specific ciphertext is substituted with spaces(" "). - If the ciphers between the curly brackets doesn’t matches with ciphers outside the bracket, those will be substituted with underscores.
After applying the above instructions, substitute all the remaining matching ciphers with random alphabets(A-Z).
Solution:
I solved this challenge manually, coming up with the above rules during trial and error. Used classic “Find-replace” to substitute alphabets and special characters.
For the sake of writeup, I wrote a script that applies all the above instructions on the output file. While scripting, I completely butchered programming efficiency, not following any rules. Somehow after a while was able to have my script running and decided not to modify it. As the saying goes, “If the code works, don’t touch it!”.
output = [] #List from output.txt
l = len(output)
#cat output.txt | sort| uniq -c
values = [
[8, '0df9b4e759512f36aaa5c7fd4fb1fba8'],
[104, '200ecd2657df0197f202f258b45038d8'],
[31, '2190a721b2dcb17ff693aa5feecb3b58'],
[8, '293f56083c20759d275db846c8bfb03e'],
[5, '2fc20e9a20605b988999e836301a2408'],
[88, '305d4649e3cb097fb094f8f45abbf0dc'],
[84, '34ece5ff054feccc5dabe9ae90438f9d'],
[45, '3a17ebebf2bad9aa0dd75b37a58fe6ea'],
[54, '457165130940ceac01160ac0ff924d86'],
[22, '4a3af0b7397584c4d450c6f7e83076aa'],
[2, '5ae172c9ea46594cea34ad1a4b1c79cd'],
[34, '5d7185a6823ab4fc73f3ea33669a7bae'],
[103, '5f122076e17398b7e21d1762a61e2e0a'],
[7, '60e8373bfb2124aea832f87809fca596'],
[230, '61331054d82aeec9a20416759766d9d5'],
[19, '66975492b6a53cc9a4503c3a1295b6a7'],
[100, '68d763bc4c7a9b0da3828e0b77b08b64'],
[23, '78de2d97da222954cce639cc4b481050'],
[75, '8cbd4cfebc9ddf583a108de1a69df088'],
[22, '9673dbe632859fa33b8a79d6a3e3fe30'],
[4, 'a94f49727cf771a85831bd03af1caaf5'],
[1, 'c53ba24fbbe9e3dbdd6062b3aab7ed1a'],
[142, 'c87a7eb9283e59571ad0cb0c89a74379'],
[41, 'd178fac67ec4e9d2724fed6c7b50cd26'],
[31, 'dfc8a2232dc2487a5455bda9fa2d45a1'],
[37, 'e23c1323abc1fc41331b9cdfc40d5856'],
[87, 'e9b131ab270c54bbf67fb4bd9c8e3177'],
[61, 'f89f2719fb2814d9ab821316dae9862f'],
[10, 'fb78aed37621262392a4125183d1bfc9'],
[1, 'fbe86a428051747607a35b44b1a3e9e9']]
curly_bracs = [brac[1] for brac in values if brac[0] == 1]
# Fiding space
#<space>HTB{.....}<space>
brac_loc = [i for i in range(l) if output[i] in curly_bracs]
if output[brac_loc[0]-4] == output[brac_loc[1]+1]:
space = output[brac_loc[1]+1]
#finding _
uscr = None
for i in range(brac_loc[0]+1,brac_loc[1]):
for j in range(brac_loc[0]):
if output[j] == output[i]:
break
elif j == brac_loc[0]-1:
uscr = i
if uscr:
break
spec = [space, output[brac_loc[0]], output[brac_loc[1]], output[uscr]]
a = [' ', '{', '}', '_']
s = list(zip(spec,a))
#removing
table = []
for i in range(len(values)):
if not(values[i][1] in spec):
table.append(values[i][1])
#creating dic
dic = {}
for i in range(26):
dic[table[i]] = str(chr(65+i))
for u in s:
dic[u[0]] = u[1]
#replacing
for i in range(l):
output[i] = dic[output[i]]
print(''.join(output))The original script can be found on my github.
The produced output:
VFTNUTGIL MGMYLBXB XB SMBTW RG PHT VMIP PHMP XG MGL QXATG BPFTPIH RV OFXPPTG YMGQUMQT ITFPMXG YTPPTFB MGW IRJSXGMPXRGB RV YTPPTFB RIIUF OXPH AMFLXGQ VFTNUTGIXTB JRFTRATF PHTFT XB M IHMFMIPTFXBPXI WXBPFXSUPXRG RV YTPPTFB PHMP XB FRUQHYL PHT BMJT VRF MYJRBP MYY BMJCYTB RV PHMP YMGQUMQT XG IFLCPMGMYLBXB VFTNUTGIL MGMYLBXB MYBR ZGROG MB IRUGPXGQ YTPPTFB XB PHT BPUWL RV PHT VFTNUTGIL RV YTPPTFB RF QFRUCB RV YTPPTFB XG M IXCHTFPTEP PHT JTPHRW XB UBTW MB MG MXW PR SFTMZXGQ IYMBBXIMY IXCHTFB VFTNUTGIL MGMYLBXB FTNUXFTB RGYL M SMBXI UGWTFBPMGWXGQ RV PHT BPMPXBPXIB RV PHT CYMXGPTEP YMGQUMQT MGW BRJT CFRSYTJ BRYAXGQ BZXYYB MGW XV CTFVRFJTW SL HMGW PRYTFMGIT VRF TEPTGBXAT YTPPTF SRRZZTTCXGQ WUFXGQ ORFYW OMF XX SRPH PHT SFXPXBH MGW PHT MJTFXIMGB FTIFUXPTW IRWTSFTMZTFB SL CYMIXGQ IFRBBORFW CUDDYTB XG JMKRF GTOBCMCTFB MGW FUGGXGQ IRGPTBPB VRF OHR IRUYW BRYAT PHTJ PHT VMBPTBP BTATFMY RV PHT IXCHTFB UBTW SL PHT MEXB CROTFB OTFT SFTMZMSYT UBXGQ VFTNUTGIL MGMYLBXB VRF TEMJCYT BRJT RV PHT IRGBUYMF IXCHTFB UBTW SL PHT KMCMGTBT JTIHMGXIMY JTPHRWB RV YTPPTF IRUGPXGQ MGW BPMPXBPXIMY MGMYLBXB QTGTFMYYL HPS{M_BXJCYT_BUSBPXPUPXRG_XB_OTMZ} IMFW PLCT JMIHXGTFL OTFT VXFBP UBTW XG ORFYW OMF XX CRBBXSYL SL PHT UB MFJLB BXB PRWML PHT HMFW ORFZ RV YTPPTF IRUGPXGQ MGW MGMYLBXB HMB STTG FTCYMITW SL IRJCUPTF BRVPOMFT OHXIH IMG IMFFL RUP BUIH MGMYLBXB XG BTIRGWB OXPH JRWTFG IRJCUPXGQ CROTF IYMBBXIMY IXCHTFB MFT UGYXZTYL PR CFRAXWT MGL FTMY CFRPTIPXRG VRF IRGVXWTGPXMY WMPM CUDDYT CUDDYT CUDDYTNow slapping the above output into this website quipquip, will do its frequency analysis magic and produce the desire result with the flag hidden.
FREQUENCY ANALYSIS IS BASED ON THE FACT THAT IN ANY GIVEN STRETCH OF WRITTEN LANGUAGE CERTAIN LETTERS AND COMBINATIONS OF LETTERS OCCUR WITH VARYING FREQUENCIES MOREOVER THERE IS A CHARACTERISTIC DISTRIBUTION OF LETTERS THAT IS ROUGHLY THE SAME FOR ALMOST ALL SAMPLES OF THAT LANGUAGE IN CRYPTANALYSIS FREQUENCY ANALYSIS ALSO KNOWN AS COUNTING LETTERS IS THE STUDY OF THE FREQUENCY OF LETTERS OR GROUPS OF LETTERS IN A CIPHERTEXT THE METHOD IS USED AS AN AID TO BREAKING CLASSICAL CIPHERS FREQUENCY ANALYSIS REQUIRES ONLY A BASIC UNDERSTANDING OF THE STATISTICS OF THE PLAINTEXT LANGUAGE AND SOME PROBLEM SOLVING SKILLS AND IF PERFORMED BY HAND TOLERANCE FOR EXTENSIVE LETTER BOOKKEEPING DURING WORLD WAR II BOTH THE BRITISH AND THE AMERICANS RECRUITED CODEBREAKERS BY PLACING CROSSWORD PUZZLES IN MAJOR NEWSPAPERS AND RUNNING CONTESTS FOR WHO COULD SOLVE THEM THE FASTEST SEVERAL OF THE CIPHERS USED BY THE AXIS POWERS WERE BREAKABLE USING FREQUENCY ANALYSIS FOR EXAMPLE SOME OF THE CONSULAR CIPHERS USED BY THE JAPANESE MECHANICAL METHODS OF LETTER COUNTING AND STATISTICAL ANALYSIS GENERALLY HTB{A_SIMPLE_SUBSTITUTION_IS_WEAK} CARD TYPE MACHINERY WERE FIRST USED IN WORLD WAR II POSSIBLY BY THE US ARMYS SIS TODAY THE HARD WORK OF LETTER COUNTING AND ANALYSIS HAS BEEN REPLACED BY COMPUTER SOFTWARE WHICH CAN CARRY OUT SUCH ANALYSIS IN SECONDS WITH MODERN COMPUTING POWER CLASSICAL CIPHERS ARE UNLIKELY TO PROVIDE ANY REAL PROTECTION FOR CONFIDENTIAL DATA PUZZLE PUZZLE PUZZLEFlag: HTB{A_SIMPLE_SUBSTITUTION_IS_WEAK}
1.4 Multipage Recyclings
The challenge provides a zip file containing the challenge script source.py and output.txt.
Contents of source.py:
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import random, os
FLAG = b'HTB{??????????????????????}'
class CAES:
def __init__(self):
self.key = os.urandom(16)
self.cipher = AES.new(self.key, AES.MODE_ECB)
def blockify(self, message, size):
return [message[i:i + size] for i in range(0, len(message), size)]
def xor(self, a, b):
return b''.join([bytes([_a ^ _b]) for _a, _b in zip(a, b)])
def encrypt(self, message):
iv = os.urandom(16)
ciphertext = b''
plaintext = iv
blocks = self.blockify(message, 16)
for block in blocks:
ct = self.cipher.encrypt(plaintext)
encrypted_block = self.xor(block, ct)
ciphertext += encrypted_block
plaintext = encrypted_block
return ciphertext
def leak(self, blocks):
r = random.randint(0, len(blocks) - 2)
leak = [self.cipher.encrypt(blocks[i]).hex() for i in [r, r + 1]]
return r, leak
def main():
aes = CAES()
message = pad(FLAG * 4, 16)
ciphertext = aes.encrypt(message)
ciphertext_blocks = aes.blockify(ciphertext, 16)
r, leak = aes.leak(ciphertext_blocks)
with open('output.txt', 'w') as f:
f.write(f'ct = {ciphertext.hex()}\nr = {r}\nphrases = {leak}\n')
if __name__ == "__main__":
main()Contents of output.txt:
ct = bc9bc77a809b7f618522d36ef7765e1cad359eef39f0eaa5dc5d85f3ab249e788c9bc36e11d72eee281d1a645027bd96a363c0e24efc6b5caa552b2df4979a5ad41e405576d415a5272ba730e27c593eb2c725031a52b7aa92df4c4e26f116c631630b5d23f11775804a688e5e4d5624
r = 3
phrases = ['8b6973611d8b62941043f85cd1483244', 'cf8f71416111f1e8cdee791151c222ad']Analysis:
The challenge script uses AES encryption with ECB mode. The encryption operation is performed on the randomly generated IV (Initialization vector). At first it looked like the class is implementing CBC mode encryption but the odd thing was the that encryption was performed on IV and XORed with the plaintext. I soon realized that this is also one of the encryption mode used in block ciphers. It's called Cipher feedback (CFB) mode.
Explanation::
CBC mode uses the encrypted output of the previous block to XOR with the next plaintext block to produce an intermediate cipher. That cipher then goes through the encryption algorithm of AES producing the final cipher block. Here is image representation:
CFB on the other directly AES encrypts the previously produced cipher to output the intermediate result. That intermediate result is XORed with plaintext to ouput the final cipher block. Here is the visual representation:
Approach:
The object class have a method named leak which if we look closer is returning out the intermediate values.
The method takes the encrypted_blocks list as an argument, generates a number r (which in this case is 3), use r and r+1 as an index number of that list to perform AES encrytion which produces two intermediate cipher of the next block from that indexed block.
Solution:
The output.txt gives out the leaked intermediate values of block number 4 and 5. Given the final ciphertext as well, simply performing XOR operation between the number block and its corresponding intermediate values will get us the flag.
Let’s try it in action:
def blockify(message, size):
return [message[i:i + size] for i in range(0, len(message), size)]
def xor(a, b):
return b''.join([bytes([_a ^ _b]) for _a, _b in zip(a, b)])
ct = "bc9bc77a809b7f618522d36ef7765e1cad359eef39f0eaa5dc5d85f3ab249e788c9bc36e11d72eee281d1a645027bd96a363c0e24efc6b5caa552b2df4979a5ad41e405576d415a5272ba730e27c593eb2c725031a52b7aa92df4c4e26f116c631630b5d23f11775804a688e5e4d5624"
r = 3
phrases = ['8b6973611d8b62941043f85cd1483244', 'cf8f71416111f1e8cdee791151c222ad']
ct = blockify(bytes.fromhex(ct),16)
print(xor(ct[r+1], bytes.fromhex(phrases[0])))
print(xor(ct[r+2], bytes.fromhex(phrases[1])))
Flag: HTB{CFB_15_w34k_w17h_l34kz}
2. PicoCTF 2023
2.1 HideToSee
Description:
The challenge provides the image to download named atbash.jpg.
It looks like a steganography challenge where there is some hidden file to extract.
Steghide does our job.
A file named encrypted.txt was extracted out with the following contents:
krxlXGU{zgyzhs_xizxp_x3y8z63y}The flag was encoded with Atbash cipher as shown in the image. Decoding with any online decoder will produce the flag.
Flag: picoCTF{atbash_crack_c3b8a63b}
2.2 ReadMyCert
Description:
The challenge provides with a Certificate signing request(CSR) file to download. According to Wikipedia:
In public key infrastructure systems, a certificate signing request is a message sent from an applicant to a certificate authority of the public key infrastructure in order to apply for a digital identity certificate.
The objective of this challenge is to read the certificate file. A tool like openssl can be used to read the contents.
$ openssl req -in readmycert.csr -noout -text
Certificate Request:
Data:
Version: 1 (0x0)
Subject: CN = picoCTF{read_mycert_60f83ace}, name = ctfPlayer
Subject Public Key Info:
Public Key Algorithm: rsaEncryption
Public-Key: (2048 bit)
Modulus:
00:ff:8a:32:07:28:14:00:2b:6f:bb:d6:c6:0f:c2:
63:37:b8:f4:75:5f:71:39:3d:bb:be:62:67:0d:06:
7f:6d:1e:65:f0:ae:08:91:29:8f:25:3d:e5:ee:db:
9e:9d:19:b8:d7:c2:98:b8:8d:fd:d1:3a:62:3d:4f:
ac:ad:18:f4:33:27:15:02:67:4b:70:7e:5c:d9:d9:
d7:80:f7:87:e9:75:a7:b7:f3:c8:b8:70:58:ff:53:
a1:9f:be:e8:69:5a:36:f4:5d:b6:d3:49:2e:53:0c:
df:d6:c8:f6:da:4e:b2:3b:a7:5a:cb:5a:e9:fc:14:
c8:9d:27:5d:ad:cd:01:c0:7b:03:3e:ac:a4:7c:41:
b5:c6:8a:28:d0:a7:0e:07:e7:fc:02:b1:1f:36:20:
1d:9a:2b:d4:1e:f6:d8:ba:f9:73:a7:e3:1e:7c:03:
8c:4e:9b:d9:eb:25:c3:38:e9:af:1e:e9:f8:5a:7a:
b3:e8:94:bd:03:bd:6f:7a:0f:a0:6c:d1:c5:a1:a0:
60:7f:60:e4:6c:70:68:46:1c:dd:d5:08:a3:11:84:
21:a4:93:21:97:ba:d8:58:66:a1:58:f0:6b:da:75:
38:33:a8:dc:c8:82:7c:b2:70:b0:f7:3c:3f:59:cf:
5e:b3:19:aa:ca:a9:bf:0b:89:fa:33:dd:27:dd:19:
7b:2d
Exponent: 65537 (0x10001)
Attributes:
Requested Extensions:
X509v3 Extended Key Usage:
TLS Web Client Authentication
Signature Algorithm: sha256WithRSAEncryption
Signature Value:
03:0e:30:25:78:93:6c:fe:59:3c:c7:5b:49:27:96:c6:4d:94:
d6:f4:76:7d:45:24:cf:f9:a2:db:f7:04:7a:60:76:f1:6f:7e:
a8:1f:7c:02:42:d2:96:d9:cb:1a:f8:1f:5a:9b:2b:c0:ed:39:
88:72:fe:10:58:50:32:d4:af:4f:b4:52:58:cf:fb:54:db:83:
46:2e:3e:cd:ce:61:a1:02:cd:16:a2:db:c0:f7:f4:f4:f6:41:
18:a1:8b:b5:5c:cd:f3:0b:a4:5b:6f:7d:1c:42:84:8b:53:3d:
e8:60:ce:cc:a3:75:16:03:a5:d6:e6:95:18:10:ba:8d:54:02:
9a:d7:30:db:6a:69:73:73:7e:67:8e:a8:dd:44:a2:bd:3e:26:
37:43:7b:fe:d1:5c:6d:c9:6e:85:a6:66:e8:b5:85:40:03:0d:
ac:7c:db:ae:4d:31:b2:b2:38:6e:40:0f:96:cc:a2:35:ec:49:
b3:a5:a9:fa:c9:0a:2e:d2:df:6d:e5:9f:f2:7f:70:73:4d:4f:
e9:7e:a5:93:a5:c8:2e:b1:04:00:fe:01:92:70:14:fb:ed:fb:
be:76:92:11:2a:b5:38:7f:75:16:a0:00:fb:1a:c3:89:63:70:
84:bf:f1:9b:e9:b8:ee:b3:55:09:02:12:cb:7c:97:b6:69:93:
95:2a:2c:ef
Contents of the flag is on the subject line.
Flag: picoCTF{read_mycert_60f83ace}
2.3 rotation
Description:
The challenge provides a downloadable file named encrypted.txt with the following contents:
xqkwKBN{z0bib1wv_l3kzgxb3l_nl5k4283}As the name suggest, the flag is encrypted using a rotation cipher. Slapping it in cyberchef and check every rotation will produce the flag.
The flag was encrypted using 8 character rotation backwards.
Flag: picoCTF{r0tat1on_d3crypt3d_fd5c4283}
2.4 SRA
Description:
After launching the instance, we are given the challenge file to download and a set of DOMAIN and PORT to connect to the launched instance.
The challenge file is named chal.py with the following contents:
from Crypto.Util.number import getPrime, inverse, bytes_to_long
from string import ascii_letters, digits
from random import choice
pride = "".join(choice(ascii_letters + digits) for _ in range(16))
gluttony = getPrime(128)
greed = getPrime(128)
lust = gluttony * greed
sloth = 65537
envy = inverse(sloth, (gluttony - 1) * (greed - 1))
anger = pow(bytes_to_long(pride.encode()), sloth, lust)
print(f"{anger = }")
print(f"{envy = }")
print("vainglory?")
vainglory = input("> ").strip()
if vainglory == pride:
print("Conquered!")
with open("/challenge/flag.txt") as f:
print(f.read())
else:
print("Hubris!")Analysis:
The source code gives a glimpse of RSA being implemented with non textbook variable names. Replacing these names with textbook variables will help in further analysis.
A more clean and easy to understand code:
from Crypto.Util.number import getPrime, inverse, bytes_to_long
from string import ascii_letters, digits
from random import choice
m = "".join(choice(ascii_letters + digits) for _ in range(16))
p = getPrime(128)
q = getPrime(128)
N = p * q
e = 65537
d = inverse(e, (p - 1) * (q - 1))
ct = pow(bytes_to_long(m.encode()), e, N)
print(f"{ct = }")
print(f"{d = }")
print("vainglory?")
vainglory = input("> ").strip()
if vainglory == m:
print("Conquered!")
with open("/challenge/flag.txt") as f:
print(f.read())
else:
print("Hubris!")This program is attached with the launched instance which provides the user with the ciphertext ct and private exponent d when the user connects with it. Further it asks for the decrypted plaintext m to which if given accurately, will print out the flag.
Approach:
We are given the ciphertext ct and private exponent d from the server. Public exponent e is already hardcoded in the challenge file.
We have to somehow recover Modulo-N from the given values to decrypt the ciphertext. Using the product of e and d then subtracting 1 will produce a multiple(k) of Euler's totient function phi. The above statement can be mathematically represented as:
As we know phi can be deduced to (p-1)*(q-1).
Here is the list of step by step instructions to find the values of both primes.
- List down all possible factors of
ed-1. - Take all possible combinations of these factors.
- Multiply them together, add
1and check if its a prime. - If step 3 returns true, compare the bit length of that prime to the bit length given which is 128 bits in the challenge source code.
Now we have our prime number. Check for all possible combinations to get the other one. In case we get more than 2 primes, simply make combinations of two primes together, multiply them together to get the Modulo-N, use it to decrypt the plaintext and if the decoded output is alphanumeric, we get the correct plaintext m.
Slap the plaintext to the server instance to recieve the flag.
Solution:
I used sage’s in-built factor and Combinations functions to help me script the program easily.
Connecting to the server generated the private exponent and the ciphertext.
Here is the solution code:
e = 65537
d = 810361095203075329357484242946716927961146066907350563335467995181289177537
ct = 34387896249574356730924521216936364430435271510517548386929128354440191093429
phi = (e*d)-1
list = []
for a,b in factor(phi):
for _ in range(b):
list.append(a)
primes = []
print("factoing primes using combinations")
for i in range(len(list)):
for comb in Combinations(list,i):
prod = product(comb)
if is_prime(prod + 1):
prime = prod + 1
if prime.nbits() == 128:
primes.append(prime)
print(primes)
print("decrypting cipher")
for vals in Combinations(primes,2):
n = product(vals)
try:
m = bytes.fromhex(hex(pow(ct,d,n))[2:]).decode()
if m.isalnum():
print(m)
break
except:
passExecuting the script with the given values will decrypt the cipher.
Entering the plaintext to the server will get us the flag.
Flag: picoCTF{7h053_51n5_4r3_n0_m0r3_38268294}
