aboutsummaryrefslogtreecommitdiff
path: root/haunt/posts/plaidctf-2019.org
diff options
context:
space:
mode:
Diffstat (limited to 'haunt/posts/plaidctf-2019.org')
-rw-r--r--haunt/posts/plaidctf-2019.org456
1 files changed, 456 insertions, 0 deletions
diff --git a/haunt/posts/plaidctf-2019.org b/haunt/posts/plaidctf-2019.org
new file mode 100644
index 0000000..836c7a6
--- /dev/null
+++ b/haunt/posts/plaidctf-2019.org
@@ -0,0 +1,456 @@
+#+TITLE: Writeups for PlaidCTF 2019
+#+DATE: <2019-04-14 Sun 00:00>
+#+TAGS: writeup security reverse-engineering capture-the-flag x86 c python
+
+My long-lived hiatus from capture-the-flag has come to an end, as I got off my
+ass this weekend to play in PlaidCTF 2019. Being a one-man team is pretty
+lonely, but my old team wasn't playing, and even if they were, I don't know if I
+would've wanted to make the commute just to play with them.
+
+The team name I came up with was 0x7c_Jake since I've been listening to a lot of
+[[https://en.wikipedia.org/wiki/Less_Than_Jake][Less than Jake]] recently and =0x7c= is =jl= in x86. With any luck, though, I won't be
+playing under that team name again -- I'm going to reach out to the ACM chapter
+at my university and ask about starting a team associated with the school.[fn:1]
+
+But I'd imagine that you don't care much for that. You're here for my challenge
+solutions, aren't you?
+
+* can you guess me (100 pts)
+
+This was a pretty simple Python sandbox escape challenge. The constraint was
+that your input could have a maximum of 10 unique characters.
+
+#+BEGIN_SRC python :hl_lines 0
+count_digits = len(set(inp))
+if count_digits <= 10: # Make sure it is a number
+ val = eval(inp)
+else:
+ raise
+#+END_SRC
+
+So if you were thinking of sending off =print(secret_value_for_password)=, you're
+out of luck.
+
+#+BEGIN_SRC python :hl_lines 0
+f = lambda x: (len(set(x)) <= 10, len(set(x)))
+f("secret_value_for_password") # >>> (False, 15)
+#+END_SRC
+
+This was the challenge I poked at for warm up, and in about fifteen minutes I
+had what I believe is an unintended solution.
+
+#+BEGIN_SRC prog
+ ____ __ __ ____ __ __
+ / ___|__ _ _ _\ \ / /__ _ _ / ___|_ _ ___ ___ ___| \/ | ___
+| | / _` | '_ \ V / _ \| | | | | _| | | |/ _ \/ __/ __| |\/| |/ _ \
+| |__| (_| | | | | | (_) | |_| | |_| | |_| | __/\__ \__ \ | | | __/
+ \____\__,_|_| |_|_|\___/ \__,_|\____|\__,_|\___||___/___/_| |_|\___|
+
+
+
+Input value: help(flag)
+No Python documentation found for 'PCTF{hmm_so_you_were_Able_2_g0lf_it_down?_Here_have_a_flag}'.
+Use help() to get the interactive help utility.
+Use help(str) for help on the str class.
+
+Nope. Better luck next time.
+#+END_SRC
+
+* i can count (50 pts)
+
+The premise of this challenge is that there's some integer encoded as an ASCII
+string. It's continually incremented by one and then checked against a
+=check_flag=[fn:2] function. The flag is just whatever integer satisfies =check_flag=.
+
+You certainly _could_ have reverse engineered =check_flag= and plugged all of its
+constraints into z3, but the function is 1394 bytes long. An easier solution is
+to realize that the constraints are checked for each digit of the integer, open
+the program in a debugger, set some breakpoints at various points in =check_flag=,
+and brute-force the value digit-by-digit.
+
+This would've been a nice opportunity to use r2pipe or GDB's Python APIs, but I
+started this challenge close enough to the end of the competition that doing it
+by hand in GDB was the best course of action. I broke at =check_flag+0x31= so I
+could see what the individual digit being checked was, as well as at
+=check_flag+0x532= so I could see if the function was jumping to a =ret= -- which
+would indicate that the digit doesn't satisfy the constraints. Every time I came
+across a correct digit, I'd add a bogus '/' to the end of the integer string
+with =set *((char *)0x56555000+0x3048) = 0x2f=[fn:3] so that =check_flag= started
+checking the following digit, rather than incrementing the integer and ruining
+everything. Again, the return key on my keyboard would have appreciated it if I
+scripted my solution, but it worked and I was able to get the flag of
+"PCTF{2052419606511006177}".
+
+* big_maffs (250 pts)
+
+I found this challenge to be really difficult, and at the time of writing this,
+my solution is still running. I began by reverse engineering the binary to its
+equivalent C.
+
+#+BEGIN_SRC c :hl_lines 0
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+struct string {
+ uint64_t length;
+ char *data;
+};
+
+static char peanut[] = {
+ 0x05, 0xbb, 0x01, 0x59, 0x6f, 0x06, 0x18, 0x61, 0x3d, 0xa0,
+ 0x3a, 0xe4, 0x9c, 0xe4, 0xe1, 0xe6, 0x73, 0x93, 0x81, 0xf2,
+ 0x10, 0x6b
+};
+
+static char banana[] = {
+ 0x00, 0x01, 0x00, 0x01, 0x00, 0x01, 0x01, 0x01,
+ 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
+};
+
+static struct string *global_4090;
+
+
+// 0x00001189 1 26 eom_error
+void eom_error(void)
+{
+ puts("no more memory? https://downloadmoreram.com/");
+ exit(1);
+}
+
+// 0x000011a3 3 51 my_malloc
+void *my_malloc(int size)
+{
+ char *ret;
+ if ((ret = malloc(size)) == NULL) {
+ eom_error();
+ }
+ return ret;
+}
+
+// 0x000011d6 3 62 my_realloc
+void *my_realloc(char *data, int length)
+{
+ char *res;
+
+ // STACK SIZE 0x20
+ if ((res = realloc(data, length)) == NULL) {
+ eom_error();
+ }
+
+ return res;
+}
+
+// 0x00001214 1 97 make_string
+struct string *make_string(char *data, int n)
+{
+ struct string *ret;
+
+ // STACK SIZE 0x20
+ ret = my_malloc(sizeof(struct string));
+ ret->data = my_malloc(n);
+ memcpy(ret->data, data, n);
+ ret->length = n;
+
+ return ret;
+}
+
+// 0x00001695 7 72 all_null?
+int all_null(struct string *s)
+{
+ int null_count;
+
+ null_count = 0;
+ while (null_count < s->length) {
+ if (s->data[null_count] == '\0') {
+ null_count++;
+ } else {
+ return 0;
+ }
+ }
+
+ return 1;
+}
+
+// 0x000016dd 8 146 ends_with_digit?
+int ends_with_digit(struct string *s)
+{
+ int i;
+
+ // STACK SIZE 0x18
+ if (all_null(s)) {
+ return 0;
+ }
+
+ i = s->length - 1;
+
+ while (i >= 0) {
+ if (s->data[i] == '\0') {
+ i--;
+ } else {
+ // True for c > 64, as well as the following cases:
+ // - c == 1
+ // - 4 <= c <= 7
+ // - 16 <= c <= 31
+ return (s->data[i] & 0xaa) > (s->data[i] & 0x55);
+ }
+ }
+
+ return 0;
+}
+
+// 0x00001275 1 70 resize_string_by_one
+void resize_string_by_one(struct string *s)
+{
+ // STACK SIZE 0x10
+ s->length++;
+ s->data = my_realloc(s->data, s->length);
+}
+
+// 0x000012bb 21 492 strum
+void strum(struct string *a, struct string *b)
+{
+ int onion;
+ int brisket;
+ int cheese;
+ char donut;
+ char syrup;
+ char carrot;
+ char melon;
+ char butter;
+
+ // STACK SIZE 0x30
+
+ butter = '\0';
+ cheese = 0;
+
+ // 0x13c3
+ while (cheese < b->length) {
+ melon = '\0';
+ brisket = 0;
+
+ while (brisket < 8) {
+ syrup = butter \
+ + ((a->data[cheese] >> brisket) & 1) \
+ + ((b->data[cheese] >> brisket) & 1);
+
+ if (banana[syrup + 2] != '\0') {
+ melon |= 1 << brisket;
+ }
+
+ butter = banana[syrup + 8];
+ brisket++;
+ }
+
+ if (a->length == cheese) {
+ resize_string_by_one(a);
+ }
+
+ a->data[cheese] = melon;
+ cheese++;
+ }
+
+ while (butter != '\0') {
+ if (cheese >= a->length) {
+ resize_string_by_one(a);
+ }
+
+ carrot = '\0';
+ onion = 0;
+
+ while (onion < 8) {
+ donut = butter + ((a->data[cheese] >> onion) & 1);
+
+ if (banana[donut + 2] != '\0') {
+ carrot |= 1 << onion;
+ }
+
+ butter = banana[donut + 8];
+ onion++;
+ }
+
+ a->data[cheese] = carrot;
+ cheese++;
+ }
+}
+
+// This function is extremely similar to strum, but with 'subl %eax, %esi; movl
+// %esi, %eax' at 0x00001335 instead of 'addl %esi, %eax'.
+void bake(struct string *a, struct string *b)
+{
+ int onion;
+ int brisket;
+ int cheese;
+ char donut;
+ char syrup;
+ char carrot;
+ char melon;
+ char butter;
+
+ // STACK SIZE 0x30
+
+ butter = '\0';
+ cheese = 0;
+
+ // 0x13c3
+
+ while (cheese < b->length) {
+ melon = '\0';
+ brisket = 0;
+
+ while (brisket < 8) {
+ syrup = butter \
+ + ((a->data[cheese] >> brisket) & 1) \
+ - ((b->data[cheese] >> brisket) & 1);
+
+ if (banana[syrup + 2] != '\0') {
+ melon |= 1 << brisket;
+ }
+
+ butter = banana[syrup + 8];
+ brisket++;
+ }
+
+ if (a->length == cheese) {
+ resize_string_by_one(a);
+ }
+
+ a->data[cheese] = melon;
+ cheese++;
+ }
+
+ while (butter != '\0') {
+ if (cheese >= a->length) {
+ resize_string_by_one(a);
+ }
+
+ carrot = '\0';
+ onion = 0;
+
+ while (onion < 8) {
+ donut = butter + ((a->data[cheese] >> onion) & 1);
+
+ if (banana[donut + 2] != '\0') {
+ carrot |= 1 << onion;
+ }
+
+ butter = banana[donut + 8];
+ onion++;
+ }
+
+ a->data[cheese] = carrot;
+ cheese++;
+ }
+}
+
+struct string *gaze(struct string *a, struct string *b)
+{
+ struct string *local_8;
+ struct string *local_10;
+ struct string *local_18;
+ struct string *local_20;
+ struct string *local_28;
+
+ // STACK SIZE 0x40
+
+ if (all_null(a)) {
+ local_28 = make_string("\x00", 1);
+ strum(local_28, b);
+ strum(local_28, global_4090);
+ return local_28;
+ }
+
+ if (all_null(b)) {
+ local_20 = make_string("\x00", 1);
+ strum(local_20, a);
+ bake(local_20, global_4090);
+ return gaze(local_20, global_4090);
+ }
+
+ local_18 = make_string("\x00", 1);
+ strum(local_18, b);
+ bake(local_18, global_4090);
+
+ local_10 = gaze(a, local_18);
+
+ local_8 = make_string("\x00", 1);
+ strum(local_8, a);
+ bake(local_8, global_4090);
+
+ return gaze(local_8, local_10);
+}
+
+void fcn_176f(struct string *a, struct string *b)
+{
+ // STACK SIZE 0x10
+ while (!ends_with_digit(a)) {
+ bake(a, b);
+ }
+ strum(a, b);
+}
+
+// 0x00001935 4 230 main
+int main(int argc, char **argv)
+{
+ struct string *local_8;
+ struct string *local_10;
+ struct string *local_18;
+ int local_1c;
+
+ // STACK SIZE 0x20
+ global_4090 = make_string("\x01", 1);
+
+ puts("Generating your flag, please wait warmly...");
+
+ local_18 = make_string("\x1e", 1);
+ local_10 = gaze(local_18, local_18);
+
+ local_8 = make_string((void *) 0x206e, 0x17);
+ fcn_176f(local_10, local_8);
+
+ local_1c = 0;
+
+ while (local_1c <= 0x15) {
+ peanut[local_1c] ^= local_10->data[local_1c];
+ local_1c++;
+ }
+
+ printf("Your flag is: %s\n", peanut);
+ return 0;
+}
+#+END_SRC
+
+TL;DR: among other things, there's a function called =gaze=[fn:4] that recursively
+generates an XOR decryption key for =peanut=.
+
+I took this be an "optimize me" challenge. My current solution memoizes the
+results of =gaze= into a linked list to reduce the number of recursive
+computations made. In retrospect, I probably should've used a binary search tree
+or a hash table instead of a linked list, but I was trying to quickly hack
+together a solution. Also in retrospect, I probably should spent my time
+figuring out what =strum= and =bake= _really_ do and reversing the calculation rather
+than trying my hand at optimizing it. Ah, well.
+
+One neat thing I found out about from working on this challenge was the
+=MALLOC_CHECK_= environment variable recognized by glibc. If it's set to =0=, heap
+corruption errors are silently ignored. My solution needed it, and I'm unsure of
+whether the heap corruption is in my translation of the original binary, or if
+it was in my memoization code. Either way, I have a feeling it will make itself
+useful again in the near future.
+
+---
+
+Addendum: As it turns out, memoization was a wildly sophomoric attempt at a
+solution, and the real solution was, as I mentioned, to figure out the purposes
+of =strum= and =bake=. It turns out that =strum= is base (-2) addition, =bake= is base
+(-2) subtraction, =gaze= is the Ackermann function, and that the structure is
+actually a [[https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic][bignum]], not a string. In this case, that poor assumption led me down
+a wrong path. Once you figure that out, you'll need to put your modular
+arithmetic chops to work as well. An excellent writeup from sasdf of [[https://balsn.tw/][Balsn]] is
+available [[https://sasdf.cf/ctf/writeup/2019/plaid/rev/bigmaffs/][here]].
+
+[fn:1] So if you currently study at UMass Amherst and you'd be interested in joining a CTF team, [[http://jakob.space/about/][shoot me an email!]]
+[fn:2] The executable wasn't stripped.
+[fn:3] Where =0x56555000= is the address that the binary was loaded to in memory, and =0x3048= is the beginning of the ASCII-encoded integer (plus an offset for whichever digit I was on)
+[fn:4] This time the binary _was_ stripped. I didn't bother updating the temporary names I used. Yes, I use foods for variables and random verbs for functions.

© 2015 - 2026 Jakob L. Kreuze