⬅ BACK
DownUnderCTF 2021 Writeups

Thank you to everyone who played DownUnderCTF 2021. I hope you enjoyed the challenges :)

Here are writeups for the hard crypto challenges I wrote.

All of the challenge files and solve scripts can be found here.

ChallengeTagsSolves
yadlpcrypto14
power signcrypto14
1337crypt v2crypto3
Substitution Cipher IIIcrypto1

yadlp

This challenge follows a similar structure to a commonly seen style of crypto CTF challenges that involve solving the discrete logarithm problem in some group other than the usual (Z/pZ)×(\mathbb{Z}/p\mathbb{Z})^\times. The general approach is to figure out some information about what the group elements are like, and then try to find an isomorphism from the group to a group where we can easily solve the discrete logarithm problem.

Group Structure Part I

We'll see that the group we are dealing with in the challenge is the set of points on some hyperbola over Fp\mathbb{F}_p. Although the operations defined in the handout code are called "addition" and "multiplication", it'll be helpful to use multiplication and exponentiation notation. When we say "elements", we usually mean points on the hyperbola, which are represented as tuples (x,y)Fp×Fp(x, y) \in \mathbb{F}_p \times \mathbb{F}_p with addition operation defined as:

(x1,y1)(x2,y2)=(x1x2+Dy1y2,x1y2+x2y1+2y1y2)(x_1, y_1) \cdot (x_2, y_2) = (x_1 x_2 + D y_1 y_2, x_1 y_2 + x_2 y_1 + 2 y_1 y_2)

The rand_element function gives us even more information about elements in this group. In fact, we can use it to get an explicit relation that all elements satisfy. The function first generates a random xFpx \in \mathbb{F}_p, then computes yy as

y=x+x2(D+1)DDy = \frac{x + \sqrt{x^2 (D+1) - D}}{D}

Rearranging, we get

(Dyx)2=x2(D+1)D    D2y22Dxy+x2=Dx2+x2D    Dx2+2DxyD2y2=D    x2+2xyDy21(modp)since D0\begin{aligned} (Dy - x)^2 &= x^2(D+1) - D \\ \implies D^2 y^2 - 2Dxy + x^2 &= Dx^2 + x^2 - D \\ \implies Dx^2 + 2Dxy - D^2 y^2 &= D \\ \implies x^2 + 2xy - Dy^2 &\equiv 1 \pmod p \qquad \text{since $D \neq 0$} \end{aligned}

It can be checked that the set of solutions to this equation, equipped with addition operation above indeed does form a group. We'll call this group H\mathcal{H}.

Diophantine equations of the form x2Dy2=1x^2 - Dy^2 = 1 are known as Pell equations and are well documented in the literature. We'll see later that the equation we found from the rand_element can be written as a Pell equation, and use that for analysing the group even more.

Challenge Analysis

For now we'll take a look at how the flag is hidden and what we'll need to recover it. The 48 byte flag is broken up into 6 blocks of 8 bytes each. These blocks are represented as the integers m1,,m6m_1, \ldots, m_6. Then, for some randomly generated elements g1,,g6g_1, \ldots, g_6, the value c=g1m1g6m6c = g_1^{m_1} \cdots g_6^{m_6} is computed.

Given cc and the gig_i, the goal is to recover the mim_i. This is known as the t-multiple discrete logarithm problem, and in this case, we can solve it by solving the discrete logarithm problem in H\mathcal{H}, combined with lattice techniques.

Let qq be the order of H\mathcal{H} and let gg be a generator of H\mathcal{H} (we will see later that H\mathcal{H} is cyclic). Define the discrete logarithm to the base gg as logg:HZq\log_g : \mathcal{H} \rightarrow \mathbb{Z}_q, that, for any hHh \in \mathcal{H}, gives us a value x=logg(h)x = \log_g(h) such that gx=hg^x = h. It can be shown that this map is a homomorphism, so logg(h1h2)=logg(h1)+logg(h2)\log_g(h_1 h_2) = \log_g(h_1) + \log_g(h_2). Therefore,

logg(c)=logg(g1m1g6m6)logg(c)=logg(g1m1)++logg(g6m6)logg(c)=m1logg(g1)++m6logg(g6)\begin{aligned} \log_g(c) &= \log_g(g_1^{m_1} \cdots g_6^{m_6}) \\ \log_g(c) &= \log_g(g_1^{m_1}) + \cdots + \log_g(g_6^{m_6}) \\ \log_g(c) &= m_1\log_g(g_1) + \cdots + m_6 \log_g(g_6) \\ \end{aligned}

Since we're working in Zq\mathbb{Z}_q, we can equivalently write

logg(c)m1logg(g1)++m6logg(g6)(modq)\log_g(c) \equiv m_1\log_g(g_1) + \cdots + m_6\log_g(g_6) \pmod q

