Crypto CTF 2022 WriteUp By tl2cents

2022-07-17

字数统计: 2.3k字 | 阅读时长≈ 14分

It’s my first time to participate in such a pure crypto competition this year. Too many crypto challenges tucked into a game within 24 hours are driving me a little unconscious. By the way, the time schedule is totally unfriendly to me in China time zone which keeps me out of the first blood. I spent about 9 hours working on the crypto challenges and finally solved 8 (checkin not included) of them with rank 51. There are various math tricks for those challenges. However, I have to mention that the descriptions of some challenges are vague and confusing, and I guess that’s why there are so few solutions to an easy challenge (not solved by me either, emmm). I’ve been moyuing for half month at home, so I decide to update this writeup in my blog. Due to time constraints, I didn’t even browse all the challenges of this competition, and I will review it later when I’m spare… Take a rain check.

Diploma (medium, 68 solves)

Given a modular p and a matrix M with shape $n \times n$ , we are supposed to find the min k such that : $M^k= E$ in $MatrixSpace(GF(p),n)$ , where $E$ is the identity matrix.

It’s a challenge about matrix group and its order. It’s easy if you’re familiar with the GL or MatrixSpace api in sage. For more info, refer to Linear Groups. Here is my exp:

# sage 9.2
import telnetlib

io = telnetlib.Telnet('08.cr.yp.toc.tf', '37313')

def readline():
    return io.read_until(b"\n")

def writeline(l):
    io.write(l+b"\n")

for i in range(100):
    print(f"[+] rounds :{i+1}")
    io.read_until(b'Generating the parameters for p =')
    p = int(io.read_until(b'\n').split(b",")[0])
    io.read_until(b'M =')
    readline()

    line=readline().decode()
    M=[]
    while "Send the order of matrix M" not in line:
        L=[int(i) for i in filter(None,line.strip().strip("[").strip("]").strip().split(" "))]
        M.append(L)
        line=readline().decode()

    print(f"[+] Matrix info: p = {p} , n = {len(M)}")
    G=GL(len(M),GF(p))
    m=G(M)
    O=int(m.order())
    writeline(str(O).encode())
    res=readline()
    print(res)
    if b"CCTF" in res:
            break

SOTS (medium easy, 113 solves)

It’s all about math trick. Therefore, I turn to google for help. After a long boring search, I found this Q&A in math.stackexchange : Efficiently finding two squares which sum to a prime. This is exactly in line with our challenge.

In our scene, we’re given an integer $n$ which is not a prime and we aim to find $a,b$ such that : $n=a^2+b^2$ . After several tries, I’m confirmed that $n$ is in form of $p*q*r$ where $p,q,r \equiv 1 \mod 4$ and can be factored in sagemath. By Thue’s Lemma, we can find $a,b,c,d,e,f$ such that $p=a^a+b^2,q=c^d+d^2,r=e^2+f^2$ in polynomial time. Therefore, by the identity : $(a^2+b^2)(x^2+y^2)=(ax+by)^2+(ay-bx)^2$ , we can find the two squares which sums to $n$. Here is my final exp in sage :

# sage 9.2
# nc 05.cr.yp.toc.tf 37331
import telnetlib

def mods(a, n):
    if n <= 0:
        return "negative modulus"
    a = a % n
    if (2 * a > n):
        a -= n
    return a

def powmods(a, r, n):
    out = 1
    while r > 0:
        if (r % 2) == 1:
            r -= 1
            out = mods(out * a, n)
        r //= 2
        a = mods(a * a, n)
    return out

def quos(a, n):
    if n <= 0:
        return "negative modulus"
    return (a - mods(a, n))//n

def grem(w, z):
    # remainder in Gaussian integers when dividing w by z
    (w0, w1) = w
    (z0, z1) = z
    n = z0 * z0 + z1 * z1
    if n == 0:
        return "division by zero"
    u0 = quos(w0 * z0 + w1 * z1, n)
    u1 = quos(w1 * z0 - w0 * z1, n)
    return(w0 - z0 * u0 + z1 * u1,
           w1 - z0 * u1 - z1 * u0)

def ggcd(w, z):
    while z != (0,0):
        w, z = z, grem(w, z)
    return w

def root4(p):
    # 4th root of 1 modulo p
    if p <= 1:
        return "too small"
    if (p % 4) != 1:
        return "not congruent to 1"
    k = p//4
    j = 2
    while True:
        a = powmods(j, k, p)
        b = mods(a * a, p)
        if b == -1:
            return a
        if b != 1:
            return "not prime"
        j += 1

def sq2(p):
    a = root4(p)
    return ggcd((p,0),(a,1))

