TJCTF 2023 Writeup

This page has been machine-translated from the original page.

I participated in TJCTF 2023, which started on 5/26, as part of 0nePadding.

We placed 71st out of 1,047 teams.

This time I got the chance to solve a Crypto challenge for the first time in a while, and it reminded me that I need to keep working on categories I’m weak at too.

As usual, I’ll write up the challenges that taught me something.

scramble(Rev)
wtmoo(Rev)
maybe(Rev)
div3rev(Rev)
dream(Rev)
neofeudalism(Forensic)
e(Crypto)
Summary

scramble(Rev)

oops, i think my siblings messed with the line order a little. The first three lines are given

The challenge provided the following Python script.

Running this code should recover the flag, but unfortunately every line after the third has been randomly shuffled, so it can no longer be executed correctly.

#first 3 lines are given
import random
seed = 1000
random.seed(seed)

#unscramble the rest
def recur(lst):
l2[i] = (l[i]*5+(l2[i]+n)*l[i])%l[i]
l2[i] += inp[i]
flag = ""
flag+=chr((l4[i]^l3[i]))
return flag
l.append(random.randint(6, 420))
l3[0] = l2[0]%mod
for i in range(1, n):
def decrypt(inp):
for i in range(n):
assert(len(l)==n)
return lst[0]
l = []
main()
def main():
l4 = [70, 123, 100, 53, 123, 58, 105, 109, 2, 108, 116, 21, 67, 69, 238, 47, 102, 110, 114, 84, 83, 68, 113, 72, 112, 54, 121, 104, 103, 41, 124]
l3[i] = (l2[i]^((l[i]&l3[i-1]+(l3[i-1]*l[i])%mod)//2))%mod
if(len(lst)==1):
assert(lst[0]>0)
for i in range(1, n):
for i in range(n):
return recur(lst[::2])/recur(lst[1::2])
print("flag is:", decrypt(inp))
l2[0] +=int(recur(l2[1:])*50)
l2 = [0]*n
flag_length = 31
mod = 256
print(l2)
n = len(inp)
inp = [1]*flag_length
l3 =[0]*n

First, I inferred the scope of each line from its variable names and organized them into the code for each function.

I then rearranged the lines within each function so that the logic behaved as intended.

The final code looked like this, and running it recovered the flag.

import random
seed = 1000
random.seed(seed)

def recur(lst):
    if(len(lst)==1):
        assert(lst[0]>0)
        return lst[0]
    return recur(lst[::2])/recur(lst[1::2])

def decrypt(inp):
    mod = 256
    n = len(inp)
    l = []

    for i in range(n):
        l.append(random.randint(6, 420))
    assert(len(l)==n)

    l2 = [0]*n
    l3 =[0]*n
    l4 = [70, 123, 100, 53, 123, 58, 105, 109, 2, 108, 116, 21, 67, 69, 238, 47, 102, 110, 114, 84, 83, 68, 113, 72, 112, 54, 121, 104, 103, 41, 124]

    for i in range(1, n):
        l2[i] = (l[i]*5+(l2[i]+n)*l[i])%l[i]
        l2[i] += inp[i]

    print(l2)
    
    l2[0] += int(recur(l2[1:])*50)
    l3[0] = l2[0]%mod

    for i in range(1, n):
        l3[i] = (l2[i]^((l[i]&l3[i-1]+(l3[i-1]*l[i])%mod)//2))%mod

    flag = ""
    for i in range(n):
        flag+=chr((l4[i]^l3[i]))

    return flag
    
def main():
    flag_length = 31
    inp = [1]*flag_length
    print("flag is:", decrypt(inp))

main()

wtmoo(Rev)

My cow keeps eating all my flags…

When I ran the provided ELF and entered an arbitrary string, it printed the result of some transformation as shown below.

I located the relevant transformation in Ghidra’s decompilation and cleaned it up, which showed that it was implemented as follows.

if ((input[i] < 'a') || ('z' < input[i])) {
    if ((input[i] < 'A') || ('Z' < input[i])) {
    if ((input[i] < '0') || ('4' < input[i])) {
        if ((input[i] < '5') || ('9' < input[i])) {
        if ((input[i] != '{') && (input[i] != '}')) {
            puts("wtmoo is this guess???");
            printf("%c\n",(ulong)(uint)(int)input[i]);
            uVar3 = 1;
            goto LAB_00401427;
        }
        }
        else {
        input[i] = input[i] + -0x15;
        }
    }
    else {
        input[i] = input[i] + '+';
    }
    }
    else {
    input[i] = input[i] + ' ';
    }
}
else {
    input[i] = input[i] + -0x3c;
}
i = i + 1;
} while( true );

I also found that if the transformed input ultimately matches "8.\'8*{;8m33[o[3[3[%\")#*\\}", the program prints the correct flag.

This transformation is applied to the input one character at a time, and there is no swapping between characters, so I could brute-force from the beginning with the following solver script to recover every character of the flag.

ans = "8.\'8*{;8m33[o[3[3[%\")#*\\}"

for i in range(len(ans)):
    for c in range(256):
        if (c < ord("a")) or (ord("z") < c):
            if (c < ord("A")) or (ord("Z") < c):
                if (c < ord("0")) or (ord("4") < c):
                    if (c < ord("5")) or (ord("9") < c):
                        if chr(c) == "{" or chr(c) == "}":
                            print(chr(c),end="")
                            break
                    else:
                        if chr(c-0x15) == ans[i]:
                            print(chr(c),end="")
                            break
                else:
                    if chr(c+0x2b) == ans[i]:
                        print(chr(c),end="")
                        break            
            else:
                if chr(c+0x20) == ans[i]:
                    print(chr(c),end="")
                    break
        else:
            if chr(c-0x3c) == ans[i]:
                print(chr(c),end="")
                break

After entering the recovered flag characters, the program printed the correct flag as shown below.

maybe(Rev)

is this an easy rev challenge?? maybe … just maybe …

Analyzing the provided ELF in Ghidra showed that it compares the input string with a byte sequence embedded in the binary using the expression (array[i] ^ array[i + -4]) != flag[i + -4].

Since the first six characters of the flag are known to be tjctf{, I wrote the following solver and reversed the process to recover the flag.

flag_arr = [ 0x12, 0x11, 0x00, 0x15, 0x0b, 0x48, 0x3c, 0x12, 0x0c, 0x44, 0x00, 0x10, 0x51, 0x19, 0x2e, 0x16, 0x03, 0x1c, 0x42, 0x11, 0x0a, 0x4a, 0x72, 0x56, 0x0d, 0x7a, 0x74, 0x4f, 0x00 ]
tmp = [0] * 0x21
for i,c in enumerate("tjctf{"):
    tmp[i] = ord(c)

# (array[i] ^ array[i + -4]) != flag[i + -4]
for i in range(4,0x21):
    for x in range(256):
        if tmp[i-4] ^ x == flag_arr[i-4]:
            tmp[i] = x
            print(chr(x), end="")
            break

# tjctf{cam3_saw_c0nqu3r3d98A24B5}

div3rev(Rev)

divide and conquer?

The challenge provided the following Python script.

For this CTF, a surprisingly large number of the Rev challenges involved recursive functions in Python.

def op1(b):
    for i in range(len(b)):
        b[i] += 8*(((b[i] % 10)*b[i]+75) & 1)
        cur = 1
        for j in range(420):
            cur *= (b[i]+j) % 420
    return b


def op2(b):
    for i in range(len(b)):
        for j in range(100):
            b[i] = b[i] ^ 69
        b[i] += 12
    return b


def op3(b):
    for i in range(len(b)):
        b[i] = ((b[i] % 2) << 7)+(b[i]//2)
    return b


def recur(b):
    if len(b) == 1:
        return b
    assert len(b) % 3 == 0
    a = len(b)
    return op1(recur(b[0:a//3]))+op2(recur(b[a//3:2*a//3]))+op3(recur(b[2*a//3:]))


flag = open("flag.txt", "r").read()
flag = flag[:-1]
b = bytearray()
b.extend(map(ord, flag))
res = recur(b)
if res == b'\x8c\x86\xb1\x90\x86\xc9=\xbe\x9b\x80\x87\xca\x86\x8dKJ\xc4e?\xbc\xdbC\xbe!Y \xaf':
    print("correct")
else:
    print("oopsies")

Reading the code shows that applying the recursive recur() function to the correct flag string yields the byte string res.

The implementation of recur() splits the given byte string into three parts and passes them to op1, op2, and op3 respectively.

If the byte string has only one element, it simply returns that value.

I initially got stuck trying to invert each op function, but a closer look showed that each specific flag element is always processed in the same way, and no swapping occurs between byte positions.

Therefore, by using only the correct flag length and brute-forcing characters from the beginning so that the final output matched, I was able to recover the flag.

In the end, I recovered the flag with the following solver.

ans = b'\x8c\x86\xb1\x90\x86\xc9=\xbe\x9b\x80\x87\xca\x86\x8dKJ\xc4e?\xbc\xdbC\xbe!Y \xaf'
flag = ["0"]*len(ans)
for i in range(len(ans)):
    for x in range(256):
        flag[i] = chr(x)
        b = "".join(flag)
        b = bytearray()
        b.extend(map(ord, flag))
        res = recur(b)
        # print(chr(x), res[i], ans[i])
        if res[i] == ans[i]:
            print(chr(x),end="")
            break

dream(Rev)

A fever dream, truly. nc tjc.tf 31500

Decompiling the provided ELF in Ghidra yields the following code.

undefined8 main(void)

{
  int iVar1;
  ulong uVar2;
  ulong uVar3;
  FILE *__stream;
  long in_FS_OFFSET;
  int x;
  int i;
  char input [256];
  char local_118 [264];
  long local_10;
  
  local_10 = *(long *)(in_FS_OFFSET + 0x28);
  setbuf(stdout,(char *)0x0);
  type_text("last night, I had a dream...\ntaylor sw1ft, the dollar store version, appeared!\n");
  prompt("what should I do? ",input,0x100);
  iVar1 = strcmp("sing",input);
  if (iVar1 != 0) {
    puts("no, no, that\'s a bad idea.");
                    /* WARNING: Subroutine does not return */
    exit(0);
  }
  prompt("that\'s a great idea!\nI started to sing the following lyrics: ",input,0x100);
  iVar1 = strcmp("maybe I asked for too [many challenges to be written]",input);
  if (iVar1 != 0) {
    puts("no, that\'s a dumb lyric.");
                    /* WARNING: Subroutine does not return */
    exit(0);
  }
  type_text("ok... that\'s a weird lyric but whatever\n");
  prompt("that leads me to ask... how many challenges did you ask for??? ",input,0x100);
  uVar2 = atol(input);
  if ((((uVar2 * 3 ^ 0xb6d8) % 0x521) * 0x23) % 0x5eb != 0x55a) {
    type_text("that\'s a stupid number.\n");
                    /* WARNING: Subroutine does not return */
    exit(0);
  }
  prompt("ok yeah you\'re asking too much of everyone; try to lower the number??? ",input,0x100);
  uVar3 = atol(input);
  if ((((uVar3 * 5) % 0x1e61 | 0x457) * 0x23 - 5) % 1000 != 0x50) {
    type_text("yeah.");
                    /* WARNING: Subroutine does not return */
    exit(0);
  }
  if ((uVar2 % uVar3 != 0x1344224) || (uVar2 * uVar3 != 0x33d5d816326aad)) {
    type_text("ok but they might think that\'s too much comparatively, duh.\n");
                    /* WARNING: Subroutine does not return */
    exit(0);
  }
  type_text("that\'s a lot more reasonable - good on you!\n");
  usleep(75000);
  type_text("ok, now that we\'ve got that out of the way, back to the story...\n");
  type_text("taylor was like, \"wow, you\'re so cool!\", and I said, \"no, you\'re so cool!\"\n");
  type_text(
           "after that, we kinda just sat in silence for a little bit. I could kinda tell I was losi ng her attention, so "
           );
  x = 0;
  for (i = 0; i < 0xc; i = i + 1) {
    prompt("what should I do next? ",input,0x100);
    iVar1 = strcmp("ask her about some flags",input);
    if (iVar1 == 0) {
      x = x + 1;
    }
    else {
      iVar1 = strcmp("ask her about her new album",input);
      if (iVar1 == 0) {
        x = x * x;
      }
      else {
        iVar1 = strcmp("ask her about her tour",input);
        if (iVar1 != 0) {
          type_text("no, that\'s weird\n");
                    /* WARNING: Subroutine does not return */
          exit(0);
        }
        x = x + 0x16;
      }
    }
  }
  if (x != 0x92f) {
    type_text("taylor died of boredom\n");
                    /* WARNING: Subroutine does not return */
    exit(0);
  }
  type_text(
           "taylor got sick and tired of me asking her about various topics, so she finally responde d: "
           );
  __stream = fopen("flag.txt","r");
  if (__stream == (FILE *)0x0) {
    type_text("no flag </3\n");
                    /* WARNING: Subroutine does not return */
    exit(0);
  }
  fgets(local_118,0x100,__stream);
  type_text(local_118);
  if (local_10 != *(long *)(in_FS_OFFSET + 0x28)) {
                    /* WARNING: Subroutine does not return */
    __stack_chk_fail();
  }
  return 0;
}

From this code, we can see that the binary accepts multiple inputs in sequence and only returns the flag if every check succeeds.

The first two checks are simple string comparisons, so you can pass them by sending the following embedded strings in order.

sing
maybe I asked for too [many challenges to be written]

The next checks were implemented as follows.

prompt("that leads me to ask... how many challenges did you ask for??? ",input,0x100);
uVar2 = atol(input);
if ((((uVar2 * 3 ^ 0xb6d8) % 0x521) * 0x23) % 0x5eb != 0x55a) {
type_text("that\'s a stupid number.\n");
                /* WARNING: Subroutine does not return */
exit(0);
}
prompt("ok yeah you\'re asking too much of everyone; try to lower the number??? ",input,0x100);
uVar3 = atol(input);
if ((((uVar3 * 5) % 0x1e61 | 0x457) * 0x23 - 5) % 1000 != 0x50) {
type_text("yeah.");
                /* WARNING: Subroutine does not return */
exit(0);
}
if ((uVar2 % uVar3 != 0x1344224) || (uVar2 * uVar3 != 0x33d5d816326aad)) {
type_text("ok but they might think that\'s too much comparatively, duh.\n");
                /* WARNING: Subroutine does not return */
exit(0);
}

More specifically, we need to find uVar2 and uVar3 that satisfy all three of the following conditions.

1. (((uVar2 * 3 ^ 0xb6d8) % 0x521) * 0x23) % 0x5eb != 0x55a
2. ((((uVar3 * 5) % 0x1e61 | 0x457) * 0x23 - 5) % 1000 != 0x50)
3. ((uVar2 % uVar3 != 0x1344224) || (uVar2 * uVar3 != 0x33d5d816326aad)

Values satisfying the first two conditions can be found easily by brute force, but brute-forcing values that satisfy the third condition is computationally impractical.

So, based on the prime factorization of 0x33d5d816326aad (3*3*29*37*409*11071*333667), I first generated pairs of values satisfying uVar2 * uVar3 == 0x33d5d816326aad and then checked whether they also satisfied conditions 1 and 2.

In the end, the following solver identified uVar2 and uVar3 satisfying all three conditions.

# 0x33D5D816326AAD = 3*3*29*37*409*11071*333667
import itertools
primes = [3,3,29,37,409,11071,333667]
p = set(primes)
check = []
for i in range(1, len(primes)):
    comb = itertools.combinations(primes, i)
    for c in comb:
        a = 1
        b = 1
        for x in p.difference(c):
            a *= x
        for y in c:
            b *= y
        if a*b == 0x33D5D816326AAD:
            # print(a,b)
            check.append((a,b))

for t in check:
    a = t[0]
    b = t[1]
    if (((a * 3 ^ 0xb6d8) % 0x521) * 0x23) % 0x5eb == 0x55a:
        if (35 * ((5 * b % 0x1E61) | 0x457) - 5) % 0x3E8 == 80:
            print(a,b)

    a = t[1]
    b = t[0]
    if (((a * 3 ^ 0xb6d8) % 0x521) * 0x23) % 0x5eb == 0x55a:
        if (35 * ((5 * b % 0x1E61) | 0x457) - 5) % 0x3E8 == 80:
            print(a,b)

In the final check, the program updates x depending on whether the input string is ask her about some flags, ask her about her new album, or ask her about her tour, and verifies that the final result becomes 0x92f.

x = 0;
for (i = 0; i < 0xc; i = i + 1) {
prompt("what should I do next? ",input,0x100);
iVar1 = strcmp("ask her about some flags",input);
if (iVar1 == 0) {
  x = x + 1;
}
else {
  iVar1 = strcmp("ask her about her new album",input);
  if (iVar1 == 0) {
    x = x * x;
  }
  else {
    iVar1 = strcmp("ask her about her tour",input);
    if (iVar1 != 0) {
      type_text("no, that\'s weird\n");
                /* WARNING: Subroutine does not return */
      exit(0);
    }
    x = x + 0x16;
  }
}
}
if (x != 0x92f) {
type_text("taylor died of boredom\n");
                /* WARNING: Subroutine does not return */
exit(0);
}

However, the number of times you can enter a string is limited to 0xc, so I needed to find the shortest valid sequence of inputs.

Finding the shortest input sequence itself was not particularly difficult; I worked it out using a greedy approach and a calculator.

The final input sequence was as follows.

sing
maybe I asked for too [many challenges to be written]
131313131
111111111
ask her about her tour
ask her about her tour
ask her about some flags
ask her about some flags
ask her about some flags
ask her about some flags
ask her about her new album
ask her about her tour
ask her about her tour
ask her about some flags
ask her about some flags
ask her about some flags

Sending this to the remote server returned the flag.

neofeudalism(Forensic)

One of my friends has gotten into neo-feudalism recently. He says that society should be more like a feudalist one, with unequal rights, legal protections, and wealth distribution.

I found this weird photo on his computer; can you find a flag?

The challenge provided the following PNG file.

Since it was a PNG file, I analyzed it with zsteg and recovered the flag embedded in the file.

zsteg -a image.png

Reference: Stego Tricks - HackTricks

e(Crypto)

smol e

The provided challenge files were the following Sage file and text file.

from Crypto.Util.number import bytes_to_long

p = random_prime(2 ^ 650)
q = random_prime(2 ^ 650)
N = p*q
e = 5
flag = open("flag.txt", "rb").read().strip()
m = bytes_to_long(b'the challenges flag is ' + flag)
c = m ^ e % N
print("N: ", N)
print("C: ", c)
print("e: ", e)

N:  853008036761402960429244085500226305898326229049062709229066738337581395441559298620215547481097485360068401045559533084692445386310317304293873811639421668853703030998563380404046228010704173349786419154143323587451196441095743638783569173579503503557413613700490069592150975220823978641111437607374483116682547794651693986279540940965888470663234601045413512056249535670198419685119952947
C:  298700332507654723773580072855784292117810966958600234446114828082727445272393622869719877676272804981941548843479760604983256960593285221389548684954375981617049731866256547635842115184695147132731165168615990125469633018271766466825307769730709868985624843944432541800012321786587028293887532995722347604510229248766961319729482167555605707032678858635163105035385522888663577785577519392
e:  5

It appears to encrypt the flag using RSA.

Since e is very small, I first thought a Low Public Exponent Attack might work, but unfortunately the condition M**e < N is not satisfied, so it cannot be decrypted that way.

However, reading the Sage file used for encryption shows that the first 23 characters of the plaintext are hardcoded.

One attack against RSA is Coppersmith’s short-pad attack, which works when the difference between two plaintexts is sufficiently small. In this case, there also seems to be a technique called the stereotyped message attack, which applies Coppersmith’s method when the high-order bits of the plaintext are known and e is very small.

Reference: Security Camp 2021 Participation Report - Qiita

Reference: RSA Attack: Stereotyped message attack | gsdt

This challenge also satisfied those conditions, so I reused part of the code from the reference article, ran the following solver script in SageMath, and recovered the flag from the decrypted result.

# partial_m.sage
n=853008036761402960429244085500226305898326229049062709229066738337581395441559298620215547481097485360068401045559533084692445386310317304293873811639421668853703030998563380404046228010704173349786419154143323587451196441095743638783569173579503503557413613700490069592150975220823978641111437607374483116682547794651693986279540940965888470663234601045413512056249535670198419685119952947
c=298700332507654723773580072855784292117810966958600234446114828082727445272393622869719877676272804981941548843479760604983256960593285221389548684954375981617049731866256547635842115184695147132731165168615990125469633018271766466825307769730709868985624843944432541800012321786587028293887532995722347604510229248766961319729482167555605707032678858635163105035385522888663577785577519392
e=5

prefix=11149651487439933873850349163109051510832664011661210400
PR.<x> = PolynomialRing(Zmod(n))
for i in range(1,2000):
    p = prefix << i
    f = (p + x)^e - c
    diff = f.small_roots(epsilon=1/30)
    if len(diff):
        print(diff)
        break

Summary

This time I solved one Crypto challenge for the first time in quite a while—really quite a while.

I’m still not very comfortable with Crypto, but algorithms like AES show up often in Rev as well, so I feel I really need to study it properly.

Published May 29, 2023

Aspiring Reverse Engineer and CTF Player (Team: 0nePadding). Passionate about WinDbg and Anti-Virus internals. OSCP / CISSP. Working at Microsoft Japan, but all views expressed are my own.かしわば(@kash1064) on Twitter