But since the mim_i are relatively small (~62 bits) compared to qq (which we will determine later), we can solve for the mim_i using lattice techniques. Specifically, consider the lattice generated by the rows of the matrix

[logg(g1)1logg(g2)1logg(g6)1logg(c)1q]\begin{bmatrix} \log_g(g_1) & 1 \\ \log_g(g_2) & & 1 \\ \vdots & & & \ddots \\ \log_g(g_6) & & & & 1 \\ \log_g(c) & & & & & 1 \\ q \end{bmatrix}

Notice that m1m_1 times the first row, plus m2m_2 times the second row, etc. take 11 times the seventh row, and an appropriate multiple of the last row, gives the short vector

(0,262,262,262,262,262,262,1)(0, 2^{62}, 2^{62}, 2^{62}, 2^{62}, 2^{62}, 2^{62}, -1)

which can be found with lattice basis reduction algorithms such as LLL.

Group Structure Part II

Group Order

All we need left to solve the challenge is a way to solve the discrete logarithm problem in H\mathcal{H}. Determining the group order is a good first step as we could use it to try and see if there is an isomorphism between H\mathcal{H} and an additive group of integers of the same order where the discrete logarithm is trivially solved by division. However, it turns out that the order of H\mathcal{H} is p+1p+1 and that H\mathcal{H} is isomorphic to the cyclic subgroup of Fp2\mathbb{F}_{p^2} of order p+1p+1. We follow a similar approach to [1] for the proof.


Claim. Let HFp×Fp\mathcal{H} \subset \mathbb{F}_p \times \mathbb{F}_p be the set of solutions to the equation

x2+2xyDy21(modp)x^2 + 2xy - Dy^2 \equiv 1 \pmod p

Assume that (D+1p)=1\left(\dfrac{D+1}{p}\right) = -1 (this is true for the challenge parameters). Then, HS\mathcal{H} \cong S where SFp2S \leq \mathbb{F}_{p^2} is the cyclic subgroup of Fp2\mathbb{F}_{p^2} of order p+1p+1.

Proof. First, note that (x+y)2(D+1)y2=x2+2xyDy2(x+y)^2 - (D+1)y^2 = x^2 + 2xy - Dy^2, so it suffices to show that the set of solutions to the equation (x+y)2(D+1)y21(modp)(x+y)^2 - (D+1)y^2 \equiv 1 \pmod p (equipped with the addition operation as defined above) is isomorphic to SS. Let f(W)=W2(D+1)f(W) = W^2 - (D+1). Note that f(W)f(W) is irreducible as it is of degree 2 and has no roots, since D+1D+1 has no square in Fp\mathbb{F}_p by assumption. Therefore Fp2Fp[W]/f(W)\mathbb{F}_{p^2} \cong \mathbb{F}_p[W]/\langle f(W) \rangle. Now, if αS\alpha \in S, then αp+1=1\alpha^{p+1} = 1 (since SS has order p+1p+1). But we can write α=r+sW\alpha = r + sW for r,sFpr,s \in \mathbb{F}_p. So,

αp+1=(r+sW)p(r+sW)=(rp+spWp)(r+sW)(x+y)p=xp+yp for all x,yFp=(r+sWp)(r+sW)xp1=1 for all xFp=(rsW)(r+sW)Wp=W(W2)p12=W(D+1)p12=W=r2s2W2=r2(D+1)s2W2=D+1\begin{aligned} \alpha^{p+1} &= (r + sW)^p (r + sW) \\ &= (r^p + s^pW^p)(r + sW) &&\quad (x+y)^p = x^p + y^p \text{ for all } x, y \in \mathbb{F}_p \\ &= (r + sW^p)(r + sW) &&\quad x^{p-1} = 1 \text{ for all } x \in \mathbb{F}_p \\ &= (r - sW)(r + sW) &&\quad W^p = W(W^2)^{\frac{p-1}{2}} = W(D+1)^{\frac{p-1}{2}} = -W \\ &= r^2 - s^2 W^2 \\ &= r^2 - (D+1)s^2 &&\quad W^2 = D+1 \end{aligned}

So, if we take r=x+yr = x+y and s=ys = y, then we see that αp+1=1=(x+y)2(D+1)y2\alpha^{p+1} = 1 = (x+y)^2 - (D+1)y^2. Therefore, we have the bijection φ:HS,(x,y)(x+y)+yW\varphi : \mathcal{H} \rightarrow S, (x, y) \mapsto (x+y) + yW. To see that this is a homomorphism, let (x1,y1),(x2,y2)H(x_1, y_1), (x_2, y_2) \in \mathcal{H}. Then

