satto1237’s diary

s4tt01237’s diary

ラーメンとかCTFとかセキュリティとか

TokyoWesterns CTF 5th 2019 Write-up

CTF セキュリティ

はじめに

2019/08/31 ~ 2019/09/02に開催されたTokyoWesterns CTF 5th 2019にチーム(NekochanNano!)で参加しました．

成績

チームとしては6問解いて107位でした (1005チーム中)．
今回は自分が解いた2問のWrite-upを書きます．

f:id:satto1237:20190902160154p:plain

Easy Crack Me [Rev, 88pts, 185solved]

Cracking is easy for you.

> file easy_crack_me
easy_crack_me: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 3.2.0, BuildID[sha1]=7e80b79602fcfd8121e9f4d9d26bb01a81f4afe5, stripped
> ./easy_crack_me 
./bin flag_is_here
> ./easy_crack_me flag
incorrect

アプローチ：Ghidraでデコンパイル + 気合で解読 + 制約条件に基づいて全探索

とりあえずidaで開いてみますが，これを静的解析するのはしんどいなという気持ちになり，すぐに方針をangrに切り替えました．

f:id:satto1237:20190902164721p:plain

しかし，上手くいきませんでした…(終)

f:id:satto1237:20190902193835p:plain

以下が上手く行かなかったangrソルバです．
問題点があれば教えてほしいです．
(strchrのせいなのか？)

import angr

length = 0x27

p = angr.Project('./easy_crack_me')
flag = claripy.BVS('flag', length*8)
state = p.factory.entry_state(args=[p.filename, flag])

for i, x in enumerate(flag.chop(8)):
    if i < 6:
        state.add_constraints(x == b'TWCTF{'[i])
    elif i == 0x25:
        state.add_constraints(x == b'5')
    elif i == 7:
        state.add_constraints(x == b'f')
    elif i == 0xb:
        state.add_constraints(x == b'8')
    elif i == 0xc:
        state.add_constraints(x == b'7')
    elif i == 0x17:
        state.add_constraints(x == b'2')
    elif i == 0x1f:
        state.add_constraints(x == b'4')
    elif i == 0x26:
        state.add_constraints(x == b'}')
    else:
        state.add_constraints(x >= b' ')
        state.add_constraints(x <= b'~')

simgr = p.factory.simulation_manager(state)

simgr.explore(find=0x400e10, avoid=[0x400777,0x400dfc])

try:
    simstate = simgr.found[0]
    print(simstate.posix.dumps(1))
    print(simstate.solver.eval(flag, cast_to=bytes))
except Exception as e:
    print(e)

angrで解けなかったので再度方針を静的解析に切り替えました．

まずはmain関数をGhidraでデコンパイルしてソースコードを解析していきます．

undefined8 FUN_00400747(int iParm1,long lParm2)

