TetCTF 2022 - shares

TL;DR

$\mathbb F_{37}^{32}$ において、係数ベクトルと、それと秘密ベクトルとの内積がシェアとして16個だけ与えられ、秘密ベクトルの前半を当てるとフラグが貰える
シェアは何度も入手出来るが秘密ベクトルの後半16個は毎回変わる
係数ベクトルの後半が一次従属になる場合を狙い、0ベクトルになるような線形和を作ることで秘密ベクトルの前半に関する式が得られる
これを前半の次元の分だけ手に入れて連立方程式を解き、秘密を復元する

Prerequisite

線形代数

Writeup

次のようなスクリプトが動いている

"""
This is an (incomplete) implement for a new (and experimental) secret/password
sharing scheme.

The idea is simple. Basically, a secret or password is turned into a set of
finite field elements and each share is just a linear combination of these
elements. On the other hand, when enough shares are collected, the finite field
elements are determined, allowing the original secret or password to be
recovered.
"""
from typing import List
from secrets import randbelow
import string

ALLOWED_CHARS = string.ascii_lowercase + string.digits + "_"
P = len(ALLOWED_CHARS)
INT_TO_CHAR = {}
CHAR_TO_INT = {}
for _i, _c in enumerate(ALLOWED_CHARS):
    INT_TO_CHAR[_i] = _c
    CHAR_TO_INT[_c] = _i


def get_shares(password: str, n: int, t: int) -> List[str]:
    """
    Get password shares.

    Args:
        password: the password to be shared.
        n: the number of shares returned.
        t: the minimum number of shares needed to recover the password.

    Returns:
        the shares.
    """
    assert len(password) <= t
    assert n > 0

    ffes = [CHAR_TO_INT[c] for c in password]
    ffes += [randbelow(P) for _ in range(t - len(password))]
    result = []
    for _ in range(n):
        coeffs = [randbelow(P) for _ in range(len(ffes))]
        s = sum([x * y for x, y in zip(coeffs, ffes)]) % P
        coeffs.append(s)
        result.append("".join(INT_TO_CHAR[i] for i in coeffs))

    return result


def combine_shares(shares: List[str]) -> str:
    raise Exception("unimplemented")


def main():
    pw_len = 16
    password = "".join(INT_TO_CHAR[randbelow(P)] for _ in range(pw_len))

    # how about n < t :D
    n = 16
    t = 32

    for _ in range(2022):
        line = input()
        if line == password:
            from secret import FLAG
            print(FLAG)
            return
        else:
            print(get_shares(password, n, t))


if __name__ == '__main__':
    main()

小文字アルファベットと数字、アンダースコア(計37文字)をそれぞれ $\mathbb F_{37}$ の成分に対応させて、16文字のパスワードを秘密とした次のような秘密分散のシェアを作成している。

パスワードにランダムな文字列を追加して32文字とし、 $\mathbb F_{37}^{32}$ のベクトル $\boldsymbol p$ として扱う
ランダムな係数ベクトル $(c_1, \dots, c_{32})$ を用意し、 $\boldsymbol p$ との内積 $s$ を計算する
係数ベクトルと $s$ の組を16個作成してシェアとし公開する

シェアの作成ごとに $\boldsymbol p$ は変わってしまうが、前半16個の要素は秘密であるパスワードであり、常に同じなのでこれを $\boldsymbol x$ とおいて $\boldsymbol p_i \coloneqq \boldsymbol x + \boldsymbol r_i$ とする。ランダムな文字列に対応するベクトルを $\boldsymbol r_i$ とおいた。

この定義より、 $\boldsymbol x$ は後半16個の要素が0であり、 $\boldsymbol r_i$ は前半16個の要素が0である。