φ((x1,y1)(x2,y2))=φ((x1x2+Dy1y2,x1y2+x2y1+2y1y2))=(x1x2+x1y2+x2y1+(D+2)y1y2)+(x1y2+x2y1+2y1y2)W\begin{aligned} \varphi((x_1, y_1) \cdot (x_2, y_2)) &= \varphi((x_1 x_2 + D y_1 y_2, x_1 y_2 + x_2 y_1 + 2 y_1 y_2)) \\ &= (x_1 x_2 + x_1 y_2 + x_2 y_1 + (D+2) y_1 y_2) + (x_1 y_2 + x_2 y_1 + 2 y_1 y_2) W \end{aligned}

But

φ((x1,y1))φ((x2,y2))=((x1+y1)+y1W)((x2+y2)+y2W)=(x1+y1)(x2+y2)+(x1+y1)y2W+(x2+y2)y1W+y1y2W2=(x1x2+x1y2+x2y1+y1y2)+(x1y2+x2y1+2y1y2)W+(D+1)y1y2=(x1x2+x1y2+x2y1+(D+2)y1y2)+(x1y2+x2y1+2y1y2)W\begin{aligned} \varphi((x_1, y_1)) \varphi((x_2, y_2)) &= ((x_1 + y_1) + y_1 W)((x_2 + y_2) + y_2 W) \\ &= (x_1 + y_1)(x_2 + y_2) + (x_1 + y_1) y_2 W + (x_2 + y_2) y_1 W + y_1 y_2 W^2 \\ &= (x_1 x_2 + x_1 y_2 + x_2 y_1 + y_1 y_2) + (x_1 y_2 + x_2 y_1 + 2 y_1 y_2) W + (D+1) y_1 y_2 \\ &= (x_1 x_2 + x_1 y_2 + x_2 y_1 + (D+2) y_1 y_2) + (x_1 y_2 + x_2 y_1 + 2 y_1 y_2) W \end{aligned}

So we have φ((x1,y1)(x2,y2))=φ((x1,y1))φ((x2,y2))\varphi((x_1, y_1) \cdot (x_2, y_2)) = \varphi((x_1, y_1)) \varphi((x_2, y_2)).

Therefore φ\varphi is an isomorphism, and HS\mathcal{H} \cong S.


If we take a look at the actual values in the challenge, we'll see that p+1p+1 is smooth, with the largest factor being 32 bits! This is a hint that we're on the right path, since we'll be able to solve the discrete logarithm problem in a reasonable time with Pohlig-Hellman.

Inverse Elements

By this point, we've pretty much already solved the challenge, but as a bonus, we can find the inverse elements of H\mathcal{H}. Although the solution script doesn't do this, this has the advantage of speed over using the isomorphism found above since the operations are slightly faster (than operations in Fp2\mathbb{F}_{p^2}). Recall the addition formula

