Fast Carmichael - HTB crypto challenge
Summary
Figure out what server.py is doing --> discover that it uses the miller-rabin primality test --> exploit said test with a carmichael number --> flag
This challenge comes from HacktheBox and is rated as very easy:
Taking a look at server.py we can see some rather complex math being done to our input:
from secret import FLAG
from Crypto.Util.number import isPrime
import socketserver
import signal
class Handler(socketserver.BaseRequestHandler):
def handle(self):
signal.alarm(0)
main(self.request)
class ReusableTCPServer(socketserver.ForkingMixIn, socketserver.TCPServer):
pass
def sendMessage(s, msg):
s.send(msg.encode())
def receiveMessage(s, msg):
sendMessage(s, msg)
return s.recv(4096).decode().strip()
def generate_basis(n):
basis = [True] * n
for i in range(3, int(n**0.5) + 1, 2):
if basis[i]:
basis[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
return [2] + [i for i in range(3, n, 2) if basis[i]]
def millerRabin(n, b):
basis = generate_basis(300)
if n == 2 or n == 3:
return True
if n % 2 == 0:
return False
r, s = 0, n - 1
while s % 2 == 0:
r += 1
s //= 2
for b in basis:
x = pow(b, s, n)
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
def _isPrime(p):
if p < 1:
return False
if not millerRabin(p, 300):
return False
return True
def main(s):
p = receiveMessage(s, "Give p: ")
try:
p = int(p)
except:
sendMessage(s, "Error!")
if _isPrime(p) and not isPrime(p):
sendMessage(s, FLAG)
else:
sendMessage(s, "Conditions not satisfied!")
if __name__ == '__main__':
socketserver.TCPServer.allow_reuse_address = True
server = ReusableTCPServer(("0.0.0.0", 1337), Handler)
server.serve_forever()
For starters, i’d rather not try and decode this cryptic source by merely looking at it. No, for this we need a more heuristic approach. Taking a look at the function names we can spot millerRabin, and the program also asks us to enter p, which is a common name used for an expression when working with modular arithmetic.
Solution
So as one would, I googled what this millerRabin could be, and as it turns out, it’s a primality test. It basically checks if numbers are prime, but the wikipedia article on it notes something interesting:
No composite number is a strong pseudoprime to all bases at the same time (contrary to the Fermat primality test for which Fermat pseudoprimes to all bases exist: the Carmichael numbers). However no simple way of finding a witness is known. A naïve solution is to try all possible bases, which yields an inefficient deterministic algorithm.
Here a light bulb went off when seeing carmichael, so i googled that next and found another wikipedia article:
Arnault gives a 397-digit Carmichael number N that is a strong pseudoprime to all prime bases less than 307:
N = p ⋅ ( 313 ( p − 1 ) + 1 ) ⋅ ( 353 ( p − 1 ) + 1 )
where
p = 29674495668685510550154174642905332730771991799853043350995075531276838753171770199594238596428121188033664754218345562493168782883
is a 131-digit prime. p is the smallest prime factor of N , so this Carmichael number is also a (not necessarily strong) pseudoprime to all bases less than p .
So far, what im getting from this is that we can bypass the primality test with a ridiculously high number derived from this formula. So lets try it:
from pwn import remote, sys, context, log, sleep
context.log_level = "info"
if len(sys.argv) == 1:
print("Usage: solve.py HOST:PORT")
exit(-1)
host, port = sys.argv[1].split(":")
c = remote(host, port)
c.recv()
p = 29674495668685510550154174642905332730771991799853043350995075531276838753171770199594238596428121188033664754218345562493168782883
N = str((p * (313 * (p - 1) + 1) * (353 * (p - 1) + 1))).encode()
log.info(f"Sending payload(??): {N}")
c.sendline(N)
sleep(1)
flag = c.recv().decode()
log.success(f"Flag returned: {flag}")
And it worked:
