This is my first time solving a challenge with LLL. I started with no understanding of lattices and filled a notebook with diagrams and failed attempts at building the lattice I needed, so I’m going to spend this writeup walking through the basics and explaining how you too can construct lattices to solve your problems.

Schnorr Signatures

First some background on the challenge. Here is the script we are given as well as the output of running the script.

We can see that this challenge uses schnorr signatures to sign the message, and our goal is to recover the private key x.

Schnorr signatures are very similar to DSA and work like this:

  • p is public large prime
  • x is private key, \(y=g^x\) is public key
  • Choose a random secret integer k
  • Let \(e \equiv H(g^k\|M) \pmod{p}\)
  • Let \(s \equiv k - x * e \pmod{p-1}\)
  • Signature is (s, e)

Like in DSA, if k is repeated it is trivial to recover the private key:

s\(_1\) - s\(_2\) = x*(e\(_2\) - e\(_1\))

In this challenge, k is not chosen randomly. Instead, we have 6 messages that are signed with ks that are known strings xor a random pad. So we don’t know what k is, but we know that the last 12 bytes of all of the k’s are the same. In fact, we even have one pair that shares the first 8 and last 12 bytes, and another pair that shares the first 9 and last 12 bytes.

Sources

There are many papers that show that even if k has a small bias it is possible to break DSA given a few signatures.

This presenation discusses attacking Schnorr signatures given that all of the LSBs are zero, which is not quite our case. I also did not manage to understand it anywhere near well enough to implement.

This paper discusses attacking DSA given shared LSB (or MSB) of k. The DSA section of this paper is similar and presents some more lattices that allowed me to more or less understand both papers. However, the differences between DSA and Schnorr signatures still gave me trouble and I wasn’t able to solve the challenge.

Finally, I found this paper which solves a more complicated problem (DSA with nonces generated with an LCG) as well as this writeup for the DSA-LCG problem. I managed to adapt the techniques from this paper to the challenge and solve the problem.

Intro to lattices

So what is a lattice and why is it interesting?

A lattice is similar to a linear span of vectors. However - instead of multiplying each base vector by any number, we can only multiply it by (positive or negative) integers.

So given the vectors \(\vec{a}, \vec{b}\) the vector \(2\vec{a} + \vec{b}\) is in the lattice spanned by the vectors, but the vector \(0.5\vec{a}\) is not (unless it also happens to equal some integer multiple of \(\vec{a}\) and \(\vec{b}\)). This means we can imagine the lattice of a group of n dimensional vectors as a set of the n dimensional points (or vectors) that can be reached by adding and subtracting those vectors. A lattice in the euclidean plane from wikipedia:

A group of points that could be the lattice of two vectors

Lattices can be expressed as matrices where the rows are the base vectors of the lattice - for some reason the convention is to use rows instead of columns, although some papers, notably the last one listed, do it in the other way. Sage uses rows to express vectors so that is the notation we will use.

Find our equations

Let’s get back to our problem. We have six signed messages \(e_1..e_6, s_1..s_6\). In each message \(s_i \equiv k_i - x * e_i \pmod{p-1}\)

Let’s just take the two pairs of k’s that have the most matching bits. We know that \(k_0\) and \(k_4\) share 12 bytes = 96 bits at the end and 9 bytes = 72 bits at the beginning, so differ by only the middle 88 bits. Therefore \(k_4 - k_0 = 2^{96}\widetilde{k_0}\) where \(\widetilde{k_0}\) is less than \(2^{88}\). Similarly, \(k_3 - k_1 = 2^{96}\widetilde{k_1}\) where \(\widetilde{k_1}\) is less than \(2^{96}\).

Let’s look at \(s_4 - s_0\):

\[s_4 - s_0 \equiv (k_4 - x * e_4) - (k_0 - x * e_1) = (k_4 - k_0) - x * (e_4 - e_0) = 2^{96}\widetilde{k_0} - x * (e_4 - e_0)\]

Likewise, \(s_3 - s_1 \equiv 2^{96}\widetilde{k_1} - x * (e_3 - e_1)\)

