-
Hack.lu CTF 2012: Zombies PPTP (450 points)
Written by Pierre Bourdon
2012-10-25 11:00:001 2 3 4 5 6 7 8 9 10 11 12 13 14
Our intel shows us that the Zombies use a MS-PPTP like protocol and luckily we could intercept a challenge-response transmission of one of the Zombie outposts. The important thing for Zombies in this war is mass! Not only brain mass but their mass. So they built their PPTP protocol compatible to all older Zombie soldiers. Luckily our science team could extract the algorithm of the challenge-response system out of a captured Zombie brain … I spare you the details, let's just say it was not a pretty sight. And here comes your part soldier: we need the password of this intercepted transmission. With this password we were finally able to turn this war to our favor. So move your ass soldier and good luck! https://ctf.fluxfingers.net/challenges/pptp.tar.gz credits: 450 +3 (1st), +2 (2nd), +1 (3rd)
The given tarball contains two important things: a Python script implementing two challenge/response algorithms for authentication, and a PCAP dump showing this TCP transmission between two hosts:
1 2 3 4 5 6
start_pptp 200 Ok dead234a1f13beef 200 41787c9f6ffde56919ca3cd8d8944590a9fff68468e2bcb6 incompatible 200 78165eccbf53cdb11085e8e5e3626ba9bdefd5e9de62ce91
In the Python script, the two algorithms are named
response_newTechnologie
andresponse_lm
. From the network dump, we can assume that the first hash sent by the client is fromresponse_newTechnologie
: the server answered it wasincompatible
, so the client tried the older method and sent the second hash, generated withresponse_lm
. The older method is probably more buggy, so let's work on it first. Here is the implementation:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
def lm_hash(self, input_password): # only use the first 14 bytes input_password = input_password[0:14] # convert all characters to uppercase chars input_password = input_password.upper() # split given password in two parts via 8 bytes password_part1 = input_password[0:8] # concat two 0 bytes to reach 8 bytes password_part2 = input_password[8:14] + "\0\0" # hash part 1 part1_des = des(password_part1) hash_part1 = part1_des.encrypt(self.constant) # hash part 2 part2_des = des(password_part2) hash_part2 = part2_des.encrypt(self.constant) # concat hash parts output_hash = hash_part1 + hash_part2 # return hash as hex value return binascii.hexlify(output_hash) def response_lm(self, challenge, password): # generate lm_hash for response password_hash = self.lm_hash(password) if len(challenge) != 16: raise ValueError("Challenge has to be 8 byte hex value.") # create three passwords for the response password_res1 = password_hash[0:16] password_res2 = password_hash[12:28] password_res3 = password_hash[28:32] + "000000000000" # response part 1 part1_des = des(binascii.unhexlify(password_res1)) res_part1 = part1_des.encrypt(binascii.unhexlify(challenge)) # response part 2 part2_des = des(binascii.unhexlify(password_res2)) res_part2 = part2_des.encrypt(binascii.unhexlify(challenge)) # response part 3 part3_des = des(binascii.unhexlify(password_res3)) res_part3 = part3_des.encrypt(binascii.unhexlify(challenge)) # create full response and return response = res_part1 + res_part2 + res_part3 return binascii.hexlify(response)
Having worked a lot with MSCHAPv2 in the past, I found this algorithm very similar to MSCHAPv2 but using 2 LM hashes instead of a NTLM hash. The first vulnerability, which is common to MSCHAPv2, is that the third part of the response only uses two variable bytes: the key of the DES algorithm for part 3 always ends with 6 NUL bytes. We can bruteforce these two bytes very easily (65536 DES computations are done in less than 0.1s on a modern computer) and get part of the LM hash of the password. Unfortunately, that is not very useful in this case: the password is too long to bruteforce the whole LM hash, so we can't do anything with these two bytes.
The second vulnerability is that the key space for the first part of the LM hash is very reduced. First, the input password is converted to uppercase. If we assume that only alphabetical characters are present, that leaves us with only
26^8
(208 billions) possible keys. Still a lot, but manageable on a GPU in several hours. However, we're in a contest, we can't reimplement a GPU cracker and wait, we want the breakthrough bonus points!The third vulnerability is that DES takes an 8 character input as the key, but actually only uses 56 bits of that input, discarding the LSB of each character. This means that on the 26 possible alphabetical characters, only 13 need to be tested: the other 13 share the same high 7 bits. This reduces the key space to
13^8
(815 millions) possible keys, which can easily be tested with a simple C program on a CPU.The last thing we need is a way to check if the first 8 characters of the passwords match the ones used to generate the hash. If they match, the first part of the LM hash (first 64 bits) will be identical. This means the first part of the response will use an identical key, and because the challenge is constant that implies the first part of the response will be identical. Our bruteforce algorithm is the following:
1 2 3
For each 8 chars password using charset (EAOISCMWGYKQZ) if DES(challenge, DES("Trololol", password)) == 78165eccbf53cdb1 found
And here is a C implementation that finds the first 8 characters of the password, in uppercase, with an unknown LSB, in about 5 minutes on my laptop:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
#define CONSTANT "Trololol" #define CHALLENGE "\xde\xad\x23\x4a\x1f\x13\xbe\xef" #define WANTED "x\x16^\xcc\xbfS\xcd\xb1" #define CHARSET "EAOISCMWGYKQZ" #define CHARSETSIZE ((unsigned long)(sizeof (CHARSET))) #define CHARSETSIZE2 ((CHARSETSIZE)*(CHARSETSIZE)) #define CHARSETSIZE4 ((CHARSETSIZE2)*(CHARSETSIZE2)) #define CHARSETSIZE8 ((CHARSETSIZE4)*(CHARSETSIZE4)) #define NSTEPS CHARSETSIZE8 static void build_key(int step, char* buffer) { int idx[8]; for (int i = 0; i < 8; ++i) { idx[i] = step % CHARSETSIZE; step /= CHARSETSIZE; } for (int i = 0; i < 8; ++i) for (int j = 0; j < 8; ++j) buffer[i*8 + j] = (CHARSET[idx[i]] >> (7 - j)) & 1; } int main(void) { char bf_key[64]; char res_key[64]; char final_res[64]; char constant_bits[64]; char challenge_bits[64]; char wanted_bits[64]; for (int i = 0; i < 8; ++i) for (int j = 7; j >= 0; --j) { constant_bits[i * 8 + (7 - j)] = (CONSTANT[i] >> j) & 1; challenge_bits[i * 8 + (7 - j)] = (CHALLENGE[i] >> j) & 1; wanted_bits[i * 8 + (7 - j)] = (WANTED[i] >> j) & 1; } for (int step = 0; step < NSTEPS; ++step) { memcpy(res_key, constant_bits, 64); memcpy(final_res, challenge_bits, 64); build_key(step, bf_key); setkey(bf_key); encrypt(res_key, 0); setkey(res_key); encrypt(final_res, 0); if (!memcmp(final_res, wanted_bits, 64)) { printf("Found: %d\n", step); return 0; } if ((step % 1000000) == 0) printf("Current step: %d\n", step); } return 0; }
According to this, the first 8 chars are (approximately):
"ZOMCIESA"
. Now we can use about the same code to bruteforce the last 6 chars. We just need to be careful to use the right part of the hash to generate the second part of the response. The C code is not very different, so I will just skip this and post the second part:"EOSEMS"
. We can easily check if our answer is valid:1 2
>>> PPTP().response_lm('dead234a1f13beef', 'ZOMCIESAEOSEMS') '78165eccbf53cdb11085e8e5e3626ba9bdefd5e9de62ce91'
The hash is exactly the same. Win! However, this is not the key yet: remember that we divided our key space by 4: we only considered uppercase characters (where we should have considered upper and lowercase), and only characters with the LSB equal to 1 (because DES ignored that bit anyway). To get the real password, we can just bruteforce the
4^14
(268 millions) different possibilities using the new technologie hash, which does not lose informations. Here is the script we used, with a small hack to hardcode that the key starts with "ZOMBIES" (this can be deduced easily by a human):1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
import pptp for i in xrange(2**7 * 4**7): n1 = i / 128 n2 = i % 128 s1 = 'ZOMBIES' s2 = s1.lower() s = '' for j in xrange(7): if n2 & 1: s += s1[j] else: s += s2[j] n2 >>= 1 s1 = 'AEOSEMS' s2 = '@DNRDLR' s3 = s1.lower() s4 = s2.lower() for j in xrange(7): l = [s1, s2, s3, s4] s += l[n1 & 3][j] n1 >>= 2 x = pptp.PPTP() if x.response_newTechnologie('dead234a1f13beef', s) == '41787c9f6ffde56919ca3cd8d8944590a9fff68468e2bcb6': print s if (i % 100000) == 0: print i
After one or two minutes of computation (<3 PyPy), we get the real key that we can submit on the website:
ZomBIEsAdOReMS
.Tweetblog comments powered by DisqusPermalink & comments