#rgbctf

Below are writeups for various problems from (rgbCTF)[https://ctftime.org/event/1042], specifically the ones that I (Timeroot) managed to solve. This is Advanced Reversing Mechanics 1 and Advanced Reversing Mechanics 2, [another witty algo challenge name], Five Fives, icanhaz, Laser 1 and Laser 2, Lofi, THE LYCH KING, Object Oriented Programming, ralphie, Sadistic Reversing 1 and Sadistic Reversing 2, Time Machine, TooSlow, and Ye Olde PRNG.

This was played under (1064CBread)[https://ctftime.org/team/5320], and we ended up getting 2nd place. :)

Advanced Reversing Mechanics 1

As the name (“ARM1”) suggests, this is an ARM binary. It’s also 32-bit, so make sure to open it in 32-bit IDA or you won’t be able to decompile. The problem statement gives some bytes,

71, 66, 61, 42, 53, 45, 7A, 40, 51, 4C, 5E, 30, 79, 5E, 31, 5E, 64, 59, 5E, 38, 61, 36, 65, 37, 63, 7C,

This function is pretty simple: main passes the input to encrypt_flag(char*), then prints out the result as series fo hex values. So what does encrypt_flag do?

char *__fastcall encryptFlag(char *result) { char v1; // r3 int v2; // t1 v1 = *result; if ( *result ) { do { *result = v1 - 1; v2 = (unsigned __int8)(result++)[1]; v1 = v2; } while ( v2 ); } return result; }

It loops through the bytes and adds one to each. Great. So take the given array, look each character up in [http://asciitable.com], look one previous, and write that down. Honestly it was faster that way than automating it. And you get the flag!

Advanced Reversing Mechanics 2

This problem is similar in structure to ARM1, but encrypt_flag() looks considerably more complicated:

_BYTE *__fastcall encryptFlag(_BYTE *result) { unsigned int v1; // r3 _BYTE *i; // r1 int v3; // r3 bool v4; // zf unsigned int v5; // r3 unsigned int v6; // r2 __int64 v7; // r2 v1 = (unsigned __int8)*result; if ( *result ) { for ( i = result; ; v1 = (unsigned __int8)*i ) { v6 = (unsigned __int8)(v1 - 10); if ( v1 > 2); v7 = i - result; if ( !*i ) break; v3 = v7 - 5 * (((signed int)((unsigned __int64)(0x66666667LL * (signed int)v7) >> 32) >> 1) - HIDWORD(v7)); v4 = v3 == 2; v5 = (((unsigned __int8)*i > v3)) & 0xFF; if ( v4 ) LOBYTE(v5) = v5 - 1; *i = v5; } } return result; }

… but why reverse when we can black-box? Some playing around reveals that the Nth character of output only depends on the first N characters of input. So let’s use this function, encrypt_flag, as an oracle, and try progressively longer things until we get our goal. We write a solver:

#include "stdio.h" #include "string.h" #define HIDWORD(foo) ((foo >> 32) & 0xFFFFFFFF) char* encryptFlag(char *result) { unsigned char v1; // r3 char *i; // r1 int v3; // r3 char v4; // zf unsigned int v5; // r3 unsigned int v6; // r2 unsigned long long v7; // r2 v1 = (unsigned char)*result; if ( *result ) { for ( i = result; ; v1 = (unsigned char)*i ) { v6 = (unsigned char)(v1 - 10); if ( v1 > 2); v7 = i - result; if ( !*i ) break; v3 = v7 - 5 * (((signed int)((unsigned long long)(0x66666667LL * (signed int)v7) >> 32) >> 1) - HIDWORD(v7)); v4 = v3 == 2; v5 = (((unsigned char)*i > v3)) & 0xFF; if ( v4 ) v5 = v5 - 1; *i = v5; } } return result; } void main(int argc, char** argv){ char* goal = "\x0A\xFB\xF4\x88\xDD\x9D\x7D\x5F\x9E\xA3\xC6\xBA\xF5\x95\x5D\x88\x3B\xE1\x31\x50\xC7\xFA\xF5\x81\x99\xC9\x7C\x23\xA1\x91\x87\xB5\xB1\x95\xE4"; int len = strlen(goal); printf("Len %d\n", len); char trial[35+1]; char check[35+1]; for(int l=0;l toVisit = new LinkedList(); LinkedList<integer> toMark = new LinkedList(); for(int x=0;x 0){ int vis = toVisit.pop(); { int x = vis/5000; int y = vis%5000; if(!map[x][y]) continue; if(marked[x][y]) continue; islands++; System.out.println("Island at "+x+", "+y); } toMark.push(vis); while(toMark.size() > 0){ int mark = toMark.pop(); int x = mark/5000; int y = mark%5000; if(!map[x][y]) continue; if(marked[x][y]) continue; marked[x][y] = true; if(x>0) toMark.add((x-1)*5000 + (y-0)); if(x0) toMark.add((x-0)*5000 + (y-1)); if(y guesses = new ArrayList(); for(int x=1;xicanhaz2

and file icanhaz2 tells us that it’s xz again:

mv icanhaz2 icanhaz2.xz && xz -d icanhaz2.xz

and we’re left with an SVG now. Viewing the SVG, it appears blank. Opening up the SVG in a text editor shows many lines of the form

<rect x="66" y="30" width="1" height="1" fill="#fffffd"></rect>

That is, boxes that are just barely off-white, in the blue channel. So find-and-replace #fffffd with #000000, and we get a visible QR code. PAss that into [https://zxing.org/w/decode] and we get a base64 string:

/Td6WFoAAATm1rRGAgAhARYAAAB0L+Wj4AbxAN1dAA2XxNFhRNBaOJSxhV08AXoOcZxtalpXU+c+q/ppfZc1/t0z3BU/P16F9jAlXbjrzh5cXk/9vLbc+8NQJ8PNawtALEPD17f25zdggODx3xzNLY3SjGTIlX0fbqo6HFkHYkIzOjjUgJcN1KbzGRouW+G8TakjrJ4y5Pk7jv/stqRiV0ICPYxKpnZSEn0aLzQSl46j6H3BBUBhRuGgxue3TXIzw5HGMlchgNBs6SCfHU0SkX4zlSKqOWSyKrJ5JMgwC47en2kI68/tRNQYaYzvGGcWcR/iEgNYO/jHVDVLAAAAADjqmgxrEIjCAAH5AfINAADD+B/oscRn+wIAAAAABFla

de-b64ing that gives garbled nonsense, but it starts with ý7zXZ��æ.. whic looks like another XZ compressed file. So run

echo "/Td6WFoAAATm1rRGAgAhARYAAAB0L+Wj4AbxAN1dAA2XxNFhRNBaOJSxhV08AXoOcZxtalpXU+c+q/ppfZc1/t0z3BU/P16F9jAlXbjrzh5cXk/9vLbc+8NQJ8PNawtALEPD17f25zdggODx3xzNLY3SjGTIlX0fbqo6HFkHYkIzOjjUgJcN1KbzGRouW+G8TakjrJ4y5Pk7jv/stqRiV0ICPYxKpnZSEn0aLzQSl46j6H3BBUBhRuGgxue3TXIzw5HGMlchgNBs6SCfHU0SkX4zlSKqOWSyKrJ5JMgwC47en2kI68/tRNQYaYzvGGcWcR/iEgNYO/jHVDVLAAAAADjqmgxrEIjCAAH5AfINAADD+B/oscRn+wIAAAAABFla" | base64 --decode | xz -d

and it prints(!) out

█████████████████████████████████ █████████████████████████████████ ████ ▄▄▄▄▄ █▀▀ ███ ▀▀█ ▄▄▄▄▄ ████ ████ █ █ █▄▀██▀▀▀ ▀█ █ █ ████ ████ █▄▄▄█ █ ▄ █ ▄ ██ █▄▄▄█ ████ ████▄▄▄▄▄▄▄█ █ ▀▄█ █▄█▄▄▄▄▄▄▄████ ████ ▄▀ ▀▀▄▄▀▀█ ▀ ▀ ▄▄▀▄ ▀████ ████▄█▀▄▀▀▄█ ▀▀ ▀▀▀▀▀▄▀▀█▄ ████ ████▄ █▀ █▄ ██▄ █▀██▀ ▀▄▀ ████ ████▄▀█▄█▄▄ ▄▀█ █ ██▄▀▀ ▀▄█▀ ████ ████▄▄▄▄██▄▄▀▀ █ ▄▀▄ ▄▄▄ ▄█▀ ████ ████ ▄▄▄▄▄ █▄█▀▄ ▄▀▄ █▄█ █ ▄████ ████ █ █ █▀█▄▀▄▀▄█▄▄▄ █▄▄█████ ████ █▄▄▄█ █▀▄██▀▀ ▀▀█ █▄█▄█▄████ ████▄▄▄▄▄▄▄█▄▄█▄█▄█▄▄█▄██▄█▄▄████ █████████████████████████████████ █████████████████████████████████

which scans in a QR code reader to rgbCTF{iCanHaz4N6DEVJOB}.

Laser 1 - Factoring

The basic approach for LaserLang here is to

Figure out a “normal” assembly implementation, using reads/writes/adds/branches/gotos

Write all the code in one line

Implement the branches and gotos by leaving the line to skip around.

To avoid the headache of juggling the order of a stack, we use a separate stack for each conceptual “register” (including “array registers”).

One nice thing about keeping your Laser program in one line like this, is that you can write all your documentation below it in the same file – a unique way to comment! So my English description of the code was actually just below the program, in my .lsr file. It was as follows:

I rsUD>rsUs rsU %⌝ > D(r'1'×'0'l ⌝ UU # \pDrsUs/ \ Dp/ print "1" store N to stack 0 store 2 to stack 1 main loop: duplicate N move N to stack 1 move N to stack 2 duplicate x move x to stack 2 modulo if 0: copy x to stack 2 decrement x (on stack 1) duplicate x duplicate x multiply (compute x2) duplicate N move N to stack 1 check greater than contine loop if 0 return

“N” is the number we’re supposed to factor. It lives in stack 0. “x” is the number we’re going to try dividing by, and we start with x = N. It lives in stack 1. We repeatedly make a copy of N and x, and divide and compute the remainder. If the remainder is 0, we copy x to stack 2 (our “results” stack). We decrement x, and continue our main loop only if x is still positive. At the end we return stack 2.

Laser 2 - Sorting

(See Laser1.md for some general tips on writing good Laser code.)

We sort through a version of selection sort, see https://en.wikipedia.org/wiki/Selection_sort. We have a list of “remaining” numbers (stacks 0/1), and a sorted list of “selected” numbers (stack 2). These are initially the given input, and empty, respectively.

In each step, we want to pick out the smallest number from the remaining ones, and put it on top of our “selected” stack. So we take the first number from “remaining” (in stack 0) and move to “selected”. Then we go one by one through each “remaining” number, moving them to stack 1 as we do so. Each time we move one from stack 0 to stack 1, we compare it with stack 2; if the number on stack 1 is smaller than on stack 2, we swap them. In this way, by the time stack 0 is empty, the smallest number has been put on stack 2.

Then we copy stack 1 back to stack 0 for the next loop.

We do this until the “remaining” list is empty, at which point stack 2 has been sorted. We return stack 2.

Code:

I> c'1'g ⌝p sUs >DsU r UrwD l⌝psUswUwDD> DcsU'0'g !⌝p >c⌝pw \>D \ \p / \ / \ p/ \p / \ / p \ sUsU # take input to stack 0 find smallest element: move top element to stack 2 loop: move top of 0 to 1 duplicate top of 1 copy top of 2 to 1 compare. if smaller, pop swap top of 1 and 2 else, pop check stack 0 cardinality if NOT 0, loop #copy stack 1 back to stack 0 check stack 1 cardinality if 0, skip: move top of 1 to 0 go back to check check stack 0 cardinality if NOT 1, main loop move last thing up return on stack 2

Lo-fi

We are given a .wav file. Listening to it, it’s generally some nice simple music; around 30 seconds, it gets a little bit more random. As it ends, there’s a few quick beeps that sound out of place. What are those beeps?

Opening this up in Audacity and looking at the spectrogram, we see the letters “tinyurl” spelled out by the quick beeps. This suggests that we need to find a ‘shortcode’, and then visit http://tinyurl.com/.

The flavortext (“Don’t let your dreams be ones and zeroes”) suggests that we should be looking for something like binary. The somewhat irregular notes in the second half of the song (29.6s - 41.5s) are a candidate. Starting from the drop, we count with the beat, writing down a 0 for each time there is no note, and 1 for each time there is. The pitch is irrelevant.

This gives the string 011001100110101000101101001100110011000000110010. Doing this in real time was way to hard, but if we slowed the song down by 4x it was much more doable. Music training is recommended.

We have 48 bits, which is good, cause that’s a multiple of 8. Decoding to ASCII gives “fj-302”. http://tinyurl.com/fj-302 redirects to a Pastebin that says rgbCTF{subscr1b3_t0_qu1nt3c_0n_yt_plz}.

LYCH King

In retrospect, perhaps this should have been done black-box, like almost everything in this category (ARM1/ARM2/SadRev1/SadRev2) was. But hey, who doesn’t want to reverse compiled Haskell?

Yeah, this binary is Haskell that was compiled by GHC. That might be reasonably accessible to you, if you (1) know Haskell, (2) know how STG machines work, and (3) know GHC’s conventions for storing thunks and STG type data. I meet, like, 0.5/3 requirements.

Goolging for “Haskell decompiler” quickly turns up [https://github.com/gereeter/hsdecomp] as exactly what we need: a decompiler for GHC-compiled 64-bit executables. Great! Let’s try it out!

$ python3 runner.py ../../rgbctf/lych/lich Error in processing case at c3uZ_info Error: Error Location: 140 Disassembly: mov rax, qword ptr [rbp + 8] mov rcx, rbx and ecx, 7 cmp rcx, 1 jne 0x407d33 add r12, 0x18 cmp r12, qword ptr [r13 + 0x358] ja 0x407d48 mov qword ptr [r12 - 0x10], 0x407c28 mov qword ptr [r12], rax lea rbx, [r12 - 0x10] mov rsi, rbx mov r14, rax mov ebx, 0x4bd600 add rbp, 0x10 jmp 0x49cf08 Main_main_closure = >>= $fMonadIO getArgs (\s3mc_info_arg_0 -> $ putStrLn ((\Main_a_info_arg_0 -> !!ERROR!!) (head s3mc_info_arg_0))

The results are a bit disappointing. It got as far as recognizing that the program is printing out some function of the input, but then it errored. How do we handle errors? We comment them out!

[https://github.com/Timeroot/hsdecomp/commit/a9244145d89019b2e8b0f45a9e23f5c043ec8155]

Basically forcing the decompiler to plow through broken stuff. (We also fix one incorrect assumption about jae being the only branch used in a certain type of case statement.) We definitely don’t get correct decompilation, but we get a lot more than before.

Main_main_closure = >>= $fMonadIO getArgs (\s3mc_info_arg_0 -> $ putStrLn ((\Main_a_info_arg_0 -> case == r3jo_info Main_a_info_arg_0 [] of c3uZ_info_case_tag_DEFAULT_arg_0@_DEFAULT -> zipWith (on (\s3m3_info_arg_0 s3m3_info_arg_1 s3m3_info_arg_2 s3m3_info_arg_3 s3m3_info_arg_4 -> . (\s3m1_info_arg_0 s3m1_info_arg_1 s3m1_info_arg_2 s3m1_info_arg_3 s3m1_info_arg_4 -> fmap $fFunctor-> chr) (\s3m2_info_arg_0 s3m2_info_arg_1 s3m2_info_arg_2 s3m2_info_arg_3 s3m2_info_arg_4 -> xor $fBitsInt)) ord) Main_a_info_arg_0 ((\Main_g_info_arg_0 Main_g_info_arg_1 -> case == r3jo_info Main_g_info_arg_0 [] of c3se_info_case_tag_DEFAULT_arg_0@_DEFAULT -> take (length $fFoldable[] Main_g_info_arg_0) (intercalate [] (map (\s3lV_info_arg_0 s3lV_info_arg_1 s3lV_info_arg_2 s3lV_info_arg_3 s3lV_info_arg_4 -> show $fShowInteger) (Main_v_info Main_g_info_arg_1 (length $fFoldable[] Main_g_info_arg_0) (S# 0)))) ) Main_a_info_arg_0 (S# 1997) ) ) (head s3mc_info_arg_0) ) ) r3jo_info = $fEq[] $fEqChar Main_v_info = \Main_v_info_arg_0 Main_v_info_arg_1 Main_v_info_arg_2 -> case == $fEqInteger Main_v_info_arg_0 (Main_r_info Main_v_info_arg_0) of c3qB_info_case_tag_DEFAULT_arg_0@_DEFAULT -> case >= $fOrdInteger Main_v_info_arg_2 (toInteger $fIntegralInt Main_v_info_arg_1) of c3qM_info_case_tag_DEFAULT_arg_0@_DEFAULT -> : Main_v_info_arg_0 (Main_v_info ((\Main_p_info_arg_0 -> + $fNumInteger Main_p_info_arg_0 (Main_r_info Main_p_info_arg_0)) Main_v_info_arg_0) Main_v_info_arg_1 (+ $fNumInteger Main_v_info_arg_2 (Main_mag_info Main_v_info_arg_0))) Main_mag_info = \Main_mag_info_arg_0 -> case == $fEqInteger Main_mag_info_arg_0 (S# 0) of c3mD_info_case_tag_DEFAULT_arg_0@_DEFAULT -> case > $fOrdInteger Main_mag_info_arg_0 (S# 0) of c3mI_info_case_tag_DEFAULT_arg_0@_DEFAULT -> case patError 4871050 Main_r_info = \Main_r_info_arg_0 -> case == $fEqInteger Main_r_info_arg_0 (S# 0) of c3oc_info_case_tag_DEFAULT_arg_0@_DEFAULT -> + $fNumInteger (* $fNumInteger (mod $fIntegralInteger Main_r_info_arg_0 (S# 10)) (^ $fNumInteger $fIntegralInteger (S# 10) (- $fNumInteger (Main_mag_info Main_r_info_arg_0) (S# 1)))) (Main_r_info (div $fIntegralInteger Main_r_info_arg_0 (S# 10)))

Even if you know Haskell, this is pretty unreadable, because

Everything is named very obtusely

Everything is pretty in prefix notation (e.g. + (f X) ((g h) Y)) instead of f X + g h Y)

A good chunk of code is missing.

We can’t fix the third part, but we can fix the first two, and use our pRoGraMmErs inTUiTioN to fill in the blanks for the third. Cleaned up:

Main_main_closure = >>= $fMonadIO getArgs (\ARGS -> $ putStrLn ((\ARG0 -> case (ARG0 == "") of __default -> zipWith (on (. (fmap $fFunctor-> chr) (xor $fBitsInt)) ord) HEAD ((\HEAD0 YY -> case (XX == "") of __default -> take (length HEAD0) (intercalate [] (map show (Function_V YY (length HEAD0) 0))) ) HEAD 1997 ) ) (head ARGS) ) ) String_Eq = $fEq[] $fEqChar -- Adds X to its digital reversal, repeatedly, in a loop -- Each time it adds the current number of digits in X to Z, a running counter (starts at 0) -- Continues until Z exceeds Y, the limit. Y is the length of HEAD0. Function_V X Y Z = case (X == (Function_R X)) of __default -> case (Z >= (toInteger Y)) of __default -> : X (Function_V ((X + (Function_R X))) Y (Z + (Function_mag X))) -- decompilation broke down here entirely -- but based on context, will guess it's the magnitude (Base 10) of A0. Function_mag A0 = case (A0 == 0) of __default -> case (A0 > 0) of __default -> case (A0 patError "lich_cipher.hs:(20,1)-(23,15)|function mag" -- returns R(X/10) + (X%10)*(10^mag(X)). -- this computes the _base 10 digit reversal_ of X. Function_R X = case (X == 0) of __default -> ( (X mod 10) * (10 ^ ((Function_mag X) - 1))) + (Function_R (X div 10))

So now the operation is pretty clear. It takes a number, 1997, and repeatedly adds it to its own base-10 reversal. It continues this until (a) it reaches a palindromic sum or (b) we have more terms than we have characters in our input string. This is what Function_V accomplishes, using Function_mag and Function_R as components.

Then intercalate [] (map show ...) turns these integers into strings and joins them. So for the sequence 1997 -> 1997 + 7991 = 9988 -> 9988 + 8899 = 18887 -> ..., we get the list ["1997", "9988", "18887", ...], and then the string "1997998818887".... The zipWith ... fmap structure is a bit obtuse, but we see xor, and HEAD (the input) and the digit string, so we can guess that it’s XORing the input with the magic digit string.

A quick trial of the program confirms this. Wow, so it’s just XORing the input with this magic string. Maybe I should have noticed that the program was its own inverse…? Nah.

So, we have encrypted text, and the program undoes itself. But we’re told the problem “has been changed very slightly” since it was first written. Two options: patch the program, or reimplement it. Patching it in IDA is easy, since searching for the bytes CD 07 (1997 in hex) turns it up right away. The relevant instruction is at 0x407C57 for those curious. I try a few different values (1997 is a year, right? So maybe 2020? 2019? 2000? 1996? 1998? Or maybe 2008, the year that the Lich King came out for WoW?) but none work, and it’s kind of slow doing this by patching it in IDA over and over.

So I reimplement the code to try a wide variety of seeds:

img = "./lich" fh = open('./cipher', 'rb') goal = bytearray(fh.read()) fh = open('./uncipher', 'rb') other = bytearray(fh.read()) def revDig(num): rev_num=0 while (num > 0): rev_num = rev_num*10 + num%10 num = num//10 return rev_num # Function to check whether the number is palindrome or not def isPalindrome(num): return (revDig(num) == num) def getPad(seed): res = "" while not isPalindrome(seed) and len(res) invParts = new Hashtable(); String[] classes = new String[]{"bv","cd","fg","gl","gq","gx","iy","mo","pr","qa","qg","vh","wz","xp","xq"}; char xorKey = new EncryptionKeyInstantiator().getEncryptionKeyFactory().getEncryptionKey(); for(String clazz : classes){ Class> clz = Class.forName(clazz); Object object = clz.getConstructors()[0].newInstance(); Method[] methods = clz.getDeclaredMethods(); for(Method m : methods){ try { String out = (String)m.invoke(object); String out2 = (String)clz.getDeclaredMethod(out).invoke(object); String out3 = (String)clz.getDeclaredMethod(out2).invoke(object); String in_enc = clazz + m.getName(); System.out.println(in_enc+" ~=> "+out3); char[] in_arr = in_enc.toCharArray(); for(int i=0;i "+out3); } catch(Exception e){ System.out.println(e); } } } String ans = ""; for(int i=0; i<goalstring.length i string bit="goalString.substring(i," bot="invParts.get(bit);" system.out.println> "+bot); ans += bot; } System.out.println(ans);

and then javac Main.java && java Main, we get Nice. Flag: rgbCTF{enterprisecodeee}.

Ralphie!

We’re given an image of a “decoder ring” of yore – but looking more closely, in the top left, is a QR code, with a variety of colors. Presumably we want something with just one color. So open it up in GIMP and play with the levels: go to “Curves”, and give the red channel a curve that is flat at 0 until the very very end. We’re left with a nice cyan QR code. Drop it in [https://zxing.org/w/decode.jspx] and we get a flag, rgbCTF{BESURETODRINKYOUROVALTINE}.

Sadistic Reversing 1

The program takes in a string and outputs an array of the style

[100, 93, 12, ... ]

and we want to find the input that matches the given output. Opening it up in IDA, the relevant strings show this is running on the Graal SubstrateVM, a toolchain for compiling Java to native code. (This theory is bolstered by the fact that invoking the program with no argument leads to a java.lang.ArrayIndexOutOfBoundsException). Reversing compiled SubstrateVM doesn’t sound like much fun, so can we blackbox this?

Some experimentation reveals that, like many simple ciphers (ahem, ARM2) the Nth character only depends on the input up to N. So we just try progressively longer things finding the right character by guessing at each step.

Solver script:

import subprocess import string import random img = "./itJX.so" goal = [114, 20, 119, 59, 104, 47, 75, 56, 81, 99, 23, 71, 56, 75, 124, 31, 65, 32, 77, 55, 103, 31, 96, 18, 76, 41, 27, 122, 29, 47, 83, 33, 78, 59, 10, 56, 15, 34, 94] query = '' matchingNow = 0 while True: sub = random.choice(string.printable) trial = query + sub result = subprocess.Popen([img, trial], universal_newlines=True, stdout=subprocess.PIPE) arr = eval(result.stdout.readlines()[0].strip()) matchingTrial = 0 if(arr == goal[0:len(arr)]): query = trial matchingNow = matchingTrial print("Built ",query)

After a couple seconds, Built rgbCTF{th1s_pr0bably_w@s_d1ff1cult6362}

Sadistic Reversing 2

This is a lot like Sadistic Reversing 1, but it seems that certain numbers of output depend on other ones elsewhere in the input – but still, the first byte of output is determined by just one thing, and the second byte is determined by two, and so on. Probably some loop of the form

long state = 0; for(int i=0; i<input.length i char next="input.charAt(" mystery1 result.append mystery2 state="mystery3(state,next);" so let blackbox this. since we not sure where have to change a byte in input get the right output just choose random place and hope it improves it. import subprocess string img="./itwk.so" goal="[117," query="rgbCTF{th1s_pr0bably_w@s_d1ff1cult6362_aaabbbcccd}" matchingnow="0" while true: flipper="random.randrange(0,len(query))" sub="random.choice(string.printable)" trial="query[0:flipper]" result="subprocess.Popen([img," universal_newlines="True," stdout="subprocess.PIPE)" arr="eval(result.stdout.readlines()[0].strip())" matchingtrial="0" if> matchingNow: query = trial matchingNow = matchingTrial print("Built ",query)

Takes about two minutes to run. (And what a shame I didn’t optimize it – we missed first blood by a matter of seconds!)

Secure RSA

We are given the following nonsense:

Secure RSA (SRSA) is a new, revolutionary way to encrypt your data that ensures the original message is unrecoverable by hackers. Top scientists from around the world have confirmed this mathematically irrefutable fact. 3 of our very own RGBSec members have developed this method, and we present it to you here. Granted, the method is very simple, and we aren't quite sure why nobody has thought of it before. Levying the power of uninjectivity, we set e to a small number. 0, in fact. Let's calculate the cipher now: (anything)^0 = 1. Since the message before encryption could have been any number in the world, the ciphertext is uncrackable by hackers. n: 69696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969 e: 0 c: 1

Well, yes, okay, there’s clearly no way to undo this encryption, but the flag data has to be somewhere – the flavortext then? We have a lot of flavortext. Looking at the first letters of each sentence:

ST3GL0LS

so the flag is rgbCTF{ST3GL0LS}.

Time Machine

The “time machine” here immediately hints a timing attack. Indeed, what does the binary do?

Generate a securely random password from the alphabet ABC...XYZ

Check user input against the password, one character at a time, returning as soon as it fails

Let the user try again, up to 250 times

If the user input matches, print out the flag.

The “one character at a time” part is what makes this vulnerable as a timing attack, as strings that match on longer prefixes take longer to check. This is over the network, so a few extra nanoseconds of checking would be totally unrecognizable, but the challenge server helpfully pauses for a whole second after each matching character. This makes the timing attack easy.

Solver script:

from socket import socket from telnetlib import Telnet import time allowed = "UVWXYZAFBCDQRSTGHIJNOPKLEM" sock = socket() sock.connect(('167.172.123.213', 13373)) #sock.connect(('localhost', 5555)) print("Header: ",sock.recv(1024)) print("Header2: ",sock.recv(1024)) known = "" for i in range(8): maxtime = 0 bestchar = "-" for trial in allowed: query = known + trial + "U"*(7-len(known)) print "Try ",query start = time.time() sock.send(query+'\n') result = sock.recv(1024) print("> " + result) result = sock.recv(1024) print("> " + result) end = time.time() tt = 1000*(end-start) print "Time = ",tt if(tt > maxtime): maxtime = tt bestchar = trial print "Keep ",bestchar known += bestchar print "Think it's ",known sock.send(known+'\n') result = sock.recv(1024) print("> " + result) t = Telnet() t.sock = sock t.interact() sock.close()

Too Slow

We’re given a binary which, we are told, will output the flag, albeit very slowly. The binary has two ffunctions: generate_key(), which returns an int32, and win(), which takes that int32 and generates the key. Figuring that generate_key() will probably be the slow part, let’s reverse that first. Hex-Rays gives

__int64 generate_key() { int v0; // eax __int64 v2; // [rsp-8h] [rbp-8h] __asm { endbr64 } for ( *((_DWORD *)&v2 - 2) = 0; *((_DWORD *)&v2 - 2) > (8*(i%4)))&0xFF); int aByte = (int)((a >> (8*i))&0xFF); int res = kByte ^ aByte; System.out.print((char)(res)); } } }

giving the flag rgbCTF{pr3d1ct4bl3_k3y_n33d5_no_w41t_cab79d}.

Ye Old PRNG

We are strongly suggested that this is an “old” PRNG. Googling for old random number generation implementations mostly brings up stuff about LCGs ([https://en.wikipedia.org/wiki/Linear_congruential_generator]) and LFSRs ([https://en.wikipedia.org/wiki/Linear_feedback_shift_register]), so we’re expecting one of those.

Connecting to the server, we can request numbers that are 3 to 100 digits long; it will then produce a sequence of random numbers for us. One of those first things to jump out is that each number appears to be entirely determined by the previous: in particular, when using 3 digits, “69” is always seen to generate “476”, and this appears to occur rather frequently.

Moving up to 100 digits numbers, it’s pretty clear that it’s not an LCG. An LCG is affine, so two inpurt numbers that are “a” apart lead to k*a difference in the results; from two (input,output) pairs we can determine what k is, and then check this against a third pair. It doesn’t work. It could be an LFSR but it’s not clear exactly how that would translate here. An LFSR generates a stream of bits, which would need to be converted to these integers. And as we noted, there doesn’t seem to be any hidden state.

Another big giveaway is that on the n=4 setting, we sometimes see loops like 4200 -> 6400 -> 9600 and so on, all ending with double zeros. There’s something base-10ish going on here.

A bit more digging on PRNGs brings us to [https://en.wikipedia.org/wiki/List_of_random_number_generators], where we see that the oldest one is the “middle square” algorithm. This fits perfectly: 69*69 = 4761 -> 476, and 4200*4200 = 17640000 -> 6400.