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 Password: |
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); i++; } else if(!random) { mpz_clrbit(key, j); 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_init(t); mpz_set_ui(t, range); mpz_t auth; mpz_init(auth); mpz_add(t, t, nonce); mpz_t newmod; mpz_init(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 Password: ^Z $ py -c 'import time; print pow(int(time.time())/3600 + 4068051704, 2**1024-1, 13371337)' 5120513 $ fg Password: 5120513 Last login: Wed Oct 24 20:53:56 2012 from 118.124.41.39 FreeBSD 9.1-RC2 (TOKEN) #0: Sun Oct 21 19:22:21 CEST 2012 $ ls secret $ cat secret NothingInHereWeAlldiedforNothing! |
The flag: NothingInHereWeAlldiedforNothing!
1 comment
Thanks for explaining this challenge, we were a bit confused about the whole thing.
Our solution:
http://eindbazen.net/2012/10/hack-lu-2012-reduced-security-agency/