TJCTF 2023 Writeup

5/26 から開催されていた TJCTF 2023 に 0nePadding として参加していました。

最終順位は 71 位 /1047 チームでした。

今回は久しぶりに Crypto 問を解く機会があり、苦手ジャンルの問題もある程度やっていかないとなと思いました。

いつも通り、学びのあった問題について Writeup を書きます。

scramble(Rev)

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

問題バイナリとして以下のような Python スクリプトのコードが与えられました。

このコードを実行すると Flag が取得できるようですが、残念ながら 4 行目以降のコードがランダムにシャッフルされてしまっており、正しく実行することができなくなっているようです。

#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

まず、各行の変数名からスコープを特定し、それぞれの関数内のコードとして整理しました。

その後、各関数内の処理が意図した動作になるように各コードを並び替えました。

最終的に以下のようなコードとなり、これを実行することで 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…

問題バイナリとして与えられた ELF を実行し、適当な文字列を入力すると、以下のように何らかの変換を行った結果が出力されました。

Ghidra でデコンパイルした結果からこの変換箇所を特定して整形したところ、以下のような処理で実装されていることがわかりました。

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 );

また、上記の処理で変換した入力値が、最終的に"8.\'8*{;8m33[o[3[3[%\")#*\\}"と一致した場合に正しい Flag が出力されることもわかりました。

この変換処理は入力された文字列に対して 1 文字ずつ行っており、文字の swap も発生していないため、以下の Solver スクリプトで先頭からブルートフォースすることですべての 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

実際に特定した Flag 文字を入力したところ、以下のように正しい Flag が出力されました。

maybe(Rev)

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

問題バイナリとして与えられた ELF を Ghidra で解析すると入力された文字列と、バイナリに埋め込まれたバイト列を(array[i] ^ array[i + -4]) != flag[i + -4]という処理で比較していることがわかりました。

Flag 文字列の先頭 6 文字まではtjctf{と一致することがわかっているので、以下の Solver を作成して処理を逆算することで 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?

問題バイナリとして以下の Python スクリプトが与えられました。

今回の CTF の Rev 問はやたら 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")

上記のコードを読むと、どうやら正しい Flag の文字列に対して recur() 関数で再帰処理を実行した結果が res のバイト列と一致することがわかります。

recur() 関数の実装を読むと、与えられたバイト列を 3 分割して、それぞれ op1,op2,op3 の関数に渡す処理を行っています。

また、バイト列の要素数が 1 の場合には、その値をそのまま return します。

各 op 関数の処理を逆算させようとして少々ハマりましたが、よく実装を見てみると Flag 文字列の特定の要素に対して行われる処理は毎回同じであり、バイト列間の swap も発生しないことがわかりました。

そのため、Flag と文字数だけ合わせつつ、最終的な出力結果が一致するように先頭から順にブルートフォースを行うことで Flag を特定できることがわかりました。

最終的に以下の Solver で Flag を取得できました。

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

問題バイナリとして与えられた ELF を Ghidra でデコンパイルすると以下のようなデコンパイルコードを得られます。

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;
}

このコードから、問題バイナリは順番に複数の入力値を受けとり、すべての入力値の検証に成功した場合にのみ Flag を返すことがわかります。

最初の 2 つの検証はシンプルに文字列一致を比較するものでしたので、バイナリに埋め込まれた以下の文字列を順に送信することでパスできます。

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

続いての検証は以下のように実装されていました。

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);
}

具体的には、以下の 3 つの式をすべて満たす uVar2 と uVar3 を特定する必要があります。

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

最初の 2 つの式を満たす値はブルートフォースで簡単に特定できますが、残念ながら 3 番目の式を満たす値をブルートフォースで特定することは計算量的に困難でした。

そのため、0x33d5d816326aad を素因数分解した結果(3*3*29*37*409*11071*333667)をもとに、uVar2 * uVar3 == 0x33d5d816326aadを満たす 2 つの値の組み合わせを先に作成しておき、それらが 1 と 2 の式を満たすか検証する方針としました。

最終的に以下の Solver で 3 つの式すべてを満たす uVar2 と uVar3 を特定できました。

# 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)

最後の検証では、入力された文字列がask her about some flagsかask her about her new album、またはask her about her tourのいずれであるかによって x に対して演算を行い、最終的な結果が 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);
}

ただし、文字列を入力できる回数は 0xc 回に制限されているため、最短の入力値を特定する必要がありました。

最短の入力値の特定自体は特に難しくなく、貪欲法と電卓を使って計算することで特定できました。

最終的な入力値は以下のようになりました。

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

これをリモートサーバに送信することで 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?

問題バイナリとして以下のような PNG ファイルが与えられます。

PNG ファイルなので zsteg を使って解析したところ、ファイルに埋め込まれた Flag を取得できました。

zsteg -a image.png

参考：Stego Tricks - HackTricks

e(Crypto)

smol e

問題バイナリとして与えられた sage ファイルとテキストファイルは以下の通りでした。

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

RSA 暗号を使用して Flag を暗号化しているようです。

e が非常に小さいため Low Public Exponet Attack が使えるかと思いましたが、残念ながらM**e < Nの条件を満たさず、復号できません。

しかし、暗号化を行っている sage ファイルを読むと、暗号化テキストの先頭 23 文字が平文で埋め込まれていました。

RSA に対する攻撃手法として、2 つの平文の差が十分に小さい場合に利用できる Coppersmith’s short-pad 攻撃がありますが、「平文の上位 bit が特定されており、かつ e が非常に小さい場合」に Coppersmith’s method を応用して暗号化を解除できる Stereotyped message 攻撃という手法があるようです。

参考：セキュリティキャンプ2021 参加記 - Qiita

参考：RSA Attack: Stereotyped message attack | gsdt

今回も上記の条件をみたすため、参考記事のコードを一部転用した以下の Solver スクリプトを SageMath で実行し、復号結果から Flag を取得することができました。

# 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

まとめ

今回は久しぶりに(本当に久しぶりに) Crypto の問題を 1 問解きました。

Crypto には苦手意識がありますが、特に AES などは Rev でもよく使うのでちゃんと勉強しておかないといけないなと思います。

Published May 29, 2023

リバースエンジニアになりたいCTF Player(Team: 0nePadding)。WinDbgとYARAが好き。OSCP / CISSP / AtCoder 緑 Microsoft Japanに所属してます。発言はすべて個人の見解。かしわば on Twitter