DESCRIPTION: Qubit Enterprises is a new company touting it's propriety method of qubit stabilization.They expect to be able to build a quantum computer that can factor a RSA-1024 number in the next 10 years.As a promotion they are giving out "time capsules" which contain a message for the future encrypted by 1024 bit RSA.They might be great engineers, but they certainly aren't cryptographers, can you find a way to read themessage without having to wait for their futuristic machine?
https://app.hackthebox.com/challenges/365
Baby Time Capsule is cryptography challenge. we are given with python source code server.py file.
Click to see source code :diamond_shape_with_a_dot_inside:
from Crypto.Util.number import bytes_to_long, getPrimeimport socketserverimport jsonFLAG =b'HTB{--REDACTED--}'classTimeCapsule():def__init__(self,msg): self.msg = msg self.bit_size =1024 self.e =5def_get_new_pubkey(self):whileTrue: p =getPrime(self.bit_size //2) q =getPrime(self.bit_size //2) n = p * q phi = (p -1) * (q -1)try:pow(self.e, -1, phi)breakexceptValueError:passreturn n, self.edefget_new_time_capsule(self): n, e = self._get_new_pubkey() m =bytes_to_long(self.msg) m =pow(m, e, n)return{"time_capsule":f"{m:X}","pubkey": [f"{n:X}",f"{e:X}"]}defchallenge(req): time_capsule =TimeCapsule(FLAG)whileTrue:try: req.sendall(b'Welcome to Qubit Enterprises. Would you like your own time capsule? (Y/n) ' ) msg = req.recv(4096).decode().strip().upper()if msg =='Y'or msg =='YES': capsule = time_capsule.get_new_time_capsule() req.sendall(json.dumps(capsule).encode() +b'\n')elif msg =='N'or msg =="NO": req.sendall(b'Thank you, take care\n')breakelse: req.sendall(b'I\'m sorry I don\'t understand\n')except:# Socket closed, bailreturnclassMyTCPRequestHandler(socketserver.BaseRequestHandler):defhandle(self): req = self.requestchallenge(req)classThreadingTCPServer(socketserver.ThreadingMixIn,socketserver.TCPServer):passdefmain(): socketserver.TCPServer.allow_reuse_address =True server =ThreadingTCPServer(("0.0.0.0", 1337), MyTCPRequestHandler) server.serve_forever()if__name__=='__main__':main()
To solve this we need knowledge of the Chinese remainder theorem.
m=message, e=5, n=public key, c=cipher text
me mod n = c
let's take x = me
x mod n = c
here x module n is remainder c, so we can say that x anc c are congruent modulo.
x ≡ c (mod n)
Here server encrypt same message with different public keys.
x ≡ c1 (mod n1)
x ≡ c2 (mod n2)
x ≡ c3 (mod n3)
The Chinese Remainder Theorem (CRT) is used to solve a set of different congruent equations with one variable but different moduli which are relatively prime.
To find x:
x = (c1 × N1 × N1-1 + c2 × N2 × N2-1 + c3 × N3 × N3-1) mod N
here, N = n1 × n2 × n3
N1 = N / n1
N2 = N / n2
N3 = N / n3
N1 × N1-1 = 1 mod n1
N2 × N2-1 = 1 mod n2
N3 × N3-1 = 1 mod n3
we can use extended euclidean algorithm to find N1-1.
I used python library to perform CRT.
Python code:
Click to see python code :diamond_shape_with_a_dot_inside:
import jsonfrom Crypto.Util.number import long_to_bytesfrom pwn import*from sympy.ntheory.modular import crtfrom sympy.simplify.simplify import nthrootconn =remote('209.97.185.157', 32141)rem =list()num =list()for i inrange(3): conn.sendline(b'Y') a = conn.recvline() r = json.loads(a[74:-1].decode()) m = r['time_capsule'] n = r['pubkey'][0] e =5 m =int(m, 16) n =int(n, 16) rem.append(m) num.append(n)x =crt(num, rem, check=True)# print(f'x = {x[0]}')flag =nthroot(x[0], 5)print(flag)print(long_to_bytes(flag))conn.sendline(b'N')conn.recvline()conn.close()
Click to see output :diamond_shape_with_a_dot_inside:
[x] Opening connection to 209.97.185.157 on port 32141[x] Opening connection to 209.97.185.157 on port 32141: Trying 209.97.185.157[+] Opening connection to 209.97.185.157 on port 32141: Done3133512701921564926666059129802238375015291423590355094862405004229914481893581069974415008616334994674940586670768933862016098685b'HTB{t3h_FuTUr3_15_bR1ghT_1_H0p3_y0uR3_W34r1nG_5h4d35!}'[*] Closed connection to 209.97.185.157 port 32141Processfinishedwithexitcode0