def merge(a,b,x,y):
    return a*x+b*y,a*y-b*x

io = telnetlib.Telnet('05.cr.yp.toc.tf','37331')

def readline():
    return io.read_until(b"\n")

def writeline(l):
    io.write(l+b"\n")

def get_sum():
    io.read_until(b"[Q]uit\n")
    writeline(b"G")
    return int(readline().decode().strip().split("=")[-1])

def solve(x,y):
    io.read_until(b"[Q]uit\n")
    writeline(b"S")
    writeline(f"{x},{y}".encode())

n=get_sum()

print(f"[+]Start to factor {n}")
rl=list(factor(n))
p1,p2,p3=rl[0][0],rl[1][0],rl[2][0]
print(f"[+]Successfully factored: {rl}")

a,b=sq2(p1)
c,d=sq2(p2)
e,f=sq2(p3)

x,y=merge(a,b,c,d)
x,y=merge(x,y,e,f)

assert x^2+y^2==n

solve(x,y)
print(readline())
print(readline())
print(readline())

polyRSA (medium easy, 145 solves)

Focus on equations :

$p = k^6 + 7*k^4 - 40*k^3 + 12*k^2 - 114*k + 31377\\q = k^5 - 8*k^4 + 19*k^3- 313*k^2 - 14*k + 14011$

Considering $k$ as variable in polynomial of IntegerRing, let $f=p(k)*q(k)-n$ . Therefore, we only have to find $f.roots()$ in IntegerRing.

n = 44538727182858207226040251762322467288176239968967952269350336889655421753182750730773886813281253762528207970314694060562016861614492626112150259048393048617529867598499261392152098087985858905944606287003243
enc = 37578889436345667053409195986387874079577521081198523844555524501835825138236698001996990844798291201187483119265306641889824719989940722147655181198458261772053545832559971159703922610578530282146835945192532

P.<k>=PolynomialRing(ZZ)
f1=(k**6 + 7*k**4 - 40*k**3 + 12*k**2 - 114*k + 31377)
f2=(k**5 - 8*k**4 + 19*k**3 - 313*k**2 - 14*k + 14011)
f=f1*f2-n
print(f.roots())
from Crypto.Util.number import *
# [(9291098683758154336, 1)]
r=9291098683758154336
p=f1(r)
q=f2(r)
phi=(p-1)*(q-1)
e=31337
d=ZZ(inverse_mod(e,phi))
flag=long_to_bytes(int(pow(enc,d,n)))
print(flag)

Starter ECC (medium, 43 solves)

It takes me a lot of time to solve this challenge since there’s something wrong with the $nth\_root$ function when it comes to $GF(p^k)$ .

Actually, this challenge has little to do with ECC. We’re given parameters $n,a,b$ of $EllipticCurve(Zmod(n), [a, b])$ and are supposed to find the correct $y$ corresponding to a given coordinate $x$ . We can factor $n$ quickly in factorDB：

$n=2^{63}*690712633549859897233^6*651132262883189171676209466993073^5$

By the ECC polynomial: $y^2=x^3+ax+b$ , we try to sqrt $x^3+ax+b$ in $Zmod(2^{63})...$ There are totally $4*2*2=8$ solutions for this equation. In sage, if you try to find $nth\_root$ of prime power modular like $p^k$ in $GF(p^k)$ , it will return the results in $Zmod(p)$ instead of $Zmod(p^k)$ ！I was stuck here for hours.

# sage 9.2
from factordb.factordb import FactorDB
from Crypto.Util.number import *
x = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046477020617917601884853827611232355455223966039590143622792803800879186033924150173912925208583
a = 31337
b = 66826418568487077181425396984743905464189470072466833884636947306507380342362386488703702812673327367379386970252278963682939080502468506452884260534949120967338532068983307061363686987539408216644249718950365322078643067666802845720939111758309026343239779555536517718292754561631504560989926785152983649035
n = 117224988229627436482659673624324558461989737163733991529810987781450160688540001366778824245275287757373389887319739241684244545745583212512813949172078079042775825145312900017512660931667853567060810331541927568102860039898116182248597291899498790518105909390331098630690977858767670061026931938152924839936

# y^2=x^3+a*x+b
# f=FactorDB(n)
# f.connect()
# pl=f.get_factor_list()

modulus=[2^63,690712633549859897233^6,651132262883189171676209466993073^5]
Gp0=Zmod(modulus[0])
Gp1=Zmod(modulus[1])
Gp2=Zmod(modulus[2])

y2=(x^3+a*x+b)%n
res1=Gp0(y2).nth_root(2,all=True)
res2=Gp1(y2).nth_root(2,all=True)
res3=Gp2(y2).nth_root(2,all=True)

