CSAW CTF 2019 Write-up

はじめに

2019/09/15 ~ 2019/09/16に開催されたCSAW CTF 2019 にチーム(NekochanNano!)で参加しました．

成績

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

beleaf [Rev, 50pts, 397solves]

tree sounds are best listened to by https://binary.ninja/demo or ghidra

beleaf

> file beleaf
beleaf: ELF 64-bit LSB shared object x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 3.2.0, BuildID[sha1]=6d305eed7c9bebbaa60b67403a6c6f2b36de3ca4, stripped

> ./beleaf 
Enter the flag
>>> meow    
Incorrect!

アプローチ：Ghidraでデコンパイル

問題文にも書いてある通りにGhidraでデコンパイルします．

undefined8 FUN_001008a1(void)
{
  size_t sVar1;
  long lVar2;
  long in_FS_OFFSET;
  ulong local_b0;
  char local_98 [136];
  long local_10;
  
  local_10 = *(long *)(in_FS_OFFSET + 0x28);
  printf("Enter the flag\n>>> ");
  __isoc99_scanf(&DAT_00100a78,local_98);
  sVar1 = strlen(local_98);
  if (sVar1 < 0x21) {
    puts("Incorrect!");
                    /* WARNING: Subroutine does not return */
    exit(1);
  }
  local_b0 = 0;
  while (local_b0 < sVar1) {
    lVar2 = FUN_001007fa((ulong)(uint)(int)local_98[local_b0]);
    if (lVar2 != *(long *)(&DAT_003014e0 + local_b0 * 8)) {
      puts("Incorrect!");
                    /* WARNING: Subroutine does not return */
      exit(1);
    }
    local_b0 = local_b0 + 1;
  }
  puts("Correct!");
  if (local_10 != *(long *)(in_FS_OFFSET + 0x28)) {
                    /* WARNING: Subroutine does not return */
    __stack_chk_fail();
  }
  return 0;
}


long FUN_001007fa(char cParm1)
{
  long local_10;
  
  local_10 = 0;
  while ((local_10 != -1 && ((int)cParm1 != *(int *)(&DAT_00301020 + local_10 * 4)))) {
    if ((int)cParm1 < *(int *)(&DAT_00301020 + local_10 * 4)) {
      local_10 = local_10 * 2 + 1;
    }
    else {
      if (*(int *)(&DAT_00301020 + local_10 * 4) < (int)cParm1) {
        local_10 = (local_10 + 1) * 2;
      }
    }
  }
  return local_10;
}

デコンパイル結果からFUN_001008a1, FUN_001007faではそれぞれ次のような処理を行っていることが分かります．
FUN_001008a1

• 入力文字列長のチェック (0x21文字未満はIncorrect)
• 配列DAT_003014e0の要素と関数FUN_001007faの返り値の比較 (異なればIncorrect)

FUN_001007fa

• 配列DAT_00301020の要素と引数を比較
• long local_10をindexとしてreturn

あとはこれらの処理を再現し，候補となる文字を総当たりすれば解けます．
以下ソルバです．

import string

DAT_003014e0 = [0x01,0x09,0x11,0x27,0x02,0x00,0x12,0x03,0x08,0x12,0x09,0x12,0x11,0x01,0x03,0x13,0x04,0x03,0x05,0x15,0x2E,0x0A,0x03,0x0A,0x12,0x03,0x01,0x2E,0x16,0x2E,0x0A,0x12,0x06]
DAT_00301020 = [0x00000077, 0x00000066, 0x0000007b, 0x0000005f, 0x0000006e, 0x00000079, 0x0000007d, 0xffffffff, 0x00000062, 0x0000006c, 0x00000072, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0x00000061, 0x00000065, 0x00000069, 0xffffffff, 0x0000006f, 0x00000074, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0x00000067, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0x00000075, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0x00000000, 0x00000000, 0x00000000, 0x00000000]

def FUN_001007fa(c):
    count = 0
    while count < len(DAT_00301020):
        if ord(c) == DAT_00301020[count]:
            break
        elif ord(c) < DAT_00301020[count]:
            count = count * 2 + 1
        else:
            if DAT_00301020[count] < ord(c):
                count = (count + 1) * 2
    return count

flag = ''
for i in range(0x21):
    for c in string.printable:
        if DAT_003014e0[i] == FUN_001007fa(c):
            flag += c
            break
print(flag)

> python solve.py
flag{we_beleaf_in_your_re_future}

flag{we_beleaf_in_your_re_future}

SuperCurve [Crypto, 300pts, 171solves]

We are a super legitimate crypto company asking you to complete an audit on our new elliptic curve, SuperCurve, in order to show those hecklers at WhiteHat how legit we are!
nc crypto.chal.csaw.io 1000

server.py

#!/usr/bin/env python3

import random
from supercurve import SuperCurve, curve

def main():
    curve = SuperCurve(
        field = 14753, order = 7919,
        a = 1, b = -1, g = (1, 1),
    )
    # print curve parameters generically
    print(curve)

    # xP = Q
    secret_scalar = random.randrange(curve.order)
    base = curve.g
    pub = curve.mult(secret_scalar, base)
    print("Public key: {}".format(pub))
    #print("Secret scalar: {}".format(secret_scalar))

    while True:
        print("What is the secret?")
        user_input = input("Asking for secret")
        user_input = int(user_input)

        if curve.mult(user_input, base) == pub:
            with open("flag.txt", "r") as f:
                print(f.read())
            break
        else:
            print("WRONGGG!")
            continue

    return 0

