Tags: chinese-remainder
Rating:
# The Challenge
> Why would you waste your time catching more than one coelacanth?
>
> nc chal.uiuc.tf 2004
>
> Author: potatoboy69
The challenge gave us a netcat interface and the source code behind it. This is the source code:
```
#!/usr/bin/python
import random
from Crypto.Util import number
from functools import reduce
TOTAL = 15
THRESHOLD = 10
MAX_COELACANTH = 9
NUM_LOCKS = 5
NUM_TRIES = 250
# substitute for math.prod
prod = lambda n: reduce(lambda x, y: x*y, n)
def create_key(t, n, size=8):
while True:
seq = sorted([number.getPrime(size) for _ in range(TOTAL)])
if len(set(seq)) != len(seq):
continue
alpha = prod(seq[:t])
beta = prod(seq[-t + 1:])
if alpha > beta:
secret = random.randint(beta, alpha)
shares = [(secret % num, num) for num in seq]
return secret, shares
def construct_key(shares):
glue = lambda A, n, s=1, t=0, N=0: (n < 2 and t % N or glue(n, A % n, t, s - A//n * t, N or n), -1)[n < 1]
mod = prod([m for s, m in shares])
secret = sum([s * glue(mod//m, m) * mod//m for s, m in shares]) % mod
return secret
if __name__ == "__main__":
print("Hi, and welcome to the virtual Animal Crossing: New Horizon coelacanth vault!")
print("There are {} different cryptolocks that must be unlocked in order to open the vault.".format(NUM_LOCKS))
print("You get one portion of each code for each coelacanth you have caught, and will need to use them to reconstruct the key for each lock.")
print("Unfortunately, it appears you have not caught enough coelacanths, and thus will need to find another way into the vault.")
print("Be warned, these locks have protection against brute force; too many wrong attempts and you will have to start over!")
print("")
num_shares = abs(int(input("How many coelacanth have you caught? ")))
if num_shares > MAX_COELACANTH:
print("Don't be silly! You definitely haven't caught more than {} coelacanth!".format(MAX_COELACANTH))
print("Come back when you decide to stop lying.")
quit()
for lock_num in range(NUM_LOCKS):
print("Generating key for lock {}, please wait...".format(lock_num))
secret, shares = create_key(THRESHOLD, TOTAL)
print(secret)
r_secret = construct_key(random.sample(shares, THRESHOLD))
assert(secret == r_secret)
print("Generated!")
print("Here are your key portions:")
print(random.sample(shares, num_shares))
for num_attempts in range(NUM_TRIES):
n_secret = abs(int(input("Please input the key: ")))
if secret == n_secret:
print("Lock {} unlocked with {} failed attempts!".format(lock_num, num_attempts))
break
else:
print("Key incorrect. You have {} tries remaining for this lock.".format(NUM_TRIES - num_attempts))
else:
print("BRUTE FORCE DETECTED. LOCKS SHUT DOWN.")
print("Get out. You don't deserve what's in this vault.")
quit()
print("Opening vault...")
with open("flag.txt", "r") as f:
print(f.read())
```
The challenge asks you for a number less than 10. If you provide a number greater than 9, it will quit. If you give it an integer less than 10, the challenge gives you that amount of "key portions," and asks you to enter the key. It gives you 250 tries to guess the key (the print statement has an off by one error).
```
Hi, and welcome to the virtual Animal Crossing: New Horizon coelacanth vault!
There are 5 different cryptolocks that must be unlocked in order to open the vault.
You get one portion of each code for each coelacanth you have caught, and will need to use them to reconstruct the key for each lock.
Unfortunately, it appears you have not caught enough coelacanths, and thus will need to find another way into the vault.
Be warned, these locks have protection against brute force; too many wrong attempts and you will have to start over!
How many coelacanth have you caught? 9
Generating key for lock 0, please wait...
Generated!
Here are your key portions:
[(119, 229), (197, 251), (0, 181), (189, 233), (22, 211), (145, 179), (195, 223), (155, 239), (179, 227)]
Please input the key: 1
Key incorrect. You have 250 tries remaining for this lock.
```
### Key generation
Looking more closely at the source code, we find the key generation function, which generates the key and shares of the key.
```
TOTAL = 15
...
def create_key(t, n, size=8):
while True:
seq = sorted([number.getPrime(size) for _ in range(TOTAL)])
if len(set(seq)) != len(seq):
continue
alpha = prod(seq[:t])
beta = prod(seq[-t + 1:])
if alpha > beta:
secret = random.randint(beta, alpha)
shares = [(secret % num, num) for num in seq]
return secret, shares
```
First, it generates 15 unique 8-bit primes. I want to see what the range of the primes are, so I ran that line a few times. I found that this includes all primes between 131 and 257. This could be helpful for later.
Next, the function computes the product of the smallest 10 of these primes, and the largest 5 of these primes separately, calling them `alpha` and `beta` respectively. A key between `alpha` and `beta` is chosen only if `alpha > beta`. If not, new primes are generated, and this repeats until the condition is satisfied.
Before returning the key, it also computes the shares. Each share is a tuple of the remainder the key divided by one of the generated primes, and the corresponding prime. After some Googling, I found that there is an algorithm that can help us: the Chinese Remainder Theorem (CRT). This is from Google:
> In number theory, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.
Thankfully, the divisors in our case are all prime numbers, so they are coprime with each other and we can use the CRT.
# The Solution
### Chinese Remainder Theorem
First, I implemented a version of the CRT. There are many implementations of the CRT online; this is the one I used.
```
from functools import reduce
prod = lambda n: reduce(lambda x, y: x*y, n)
def mul_inv(a, b):
b0 = b
x0, x1 = 0, 1
if b == 1: return 1
while a > 1:
q = a // b
a, b = b, a%b
x0, x1 = x1 - q * x0, x0
if x1 < 0: x1 += b0
return x1
def chinese_remainder(n, a):
sum = 0
product = prod(n)
for n_i, a_i in zip(n, a):
p = product // n_i
sum += a_i * mul_inv(p, n_i) * p
return sum % product, product
shares = [(125, 193), (13, 167), (63, 229), (87, 131), (106, 191), (120, 257), (9, 163), (78, 173), (126, 137)]
n = [s[1] for s in shares]
a = [s[0] for s in shares]
key, N = chinese_remainder(n, a)
```
Next, I manually tested this algorithm to see if I can break the keys (I ran the source code locally, making it print out the shares and the actual key). Unfortunately, after testing with several inputs, it seems like the key the CRT generated was wrong. That's because the CRT finds the MINIMUM value `x` that satisfies the constraints; there are mulitple possible values of `x`. The general solution for CRT is actually: `x + N * k`, where N is the product of the divisors (the 9 primes), and `k` is some non-negative constant. So, our next step is to find `k`.
### Finding `k`
We only have 250 tries per password, so we can't just try all `k`. I first did some experimenting. We can reduce the possible values for `k` if we can find `alpha` and `beta`. We have access to 9 of the 15 primes, and we know there are only 24 primes between 131 and 257. This means there are 15 possible options left for the 6 primes we don't know, which equates to `15 choose 6 = 5005` possible combinations of missing primes. For each of those combinations, we can compute `alpha` and `beta`, and if `alpha > beta`, find all `k` such that the key lies between `alpha` and `beta`.
```
from itertools import combinations
from functools import reduce
from math import ceil, floor
prod = lambda n: reduce(lambda x, y: x*y, n)
def generate_possible_keys(shares):
possible_primes = set([131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257])
primes = sorted([s[1] for s in shares])
for p in primes:
possible_primes.remove(p)
comb = combinations(list(possible_primes), 15 - len(shares))
x, N = crt(shares) # all x + Nk
possible_ks = set([])
for c in comb:
seq = sorted(primes + list(c))
alpha = prod(seq[:10])
beta = prod(seq[-10 + 1:])
if alpha > beta:
range_n = (beta - x, alpha - x)
range_k = (ceil(range_n[0] / N), floor(range_n[1] / N))
for k in range(range_k[0], range_k[1] + 1):
possible_ks.add(k)
print(possible_ks)
possible_keys = [x + N * k for k in possible_ks]
return possible_keys
shares = [(125, 193), (13, 167), (63, 229), (87, 131), (106, 191), (120, 257), (9, 163), (78, 173), (126, 137)]
possible_keys = generate_possible_keys(shares)
```
I tested this out on several different lists of shares and found that number of unique `k`s was always less than 250. So, I could try all possible values of `k` within the guessing limits. In fact, this is ONLY true if the number of shares I request is 9. If we only have access to 8 shares, the number of possible `k`s balloons to the ten thousands. Having access to even less shares would increase possible values of `k` even more.
After the CTF, I realized that the values of `k`s never even went above 250. I could have just tried all `k`s in the range `[0, 250)`.
### Putting it all together
I wrote a script in Python to interact with the socket interface for me:
```
import socket
def netcat(hn, p):
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect((hn, p))
data = sock.recv(1024).decode()
print(data)
data = sock.sendall(b'9\n')
data = sock.recv(1024).decode()
print(data)
for _ in range(5):
shares = eval(data.split("\n")[-2])
xs = generate_possible_keys(shares)
for x in xs:
print(x)
sock.sendall(f"{x}\n".encode())
data = sock.recv(1024).decode()
print(data)
if "Key incorrect" not in data:
break
netcat("chal.uiuc.tf", 2004)
print('done')
```
After unlocking the last key, we see this:
```
Opening vault...
Looks like the vault has already been emptied :( however, you can have this flag instead: uiuctf{small_oysters_expire_quick}
```
