In this task, one had to break an instance of the Goldreich-Goldwasser-Halevi lattice encryption scheme.

The task description reads:

I remember some of the AI engineers saying this was a very unusual cryptosystem. It was used to encrypt and transmit information of the enormous importance. Moreover, it seems there’s no need to share a key before the transmission.

We’ve found some kind of a key file, a ciphertext and the enciphering script itself. Is it possible to decrypt the data?

The script linked in the challenge description uses the following sage function to encrypt a message:

def encrypt(plain_block, W, delta=151):
    n = W.ncols()
    m = vector([ord(ch)  for ch in plain_block])
    r = random_vector(ZZ, n, x=-delta+1, y=delta)
    e = m * W + r
    return e

In that snippet, $W$ is a unimodular square integer matrix loaded from the key.public file. That is, encryption essentially consists of the operation

\[ e \;=\; m\cdot W + r \]

where $r$ is a small random error vector and the message $m$ is suitably interpreted as an integer vector.

Now what seems to be required to obtain $m\cdot W$ (hence $m$) from the disturbed vector $m\cdot W+r$ is solving the closest vector problem (CVP) in the lattice spanned by the columns of $W$. However, this seems to be, to the best of public knowledge, quite hard in general, hence naïvely throwing the given point into sage just heats your CPU for a long time.

However, as described by Phong Nguyen in 1999, the lattice used in the cryptosystem exhibits a rather large gap, that is, the shortest non-zero vector in the lattice is quite long (compared to the error vector $r$).

---

We shall therefore use the so-called embedding technique to solve the challenge. (A less visual description of this method can be found in section 18.3 of this book.) For illustration, we will pretend that our lattice is just $1$-dimensional, with the intuition easily carrying over to arbitrary dimensions. Suppose given the following CVP instance:

Here, lattice points are the black dots, and the point whose closest lattice point we are looking for is red. In the GGH setting, the red point would be $e=m\cdot W+r$ and the lattice would be spanned by $W$.

We can reduce this CVP instance to an instance of the shortest vector problem (SVP) by adding an additional dimension and basis vector to the lattice: The additional basis vector is given by shifting the given point $e$ a little bit $\varepsilon$ (for example $1$) along the new axis. In the following picture, the new basis vector is plotted orange, the lattice obtained this way is gray, and the original (embedded) lattice is still black.

If we now solve the SVP in that lattice and project the shortest vector back to the original lattice (essentially removing the extra coordinate added for the embedding) — let us call this vector $\delta$ —, then the error vector $r$ is just $\delta$, hence we can obtain $m$ as $(e-\delta)\cdot W^{-1}$. Again, a picture might help: The bright blue point is a solution to the SVP in the $2$-dimensional lattice; the dark blue point is its projection $\delta$ to the original lattice; and the green point on the right is the solution to the original CVP instance obtained by translating the given red point by $-\delta$.

---

Speaking code, this is surprisingly easy: Reusing the read_* functions from crypt.py, the attack is fully implemented in sage within a few lines:

#!/usr/bin/env sage
from crypt import read_mat, read_ciphertext
from sage.modules.free_module_integer import IntegerLattice

W = read_mat('key.public')
e = read_ciphertext('ciphertext')

B = W.stack(e).augment(vector([0] * W.ncols() + [1]))
d = IntegerLattice(B).shortest_vector()
print('d = {}'.format(d))

m = W.solve_left(e - d[:-1])
print('m = {}'.format(m))

print('\n    --> {}'.format(''.join(map(chr, m))))

After only a few seconds, this prints the flag

$ ./pwn.sage
d = (-4, -2, 4, -1, -2, -3, 2, -3, 3, 2, 0, 0, -2, -1, -4, 1, 2, -3, 2, 2, -2, -4, 0, 3, -4, -3, -1, -4, 3, 4, -4, -2, -4, -1, -2, -4, 2, -1, 1)
m = (86, 111, 108, 103, 97, 67, 84, 70, 123, 71, 71, 72, 95, 117, 115, 101, 115, 95, 66, 97, 98, 97, 105, 95, 97, 110, 100, 95, 104, 97, 116, 101, 115, 95, 76, 76, 76, 125)

    --> VolgaCTF{GGH_uses_Babai_and_hates_LLL}