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

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

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

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

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

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

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

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

.