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).

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

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

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

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

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}:

```
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`

.