Cryptography Challenge
Hello Been a while since i dropped a CTF writeup
I plan to write about a Return-Oriented Programming (ROP) challenge here I completed earlier this month, along with two interesting cryptography challenges I worked on over the weekend as part of the UrchinSec CTF. All of these challenges were rated medium difficulty by the event organizers.
CHALLENGE 1: WarmUp
from sympy import mod_inverse
def generate_knapsack():
knapsack = [1, 2]
for i in range(6):
knapsack.append(sum(knapsack) + 1)
return knapsack
def convert_to_bits(message):
bits = []
for char in message:
char_bits = bin(ord(char))[2:].zfill(8)
bits.extend([int(b) for b in char_bits])
return bits
def encrypt_message(message, knapsack, m, n):
bits = convert_to_bits(message)
chunk_size = len(knapsack)
chunks = [bits[i:i + chunk_size] for i in range(0, len(bits), chunk_size)]
ciphertext = []
for chunk in chunks:
if len(chunk) < chunk_size:
chunk += [0] * (chunk_size - len(chunk))
c_value = sum(k * b for k, b in zip(knapsack, chunk))
encrypted_value = (c_value * n) % m
ciphertext.append(encrypted_value)
return ciphertext
if __name__ == "__main__":
message = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
knapsack = generate_knapsack()
m = 257
n = random.randint(-1000, 1000)
ciphertext = encrypt_message(message, knapsack, m, n)
print("Ciphertext:", ciphertext)
Ciphertext: [251, 210, 197, 79, 48, 120, 179, 12, 197, 143, 107, 230, 230, 230, 89, 89, 107, 217, 217, 217, 80, 242, 158, 179, 25, 55, 210, 80, 88, 230, 107, 80, 43, 199, 43, 80, 30, 230, 251, 80, 125, 55, 25, 80, 48, 25, 204, 204, 204, 204, 215]
SOLUTION
Let’s go over how this ciphertext was generated. First, a variable called knapsack was created. This knapsack variable is then used along with a random number n and a modulus variable m = 257.
The goal here is to retrieve the original message from the given ciphertext generated using this algorithm.
The first thing I did was analyze the encrypt_message function, which performs the encryption. This function converts the message into bits and separates them into chunks of length len(knapsack). It then multiplies each chunk by the unknown variable n and applies the modulus.
The ciphertext we have is the result after this operation.
c_value = sum(k * b for k, b in zip(knapsack, chunk))
encrypted_value = (c_value * n) % m
Let’s take a look at how the ciphertext is generated, each of the value of knapsack is multiplied by a bit of the chunk message
There may be a flaw here. Consider the operation (c_value * n) % m. The key point to note is that if the modulus operation is applied to a smaller positive number, it does not affect the result
For example :
2 % 7 == 2
A potential flaw here lies in the knapsack value being set as [1, 2, 4, 8, 16, 32, 64, 128], since generate_knapsack() returns a static value. Recall that c_value is generated by summing the product of each knapsack value with corresponding bits (either 1 or 0). In the unlikely scenario where all bits are set to 1 (non-ASCII), c_value would be 255, which is less than the modulus.
This is where n helps resolve the issue: by multiplying c_value by n, it increases the value beyond the modulus, making the ciphertext harder to reverse.
Finding n
The n used to generate the cipher is an integer between -1000 and 1000, not a large keyspace to bruteforce if you ask me , however its always important to do things more efficiently “when you can”.
since I know part of the plaintext (what the flag begins with) and i can use that to derive the n used in the equation that provides the corresponding cipher.
Note: every flag starts with “urchinsec”
Encrypting my own flag
First i converted the first 2 characters (ur) to binary as done in the encryption algorithm above
u = [0, 1, 1, 1, 0, 1, 0, 1]
r = [0, 1, 1, 1, 0, 0, 1, 0]
then i got their corresponding c_value
where k = [1, 2, 4, 8, 16, 32, 64, 128]
sum(k * b for k, b in zip(knapsack, r))
u ==== 174
r === 78
ciphertext = [251, 210, 197, 79, 48, 120, 179, 12, 197, 143, 107, 230, 230, 230, 89, 89, 107, 217, 217, 217, 80, 242, 158, 179, 25, 55, 210, 80, 88, 230, 107, 80, 43, 199, 43, 80, 30, 230, 251, 80, 125, 55, 25, 80, 48, 25, 204, 204, 204, 204, 215]
From this, we can deduce that the character ‘u’ (the first character of the flag) produced a c_value of 174, corresponding to the first ciphertext value of 251. Similarly, ‘r’ produced a c_value of 78, which corresponds to a ciphertext value of 210.
In the iteration below, I calculated the value of n that, when multiplied by the c_value for ‘u’ and ‘r’, yields their respective ciphertext values of 251 and 210.
for n in range(-1000, 1000):
if ((174 * n) % 257 == 251) and ((78 * n) % 257 == 210):
print(i)
Turns out , there are a couple of possible values of n, i chose 62
Reversing ciphertext (Finding plaintext )
Now that we know n, k (knapsack), and m, the only unknown variable left is the plaintext.
The next question to address, then, is: which ASCII character (in the range 32 to 127) would yield the given ciphertext using the above algorithm with all variables accounted for?
m = 257
ola = ''
n = 64
ciphertext = [251, 210, 197, 79, 48, 120, 179, 12, 197, 143, 107, 230, 230, 230, 89, 89, 107, 217, 217, 217, 80, 242, 158, 179, 25, 55, 210, 80, 88, 230, 107, 80, 43, 199, 43, 80, 30, 230, 251, 80, 125, 55, 25, 80, 48, 25, 204, 204, 204, 204, 215]
for j in ciphertext:
for i in range(32, 127):
chunk = convert_to_bits(chr(i))
c_value = sum(k * b for k, b in zip(knapsack, chunk))
if ((c_value * n) % m) == j:
ola+=(chr(i))
print(ola)
============================================================
Tr3ppl3 Stuffs
#!/usr/bin/env python3
from Crypto.Util.number import getPrime, bytes_to_long
with open('flag.txt', 'rb') as f:
flag = f.read()
p = getPrime(1024)
q = getPrime(1024)
r = getPrime(1024)
n1 = p * q
n2 = p * r
n3 = q * r
moduli = [n1, n2, n3]
e = 65537
c = bytes_to_long(flag)
for n in moduli:
c = pow(c, e, n)
print("Encrypted message:", c)
with open('public-key.txt', 'w') as f:
f.write(f'n1: {n1}\n')
f.write(f'n2: {n2}\n')
f.write(f'n3: {n3}\n')
f.write(f'e: {e}\n')
f.write(f'c: {c}\n')
n1= 13867714277838326859434141360807126266988181051937691542720478418900742622487476887000656853897982839471460140185684018914440756440556729087389072578013467286815328553713462055920345115855791765238366372179412680116075169975393328050865875339384668108111346738113960352417722977540340666758452044804022538440159211522070499214448440719690800137276711042521317382781533688637617761177287887907758146318457772914415682758679918032976640744321033974300959199696464501906455225891794560720844314968771280659472377943231331641875340677526653689250244217219907971921829288080314290063506963456144212483509162974366807921979
n2= 17927735574177320194848318418235001068997271079087971789634703982572674848578451538875202615588580716164655574536384549093649682917017825684657701503860986896187290471258481237400622176271362761168908135788945003341162330346916547198330806215741808128176090032632472660890590964751813395114783904537959063721183330663548506084027893121866027955931624962212334321689943348627498071027965403990280434233875995691837345133010841620725043983468838002901540254921373846246649579342996291922616728645385101976043981088285904718975629169143452456299479123325380939400104364355380586108227679518185723459474280104976741611251
n3= 22028871217815368590508935678901115805680414747406956084626690162228030261041925736297743271590455693409721333028841498368646841160349146338416150860715525872894476206762924468484783297112829812273714272505690386899539197391794335997773084843803810816300680240126661406634232555713608389689386797404392103317004971701232793270476882695037289851795372610834374445176629233245247506250070493438866110603354631599199020064180967657565037951617865082532325342883190214781057565516003407960037770643505735135704106444100281795297535233604930832284642745486553954322079734200972056930865484862720843375357617469824569196081
e= 65537
c= 159820800271683909955969199347809226263066780945008228617057381390715205653829404005020320683713943084709437889168457577565120939166875780657172536581844989368575807012158001081708881433905875787759318316021448663643497050035256788497368894658783098756561669330930359021635865629027555058197121059654759784853611495340486636825839396146543378317360868257008413313377586650632786527739979553534878000134654372973555254046265162085773356884735448877440528007227901771068342100423775888354694745898639423664799608860305153083747715511704321793245331609809017276522382587901657911130313216753983466299557871896980699 * 59 * 41 * 23 * 2
RSA ?
This other challenge, however, follows the basic RSA encryption equation: the plaintext raised to the power of e, modulo the product of two prime numbers (p and q).
C = M**e mod N.
Yh… our entire internet rest on this simple math lol, the security of this lies in the dificulty of how hard it will be to factorize multiplication of two prime numbers without bruteforce
To decrypt , we need to know the value of the two prime numbers that took path in the encryption (p, q), deduct one from each and multiply them (p-1)(q-1), then take inverse of e mod this multiplication, let’s call the result d
To retrieve the plaintext, we then have to multiply the ciphertext with d (computed above) modulus of n (p*q)
Glad that is out of the way, you can read more about it here …. https://people.csail.mit.edu/rivest/Rsapaper.pdf
Remember the security of this relies on the value of p and q.
back to the flag encyption above, we can see p , q and r were generated with getPrime(1024), 1024 bytes is definately not bruteforceable , so gettig the value of p, r and q that way is out of question
However, in there genius implementation they encrypted the plaintext thrice , using 3 public keys and provided us with it
n1 = p * q
n2 = p * r
n3 = q * r
Why is this such a bad idea ? : GCD (Greatest Common Divisor ) also known as highest common factor
The greatest common divisor (GCD) is the largest integer that divides two variables. For any two distinct prime numbers, the GCD is 1. However, in a situation like the one above with n1 = pq and n2 = pr, these two numbers share a GCD of p, as they are both divisible only by p and they are all prime
To retrive variable p, q and r . These are things we should note ….
pq and pr share a common divisor of p
pr and qr share a common divisor of r
qr and pq share a common divisor of q
There are two common algorithms used for retriving GCD, euclidean algorithm (simpler but slower) and Lehmer’s GCD algorithm (faster for large numbers ) check implementation here : https://gist.github.com/cmpute/baa545f0c2b6be8b628e9ded3c19f6c1
def extended_gcd(a, b):
"""Return gcd(a, b), and x, y such that a*x + b*y = gcd(a, b)"""
if a == 0:
return b, 0, 1
gcd, x1, y1 = extended_gcd(b % a, a)
x = y1 - (b // a) * x1
y = x1
return gcd, x, y
p == extended_gcd(n1, n2)
After retrieving the value of p, q, and r , we can proceed with the decryption,
Remember the ciphertext was first encrypted with n1 followed by n2 then n3 , to decrypt we have to reverse the order. First decrypt from n3 followed by n2 then n1.
RSA decryption equation
d = e**−1 mod (p − 1)(q − 1).
Decoding: m = M**d mod N.
from sympy import mod_inverse
def decrypt(p, q, M):
N = p * q
phi_N = (p - 1) * (q - 1)
# Step 3: Calculate d, the modular inverse of e modulo phi(N)
d = mod_inverse(e, phi_N)
# Step 4: Decode M by calculating m = M^d mod N
m = pow(M, d, N)
return m