You are walking with your friends in search of sweets and discover a mansion in the distance. All your friends are too scared to approach the building, so you go on alone. As you walk down the street, you see expensive cars and math papers all over the yard. Finally, you reach the door. The doorbell says “Michael Fastcar”. You recognise the name immediately because it was on the news the day before. Apparently, Fastcar is a famous math professor who wants to get everything done as quickly as possible. He has even developed his own method to quickly check if a number is a prime. The only way to get candy from him is to pass his challenge.
Files Provided
server.py
Challenge Script
1from secret import FLAG
2from Crypto.Util.number import isPrime
3import socketserver
4import signal
5
6class Handler(socketserver.BaseRequestHandler):
7
8 def handle(self):
9 signal.alarm(0)
10 main(self.request)
11
12class ReusableTCPServer(socketserver.ForkingMixIn, socketserver.TCPServer):
13 pass
14
15def sendMessage(s, msg):
16 s.send(msg.encode())
17
18def receiveMessage(s, msg):
19 sendMessage(s, msg)
20 return s.recv(4096).decode().strip()
21
22def generate_basis(n):
23 basis = [True] * n
24
25 for i in range(3, int(n**0.5) + 1, 2):
26 if basis[i]:
27 basis[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
28 return [2] + [i for i in range(3, n, 2) if basis[i]]
29
30def millerRabin(n, b):
31 basis = generate_basis(300)
32 if n == 2 or n == 3:
33 return True
34
35 if n % 2 == 0:
36 return False
37
38 r, s = 0, n - 1
39 while s % 2 == 0:
40 r += 1
41 s //= 2
42 for b in basis:
43 x = pow(b, s, n)
44 if x == 1 or x == n - 1:
45 continue
46 for _ in range(r - 1):
47 x = pow(x, 2, n)
48 if x == n - 1:
49 break
50 else:
51 return False
52 return True
53
54def _isPrime(p):
55 if p < 1:
56 return False
57 if not millerRabin(p, 300):
58 return False
59
60 return True
61
62def main(s):
63 p = receiveMessage(s, "Give p: ")
64
65 try:
66 p = int(p)
67 except:
68 sendMessage(s, "Error!")
69
70 if _isPrime(p) and not isPrime(p):
71 sendMessage(s, FLAG)
72 else:
73 sendMessage(s, "Conditions not satisfied!")
74
75if __name__ = '__main__':
76 socketserver.TCPServer.allow_reuse_address = True
77 server = ReusableTCPServer(("0.0.0.0", 1337), Handler)
78 server.serve_forever()
The script we’re given looks rather complicated, but it boils down to a pretty simple condition that we have to satisfy before we’re given the flag.
Prime and Not Prime?
If we look at the main function of the script, we can see the following lines of code:
70if _isPrime(p) and not isPrime(p):
71 sendMessage(s, FLAG)
72else:
73 sendMessage(s, "Conditions not satisfied!")
At first glance, this doesn’t really make a lot of sense. How can a number simultaneously be a prime number, and not a prime number? Well that depends on how we’re testing the primality of that number.
We can see that there are two different functions that are being used here:
_isPrime()isPrime()
The isPrime() function is being imported from Crypto.Util.number, whereas the _isPrime() function is being defined within the server.py script itself:
54def _isPrime(p):
55 if p < 1:
56 return False
57 if not millerRabin(p, 300):
58 return False
59
60 return True
It looks like the _isPrime() function is using the Miller-Rabin Primality Test to determine if the number passed in is a prime.
So, putting all of this together, we can see that we need to supply a number that will be determined to be a prime by the Miller-Rabin test, and determined to be a non-prime by the python Crypto library (also called `pycryptodome).
Miller-Rabin Test
So what is the Miller-Rabin test? The Miller-Rabin test is a probabilistic primality test that determines whether or not a number is likely to be prime. It’s essentially an automated educated guess that gets more accurate as the time you spend running the test goes up. Because the test is probabilistic, there is a chance that it will produce false positives, stating that a given number is prime when in fact it is not. That is the result that we want to produce here.
Test Operation
To test the primality of a number $n$, we record the value of $n-1$ as $2^sd$, where $s$ is a positive integer and $d$ is a positive odd integer. We then choose a base number that is co-prime to $n$. A number is considered co-prime to another number when they share no common factors with each other except $1$.
We then check if either of the following congruence relations hold:
$$a^d \equiv 1 \pmod n$$
$$a^{2^rd} \equiv -1 \pmod n \ \ \ 0 \leq r < s$$
If either of these relations does hold, we pick a new base a repeat the test. The more rounds of testing we perform, we more confident we can be that $n$ is a prime. So how do we mess with this? Enter Carmichael numbers.
Carmichael Numbers
Carmichael numbers are composite numbers (i.e. non-prime) that satisfy the following congruence relation:
$$b^n \equiv b \pmod n$$
We can rewrite the relation like so:
$$b^{n-1} \equiv 1 \pmod n$$
Notice that this looks very similar to one of the relations used by the Miller-Rabin test:
$$a^d \equiv 1 \pmod n$$
Because Carmichael numbers satisfy the same congruence relation that is used by the Miller-Rabin test, we can likely use one of them to fool it and get our flag. On the Carmichael number wikipedia page, there is a section that details a number that is determined as a “strong pseudoprime to all prime bases less than 307”. Take a look at the millerRabin function in our server.py and see that it is using all bases less than 300:
30def millerRabin(n, b):
31 basis = generate_basis(300)
Looks like this number is going to work, but what is its actual value?
Big Math
If we read the wikipedia page a little, we get given a formula for calculating this magic number:
$$ N=p*(313*(p-1)+1)*(353*(p-1)+1) $$
We also get given the value of $p$:
$$p=29674495668685510550154174642905332730771991799853043350995075531276838753171770199594238596428121188033664754218345562493168782883$$
Obviously this number is going to be huge, so we should use a script to calculate it.
Solution
We can use this python script to calculate the value of our magic number.
1p=29674495668685510550154174642905332730771991799853043350995075531276838753171770199594238596428121188033664754218345562493168782883
2N=p*(313*(p-1)+1)*(353*(p-1)+1)
3print(N)
Now all we need to do is start the challenge instance, run our small calculation script, and pipe its output over to nc:
python3 calc.py | nc IP PORT
Just like magic, out pops our flag.
Comments
Nothing yet. Say the first thing.
Sign in to join the conversation.