{
  char cVar1;
  char *__s;
  int iVar2;
  undefined8 uVar3;
  size_t sVar4;
  char *pcVar5;
  long lVar6;
  undefined8 *puVar7;
  long in_FS_OFFSET;
  byte bVar8;
  int local_1b8;
  int local_1b4;
  int local_1b0;
  uint local_1ac;
  int local_1a8;
  int local_1a4;
  int local_1a0;
  uint local_19c;
  int local_198;
  int local_194;
  int local_190;
  int local_18c;
  char *local_188;
  undefined8 local_168;
  undefined8 local_160;
  undefined8 local_158;
  undefined8 local_150;
  undefined8 local_148;
  undefined8 local_140;
  undefined8 local_138;
  undefined8 local_130;
  undefined8 local_128;
  undefined8 local_120;
  undefined8 local_118;
  undefined8 local_110;
  undefined8 local_108;
  undefined8 local_100;
  undefined8 local_f8;
  undefined8 local_f0;
  undefined8 local_e8;
  undefined8 local_e0;
  undefined8 local_d8;
  undefined8 local_d0;
  undefined8 local_c8;
  undefined8 local_c0;
  undefined8 local_b8;
  undefined8 local_b0;
  undefined8 local_a8 [16];
  undefined8 local_28;
  undefined8 local_20;
  long local_10;

  bVar8 = 0;
  local_10 = *(long *)(in_FS_OFFSET + 0x28);
  if (iParm1 == 2) {
    __s = *(char **)(lParm2 + 8);
    sVar4 = strlen(__s);
    if (sVar4 != 0x27) {
      puts("incorrect");
                    /* WARNING: Subroutine does not return */
      exit(0);
    }
    iVar2 = memcmp(__s,"TWCTF{",6);
    if ((iVar2 != 0) || (__s[0x26] != '}')) {
      puts("incorrect");
                    /* WARNING: Subroutine does not return */
      exit(0);
    }
    local_e8 = 0;
    local_e0 = 0;
    local_d8 = 0;
    local_d0 = 0;
    local_c8 = 0;
    local_c0 = 0;
    local_b8 = 0;
    local_b0 = 0;
    local_28 = 0x3736353433323130;
    local_20 = 0x6665646362613938;
    local_1b8 = 0;
    while (local_188 = __s, local_1b8 < 0x10) {
      while (pcVar5 = strchr(local_188,(int)*(char *)((long)&local_28 + (long)local_1b8)),
            pcVar5 != (char *)0x0) {
        *(int *)((long)&local_e8 + (long)local_1b8 * 4) =
             *(int *)((long)&local_e8 + (long)local_1b8 * 4) + 1;
        local_188 = pcVar5 + 1;
      }
      local_1b8 = local_1b8 + 1;
    }
    iVar2 = memcmp(&local_e8,&DAT_00400f00,0x40);
    if (iVar2 != 0) {
      puts("incorrect");
                    /* WARNING: Subroutine does not return */
      exit(0);
    }
    local_168 = 0;
    local_160 = 0;
    local_158 = 0;
    local_150 = 0;
    local_148 = 0;
    local_140 = 0;
    local_138 = 0;
    local_130 = 0;
    local_1b4 = 0;
    while (local_1b4 < 8) {
      local_1b0 = 0;
      local_1ac = 0;
      local_1a8 = 0;
      while (local_1a8 < 4) {
        local_1b0 = local_1b0 + (int)__s[(long)local_1a8 + (long)(local_1b4 << 2) + 6];
        local_1ac = local_1ac ^ (int)__s[(long)local_1a8 + (long)(local_1b4 << 2) + 6];
        local_1a8 = local_1a8 + 1;
      }
      *(int *)((long)&local_168 + (long)local_1b4 * 4) = local_1b0;
      *(uint *)((long)&local_148 + (long)local_1b4 * 4) = local_1ac;
      local_1b4 = local_1b4 + 1;
    }
    local_128 = 0;
    local_120 = 0;
    local_118 = 0;
    local_110 = 0;
    local_108 = 0;
    local_100 = 0;
    local_f8 = 0;
    local_f0 = 0;
    local_1a4 = 0;
    while (local_1a4 < 8) {
      local_1a0 = 0;
      local_19c = 0;
      local_198 = 0;
      while (local_198 < 4) {
        local_1a0 = local_1a0 + (int)__s[(long)(local_198 << 3) + (long)local_1a4 + 6];
        local_19c = local_19c ^ (int)__s[(long)(local_198 << 3) + (long)local_1a4 + 6];
        local_198 = local_198 + 1;
      }
      *(int *)((long)&local_128 + (long)local_1a4 * 4) = local_1a0;
      *(uint *)((long)&local_108 + (long)local_1a4 * 4) = local_19c;
      local_1a4 = local_1a4 + 1;
    }
    iVar2 = memcmp(&local_168,&DAT_00400f40,0x20);
    if ((iVar2 != 0) || (iVar2 = memcmp(&local_148,&DAT_00400f60,0x20), iVar2 != 0)) {
      puts("incorrect");
                    /* WARNING: Subroutine does not return */
      exit(0);
    }
    iVar2 = memcmp(&local_128,&DAT_00400fa0,0x20);
    if ((iVar2 != 0) || (iVar2 = memcmp(&local_108,&DAT_00400f80,0x20), iVar2 != 0)) {
      puts("incorrect");
                    /* WARNING: Subroutine does not return */
      exit(0);
    }
    lVar6 = 0x10;
    puVar7 = local_a8;
    while (lVar6 != 0) {
      lVar6 = lVar6 + -1;
      *puVar7 = 0;
      puVar7 = puVar7 + (ulong)bVar8 * 0x1ffffffffffffffe + 1;
    }
    local_194 = 0;
    while (local_194 < 0x20) {
      cVar1 = __s[(long)local_194 + 6];
      if ((cVar1 < '0') || ('9' < cVar1)) {
        if ((cVar1 < 'a') || ('f' < cVar1)) {
          *(undefined4 *)((long)local_a8 + (long)local_194 * 4) = 0;
        }
        else {
          *(undefined4 *)((long)local_a8 + (long)local_194 * 4) = 0x80;
        }
      }
      else {
        *(undefined4 *)((long)local_a8 + (long)local_194 * 4) = 0xff;
      }
      local_194 = local_194 + 1;
    }
    iVar2 = memcmp(local_a8,&DAT_00400fc0,0x80);
    if (iVar2 != 0) {
      puts("incorrect");
                    /* WARNING: Subroutine does not return */
      exit(0);
    }
    local_190 = 0;
    local_18c = 0;
    while (local_18c < 0x10) {
      local_190 = local_190 + (int)__s[(long)((local_18c + 3) * 2)];
      local_18c = local_18c + 1;
    }
    if (local_190 != 0x488) {
      puts("incorrect");
                    /* WARNING: Subroutine does not return */
      exit(0);
    }
    if ((((__s[0x25] != '5') || (__s[7] != 'f')) || (__s[0xb] != '8')) ||
       (((__s[0xc] != '7' || (__s[0x17] != '2')) || (__s[0x1f] != '4')))) {
      puts("incorrect");
                    /* WARNING: Subroutine does not return */
      exit(0);
    }
    printf("Correct: %s\n",__s);
    uVar3 = 0;
  }
  else {
    fwrite("./bin flag_is_here",1,0x12,stderr);
    uVar3 = 1;
  }
  if (local_10 == *(long *)(in_FS_OFFSET + 0x28)) {
    return uVar3;
  }
                    /* WARNING: Subroutine does not return */
  __stack_chk_fail();
}

