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}'