Google CTF 2022 quals writeup

Google Capture The Flag 2022 の qualification roundのMaybe Somedayという問題のwriteupです。それなりに難しかったと思うけど、終わってみると 35 solves でこれは解かれすぎではという印象を受けます。世界にはたくさん強いCTFプレイヤーがいるんだなあ

問題概要
考察
解法
exploit

問題概要

大体こういう感じです。ソースコード全文はgoogle ctfの問題リポジトリに上がっています。

def challenge(p):
    secret = os.urandom(2)
    secret = hashlib.sha512(secret).hexdigest().encode()

    c0 = p.encrypt(secret)
    print(f'{c0 = }')

    cs = [int(input()) for _ in range(20)]
    for c in cs:
        try:
            p.fast_decrypt(c)
            print('😀')
        except:
            print('😡')

    guess = input().encode()

    if guess != secret: raise Exception('incorrect guess!')

def main():
    p = Paillier()
    n, g = p.public_key()
    print(f'{n = }')
    print(f'{g = }')

    try:
        for _ in range(16):
            challenge(p)
            print('💡')
        print(f'🏁 {flag}')
    except:
        print('👋')

2バイトの平文をあれやこれやしたあとに $c_0$ という暗号文をもらえて、その暗号文の元の平文を16回連続で当てられたらフラグをもらえます。
手がかりとして、Paillier暗号の復号オラクルがもらえます。平文はPKCS#1 v1.5 形式でパディングされるという前提があり、復号時にこの形式に沿っているかどうか、ということがオラクルからわかります
- このパディング形式では、平文plaintext をパディングすると 00 02 random 00 plaintext という形式になるように random が埋められます（randomにはヌルバイト00は含まないように構成します）

考察

解法

以上のことを考えると、 $c''_0$ がパディングのチェックを通過するかどうかということは、もともとの平分の狙った範囲に特定の文字が存在するかというオラクルになることがわかります。平文の候補は $2^{16}$ 通りしかないので、このオラクルをうまくつかって候補を絞り込めば平文が一意に定められそうです

exploit

今回は先頭10バイト*2に'0'を含む|含まない、'1'を含む|含まない……という分岐を構成して候補を絞り込みました。ちょっと運要素があって16回連続で成功するときとしないときがありますが、分の悪い勝負ではないです

ソースコード汚すぎてびっくり

from ptrlib import Socket
from Crypto.Util.number import inverse
from itertools import product
import hashlib


table = []
for b in product(list(range(256)), repeat=2):
    table.append(hashlib.sha512(bytes(b)).hexdigest())

size = 10
basenum = int("3000" * size, 16)
basealp = int("6100" * size, 16)
one = int("0100" * size, 16)

sock = Socket("nc maybe-someday.2022.ctfcompetition.com 1337")

n = int(sock.recvlineafter("n = "))
g = int(sock.recvlineafter("g = "))


for stage in range(16):
    print("stage: {}".format(stage + 1))
    c0 = int(sock.recvlineafter("c0 = "))


    
    c1 = c0 * pow(g, 0xff << 1024, n**2) % (n**2)


    cs = []
    for i in range(20):
        if i <= 9:
            cs.append(c1 * inverse(pow(g, (basenum + one * i) << (1024 - size*8*2), n**2), n**2) % (n**2))
        elif i <= 0xf:
            cs.append(c1 * inverse(pow(g, (basealp + one * (i - 10)) << (1024 - size*8*2), n**2), n**2) % (n**2))
        else:
            cs.append(c1 * inverse(pow(g, (basenum + one * (i - 16)) << (1024 - size*8*2 - 8), n**2), n**2) % (n**2))

    for c in cs:
        sock.sendline(str(c))

    isin = [0 for _ in range(20)]
    for i, c in enumerate(cs):
        if '😀' in sock.recvline().decode():
            isin[i] = 1

    for h in table:
        head = h[:2*size][::2]
        head2 = h[:2*size+1][1::2]
        match = True
        for i in range(16):
            if isin[i] == 1:
                if hex(i)[2:] not in head:
                    match = False
                    break
            else:
                if hex(i)[2:] in head:
                    match = False
                    break

        for i in range(4):
            if isin[i+0x10] == 1:
                if hex(i)[2:] not in head2:
                    match = False
                    break
            else:
                if hex(i)[2:] in head2:
                    match = False
                    break

        if match:
            sock.sendline(h)
            line = sock.recvline().decode()
            if '💡' in line:
                break
            else:
                print(line)
                raise ValueError("bad luck")
    else:
        raise ValueError("not found")

sock.interactive()