The only unknowns here are x, \(\widetilde{k_0}\), and \(\widetilde{k_1}\) and we know that \(\widetilde{k_0}\) and \(\widetilde{k_1}\) are “small” (relative to x and q which are 255 bits)

Lattice fun

Let’s take the following lattice:

\[\begin{bmatrix} 1 & 0 & 0 & 0 & s_4 - s_0 & s_3 - s_1\\ 0 & 1 & 0 & 0 & e_4 - e_0 & e_3 - e_1\\ 0 & 0 & 1 & 0 & 2^{96} & 0\\ 0 & 0 & 0 & 1 & 0 & 2^{96}\\ 0 & 0 & 0 & 0 & p - 1 & 0\\ 0 & 0 & 0 & 0 & 0 & p - 1\\ \end{bmatrix}\]

Let us prove that the vector \(\begin{pmatrix}1 & x & -\widetilde{k_0} & -\widetilde{k_1} & 0 & 0\end{pmatrix}\) is in the lattice - we show that there exist \(\begin{pmatrix}a & b & c & d & e & f\end{pmatrix}\) such that

\[a\begin{pmatrix}1 \\ 0 \\ 0 \\ 0 \\ s_4 - s_0 \\ s_3 - s_1\end{pmatrix} + b\begin{pmatrix}0 \\ 1 \\ 0 \\ 0 \\ e_4 - e_0 \\ e_3 - e_0 \end{pmatrix} + ... = \begin{pmatrix}1 \\ x \\ -\widetilde{k_0} \\ -\widetilde{k_1} \\ 0 \\ 0\end{pmatrix}\]

For:

\[a=1, b=x\\c=-\widetilde{k_0}, d=-\widetilde{k_1}\\e=\frac{(s_4-s_0)+x(e_4-e_0)-2^{96}\widetilde{k_0}}{p-1}\\f=\frac{(s_3-s_1)+x(e_3-e_1)-2^{96}\widetilde{k_1}}{p-1}\]

this equation works because of the equation we found on the s’s before (which is the same reason e and f are whole numbers).

Note that we don’t know \(\begin{pmatrix}a & b & c & d & e & f\end{pmatrix}\) or the values of this vector, but we do know all of the base vectors of the lattice. If we could somehow find our vector given the lattice we would have x and win the challenge.

The magic is LLL - well, almost. LLL is an algorithm that takes a lattice and returns an equivalent lattice where the bases are “nearly minimal”. What many uses of lattices attempt to do is come up with a lattice that contains a vector we are looking for, where that vector is “very small” in the lattice, and hope that the vector is one of the bases that will show up using LLL. In our current lattice this is not the case (because \(\lvert v \rvert\) > x which is “big”) but I couldn’t get this to work no matter how I played with the lattice.

Instead, we can use an algorithm called Babai’s algorithm which takes a lattice and a target vector and returns a vector that is in the lattice that is “nearly closest” to that vector (finding the closest vector is NP-Hard). Under the cover Babai uses LLL but we’ll ignore the hard math. I copied Babai’s algorithm directly from the CTF writeup above.

So let’s take a guess for the target vector and call Babai’s algorithm! We know that \(\widetilde{k_0}\) is 88 bits long and \(\widetilde{k_1}\) is 96 bits long and x is smaller than p. So let’s guess that they are all half of their maximum value and call Babai with a target vector of

\[\begin{pmatrix}1 & \frac{p}{2} & -2^{87} & -2^{95} & 0 & 0\end{pmatrix}\]

and we get… absolute garbage:

\[\begin{pmatrix}19004404641857448369721625 \\ 74491455700632367250308508790259224961771359766159068028564605514345385168096 \\ -177809793803397197192283982 \\ -39622479127730852821173525087 \\ 14988491028316575056440150 \\ -21612329887833786013099171\end{pmatrix}\]

We know this is not the vector we are looking for because the first value is not 1 and the last two are not 0.

The problem here is that \(\frac{p}{2}\) and even \(2^{88}\) are big numbers. That means the length of our target vector is really big and there are lots of vectors that are relatively close to it. If our target vector was smaller, our chance of finding it exactly would be much higher.