(x,y)(x,y)=(xx+Dyy,xy+xy+2yy)(x, y) \cdot (x', y') = (xx' + Dyy', xy' + x'y + 2yy')

The identity element is clearly (1,0)(1, 0), so to find the inverse element of (x,y)(x, y), we want to find (x,y)(x', y') such that (x,y)(x,y)=(1,0)(x, y) \cdot (x', y') = (1, 0). Let (x,y)=(x+2y,y)(x', y') = (x + 2y, -y). Then

(x,y)(x,y)=(x,y)(x+2y,y)=(x(x+2y)Dy2,xy+(x+2y)y2y2)=(x2+2xyDy2,xy+xy+2y22y2)=(1,0)\begin{aligned} (x, y) \cdot (x', y') &= (x, y) \cdot (x + 2y, -y) \\ &= (x(x + 2y) - Dy^2, -xy + (x + 2y)y - 2y^2) \\ &= (x^2 + 2xy - Dy^2, -xy + xy + 2y^2 - 2y^2) \\ &= (1, 0) \end{aligned}

So (x,y)1=(x+2y,y)(x, y)^{-1} = (x + 2y, -y).

Another advantage of figuring out inverse elements is that you can solve the challenge without finding the isomorphism to Fp2\mathbb{F}_{p^2} by guessing that the order is p+1p+1 since it is smooth, and then implementing Pohlig-Hellman and BSGS to use the addition, multiplication and inverse operations.

References


power sign

Challenge Overview

We are given the code running on a server that implements a signature scheme. We can ask the server to sign one message, then we are challenged to forge a signature for a random message.

The signature scheme resembles the Rabin signature algorithm. The public key is an RSA modulus N=pqN = pq whose prime factorisation is the private key. A message MM is signed by first computing a randomised hash H(M,u)H(M, u) (where uu is random) of MM. If H(M,u)H(M, u) has a square root modulo NN, a square root xx modulo NN is computed and the signature (x,u)(x, u) is outputted. Otherwise, we try again with a different uu. Note that computing square roots modulo NN, or even determining whether a number has a square root modulo NN is equivalent to factoring NN. To verify a signature (x,u)(x, u) for the message MM, we simply check that the equality x2H(m,u)(modN)x^2 \equiv H(m, u) \pmod N holds.

In the challenge, the primes generated are of the form p3(mod4)p \equiv 3 \pmod 4. This is done because if pp is a prime such that p3(mod4)p \equiv 3 \pmod 4, then if a square root of a{0,,p1}a \in \{ 0, \ldots, p-1 \} exists, it can be easily computed as ±ap+14modp\pm a^{\frac{p+1}{4}} \mod p. To compute a square root of cc modulo NN, we compute square roots of cc modulo pp and modulo qq, then combine them with the Chinese Remainder Theorem.

Security of Rabin Signatures

Before we proceed, we'll take a look at an easy attack against a simplified variant of the Rabin signature algorithm. Specifically, we consider a variant that does not use a hash function at all, i.e. to sign a message MM the signer simply computes a square root of MM modulo NN. For simplicity, we assume that all the messages to be signed actually do have square roots modulo NN, though it does not really matter. There is one trivial attack; anyone can "forge" a valid signature for MM if MM is a perfect square. For example, if M=9M = 9, then x=3x = 3 is a valid signature since x2m(modN)x^2 \equiv m \pmod N.

More interestingly however, it turns out that we can recover the private key given access to a signing oracle. We do this by choosing a random x<Nx < N and ask the oracle to sign x2modNx^2 \mod N. It returns a square root yy of x2x^2 modulo NN. Now, if y±x(modN)y \neq \pm x \pmod N, then we have

x2y2(modN)    x2y20(modN)    x2y2=kNfor some k    (xy)(x+y)=kN\begin{aligned} x^2 &\equiv y^2 \pmod N \\ \implies x^2 - y^2 &\equiv 0 \pmod N \\ \implies x^2 - y^2 &= kN \quad \text{for some $k$} \\ \implies (x-y)(x+y) &= kN \end{aligned}

so gcd(xy,N)\gcd(x-y, N) reveals a nontrivial factor of NN.

The Hash Function

This section and the next are somewhat algebra-heavy and basic results from algebra are used without proof for brevity. It may be worthwhile to read up on finite fields, field extensions and Galois theory (for later) if they are unfamiliar concepts.

We learned the importance of a good, randomised hash function in the previous section. And more importantly, we learned that a hash function which is simply the identity map (i.e. sends any input to itself), is completely insecure. We will now take a look at the hash function in the challenge.

Choose a composite integer nn and a proper divisor mm (in the challenge we have n=15,m=3n = 15, m = 3). Let rr be the smallest prime number following NN, where NN is the signer's public key. We will work in an extension field K=FrnFr[x]/(f)K = \mathbb{F}_{r^n} \cong \mathbb{F}_r[x]/(f) of Fr\mathbb{F}_r, where fFr[x]f \in \mathbb{F}_r[x] is a public degree nn irreducible polynomial. Let z=x+(f)z = x + (f). Then zz generates KK and {1,z,z2,,zn1}\{ 1, z, z^2, \ldots, z^{n-1} \} is basis for KK when viewed as an nn-dimensional Fr\mathbb{F}_r-vector space. That is, elements in KK can be written in the form a0+a1z++an1zn1a_0 + a_1 z + \cdots + a_{n-1} z^{n-1} where aiFra_i \in \mathbb{F}_r.

The randomised hash function HH takes as input a message MM and an integer uu. Write MM in terms of powers of rr:

M=M0+M1r+M2r2++MkrkM = M_0 + M_1 r + M_2 r^2 + \cdots + M_k r^k

where Mi<rM_i < r. Then, MM is converted to an element hh in KK by computing

h=Mk+Mk1z+Mk2z2++M0zkh = M_k + M_{k-1} z + M_{k-2} z^2 + \cdots + M_0 z^k

To obtain the hash, the function computes (h+uz)rm(h + uz)^{r^m} which we write as

(h+uz)rm=a0+a1z++an1zn1(h + uz)^{r^m} = a_0 + a_1 z + \cdots + a_{n-1} z^{n-1}

The output is a0a_0.

Choosing a Message to be Signed

After the server provides us with its public key, it prompts us to send a message to be signed. Note that (in the sign function) uu isn't chosen randomly; it starts at 11 and increments until H(M,u)H(M, u) is a square. There is also a peculiar restriction on the message; it has to be larger than NmN^m and smaller than NnN^n.

If we were able to send messages of any size for the server to sign, we can easily find a message that will help us to recover the private key. Specifically, we would choose a random s<Ns < N and send the message (r1)+(s2modN)r(r - 1) + (s^2 \mod N) r. The hash function will convert this to h=(s2modN)+(r1)zh = (s^2 \mod N) + (r - 1)z and output the constant term in (h+uz)rm(h + uz)^{r^m} which happens to just be s2modNs^2 \mod N since all elements aFra \in \mathbb{F}_r satisfy ar=aa^r = a by Fermat's Little Theorem. So when the server signs this, we have the exact same situation as the attack described two sections ago. However, the size check prevents this attack.

Recall that the identity map is insecure as a hash function for the reasons given two sections ago. It turns out that our particular hash function is the identity map on a specific subset, or rather, subfield of KK other than Fr\mathbb{F}_r. We have

H(M,u)=(h+uz)rmH(M, u) = (h + uz)^{r^m}

where hh is the element in KK we obtain by converting MM. We can write this as a composition H=fgH = f \circ g where

g(M,u)=h+uzf(x)=xrmg(M, u) = h + uz \qquad f(x) = x^{r^m}

The goal will be to find fixed points of HH, which can be done by finding fixed points of ff since we can easily manipulate the result of g(M,u)g(M, u) by carefully choosing MM. Fixed points of ff satisfy

f(x)=x    xrm=x    xrmx=0f(x) = x \implies x^{r^m} = x \implies x^{r^m} - x = 0

Note that for a finite field EE of order rmr^m, the elements of EE are given by the roots of xrmxx^{r^m} - x. This follows from the fact that the multiplicative group E×=E{0}E^\times = E - \{ 0 \} is a cyclic group of order rm1r^m - 1, so if αE\alpha \in E, then αrm1=1\alpha^{r^m - 1} = 1 and so αrm=α\alpha^{r^m} = \alpha. That E×E^\times is cyclic of order rm1r^m - 1 follows from the structure theorem for finite abelian groups which states that any finite abelian group is a direct product of cyclic groups. There are a lot of references online for these results and their proofs.

So, to solve for the roots of xrmxx^{r^m} - x we simply need to look at elements in the finite field EE of order rmr^m. Since mm divides nn, then this field is actually a subfield of KK because if xx satisfies xrm=xx^{r^m} = x, then it also satisfies

xrn=xrkm=x(rm)k=x(rm)(rm)k1=(xrm)(rm)k1=x(rm)k1=x\begin{aligned} x^{r^n} &= x^{r^{km}} \\ &= x^{(r^m)^k} \\ &= x^{(r^m)(r^m)^{k-1}} \\ &= (x^{r^m})^{(r^m)^{k-1}} \\ &= x^{(r^m)^{k-1}} \\ &\quad \vdots \\ &= x \end{aligned}

(and it can also be checked that EE actually is a field). This is good for us as it means we can write the elements in terms of zz which is what the server will be expecting.

Let zEz_E be a generator of EE. Because EE is a subfield of KK, then zEz_E can be written as

zE=e0+e1z+en1zn1z_E = e_0 + e_1 z + \cdots e_{n-1} z^{n-1}

where eiFre_i \in \mathbb{F}_r. Choose a random s<Ns < N. We will want to find an element in KK of the form

(s2modN)+a1z+anzn1(s^2 \mod N) + a_1 z + \cdots a_n z^{n-1}

such that when HH is applied to this element, the constant term remains as s2modNs^2 \mod N which will be the output of the hash function. To do this, we will find an element in EE with s2modNs^2 \mod N as its constant term, and then subtract zz from it to account for the randomising value uu which we can predict will be 11.

The element in KK we are interested in is obtained by computing

(s2modN)e01zEz=(s2modN)+a1z++anzn1(s^2 \mod N) e_0^{-1} z_E - z = (s^2 \mod N) + a_1 z + \cdots + a_n z^{n-1}

To send this to the server, we encode it as an integer:

an+an1r++a1rn2+(s2modN)rn1a_n + a_{n-1} r + \cdots + a_1 r^{n-2} + (s^2 \mod N) r^{n-1}

The server will compute for us a square root yy of s2modNs^2 \mod N and if we have y±sy \neq \pm s, we can easily recover the private key using the technique described two sections ago.

Once we have the private key, we can use the provided functions in the handout code to sign the challenge message and capture the flag.

Easier Solution

I was made aware of this by S3v3ru5's solve during the CTF, but choosing the message to be signed can actually be quite simple (though fundamentally relies on most of the above theory); the idea is to shift the goal posts a bit and instead of trying to find a fixed message, we find a message whose hash is something we can control. We do this by noting that since xrn=xx^{r^n} = x for all xKx \in K, then for any of our chosen xKx \in K, if we send xrnmzux^{r^{n - m}} - zu, then after being hashed, the result is exactly xx. I imagine most teams would have solved this way instead of finding the subfield which is quite a bit more complicated. I obviously lacked the hindsight to spot this solution when writing the challenge, but it's pretty neat :)