if __name__ == "__main__":
    exit(main())

supercurve.py

"""
supercurve.py

    An implementation of a weak elliptic curve over a prime field in standard Weirstrauss form:
        y^2 = x^3 + ax + b

    Derived from: https://github.com/andreacorbellini/ecc/blob/master/logs/common.py
"""

class SuperCurve:

    def __init__(self, field, order, a, b, g):
        """
        a, b = coefficients
        g = base point
        """
        self.field = field
        self.order = order

        self.a = a
        self.b = b
        self.g = g

        assert pow(2, field - 1, field) == 1
        assert (4 * a * a * a + 27 * b * b) % field != 0

    def __str__(self):
        return "a = {}\nb = {}\np = {}\nn = {}".format(self.a, self.b, self.field, self.order)

    def is_on_curve(self, point):
        if point is None:
            return True

        (x, y) = point
        return (y * y - x * x * x - self.a * x - self.b) % self.field == 0

    def add(self, p1, p2):
        assert self.is_on_curve(p1)
        assert self.is_on_curve(p2)

        if p1 is None:
            return p2
        if p2 is None:
            return p1

        (x1, y1) = p1
        (x2, y2) = p2

        if x1 == x2 and y1 != y2:
            return None

        if x1 == x2:
            m = (3 * x1 * x1 + self.a) * SuperCurve.inv_mod(2 * y1, self.field)
        else:
            m = (y1 - y2) * SuperCurve.inv_mod(x1 - x2, self.field)

        x3 = m * m - x1 - x2
        y3 = y1 + m * (x3 - x1)
        result = (x3 % self.field, -y3 % self.field)
        assert self.is_on_curve(result)
        return result

    def double(self, p):
        return self.add(p, p)

    def neg(self, p):
        if p is None:
            return None

        (x, y) = p
        res = x, -y % self.field
        assert self.is_on_curve(res)
        return res

    def mult(self, scal, point):
        if scal % self.order == 0 or point is None:
            return None
        if scal < 0:
            return self.neg(self.mult(-scal, point))

        result = None
        addend = point

        while scal:
            if scal & 1:
                result = self.add(result, addend)
            addend = self.double(addend)
            scal >>= 1

        return result

    @staticmethod
    def inv_mod(n, p):
        if n == 0:
            raise Exception
        if n < 0:
            return p - SuperCurve.inv_mod(-n, p)

        s, old_s = 0, 1
        t, old_t = 1, 0
        r, old_r = p, n

        while r != 0:
            quotient = old_r // r
            old_r, r = r, old_r - quotient * r
            old_s, s = s, old_s - quotient * s
            old_t, t = t, old_s - quotient * t

        gcd, x, y = old_r, old_s, old_t

        assert gcd == 1
        assert (n * x) % p == 1
        return x % p


curve = SuperCurve(
    field = 14753, order = 14660,
    a = 1, b = -1, g = (1, 1),
)

> nc crypto.chal.csaw.io 1000
a = 1
b = -1
p = 14753
n = 7919
Public key: (1719, 13842)
What is the secret?
1127
WRONGGG!

アプローチ：愚直にブルートフォース

まずserver.pyから正しいsecretを入力すればflagが読み取れることが分かります．
ここでのsecretはbase pointを楕円曲線上で何倍すればPublic keyと一致するかというものです．

楕円曲線上でを満たすを見つけるのは離散対数問題であるため，通常であれば総当たりで解くことは困難です． しかし，今回の問題に限ればfieldとorderが小さいため愚直に総当たりしても一瞬で解けてしまいます．

以下ソルバです．

import re
from supercurve import SuperCurve
from socket import *

def recvuntil(msg):
    rec = ''
    while msg not in rec:
        rec = s.recv(1024).decode('utf-8')

    return rec

s = socket(AF_INET, SOCK_STREAM)
s.connect(('crypto.chal.csaw.io', 1000))

curve = SuperCurve(
    field = 14753, order = 7919,
    a = 1, b = -1, g = (1, 1),
)
base = curve.g

rec = recvuntil('Public key:')
match = re.search(r"\((.+)\)",rec)
target = tuple(map(int,match.group(1).split(', ')))
print('Public key: {}'.format(target))

for scale in range(curve.order):
    pub =  curve.mult(scale, base)
    if pub == target:
        print('secret: {}'.format(scale))
        s.send(str(scale).encode('utf-8') + b'\n')
        rec = s.recv(1024).decode('utf-8')
        break

print(rec)

> python solve.py
Public key: (7031, 11777)
secret: 5829
flag{use_good_params}

flag{use_good_params}

まとめ

• beleafとSuperCurveは簡単だったのですんなりと解けた
• byte_me, count_on_me, Fault Boxは10時間くらい取り組んだけど解けなかった（つらスギィ）
• count_on_me, Fault Boxは良問だと思うのでWrite-up読んで勉強したい (byte_meはエスパーが必要なのでダメ)
• 今回のCTFはCryptoが他ジャンルよりも簡単だったのでもう少しチームに貢献したかった（完）