Ursa Minor
4 minutos de lectura
Se nos proporciona el siguiente código y una instancia a la que conectarnos:
#!/usr/local/bin/python
#
# Polymero
#
# Imports
from Crypto.Util.number import isPrime, getPrime, inverse
import hashlib, time, os
# Local import
FLAG = os.environ.get('FLAG').encode()
class URSA:
# Upgraded RSA (faster and with cheap key cycling)
def __init__(self, pbit, lbit):
p, q = self.prime_gen(pbit, lbit)
self.public = {'n': p * q, 'e': 0x10001}
self.private = {'p': p, 'q': q, 'f': (p - 1)*(q - 1), 'd': inverse(self.public['e'], (p - 1)*(q - 1))}
def prime_gen(self, pbit, lbit):
# Smooth primes are FAST primes ~ !
while True:
qlst = [getPrime(lbit) for _ in range(pbit // lbit)]
if len(qlst) - len(set(qlst)) <= 1:
continue
q = 1
for ql in qlst:
q *= ql
Q = 2 * q + 1
if isPrime(Q):
break
while True:
plst = [getPrime(lbit) for _ in range(pbit // lbit)]
if len(plst) - len(set(plst)) <= 1:
continue
p = 1
for pl in plst:
p *= pl
P = 2 * p + 1
if isPrime(P):
break
return P, Q
def update_key(self):
# Prime generation is expensive, so we'll just update d and e instead ^w^
self.private['d'] ^= int.from_bytes(hashlib.sha512((str(self.private['d']) + str(time.time())).encode()).digest(), 'big')
self.private['d'] %= self.private['f']
self.public['e'] = inverse(self.private['d'], self.private['f'])
def encrypt(self, m_int):
c_lst = []
while m_int:
c_lst += [pow(m_int, self.public['e'], self.public['n'])]
m_int //= self.public['n']
return c_lst
def decrypt(self, c_int):
m_lst = []
while c_int:
m_lst += [pow(c_int, self.private['d'], self.public['n'])]
c_int //= self.public['n']
return m_lst
# Challenge setup
print("""|
| ~ Welcome to URSA decryption services
| Press enter to start key generation...""")
input("|")
print("""|
| Please hold on while we generate your primes...
|\n|""")
oracle = URSA(256, 12)
print("| ~ You are connected to an URSA-256-12 service, public key ::")
print("| id = {}".format(hashlib.sha256(str(oracle.public['n']).encode()).hexdigest()))
print("| e = {}".format(oracle.public['e']))
print("|\n| ~ Here is a free flag sample, enjoy ::")
for i in oracle.encrypt(int.from_bytes(FLAG, 'big')):
print("| {}".format(i))
MENU = """|
| ~ Menu (key updated after {} requests)::
| [E]ncrypt
| [D]ecrypt
| [U]pdate key
| [Q]uit
|"""
# Server loop
CYCLE = 0
while True:
try:
if CYCLE % 4:
print(MENU.format(4 - CYCLE))
choice = input("| > ")
else:
choice = 'u'
if choice.lower() == 'e':
msg = int(input("|\n| > (int) "))
print("|\n| ~ Encryption ::")
for i in oracle.encrypt(msg):
print("| {}".format(i))
elif choice.lower() == 'd':
cip = int(input("|\n| > (int) "))
print("|\n| ~ Decryption ::")
for i in oracle.decrypt(cip):
print("| {}".format(i))
elif choice.lower() == 'u':
oracle.update_key()
print("|\n| ~ Key updated succesfully ::")
print("| id = {}".format(hashlib.sha256(str(oracle.public['n']).encode()).hexdigest()))
print("| e = {}".format(oracle.public['e']))
CYCLE = 0
elif choice.lower() == 'q':
print("|\n| ~ Closing services...\n|")
break
else:
print("|\n| ~ ERROR - Unknown command")
CYCLE += 1
except KeyboardInterrupt:
print("\n| ~ Closing services...\n|")
break
except:
print("|\n| ~ Please do NOT abuse our services.\n|")
El servidor genera dos números primos lisos (smooth primes) $p$ y $q$ (que significa que $p - 1$ y $q - 1$ se pueden factorizar fácilmente en factores pequeños). Sin embargo, no nos dan $n = p \cdot q$, sino el hash SHA256 de $n$. Por otro lado, $e = 65537$, como habitualmente. La flag se cifra con RSA según los parámetros generados.
Después, nos dan la oportunidad de cifrar mensajes, descifrar mensajes o actualizar la clave.
Me resultó extraña la función encrypt:
def encrypt(self, m_int):
c_lst = []
while m_int:
c_lst += [pow(m_int, self.public['e'], self.public['n'])]
m_int //= self.public['n']
return c_lst
En primer lugar, el mensaje tiene que ser enviado en formato decimal. Además, si el número es mayor que $n$, la función realizará más de una iteración del bucle while. Entonces, podemos obtener $n$ mediante Búsqueda Binaria:
Introducimos un número $x$. Si $x \geq n$, el servidor devolverá más de un texto cifrado; y si $x < n$, el servidor responderá con un único texto cifrado. Por tanto, podemos poner dos límites (por ejemplo, $2^{256}$ y $2^{512}$) y dividir el intervalo con Búsqueda Binaria hasta encontrar $n$:
a, b = 2 ** 256, 2 ** 512
while a + 1 != b:
test_n = (a + b) // 2
if len(encrypt(r, test_n)) > 1:
b = test_n
else:
a = test_n
n = a if a % 2 else b
print(n, a, b)
assert hashlib.sha256(str(n).encode()).hexdigest() == n_id_hex
Para verificar que es correcto, podemos comprobar que el hash SHA256 de $n$ coincide con el que envió el servidor al principio.
Una vez que tenemos $n$, podemos usar el algoritmo p - 1 de Pollard para factorizarlo y descifrar la flag como en la mayoría de retos de RSA:
p, q = pollard_p_1(n)
assert n == p * q
phi_n = (p - 1) * (q - 1)
d = pow(e, -1, phi_n)
m = pow(flag_enc, d, n)
print(bytes.fromhex(hex(m)[2:]))
r.close()
Y así conseguimos la flag:
$ python3 solve.py blackhat2-09afaf950bafc7bc0c7c3d69fcaeb7df-0.chals.bh.ctf.sa
[+] Opening connection to blackhat2-09afaf950bafc7bc0c7c3d69fcaeb7df-0.chals.bh.ctf.sa on port 443: Done
b'BlackHatMEA{96:19:07a094190d0777d995d4bb9f504a494631855c36}'
[*] Closed connection to blackhat2-09afaf950bafc7bc0c7c3d69fcaeb7df-0.chals.bh.ctf.sa port 443
El script completo se puede encontrar aquí: solve.py.