VolgaCTF – XXY

The challenge is presented with the following description:

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 key file consisted of a file with signed 180(?)-bit integers and a ciphertext.

#!/usr/bin/env sage
from sage.all import *

hRR = RealField(10000)

def read_mat(name):
    with open(name, 'r') as f:
        data = f.read()
        data = [map(int, s.split(' '))  for s in data.split('\n')]
        n = len(data)
        M = MatrixSpace(ZZ, n, n)(data)
        return M

def read_ciphertext(ciphertext_file_name):
    with open(ciphertext_file_name, 'r') as f:
        data = f.read()
        e = vector(map(int, data.split(' ')))
        return e

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

def decrypt(e, V, W):
    n = V.ncols()
    VV = MatrixSpace(hRR, n, n)(V)
    t = vector([int(round(i))  for i in VV.solve_left(e)])
    v = t * V
    m = W.solve_left(v)
    ciphertext_block = ''.join([chr(i)  for i in m])
    return ciphertext_block

The signed integers forms a 38 \times 38 matrix \mathbf{W}, which in this case is the public key. The ciphertext \mathbf{e} is formed by computing \mathbf{m}\mathbf{W} + \mathbf{e}, were \mathbf{m} is the message and \mathbf{r} is a random error vector with entries in the range [-\delta+1,\delta-1]. Now, we could use the \textsf{decrypt} function using only the public key. The problem is that it is very ill-conditioned and the basic vectors are not orthogonal and would not produce a correct result.

So, what can we do to remedy the problem? We can use the LLL algorithm, which tranforms the matrix into a very nicely conditioned matrix using no additional information what-so-ever. This is actually the whole key to the attack. Using Sage, we compute the LLL-reduced form, \mathbf{V}' and can then easily obtain the flag by feeding the \textsf{decrypt} function with the known \mathbf{e}, \mathbf{W} and the estimate \mathbf V'. Doing so, outputs the flag VolgaCTF{GGH_uses_Babai_and_hates_LLL}.


One thought on “VolgaCTF – XXY

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s