Lattice-Based Cryptanalysis

12 minute read

Hey there, it is been a long time since my last post. In this post, I will walk through a challenge that took me lots of time to solve. It is the LOL challenge from 34C3 CTF. Actually, the ctf ended long time ago, I didn’t play there. Nevertheless, I was checking past CTFs challenges and this challenge caught my eye. It took me about a week to solve this challenge.

Examining the challenge

The challenge comes in the form of encrypted file and source code for encryption algorithm as well as a compiled version. This is the pseudo code for the encryption algorithm:

function secure_word(mersenne_twister mt):
    random: 64 bit integer
    for (i = 0; i < 64; i = i + 1)
        random |= (mt.next_random_number() & 1) << i;
    return random;

function encrypt(string Message):
    M = vector where each character in Message is element in M
    L = length of the vector M
    constant_mt = mersenne twister with seed (0)
    A = 64xL matrix
    for row in A.rows:
        for column in A.columns:
            A[row][column] = constant_mt.next_random_number()
    K = vector of length 64
    secure_mt = mersenne twister with secret random 64bit seed
    for (i = 0; i < K.length; i = i+1)
        K[i] = secure_word(secure_mt)
    CipherText = A*M+k
    return length of M and the CipherText

Note that pseudo code is equivalent to the provided source code under the following assumptions:

  1. All Mersenne twister instances are the MT19937 64bit version
  2. All calculations are mod
  3. Vector here means a Matrix of dimensions N×1 not to be confused with vector data structure.

We notice that CipherText will always be of fixed length (vector of 64 Integers) regardless of the length of the message. As result, we can tell that the provided algorithm isn’t bijective, so it doesn’t sound like an encryption algorithm. Due to pigeonhole principle problems will happen when the length of Message is greater than or equal to 64. After checking the provided encrypted file, we found that the length of the message is 37.

Another notice is that the encryption function itself. First the vector is of length 37 and the vector is of length 64. So it can’t be solved by means of solving system of linear equations. However, it can be solved as closest vector problem using lattice methods

What the heck is a lattice?

For the sake of our write-up, we can think of a lattice as an N-dimensional uniform grid of points, this picture shows a three dimensional lattice (the blue dots) generated by SageMath.

3D lattice generated by sage

Normally it is a bit of challenge to visualize anything greater than 3 dimensions but mathematics have no problem dealing with higher dimensions well… practically everything.

One notable property about a lattice is that it is always possible to draw a sphere around any lattice point that only contains that lattice point. (of course, this generalizes to N-dimensional lattices and respective higher dimensional spheres). That visual representation of a lattice is usually not very helpful for anything but understanding the concepts. In order to do most if not all of the cryptanalysis, we use other representation, called Lattice Basis. Lattice basis is a group of vectors where any other lattice point can be formed by linear combination of them. More formally, a lattice can be defined in terms of lattice basis as the following as taken from Daniele Micciancio Lectures

let be linearly independent vectors in . The lattice generated by is defined by:

We will not always stick to the exact definition, In some examples, each lattice base will be represented as row (unlike the definition which represented it as a column). Best way to learn is by examples, let’s take for example the following lattice basis:

We can generate some points in these lattice using the following sage code

b = matrix([
	[3, -18, -2],
	[14, 4, 0],
	[-5, 12, -15]
])
point_list = []
for i in range(-5,5):
    for j in range(-5,5):
        for k in range(-10,10):
            x = vector([i,j,k])
            point_list.append(a*x)

point(point_list)

In fact, this is the exact code I used to generate the lattice points you saw in the above picture.

Another important feature of lattice basis is that it is not unique, given any lattice, there are infinitely many basis that can form that exact same lattice in general you can do the following to any vector in the Basis yet preserve the same lattice:

  1. Replace the vector with
  2. Replace the vector with where and

Closest Vector Problem(CVP)

According to Daniele Micciancio Lectures, the closest vector problem is defined by:

Given a basis and a target vector find lattice vector closest to .

