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
（私は数学弱者なので、以下は数学的に正しくない可能性が大いにあります。ご注意ください）
$ 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')))