Hack.lu 2012 CTF Challenge #4 (250)

4 – Reduced Security Agency

Some of our guys broke into the Reduced Security Agency and stole the source of their highly secure login system. Unfortunately no one of them made it uninfected back and so we only have a part of the source. Now it’s your turn to break their system and login to the agency.

HOST: ctf.fluxfingers.net
PORT: 2062
SOURCE: reduced_security_agency.tar.gz

Summary: weak RSA private key generation

$ ssh -p2062 hellman@ctf.fluxfingers.net
Please enter Token for user: user
nonce: 3602757791

After studying the sources, you can easily notice a strange key generation algo:

j = 2047;
while(i != j) {
	random = gmp_urandomb_ui(state, 1);
	if(random) {
		mpz_setbit(key, i);
	else if(!random) {
		mpz_clrbit(key, j);

Obviously all such keys look like 0b111111…1111. Let’s bruteforce count of 1’s for a private key for a given pubkey:

x0 = x = pow(31337, e, n)
for i in xrange(2048):
    if x == 31337:
        print "GOOD", i
    x = (pow(x, 2, n) * x0) % n
$ py brute.py 
GOOD 1023

So the private key is 2**1024 – 1. Let’c check how the challenge response is calculated:

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;

Response is pow(time()/3600 + nonce, privkey, 3133731337):

$ ssh -p2062 user@ctf.fluxfingers.net
Please enter Token for user: user
nonce: 4068051704
$ py -c 'import time; print pow(int(time.time())/3600 + 4068051704, 2**1024-1, 13371337)'
$ fg
Password: 5120513
Last login: Wed Oct 24 20:53:56 2012 from
FreeBSD 9.1-RC2 (TOKEN) #0: Sun Oct 21 19:22:21 CEST 2012
$ ls
$ cat secret

The flag: NothingInHereWeAlldiedforNothing!

1 comment

  1. Reinhart says:

    Thanks for explaining this challenge, we were a bit confused about the whole thing.

    Our solution:

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>