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:

start_pptp
200 Ok
dead234a1f13beef
200 41787c9f6ffde56919ca3cd8d8944590a9fff68468e2bcb6
incompatible
200 78165eccbf53cdb11085e8e5e3626ba9bdefd5e9de62ce91

In the Python script, the two algorithms are named response_newTechnologie and response_lm. From the network dump, we can assume that the first hash sent by the client is from response_newTechnologie: the server answered it was incompatible, so the client tried the older method and sent the second hash, generated with response_lm. The older method is probably more buggy, so let’s work on it first. Here is the implementation:

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:

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:

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

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

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.