Google CTF 2022 quals writeup - Maybe Someday

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$ を復号オラクルにそのまま投げても必ずパディングのチェックに成功するのでなんの情報も得られません
パディングが不正になるのは復号後の平文が00 02 から始まらないか、randomとplaintext を区別するような00 がないときです
今回の平文はhexdigestであることがわかっているので、plaintextの各バイトは'0'から'f'までのいずれか、すなわち 30 31 32 33 34 35 36 37 38 39 61 62 63 64 65 66 のいずれかになり、00は必ず含まれません
paillier暗号には加法準同型性があり、平文 $m$ の暗号文 $c$ が与えられた際に、任意の $x$ を持ってきて $m + x$ を暗号化した暗号文 $c'$ を自由に作ることができます

解法

paillier暗号の加法準同型性を用いて、与えられたは00 02 random 00 plaintextという平文を暗号化したものであったところをとして00 02 random ff plaintextに対する暗号文にすることができます
- 当然これは00を含まない平文に復号されるので必ずパディングのチェックでエラーになります
更にの平文から適当な値alphaを引いた平文 00 02 random ff (plaintext - alpha) に復号される暗号文も構成できます
- このときは plaintext - alpha に 00 となるような値があるかどうかで、復号に成功するかどうかが変わります
ここで例えば平文が '1234512345' という文字列だった場合、バイト列では 31 32 33 34 35 31 32 33 34 35となります。ここからalphaとして30 00 30 00 30 00 30 00 30*1を引いたとすると $c''_0$ を復号した平文は00 31 02 33 04 30 01 32 03 34 となり、00 が含まれるのでパディングのチェックを通過します
一方平文が 'abcdeabcde' という文字列だった場合、バイト列では 61 62 63 64 65 61 62 63 64 65となります。ここからalphaとして同じく30 00 30 00 30 00 30 00 30を引いたときは30 62 32 63 34 60 31 62 33 64となって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 = "))


    # fill 0
    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()

*1:繰り下がりを考えたくないので1文字空きにしています

*2:1バイト空きなので20バイトのうち奇数バイト

ふるつき

v('=')v かに

Google CTF 2022 quals writeup - Maybe Someday

問題概要

考察

解法

exploit