係数ベクトルも同様に分割する。シェアは一度に複数(16個)作られるので $j$ 番目に作られたシェアで用いた係数ベクトルを $\boldsymbol c_j + \boldsymbol c_j'$ のようにおく。この時、 $\boldsymbol c_j$ は後半16個の要素が0であり、 $\boldsymbol c_j'$ は前半16個の要素が0である。

$j$ 番目に作られたシェア $s$ を $s_j$ とおくと次が成り立つ。

$\begin{aligned} s_j \equiv \langle \boldsymbol b_j, \boldsymbol p_i\rangle &\equiv \langle \boldsymbol c_j,\boldsymbol x\rangle + \langle \boldsymbol c_j', \boldsymbol x\rangle + \langle \boldsymbol c_j,\boldsymbol r_i\rangle + \langle \boldsymbol c_j', \boldsymbol r_i \rangle &\mod 37\cr &\equiv \langle \boldsymbol c_j,\boldsymbol x\rangle + \langle \boldsymbol c_j', \boldsymbol r_i \rangle &\mod 37 \end{aligned}$

$\boldsymbol x, \boldsymbol r_i$ の2つが未知数でその次元は32であるにも関わらず式が16個しか得られないので解くことが出来ない。ここで、 $\boldsymbol x$ は $i$ に依存しないのでなんとかして $\boldsymbol r_i$ を消すことが出来れば、シェアの入手をまたいで $\boldsymbol x$ が解けるような式の集合を用意出来る可能性を思いつく。

内積は双線型性という非常に便利な性質があるので、試しにここで得られたシェアの線形結合を考えてみる。

$\sum_{j=1}^{16} a_js_j \equiv \left\langle \sum_{j=1}^{16} a_j \boldsymbol c_j,\boldsymbol x\right\rangle + \left\langle \sum_{j=1}^{16} a_j \boldsymbol c_j', \boldsymbol r_i \right\rangle \mod 37$

もし、 $\boldsymbol c_1', \dots, \boldsymbol c_{16}'$ が一次従属なら、 $\sum_{j=1}^{16} a_j \boldsymbol c_j' = 0$ (0ベクトル) になるような $a_1, \dots, a_{16}$ が存在する。この時、当然 $\left\langle \sum_{j=1}^{16} a_j \boldsymbol c_j', \boldsymbol r_i \right\rangle$ は0になるので、 $s_i' \coloneqq \sum_{j=1}^{16} a_js_j, \boldsymbol d_i \coloneqq \sum_{j=1}^{16} a_j \boldsymbol c_j$ とおくと次が成り立つ。

$s_i' \equiv \langle \boldsymbol d_i, \boldsymbol x \rangle \mod 37$

これで未知数の次元が16になった上に、 $r_i$ に依存しないためこのような $i$ となるようなシェアの入手を16回繰り返せば $\boldsymbol x$ が復元出来る。

ただこれには $\boldsymbol c_1', \dots, \boldsymbol c_{16}'$ が一次従属である必要がある。ランダムにとってきたベクトルは大抵の場合一次独立であるが、 $\mathbb F_{37}$ 成分の場合は次のような雑な計算をすると $1/37$ になる。

先頭15個のベクトルの線形結合で表されるベクトルの個数は係数が15個あることから $37^{15}$ 個であり、一方で $\boldsymbol c_j'$ は $\mathbb F_{37}^{16}$ のベクトルと同一視出来るのでその総数は $37^{16}$ 、よって $\boldsymbol c_{16}'$ が先頭15個のベクトルの線形結合となる確率は $37^{15}/37^{16} = 1/37$ になる。

というわけで取ってきたシェアから、 $\boldsymbol c_j' \ (1 \leq j \leq 16)$ が一次従属であるかどうかを調べ、もしそうなら線形和が0ベクトルとなるような係数 $a_j$ を導出して $s_i', \boldsymbol d_i$ を計算する。そうして最終的に次を満たす $\boldsymbol x$ を求める。 $\boldsymbol d_i^{(n)}$ で、 $\boldsymbol d_i$ の第 $n$ 成分を表すものとする。

