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(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:


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!
[(119, 229), (197, 251), (0, 181), (189, 233), (22, 211), (145, 179), (195, 223), (155, 239), (179, 227)]
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 for s in shares]
a = [s 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 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 / N), floor(range_n / N))
for k in range(range_k, range_k + 1):

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 ks 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 ks 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 ks never even went above 250. I could have just tried all ks 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}


Original writeup (https://github.com/coconut750750/ctfs/blob/master/UIUCTF%202020/coelacanth_vault_writeup.md).