Custom Encryption - PicoCTF 2024
Description:
Can you get sense of this code file and write the function that will decode the given encrypted file content. Find the encrypted file here flag_info and code file might be good to analyze and get the flag.
Can you get sense of this code file and write the function that will decode the given encrypted file content. Find the encrypted file here flag_info and code file might be good to analyze and get the flag.
Inital recon
When it comes to these sort of reverse engineering challenges, I like to follow this methodology:
1. Understand what the code does, what the functions do and what variables are being input.
2. Write down the logic flow of the program
3. Make a program that reverses the logic flow to get any secrets we need
Looking through the code file, we can see that we have 6 functions. In order to not get overwhelmed, I like to take the functions one by one, understanding them what they do. Even if they end up being complicated, treating them as a “black box” and just knowing in general what it does also works.
1. Understand what the code does, what the functions do and what variables are being input.
2. Write down the logic flow of the program
3. Make a program that reverses the logic flow to get any secrets we need
Looking through the code file, we can see that we have 6 functions. In order to not get overwhelmed, I like to take the functions one by one, understanding them what they do. Even if they end up being complicated, treating them as a “black box” and just knowing in general what it does also works.
generator
Simple enough, it takes in 3 variables g,x and p and returns g^x % p
encrypt
Takes in a plaintext and a key. For every character in plaintext, multiply the ascii value of the character in plaintext by the key and 311.
Is_prime
Checks if a number is prime using “naive trial division primality test”.
Although you might not know the specific prime checking algorithm used (neither did I when I was solving), you can infer from the function name its function.
To double check, we can iterate through every number from 1 to 100 and check if they return True for is_prime(number). Sure enough, is_prime(number) returns True for every prime number.
dynamic_xor_encrypt
Two arguments, plaintext and text_key are given to return a cipher_text. From the for loop we can see that for every character in plaintext (starting from the end of plaintext), we add the character with the ascii value equivalent to the ascii value of the character in plaintext XOR the ascii value of the character chosen from text_key
for i, char in enumerate(plaintext[::-1]):
key_char = text_key[i % key_length]
encrypted_char = chr(ord(char) ^ ord(key_char))
cipher_text += encrypted_char
key_char = text_key[i % key_length]
encrypted_char = chr(ord(char) ^ ord(key_char))
cipher_text += encrypted_char
How would this look like? Lets say we want to encrypt our plaintext “gabbage” with a text_key of “abcd”
1. Reverse “gabbage” to get “egabbag”
2. XOR each character with “egabbag” with a different character from text_key. Once the chosen character from text_key “hits” the last character, “d”, wrap-around to use “a” instead
3. Save the output of the XOR into cipher_text
1. Reverse “gabbage” to get “egabbag”
2. XOR each character with “egabbag” with a different character from text_key. Once the chosen character from text_key “hits” the last character, “d”, wrap-around to use “a” instead
3. Save the output of the XOR into cipher_text
For readability’s sake the cipher text shown in the diagram is not the exact result of the XOR, like ‘e’ XOR ‘a’ does NOT give ‘f’.
Test
This is the main function. We get two numbers, p and q, and check if at least one of them are a prime. If none of them are primes, the function exits. Then, a and b are a random integer chosen from a range p-10 to p and g-10 to g (inclusive) respectively.
Next, u and v are defined using the generator function using g, a, p and g, b, p respectively. Variables key and b_key are defined using the generator function using v, a, p and u, b, p.
Next, u and v are defined using the generator function using g, a, p and g, b, p respectively. Variables key and b_key are defined using the generator function using v, a, p and u, b, p.
A check is used to ensure that b_key is equal to key. If it is, shared_key is initialised as the value of key, if not the function returns.
Finally, the cipher is calculated by passing in the plain_text into dynamic_xor_encrypt along with the text_key, and saving it as semi_cipher. semi_cipher is then passed into the encrypt function along with a shared_key to get the cipher.
Finally, the cipher is calculated by passing in the plain_text into dynamic_xor_encrypt along with the text_key, and saving it as semi_cipher. semi_cipher is then passed into the encrypt function along with a shared_key to get the cipher.
Reversing the program
Time to actually start coding! First, we look at the info we have. In enc_flag, we are given a, b and cipher.
a = 90
b = 26
cipher is: [61578, 109472, 437888, 6842, 0, 2052 ... 47894, 82104, 116314]
b = 26
cipher is: [61578, 109472, 437888, 6842, 0, 2052 ... 47894, 82104, 116314]
Also, on the last line, we can see that the whole program is run with “trudeau” being the text_key for the test function.
if __name__ == "__main__":
message = sys.argv[1]
test(message, "trudeau")
message = sys.argv[1]
test(message, "trudeau")
If we were to step by step reverse the program using cipher and the text_key, we can see that we fail as we don’t have the shared_key. Following the logic flow of the program, we can also see that the shared_key is calculated using p, g, a and b, with a and b being the variables we know.
So to crack this, we have to find a valid p and g that will allow us to get the correct shared_key to get the correct plain_text. The first thing I noticed was the small range in which a and b are taken from, being 11 possible numbers depending on p and q.
So to crack this, we have to find a valid p and g that will allow us to get the correct shared_key to get the correct plain_text. The first thing I noticed was the small range in which a and b are taken from, being 11 possible numbers depending on p and q.
a = randint(p-10, p)
b = randint(g-10, g)
This gives us 11*11 = 121 possible combinations of p and g. We can narrow this down further by looking at the checks on p and g performed, telling us that at least p or g are a prime number. We can also see that after a number of calls to the generator function using p, g, a and b, the key has to be equal to the b_key as well, reducing our brute force attack surface lesser.
Now that we know how to generate possible values of p and g that pass the program’s checks, we can generate possible values of shared_key, and begin to reverse the encryption functions of the program.
Now that we know how to generate possible values of p and g that pass the program’s checks, we can generate possible values of shared_key, and begin to reverse the encryption functions of the program.
Reversing the encrypt function
The ascii character for every value in the plaintext is multiplied by key and 311 and the result is appended to an array. So for every element in the array, we have to divide it by 311 and then divide it by the key, and find the character whose ascii value is equal to the result.
def decrypt(ciphertext, key):
plaintext = ""
for element in ciphertext:
plaintext += chr(element // 311 // key)
return plaintext
plaintext = ""
for element in ciphertext:
plaintext += chr(element // 311 // key)
return plaintext
Reversing the dynamic_xor_encrypt
One crucial property about xor is that its completely reversible, meaning that when A XOR B = C:
1. C XOR B = A
2. C XOR A = B
3. B XOR A = C
So if we know two variables like the cipher_text and text_key we can just XOR them together to get the plaintext.
To reverse this, we can just take each character in our cipher_text, XOR it using the same character from the key (using the same repeating key pattern), and then reverse that to get the plaintext!
1. C XOR B = A
2. C XOR A = B
3. B XOR A = C
So if we know two variables like the cipher_text and text_key we can just XOR them together to get the plaintext.
To reverse this, we can just take each character in our cipher_text, XOR it using the same character from the key (using the same repeating key pattern), and then reverse that to get the plaintext!
def dynamic_xor_decrypt(ciphertext, text_key):
plaintext = ""
key_length = len(text_key)
for i,char in enumerate(ciphertext):
key_char = text_key[i % key_length]
decrypted_char = chr(ord(char) ^ ord(key_char))
plaintext += decrypted_char
return plaintext[::-1]
plaintext = ""
key_length = len(text_key)
for i,char in enumerate(ciphertext):
key_char = text_key[i % key_length]
decrypted_char = chr(ord(char) ^ ord(key_char))
plaintext += decrypted_char
return plaintext[::-1]
Putting it all together
Here are the steps to find the flag:
1. Generate possible values of p and g based off of a and b respectively, where at least p or g are prime numbers and the resultant key is equal to b_key
2. Decrypt the cipher with our written decrypt() function using the cipher and the calculated shared_key, and save it as semi_cipher
3. Use the semi_cipher with text_key as input into our dynamic_xor_decrypt to get our plaintext!
1. Generate possible values of p and g based off of a and b respectively, where at least p or g are prime numbers and the resultant key is equal to b_key
2. Decrypt the cipher with our written decrypt() function using the cipher and the calculated shared_key, and save it as semi_cipher
3. Use the semi_cipher with text_key as input into our dynamic_xor_decrypt to get our plaintext!
def is_prime(p):
v = 0
for i in range(2, p + 1):
if p % i == 0:
v = v + 1
if v > 1:
return False
else:
return True
def generator(g, x, p):
return pow(g, x) % p
def dynamic_xor_decrypt(ciphertext, text_key):
plaintext = ""
key_length = len(text_key)
for i,char in enumerate(ciphertext):
key_char = text_key[i % key_length]
decrypted_char = chr(ord(char) ^ ord(key_char))
plaintext += decrypted_char
return plaintext[::-1]
def decrypt(ciphertext, key):
plaintext = ""
for element in ciphertext:
plaintext += chr(element // 311 // key)
return plaintext
a = 90
b = 26
text_key = "trudeau"
cipher = [61578, 109472, 437888, 6842, 0, 20526, 129998, 526834, 478940, 287364, 0, 567886, 143682, 34210, 465256, 0, 150524, 588412, 6842, 424204, 164208, 184734, 41052, 41052, 116314, 41052, 177892, 348942, 218944, 335258, 177892, 47894, 82104, 116314]
list_of_possible_p = range(a,a+10+1)
list_of_possible_g = range(b,b+10+1)
for possible_p in list_of_possible_p:
for possible_g in list_of_possible_g:
if not is_prime(possible_p) and not is_prime(possible_g):
break
u = generator(possible_g, a, possible_p)
v = generator(possible_g, b, possible_p)
key = generator(v, a, possible_p)
b_key = generator(u, b, possible_p)
if key != b_key:
break
shared_key = key
semi_cipher = decrypt(cipher,shared_key)
plain_text = dynamic_xor_decrypt(semi_cipher,text_key)
print(plain_text)
v = 0
for i in range(2, p + 1):
if p % i == 0:
v = v + 1
if v > 1:
return False
else:
return True
def generator(g, x, p):
return pow(g, x) % p
def dynamic_xor_decrypt(ciphertext, text_key):
plaintext = ""
key_length = len(text_key)
for i,char in enumerate(ciphertext):
key_char = text_key[i % key_length]
decrypted_char = chr(ord(char) ^ ord(key_char))
plaintext += decrypted_char
return plaintext[::-1]
def decrypt(ciphertext, key):
plaintext = ""
for element in ciphertext:
plaintext += chr(element // 311 // key)
return plaintext
a = 90
b = 26
text_key = "trudeau"
cipher = [61578, 109472, 437888, 6842, 0, 20526, 129998, 526834, 478940, 287364, 0, 567886, 143682, 34210, 465256, 0, 150524, 588412, 6842, 424204, 164208, 184734, 41052, 41052, 116314, 41052, 177892, 348942, 218944, 335258, 177892, 47894, 82104, 116314]
list_of_possible_p = range(a,a+10+1)
list_of_possible_g = range(b,b+10+1)
for possible_p in list_of_possible_p:
for possible_g in list_of_possible_g:
if not is_prime(possible_p) and not is_prime(possible_g):
break
u = generator(possible_g, a, possible_p)
v = generator(possible_g, b, possible_p)
key = generator(v, a, possible_p)
b_key = generator(u, b, possible_p)
if key != b_key:
break
shared_key = key
semi_cipher = decrypt(cipher,shared_key)
plain_text = dynamic_xor_decrypt(semi_cipher,text_key)
print(plain_text)
(venv) C:\Users\gabbage\Desktop\coding\venv>python custom_decryption.py
daf}bdigawp}}teyrrctfyd{jns`edcww
effr|}{fd`tssrse}srgtg}dyfbpaedgvv
daf}bdigawp}}teyrrctfyd{jns`edcww
f`gydzbmgcwpx~|eLrkwhCdfRP}`edhup
effr|}{fd`tssrse}srgtg}dyfbpaedgvv
daf}bdigawp}}teyrrctfyd{jns`edcww
f`gydzbmgcwpx~|eLrkwhCdfRP}`edhup
f`g~gzcjgcwpzeA|riwhAdglU}`ediuw
picoCTF{custom_d2cr0pt6d_49fbee5b}
daf}bdigawp}}teyrrctfyd{jns`edcww
f`gydzbmgcwpx~|eLrkwhCdfRP}`edhup
f`g~gzcjgcwpzeA|riwhAdglU}`ediuw
picoCTF{custom_d2cr0pt6d_49fbee5b} <-- here!
f`g~gzcjgcwpzeA|riwhAdglU}`ediuw
picoCTF{custom_d2cr0pt6d_49fbee5b}
effr|}{fd`tssrse}srgtg}dyfbpaedgvv
effr|}{fd`tssrse}srgtg}dyfbpaedgvv
bgepys~ddgtsrpoewpr{tevd|beqaed{qv
daf}bdigawp}}teyrrctfyd{jns`edcww
bgepys~ddgtsrpoewpr{tevd|beqaed{qv
daf}bdigawp}}teyrrctfyd{jns`edcww
daf}bdigawp}}teyrrctfyd{jns`edcww
ėŭþɉфʴЗɝáĒñöȦɥԵs܀Ƒr֬݇dϩٶ۪Ǘ#erĒ²
ėŭþɉфʴЗɝáĒñöȦɥԵs܀Ƒr֬݇dϩٶ۪Ǘ#erĒ²
daf}bdigawp}}teyrrctfyd{jns`edcww
effr|}{fd`tssrse}srgtg}dyfbpaedgvv
daf}bdigawp}}teyrrctfyd{jns`edcww
f`gydzbmgcwpx~|eLrkwhCdfRP}`edhup
effr|}{fd`tssrse}srgtg}dyfbpaedgvv
daf}bdigawp}}teyrrctfyd{jns`edcww
f`gydzbmgcwpx~|eLrkwhCdfRP}`edhup
f`g~gzcjgcwpzeA|riwhAdglU}`ediuw
picoCTF{custom_d2cr0pt6d_49fbee5b}
daf}bdigawp}}teyrrctfyd{jns`edcww
f`gydzbmgcwpx~|eLrkwhCdfRP}`edhup
f`g~gzcjgcwpzeA|riwhAdglU}`ediuw
picoCTF{custom_d2cr0pt6d_49fbee5b} <-- here!
f`g~gzcjgcwpzeA|riwhAdglU}`ediuw
picoCTF{custom_d2cr0pt6d_49fbee5b}
effr|}{fd`tssrse}srgtg}dyfbpaedgvv
effr|}{fd`tssrse}srgtg}dyfbpaedgvv
bgepys~ddgtsrpoewpr{tevd|beqaed{qv
daf}bdigawp}}teyrrctfyd{jns`edcww
bgepys~ddgtsrpoewpr{tevd|beqaed{qv
daf}bdigawp}}teyrrctfyd{jns`edcww
daf}bdigawp}}teyrrctfyd{jns`edcww
ėŭþɉфʴЗɝáĒñöȦɥԵs܀Ƒr֬݇dϩٶ۪Ǘ#erĒ²
ėŭþɉфʴЗɝáĒñöȦɥԵs܀Ƒr֬݇dϩٶ۪Ǘ#erĒ²
The “here!” has been added in post for readability
Thanks for reading!