LSE Blog

Operating systems, computer security, languages theory, and even more!

  • About us

    • Main website
    • Git repositories
    • @lse_epita

    RSS Feed

  • Categories
    • Events
    • Hardware
    • Language
    • Reverse Engineering
    • Security
    • System
      • Linux
    • Tutorials
      • Parallelism
      • PythonGDB
    • Writeups
      • CSAW CTF 2012 Quals
      • DEFCON 2013 Quals
      • DEFCON2K12 Prequals
      • Hack.lu CTF 2012
      • Hack.lu CTF 2013
      • NDH2K12 Prequals
      • NDH2K13 Quals
      • Olympic-CTF 2014
      • PlaidCTF 2012
      • SecuInside2K12 Prequals
      • ebCTF 2013
  • Authors
    • ✉ Samuel Angebault
    • ✉ Remi Audebert
    • ✉ Jean-Loup Bogalho
    • ✉ Pierre Bourdon
    • ✉ Marwan Burelle
    • ✉ Samuel Chevet
    • ✉ Pierre-Marie de Rodat
    • ✉ Ivan Delalande
    • ✉ Corentin Derbois
    • ✉ Nassim Eddequiouaq
    • ✉ Louis Feuvrier
    • ✉ Fabien Goncalves
    • ✉ Nicolas Hureau
    • ✉ Gabriel Laskar
    • ✉ Stanislas Lejay
    • ✉ Franck Michea
    • ✉ Bruno Pujos
    • ✉ Clement Rouault
    • ✉ Pierre Surply
    • ✉ Kevin Tavukciyan
  • Hack.lu CTF 2012: Zombies PPTP (450 points)

    Written by Pierre Bourdon
    2012-10-25 11:00:00

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

     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.

    Tweet
    Permalink & comments
    blog comments powered by Disqus

© LSE 2012 — Main website — RSS Feed