PlaidCTF 2015 – Crypto/Lazy – Rayden & Security

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 [latex]\textbf{s}=\langle s_1, s_2, \ldots, s_n\rangle\in\mathbb{N}^n[/latex] 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 [latex]r[/latex] and [latex]q[/latex] that are coprime (that their gcd is 1) and

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

where [latex]\textbf{1}[/latex] is the [latex]1[/latex]-vector. We use [latex]r[/latex] and [latex]q[/latex] to hide the super-increasing property by computing a vector [latex]\textbf{b}[/latex] 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 [latex]\textbf{b}[/latex] and the private key is [latex](s, r, q)[/latex]. For some plaintext [latex]m[/latex], we perform encryption by computing its bitwise dot product with [latex]\textbf{b}[/latex]:

\text{Encryption:}\quad c = \textbf{b}^\text{T}\textbf{m}

where [latex]m_i \in \textbf{m}[/latex] is the [latex]i[/latex]-th bit in [latex]m[/latex]. To decrypt, we find the modulo multiplicative inverse of [latex]r\text{ }(\text{mod }q)[/latex] 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 [latex]\textbf{m}[/latex] by solving the multidimensional subset sum problem, which is easy since [latex]\textbf{s}[/latex] is super-increasing: we check for the first [latex]s_1 \leq c^\prime[/latex] and compute [latex]c^{\prime\prime}=c^\prime-s_1[/latex] and repeat until we get all [latex]s_i \in \textbf{s}[/latex].

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 [latex]c[/latex] 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 [latex]c[/latex] 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 [latex]\mathbb{Z}[/latex]:

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 [latex]R[/latex] 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 [latex]\pm 1, 0[/latex]. We then map [latex]1 \mapsto 0[/latex] and [latex]-1 \mapsto 1[/latex] to yield our original message bitvector [latex]\textbf{m}[/latex].

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.

Leave a Reply Cancel reply