From dc9c9fa805c6d122f305b7eb251e747478881968 Mon Sep 17 00:00:00 2001 From: "Jakob L. Kreuze" Date: Sat, 4 May 2019 18:39:25 -0400 Subject: Rename post --- posts/PlaidCTF 2019 Writeups/plaidctf-2019.org | 456 --------------------- posts/Writeups for PlaidCTF 2019/plaidctf-2019.org | 456 +++++++++++++++++++++ 2 files changed, 456 insertions(+), 456 deletions(-) delete mode 100644 posts/PlaidCTF 2019 Writeups/plaidctf-2019.org create mode 100644 posts/Writeups for PlaidCTF 2019/plaidctf-2019.org (limited to 'posts') diff --git a/posts/PlaidCTF 2019 Writeups/plaidctf-2019.org b/posts/PlaidCTF 2019 Writeups/plaidctf-2019.org deleted file mode 100644 index 6818718..0000000 --- a/posts/PlaidCTF 2019 Writeups/plaidctf-2019.org +++ /dev/null @@ -1,456 +0,0 @@ -#+TITLE: Writeups for PlaidCTF 2019 -#+DATE: <2019-04-14 Sun> -#+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 -#include -#include -#include - -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. diff --git a/posts/Writeups for PlaidCTF 2019/plaidctf-2019.org b/posts/Writeups for PlaidCTF 2019/plaidctf-2019.org new file mode 100644 index 0000000..8491347 --- /dev/null +++ b/posts/Writeups for PlaidCTF 2019/plaidctf-2019.org @@ -0,0 +1,456 @@ +#+TITLE: Writeups for PlaidCTF 2019 +#+DATE: <2019-04-14 Sun> +#+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 +#include +#include +#include + +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. -- cgit v1.3