Potluck CTF - Upside-down Cake

This is the solution of the challenge “Upside-down Cake” from Potluck CTF. It was an modular equation solved after transformation by the Coppersmith method applied to bivariate polynomials.

Details

Category: cryptography

Author: Neobeo

Points: 258

Description

Let’s bake a cake – an upside-down cake full of secrets! Ready to flip the script?

challenge16-dist.tgz

Solution

The python script is simple, the flag is 44 byte long and has the form potluck{???????????????????????????????????}. It is split into two halves. Each half is inverted modulo $p$ and added together. We got the result in the comment:

1

# upside_down_cake = 5437994412763609312287807471880072729673281757441094697938294966650919649177305854023158593494881613184278290778097252426658538133266876768217809554790925406

The only confusing part is the computation of $p$:

1

p = ~-(-~(()==()))** 521

But if we break it into pieces we have:

1
2
3
4

>>> -~(()==())
2
>>> -(-~(()==()))** 521 == -(2**521)
True

Finally using the bitwise not operator ~ on $-(2^{521})$ flips all the bits and gives $p = 2^{521}-1$

1
2
3

>>> p = ~-(-~(()==()))** 521
>>> p == 2**521 - 1
True

Then we have the equation: $$x^{-1} + y^{-1} = a \mod p$$ With $a$ being the value given in the comment. The first thing to notice is that the values $x,y$ are 176 bit long which is very small compared to $p$. This kind of equation can be solved for small roots by a variation of the Coppersmith method applied to bivariate polynomials. However we do not have yet a bivariate polynomials. If we multiply both side by $xy$ we got: $$y + x = xya \mod p$$ Now we can applied such method but the solution $(0,0)$ is now a valid solution and very small as well. To overcome that, we can integrate in our polynomial the fact that $x$ start with the value potluck{. We can compute $x_0$ being the known upper bits of $x$:

1

x0 = int.from_bytes(b"potluck{") << (14*8)

Now, our polynomial is: $$(x+x_0) + y = (x+x_0)ya$$ With $x$ being only 112 bits long. Coppersmith method for bivariate polynomials is not implemented in Sage but I used an implementation by William Wang. The method gave two solutions:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

load("coppersmith.sage")
sage: X = 2^112
sage :Y = 2^176
sage: p = ~-(-~(()==()))** 521
sage: R = Integers(p)
sage: P.<x, y> = PolynomialRing(R)
sage: a = 5437994412763609312287807471880072729673281757441094697938294966650919649177305854023158593494881613184278290778097252426658538133266876768217809554790925406
sage: x0 = int.from_bytes(b"potluck{") << (14*8)
sage: pol = (x+x0) + y - (x+x0)*y*a
sage: sol = small_roots(pol, (X,Y))
sage: sol
[(6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977272374905955192577815649869195249672466374139562717052,
  42067066288931243978195966060845361747012678086516601),
 (2458010838905120235951082448314233,
  18130580763265784669399824700546101403407444085862269)]

Hopefully the second one gave the flag:

1
2

sage: print(b"potluck{" + int(sol[1][0]).to_bytes(14) + int(sol[1][1]).to_bytes(22))
b'potluck{y0u_c4n_hav3_y0ur_cak3_&_ea7_1t_t0o}'