Luckily there is a trick found in the last paper above that allows us to use a small target vector - we divide the 1s in the lattice base by our “guess” of the value we are looking for. So our new lattice will be:

\[\begin{bmatrix} 1 & 0 & 0 & 0 & s_4 - s_0 & s_3 - s_1\\ 0 & \frac{2}{p-1} & 0 & 0 & e_4 - e_0 & e_3 - e_1\\ 0 & 0 & \frac{1}{2^{87}} & 0 & 2^{96} & 0\\ 0 & 0 & 0 & \frac{1}{2^{95}} & 0 & 2^{96}\\ 0 & 0 & 0 & 0 & p - 1 & 0\\ 0 & 0 & 0 & 0 & 0 & p - 1\\ \end{bmatrix}\]

We can now see that the vector:

\[\begin{pmatrix}1 & \frac{2x}{p-1} & \frac{-\widetilde{k_0}}{2^{87}} & \frac{-\widetilde{k_1}}{2^{95}} & 0 & 0\end{pmatrix}\]

is in our new lattice and it’s size is approximately \(\lvert v \rvert = \sqrt{1+1+1+1} = 2\). This is very small relative to a lattice whose bases include values of size p.

It took me a while to wrap my mind around this trick. We are doing actual division here, not division mod (p-1). Our lattice is still integer multiplication of our bases, but now the elements of our bases also include fractions. It seems cheating but it works.

So now we are looking for a vector close to \(\begin{pmatrix}1 & 1 & -1 & -1 & 0 & 0\end{pmatrix}\) that is in our lattice. Again we run Babai’s algorithm and we get:

\[\begin{pmatrix}1 \\ \frac{111574259168847904430349592677759764400719856452517867150959157414355914856867}{74491455700632367250308508790259224961771359766159060737998863801337906757431} \\ \frac{-3943461667509540392813061}{38685626227668133590597632} \\ \frac{5257638527947030812735243263}{39614081257132168796771975168} \\ 0 \\ 0\end{pmatrix}\]

Multiplying the second item by \(\frac{p-1}{2}\) gives us x=111574259168847904430349592677759764400719856452517867150959157414355914856867, and we can confirm that pow(2, x, p) == y and decrypt the flag to obtain rarctf{zZZzZZZZzzZZZzzZZZZZZzZzzzZzzZZzZzzZZzzzZZZZzZZz_s0rry_1_w4s_t00_t1r3d_t0_c0me-up_w1th_4n_4ctual-fl4g_7686f36b65}

Constructing the lattice

Before we go a word about how we constructed our lattice. The entire magic of LLL and Babai happens because we construct a lattice in which there is a “good” vector for us. The innovation of many papers that solve problems with lattices is coming up with appropriate lattices and target vectors, but they often share similar structure. I think a good way to construct your own lattices is to read some of the papers and understand how their lattices work, but there are a few basic forms:

The one we used I didn’t see exactly anywhere else, but it is simple to repeat. Given a number of equations of the form:

\[a_i + b_i * x + c_i * y + d_i * z \equiv 0 \pmod{n}\]

we build a lattice that looks like this:

\[\begin{bmatrix} 1 & 0 & 0 & 0 & a_0 & a_1 & ...\\ 0 & 1 & 0 & 0 & b_0 & b_1 & ...\\ 0 & 0 & 1 & 0 & c_0 & c_1 & ...\\ 0 & 0 & 0 & 1 & d_0 & d_1 & ...\\ 0 & 0 & 0 & 0 & n & 0 & ...\\ 0 & 0 & 0 & 0 & 0 & n & ...\\ ...\\ \end{bmatrix}\]

which contains the vector \(\begin{pmatrix}1 & x & y & z & 0 & 0 & 0\end{pmatrix}\) . Don’t forget the division trick to obtain a smaller target vector

The rows should extend so that the number of n’s match the number of equations

We could also ignore our constants and use this lattice:

