TokyoWesterns CTF 4th 2018 Writeup

この大会は2018/9/1 9:00(JST)~2018/9/3 9:00(JST)に開催されました。
今回もチームで参戦。結果は748点で810チーム中73位でした。
自分で解けた問題をWriteupとして書いておきます。

Welcome!! (warmup)

問題にフラグが書いてある。

TWCTF{Welcome_TokyoWesterns_CTF_2018!!}

scs7 (warmup, crypto)

$ nc crypto.chal.ctf.westerns.tokyo 14791
encrypted flag: Lp4uky56vYPMXQFF8UKebFyXDSqzTA8559WQutXcsVrfr2DAwBpeB4Rfs0c8rBNF
You can encrypt up to 100 messages.

message:  
ciphertext: k

message: !
ciphertext: j

message: "
ciphertext: G

message: #
ciphertext: Y

message: $
ciphertext: q

message: %
ciphertext: e

message: &
ciphertext: i

message: '
ciphertext: Z

message: (
ciphertext: t

message: )
ciphertext: f

message: *
ciphertext: U

message: +
ciphertext: W

message: ,
ciphertext: 0

message: -
ciphertext: B

message: .
ciphertext: R

message: /
ciphertext: m

message: 0
ciphertext: b

message: 1
ciphertext: x

message: 2
ciphertext: p

message: 3
ciphertext: 1

message: 4
ciphertext: T

message: 5
ciphertext: D

message: 6
ciphertext: F

message: 7
ciphertext: d

message: 8
ciphertext: K

message: 9
ciphertext: N

message: :
ciphertext: S

message: ;
ciphertext: vh

message: <
ciphertext: vv

message: =
ciphertext: va

message: >
ciphertext: v4

message: ?
ciphertext: vQ

message: @
ciphertext: v7

message: A
ciphertext: vM

message: B
ciphertext: vn

message: C
ciphertext: vA

message: D
ciphertext: vJ

message: E
ciphertext: vP

message: F
ciphertext: v6

message: G
ciphertext: v8

message: H
ciphertext: vL

message: I
ciphertext: v3

message: J
ciphertext: v2

message: K
ciphertext: vs

message: L
ciphertext: vu

message: M
ciphertext: vw

message: N
ciphertext: v9

message: O
ciphertext: vz

message: P
ciphertext: vX

message: Q
ciphertext: vc

message: R
ciphertext: vg

message: S
ciphertext: vr

message: T
ciphertext: vC

message: U
ciphertext: vV

message: V
ciphertext: vE

message: W
ciphertext: vH

message: X
ciphertext: v5

message: Y
ciphertext: vo

message: Z
ciphertext: vy

message: [
ciphertext: vk

message: \
ciphertext: vj

message: ]
ciphertext: vG

message: ^
ciphertext: vY

message: _
ciphertext: vq

