PHL Tech Magazine

Post: SECCON Beginners CTF 2024 crypto writeup

coder_prem

coder_prem

Hi, I'm Prem. I'm professional WordPress Web Developer. I developed this website. And writing articles about Finance, Startup, Business, Marketing and Tech is my hobby.
Hope you will always get informative articles which will help you to startup your business.
If you need any kind of wordpress website then feel free to contact me at webexpertprem@gmail.com

Categories


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)

RSA cryptographyIn the problem of public key and, n

and the ciphertext cIn addition to knowing nYou 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, qThere isPrime numbers  pUsing q = 2p + 1It can be expressed asPrime numbers(safe prime). p, qIf each safe prime were separate, this would not be a problem, but in this case qused to configure pAs it is nIt has also been used in nbut n = pq = p(2p + 1) = 2p^2 + pand pIt can be expressed simply by this.

  nfrom pYou can ask forsecret keyBecause you can get ccan 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. p, qAgainst a = p - x, b = q - xcan be expressed as a, b, xexists, a, b, xWe know that is a square number, n, e, cIn addition to aband a, bA divisor of a_f, b_fis being passed.

first, a, bis a square number, so a_f^2, b_f^2Also a, bIt looks like it will be a divisor of . \frac{ab}{a_f^2b_f^2}When I calculated it, it turned out to be a small enough value.Prime FactorizationDone. Each prime factor is a, bIf you look for where it comes from, a, bIt can be said that this was what was required.

  a, bIf you understand n = pq = (a + x)(b + x) = x^2 + x(a + b) + abis the unknown variable xSo this can be solved too. xis obtained, and so on and so forth. p, qAlso required ccan 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  cFirst 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.

first nThe assertion in step 1 is m \lt nBecause I only saw mIf you change it to -1, n - 1is encrypted. This can be decrypted using step 2.

Next, do your best on step 2 cgive

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( E_1) point on G_1and on the extension fieldElliptic curves( E_2) point on G_2And there was P = sG_1, Q = tG_2, R = cstG_2Smaller than cThe 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 points P, Qto some other finite field. e(P, Q)And it has a property called bilinearity. e(aP, bQ) = e(P, Q)^{ab} is satisfied.

If you use this effectively e(sG_1, tG_2)^c = e(G_1, cstG_2)fulfilling cBy exploring cIt 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, E_1, E_2likeElliptic curvesAnd, E_2on a 12-degree extension field defined as the sextic twist ofElliptic curves  E_{12}appeared, E_1, E_2The above points are well E_{12}It 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 is P, QBoth q-torsion point is required, but G_2teeth qG_2 \ne 0So this function can’t be used, so instead Pbut qThe 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, n, e=17, t_1, t_2, c_1, c_2, c_3 You will receive: t_1, t_2is a random value, c_1 = (m + s)^e \pmod n, c_2 = (m + st_1)^e \pmod n, c_3 = (mt_2 + s)^e \pmod n(However, sare 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 this m, sThere 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 c_1, c_2 About f_1 = (m + s)^e - c_1, f_2 = (m + st_1)^e - c_2Set up a formula like this and use the elimination formula to remove the variable sIf you erase, mOne variable that has onlypolynomial  g_1can be. c_2, c_3Think similarly about g_2When you get a common root mTwo 1-variables withpolynomial  g_1, g_2is now available.

I thought that all I had to do was get the GCD for this… g_1, g_2seems to have a larger common root, \gcd(g_1, g_2)teeth m^17 + \alphaI 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, f(x) = x^{17} + \alphaThe formula is m17th order with rootpolynomialSo, in reality m^e \against nHere, 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 different nsame eHaveRSAThe ciphertext of eIf 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…

Lora Helmin

Lora Helmin

Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

Leave a Reply

Your email address will not be published. Required fields are marked *

Related Popular Posts

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.