$\begin{pmatrix} s_1' \cr s_2' \cr \vdots \cr s_{16}' \end{pmatrix} = \begin{pmatrix} \langle\boldsymbol d_1, \boldsymbol x\rangle \cr \langle\boldsymbol d_2, \boldsymbol x \rangle \cr \vdots \cr \langle\boldsymbol d_{16}, \boldsymbol x \rangle \end{pmatrix} = \begin{pmatrix} \boldsymbol d_1^{(1)} & \boldsymbol d_1^{(2)} & \dots & \boldsymbol d_1^{(16)} \cr \boldsymbol d_2^{(1)} & \boldsymbol d_2^{(2)} & \dots & \boldsymbol d_2^{(16)} \cr & & \vdots \cr \boldsymbol d_{16}^{(1)} & \boldsymbol d_{16}^{(2)} & \dots & \boldsymbol d_{16}^{(16)} \end{pmatrix} \begin{pmatrix} x_1 \cr x_2 \cr \vdots \cr x_{16} \end{pmatrix}$

$\boldsymbol x$ が求まったら、これをパスワードの文字列に戻して提出するとフラグが得られる。

Code

from pwn import process
import string
import sys

ALLOWED_CHARS = string.ascii_lowercase + string.digits + "_"
P = len(ALLOWED_CHARS)
Fp = GF(P)
INT_TO_CHAR = {}
CHAR_TO_INT = {}
for _i, _c in enumerate(ALLOWED_CHARS):
    INT_TO_CHAR[_i] = _c
    CHAR_TO_INT[_c] = _i

n = 16
t = 32
DEBUG = False

if len(sys.argv) > 1 and "-d" in sys.argv:
    DEBUG = True

if DEBUG:
    sc = process(["python3", "shares.py"])
    answer = "testunkoaaaabbbb"
else:
    sc = process(["python3", "org_shares.py"])
    answer = None

if answer is not None:
    v_pwd = []
    for c in answer:
        v_pwd.append(CHAR_TO_INT[c])

    v_pwd = vector(Fp, v_pwd)

def to_vec(s):
    v1 = []
    for c in s[:16]:
        v1.append(CHAR_TO_INT[c])

    v1 = vector(Fp, v1)

    v2 = []
    for c in s[16:32]:
        v2.append(CHAR_TO_INT[c])

    v2 = vector(Fp, v2)

    s = Fp(CHAR_TO_INT[s[32]])

    return v1, v2, s


def get_share(password=None):
    send = True
    if password is None:
        password = "unko"
        send = False

    sc.sendline(password.encode())
    if send:
        sc.interactive()
        exit()

    ret = []
    res = eval(sc.recvline().strip().decode())
    for r in res:
        ret.append(to_vec(r))

    return ret

new_v1s = []
new_ss = []
dep_cnt = 0
while dep_cnt < 16:
    v1s = []
    v2s = []
    ss = []
    for v1, v2, s in get_share():
        v1s.append(v1)
        v2s.append(v2)
        ss.append(s)

    ker = (Fp^16).linear_dependence(v2s)
    if len(ker) > 0:
        dep_cnt += 1
        ker = vector(ker[0])
        new_v1 = ker * matrix(v1s)
        new_s = ker * vector(ss)
        if answer is not None:
            assert new_v1 * v_pwd == new_s

        new_v1s.append(new_v1)
        new_ss.append(new_s)

M = matrix(new_v1s)
v = vector(new_ss)

pwd = ""
x = M.solve_right(v)
for c in x:
    pwd += INT_TO_CHAR[int(c)]

print(pwd)
if answer is not None:
    assert answer == pwd

get_share(pwd)

Flag

ローカルで解いただけなので無し

Resources

CTF-Writeups/TetCTF/2022/shares at master · nguyenduyhieukma/CTF-Writeups: 問題ファイル