cd ~

soon_haari

f, l and ag

I authored a challenge for Dreamhack Invitational Quals, and the CTF was ended with one solve for this challenge.

This challenge is a revenge version of fl and ag which was authored by poro(kwoncycle).

Description

Amo was playing and split the flag! Then, Nando tripped over the split flag and it broke into even more pieces!
Can the three pieces of the flag be put back together?

The format of the flag is DH{...}.

prob.py

from Crypto.Util.number import getPrime, GCD, bytes_to_long

while True:
    p = getPrime(1024)
    q = getPrime(1024)
    e = 0x101
    if GCD((p - 1) * (q - 1), e) == 1:
        break
N = p * q

with open('flag', 'rb') as f:
    flag = f.read()
    assert len(flag) == 68

f, l, ag = flag[:17], flag[17:34], flag[34:]
f, l, ag, flag = map(bytes_to_long, (f, l, ag, flag))

f_enc = pow(f, e, N)
l_enc = pow(l, e, N)
ag_enc = pow(ag, e, N)
flag_enc = pow(flag, e, N)

print(f"{N = }")
print(f"{e = }")
print(f"{f_enc = }")
print(f"{l_enc = }")
print(f"{ag_enc = }")
print(f"{flag_enc = }")

The intended solution works with 3 big steps. I will define some variables before starting.

$A$ = f, $B$ = l, $C$ = ag, $D$ = flag

$A_{e}$ = f_enc, $B_{e}$ = l_enc, $C_{e}$ = ag_enc, $D_{e}$ = flag_enc

Also, $a$ = $A / C$, $b$ = $B / C$

Note that every operation is handled on $\mathbb{Z}_N$.

  1. We have 3 multivariate polynomials represented with $a$, $b$. So let’s somehow use Franklin-Reiter attack, and construct another polynomial only represented with $b$.
  2. Apply Franklin-Reiter attack to recover $b$. We can easily recover $a$ after that.
  3. $a$ is defined by $A / C$ and $A, C$ is much smaller compared to $N$, so we can recover $A, C$ with LLL algorithm. Recover $B$ and finally solve the challenge.

Step 1.

This is the proven information.

$A^{257} = A_{e}, B^{257} = B_{e}, C^{257} = C_{e}, D^{257} = D_{e}$

$D$ is the concatenated result of $A$, $B$, $C$, or f, l, ag, and they have the size of 17, 17, 34 bytes, so $D$ can be written differently.

$D = 256^{51}A + 256^{34}B + C$

Divide both sides with $C$, in the same way with fl and ag.

$D / C = 256^{51}a + 256^{34}b + 1$
$D_{e} / C_{e} = (256^{51}a + 256^{34}b + 1)^{257}$
$(256^{51}a + 256^{34}b + 1)^{257} = D_{e} / C_{e}$

And these are the other equations provided to us.

$a^{257} = A_{e} / C_{e}, b^{257} = B_{e} / C_{e}$


We define 3 functions according to the info.

$f_{1}(x, y) = (256^{51}x + 256^{34}y + 1)^{257} - D_{e} / C_{e}$
$f_{2}(x) = x^{257} - A_{e} / C_{e}$
$f_{3}(y) = y^{257} - B_{e} / C_{e}$

Note that the result of $f_{1}(a, b), f_{2}(a), f_{3}(b)$ are all zero.



The idea of using the Franklin-Reiter attack, and polynomial GCD is correct, but since there are 2 variables it can’t be done with the same method.

A lot of people thought of using Gröbner basis(including RBTree), but we concluded that it would be difficult.


This challenge can be solved by assuming one variable($y$) is a constant and focusing on eliminating the other variable($x$).

Q.<y> = PolynomialRing(Zmod(N))
P.<x> = PolynomialRing(Q)

f1 = P((x * 256^51 + y * 256^34 + 1)^e - (flag_enc / ag_enc) % N)
f2 = P(x^e - (f_enc / ag_enc) % N)
f3 = Q(y^e - (f_enc / ag_enc) % N)

Set the PolynomialRing like this with SageMath, and lower $x$’s exponent step-by-step. Our goal is to make $x$ disappear.

Since f1(a) == 0, and f2(a) == 0 are always satisfied, applying GCD keeps satisfying f1(a) == 0과 f2(a) == 0.


The twist is that monic operation is not possible in this case, while it is needed for polynomial GCD. Because we can’t find the inverse of constants(polynomial of $y$ in this case).

However, multiplying the coefficient of $x$’s highest order term of other polynomials makes two polynomials have the same highest order term.

By subtraction, we can lower $x$’s power one-by-one.

However2, the size of constant coefficients(polynomial of $y$) gets extremely large, so it must be updated using f3 which is also a known polynomial of $y$. That way, every coefficient stays under the power of $y^{257}$.

It can be simply implemented like this.

while f2.degree() > 0:
    f1_coef = f1[f1.degree()]
    f2_coef = f2[f2.degree()]

    f1 *= f2_coef
    f2 *= f1_coef

    f1 = P([coef % f3 for coef in list(f1)])
    f2 = P([coef % f3 for coef in list(f2)])

    f1 -= f2 * x^(f1.degree() - f2.degree())

    if f1.degree() < f2.degree():
        f1, f2 = f2, f1

g = f2[0]

Step 2.

Now as we said earlier, we can recover b with Franklin-Reiter attack for g and f3, and recover a, A, B, C and solve the challenge.

My full solve code: ex.sage