message: `
ciphertext: ve

message: a
ciphertext: vi

message: b
ciphertext: vZ

message: c
ciphertext: vt

message: d
ciphertext: vf

message: e
ciphertext: vU

message: f
ciphertext: vW

message: g
ciphertext: v0

message: h
ciphertext: vB

message: i
ciphertext: vR

message: j
ciphertext: vm

message: k
ciphertext: vb

message: l
ciphertext: vx

message: m
ciphertext: vp

message: n
ciphertext: v1

message: o
ciphertext: vT

message: p
ciphertext: vD

message: q
ciphertext: vF

message: r
ciphertext: vd

message: s
ciphertext: vK

message: t
ciphertext: vN

message: u
ciphertext: vS

message: v
ciphertext: ah

message: w
ciphertext: av

message: x
ciphertext: aa

message: y
ciphertext: a4

message: z
ciphertext: aQ

message: {
ciphertext: a7

message: |
ciphertext: aM

message: }
ciphertext: an

message: ~
ciphertext: aA

スクリプトを作って、ASCII文字を何回か暗号化を試してみると、この順番に規則性があることに気づいた。
上記の場合は以下の順番になっている。

kjGYqeiZtfUW0BRmbxp1TDFdKNShva4Q7MnAJP68L32suw9zXcgrCVEH5oy

";"で必ず2バイトになり、"v"で1文字目が変わる。
使われている文字は以下の59種類。

0123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz

Base59のエンコードという感じだが、テーブルの順番は都度変わるので、テーブルを割り出してから、デコードすればフラグを復号できる。

import socket
import re

def decrypt(tbl, s):
    l = len(tbl)
    val = 0
    for i in range(len(s)):
        val += tbl.index(s[i]) * (l ** (len(s) - i - 1))

    dec = ''
    while True:
        val, remain = val / 256, val % 256
        dec = chr(remain) + dec
        if val == 0:
            break
    return dec

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('crypto.chal.ctf.westerns.tokyo', 14791))

data = s.recv(1024)
print data
pattern = 'encrypted flag: (.+)\nYou'
m = re.search(pattern, data, re.DOTALL)
enc_flag = m.group(1)

tbl = ''
for code in range(ord(';'), ord('v')):
    data = s.recv(1024)
    print data + chr(code)
    s.sendall(chr(code) + '\n')
    data = s.recv(1024)
    print data
    pattern = 'ciphertext: (.+)\n'
    m = re.search(pattern, data)
    tbl += m.group(1)[1]

flag = decrypt(tbl, enc_flag)
print flag
TWCTF{67ced5346146c105075443add26fd7efd72763dd}

mixed cipher (crypto)

処理概要は以下の通り。

1.encrypt
・RSA暗号(hex表記)
・AES暗号(hex表記)(iv付き)

2.decrypt
・RSA復号
・最後の文字を除き、'#'にされる。

3.print_flag
・フラグをAES暗号して表示
・ivは'#'にされる。

4.print_key
・AESの暗号鍵をRSA暗号して表示

複数の問題が織り交ざった問題。方針は以下のとおり。

1.特定のデータを送り込み、その結果からRSA暗号のnを算出する。
2.LSB decryption oracle attackでRSA暗号化されたAES暗号鍵を復号する。
3.ivはgetrandbitsで生成されているので、Mersenne Twisterの機構を使っている。
 このことから、AES暗号のivを予測する。
4.2.と3.で得られた暗号鍵とivを使ってフラグを復号する。

コードにすると以下の通りで、フラグが得られる。

import socket
import random
from fractions import Fraction
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes

BLOCK_SIZE = 16

def recvuntil(s, tail):
    data = ''
    while True:
        if tail in data:
            return data
        data += s.recv(1)

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    gcd = b
    return gcd, x, y

def lsb_oracle(s, enc):
    print '2'
    s.sendall('2\n')
    data = recvuntil(s, 'text: ')
    print data + enc
    s.sendall(enc + '\n')
    data = recvuntil(s, 'key\n')
    print data
    dec = int(data.split('\n')[1][-2:], 16)
    return dec % 2

def unpad(s):
    n = ord(s[-1])
    return s[:-n]

def untemper(rand):
    rand ^= rand >> 18;
    rand ^= (rand << 15) & 0xefc60000;
 
    a = rand ^ ((rand << 7) & 0x9d2c5680);
    b = rand ^ ((a << 7) & 0x9d2c5680);
    c = rand ^ ((b << 7) & 0x9d2c5680);
    d = rand ^ ((c << 7) & 0x9d2c5680);
    rand = rand ^ ((d << 7) & 0x9d2c5680);
 
    rand ^= ((rand ^ (rand >> 11)) >> 11);
    return rand

def aes_decrypt(aeskey, aesiv, s):
    iv = aesiv
    aes = AES.new(aeskey, AES.MODE_CBC, iv)
    return unpad(aes.decrypt(s[BLOCK_SIZE:]))

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('crypto.chal.ctf.westerns.tokyo', 5643))

data = recvuntil(s, 'key\n')
print data

#### calculate n ####
try_rsa_enc = []
for m in [2, 4, 16]:
    print '1'
    s.sendall('1\n')
    data = recvuntil(s, 'text: ')
    print data + chr(m)
    s.sendall(chr(m) + '\n')
    data = recvuntil(s, 'key\n')
    print data
    enc = data.split('\n')[0].split(' ')[1]
    try_rsa_enc.append(int(enc, 16))

diff1 = (try_rsa_enc[0]) ** 2 - try_rsa_enc[1]
diff2 = (try_rsa_enc[1]) ** 2 - try_rsa_enc[2]

n, _, _ = egcd(diff1, diff2)
e = 65537

#### get encrypted key ####
print '4'
s.sendall('4\n')
data = recvuntil(s, 'key\n')
print data
enc_key = data.split('\n')[1]

#### calculate key ####
c = int(enc_key, 16)
bounds = [0, Fraction(n)]

i = 0
while True:
    print 'Round %d' % (i+1)
    i += 1

    c2 = (c * pow(2, e, n)) % n
    h2 = '%x' % c2
    if len(h2) % 2 == 1:
        h2 = '0' + h2
    lsb = lsb_oracle(s, h2)
    if lsb == 1:
        bounds[0] = sum(bounds)/2
    else:
        bounds[1] = sum(bounds)/2
    diff = bounds[1] - bounds[0]
    diff = diff.numerator / diff.denominator

    if diff == 0:
        m = bounds[1].numerator / bounds[1].denominator
        break
    c = c2

aeskey = long_to_bytes(m, 16)

#### get iv (Mersenne Twister) ###
N = 624
state = []
for i in range(N / 4):
    print '1'
    s.sendall('1\n')
    data = recvuntil(s, 'text: ')
    print data + '0'
    s.sendall('0' + '\n')
    data = recvuntil(s, 'key\n')
    print data
    enc = data.split('\n')[1].split(' ')[1]
    iv = int(enc[:BLOCK_SIZE*2], 16)
    state.append(untemper(iv & 0xffffffff))
    state.append(untemper((iv >> 32) & 0xffffffff))
    state.append(untemper((iv >> 64) & 0xffffffff))
    state.append(untemper((iv >> 96) & 0xffffffff))

state.append(N)
random.setstate([3, tuple(state), None])

aesiv = long_to_bytes(random.getrandbits(BLOCK_SIZE*8), 16)

#### get encrypted flag ####
print '3'
s.sendall('3\n')
data = recvuntil(s, 'key\n')
print data

enc_flag = data.split('\n')[2]
flag = aes_decrypt(aeskey, aesiv, enc_flag.decode('hex'))
print flag
TWCTF{L#B_de#r#pti#n_ora#le_c9630b129769330c9498858830f306d9}

mondai.zip (warmup, misc)

パスワード付きzipファイルを解凍することを繰り返す問題。この問題は、他のメンバが途中まで解いていたものの続きで、後半のみを自分で解いた。
最初はzipファイルのファイル名(拡張子を除く)がパスワードになっていた。

y0k0s0

このパスワードで展開すると、パスワード付きzipファイルの他にpcapngファイルが入っている。
192.168.11.5宛の通信のデータ長を見て、文字にする。

データ長:87, 101, 49, 99, 111, 109, 101
→ We1come

このパスワードで展開すると、パスワード付きzipファイルの他にlist.txtというランダムな文字列のリストが入っている。ここからは自分で解いた部分。このリストはパスワード候補のリストと考え、クラックする。

$ fcrackzip -u -D -p list.txt mondai.zip 


PASSWORD FOUND!!!!: pw == eVjbtTpvkU

このパスワードで展開すると、1c9ed78bab3f2d33140cbce7ea223894というファイル名のファイルが入っているだけ。このファイル名をパスワードのmd5の値と考え、逆変換する。

happyhappyhappy

このパスワードで展開すると、パスワード付きzipファイルの他にREADME.txtがあり、password is too short と書いてある。今度のzipパスワードは短いようなので、またまたfcrackzipで攻める。

$ fcrackzip -u -l 1-4 mondai.zip 


PASSWORD FOUND!!!!: pw == to

このパスワードで展開すると、パスワード付きzipファイルの他にsecret.txtがあり、次のように書いてある。

Congratulation!
You got my secret!

Please replace as follows:
(1) = first password
(2) = second password
(3) = third password
...

TWCTF{(2)_(5)_(1)_(4)_(3)}

これまで出てきたパスワードをsecret.txtに記載されている順番に組み立てる。

TWCTF{We1come_to_y0k0s0_happyhappyhappy_eVjbtTpvkU}