SECCON Beginners CTF 2024 crypto writeup

I attended SECCON Beginners CTF 2024 and solved the crypto problems. It took me about 5 hours to solve all 5 problems, which was probably the best.*1The other four questions were Second Blood.

While I was relieved to see that I was still able to maintain a certain level of ability in the crypto field, looking back it is disappointing that I became satisfied before tackling the problems in other categories, which resulted in my final score and ranking being so subpar.

• Safe Prime (12 mins)
• Math (17 points)
• ARES (1 hour 16 minutes)
• bless (59 points)
• Try hard in my style (2 hours)

Safe Prime (12 mins)

RSA cryptographyIn the problem of public key

and the ciphertextIn addition to knowingYou can see that it is made up as follows:

while True:
    p = getPrime(512)
    q = 2 * p + 1
    if isPrime(q):
        break

n = p * q

As the question name suggests,There isPrime numbersUsingIt can be expressed asPrime numbers(safe prime).If each safe prime were separate, this would not be a problem, but in this caseused to configureAs it isIt has also been used inbutandIt can be expressed simply by this.

fromYou can ask forsecret keyBecause you can getcan be decrypted and a flag is obtained. You can solve the equation directly, but this time I was lazy and solved it using SageMath.

n = 2929...
c = 4079...
PR.<x> = PolynomialRing(ZZ)
f = x*(2*x + 1) - n
p = int(f.roots()(0)(0))
q = n // p

d = pow(65537, -1, (p-1)*(q-1))
m = pow(c, d, n)
print(bytes.fromhex(hex(m)(2:)).decode())

It's been a while since my last CTF, so it took me 12 minutes to set up the environment.

Math (17 points)

me tooRSAThis is the problem.Againstcan be expressed asexists,We know that is a square number,In addition toandA divisor ofis being passed.

first,is a square number, soAlsoIt looks like it will be a divisor of .When I calculated it, it turned out to be a small enough value.Prime FactorizationDone. Each prime factor isIf you look for where it comes from,It can be said that this was what was required.

If you understandis the unknown variableSo this can be solved too.is obtained, and so on and so forth.Also requiredcan be decrypted.

The solution script is here. It's pretty messy now. I think I can write it a bit better.

n = 2834...
e = 65537
cipher = 2158...
ab = 2834...

af = 4701...
bf = 3576...

