b00t2root '19 Writeup

この大会は2019/3/30 2:30(JST)～2019/3/31 2:30(JST)に開催されました。
今回もチームで参戦。結果は4155点で323チーム中5位でした。
自分で解けた問題をWriteupとして書いておきます。

Welcome (misc)

slackに入ると、#generalチャネルにフラグが書いてあるメッセージがピン止めされている。

b00t2root{w3lc0me_h0pe_y0u_h4v3_fun}

Steve Rogers (linux)

添付のシェルスクリプトでログインする。プロセスを見ると、フラグを引数にして実行されているものがあった。

steve@2ad43eba9d74:~$ ls -la
total 20
drwxr-xr-x 2 steve steve 4096 Mar 29 15:30 .
drwxr-x--x 1 root  root  4096 Mar 29 15:30 ..
-rw-r--r-- 1 steve steve  220 Mar 29 15:30 .bash_logout
-rw-r--r-- 1 steve steve 3771 Mar 29 15:30 .bashrc
-rw-r--r-- 1 steve steve  807 Mar 29 15:30 .profile
steve@e7d4a74360d0:~$$ ps -ef | grep b00t2root | grep -v grep
root         1     0  0 22:03 pts/0    00:00:00 bash /tmp/42.sh b00t2root{Cmd_l1n3_fl4g5_4r3_0bv10u5}

b00t2root{Cmd_l1n3_fl4g5_4r3_0bv10u5}

cuz_rsa_is_lub (crypto)

nをFermat法で素因数分解して、復号する。

from Crypto.Util.number import *

def isqrt(n):
    x = n
    y = (x + n // x) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

def fermat(n):
    x = isqrt(n) + 1
    y = isqrt(x * x - n)
    while True:
        w = x * x - n - y * y
        if w == 0:
            break
        elif w > 0:
            y += 1
        else:
            x += 1
    return x - y, x + y

n = 71641831546926719303369645296528546480083425905458247405279061196214424558100678947996271179659761521775290973790597533683668081173314940392098256721488468660504161994357
e = 65537
c = 63127079832500412362950100242549738176318170072331491750802716138621322974529994914407846448954487685068331564008936808539420562251661435790855422130443584773306161128156

p, q = fermat(n)

phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)

flag = long_to_bytes(m)
print flag

b00t2root{RSA_c4n_b3_vuln3r4bl3}

Scatter Me (crypto)

x:y:1というデータが;区切りで並んでいる。scatter(散布)というタイトルからも散布図を書けばフラグになりそう。

import matplotlib.pyplot as plt
import numpy as np

with open('scatter.txt', 'r') as f:
    data = f.read()

codes = data.split(';')
x = np.arange(len(codes), dtype = 'float')
y = np.arange(len(codes), dtype = 'float')
for i in range(len(codes)):
    x[i] = float(codes[i].split(':')[0])
    y[i] = float(codes[i].split(':')[1])

plt.scatter(x, y, label="flag")
plt.legend()
plt.show()

b00t2root{300728}

Genetics (crypto)

https://github.com/JohnHammond/ctf-katanaのDNA Codeの対応表を参考に復号する。

import string

dna_code_tbl = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890 .'

enc = 'ACCAGTAAAACGTTGAGACAGTTGAATATCAAACTACACCGAATTCATATGTCACAGCGGCCGACACAGATGATAACA'

enc = enc.replace('A', '00')
enc = enc.replace('C', '01')
enc = enc.replace('G', '10')
enc = enc.replace('T', '11')

dec = ''
for i in range(0, len(enc), 6):
    idx = int(enc[i:i+6], 2)
    dec += dna_code_tbl[idx]

print dec

実行結果は以下の通り。

flag is dnaCrypto1sAwesome

b00t2root{dnaCrypto1sAwesome}

Let's Travel (crypto)

異なる2つの文字列を与えて、同じHash値になればよい。頭に\x00をつけてもHash値は変わらないので、そのような2つを送信する。

import socket

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

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('18.188.225.135', 2001))

place1 = 'Angkor'
place2 = '\x00' + place1
data = recvuntil(s, '1: \n').strip()
print data + place1
s.sendall(place1 + '\n')
data = recvuntil(s, '2: \n').strip()
print data + place2
s.sendall(place2 + '\n')
data = recvuntil(s, '\n').strip()
data += recvuntil(s, '\n').strip()
data += recvuntil(s, '\n').strip()
print data

b00t2root{C0ngr4tulati0n5!_y0u_c4n_n0w_go_4nywh3re}

Strange Oracle (crypto)

RSA LSB Oracle Attackで攻めたいが、アクセス回数制限があるため、普通のやり方だと攻撃しきれない。何回か試したところ、最初の方のアクセスでは、lsbは0になることが分かっている。そのため、制限ぎりぎりアクセスできるよう決め打ちで最初はlsbは0として、途中からアクセスして判断する方式にする。

import socket
from fractions import Fraction
from Crypto.Util.number import long_to_bytes

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):
    data = recvuntil(s, ': ')
    print data
    print '2'
    s.sendall('2\n')
    data = recvuntil(s, ': ')
    print data + enc
    s.sendall(enc + '\n')
    data = recvuntil(s, '\n').strip()
    print data.encode('hex')
    print data
    if data == 'I like it!':
        return 0
    else:
        return 1

LIMIT = 450

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('18.188.225.135', 2002))

data = recvuntil(s, ': ')
print data

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

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

for i in range(2, 10):
    if n % i == 0:
        n = n / i
        break

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

#### get flag ####
c = int(enc_flag, 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
    if i > (1024 - LIMIT + 4):
        lsb = lsb_oracle(s, h2)
    else:
        lsb = 0
    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

flag = long_to_bytes(m)
print flag

b00t2root{dr_s7r4ng3_1s_4_m4rv3l0u5_0r4cl3}