E = EllipticCurve(Zmod(n), [a, b])

for r1 in res1:
    for r2 in res2:
        for r3 in res3:
            y=int(CRT([ZZ(r1),ZZ(r2),ZZ(r3)],modulus))
            assert (y^2-x^3 - a*x-b)%n == 0
            G = E(x, y)
            print(long_to_bytes(int(CRT([ZZ(r1),ZZ(r2),ZZ(r3)],modulus))))

DBB (medium, 43 solves)

Similar to the starter ECC challenge, this time we are supposed to compute the discrete logarithm in ECC. There is something worthy of attention with the $discret\_log$ api in sage when it comes to $Zmod(n)$ with a given smooth order.

First, just factor n in sage and n is in form of $p*q*r$ . Therefore we try to compute the discrete logarithms in $GF(p),GF(q),GF(r)$ and combine them with Chinese Reminder Theorem. Luckily, we find the order $O_p,O_q,O_r$ are all smooth ( $O_n=O_p*O_q*O_r$ ). It’s rather easy in sage. However, when you want to use the $ord$ parameter in $discrete\_log$ , you have to use the order of base element instead of the curve’s order. Also, in the CRT process, the modular is also the order of the base element.

# sage
from Crypto.Util.number import *

n = 34251514713797768233812437040287772542697202020425182292607025836827373815449
# print(factor(n))
p,q,r=11522256336953175349 , 14624100800238964261 , 203269901862625480538481088870282608241
assert p*q*r==n
BASE_POINT_x = 7331
PX,PY = (10680461779722115247262931380341483368049926186118123639977587326958923276962, 4003189979292111789806553325182843073711756529590890801151565205419771496727)
P = (PX,PY)
A=31337

B= (PY^2 - PX^3-A*PX) % n

Ep = EllipticCurve(GF(p), [A, B])
Eq = EllipticCurve(GF(q), [A, B])
Er = EllipticCurve(GF(r), [A, B])
E = EllipticCurve(IntegerModRing(n), [A, B])
Op,Oq,Or=Ep.order(),Eq.order(),Er.order()
order=Op*Oq*Or
Y=E(P)

# y^2 = x^3 + A*x + B
# Smooth
print(factor(Ep.order()))
print(factor(Eq.order()))
print(factor(Er.order()))

def get_y(a,b,p,x):
    G=GF(p)
    y2=G((x^3+a*x+b)%p)
    roots=y2.nth_root(2,all=True)
    return roots

x1= BASE_POINT_x % p
y1= get_y(A,B,p,x1)
x2= BASE_POINT_x % q
y2= get_y(A,B,q,x2)
x3= BASE_POINT_x % r
y3= get_y(A,B,r,x3)

P0=Ep((x1,y1[0]))
P1=Ep((x1,y1[1]))
P_ =Ep(P)
Q0=Eq((x2,y2[0]))
Q1=Eq((x2,y2[1]))
Q_ =Eq(P)
R0=Er((x3,y3[0]))
R1=Er((x3,y3[1]))
R_ =Er(P)

for Bp in [P0,P1]:
    dlp1=discrete_log(P_, Bp, operation="+")
    for Bq in [Q0,Q1]:
        dlp2=discrete_log(Q_, Bq, operation="+")
        for Br in [R0,R1]:            
            dlp3=discrete_log(R_, Br, operation="+")
            Base = E((BASE_POINT_x,CRT([ZZ(Bp.xy()[1]),ZZ(Bq.xy()[1]),ZZ(Br.xy()[1])],[p,q,r])))
            try:
                dlp=CRT([ZZ(dlp1),ZZ(dlp2),ZZ(dlp3)],[Bp.order(),Bq.order(),Br.order()])
                assert dlp*Base == Y
            except:
                print([dlp1,dlp2,dlp3])
                continue
            print(long_to_bytes(int(dlp)))

Sparse (medium hard, 38 solves)

I think it’s an easy challenge or maybe my solution is unexpected. Notice that $q=p-\sum_{i=1}^{5}C_i*2^{P_i}$ where $C_i$ is randomly selected form {0,-1} and $P_i$ is randomly selected from [3,417-3] ( p is 417-bit ). In some cases, p and q are close and from sqrt(n) we can derive p’s most MSBs and factor n by coppersmith method. In this challenge, it’s not applicable. Therefore, I just brute force the $P_i$ supposing that at least half of $C_i$s are zero and try to find the roots of $f=x*(x-2^i-2^j)-n$.

from Crypto.Util.number import *
from tqdm import tqdm

