Categories

# PlaidCTF 2015 – Crypto/Lazy

My knapsack brings all the boys to the yard, and they’re like “that crypto is hard” (note: this flag is not in the flag{} format)

PlaidCTF 2015 – Crypto/Lazy

The challenge provided a few files: pubkey.txt, ciphertext.txt, knapsack.py, utils.py. After inspecting the code, it seems that the contents of ciphertext.txt was encrypted using Merkle-Hallman knapsack (MHK) cryptography, which was found to be insecure by cryptographer Adi Shamir in 1984.

The MHK cryptosystem uses a sequence of natural numbers $\textbf{s}=\langle s_1, s_2, \ldots, s_n\rangle\in\mathbb{N}^n$ that has the super-increasing property (that every term is greater than the sum of all preceding terms).

s_{k+1} > \sum_{j=1}^k s_j

We also choose two random integers $r$ and $q$ that are coprime (that their gcd is 1) and

q > \textbf{1}^T\textbf{s}

where $\textbf{1}$ is the $1$-vector. We use $r$ and $q$ to hide the super-increasing property by computing a vector $\textbf{b}$ where

\begin{aligned} \textbf{b}&=\langle b_1, b_2, \ldots, b_n\rangle\\ b_i&\equiv rs_i \mod q\quad(b_i\in\textbf{b}) \end{aligned}

Our public key is then $\textbf{b}$ and the private key is $(s, r, q)$. For some plaintext $m$, we perform encryption by computing its bitwise dot product with $\textbf{b}$:

where $m_i \in \textbf{m}$ is the $i$-th bit in $m$. To decrypt, we find the modulo multiplicative inverse of $r\text{ }(\text{mod }q)$ and compute

\begin{alignedat}{2} c^\prime &\equiv cr^{-1} &\mod q\\ &\equiv (\textbf{b}^T\textbf{m})r^{-1}&\mod q\\ &\equiv \left(\sum_{i=1}^n b_im_i\right)r^{-1} &\mod q\\ &\equiv \sum_{i=1}^n m_i(b_ir^{-1}) &\mod q\\ &\equiv \sum_{i=1}^n m_is_i &\mod q\\ &\equiv \textbf{m}^T\textbf{s}\\ \text{where}\\ &b_ir^{-1}\equiv rs_ir^{-1}\equiv s_i &\mod q \end{alignedat}

and we can recover each bit of the message $\textbf{m}$ by solving the multidimensional subset sum problem, which is easy since $\textbf{s}$ is super-increasing: we check for the first $s_1 \leq c^\prime$ and compute $c^{\prime\prime}=c^\prime-s_1$ and repeat until we get all $s_i \in \textbf{s}$.

To carry out an attack on the given ciphertext we follow the description provided by Adi Shamir in his paper. We know that the ciphertext $c$ is in the form

\begin{aligned} c &= \textbf{b}^\text{T}\textbf{m}\\ &= \sum_{i=1}^n b_i m_i\\ &= b_1m_1 + b_2m_2 + \ldots + b_nm_n \end{aligned}

We read in the ciphertext $c$ as a large integer and the public key as a comma-delimited string, which we convert into a list of integers. Then, we use SageMath to construct the lattice in the ring of integers $\mathbb{Z}$:

L = \begin{bmatrix} 2 & 0 & 0 & \ldots & 0 & b_1 \\ 0 & 2 & 0 & \ldots & 0 & b_2 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \ldots & 2 & b_n \\ 1 & 1 & 1 & \ldots & 1 & c \\ \end{bmatrix}
Z = IntegerRing()
L = MatrixSpace(Z, len(pubkey))(2)
row = matrix(Z, 1, len(pubkeys), [1 for k in pubkey]
col = matrix(Z, len(pubkeys)+1, pubkeys+[c]]
L = L.stack(row).augment(col)

and compute the reduced basis lattice $R$ using the Lenstra-Lenstra-Lovasz (LLL) algorithm by invoking R = L.LLL(). This helps us solve the multidimensional subset sum problem. We are interested in a row that consists only of $\pm 1, 0$. We then map $1 \mapsto 0$ and $-1 \mapsto 1$ to yield our original message bitvector $\textbf{m}$.

R = L.LLL()
m = [row for row in R for cell in row if cell in [1,0,-1]][0]
m = [1 for v in m if v == -1 else 0]
m = int(reversed(''.join([str(v) for v in m])), 2)
m = hex(m)[2:][:-1]
print(m.decode('hex'))

which gives us the flag lenstra_and_lovasz_liked_lattices.