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.