\[\begin{bmatrix} 1 & 0 & 0 & b_0 & b_1 & ...\\ 0 & 1 & 0 & c_0 & c_1 & ...\\ 0 & 0 & 1 & d_0 & d_1 & ...\\ 0 & 0 & 0 & n & 0 & ...\\ 0 & 0 & 0 & 0 & n & ...\\ ...\\ \end{bmatrix}\]

which contains \(\begin{pmatrix}x & y & z & a_0 & a_1 & ...\end{pmatrix}\) - that is, we moved our constants from the lattice basis to the target vector. Even though this gives us pretty large elements in our target vector, this lattice can also be used to solve the challenge (after using the division trick to reduce x y and z)

Another construction which works for monic equations (where our variable that changes every equation is multiplied by 1) is:

\(a_0 + b_0 * x + y_0 \equiv 0 \pmod{n}\) \(a_1 + b_1 * x + y_1 \equiv 0 \pmod{n}\)

build this lattice:

\[\begin{bmatrix} 1 & 0 & a_0 & a_1 & ...\\ 0 & 1 & b_0 & b_1 & ...\\ 0 & 0 & n & 0 & ...\\ 0 & 0 & 0 & n & ...\\ ...\\ \end{bmatrix}\]

and then the vector \(\begin{pmatrix}1 & x & y_0 & y_1 & ...\end{pmatrix}\) is in our lattice. This vector is not particularly small and there is no way to make the y’s smaller but some papers use it to great effect (in particular the first paper on breaking DSA with lattices).

The code

Here is my final solution in sage

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha224

p =  148982911401264734500617017580518449923542719532318121475997727602675813514863
g =  2
y =  99943368625476277151400768907519717344447758596311103260066302523387843692499
data = [
 (82164720827627951718117576622367372918842412631288684063666489980382312886875, 20555462814568596793812771425415543791560033744700837082533238767135),
 (121728190859093179709167853051428045020048650314914045286511335302789797110644, 18832686601255134631820635660734300367214611070497673143677605724980),
 (146082371876690961814167471199278995325899717136850705507399907858041424152875, 17280327447912166881602972638784747375738574870164428834607749483679),
 (70503066417308377066271947367911829721247208157460892633371511382189117698027, 18679076989831101699209257375687089051054511859966345809079812661627),
 (129356717302185231616252962266443899346987025366769583013987552032290057284641, 2084781842220461075274126508657531826108703724816608320266110772897),
 (12183293984655719933097345580162258768878646698567137931824149359927592074910, 15768525934046641405375930988120401106067516205761039338919748323087),
]

ss = [d[0] for d in data]
es = [d[1] for d in data]

def Babai_closest_vector(B, target):
    # Babai's Nearest Plane algorithm
    M = B.LLL()
    G = M.gram_schmidt()[0]
    small = target
    for _ in range(1):
        for i in reversed(range(M.nrows())):
            c = ((small * G[i]) / (G[i] * G[i])).round()
            small -= M[i] * c
    return target - small

B = Matrix(
    [
        [1,0,0,0,(ss[4]-ss[0]), (ss[3]-ss[1])],
        [0,2/(p-1),0,0,(es[4]-es[0]), (es[3]-es[1])],
        [0,0,1/(1<<87),0,1<<96,0],
        [0,0,0,1/(1<<95),0,1<<96],
        [0,0,0,0,p-1,0],
        [0,0,0,0,0,p-1],
    ])

Y = vector([1, 1, -1, -1, 0, 0])
W = Babai_closest_vector(B, Y)
x = W[1] * (p-1) / 2

print(W)
print(x)
print(pow(2,x,p) == y)

key = sha224(long_to_bytes(x)).digest()[:16]
ct =  bytes.fromhex("e426c232b20fc298fb4499a2fff2e248615a379c5bc1a7447531f8a66b13fb57e2cf334247a0589be816fc52d80c064b61fa60261e925beb34684655278955e0206709f95173ad292f5c60526363766061e37dd810ee69d1266cbe5124ae18978214e8b39089b31cad5fd91b9a99e344830b76d456bbf92b5585eebeaf85c990")
iv = bytes.fromhex("563391612e7c7d3e6bd03e1eaf76a0ba")
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(ct)
print(flag)