Hello everyone:) Omnia is writing you this writeup for the cryptography challenge she solved during the BlackHat MEA 2024 named Trypanophobia. This is to prove that she isn’t so afraid of needles:)
Exploration
First, let’s look at the source code!
#!/usr/bin/env python3
# Native imports
import os, json, hashlib
# Non-native imports
from Crypto.Util.number import getPrime, isPrime, inverse, GCD # pip install pycryptodome
# Flag import
FLAG = os.environ.get('DYN_FLAG')
if isinstance(FLAG, str):
FLAG = FLAG.encode()
# Functions & Classes
class RSAKey:
def __init__(self):
self.public = None
self.private = None
@staticmethod
def new():
p = getPrime(1024)
while True:
q = getPrime(1024)
f = (p - 1) * (q - 1)
if GCD(f, 0x10001) == 1:
break
key = RSAKey()
key.public = {
'e' : 0x10001
}
key.private = {
'p' : [p, q]
}
key.update()
return key
def update(self):
self.public['n'] = 1
self.private['f'] = 1
for p in self.private['p']:
self.public['n'] *= p
self.private['f'] *= (p - 1)
self.private['d'] = inverse(self.public['e'], self.private['f'])
def pad(self, x):
y = int(hashlib.sha256(str(set(self.private['p'])).encode()).hexdigest(), 16)
while x < self.public['n']:
x *= y
x //= y
return x
def encrypt(self, x):
if 0 < x < self.public['n']:
return pow(self.pad(x), self.public['e'], self.public['n'])
else:
return 0
# Challenge set-up
HDR = """|
| ┏┳┓ ┓ ┓ •
| ┃ ┏┓┓┏┏┓┏┓┏┓┏┓┏┓┣┓┏┓┣┓┓┏┓
| ┻ ┛ ┗┫┣┛┗┻┛┗┗┛┣┛┛┗┗┛┗┛┗┗┻
| ┛┛ ┛"""
print(HDR)
ourKey = RSAKey.new()
# Server loop
TUI = "|\n| Menu:\n| [A]dd a key\n| [E]ncrypt flag\n| [Q]uit\n|"
while True:
try:
print(TUI)
choice = input("| > ").lower()
if choice == 'q':
print('|\n| [~] Goodbye ~ !\n|')
break
elif choice == 'a':
uin = json.loads(input("| > (JSON) "))
assert uin.keys() == {'p', 'q'}
if all([
isPrime(uin['p']), isPrime(uin['q']),
len(bin(uin['p'])) == 1024 + 2,
len(bin(uin['q'])) == 1024 + 2
]):
ourKey.private['p'] += [uin['p'], uin['q']]
ourKey.update()
else:
print('| [!] Invalid primes.')
elif choice == 'e':
enc = ourKey.encrypt(int.from_bytes(FLAG, 'big'))
print('| Flag = 0x{:x}'.format(enc))
else:
print('| [!] Invalid choice.')
except KeyboardInterrupt:
print('\n|\n| [~] Goodbye ~ !\n|')
break
except Exception as e:
print('| [!] ERROR :: {}'.format(e))It’s quite loooong~!
Let’s break it down~(I will use comments when possible:)
We will start with the RSAKey class.
class RSAKey:
def __init__(self):
self.public = None
self.private = None
@staticmethod
def new(): # Pretty standard RSA key generation
p = getPrime(1024)
while True:
q = getPrime(1024)
f = (p - 1) * (q - 1)
if GCD(f, 0x10001) == 1:
break
key = RSAKey()
key.public = {
'e' : 0x10001
}
key.private = { # This can be confusing at times since p refers to both p and q
'p' : [p, q]
}
key.update()
return key
def update(self): #Standard too"~"
self.public['n'] = 1
self.private['f'] = 1
for p in self.private['p']:
self.public['n'] *= p
self.private['f'] *= (p - 1)
self.private['d'] = inverse(self.public['e'], self.private['f'])
def pad(self, x): # Now this is a weird padding, Will discuss it later
y = int(hashlib.sha256(str(set(self.private['p'])).encode()).hexdigest(), 16)
while x < self.public['n']:
x *= y
x //= y
return x
def encrypt(self, x):# Standard!
if 0 < x < self.public['n']:
return pow(self.pad(x), self.public['e'], self.public['n'])
else:
return 0We see that the RSAKey class is, surprise surprise, a class for generating RSA keys.It uses the standard well-known Textbook RSA with solid prime generation and lengths. However, We have a custom padding here, Let’s Note that.
Let’s continue with the rest of the code~
# Challenge set-up
HDR = """|
| ┏┳┓ ┓ ┓ •
| ┃ ┏┓┓┏┏┓┏┓┏┓┏┓┏┓┣┓┏┓┣┓┓┏┓
| ┻ ┛ ┗┫┣┛┗┻┛┗┗┛┣┛┛┗┗┛┗┛┗┗┻
| ┛┛ ┛"""
print(HDR)
ourKey = RSAKey.new() # W start by creating a key
# Server loop
TUI = "|\n| Menu:\n| [A]dd a key\n| [E]ncrypt flag\n| [Q]uit\n|"
while True:
try:
print(TUI)
choice = input("| > ").lower()
if choice == 'q':
print('|\n| [~] Goodbye ~ !\n|') # Q is for quitters, not us:)
break
elif choice == 'a':
uin = json.loads(input("| > (JSON) "))
assert uin.keys() == {'p', 'q'} # WOW, we can add our own key, here we can add p and q
if all([
isPrime(uin['p']), isPrime(uin['q']), # It has to be a prime
len(bin(uin['p'])) == 1024 + 2,# it has to be 1024-bit, so no small primes
len(bin(uin['q'])) == 1024 + 2
]):
ourKey.private['p'] += [uin['p'], uin['q']] # if we passed all checks, we add our primes to the list of primes
ourKey.update() # updates the keys
else:
print('| [!] Invalid primes.')
elif choice == 'e':# choosing e will let us get the encrypted flag, we can also get it after adding keys
enc = ourKey.encrypt(int.from_bytes(FLAG, 'big'))
print('| Flag = 0x{:x}'.format(enc))
else:
print('| [!] Invalid choice.')
except KeyboardInterrupt:
print('\n|\n| [~] Goodbye ~ !\n|')
break
except Exception as e:
print('| [!] ERROR :: {}'.format(e))So0o0:, we have an RSA system that allows us to add our own key and it encrypts the flag. How easy can these be?! Welp, not that easy:(
Observations
We don’t have any Ns
W don’t have the value of N since it will make the challenge way easier to solve and this is Polymoro easy:)
We can add any pair of 1024-bit primes
If we choose option “a” it will ask us for a json of p and q, it will then add them to the list of primes. Then, the update method is called and these new primes will be multiplied by with the original primes to form a 4-primes modulus.
The padding function Has a fatal weakness!
If we looked closely at the padding function
def pad(self, x):
y = int(hashlib.sha256(str(set(self.private['p'])).encode()).hexdigest(), 16)
while x < self.public['n']:
x *= y
x //= y
return xHere, we see that it first calculate a hash from the “set” of private keys. A set? not a list? huh?
Now Omnia can tell! Set are infamous for not allowing duplicates! this is our clue! Imma add it to the note~!
Did you get the trick? DW, Omnia will tell you~ since the padding function is dependent on the list of primes, and since it uses sets that don’t allow duplicates ~~ We can add the same pair of primes twice! Doing so, the padding function will ignore our second addition of the prime and the padding will be the same !
Adding primes allows us to decrypt
Omnia found this fun mathematical fact. Since we know part of the primes of n (Since, Well, We made them and added them) We can decrypt the encrypted flag mod our primes!
Forming our theory
Now, following our observations, We can exploit the challenge like this:
- We generate two primes p and q ( We can generate 1 prime but Omnia hates the phi formula for double primes:)
- Next, we send the server our two primes p and q
- We ask the server to encrypt the flag with the new keys inside the original modulus obtaining C1
- Then we add the same two primes p and q to the server
- Then we ask it again to encrypt the flag with the new primes, Obtaining C2
- Why did we do that? to make use of observation 3- now we have two encrypted flags with the same padding
- Now we can make use of observation 4 and decrypt the flag mod the product of our primes
our_d = pow(e, -1, (p-1)*(q-1))
m1 = pow(c1, d, p*q)
m2 = pow(c2, d, p*q)Pretty cool so far! We got the decrypted flag 0o0? No:( cuz the flag is padded:( and we don’t know the pad because it depends on the private key list that contains the the original p and q that we don’t know yet:(
Right now we have the padded flag in this formula
m1 = x * y**k1 mod p * q
m2 = x *y**k1 mod p * qK1 and K2 are the times the pad has been added ( look at the loop in the padding function )
Welp, we need to figure them out. Omnia noticed that the pad is a sha256 hash, meaning that it is a 256-bit number! now let Omnia do some calculations for you to show you something interesting~!
# y is a 256 bit string
# Omnia will assume that the flag is about 300 bits
# Recall how the pad is calculated
def pad(self, x): # Now this is a weird padding, Will discuss it later
y = int(hashlib.sha256(str(set(self.private['p'])).encode()).hexdigest(), 16)
while x < self.public['n']:
x *= y
x //= y
return x
#Here, we see that the flag x is multiplied until it barely exceeds n, our goal here is to calculate how many time y is added
# let's see after every addition of primes
n = _p * _q * p * q
n_size = 1024 + 1024 + 1024 + 1024 = 4096
c = x * y **k mod n # y is multiplied k times
y_size = 256
x_assumed_size = 300
k1 = n/ x_multi_y_size = 4096/256 = 16
# Since the last y multiplication is undone and the flag size is assumed to be about ~ 300 bit
k1 = 16 - 1 - 1 = 14
# We can do the same after the 2nd addition
n = _p * _q * p**2 * q**2
n_size = 1024 * 6 = 6144
k2 + 2 = 6144/256 = 24
k2 = 22
Niceoo~!
Now it’s a two equations in two variables! mathy mathy time!!
m1 = x * y**14 mod p * q
m2 = x * y**22 mod p * q
m2 * m1**(-1) = y**(22-14) mod p * q
m2 * m1**(-1) = y**8 mod p * q
y = Mod(m2/m1,p*q).nth_root(8) # this is modular root, not integers, it is available in sagemath
# substitute y in the first equation and solve for x
x = m1 * y **(-14) mod p * q
print(long_to_bytes(x))
Oh! the flag!!!
Since Omnia’s mind is so messy, she decided to write a complete solve script for this challenge
Solve script
import json
from pwn import remote
from sage.all import Mod
from Crypto.Util.number import getPrime, long_to_bytes
p = getPrime(1024)
q = getPrime(1024)
e = 65537
io = remote("server",port) # add server and port
io.sendlineafter(b'> ', b'a')
io.sendlineafter(b'> (JSON) ', json.dumps({'p': p, 'q': p}).encode())
io.sendlineafter(b'> ', b'e')
io.recvuntil(b'Flag = ')
c1 = int(io.recvline().decode(), 16)
d = pow(e, -1, (p - 1) * (q - 1))
m1 = pow(c1, d, p * q)
io.sendlineafter(b'> ', b'a')
io.sendlineafter(b'> (JSON) ', json.dumps({'p': p, 'q': p}).encode())
io.sendlineafter(b'> ', b'e')
io.recvuntil(b'Flag = ')
c2 = int(io.recvline().decode(), 16)
io.close()
m2 = pow(c2, d, p * q)
y = Mod(m2/m1,p*q).nth_root(22-14)
flag = long_to_bytes(int( Mod(m1,p*q)/y**14))
print(flag)Toldya, Omnia is not afraid of needles!
