a8888a   a8888a  dP                
                  d8' ..8b d8' ..8b 88                
.d8888b. 88d888b. 88 .P 88 88 .P 88 88d888b. d888888b 
88'  `88 88'  `88 88 d' 88 88 d' 88 88'  `88    .d8P' 
88.  .88 88    88 Y8'' .8P Y8'' .8P 88.  .88  .Y8P    
`8888P88 dP    dP  Y8888P   Y8888P  88Y8888' d888888P 
     .88                                              
 d8888P

Plaid CTF 2015 - Lazy Writeup

 21 April 2015 by nwert

We were provided with the files knapsack.py, utils.py, ciphertext.txt and pubkey.txt. Before having any look at the code, I already suspected that this might be about the Merkle-Hallman knapsack cryptosystem [1] and after a quick one I was proven right. In principle the idea with this system is to generate a superincreasing sequence of numbers \((x_i)\), \(x_i \in \mathbb{N}_{>0}\), thus

$$\forall j: x_j > \sum_{i=0}^{j-1} x_i.$$

To hide the superincreasing property we further choose a random \(r\) and a modulus \(N\) and compute the sequence \((y_i)\) where \(y_i = rx_i \mod N\). The public key is then given by \((y_i)\) and the private key by \(((x_i), r, N)\). Now to encrypt a message \(m\) we split it up in its bits \((b_i)\) and compute \(c = \sum_i y_i b_i\). Decryption is then done by first computing \(c' = c r^{-1} \mod N\) and recovering \((b_i)\) from \(c'\), which is possible due to the superincreasing nature of \((x_i)\). Thus we would check for the first \(x_i \leq c'\) yielding the first bit, then update \(c'' = c'-x_i\) and start anew.

Fortunately for us, attacking the scheme is not too hard either [2]. We can use lattice methods to solve the equation

$$c = y_1b_1 + y_2b_2 + \cdots + y_Nb_N$$

for the \(b_i \in \{0,1\}\). This is done by considering the lattice

$$ \begin{pmatrix} y_1 & 1 & 0 & \cdots & 0 \\ y_2 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ y_N & 0 & 0 & \cdots & 1 \\ -c & 0 & 0 & \cdots & 0 \end{pmatrix} $$

and using LLL reduction. After a bit of Sage, finding the right row (basically looking for zeroes and ones) and guessing some non-recovered characters the flag read lenstra_and_lovasz_liked_lattices.

References

  1. Merkle, Ralph; Hellman, Martin (1978). Hiding information and signatures in trapdoor knapsacks.
  2. Shamir, Adi (1984). A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem.