Edited at

TokyoWesterns CTF 4th 2018 Write-up

More than 1 year has passed since last update.

TokyoWesterns CTF 4th 2018 に チーム m1z0r3 として参加して、1015点で53位でした。

自分は以下の4問を解き、416点を入れました。



  • SimpleAuth (55pt) - Warmup / Web


  • scs7 (112pt) - Warmup / Crypto


  • mondai.zip (95pt) - Warmup / Misc


  • Revolutional Secure Angou (154pt) - Crypto

忘れないうちに Write-up を書きます。


SimpleAuth

問題文のURLにアクセスするとソースコードが見える

if (!empty($_SERVER['QUERY_STRING'])) {

$query = $_SERVER['QUERY_STRING'];
$res = parse_str($query); // ココ
if (!empty($res['action'])){
$action = $res['action'];
}
}

ここの parse_str($query) の処理が間違っており、 PHP Manual を読むと、第二引数がない場合は 現在のスコープに勝手に変数をセットする らしい。

というわけで $hashed_password をセットすれば良い。

/?action=auth&hashed_password=c019f6e5cd8aa0bbbcc6e994a54c757e

にアクセスすれば FLAG が降ってくる。


scs7

nc crypto.chal.ctf.westerns.tokyo 14791 をすると、暗号化された FLAG が送られ、その後メッセージを送信すると暗号化して返してくれる。

色々試した結果、以下のことがわかった。


  • 暗号文は、メッセージをHexエンコードしたものを59進法に変換したものである。

  • ただし、59進法で使われる 0-58 をどの記号に割り当てるかは毎回バラバラである。

したがって、はじめに 0-58 がどの記号に対応するか対応表を作ってしまえば、暗号化された FLAG を復号することができる。具体的には chr(59) から chr(117) までを試して、暗号文の最後の桁の文字を見ると、それが 0-58 の数字に対応する。

#!/usr/bin/env python

import socket

HOST = 'crypto.chal.ctf.westerns.tokyo'
PORT = 14791

def sock(ip, port):
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect((ip, port))
return s, s.makefile('rw', bufsize=0)

def read_until(f, delim='\n'):
data = ''
while not data.endswith(delim):
data += f.read(1)
return data

def main():
print 'nc %s %s\n' % (HOST, PORT)
s, f = sock(HOST, PORT)

result = read_until(f).strip()
print result
encrypted_flag = result.split(': ')[1]
print read_until(f).strip()

table = {}
for i in range(59, 118):
print read_until(f, ': ').strip() + chr(i)
s.send(chr(i) + '\n')
result = read_until(f).strip()
print result
table[result[-1]] = i - 59

flag = 0
for i, s in enumerate(encrypted_flag[::-1]):
flag += table[s] * (59 ** i)

print
print hex(flag)[2:-1].decode('hex')

if __name__ == '__main__':
main()


mondai.zip

mondai.zip が渡され、解凍すると中からまた Zip ファイル(パスワード付き)が出てきて、パスワードを解読して解凍するとまた Zip ファイルが出てきて… みたいな問題。

ちなみに、1番目のパスワードが一番難しかった… 他の人が2番目まで解いてくれたので残りをやった。


1番目のパスワード

ファイル名がそのままパスワード


2番目のパスワード

capture.pcapng を開くと、不自然なデータを持つ ICMP パケットが並んでおり、データサイズに着目するとパスワードがわかる

$ tshark -n -t e -r capture.pcapng -Y 'icmp and ip.dst == 192.168.11.5' -T fields -e data.len

print(''.join([chr(i) for i in [87, 101, 49, 99, 111, 109, 101]]))


3番目のパスワード

list.txt がパスワードリストで、どれかが正解

from zipfile import ZipFile

password_list = open('list.txt', 'r').read().split('\n')
with ZipFile('mondai.zip') as zf:
for password in password_list:
try:
zf.extractall(pwd=password)
print '+ Completed! Pass: ' + password
break
except:
continue


4番目のパスワード

ファイル名が MD5 ハッシュ値で、元のメッセージがパスワード


5番目のパスワード

README.txt を見ると、 "password is too short" とのことなので総当たりを試す

解凍すると secret.txt が出てくるので、指示通り ( TWCTF{(2)_(5)_(1)_(4)_(3)} ) に FLAG を組み立てる


Revolutional Secure Angou

:warning: (私は数学弱者なので、以下は数学的に正しくない可能性が大いにあります。ご注意ください)

$ q \times e \equiv 1 \pmod{P} $ より、次のように考えた。

qe = px + 1

x = \frac{q}{p}e - \frac{1}{p} \approx \frac{q}{p}e \left(\because 0 \lt \frac{1}{p} \ll 1 \right)

ここで、 $p$ と $q$ は巨大な素数であり、 $\frac{q}{p}$ の値はそこまで大きくならないと仮定すると、 $x$ の値は $e$ と大幅には変わらない(ブルートフォース可能)と判断した。

また、

qe = px + 1

ne = p^2 x + p

p^2 = \frac{ne - p}{x} \approx \frac{ne}{x} \left(\because ne \gg p \right)

となるので、$x$ を徐々に増加さながら、 $\frac{ne}{x}$ を超えない最大の平方数を計算し、その平方根を元の式に代入して成立するか確かめた。

require 'openssl'

key = OpenSSL::PKey::RSA.new File.read('publickey.pem')
e, n = key.e.to_i, key.n.to_i

# num 以下の最大の平方数を求める
def search_square(num)
ds = num.to_s.reverse.scan(/..|.$/).reverse.map(&:reverse)
k, n = 0, 0
ds.each do |d|
k = (k.to_s + d.to_s).to_i
j = 0
j += 1 while ((n.to_s + j.to_s).to_i + 1) ** 2 <= k
n = (n.to_s + j.to_s).to_i
end
n
end

2.upto(1000000) do |x|
puts x if x % 1000 == 0
p = search_square(n * e / x)
q = n / p
if p * (p * x + 1) == n * e
puts "+ p: #{p}"
puts "+ q: #{q}"
break
end
end

# rsatool.py を用いて、秘密鍵 (privatekey.pem) を生成する
# $ python rsatool.py -f PEM -o privatekey.pem -p [p] -q [q]

key = OpenSSL::PKey::RSA.new File.read('privatekey.pem')
File.binwrite('flag', key.private_decrypt(File.binread('flag.encrypted')))