assert ab % (af^2 * bf^2) == 0
factors = list(factor(ab // (af^2 * bf^2)))

PR.<x> = PolynomialRing(ZZ)

for i in range(0, 2**len(factors)):
    a = int(af**2)
    b = int(bf**2)
    for j in range(0, len(factors)):
        if (i >> j) & 1:
            a *= int(factors(j)(0)) ** int(factors(j)(1))
        else:
            b *= int(factors(j)(0)) ** int(factors(j)(1))

    f = (a + x) * (b + x) - n
    for ans in f.roots():
        xx = int(ans(0))**int(ans(1))
        if not is_square(xx):
            break

        p = a + xx
        q = b + xx

        d = pow(e, -1, (p-1)*(q-1))
        m = pow(cipher, d, n)
        print(bytes.fromhex(hex(m)(2:)))

ARES (1 hour 16 minutes)

I kept relatively careful notes while I was solving the problems, so I'll just paste them here as is.

RSA Flag encrypted with First you get it, and then you can do the following infinitely

• 1: Any plaintext RSAEncrypt with → CBCEncrypted with AES in mode
• 2: Any ciphertext CBCDecrypt with AES in mode → RSADecrypt with
  • However, the ciphertext must be aligned.

firstThe assertion in step 1 isBecause I only sawIf you change it to -1,is encrypted. This can be decrypted using step 2.

Next, do your best on step 2give

If you implement this as is, it will look like this:

from ptrlib import Socket, xor, chunks

sock = Socket("nc ares.beginners.seccon.games 5000")

e = int(65537)
enc_flag = int(sock.recvlineafter("enc_flag: ").strip(), 16)


sock.sendlineafter("> ", "1")
sock.sendlineafter("m: ", "-1")
c = sock.recvlineafter("c: ")
sock.sendlineafter("> ", "2")
sock.sendlineafter("c: ", c)
n = int(sock.recvlineafter("m: ")) + 1


sock.sendlineafter("> ", "1")
sock.sendlineafter("m: ", str(2**1000))
c = bytes.fromhex(sock.recvlineafter("c: ").decode().strip())
c = chunks(c, 16)

target = int.to_bytes(enc_flag, 128, "big")
target = chunks(target, 16)

plaintext_block = chunks(int.to_bytes(int(pow(2**1000, e, n)), 128, "big"), 16)

for k in range(1, len(target)):
    c(-(k+1)) = xor(xor(c(-(k+1)), plaintext_block(-k)), target(-k))

    
    sock.sendlineafter("> ", "2")
    sock.sendlineafter("c: ", b"".join(c).hex())
    m = int(sock.recvlineafter("m: "))
    d = pow(m, e, n)
    d = int.to_bytes(int(d), 128, "big")
    plaintext_block = chunks(d, 16)


iv = xor(xor(c(0), plaintext_block(0)), target(0))
c = b"".join(c(1:)) 
sock.sendlineafter("> ", "2")
sock.sendlineafter("c: ", (iv + c).hex())
flag = int(sock.recvlineafter("m: "))
print(int.to_bytes(flag, 128, "big"))

This problem was very interesting. From the simple problem setting,RSAIt is necessary to come up with a seemingly complicated solution that goes back and forth between the world of AES and the world of RSA. Oracle The attack is well-balanced and pretty clean.scriptI think it's a good problem for beginners, and also a good example of how to combine multiple cryptosystems.

bless (59 points)

BLS12-381Elliptic curves() point onand on the extension fieldElliptic curves() point onAnd there wasSmaller thanThe problem is to find the answer.

At first glance, the question format reminds me of pairing, and BLS12-381 is not a familiar question.Elliptic curvesHowever, I also recall that it had something to do with pairing.

What is pairing?Elliptic curvesTop two pointsto some other finite field.And it has a property called bilinearity. is satisfied.

If you use this effectivelyfulfillingBy exploringIt seems that what is required is…

To specifically achieve this, I searched for “pairing BLS12-381” and found the following article. According to the article, when using BLS12-381,likeElliptic curvesAnd,on a 12-degree extension field defined as the sextic twist ofElliptic curvesappeared,The above points are wellIt seems that pairing calculations can be performed by transferring the data to

project-euphoria.dev

I must have attended the Yoshicamp lecture that this article was based on, but I had forgotten the content, soScript KiddieThe function weil_pairing used in the article isBoth-torsion point is required, butteethSo this function can't be used, so insteadbutThe tricky part was that I needed to use tate_pairing, which only requires that it be a -torsion point.

import json

p = 0x1a01...
q = 0x73ED...

F1 = GF(p)
E1 = EllipticCurve(F1, (0, 4))
G1 = E1(0x17..., 0x08...)

F2 = GF(p^2, 'x', modulus=x^2+1)
E2 = EllipticCurve(F2, (0, 4*(1+F2.gen())))

F12.<w> = GF(p**12, "w", x**12 - 2*x**6 + 2)
i12 = w**6 - 1
z = w^-1
E12 = EllipticCurve(F12, (0, 4))

def F2_to_F12(coeffs):
    assert len(coeffs) == 2
    c, d = coeffs
    return c + d*i12


def sextic_twist(P):
    x = F2_to_F12(P.x().list())
    y = F2_to_F12(P.y().list())
    return E12(z^2*x, z^3*y)

def load(data):
    P = E1(data("P")("x"), data("P")("y"))
    Q = E2(F2(data("Q")("x")), F2(data("Q")("y")))
    R = E2(F2(data("R")("x")), F2(data("R")("y")))

    return P, Q, R

data = json.load(open("output.json"))

flag = ()
for d in data:
    P, Q, R = load(d)

    a = E12(P).tate_pairing(sextic_twist(Q), q, 12)
    b = E12(G1).tate_pairing(sextic_twist(R), q, 12)
    for v in range(1, 256):
        if a**v == b:
            flag.append(v)
            break
    print(bytes(flag))

I think this was a very good introductory problem about pairing. This was the first problem I was able to solve that involved pairing, and I think it prepared me well for problems that involve pairing.

Try hard in my style (2 hours)

RSAWhen connecting to the server, You will receive:is a random value,(However,are random unknown variables).

There are three ciphertexts, and it seems likely that they can be solved by exploiting some relationship between the ciphertexts.

For now, let's leave it like thisThere are two unknown variables, so I don't know what to do. First,Coppersmith’s Short Pad Attack Consider deleting a variable in the following way:

Appropriately AboutSet up a formula like this and use the elimination formula to remove the variableIf you erase,One variable that has onlypolynomialcan be.Think similarly aboutWhen you get a common rootTwo 1-variables withpolynomialis now available.

I thought that all I had to do was get the GCD for this…seems to have a larger common root,teethI don't know how this happened, but I'm still not able to solve it in this state, so I'm in trouble.

I was in trouble,The formula is17th order with rootpolynomialSo, in realityHere, the nature of the problem that “you get a new value every time you connect to the server” comes into play, and the same plaintext is encrypted with differentsameHaveRSAThe ciphertext ofIf we gather togetherHaståd’s Broadcast Attack is possible.

So this problem was solved as follows

from ptrlib import Socket, crt

def pgcd(a, b):
  while b:
    a, b = b, a % b
  return a.monic()


e = 17
def collect():
    sock = Socket("localhost", 9999)
    

    
    n = int(sock.recvlineafter("n=").strip())
    t1 = int(sock.recvlineafter("t1=").strip())
    t2 = int(sock.recvlineafter("t2=").strip())
    c1 = int(sock.recvlineafter("c1=").strip())
    c2 = int(sock.recvlineafter("c2=").strip())
    c3 = int(sock.recvlineafter("c3=").strip())

    PR.<m, s> = PolynomialRing(Zmod(n))

    PRz = PolynomialRing(Zmod(n), ("mz", "sz"))
    f1 = (m + s)**e - c1
    f2 = (m + s*t1)**e - c2
    g1 = f1.change_ring(PRz).resultant(f2.change_ring(PRz), s)

    PRy = PolynomialRing(Zmod(n), ("my", "sy"))
    f3 = (m + s*t1)**e - c2
    f4 = (m*t2 + s)**e - c3
    g2 = f3.change_ring(PRy).resultant(f4.change_ring(PRy), s)

    PRn.<mn> = PolynomialRing(Zmod(n))
    h1 = PRn(g1.univariate_polynomial())
    h2 = PRn(g2.univariate_polynomial())

    k = pgcd(h1, h2)
    
    c = int(-k.constant_coefficient())
    return c, n

pairs = ()
for _ in range(e):
    c, n = collect()
    pairs.append((c, n))
x = crt(pairs)(0)
flag = Integer(x).nth_root(e)
print(bytes.fromhex(hex(flag)(2:)).decode())

It was a very satisfying problem because it allowed me to approach the problem by repeatedly considering and experimenting to find an effective policy. The problem itself was reminiscent of Franklin-Reister's Related Message Attack, but also involved variable elimination like Coppersmith's Short Pad Attack.polynomialGCD, Haståd's Broadcast Attack andRSAorpolynomialThe structure of the exhibition allows visitors to take a cross-sectional look at various approaches to this issue, which I think is very beautiful.

The only thing I regret is that I was misled by the “Hard” tag and ended up writing down the time it took to clear the variables, and that I caused a lot of bugs in the experiment, which slowed down the solution.

---

This year's SECCON Beginners CTF was also very interesting and educational, providing problems that could be a stepping stone to the next CTF, and I thought it was a good crypto set. It was fun.

*1:I think I would have lost if chocorusk, who had solved the two more difficult questions before me, had tried all of them…