これを気合で解読すると以下の処理を行っていることが分かります．

  • 文字列長の確認 (0x27文字)
  • flagフォーマットの確認 (TWCTF{*f***87**********2*******4*****5})
  • 0123456789abcdefの出現回数の確認 ([3, 2, 2, 0, 3, 2, 1, 3, 3, 1, 1, 3, 1, 2, 2, 3])
  • 7文字目以降から4文字区切りで総和をとって確認 ([0x15e, 0xda, 0x12f, 0x131, 0x100, 0x131, 0xfb, 0x102])
  • 7文字目以降から4文字区切りで総XORをとって確認 ([0x52, 0x0c, 0x01, 0x0f, 0x5c, 0x05, 0x53, 0x58])
  • 7文字目以降から8文字飛ばしで4文字毎に総和をとって確認 ([0x129, 0x103, 0x12b, 0x131, 0x135, 0x10b, 0xff, 0xff])
  • 7文字目以降から8文字飛ばしで4文字毎に総XORをとって確認 ([0x01, 0x57, 0x07, 0x0d, 0x0d, 0x53, 0x51, 0x51])
  • 7文字目以降から1文字飛ばしで総和をとって確認 (0x488)
  • 7文字目以降が[a-f]または[0-9]のどちらに含まれるか確認 ([a-f] -> 0x80, [0-9] -> 0xff, [0x80, 0x80, 0xff, 0x80, 0xff, 0xff, 0xff, 0xff, 0x80, 0xff, 0xff, 0x80, 0x80, 0xff, 0xff, 0x80, 0xff, 0xff, 0x80, 0xff, 0x80, 0x80, 0xff, 0xff, 0xff, 0xff, 0x80, 0xff, 0xff, 0xff, 0x80, 0xff])

あとはこれらの制約条件に基づいて全探索すれば解けます．

# flag = 'TWCTF{*f***87**********2*******4*****5}'
flag = '*f***87**********2*******4*****5'

appearance = [3, 2, 2, 0, 3, 2, 1, 3, 3, 1, 1, 3, 1, 2, 2, 3]
main_constraint =[0x80, 0x80, 0xff, 0x80, 0xff, 0xff, 0xff, 0xff, 0x80, 0xff, 0xff, 0x80, 0x80, 0xff, 0xff, 0x80, 0xff, 0xff, 0x80, 0xff, 0x80, 0x80, 0xff, 0xff, 0xff, 0xff, 0x80, 0xff, 0xff, 0xff, 0x80, 0xff]
plus_constraint1 = [0x15e, 0xda, 0x12f, 0x131, 0x100, 0x131, 0xfb, 0x102]
xor_constraint1 = [0x52, 0x0c, 0x01, 0x0f, 0x5c, 0x05, 0x53, 0x58]
plus_constraint2 = [0x129, 0x103, 0x12b, 0x131, 0x135, 0x10b, 0xff, 0xff]
xor_constraint2 = [0x01, 0x57, 0x07, 0x0d, 0x0d, 0x53, 0x51, 0x51]