Alternative Approach via Linearity Properties

This solution idea is due to rkm0959 who taught me this during the CTF after he solved it. Instead of looking at the fields involved, we can simply note that the hash function has some nice linearity properties. In particular

H(M,u)=H(M,0)+uH(0,1)(modr)H(M, u) = H(M, 0) + u H(0, 1) \pmod r

So to forge a signature for any given MM, we simply let x=1x = 1 and solve for uu:

x2=H(M,u)    x=H(M,u)since x=1    x=H(M,0)+uH(0,1)    u=H(0,1)1(xH(M,0))\begin{aligned} x^2 &= H(M, u) \\ \implies x &= H(M, u) \qquad \text{since $x = 1$} \\ \implies x &= H(M, 0) + u H(0, 1) \\ \implies u &= H(0, 1)^{-1}(x - H(M, 0)) \end{aligned}

Then, (x,u)(x, u) is a valid signature for MM.

This attack doesn't need to use the signing oracle and shows that the signature scheme is completely broken when using this hash function. Pretty cool solution!

Alternative Approach via Galois Theory

Alternatively, one might recognise the resemblance of the function ff with the Frobenius map ϕ:KK,xxr\phi : K \rightarrow K, x \mapsto x^r which is an Fr\mathbb{F}_r-automorphism that generates the Galois group GG of K/FrK/\mathbb{F}_r. Note that GG is cyclic and of order nn as ϕn:KK,xxrn\phi^n : K \rightarrow K, x \mapsto x^{r^n} is the identity map. The Fundamental Theorem of Galois Theory tells us that there is a one-to-one correspondence between the subgroups of the Galois group of KK, and the intermediate fields of KK. Explicitly, for a given subgroup HH of GG, the corresponding intermediate field of KK is given by the fixed field KHK^H, the set of all elements in KK which are fixed by all of the maps in HH. Another result, sometimes known as the Fixed Field Theorem, tells us that the order of HH is equal to the degree of KK as an extension of KHK^H. We use this, along with the fact that the subfields of KK are given by Frd\mathbb{F}_{r^d} where dd divides nn, to find the fixed fields.

