A Dance of add and mul - Alpacahack Round 3

Table of Contents

Challenge overview

Here’s a brief overview of the challenge code:

flag = os.environ.get("FLAG", "fakeflag").encode()
bit_length = len(flag) * 8

# BLS12-381 curve
p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
K = GF(p)
E = EllipticCurve(K, (0, 4))

G1, G2 = E.gens()
o1, o2 = G1.order(), G2.order()

xs = [random.randrange(0, o1) for _ in range(bit_length + 1)]
m = bytes_to_long(flag)

cs = []
for c, (x1, x2) in zip(bin(m)[2:].zfill(bit_length), zip(xs[:-1], xs[1:])):
  if c == "1":
    x1, x2 = x2, x1
  cs.append(x1 * G1 + x2 * G2)

print([P.xy() for P in cs])

It first generates some random numbers $x_i$, and then, for each bit of the flag, it computes:

$$ P_i = \begin{cases} x_i \cdot G_1 + x_{i+1} \cdot G_2, & \text{if } c_i = 0 \\ x_{i+1} \cdot G_1 + x_i \cdot G_2, & \text{if } c_i = 1 \end{cases} $$

We are not given the $x_i$ values, so there must be a way to either recover them from the $P_i$ values, or to distinguish the swap.

Solution

First, notice that the curve is a known one, so there are no direct attacks on it. Also, we are given 2 generators $G_1$ and $G_2$ for the curve, with the same order $o_1 = o_2$.

The order of $G_i$ can be factored as:

$$ o_i = 3 \cdot 11 \cdot 10177 \cdot 859267 \cdot 52437899 \cdot p $$

where $p$ is a large prime number.

While the order of the curve is:

$$ 3 \cdot 11^2 \cdot 10177^2 \cdot 859267^2 \cdot 52437899^2 \cdot p $$

So, the curve can be decomposed as:

$$ E(K) \cong \mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/(11 \cdot \text{...} \cdot 52437899)\mathbb{Z} \times \mathbb{Z}/(11 \cdot \text{...} \cdot 52437899)\mathbb{Z} \times \mathbb{Z}/p\mathbb{Z} $$

In fact, for cryptographic applications, the generator used is a point with order $p$, so it generates only one prime cyclic subgroup of the curve.

All this to say that $G_1$ and $G_2$ generate different cyclic subgroups of points (but not distinct), and so there is no relation of the form $G_1 = a \cdot G_2$. To generate all the points of the curve, we can do

$$ P = a \cdot G_1 + b \cdot G_2 $$

.

One important takeaway from this analysis is that both orders have small factors, so if we had an equation in the form $P_i = x_i \cdot G_1$ or $P_i = x_i \cdot G_2$, we could solve the Dlog for the small factors, thus recovering $x_i$ modulo the small factors (with Pohlig-Hellman).

2 points at a time

A very easy way to get such an equation is to compute the difference between two consecutive points. For the first 2 points, as we know that $c_0$ is 0 (ASCII starts with bit 0):

$$ P_0 - P_1 = \begin{cases} (x_0 - x_1) \cdot G_1 + (x_1 - x_2) \cdot G_2 & \text{if } c_1 = 0 \\ (x_0 - x_2) \cdot G_1 & \text{if } c_1 = 1 \end{cases} $$

Now we could try to compute the Dlog (or the Weil pairing). If it fails, then we know that $c_1 = 0$.

sage: R = G1 + G2
sage: R.log(G1)
ValueError: ECDLog problem has no solution (non-trivial Weil pairing)

Extending this idea for all the cases of $c_i$ and $c_{i+1}$ we can recover the flag.

1 point at a time (recovering partial $x_i$)

Another way is to exploit the small factors of the order (this is what I did to solve the challenge).

First multiply each point by $ 3 \cdot 859267 \cdot 52437899 \cdot p$, so getting $P_i$ and $G_i$ with order $ 11 \cdot 10177 $ (Very small!).

From here, we could compute the 2dimensional Dlog using Weil pairing, or we could use isogenies.

Notice that if we construct an isogeny $\varphi$ with kernel generated by $G1$ and apply it to $P_i$, this will result in

$$ \varphi (P_i) = \varphi(x_i \cdot G_1 + x_{i+1} \cdot G_2) = x_i \cdot \varphi(G_1) + x_{i+1} \cdot \varphi(G_2) = x_{i+1} \cdot \varphi(G_2) $$
sage: G1 = G1 * cof
sage: G2 = G2 * cof
sage: G1.order().factor()
11 * 10177
sage: G2.order().factor()
11 * 10177
sage: phiG1 = E.isogeny(G1, algorithm='factored')
sage: phiG2 = E.isogeny(G2, algorithm='factored')

So, for each $P_i$ we can apply the isogeny and compute

$$ \begin{aligned} x_{i+1} &\ = \ \text{discrete\_log}(\varphi_{G_1}(P_i), \varphi(G_2)) \\ x_i &\ = \ \text{discrete\_log}(\varphi_{G_2}(P_i), \varphi(G_1)) \end{aligned} $$

Do this for each $P_i$ and we have recovered the coefficients $x_i$ modulo $11 \cdot 10177$.

At this point recovering the flag is trivial.

recxs = [outs[0][0], outs[0][1]]
recbits = '0'
for a, b in outs[1:]:
  if a == recxs[-1]:
    recxs.append(b)
    recbits += '0'
  else:
    recxs.append(a)
    recbits += '1'
print(bytes.fromhex(hex(int(recbits, 2))[2:]))
# b'Alpaca{this_title_is_inpired_by_a_rhythm_game}'