def flag_check(flag):
    total = 0
    for i in range(0x10):
        total += ord(flag[i * 2])
    if total != 0x488:
        return False

    for i in range(8):
        plus_check = 0
        xor_check = 0
        for j in range(i,32,8):
            plus_check += ord(flag[j])
            xor_check ^= ord(flag[j])
        if plus_constraint2[i] != plus_check or xor_constraint2[i] != xor_check:
            return False
    return True

def appearance_check(flag):
    for i,c in enumerate('0123456789abcdef'):
        if flag.count(c) > appearance[i]:
            return False
    return True

def candidates_search(s, d, base):
    if d == 4:
        plus_check = 0
        xor_check = 0
        for c in s:
            plus_check += ord(c)
            xor_check ^= ord(c)
        if plus_constraint1[base // 4] == plus_check and xor_constraint1[base // 4] == xor_check:
            yield s
    else:
        if flag[base + d] != '*':
            yield from candidates_search(s + flag[base + d], d + 1, base)
        else:
            if main_constraint[base + d] == 0x80:
                for c in 'abcdef':
                    yield from candidates_search(s + c, d + 1, base)
            else:
                for c in '012456789':
                    yield from candidates_search(s + c, d + 1, base)

def flag_search(s, d, candidates_list):
    if d == 8:
        if flag_check(s):
            yield s
    else:
        for h in candidates_list[d]:
            if appearance_check(s + h):
                yield from flag_search(s + h, d + 1, candidates_list)

candidates_list = []
for base in range(0,32,4):
    x = []
    for candidate in candidates_search('', 0, base):
        x.append(candidate)
    candidates_list.append(x)

print('TWCTF{{{}}}'.format(next(flag_search('', 0, candidates_list))))

> python solve.py
TWCTF{df2b4877e71bd91c02f8ef6004b584a5}

TWCTF{df2b4877e71bd91c02f8ef6004b584a5}

動けばいいやと思って書いてるので必然的にクソコードになる

Simple Logic [Crypto, 95pts, 167solved]

Simple cipher is always strong.

encrypt.rb

require 'securerandom'
require 'openssl'

ROUNDS = 765
BITS = 128
PAIRS = 6

def encrypt(msg, key)
    enc = msg
    mask = (1 << BITS) - 1
    ROUNDS.times do
        enc = (enc + key) & mask
        enc = enc ^ key
    end
    enc
end

def decrypt(msg, key)
    enc = msg
    mask = (1 << BITS) - 1
    ROUNDS.times do
        enc = enc ^ key
        enc = (enc - key) & mask
    end
    enc
end

fail unless BITS % 8 == 0

flag = SecureRandom.bytes(BITS / 8).unpack1('H*').to_i(16)
key = SecureRandom.bytes(BITS / 8).unpack1('H*').to_i(16)

STDERR.puts "The flag: TWCTF{%x}" % flag
STDERR.puts "Key=%x" % key
STDOUT.puts "Encrypted flag: %x" % encrypt(flag, key)
fail unless decrypt(encrypt(flag, key), key) == flag # Decryption Check

PAIRS.times do |i|
    plain = SecureRandom.bytes(BITS / 8).unpack1('H*').to_i(16)
    enc = encrypt(plain, key)
    STDOUT.puts "Pair %d: plain=%x enc=%x" % [-~i, plain, enc]
end

output

Encrypted flag: 43713622de24d04b9c05395bb753d437
Pair 1: plain=29abc13947b5373b86a1dc1d423807a enc=b36b6b62a7e685bd1158744662c5d04a
Pair 2: plain=eeb83b72d3336a80a853bf9c61d6f254 enc=614d86b5b6653cdc8f33368c41e99254
Pair 3: plain=7a0e5ffc7208f978b81475201fbeb3a0 enc=292a7ff7f12b4e21db00e593246be5a0
Pair 4: plain=c464714f5cdce458f32608f8b5e2002e enc=64f930da37d494c634fa22a609342ffe
Pair 5: plain=f944aaccf6779a65e8ba74795da3c41d enc=aa3825e62d053fb0eb8e7e2621dabfe7
Pair 6: plain=552682756304d662fa18e624b09b2ac5 enc=f2ffdf4beb933681844c70190ecf60bf

アプローチ：keyを下位bitから求めていく

encrypt.rbの本質的な暗号化処理は以下のようになります．

enc = (enc + key) & mask
enc = enc ^ key

一見シンプルな暗号化処理ですが，enc + keyの際に発生する繰り上がりがその後のenc ^ keyに影響を与えてしまうため，keyの特定が難しくなっているように見て取れます．
しかし，ネックになっているのが繰り上がりなのであれば繰り上がりが発生しない最下位bitからkeyを徐々に確定していくことでkeyの特定が可能になると考えられます．
そこで，outputとして与えられたPair1~6のplainの下位1byteを暗号化した際にencの下位1byteと一致するようなkeyを求め，そこから徐々にkeyを確定させていくソルバを書きました．

ROUNDS = 765

def encrypt(msg, key, mask):
    enc = msg
    for _ in range(ROUNDS):
        enc = (enc + key) & mask
        enc = enc ^ key

    return enc

def decrypt(msg, key):
    enc = msg
    mask = (1 << 128) - 1
    for _ in range(ROUNDS):
        enc = enc ^ key
        enc = (enc - key) & mask

    return enc

enc_flag = 0x43713622de24d04b9c05395bb753d437
msgs = [0x29abc13947b5373b86a1dc1d423807a ,0xeeb83b72d3336a80a853bf9c61d6f254,0x7a0e5ffc7208f978b81475201fbeb3a0,0xc464714f5cdce458f32608f8b5e2002e,0xf944aaccf6779a65e8ba74795da3c41d,0x552682756304d662fa18e624b09b2ac5]
encs = [0xb36b6b62a7e685bd1158744662c5d04a,0x614d86b5b6653cdc8f33368c41e99254,0x292a7ff7f12b4e21db00e593246be5a0,0x64f930da37d494c634fa22a609342ffe,0xaa3825e62d053fb0eb8e7e2621dabfe7,0xf2ffdf4beb933681844c70190ecf60bf]

fixed_keys = [0x09] # Brute-force search in advance
for bits in range(16,136,8):
    print('BITS: {}'.format(bits))
    fixed_bits = bits - 8
    mask = (1 << bits) - 1
    keys = []
    print('fixed_keys: {}'.format(list(map(hex,fixed_keys))))
    for fixed_key in fixed_keys:
        for x in range(0,256):
            check = True
            for i in range(6):
                enc = encrypt(msgs[i] & mask, (x << fixed_bits) + fixed_key, mask)
                if  enc != (encs[i] & mask):
                    check = False
            if check:
                keys.append((x << fixed_bits) + fixed_key)
    fixed_keys = keys

for key in fixed_keys:
    dec = decrypt(enc_flag, key)
    print('TWCTF{{{}}}'.format(hex(dec)[2:]))

> python solve.py
BITS: 16
fixed_keys: ['0x9']
BITS: 24
fixed_keys: ['0x5509', '0xd509']
BITS: 32
fixed_keys: ['0x73d509', '0xf3d509']
BITS: 40
fixed_keys: ['0x7773d509', '0xf773d509']
BITS: 48
fixed_keys: ['0x3e7773d509', '0xbe7773d509']
BITS: 56
fixed_keys: ['0x153e7773d509', '0x953e7773d509']
BITS: 64
fixed_keys: ['0x3a153e7773d509', '0xba153e7773d509']
BITS: 72
fixed_keys: ['0x29ba153e7773d509', '0xa9ba153e7773d509']
BITS: 80
fixed_keys: ['0x57a9ba153e7773d509', '0xd7a9ba153e7773d509']
BITS: 88
fixed_keys: ['0x4957a9ba153e7773d509', '0xc957a9ba153e7773d509']
BITS: 96
fixed_keys: ['0x494957a9ba153e7773d509', '0xc94957a9ba153e7773d509']
BITS: 104
fixed_keys: ['0x5c494957a9ba153e7773d509', '0xdc494957a9ba153e7773d509']
BITS: 112
fixed_keys: ['0x6bdc494957a9ba153e7773d509', '0xebdc494957a9ba153e7773d509']
BITS: 120
fixed_keys: ['0x1aebdc494957a9ba153e7773d509', '0x9aebdc494957a9ba153e7773d509']
BITS: 128
fixed_keys: ['0x521aebdc494957a9ba153e7773d509', '0xd21aebdc494957a9ba153e7773d509']
TWCTF{ade4850ad48b8d21fa7dae86b842466d}

TWCTF{ade4850ad48b8d21fa7dae86b842466d}

まとめ

  • Crypto, Revの簡単な問題は徐々に解けるようになってきた気がする
  • Web, Pwnはチームメイトに任せっぱなしで問題すら見てないのでwrite-up読んで勉強します
  • Happy! と meow を解きたかった…