In the challenge, we have n=15n = 15, so the Galois group GG is isomorphic to Z/15Z\mathbb{Z}/15\mathbb{Z}. The table below lists out the subgroups of GG and their corresponding intermediate fields (id\mathrm{id} denotes the identity map):

Subgroup of GGIntermediate Field of KK
H0={id}H_0 = \{ \mathrm{id} \}KH0=KK^{H_0} = K (all elements are fixed by id\mathrm{id})
H1={id,ϕ5,ϕ10}H_1 = \{ \mathrm{id}, \phi^5, \phi^{10} \}KH1=Fr5K^{H_1} = \mathbb{F}_{r^5}
H2={id,ϕ3,ϕ6,ϕ9,ϕ12}H_2 = \{ \mathrm{id}, \phi^3, \phi^6, \phi^9, \phi^{12} \}KH2=Fr3K^{H_2} = \mathbb{F}_{r^3}
GGKG=FrK^G = \mathbb{F}_r (only Fr\mathbb{F}_r is fixed by all automorphisms)

From this, we can see that Fr3\mathbb{F}_{r^3} is fixed by ϕ3\phi^3.


1337crypt v2

The challenge claims to be a more complex version of 1337crypt from last year's DUCTF. Reading the solution for 1337crypt may help a bit with some initial ideas as both challenges play with the idea of partial knowledge. In both challenges, we are given hints to recover the prime factors, but the hints themselves seem to omit some bits of information. Specifically, the hints are the integer parts of some values that should actually contain a fractional part as well. As we will see (and as you may suspect :)), lattice techniques will help us to recover this missing information and therefore the primes.

Flag Encryption

We start by looking at how the flag is encrypted so that we have a clear idea of what we need to recover it. The flag is encrypted in a way very similar to RSA. The only difference is that instead of using integers, we use Gaussian integers. If you aren't familiar with Gaussian integers, I highly recommend reading this excellent blog post by CryptoHack for some extra background.

We work in the ring (Z/nZ)[i](\mathbb{Z}/n\mathbb{Z})[i] (we will just write this as Zn[i]\mathbb{Z}_n[i]) where n=pqn = pq is the RSA modulus. The flag is encoded as an element mm, of Zn[i]\mathbb{Z}_n[i] by choosing a random integer r<nr < n and computing m=r+flagim = r + \mathrm{flag} \cdot i.

The ciphertext is obtained by raising mm to the eeth power. In the challenge, ee is 0x1337.

To decrypt the ciphertext, we must find the multiplicative inverse of ee modulo the order of Zn[i]\mathbb{Z}_n[i]. (Note: in this context, when we say "the order of Zn[i]\mathbb{Z}_n[i]" we mean the cardinality of the multiplicative group of Zn[i]\mathbb{Z}_n[i]) The order of Zn[i]\mathbb{Z}_n[i] is φ(n)=(p1)(q1)\varphi(n) = (p-1)(q-1), so to compute it, we'll need to recover the primes.

Hints

The challenge generates 1337-bit primes pp and qq and gives us two hints, and the ciphertext. Using these hints, we need to recover pp and qq.

Hint 1

