LA CTF 2024 hOlyT Writeup
It was a bit unfortunate that I could only solve one chal this time. There were two chals that I looked into (prove it! and budget-bag) but I could not solve them on time. I'll maybe get back to them, once I have more free time. The competition website is here.
crypto/hOlyT
Author: freedGod is trying to talk to you through a noisy wire
Use
nc chall.lac.tf 31171to talk to him.
The code that the server runs server.py is as follows:
## server.py
from Crypto.Util.number import getPrime, bytes_to_long
import random
def legendre(a, p):
return pow(a, (p - 1) // 2, p)
def tonelli(n, p):
q = p - 1
s = 0
while q % 2 == 0:
q //= 2
s += 1
if s == 1:
return pow(n, (p + 1) // 4, p)
for z in range(2, p):
if p - 1 == legendre(z, p):
break
c = pow(z, q, p)
r = pow(n, (q + 1) // 2, p)
t = pow(n, q, p)
m = s
t2 = 0
while (t - 1) % p != 0:
t2 = (t * t) % p
for i in range(1, m):
if (t2 - 1) % p == 0:
break
t2 = (t2 * t2) % p
b = pow(c, 1 << (m - i - 1), p)
r = (r * b) % p
c = (b * b) % p
t = (t * c) % p
m = i
return r
def xgcd(a, b):
if a == 0 :
return 0,1
x1, y1 = xgcd(b % a, a)
x = y1 - (b // a) * x1
y = x1
return x, y
def crt(a, b, m, n):
m1, n1 = xgcd(m, n)
return ((b * m * m1 + a * n* n1) % (m * n))
def advice(x, p, q):
if legendre(x, p) != 1:
exit()
if legendre(x, q) != 1:
exit()
x1 = tonelli(x, p) * random.choice([1, -1])
x2 = tonelli(x, q) * random.choice([1, -1])
y = crt(x1, x2, p, q)
return y
def main():
p = getPrime(1024)
q = getPrime(1024)
N = p * q
e = 65537
m = bytes_to_long(b"lactf{redacted?}")
ct = pow(m, e, N)
print(f"ct = {ct}")
print(f"N = {N}")
print(f"e = {e}")
while 1:
x = int(input("What do you want to ask? > "))
ad = advice(x, p, q)
print(ad)
if __name__ == "__main__":
main()Let's first connect to the server and have it print out the ciphertext, modulus, and public key.
ct = 7795478703951910298760800512251016604742954197898050479871934501928567145784802604542002268080404992780678217646124951840673797270491710309688112924721561151731605873112953711785868170966477869814463719384874577110299248963713396172759754647405773964179242806311505685143222093888093347835985735639754440152848146516109884968142336041568834166265316368983280221226951298952481486521619997411247561491239782604374151098554182647251791561517307089804991475650432858727962467022168414859936296189874338448996484184334288550871046087698350678567999518807001116688026839842507335016985102010047274042512865191879615627189
N = 17831104667040256134725887251427780309283441190346378241363820041577227275015801947889351608323543022862201231205425355290220006633567994093510271341296137236696435486220210052887153794743228135603531011013817226919624495642090379006823492988501642462491665647285840701843758122419384518395935175111969431981176852184961902749819593573017708973408100060762005631607410042285600792954074826599343773206465846004997125247332792765111462262606314067259767823386343138746280621268625953047895333695773948796251064112811522554255832429054369092856990234149099315668149570501794323907590910167206485076585099237050507816159
e = 65537In server.py, the first four helper functions legendre(a, p), tonelli(n, p), xgcd(a, b), and crt(a, b, m, n) are pretty typical algorithms in number theory, and so there isn't anything much that we need to take a deep look into.
The advice function advice(x, p, q) however is interesting. Given an input $x$, it computes its square root $y$ (i.e., $x = y^2$) in $\textrm{mod } p$ and $\textrm{mod } q$. Then, it sometimes multiplies $-1$ to $y \textrm{ mod } p$ and/or $y \textrm{ mod } q$.
## From server.py
def advice(x, p, q):
if legendre(x, p) != 1:
exit()
if legendre(x, q) != 1:
exit()
x1 = tonelli(x, p) * random.choice([1, -1])
x2 = tonelli(x, q) * random.choice([1, -1])
y = crt(x1, x2, p, q)
return yLet $m_1$ and $n_1$ be the output of xgcd(p,q), i.e., $pm_1 + q n_1 = 1$. Then crt(x1, x2, p, q) would return $x_2 p m_1 + x_1 q n_1 \textrm{ mod } N$.
If we feed $x = 1$ into advice(x, p, q), then $x_1 = 1$ or $p-1$, and $x_2 = 1$ or $x_2 = q-1$ similarly. So, there are four possibilities:
and hence, there are four possible values for the output of advice(x, p, q):
Simplifying it a bit, we get
\[ \begin{align} \mathrm{advise} & = \begin{cases} 1 & \qquad \quad \text{if } (x_1, x_2) = (1, 1) \\ (q-1)p m_1 + q n_1 & \qquad \quad \text{if } (x_1, x_2) = (1, q-1) \\ p m_1 + (p-1)q n_1 & \qquad \quad \text{if } (x_1, x_2) = (p-1, 1) \\ N-1 & \qquad \quad \text{if } (x_1, x_2) = (p-1, q-1) \\ \end{cases} \end{align} \](They are all in $\textrm{mod } N$, of course.)
After "asking for the advice" multiple times, we can confirm that there are four different possible values for "advices" and two of them are $1$ and $N-1$ indeed.
advice1 = 1
advice2 = 5287777601238293523981811494581220691303194637423961140491216223083428308956095244834202549311570881496889752712676367619031571275642899318497063185249821345647331101077718320085534011766574399534626275869397780756135151510387353887061619044081762336730157777890978513661037167287196170717083630998547728678442124653719323218496331423510274573038831528686967059211961114374256096552045957173457049642231463409924134243522665941512000838223624978949908822912588169844952533849109925131151795615090030577149003683343962388502388786278395259552288577776773741360197776419851637543495068989503487348052288499709046665144
advice3 = 12543327065801962610744075756846559617980246552922417100872603818493798966059706703055149059011972141365311478492748987671188435357925094775013208156046315891049104385142491732801619782976653736068904735144419446163489344131703025119761873944419880125761507869394862188182720955132188347678851544113421703302734727531242579531323262149507434400369268532075038572395448927911344696402028869425886723564234382595072991003810126823599461424382689088309859000473754968901328087419516027916743538080683918219102060429467560165753443642775973833304701656372325574307951794081942686364095841177702997728532810737341461151015
advice4 = 17831104667040256134725887251427780309283441190346378241363820041577227275015801947889351608323543022862201231205425355290220006633567994093510271341296137236696435486220210052887153794743228135603531011013817226919624495642090379006823492988501642462491665647285840701843758122419384518395935175111969431981176852184961902749819593573017708973408100060762005631607410042285600792954074826599343773206465846004997125247332792765111462262606314067259767823386343138746280621268625953047895333695773948796251064112811522554255832429054369092856990234149099315668149570501794323907590910167206485076585099237050507816158This means that the remaining two must be $(q-1)p m_1 + q n_1$ and $p m_1 + (p-1)q n_1$. It is unclear which one is which, but that is not crucial because, adding $p m_1 + q n_1$ to both of them gives a multiple of $p$ and $q$ respectively.
\[ \begin{align} & p m_1 + q n_1 + p m_1 + (p-1)q n_1 = 2 p m_1 + pq n_1 = 2 p m_1 \mod N \\ & p m_1 + q n_1 + (q-1)p m_1 + q n_1 = 2 q n_1 + pq m_1 = 2 q n_1 \;\mod N \end{align} \]We can compute $2^{-1} \textrm{ mod } N$ and multiply it to both to get $p m_1$ and $q n_1$. Then, we can take $\gcd(p m_1, N)$ and $\gcd(q n_1, N)$ to extract $p$ and $q$. We are done now; now that we have $p$ and $q$, we can just compute the private key $d$ and decrypt the ciphertext.
## sol.py
import math
from Crypto.Util.number import long_to_bytes
from sympy import primefactors, isprime
ct = ...
N = ...
e = 65537
advice1 = 1
advice2 = ...
advice3 = ...
advice4 = ...
advices = [advice1, advice2, advice3, advice4]
two_q_n1 = (advice1 + advice2) % N
two_p_m1 = (advice1 + advice3) % N
two_inv = pow(2, -1, N)
q_n1 = (two_q_n1 * two_inv) % N
p_m1 = (two_p_m1 * two_inv) % N
# print((q_n1 + p_m1) % N) # Confirming this is 1.
gcd = math.gcd(q_n1, p_m1)
q_n1_coprime = q_n1 // gcd
p_m1_coprime = p_m1 // gcd
q = math.gcd(q_n1_coprime, N)
p = math.gcd(p_m1_coprime, N)
# print(p * q) # Indeed equal to N
phi_N = (p-1) * (q - 1)
d = pow(e, -1, phi_N)
m = pow(ct, d, N)
print(long_to_bytes(m))
## b'lactf{1s_r4bin_g0d?}'Flag: lactf{1s_r4bin_g0d?}