SECCON Beginners CTF 2024 crypto writeup

Post: SECCON Beginners CTF 2024 crypto writeup

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

Safe Prime (12 mins)

RSA cryptographyIn the problem of public key $e, n$

and the ciphertext $c$ In addition to knowing $n$ You 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, $q$ There isPrime numbers $p$ Using $q = 2p + 1$ It can be expressed asPrime numbers(safe prime). $p, q$ If each safe prime were separate, this would not be a problem, but in this case $q$ used to configure $p$ As it is $n$ It has also been used in $n$ but $n = pq = p(2p + 1) = 2p^2 + p$ and $p$ It can be expressed simply by this.

$n$ from $p$ You can ask forsecret keyBecause you can get $c$ can 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, q$ Against $a = p - x, b = q - x$ can be expressed as $a, b, x$ exists, $a, b, x$ We know that is a square number, $n, e, c$ In addition to $ab$ and $a, b$ A divisor of $a_f, b_f$ is being passed.

first, $a, b$ is a square number, so $a_f^2, b_f^2$ Also $a, b$ It 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, b$ If you look for where it comes from, $a, b$ It can be said that this was what was required.

$a, b$ If you understand $n = pq = (a + x)(b + x) = x^2 + x(a + b) + ab$ is the unknown variable $x$ So this can be solved too. $x$ is obtained, and so on and so forth. $p, q$ Also required $c$ can 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 $c$ 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.

first $n$ The assertion in step 1 is $m \lt n$ Because I only saw $m$ If you change it to -1, $n - 1$ is encrypted. This can be decrypted using step 2.

Next, do your best on step 2 $c$ give

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_1$ and on the extension fieldElliptic curves( $E_2$ ) point on $G_2$ And there was $P = sG_1, Q = tG_2, R = cstG_2$ Smaller than $c$ The 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, Q$ to 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 $c$ By exploring $c$ It 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_2$ likeElliptic curvesAnd, $E_2$ on a 12-degree extension field defined as the sextic twist ofElliptic curves $E_{12}$ appeared, $E_1, E_2$ The 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, Q$ Both $q$ -torsion point is required, but $G_2$ teeth $qG_2 \ne 0$ So this function can’t be used, so instead $P$ but $q$ The 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_2$ is 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, $s$ 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 this $m, s$ There 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_2$ Set up a formula like this and use the elimination formula to remove the variable $s$ If you erase, $m$ One variable that has onlypolynomial $g_1$ can be. $c_2, c_3$ Think similarly about $g_2$ When you get a common root $m$ Two 1-variables withpolynomial $g_1, g_2$ is now available.

I thought that all I had to do was get the GCD for this… $g_1, g_2$ seems to have a larger common root, $\gcd(g_1, g_2)$ teeth $m^17 + \alpha$ I 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} + \alpha$ The formula is $m$ 17th order with rootpolynomialSo, in reality $m^e \against n$ Here, 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 $n$ same $e$ HaveRSAThe ciphertext of $e$ If 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

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

Post: SECCON Beginners CTF 2024 crypto writeup

coder_prem

Categories

Recent Posts

7 Examples of Great Branded Content

UK Business Growth: Essential Legal Services for Startups

Making Your Products Stand Out

Can chiplets save the US semiconductor industry? – Computerworld

‘Moana 2’ sails to a record $221 million opening as Hollywood celebrates a moviegoing feast – National

Safe Prime (12 mins)

Math (17 points)

ARES (1 hour 16 minutes)

bless (59 points)

Try hard in my style (2 hours)

Lora Helmin

Leave a Reply Cancel reply

Related Popular Posts

7 Examples of Great Branded Content

UK Business Growth: Essential Legal Services…

Making Your Products Stand Out

About PHL TECH MAGAZINE

Recent Posts

Genuine TFSA contribution mistake still leads to CRA tax and penalty

Is retirement still possible after a costly divorce at age 61?

How to stay on budget when travelling this summer

Get interesting news