The first hint, which we will call DD, is D=p2+q2D = p^2 + q^2. This seems like a pretty big hint, and indeed if we were also given n=pqn = pq we could easily recover the primes by finding the roots of a simple univariate polynomial. As far as I am aware, DD can't be used to directly recover pp and qq either; there are techniques such as factoring p2+q2=(p+qi)(pqi)p^2 + q^2 = (p + qi)(p - qi) over the Gaussian integers, but this requires factoring DD over the integers which may take a long time. That said, if you were able to find a solution using this hint alone I'd be interested in seeing it :)

Hint 2

There is a lot more going on in the second hint. But firstly, some background. Number field is just a fancy name for an (finite) extension of the rational numbers Q\mathbb{Q}. The simplest number field is Q\mathbb{Q} itself, and the rational complex numbers, Q(i)\mathbb{Q}(i) is also a number field.

We can see that a number field is constructed from pp and qq. In Sage, the first argument to NumberField is the defining polynomial. The roots of this polynomial specify the elements to be adjoined to Q\mathbb{Q} to get the number field. We see that the defining polynomial for KK is (xp)2+q2(x-p)^2 + q^2, which has roots p±qip \pm qi. Therefore, we define

K=Q(p+qi)K = \mathbb{Q}(p + qi)

(side note: we only need to adjoin one root since the other, it's conjugate, can be obtained from the root with usual field operations). In the handout code, z=p+qiz = p + qi denotes this adjoined element.

Now, for the values we are given. We get two instances of values with the same form. For the jjth hint (j=1,2j = 1, 2), two 1337-bit numbers aja_j and bjb_j are generated, as well as two ll-bit numbers cjc_j and djd_j. Then, xjx_j is computed as

xj=(aj+2lcj)+(bj+2ldj)zx_j = (a_j + 2^{-l} c_j) + (b_j + 2^{-l} d_j) z

Lastly,

xj2=xjxj|x_j|^2 = x_j \overline{x_j}

is computed and we are given the three values (xj2,aj,bj)(\lfloor |x_j|^2 \rfloor, a_j, b_j). Note that xj\overline{x_j} denotes the complex conjugate of xjx_j, so the value xjxjx_j \overline{x_j} gives us the squared complex modulus of xjx_j. For ease of reading, we will write yy instead of xj2\lfloor |x_j|^2 \rfloor.

Importantly, we note that xjx_j is an element of KK and its components are rational numbers with fractional parts. Similarly, xj2|x_j|^2 is a rational number with a fractional part. However, we are only given the integer parts of these values, so it seems like we might be missing some information.

Solution

Let's analyse the second hint in further detail and see if we can use it to recover the primes directly, or find a relation involving the primes that will help us to do so.

Analysing Hint 2

There will be some tedious algebra, so to make things a bit more readable we will drop the subscripts. Note that we use hint 1 here since p2+q2p^2 + q^2 appears. We have

x=(a+2lc)+(b+2ld)z=(a+2lc)+(b+2ld)(p+qi)=((a+2lc)+(b+2ld)p)+(b+2ld)qi    x2=((a+2lc)+(b+2ld)p)2+((b+2ld)q)2=(a+2lc)2+2(a+2lc)(b+2ld)p+(b+2ld)2p2+(b+2ld)2q2=(a+2lc)2+2(a+2lc)(b+2ld)p+(b+2ld)2D=a2+22lac+22lc2+2abp+22ladp+22lbcp+222lcdp+(b2+22lbd+22ld2)D=a2+22lac+22lc2+2abp+22ladp+22lbcp+222lcdp+b2D+22lbdD+22ld2D\begin{aligned} x &= (a + 2^{-l} c) + (b + 2^{-l} d) z \\ &= (a + 2^{-l} c) + (b + 2^{-l} d) (p + qi) \\ &= ((a + 2^{-l} c) + (b + 2^{-l} d) p) + (b + 2^{-l} d) qi \\ \implies |x|^2 &= ((a + 2^{-l} c) + (b + 2^{-l} d) p)^2 + ((b + 2^{-l} d)q)^2 \\ &= (a + 2^{-l} c)^2 + 2(a + 2^{-l} c)(b + 2^{-l} d) p \\ &\quad + (b + 2^{-l} d)^2 p^2 + (b + 2^{-l} d)^2 q^2 \\ &= (a + 2^{-l} c)^2 + 2(a + 2^{-l} c)(b + 2^{-l} d) p + (b + 2^{-l}d)^2 D \\ &= a^2 + 2 \cdot 2^{-l} ac + 2^{-2l} c^2 + 2 a b p + 2 \cdot 2^{-l} adp + 2 \cdot 2^{-l} bcp + 2 \cdot 2^{-2l} c d p \\ &\quad + (b^2 + 2 \cdot 2^{-l} bd + 2^{-2l} d^2) D \\ &= a^2 + 2 \cdot 2^{-l} ac + 2^{-2l} c^2 + 2 a b p + 2 \cdot 2^{-l} adp + 2 \cdot 2^{-l} bcp + 2 \cdot 2^{-2l} c d p \\ &\quad + b^2 D + 2 \cdot 2^{-l} bd D + 2^{-2l} d^2 D \end{aligned}

Now, this looks like a mess and it kinda is, but fortunately we can clean it up a bit. Recall that aa and bb are 1337-bit numbers, while cc and dd are 338-bit numbers (l=338l = 338). The following table gives the approximate size of each term (when considered as an integer), which we will use to reason with soon. Note that D=p2+q2D = p^2 + q^2 is on the order of 2×13372 \times 1337 bits.

TermSize (in bits)
a2a^22×13372 \times 1337
22lac2 \cdot 2^{-l} ac13371337
22lc22^{-2l}c^200
2abp2abp3×13373 \times 1337
22ladp2 \cdot 2^{-l} adp2×13372 \times 1337
22lbcp2 \cdot 2^{-l} bcp2×13372 \times 1337
222lcdp2 \cdot 2^{-2l} cdp13371337
b2Db^2 D4×13374 \times 1337
22lbdD2 \cdot 2^{-l} bd D3×13373 \times 1337
22ld2D2^{-2l} d^2 D2×13372 \times 1337

Now, what we will do is divide (integer division) the entire expression by 2ab2ab. Because 2ab2ab is around 2×13372 \times 1337 bits in size, we can more or less throw away any term whose size is 2×13372 \times 1337 or less. This leaves us with

x22ab=y2abp+(b2+22lbd)D2abp+b2D2ab+2ldDa\begin{aligned} \frac{|x|^2}{2ab} = \frac{y}{2ab} &\approx p + \frac{(b^2 + 2 \cdot 2^{-l} bd) D}{2ab} \\ &\approx p + \frac{b^2D}{2ab} + \frac{2^{-l}dD}{a} \end{aligned}

This approximation itself is very accurate, and only differs by a few bits due to the 2×13372 \times 1337 terms. However, we don't know dd, so this equation isn't as useful for us. Instead, we write

y2abp+b2D2ab+2lDad=p+b2D2ab+2lDad+k\begin{aligned} \frac{y}{2ab} &\approx p + \frac{b^2 D}{2ab} + \left \lfloor \frac{2^{-l} D}{a} \right \rfloor d \\ &= p + \frac{b^2 D}{2ab} + \left \lfloor \frac{2^{-l} D}{a} \right \rfloor d + k \end{aligned}

where k<2l|k| < 2^l. Note that the approximation is off by a term of size approximately ll bits because of integer division rounding. We will omit the \lfloor \rfloor, but it should be understood that we are performing integer division.

Using Hint 2

Now let's bring back the subscripts, noting that we have two instances:

{y12a1b1=p+b12D2a1b1+2lDa1d1+k1y22a2b2=p+b22D2a2b2+2lDa2d2+k2\begin{aligned} \begin{cases} \frac{y_1}{2a_1 b_1} &= p + \frac{b_1^2 D}{2 a_1 b_1} + \frac{2^{-l} D}{a_1} d_1 + k_1 \\ \frac{y_2}{2a_2 b_2} &= p + \frac{b_2^2 D}{2 a_2 b_2} + \frac{2^{-l} D}{a_2} d_2 + k_2 \\ \end{cases} \end{aligned}

Finally, let's combine these two equations to eliminate pp.

y1b12D2a1b12lDa1d1k1=y2b22D2a2b22lDa2d2k2\frac{y_1 - b_1^2 D}{2 a_1 b_1} - \frac{2^{-l} D}{a_1} d_1 - k_1 = \frac{y_2 - b_2^2 D}{2 a_2 b_2}- \frac{2^{-l} D}{a_2} d_2 - k_2

Just so it's easier to read, let tj=yjbj2D2ajbjt_j = \frac{y_j - b_j^2 D}{2 a_j b_j} and sj=2lDajs_j = \frac{2^{-l} D}{a_j}. Then, rewriting the above equation, we have:

t1s1d1k1=t2s2d2k2t_1 - s_1 d_1 - k_1 = t_2 - s_2 d_2 - k_2

or to put it in a more exciting way:

f(d1,d2,k)=t1s1d1t2+s2d2k=0f(d_1, d_2, k) = t_1 - s_1 d_1 - t_2 + s_2 d_2 - k = 0

Now, ff has "small" integer roots d1,d2d_1, d_2 and kk. An algorithm for finding small roots of multivariate polyomials over the integers is described in this paper. Following a similar idea, defund's coppersmith implementation can also be used by working over an arbitrary ring Z/NZ\mathbb{Z}/N\mathbb{Z} for some large NN.

Lattice Approach

However, we can also recover d1d_1 and d2d_2 with a very simple lattice. Consider the lattice generated by the rows of the following matrix:

[s110s201t1t200]\begin{bmatrix} s_1 & 1 & 0 \\ s_2 & 0 & 1 \\ t_1 - t_2 & 0 & 0 \end{bmatrix}