PlaidCTF2021 | leaky block cipher - crypto-writeup-public

#good_challenges_2021

#PlaidCTF2021

import flag
import hashcash

import secrets
from Crypto.Cipher import AES

def gf128(a, b):
    a = int.from_bytes(a, byteorder="big")
    b = int.from_bytes(b, byteorder="big")
    R = 128
    P = sum(1 << x for x in [R, 7, 2, 1, 0])
    r = 0
    for i in range(R):
        if a & (1 << i):
            r ^= b << i
    for i in range(R)[::-1]:
        if r & (1 << (i+R)):
            r ^= P << i
    return r.to_bytes(16, byteorder="big")

def xor(a, b):
    return bytes(x^y for x,y in zip(a,b))

class LeakyBlockCipher:
    def __init__(self, key = None):
        if key is None:
            key = secrets.token_bytes(16)
        self.key = key
        self.aes = AES.new(key, AES.MODE_ECB)
        self.H = self.aes.encrypt(bytes(16))
    def encrypt(self, iv, data):
        assert len(iv) == 16
        assert len(data) % 16 == 0
        ivi = int.from_bytes(iv, "big")
        cip = bytes()
        tag = bytes(16)
        for i in range(0,len(data),16):
            cntr = ((ivi + i // 16 + 1) % 2**128).to_bytes(16, byteorder="big")
            block = data[i:i+16]
            enced = self.aes.encrypt(xor(cntr, block))
            cip += enced
            tag = xor(tag, enced)
            tag = gf128(tag, self.H)
        tag = xor(tag, self.aes.encrypt(iv))
        return cip, tag

def main():
    resource = secrets.token_hex(8)
    print(resource)
    token = input()
    assert hashcash.check(token.strip(), resource, bits=21)

    print("Thanks for helping me try to find this leak.")
    print("Here's a few rounds of the cipher for you to investigate.")
    print("")
    for _ in range(20):
        G = LeakyBlockCipher()
        iv = secrets.token_bytes(16)
        print("iv =", iv.hex())
        plaintext = bytes.fromhex(input("plaintext = "))
        assert len(plaintext) > 100
        cip, tag = G.encrypt(iv, plaintext)
        print("secure auth tag =", tag.hex())
        print("")
        enc_iv = G.aes.encrypt(iv).hex()
        print("Have you caught the drip?")
        print("It looks like ", enc_iv[:-1] + "X")
        guess = input("So what is X? ").strip()
        if guess == enc_iv[-1:]:
            print("Good.  Now just to check, do it again for me.")
        else:
            print("Sorry, the answer was", enc_iv[-1:])
            break
    else:
        print(flag.flag)

if __name__ == "__main__":
    main()

#Polynomial

#quadratic_residue

overview

20回クエリに答えることができればフラグがもらえる
クエリ
- 16byteの iv が毎回ランダムに生成される（もらえる）
- 100文字以上の plaintext を贈り、 (iv, plaintext) が暗号化され、 tag がもらえる
- iv をAESで暗号化した enc_iv の、最後の ~~1バイト~~ 4bitである X
  
  以外
  
  がもらえるので X を当てる
ブロック $i={1, 2, \dots, n}$ の暗号化（ GCM に近いけど違う）
$tag_0 = 0, H = E(0)$
$cnt = (iv + i) \mod 2^{128}$
$c_i = E(cnt \oplus m_i)$
$tag_i = (tag_{i-1} \oplus c_i) * H \mod P$ (where $P = x^{128} + x^7+x^2+x+1$ ）
$tag_{last} = tag_n \oplus E(iv)$

observation

$tag$ から、 $E(iv)$ を求めればよく、 $tag_0, c_i$ は既知なので、 $H$ がわかれば良い？
- $H = E(0)$ なので、そうなるように、 $m_1$ を工夫して送れば $c_1 = E(0)$ になる？
- - $c_1 = E(cnt \oplus m_1) = E(iv + 1 \oplus m_1)$ より、 $c_1 = E(0)$ としたければ $m_1 = iv + 1$
- [! $c_1$ わからないのでダメだった]
たとえば、 $c_i = E(0)$ とすると
- $tag_1 = E(0) * H \mod P$
- $tag_2 = (E(0)*H \oplus E(0)) * H \mod P \equiv (E(0)H + E(0))H \mod P$
- - $= E(0)H^2 + E(0)H \mod P$
  - $= H^3 + H^2 \mod P$
- $tag_{last} = E(0)H^{n+1} + \cdots + E(0)H + E(iv) \mod P$
- - $= H(H(H(\cdots))) + E(iv) \mod P$
例えば…… $c_i = E(iv)$ とすると
- $tag_{last}= E(iv) H^{n} + \cdots + E(iv)H + E(iv) \mod P$
$E(iv)$ の末尾4bitだけを求められているのはなぜ？　全体は求められないが4bit程度なら求められるのだろうか……？
冷静に考えて4bitわかるなら5bitもわかりそうだしそれなら8bit 16bitくらいは全探索できるのではという気分になる

solution

$c_i = E(iv)$ として
$tag_{last} = E(iv) (H^{n} + \cdots + H + 1)$ なので
$E(iv)$ の正しい値を得られれば $\frac{tag_{last}}{E(iv)} = (H^{n} + \cdots + H + 1)$ が成り立つ $\leftrightarrow$

$E(iv) | tag_{last}$ であるはず
$GF(2^{128})$ 上では、 $(1 + x + x^2 + \dots + x^n) = (1 + x)^n$ という式が成り立つ
- 嘘でした
- 方針
  
  $E(iv)$ の末尾4bitを探索し、得られた $(H^n + \cdots + H + 1)$ が $n$ 乗根を持っていれば（ $\leftrightarrow n$ 次剰余であれば？）それは正しい $E(iv)$ であろう、と判断できる
ただし、 $n$ の値が小さい場合には false positive な $E(iv)$ が探索されうる
- $GF(2^{128})$ の multiplicative order は $2^{128}-1$ で、これは $3, 5, 17, 257, \dots$ などの素因数を持つので $g \in GF(2^{128})$ を選んで $g^{15}$ を考えると、この multiplicative order は $(2^{128} - 1) / 15$ になる
- - ので、 $g \in GF(2^{128})$ を適当に選んだ時、 $x^{15} = g$ となるような $x$ が存在する確率は $1/15$
  - - というのも $x \to x^{15}$ という射を考えると、位数が $2^{128}-1 \to (2^{128}-1)/15$ と減っているわけだから、写った先に重複がある。ランダムに $x$ を選んで、それが $x \to x^{15}$ の写る先である割合は $1/15$ という話
方針

$n$ はできるだけ大きくして、 false positive をなくしたい
$(H^n + \cdots + H + 1) = (1 + H)^n$ は、いつでも必ず $n$ 乗根をもつ
一方、誤った $E(iv)$ の探索結果から得られる $\frac{tag_{last}}{E(iv)} = H'$ は、 $GF(2^{128})$ のランダムな要素とみなせるので、 $n | (2^{128} - 1)$ のとき、 $1/n$ の確率で $n$ 乗根を持つ

implementation

以下を20回やる
- iv をもらえるので cntr を計算して、 iv + cntr を 255ブロック送る
- tag と enc_iv' がもらえる
- 4bit 全探索して $tag / Enc(iv)$ が 255 乗根を持っているような $Enc(iv)$ を見つけ、それを返すと次のステージにいけるかも
[PR.とintの変換にはinteger_representation / fetch intを使う](</entry/PR.\<x>とintの変換にはinteger_representation / fetch intを使う>)

from ptrlib import Socket

sock = Socket("localhost", 19999)

R.<x> = GF(2)[]
F = GF(2^128, name='a', modulus=x^128+x^7+x^2+x+1)


for _ in range(20):
    iv = int(sock.recvlineafter("iv = "), 16)
    plaintext = b""
    for i in range(255):
        cntr = (iv + i + 1) % (2**128)
        plaintext += int(iv ^^ cntr).to_bytes(16, "big")
    sock.sendlineafter("plaintext = ", plaintext.hex())

    tag = F.fetch_int(int(sock.recvlineafter("tag ="), 16))
    sock.recvuntil("like ")
    enc_iv_ = sock.recvuntil("X")[:-1].strip().decode()

    for x in range(2**4):
        enc_iv = F.fetch_int(int(enc_iv_ + "{:x}".format(x), 16))
        Hn1 = tag / enc_iv
        try:
            Hn1.nth_root(255)
            sock.sendlineafter("So what is X? ", "{:x}".format(x))
            print(sock.recvline())
            break
        except ValueError:
            pass
    else:
        raise ValueError("not found")


sock.interactive()

overview

以外

observation

solution

implementation