Google CTF 2018 Quals Writeup

この大会は2018/6/23 9:00(JST)～2018/6/25 9:00(JST)に開催されました。
今回もチームで参戦。結果は1001点で220チーム中45位でした。
自分で解けた問題をWriteupとして書いておきます。

PERFECT SECRECY(CRYPTO)

コードを読むと、以下のような流れ。

以下をそのまま並べて入力指定
m0: 1バイト
m1: 1バイト
ciphertext: 1024/8=128バイト

ciphertextを復号したデータを数値化。以下を100回繰り返す。
p = そのLSBが0の場合m0、1の場合m1
k = 0～2のランダム値
c = (ord(p) + k) % 2
chr(c)を表示

このことから以下がわかる。

kの値は100回行うと偶数：奇数=2:1（およそ）になる。
m0にASCIIコードが偶数、m1にASCIIコードが奇数となる文字を指定する。
cは0が多ければ、復号データのLSBは0、1が多ければ復号データのLSBは1と判断できる。

ここまでわかれば、LSB decryption oracle attack で復号できる。

from fractions import Fraction
from Crypto.PublicKey import RSA
import socket

def lsb_oracle(cipher):
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect(('perfect-secrecy.ctfcompetition.com', 1337))
    m0 = '0'
    m1 = '1'
    ciphertext = cipher
    send_data = m0 + m1 + ciphertext
    s.sendall(send_data)
    data = s.recv(1)
    data += s.recv(99)
    cnt0 = data.count('\x00')
    cnt1 = data.count('\x01')
    if cnt0 > cnt1:
        return 0
    else:
        return 1

with open('key_pub.pem', 'r') as f:
    pub_data = f.read()

pubkey = RSA.importKey(pub_data)
n = pubkey.n
e = pubkey.e
print e

with open('flag.txt', 'rb') as f:
    c = int(f.read().encode('hex'), 16)

bounds = [0, Fraction(n)]

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

    c2 = (c * pow(2, e, n)) % n
    h2 = '%0256x' % c2
    ct2 = h2.decode('hex')
    lsb = lsb_oracle(ct2)
    if lsb == 1:
        bounds[0] = sum(bounds)/2
    else:
        bounds[1] = sum(bounds)/2
    diff = bounds[1] - bounds[0]
    diff = diff.numerator / diff.denominator
    print diff
    if diff == 0:
        m = bounds[1].numerator / bounds[1].denominator
        break
    c = c2

flag = ('%0256x' % m).decode('hex')
print flag

復号すると、意味のないデータの後ろにフラグが入っていた。

CTF{h3ll0__17_5_m3_1_w45_w0nd3r1n6_1f_4f73r_4ll_7h353_y34r5_y0u_d_l1k3_70_m337}