Hack.lu 2012 – Reduced Security Agency

The name of the challenge obviously implies it has something to do with RSA, but the given information confused us completely. We are given a source file containing some functions, and a “rsa.pub” file which appears to contain a modulus and an exponent (both very large).

When you connect to the service you get a “nonce” number and you have to enter the corresponding password. It was pretty clear that the gen_auth function from the given source had something to do with this:

unsigned int
gen_auth(mpz_t key, mpz_t modulus, mpz_t nonce)
	time_t now = time(NULL);
	unsigned int range = now / 3600;
	unsigned int token;

	mpz_t t;

	mpz_set_ui(t, range);
	mpz_t auth;
	mpz_add(t, t, nonce);
	mpz_t newmod;
	mpz_set_ui(newmod, 13371337);
	mpz_powm(auth, t, key, newmod);
	token = mpz_get_ui(auth);

	return token;

The rest of the source and the rsa key confused us however, since the modulus from the rsa.pub is not used anywhere the corresponding exponent is probably also useless. And the rest of the functions in the source mention “keys” but the generated keys are very large (2048 bits) and because of the way they were generated they could not work for any RSA-like scheme. We just couldn’t figure out how they could possibly relate to gen_auth, so we concluded that they were for a later part of the challenge and ignored them for now.

Looking at gen_auth, we can see it does modular exponentiation using 13371337 as the modulus. This is not a prime number:

user@box:~$ factor 13371337
13371337: 7 73 137 191

This means there are only lcm(7-1, 73-1, 137-1, 191-1) == 116280 unique keys possible, where lcm is the lowest common multiple function. In python:

# greatest common divisor of a and b
def gcd(a, b):
	while b:      
		a, b = b, a % b
	return a

# lowest common multiple of a and b
def lcm(a, b):
	return a * b // gcd(a, b)

# prime factors of 13371337
ps = [7, 73, 137, 191]

totalkeys = reduce(lcm, (p - 1 for p in ps))

This means it is pretty feasible to bruteforce this. Actually continuing with this idea it is possible to bruteforce even more efficiently, since if a given nonce does not have prime order modulo one of the factors of 13371337 the number of unique keys will be even lower. This means that depending on the nonce the server gives, it is possible to check multiple equivalent keys at once.

First we calculate the orders of all the elements modulo the prime factors:

def findorder(x,p):
	if x == 0: return 1
	for i in range(1,p):
		if pow(x,i,p) == 1: return i

# prime factors of 13371337
ps = [7, 73, 137, 191]

# order of x for x in Z_p for p in ps
orders = [[findorder(x, p) for x in range(p)] for p in ps]

Since the prime factors are very small this is efficient enough, and it’s easy to understand. Now we can calculate the number of unique keys for a given nonce:

def unique_key_count(nonce):
	global ps, orders
	return reduce(lcm, (o[nonce % p] for p, o in zip(ps, orders)))

The equivalent keys (< 116280) for a given key/nonce combo are then given by: [python] def equivalent_keys(nonce, key): global totalkeys return range(key, totalkeys, unique_key_count(nonce)) [/python] In our bruteforcer we keep the entire keyspace in a bitarray, with True representing keys that have not been eliminated. We can calculate the best key to try for a given nonce as follows: [python] def find_best_key(keys, nonce): global totalkeys uniqkeys = unique_key_count(nonce) # number of equivalent keys that exist for each unique key equivkeys = totalkeys / uniqkeys bestkey = None bestcount = -1 for key in range(1, uniqkeys + 1): # how many of the keys equivalent to key have not been tested yet? keycnt = keys[key:totalkeys:uniqkeys].count() if keycnt > bestcount: bestkey = key bestcount = keycnt # exit loop early if all equivalents are untested, since that's # already the best possible score. if bestcount == equivkeys: break return bestkey [/python] Then it's just a matter of plugging in a SSH library (we used paramiko) to perform the bruteforce. Our bruteforce found the key (65535) in 2767 requests in less than 5 minutes, eliminating on average 42 keys per authentication attempt. As it turned out, there is no more to this challenge. Read other writeups for an explanation of how the other code was related and how it could be solved without bruteforce!