Nookcrypt

Challenge Summary

Tom Nook is testing a new encryption scheme for nookphones, but it seems to be a bit faulty… can you break it?

The challenge description tells us that we're doing something ECC related, and that we've got to exploit a fault attack somewhere.

We're presented with a service with the following functionality

1. Gives us an encrypted version of the flag, and the string 'hello world'. If we run it enough, we observe that we occasionally get different results, clueing us into this having an error.
2. We enter a message 'x' and get Enc('x'). This is confirmed to be non-faulty via challenge hints

Solution

Recovering the curve

Since encryption returns two large numbers, we assume that these are elliptic curve points. Since (2) is non-faulty, we expect these to be on the curve, and so we use them to recover the curve. We further assume that the elliptic curve is of large characteristic, and not on an extension field. This means that the curve is the set of all points \({x, y}\) s.t. \(y^2 \equiv x^3 + ax + b\pmod p\), for fixed parameters \([a, b, p]\).

Given many elliptic curve points \((x_i, y_i)\) we want to recover the base field \(F_p\) and parameters of the elliptic curve. The idea for doing this is to first recover \(p\) by making many expressions that we can evaluate which are \(0 \pmod p\), and then taking the GCD of them. Afterwards, recovering the elliptic curve \(a, b\) is easy.

Recall that
Therefore if subtract two such equations for \((x_i, y_i)\) and \((x_{i+1}, y_{i+1})\) and re-arrange, we get

\[y_{i}^2 - y_{i+1}^2 - (x_i^3 - x_{i+1}^3) = a(x_i - x_{i + 1}) \pmod p\]

For brevity, let \(c_i := y_{i}^2 - y_{i+1}^2 - (x_i^3 - x_{i+1}^3)\)

We can rewrite this as \(a \equiv c_i(x_i - x_{i+1})^{-1} \pmod p\)

However we can make a similar such expression for \(a\), for every pair of points \((x_i, x_{i+1})\). Setting two such expressions equal to one another, we get \[c_{i+1}(x_{i+1} - x_{i+2})^{-1} \equiv c_i(x_i - x_{i+1})^{-1} \pmod p\]

We can't actually evaluate this due to the modular inverse, so we multiply both sides by the inverses. Finally, we rearrange to get something \(0 \pmod p\):

\[c_{i+1}(x_i - x_{i+1}) - c_i(x_{i+1} - x_{i+2}) \equiv 0 \pmod p\]

We can evaluate the left hand side over the integers, since we know all the constituent terms. Therefore we take the GCD of many such expressions to recover \(p\).
To recover \(a\) use the expression for \(a\) derived before, and finally to recover \(b\) use the elliptic curve equation.

Doing this we've recovered the elliptic curve.

Recovering the encryption function

Since this is sourceless, we guess that we don't actually have an encryption function, and instead \(Enc(x) = xG\), G being the elliptic curve generator. To test this, we send \(Enc(1)\) to the server and set \(G\) to this value, and choose \(x\) at random, and get \(Enc(x)\) and just check if \(xG = Enc(x)\). It turns out that this is true.

Sicing the flag

Finally time to get the flag. Our goal is essentially to recover the discrete logarithm of \(Enc(Flag)\), leveraging the fact we have faulty computations of \(Enc(Flag)\). They clarified that the error model is an odd one, where the prime \(p\) of the elliptic curve is corrupted to \(p'\) throughout the entire encryption, and corrupted in the same way for Enc(flag) and Enc("hello world").

So what does it mean if the prime \(p\) is corrupted to \(p'\) and we actually do computations on the Elliptic curve \(y^2 \equiv x^3 + ax + b \pmod{p'}\)?

First, with overwhelming probability our generator \(G\) is not actually on this elliptic curve. However, for any EC point \(Z\), and numbers \(a, p'\), there exists a \(b'\) such that \(Z\) is on the elliptic curve with parameters \([a, b', p']\). Exercise: Convince yourself of this =). Recall that on a short weierstrass curve, the addition and point doubling laws don't depend on \(b\). Therefore it is perfectly fine to consider our \(G\) as being on the curve \(y^2 \equiv x^3 + ax + b' \pmod{p'}\).

With overwhelming probability, this curve is weak, so we can do small subgroup attacks to recover the discrete log modulo distinct small primes. (This high level attack idea is basically the same as invalid curve attacks, sans the different prime \(p'\).) We then repeat for different corruptions to recover the flag modulo many small primes, and finally just CRT to recover the flag.

Moreover, we find that sometimes \(p'\) is not actually a prime, but instead has factors \(cd\). In these cases, you really have two elliptic curves with the same \(a,b\) parameters, just one mod \(c\) and one mod \(d\). This makes breaking such curves even easier.

Recovering the faulty \(b', p'\) parameters

All thats left is to describe how we get the new curve parameters \(b'\) and \(p'\). Notice that we know 3 points on this new curve, Enc(Flag), Enc("hello\ world"), and \(G\). Let these be represented as \((x_0, y_0), (x_1, y_1), (x_2, y_2)\). The core idea is the same as how we recovered the elliptic curve prime, get two equations that are 0 mod p'. To do this, we take the curve equation for each point, subtract two such equations to remove the dependence on \(b'\), and re-arrange terms. This gives us:

\[y_i^2 - y_{i + 1}^2 - (x_i^3 - x_{i+1}^3) - a(x_i - x_{i + 1}) \equiv 0 \pmod{p'}\]

We take the GCD of two such equations, and then use the defining elliptic curve equation to recover \(b'\). Thus using the idea of the prior section we sice the flag uiuctf{th4t_5ur3_w4s_f4ulty_huh?}