※前回の記事と被る部分の説明は割愛するので先にそっちを読んで下さい

TL;DR

  • 前回のsharesの続き、秘密にランダム文字列は付与されないが1/2の確率でシェアに18がエラー項として加算される
  • 係数とシェアを2倍すると、$18\times 2 = 36 \equiv -1 \mod 37$より、エラー項の大きさが小さくなるからLWEっぽく解く
  • エラー項を短いベクトルとしてそれを導出するようなSVPを解いた

Prerequisite

  • LWEの解法
    • 実質CVPだが、エラー項が最短ベクトルになるようなSVPに落とした
    • なお、Babaiの最近平面アルゴリズムは刺さらなかった

Writeup

次のようなスクリプトが動いている(sharesは前問のファイル)

"""
In this new version, I introduce a new feature: master share. A master share
is always required to recover the original secret/password.

I implement this feature by using the master share to "encrypt" the linear
combination results.
"""
from shares import *
from typing import Tuple, List
from secrets import randbits, randbelow

MASTER_SHARE_SZ = 128


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

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

    Returns:
        the shares, including the master share (n + 1 shares in total).
    """
    assert n <= MASTER_SHARE_SZ
    master_share = randbits(MASTER_SHARE_SZ)
    unprocessed_non_master_shares = get_shares(password, n, t)
    non_master_shares = []
    for i, share in enumerate(unprocessed_non_master_shares):
        v = CHAR_TO_INT[share[-1]]
        if (master_share >> i) & 1:
            v = (v + P // 2) % P
        non_master_shares.append(share[:-1] + INT_TO_CHAR[v])

    return master_share, non_master_shares


def combine_shares_v2(master_share: int, non_master_shares: List[str]) -> str:
    raise Exception("unimplemented")


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

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


if __name__ == '__main__':
    main()

前の問題であるsharesと同様の秘密分散が行われているが、今回は秘密の文字列にランダムな文字列は付与されず最初から32文字で、代わりに1/2の確率で18がシェアに加算される($\mathbb F_{37}$上の計算なので、当然37で余りをとったものになる)。

したがって今回得られるシェアは、係数ベクトル$\boldsymbol c_i \in \mathbb F_{37}^{32}$と、$s_i \equiv \langle \boldsymbol c_i, \boldsymbol x\rangle + e_i \mod 37$である。ここで$\boldsymbol x$は秘密の文字列のベクトル表現であり、$e_i$はエラー項で$e_i \in \{0, 18\}$を満たす

エラー項が大きすぎてLWEに落とし込むようなアプローチは難しそうに見えるが、前回同様内積の双線形性を利用すると次が成り立つ。

$$ 2s_i \equiv \langle 2\boldsymbol c_i, \boldsymbol x \rangle + 2e_i \mod 37 $$

ここで、$2e_i \in \{0,36\} \equiv -1 \mod 37$であり、エラー項が非常に小さくなることから、格子を上手く使えば解けそうな予感がする。2回シェアを入手して計64個の$\boldsymbol c_i, s_i$の組に対して、次が成り立つ。ここで$p\coloneqq 37$とし、$c_{i,j}$は$\boldsymbol c_i$の第$j$成分を指す。

$$ \begin{pmatrix} -2s_1 & 2c_{1,1} & 2c_{1,2} & \dots & 2c_{1,64} & p &\cr -2s_2 & 2c_{2,1} & 2c_{2,2} & \dots & 2c_{2,64} & & p \cr \vdots & & & \vdots & & & & \ddots \cr -2s_{64} & 2c_{64,1} & 2c_{64, 2} & \dots & 2c_{64, 64} & & & & p \end{pmatrix} $$

これに右から$(1,x_1, x_2, \dots, x_{32}, k_1, k_2, \dots, k_{32})^T$を掛けると($k_i$は$p$で割ったときの商に対応する整数)、$(-2e_1, -2e_2, \dots, -2e_{32})^T$が出てきて、このベクトルの各成分は0か1となる。

よって「列ベクトル」を基底としたこの格子の小さなベクトルとして、このベクトルが出てきてくれる可能性がある。

実際簡約してみると体感で数回に1回は基底簡約(LLL)で成分の絶対値が1であるベクトルが出てきてくれる。

エラーベクトルが復元出来たのであとはこれを上の式に代入して消して上げると前回のように$2s_i \equiv \langle 2\boldsymbol c_i, \boldsymbol x \rangle \mod 37$の式が得られる。これを$\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 = 32
t = 32
DEBUG = False

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

if DEBUG:
    sc = process(["python3", "shares_v2.py"])
    answer = "test" * 8
else:
    sc = process(["python3", "shares_v2_org.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[:32]:
        v1.append(CHAR_TO_INT[c])

    v1 = vector(Fp, v1)

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

    return v1, 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


while True:
    shares = []
    shares += get_share()
    shares += get_share()

    M = []
    ss = []
    for v, s in shares:
        M.append(2 * vector(Fp, v))
        ss.append(2 * Fp(s))

    ss = vector(Fp, ss)
    M = matrix(Fp, M)
    _M = matrix(ZZ, M)
    _ss = -1 * vector(ZZ, ss)
    _ss = matrix(_ss).transpose()
    pI = P * identity_matrix(2*n)
    _M = _ss.augment(_M).augment(pI).transpose()

    print("[+] LLL")
    found = False
    for e in _M.LLL():
        norm = e.norm()
        if norm != 0 and norm <= 8:
            found = True
            e = vector(Fp, e)
            print(e)
            if answer is not None:
                if M*v_pwd + e == ss:
                    x = M.solve_right(ss - e)
                    print("minus")
                elif M*v_pwd - e == ss:
                    x = M.solve_right(ss + e)
                    print("plus")
                else:
                    print("ha?")
                    exit()

            sig = 0
            for c in e:
                if int(c) == 1:
                    sig = 1
                    break
                if int(c) == P-1:
                    sig = -1
                    break

            if sig == 1:
                x = M.solve_right(ss + e)
            elif sig == -1:
                x = M.solve_right(ss - e)
            else:
                print("ha?")
                exit()

            pwd = ""
            for c in x:
                pwd += INT_TO_CHAR[int(c)]

            print(pwd)

            get_share(pwd)

    if found:
        break

Flag

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

Resources