or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
Nookcrypt
Challenge Summary
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

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