ahssp

d3pack is a crypto challenge I made in d3ctf.

d3pack

This challenge is based on the affine hidden subset sum problem$^{[1]}$. Given $\mathbf{h},\mathbf{e},p$ satisfying $\mathbf{h}+s\mathbf{e}=\alpha_1\mathbf{x}_1+\alpha_1\mathbf{x}_1+\cdots+\alpha_1\mathbf{x}_1(mod\; p)$, find $s$.

The key to solving this problem is to use the concept of an orthogonal lattice. Given a lattice $\mathcal{L}\subseteq\mathbb{Z}^m$, its orthogonal lattice is defined as :

$\mathcal{L}^{\perp}:=\{\mathbf{v}\in\Z^m|\forall\mathbf{b}\in\mathcal{L},\langle\mathbf{v},\mathbf{b}\rangle=0\}$

The completion of a lattice $\mathcal{L}$ is the lattice $\bar{\mathcal{L}}=(\mathcal{L}^{\perp})^{\perp}$. Clearly, $\mathcal{L}$ is a sublattice of $\bar{\mathcal{L}}$.

Solving method

For this problem, we denote by $\mathcal{L}_{\mathbf{x},\mathbf{e}}$ the lattice generated by $\mathbf{e}$ and the vectors $\mathbf{x}_i$, and by $\mathcal{L}_\mathbf{x}$ the lattice generated by the vectors $\mathbf{x}_i$ only.

To solve this challenge, the first step is to compute the completion lattice $\bar{\mathcal{L}}_\mathbf{x}$.

We write $\mathbf{h}=[h_1,h_2,\mathbf{h}'],\mathbf{e}=[e_1,e_2,\mathbf{e}']$ where $\mathbf{h}',\mathbf{e}'\in\mathbb{Z}^{m-2}$ ,$B=\begin{bmatrix} h_1&e_1\\ h_2&e_2 \end{bmatrix}^{-1}$, and form the lattice as follows:

$\mathcal{L}_0= \begin{bmatrix} p\mathbf{I}_2&\\ -[\mathbf{h}',\mathbf{e}']B&\mathbf{I}_{m-2} \end{bmatrix}$

It can be proved that $\mathcal{L}_0$ is the orthogonal lattice of $[\mathbf{h},\mathbf{e}]$.

Then compute an LLL-reduced basis of $\mathcal{L}_0$ and extract the first $m-n-1$ basis vectors to obtain $\mathcal{L}_{\mathbf{x},\mathbf{e}}^{\perp}$.

Next, we compute $\bar{\mathcal{L}}_{\mathbf{x},\mathbf{e}}=(\mathcal{L}_{\mathbf{x},\mathbf{e}}^{\perp})^{\perp}$ using the BKZ algorithm$^{[1][2]}$, and the first $n$ basis vectors of LLL-reduced basis for $\bar{\mathcal{L}}_{\mathbf{x},\mathbf{e}}$ is $\bar{\mathcal{L}}_\mathbf{x}$.

Finally, we utilize the greedy algorithm described in the article$^{[1]}$ to recover $\mathbf{x}_i$, and then determine $s$ by solving linear equations over the field modulo $q$.

exp:

# https://eprint.iacr.org/2020/461.pdf
from Crypto.Util.number import *


def allpmones(v):
    return len([vj for vj in v if vj in [-1, 0, 1]]) == len(v)


def orthoLattice(B, x0):
    r, m = B.nrows(), B.ncols()
    M = identity_matrix(m).change_ring(ZZ)
    B1 = B[:, :r]
    B2 = B[:, r:]
    V = Matrix(Zmod(x0), B1)
    W = V.inverse()
    M[r:m,:r] = -(W * B2.change_ring(Zmod(x0))).change_ring(ZZ).transpose()
    M[:r, :r] = x0 * identity_matrix(r)
    return M


def allones(v):
    if len([vj for vj in v if vj in [0, 1]]) == len(v):
        return v
    if len([vj for vj in v if vj in [0, -1]]) == len(v):
        return -v
    return None


def recoverBinary(M5):
    lv = [allones(vi) for vi in M5 if allones(vi)]
    n = M5.nrows()
    for v in lv:
        for i in range(n):
            nv = allones(M5[i] - v)
            if nv and nv not in lv:
                lv.append(nv)
            nv = allones(M5[i] + v)
            if nv and nv not in lv:
                lv.append(nv)
    return Matrix(lv)


def kernelLLL(M):
    n = M.nrows()
    m = M.ncols()
    if m < 2 * n:
        return M.right_kernel().matrix()
    K = 2 ^ (m//2) * M.height()

    MB = Matrix(ZZ, m + n, m)
    MB[:n] = K * M
    MB[n:] = identity_matrix(m)

    MB2 = MB.T.LLL().T

    assert MB2[:n, : m - n] == 0
    Ke = MB2[n:, : m - n].T

    return Ke

n = 50
m = 180
p= # from output.txt
h= # from output.txt
e= # from output.txt
e = vector(e)
h = vector(h)
print("n =", n, "m =", m)

E = matrix(ZZ, 2, m, [e.list(), h.list()])
M = orthoLattice(E, p)
t = cputime()
M2 = M.LLL()
print("LLL step1: %.1f" % cputime(t))
MOrtho = M2[: m-n-1]
print(" log(Height,2)=",int(log(MOrtho.height(),2)))
t2 = cputime()
ke = kernelLLL(MOrtho)
print(" Kernel: %.1f" % cputime(t2))
print(" Total step1: %.1f" % cputime(t))

beta = 2
tbk = cputime()
while beta < n:
    if beta == 2:
        M5 = ke.LLL()
    else:
        M5 = M5.BKZ(block_size=beta)

    # we break when we only get vectors with {-1,0,1} components
    if len([True for v in M5 if allpmones(v)]) == n:
        break

    if beta == 2:
        beta = 10
    else:
        beta += 10

print("BKZ beta=%d: %.1f" % (beta, cputime(tbk)))
t2 = cputime()
MB = recoverBinary(M5)
print("  Recovery: %.1f" % cputime(t2))
L = matrix(Zmod(p), MB).transpose()[:n+1]
L = L.augment(-e[:n+1].column())
h_ = h[0:n+1]
a = L^-1*h_

a = [long_to_bytes(ZZ(i)).strip() for i in a]
for block in a:
    if b"d3ctf" in block:
        print(block)

Reference

[1] Coron J S, Gini A. A polynomial-time algorithm for solving the hidden subset sum problem[C]//Advances in Cryptology–CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part II. Cham: Springer International Publishing, 2020: 3-31.(https://eprint.iacr.org/2020/461.pdf)

[2] Phong Q. Nguyen and Jacques Stern. Merkle-hellman revisited: A cryptanalysis of the Qu-Vanstone cryptosystem based on group factorizations. In Advances in Cryptology - CRYPTO ’97, 17th Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 1997, Proceedings, pages 198–212, 1997.
(https://link.springer.com/content/pdf/10.1007/BFb0052236.pdf)