Understanding CVP is crucial in order to solve the LOL crypto challenge, so let’s put it in layman terms. If you have any point (even if it doesn’t belong to the lattice), the goal is finding the nearest lattice point close that original random point.

I spent a long time misunderstanding the problem as given a lattice point ONLY, the goal is finding the nearest lattice point close that original lattice point. WHICH IS BY THE WAY WRONG. I learned this the hard way, I won’t spoil the fun now! I will explain the implication of my misunderstanding at the challenge’s solution section. It was so ridiculous that I couldn’t reason about it!

CVP is NP-hard, tldr; this is bad if we are trying to solve CVP. However, there is an approximation algorithm called Babai’s nearest plane algorithm. This algorithm provides an approximation that can be exponentially (in the dimensions of the lattice)far from the closest vector. Practical, Babai’s algorithm provides results are much from the exponential upper bound. Babai’s algorithm has rigorous proofs that determine when will it work well, and when will the results be useless. Put the maths aside, here is the sage code for Babai’s nearest plane algorithm.

def Babai_CVP(Lattice, target):
    M = Lattice.LLL()
    G = M.gram_schmidt()[0]
    diff = target
    for i in reversed(range(M.nrows())):
        diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
    return target - diff

Note that for this algorithm to work correctly the given lattice must follow the lattice basis definition (each vector must be represented by a column).

Solving The LOL Challenge

Back to the original challenge. As a quick reminder, the encryption function looks like this:

  • is the ciphertext represented by a vector of length .
  • is a constant matrix of dimensions filled by MT19937-64 random numbers row by row.
  • is the plaintext vector, we know that its length is .
  • is a vector of length , each element in that vector is 64bits of Mersenne Twister random numbers truncated to the LSB and concatenated to form a 64bit.

So let’s form a lattice basis that looks like this:

This Lattice has bases each of which has dimensions. Our goal here is to find an interesting lattice point, here is what are we looking for, A point that can give us any clue about the message. Let’s take for example the following lattice point

I was stuck here, I was trying to get a close point that can be a lattice point and I know its components. But later I realized that it doesn’t have to be a lattice point and actually, we can form a target vector that is very close to .

So the plan is to inject the lattice defined by and the target vector into Babai’s CVP approximation and hope that we get thelattice point . If everything worked well, we will be able to retrieve the message from .

from sage.all import *
from struct import *

def Babai_CVP(Lattice, target):
    M = Lattice.LLL()
    G = M.gram_schmidt()[0]
    diff = target
    for i in reversed(range(M.nrows())):
        diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
    return target - diff

n = 37
k = 64
M = 2^64

C = open("/home/oddcoder/lol_crypto/flag.txt.enc").read()[8:]
random_nums = [int(x) for x in open("/home/oddcoder/lol_crypto/randoms").
        read().split("\n")[:-1]]

c = vector(k*[0])

for i in range(k):
    c[i] = unpack("=Q", C[0:8])[0]
    C = C[8:]

A = matrix(k,n)

for i in range(k):
    for j in range(n):
        A[i, j] = random_nums[i*n+j]

B = matrix(n+k,n+k)

for i in range(k):
    B[i,i] = M/4

for i in range(k):
    for j in range(n):
        B[i,k+j] = A[i][j]

for i in range(k, n+k):
    B[i,i] = 1

t = vector(ZZ, [0]*(n+k))

for i in range(k):
    t[i] = c[i]

P = Babai_CVP(B.transpose(),t)
print "".join(chr(c) for c in P[k:])

The randoms file content is generated using this C++ code:

#include <bits/stdc++.h>
using namespace std;

struct RNG {
    random_device dev;
    mt19937_64 rng;
    RNG(uint64_t seed) : rng(seed) {}
    uint64_t next_qword_fast() {
        return rng();
    }
};

int main() {
    RNG rng(0);
    for (int i = 0;i < 64*37;i++)
        cout << rng.next_qword_fast() << endl;
}

And The content of emerges 34C3_l3nstra_w0uld_h4ve_b33n_s0_proud.

Leave a Comment