n = 94144887513744538681657844856583985690903055376400570170371837200724227314957348031684706936655253125445176582486308241015430205703156336248578475428712275706238423997982248462635972817633320331030484841129628650918661036694615254018290264619628335177
c = 80250313885079761377138486357617323555591919111371649902793873860183455237161293320577683249054725852540874552433031133240624696119120378419135912301004715004977978507247634217071922495893934816945961054193052791946557226599493364850793396744903765857

P.<x>=PolynomialRing(ZZ)
for i in tqdm(range(3,417-3)):
    for j in range(3,417-3):
         # for k in range(3,417-3):
        f=x*(x-2**i-2**j)-n
        roots=f.roots()
        if len(roots)!=0:
            print(roots)
# Get roots
p=306830388836804329141962887303478929481030609690558681791188661267432264489154832486621075592202056601614588786165284573906787
q=n//p

print(long_to_bytes(int(pow(c,inverse(65537,(p-1)*(q-1)),n))))

Cantilever (medium, 60 solves)

This challenge is a classic smooth prime problem and related to two famous algorithm: Pollard’s p-1 algorithm for integer factorization and Pohlig Hellman algorithm for discrete logarithm. Just implementing the two algorithms is enough for this challenge. Lately, I’m also designing crypto challenges related to the two algorithms, so this challenge makes me feel very familiar.

from tqdm import tqdm
from Crypto.Util.number import *

n = 7069789930583271525053215046247773438899869283661158227309691853515987055334306019600324056376312479212090202373516405860759222837585952590589336295698718699890424169542280710721069784487366121478569760563045886361884895363592898476736269784284754788133722060718026577238640218755539268465317292713320841554802703379684173485217045274942603346947299152498798736808975912326592689302969859834957202716983626393365387411319175917999258829839695189774082810459527737342402920881184864625678296442001837072332161966439361793009893108796934406114288057583563496587655548536011677451960307597573257032154009427010069578913
c_1 = 488692928085934899944055554857568564903346089951134051486941368561567330884363274156339625953702601270565654444836193796061118053575538224794730472032345171432952984560662218697488844007827176184413713651118743456250147472678673801728916283759932987216388378211555067885210167894310696549664382751443669387953644382833924884208966436685137553434532738845959014828804809425096115758364136546390809453200055265653531950423111482644330073443545410319576097902472017235065047191133112557289289189187696092145850680765843608118584107829268136014912479701945735063525799796920293418182776436767911172221104640501952880057
c_2 = 109770827223661560471527567179288748906402603483328748683689436879660543465776899146036833470531024202351087008847594392666852763100570391337823820240726499421306887565697452868723849092658743267256316770223643723095601213088336064635680075206929620159782416078143076506249031972043819429093074684182845530529249907297736582589125917235222921623698038868900282049587768700860009877737045693722732170123306528145661683416808514556360429554775212088169626620488741903267154641722293484797745665402402381445609873333905772582972140944493849645600529147490903067975300304532955461710562911203871840101407995813072692212

def pollard_pm1(N,B=0):
    if not B: B=ceil(sqrt(N))
    a = Integers(N).random_element()
    b = a
    for ell in tqdm(primes(B)):
        q = 1
        while q < N:
            q *= ell
        b = b^q
        if b == 1:
            return 0
        d = gcd(b.lift()-1,N)
        if d > 1: return d
    return 0

p=pollard_pm1(n,2^19)
q=n//p
assert p*q==n
e = 0x10001
flag1=long_to_bytes(int(pow(c_1,inverse(e,(p-1)*(q-1)),n)))
print(flag1)

Gp=GF(p)
c_2=Gp(c_2)
flag2 = long_to_bytes(int(c_2.log(Gp(e))))

print(flag1+flag2)

Baphomet (easy, 93 solves)

Xor tricks. From the encrypted flag length, we get the key length by $len(flag)//8=6$ . Therefore by the flag format b64encode(b"CCTF{"), we can get the 6-byte $xor\_key$ and it’s all done.

from base64 import b64encode,b64decode

def xor(b1,b2):
    return bytes([x^y for x,y in zip(b1,b2)])

encflag=open("./flag.enc","rb").read()
key_len=len(encflag)//8
# ken_len = 6
prefix = b64encode(b"CCTF{")[:key_len].decode("utf8")
known_prefix=""

for b in prefix:
    if b.islower():
        known_prefix += b.upper()
    else:
        known_prefix += b.lower()
        
print(known_prefix)
key = xor(known_prefix.encode(),encflag[:key_len])

msg=b""

for i in range(len(encflag)//key_len):
    msg+=xor(encflag[i*6:i*6+6],key)
print(msg)

flag=""

for b in msg.decode():
    if b.islower():
        flag += b.upper()
    else:
        flag += b.lower()

print(b64decode(flag.encode()))