AlpacaHack B-SIDE: HellCouple Writeup

HellCouple

脆弱なカップル！

import secrets
import hashlib
from Crypto.Cipher import AES
import os

FLAG = os.getenv("FLAG", "Alpaca{dummy}").encode()

# https://datatracker.ietf.org/doc/html/rfc3526#section-2
p = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff
g = 2

alice_private = secrets.randbelow(p)
bob_private = secrets.randbelow(p)

alice_public = pow(g, alice_private, p)
bob_public = pow(g, bob_private, p)

print("alice_public:", alice_public)
print("bob_public:", bob_public)
print("leak:", alice_private & (2**1500 - 1))

shared_key = pow(alice_public, bob_private, p)
assert shared_key == pow(bob_public, alice_private, p)
session_key = hashlib.sha256(shared_key.to_bytes(p.bit_length() // 8, "big")).digest()

cipher = AES.new(session_key, AES.MODE_CTR)
encrypted_flag = cipher.nonce + cipher.encrypt(FLAG)
print("encrypted_flag:", encrypted_flag.hex())

解法

alice_private(以下$a$)とalice_public(以下$A$)は、それぞれ以下で表されます。

\begin{align}
a &= leak + k \cdot 2^{1500} \\
A &\equiv g^a \pmod p
\end{align}

ただし、$k$は、上位36bit($p$のbit長は1536bit)です。
ここで、$A$に$a$を代入すると、

A = g^{leak + k \cdot 2^{1500}} \equiv g^{leak} \cdot (g^{2^{1500}})^k \pmod p

と式変形ができ、結果的に未知変数は$k$となります。
このままだと求めづらいので、未知変数$k$だけに変形していきましょう。
まず、$g^{leak}$を左辺に移し、それを$T$と定義します。

T = A \cdot (g^{leak})^{-1}

ここで、$A\equiv g^{leak + k \cdot 2^{1500}} \pmod p$より、

T \equiv  g^{leak + k \cdot 2^{1500}}\cdot (g^{leak})^{-1}

となります。
指数法則より、$ g^{leak} \cdot (g^{2^{1500}})^k$となので、

T \equiv  g^{leak} \cdot (g^{2^{1500}})^k \cdot (g^{leak})^{-1}

$g^{leak}$とその逆元が打ち消しあうため、最終的に

T \equiv (g^{2^{1500}})^k \pmod p

となります。$g^{2^{1500}}$を$H$と定義すると、

T \equiv H^k \pmod p

ときれいな式かつ$k$を求めるという離散対数問題に帰着することができます。

最後にこの離散対数問題を解く方法を考えてみましょう。
今回、未知変数のbit長は36bitであることから、$2^{36}$回程度探索をすればよさそうです。
しかし、$2^{36} = 68719476736$回であることからそのまま総当たりするのは厳しいでしょう。

ここで、離散対数問題を解くためのアルゴリズムBaby-step Giant-step(BSGS)を用います。
BSGSは、

g^x \equiv h \pmod p

の$x$の探索範囲$0 \le x < n$を$\sqrt{n}$にできます。
ステップ数$m \approx \sqrt{n}$として、未知$x$を

x = im + j\space (0 \le i, j < m)

と分解します。
すると、

g^x = g^{im+j} = (g^m)^i \cdot g^j

より、

(g^m)^i \cdot g^j  \equiv h \pmod p

と表せます。両辺$(g^m)^{-i}$をかけると

g^j\equiv h \cdot (g^m)^{-i} \pmod p

となり、これらが成立するような$i, j$を探索する問題と考えることができます。

まず、$g^j \pmod p \space(j = 0, 1, \dotsm, m-1)$を全部計算してハッシュ表に入れます。
この操作はBaby-stepと呼ばれます。
そして$h \cdot (g^m)^{-i} \space (i_0,1,\dots, m)$で計算し、Baby-stepで作成したハッシュ表に存在するか確認します。また、この操作はGiant-stepと呼ばれます。
もし、みつかったら上記式が成立するため、

h \equiv (g^m)^i \cdot g^j \equiv g^{im+j} \equiv g^x

より、解は$im+j$であることがわかります。$N = 2^{36}$とすると、$sqrt{2^{36}} = 262144$より明らかに間に合うでしょう。

このようにして秘密鍵$a$を復元し、共有鍵 -> SHA256 -> AES-CTRの順で復号すれば解けるでしょう。

コードは以下のようになります。

import math
import hashlib
from Crypto.Cipher import AES

p = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff
g = 2
LOW = 1500
MASK = (1 << LOW) - 1

d = {}
with open("../distfiles/output.txt", "r") as f:
    for line in f:
        line = line.strip()
        if not line or ":" not in line:
            continue
        k, v = line.split(":", 1)
        d[k.strip()] = v.strip()

A = int(d["alice_public"])
B = int(d["bob_public"])
leak = int(d["leak"]) & MASK
enc = bytes.fromhex(d["encrypted_flag"])

H = pow(g, 1 << LOW, p)
T = (A * pow(pow(g, leak, p), p - 2, p)) % p

bound = 1 << (p.bit_length() - LOW)
m = math.isqrt(bound - 1) + 1

tbl = {}
e = 1
for j in range(m):
    if e not in tbl:
        tbl[e] = j
    e = (e * H) % p

factor = pow(pow(H, p - 2, p), m, p)
gamma = T
k = None
for i in range(m + 1):
    j = tbl.get(gamma)
    if j is not None:
        x = i * m + j
        if x < bound:
            k = x
            break
    gamma = (gamma * factor) % p

if k is None:
    raise SystemExit("k not found")

a = leak + k * (1 << LOW)
if pow(g, a, p) != A:
    raise SystemExit("Not valid a")

s = pow(B, a, p)
key = hashlib.sha256(s.to_bytes(p.bit_length() // 8, "big")).digest()
nonce, ct = enc[:8], enc[8:]
flag = AES.new(key, AES.MODE_CTR, nonce=nonce).decrypt(ct)
print(flag.decode())

Flag: Alpaca{1_hat3_c0u913s:fire:}