# Some Elliptic Curve Cryptography Attacks
Trong Blog này chúng ta sẽ tìm hiểu qua một số kiểu tấn công cơ bản đối với hệ mật đường cong Elliptic, nội dung trong bài được mình tham khảo trong hai trang là [**elikaski**](https://github.com/elikaski/ECC_Attacks) và [**jvdsn**](https://github.com/jvdsn/crypto-attacks/tree/master/attacks/ecc).

## ECDH Attacks
### Recovers Parameters When Two Points Are Known
Cho một đường cong $E$ được định nghĩa trong trường hữu hạn $\text{GF}(p)$ như sau:
$$E:y^2 \equiv x^3 + a.x + b \pmod p$$

Giả sử ta **chưa biết** hai giá trị quan trọng của đường cong là $a$ và $b$, nhưng ta biết được tọa độ của **hai điểm** thuộc đường cong là $Q(x_Q,y_Q)$ và $G(x_G,y_G)$ thì ta sẽ khôi phục lại $a$ và $b$ như thế nào?

Từ $Q(x_Q,y_Q)$ và $G(x_G,y_G)$, ta sẽ có hệ phương trình như sau:
$$
\left\{\begin{matrix}
y^2_Q \equiv x_Q^3 + a.x_Q + b \pmod p \hspace{5mm} (1)\\
y^2_G \equiv x_G^3 + a.x_G + b \pmod p \hspace{5mm} (2)
\end{matrix}\right.
$$

Lấy $(2) - (1)$ ta được:
$$y^2_G - y^2_Q \equiv x_G^3 - x_Q^3 + (x_G - x_Q).a \pmod p$$

Cô lập $a$ và ta được công thức tính $a$ là:
$$a \equiv \frac{(y^2_G - y^2_Q) - (x_G^3 - x_Q^3)}{x_G - x_Q} \pmod p$$

Có $a$, ta thay vào phương trình $(1)$ rồi cô lập $b$:
$$b \equiv y^2_Q - x_Q^3 - a.x_Q \pmod p$$

++**Ví dụ:**++ Cho đoạn code dưới đây, yêu cầu tìm lại giá trị $a$ và $b$ từ các dữ kiện đã cho.
:::spoiler **Source**

from sage.all import *

from sage.all import *

p = 0xfffffffffffffffffffffffffffffffeffffffffffffffff
a = ?
b = ?
E = EllipticCurve(GF(p), [a, b])

d = randint(1, p)
G = E.gens()[0]
Q = G * d

print(f"{p = }")
print(f"G = {G.xy()}")
print(f"Q = {Q.xy()}")

# p = 6277101735386680763835789423207666416083908700390324961279
# G = (3289624317623424368845348028842487418520868978772050262753, 5673242899673324591834582889556471730778853907191064256384)
# Q = (5089873073180314048188387513463598376496673089867943506536, 2442666922275797550562962625908997817036343309306014041744)

:::
Ta sẽ code một hàm để tính toán lại $a$ và $b$ từ lý thuyết đã học ở trên như sau:

def recover(p, x1, y1, x2, y2): #Truyền Q hay G trước đều được
    a = pow(x1 - x2, -1, p) * (pow(y1, 2, p) - pow(y2, 2, p) - (pow(x1, 3, p) - pow(x2, 3, p))) % p
    b = (pow(y1, 2, p) - pow(x1, 3, p) - a * x1) % p
    return int(a), int(b)

**Kết quả:**

a = 6277101735386680763835789423207666416083908700390324961276
b = 2455155546008943817740293915197451784769108058161191238065

---

### The Order Of The Generator Is Too Small

:::info
:pencil: **order** của điểm sinh cũng bằng **order** của đường cong.
:::

Tương tự như RSA khi sử dụng hai số nguyên tố $p$ và $q$ quá nhỏ để tạo modulus thì với **ECC**, nếu như ta sử dụng đường cong có modulus quá nhỏ, cỡ $\leq 45$ bit thì bài toán **DLP** sẽ được giải rất nhanh, với độ phức tạp chỉ là $O(\sqrt{n})$ với $n$ là **order** của đường cong mà thôi.

++**Ví dụ:**++ Cho đoạn code dưới đây, yêu cầu tìm lại khóa bí mật $d$ từ các dữ kiện đã cho.
:::spoiler **Souce**

from sage.all import *

p = random_prime(2**32)
a = randint(1, p)
b = randint(1, p)

E = EllipticCurve(GF(p), [a,b])
G = E.gens()[0]
n = G.order()

d = randint(1, p)
Q = d * G

print(f"{a = }")
print(f"{b = }")
print(f"{p = }")
print(f"G = {G.xy()}")
print(f"Q = {Q.xy()}")

# a = 469959113
# b = 435140083
# p = 957749491
# G = (498070615, 681830144)
# Q = (328569657, 868726199)

:::
Thấy rằng modulus của đường cong $E$ khá là khiêm tốn, chỉ $32$ bit mà thôi, ta hoàn toàn có thể sử dụng hàm `discrete_log()` của **sagemath** để tính lại $d$ từ $Q$ và $G$ luôn:

from sage.all import *
a = 469959113
b = 435140083
p = 957749491
E = EllipticCurve(GF(p), [a,b])

G = E(498070615, 681830144)
Q = E(328569657, 868726199)

d = discrete_log(Q, G, operation = "+")

assert Q == G * d
print(f"{d = }")

**Kết quả:** `d = 596641026`

---

### The Order Of The Generator Is A Smooth Number (Pohlig hellman)
Một trong những kiểu tấn công khá phổ biến đối với các bài CTF liên quan đến **ECC**. Đúng như tiêu đề thì khi này order của điểm sinh hay order của đường cong không phải một số nguyên tố, mà là một số smooth, aka số có rất nhiều thừa số nguyên tố nhỏ như $2,3,5,7,11\dots$

Đặt $n = \text{ord}(G)$, giả sử ta có có phân tích thừa số nguyên tố của $n$ là:
$$n = p_1^{e_1}.p_2^{e_2}.p_3^{e_3}\dots$$

Ý tưởng chính của kiểu tấn công này là chia order của đường cong ban đầu thành các nhóm con nhỏ hơn có order là $p_1^{e_1},p_2^{e_2},p_3^{e_3}\dots$ sau đó giải bài toán Logarit rời rạc trên các nhóm nhỏ đó, cuối cùng ta dùng **CRT** để kết hợp các nghiệm lại thành giá trị $d$ ban đầu.

:::info
:pencil: Chỉ khi bài toán dùng điểm sinh $G$ để thực hiện phép nhân thì ta mới xét order của $G$, còn nếu bài toán sử dụng một điểm $P$ nào khác điểm sinh thì ta phải xét order của điểm $P$ đó chứ không xét order của $G$.
:::

Tại sao thuật toán này chỉ có thể hoạt động tốt khi $n$ có nhiều ước nhỏ? Như đã nhắc ở phần trước đó thì độ phức tạp của thuật toán **DLP** là $O(\sqrt{n})$, nếu như $n$ là một số nguyên tố quá lớn thì bài toán sẽ trở nên bất khả thi để giải vì khi này độ phức tạp là quá lớn.

Nhưng khi $n$ được phân tích thành các ước nhỏ hơn là $p_1^{e_1},p_2^{e_2},p_3^{e_3}\dots$ thì độ phức tạp sẽ giảm xuống còn:
$$O(\sum {e_i . \sqrt{p_i}})$$

++**Ví dụ 1:**++ Ta sẽ phân tích thuật toán **Pohlig hellman** một cách chi tiết hơn qua ví dụ sau: Cho đường cong $E$ trên trường hữu hạn $GF(4289)$ như sau:

$$E: y^2 \equiv x^3 + 399.x + 2633 \pmod {4289}$$

Ta được cho một điểm sinh $G = (1998, 3062)$ và một điểm $Q = G .d = (524, 315)$ với $d$ là khóa bí mật, và mục tiêu của ta là tìm lại nó.

Đặt $n = \text{order}(G) = 4284$, ta có phân tích thừa số nguyên tố của $n$ là $n = 2^2.3^2.7^1.17^1$, giờ ta sẽ tìm cách chuyển bài toán DLP ban đầu thành các bài toán DLP trên các tập con nhỏ hơn, rồi sau đó sử dụng **CRT** là có được $d$ ban đầu.

Vì có tổng cộng $4$ nhóm con có order lần lượt là $4, 7, 9$ và $17$ nên ta cũng phải tìm được $4$ điểm $G'$ và $4$ điểm $Q'$ có order tương ứng. Ta có hệ phương trình như sau:
$$
\left\{\begin{matrix}
Q'_4 \equiv G'_4 .d \pmod 4 \\
Q'_7 \equiv G'_7 .d \pmod 7 \\
Q'_9 \equiv G'_9 .d \pmod 9 \\
\hspace{6mm} Q'_{17} \equiv G'_{17} .d \pmod {17}
\end{matrix}\right.\hspace{6mm} (*)
$$

Vì order của các nhóm con **rất nhỏ** nên ta hoàn toàn có thể giải bài toán **DLP** rất dễ dàng, được các kết quả như sau:
$$
\left\{\begin{matrix}
d \equiv d_1 \pmod 4 \\
d \equiv d_2 \pmod 7 \\
d \equiv d_3 \pmod 9 \\
\hspace{3mm}d \equiv d_4 \pmod {17}
\end{matrix}\right.
$$

> Sau đó ta dùng **CRT** là có thể tìm lại $d$ rồi.

:::info
:question: Nhưng mà tìm các điểm $Q'$ và $G'$ có order là $4,7,9,17$ như thế nào nhỉ?
:::

Rất đơn giản, để tạo ra một điểm $Z'$ có order là $i$ từ điểm $Z$ ban đầu ta chỉ cần tính theo công thức:
$$Z' = Z \times \frac{\text{order}(Z)}{i}$$

> Với điều kiện $i$ phải là một ước của $\text{order}(Z)$, nếu không ta không thể tìm được một điểm có order $i$ như vậy.

Ta tìm các điểm thỏa mãn và thay vào $(*)$, ta được một hệ phương trình như sau:
$$
\left\{\begin{matrix}
(2922, 3240) \equiv (2922, 1049)\times d \pmod 4 \\
(1002, 4173) \equiv (4271, 782)\times d \pmod 7 \\
(3059, 3788) \equiv (3059, 3788)\times d \pmod 9 \\
(4157, 2365) \equiv (3382, 1949)\times d \pmod {17}
\end{matrix}\right.
$$

Giải bài toán **DLP** để tìm $d$ với từng phương trình của hệ phương trình trên, ta có được hệ phương trình mới là:
$$
\left\{\begin{matrix}
d \equiv 3 \pmod 4 \\
d \equiv 4 \pmod 7 \\
d \equiv 1 \pmod 9 \\
\hspace{3mm} d \equiv 3 \pmod {17}
\end{matrix}\right.
$$

Sử dụng **CRT**, ta tính được `d = 1975`, bài toán kết thúc.

Thực hiện bằng **sagemath** như sau:
:::spoiler **Script**

from sage.all import *

a = 399
b = 2633
p = 4289
E = EllipticCurve(GF(p), [a, b])

G = E(1998, 3062)
Q = E(524, 315)

def pohlig_hemmlan(Q, G):
    d_remainders = []
    small_modulus = []

    n = G.order()
    factors = factor(n)
    
    for q, e in factors:
        # nhóm con của Q và G
        small_Q = Q * (n // (q**e))
        small_G = G * (n // (q**e))
        
        small_d = discrete_log(small_Q, small_G, operation = "+")
        
        d_remainders.append(small_d)
        small_modulus.append(q**e)

    return crt(d_remainders, small_modulus)

# Tìm d sao cho Q = G * d
d = pohlig_hemmlan(Q, G)
assert Q == G * d
print(f"{d = }")

# d = 1975

:::
++**Ví dụ 2:**++ Tìm lại $Flag$ từ các dữ kiện đã cho:
:::spoiler **Source**

from sage.all import *
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from hashlib import sha1

p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = ?
b = ?

flag = b"KCSC{????????????????????????????????}"

E = EllipticCurve(GF(p), [a, b])
G = E.gens()[0]

# secret key
d = int(random_prime(2**64))

# public key
Q = G * d

# AES encryption
key = sha1(str(d).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_ECB)
ciphertext = cipher.encrypt(pad(flag, 16)).hex()

print(f"G = {G.xy()}")
print(f"Q = {Q.xy()}")
print(f"{ciphertext = }")

# G = (89239274808899735280453750144885112288759661264541820395615102829857259053511, 34826102314608961434113145687288782952695936427644026769763458131126368245176)
# Q = (78498026291438679799525382446810568925459064185412655197272208683736166029031, 27397101429484393233035883342096342294595971890866377032008796822238612188973)
# ciphertext = '9249961d8a9b2d58ff7ae5e00b64403c18d82d00016f3f3a1ba24953a8eb31d9dbdde0e9c7b0cacd98f337a2b9e7c137'

:::
---

### Not Verifying That A Point Is On The Curve (Invalid curve attack)
Đây là một kiểu tấn công thường gặp, được sử dụng khi server không có các hàm **xác thực** rằng một điểm ta gửi vào có nằm trên đường cong của server hay không, từ đó ta có thể gửi một điểm thuộc một **đường cong khác** mà đường cong đó có thể dễ dàng giải bài toán **DLP** hơn, từ đó gián tiếp giải được bài toán **DLP** trên đường cong ban đầu.

Nhưng mà làm sao để biết được rằng liệu một điểm mới do ta gửi vào có được tính toán theo đường cong cũ hay không?

Điều này phụ thuộc vào thuật toán mà server dùng để thực hiện phép nhân điểm. Ta có thể chia ra làm hai trường hợp là server sử dụng thuật toán **Double and Add** hoặc là thuật toán **Montgomery ladder**. Ở phần này ta sẽ tìm hiểu về cách tấn công nếu như server sử dụng thuật toán Double and Add để thực hiện phép nhân điểm.

Thuật toán **Double and Add** sử dụng thuật toán cộng điểm như sau:

<img style="display: block; margin: auto;" width="500" src="https://hackmd.io/_uploads/HJWH7osRyx.png"/>

Có thể thấy rằng thuật toán không hề đụng đến giá trị $b$ để tính toán, thêm vào đó server không hề kiểm tra liệu điểm ta nhập vào có thuộc đường cong $E$ của server không? Nên ý tưởng tấn công của ta sẽ là tìm một điểm $b'$ sao cho đường cong mới là $E':y^2 \equiv x^3 + a.x + b' \pmod p$ có order là một **smooth number**, sau đó ta lựa một điểm $P$ thuộc $E'$ và gửi qua cho server tính $Q = P.d$, mà order của $E'$ là smooth number nên ta hoàn toàn có thể sử dụng thuật toán **Pohlig hellman** để giải $Q = P.d$ để có được $d$ ban đầu.

++**Ví dụ:**++ Khai thác lỗ hổng của server này và lấy lại được $Flag$:
:::spoiler **Source**

from os import urandom
from collections import namedtuple
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import inverse
from hashlib import sha256

FLAG = b"KCSC{invalid_curve_attack_on_ECC!!!}"

Point = namedtuple("Point", "x y")
Curve = namedtuple("Curve", "p a b G")

p = 6277101735386680763835789423207666416083908700390324961279
a = -3
b = 2455155546008943817740293915197451784769108058161191238065
G = Point(3289624317623424368845348028842487418520868978772050262753, 5673242899673324591834582889556471730778853907191064256384)
order = 6277101735386680763835789423176059013767194773182842284081
P_192 = Curve(p, a, b, G)

O = "Origin"
def point_inverse(P, C):
    if P == O:
        return P
    return Point(P.x, -P.y % C.p)

def point_addition(P, Q, C):
    if P == O:
        return Q
    elif Q == O:
        return P
    elif Q == point_inverse(P, C):
        return O
    else:
        if P == Q:
            lam = (3 * P.x**2 + C.a) * inverse(2 * P.y, C.p)
            lam %= C.p
        else:
            lam = (Q.y - P.y) * inverse((Q.x - P.x), C.p)
            lam %= p
    Rx = (lam**2 - P.x - Q.x) % C.p
    Ry = (lam * (P.x - Rx) - P.y) % C.p
    R = Point(Rx, Ry)
    return R

def double_and_add(P, n, C):
    Q = P
    R = O
    while n > 0:
        if n % 2 == 1:
            R = point_addition(R, Q, C)
        Q = point_addition(Q, Q, C)
        n = n // 2
    return R

# secret key
d = int.from_bytes(urandom(12), byteorder="little")
print(f"{d = }")

# AES encryption
key = sha256(str(d).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_ECB)
ciphertext = cipher.encrypt(pad(FLAG, 16)).hex()
print(f"{ciphertext = }")

print("Please send a tuple contains Px and Py")
while True:
    your_point = eval(input("> "))
    Px = int(your_point[0])
    Py = int(your_point[1])
    P = Point(Px, Py)
    
    Q = double_and_add(P, d, P_192)
    print((Q.x, Q.y))

:::
---

### The Curve Is Singular (singular curve attack)
Một trong những tính chất quan trọng để giữ được tính bảo mật của một đường Elliptic là nó **không được** là một **đường cong kỳ dị** (sigular curve), tức phải là một đường cong mà hai giá trị $a$ và $b$ thỏa mãn tính chất:
$$4a^3 + 27b^2 \equiv 0 \pmod p$$

Một đường cong mà không thỏa mãn tính chất trên sẽ tồn tại một **điểm kỳ dị** (singular point). Có hai loại điểm kỳ dị, là **node** và **cusp**:

Một đường cong mà tồn tại một điểm node thì đường cong đó sẽ có một **nghiệm kép**, nên có thể được viết lại nó theo công thức:
$$y^2 \equiv (x-x_0)^2.(x-x_1) \pmod p$$

Khi này ta tịnh tiến đường cong sang **trái** để cho điểm node nằm ngay gốc tọa độ bằng cách thay biến $x$ thành $(x+x_0)$ và ta được một dạng mới của đường cong là:
$$y^2 \equiv x^2.(x+x_0-x_1) \pmod p$$

Đặt $t = x_0 - x_1$, ta viết lại đường cong là $y^2 \equiv x^2.(x+t) \pmod p$. Khi này ta có thể xây dựng một ánh xạ từ các điểm $(x,y)$ trên đường cong sang các phần tử trong nhóm nhân $\mathbb{F}^*_p$, cụ thể là phép ánh xạ:
$$(x, y) \mapsto z = \frac{y+\sqrt{t} . x}{y-\sqrt{t} . x} \pmod p$$

> Ở đây $\sqrt{t}$ là căn bậc hai modulo $p$ của $t$, giả sử $t$ là quadratic residue.

Phép cộng các điểm trên đường cong, khi được chuyển qua ánh xạ này, sẽ tưởng ứng với phép nhân trong nhóm $\mathbb{F}^*_p$:
$$(x_1, y_1) + (x_2, y_2) \mapsto z_1 \cdot z_2$$

> Điều này biến bài toán **ECDLP** trở thành bài toán **DLP** thông thường trong nhóm $\mathbb{F}^*_p$ - vốn dễ hơn nhiều.

Hệ quả của phép ánh xạ trên đó là phép tính $Q = n.G$ sẽ trở thành phép tính:
$$z_Q \equiv z_G^n \pmod p$$

Và nếu $p-1$ là một **smooth number** hoặc $p$ không quá lớn thì việc giải bài toán **DLP** trên để tìm lại $n$ là vô cùng đơn giản, bằng cách sử dụng thuật toán **Pohlig hellman** hoặc **Baby-step Giant-step** mà thôi.

++**Ví dụ:**++ Ta có một đường cong $E$ được định nghĩa trên trường hữu hạn $\text{GF}(23981)$ như sau:
$$E: y^2 \equiv x^3 + 17230x+22699$$

>Cho $G = (1451, 1362)$ và $Q = G.d =(3141, 12767)$, mục tiêu của ta là tìm lại $d$.

Đây là một đường cong kỳ dị vì $4a^3+27b^2 \equiv 0 \pmod {23981}$, và điểm kỳ dị nằm tại tọa độ $(23796, 0)$, giờ ta sẽ tịnh tiến đường con sang trái sao cho điểm kỳ dị nằm tại gốc tọa độ, bằng phép ánh xạ:
$$(x,y) \mapsto (x-23796, y-0)$$

Ta được đường cong mới là:
$$y^2 \equiv x^3 + 23426x^2 \pmod {23981}$$

Có thể được viết lại thành:
$$y^2 \equiv x^2(x+23426) \pmod {23981}$$

Với $t = 23426$, ta có $\sqrt{23426} \equiv 7020 \pmod {23981}$. Giờ ta ánh xạ điểm $G$ và $Q$ trên đường cong sang nhóm nhân $\mathbb{F}^*_p$ bằng phép ánh xạ:
$$(x, y) \mapsto z = \frac{y+7020x}{y-7020x}$$

Được:
$$G \mapsto z_G = \left (\frac{y_G+7020.x_G}{y_G-7020.x_G}\right ) = u$$

$$Q \mapsto z_G^d = u^d = \left (\frac{y_Q+7020.x_Q}{y_Q-7020.x_Q}\right) = v$$

Khi này bài toán ban đầu của ta trở thành tìm $d$ sao cho:
$$u^d \equiv v \pmod p$$

Hay đó chính là bài toán **DLP** trong trường hữu hạn, ta hoàn toàn có thể giải được nếu như $p$ đủ nhỏ hoặc $p-1$ là smooth number, thực hiện trong **sagemath** như sau:
:::spoiler **Script**

from sage.all import *
p = 23981
a = 17230
b = 22699

F = GF(p)
x = PolynomialRing(F, "x").gen()
f = x**3 + a*x + b

G = (1451, 1362)
Q = (3141, 12767)

print(f.roots())
# [(370, 1), (23796, 2)] thấy rằng x = 23796 là nghiệm kép, nên nó sẽ là điểm kỳ dị

# giờ ta sẽ dịch đường cong sang bên trái bằng cách dùng .sub()
f_ = f.subs(x = x + 23796)

# Giờ điểm G và Q của ta sẽ có tọa độ mới là:
G_ = (G[0] - 23796, G[1])
Q_ = (Q[0] - 23796, Q[1])

# để xem được giá trị t, ta dùng factor như sau:
print(factor(f_))
# (x + 23426) * x^2 vậy giá trị t là 23426

t = 23426
# căn bậc hai của t
t_sqrt = F(t).square_root() #7020

# giờ ta ánh xạ G, Q thành u, v như sau:
u = ((G_[1] + t_sqrt*G_[0]) * pow(G_[1] - t_sqrt*G_[0], -1, p)) % p
v = ((Q_[1] + t_sqrt*Q_[0]) * pow(Q_[1] - t_sqrt*Q_[0], -1, p)) % p

u = Mod(u, p)
v = Mod(v, p)

d = discrete_log(v, u)
print(f"{d = }")
# 53

:::
:pencil: Thuật toán **Singular curve attack** như sau:
:::spoiler **Singular curve attack**

from sage.all import GF

# https://github.com/jvdsn/crypto-attacks/blob/master/attacks/ecc/singular_curve.py
def attack(p, a2, a4, a6, Gx, Gy, Px, Py):
    """
    Solves the discrete logarithm problem on a singular curve (y^2 = x^3 + a2 * x^2 + a4 * x + a6).
    :param p: the prime of the curve base ring
    :param a2: the a2 parameter of the curve
    :param a4: the a4 parameter of the curve
    :param a6: the a6 parameter of the curve
    :param Gx: the base point x value
    :param Gy: the base point y value
    :param Px: the point multiplication result x value
    :param Py: the point multiplication result y value
    :return: l such that l * G == P
    """
    x = GF(p)["x"].gen()
    f = x ** 3 + a2 * x ** 2 + a4 * x + a6
    roots = f.roots()

    # Singular point is a cusp.
    if len(roots) == 1:
        alpha = roots[0][0]
        u = (Gx - alpha) / Gy
        v = (Px - alpha) / Py
        return int(v / u)

    # Singular point is a node.
    if len(roots) == 2:
        if roots[0][1] == 2:
            alpha = roots[0][0]
            beta = roots[1][0]
        elif roots[1][1] == 2:
            alpha = roots[1][0]
            beta = roots[0][0]
        else:
            raise ValueError("Expected root with multiplicity 2.")

        t = (alpha - beta).sqrt()
        u = (Gy + t * (Gx - alpha)) / (Gy - t * (Gx - alpha))
        v = (Py + t * (Px - alpha)) / (Py - t * (Px - alpha))
        return int(v.log(u))

    raise ValueError(f"Unexpected number of roots {len(roots)}.")

:::
---

### The Curve Is Supersingular (MOV attack)
Cho một đường cong Elliptic có modulus là $p$ và order của đường cong là $n$, **Embedding Degree** của một đường cong là một số $k$ nhỏ nhất nào đó sao cho:
$$p^k \equiv 1 \pmod n$$

Thông thường, giá trị $k$ sẽ rất lớn, xấp xỉ kích thước của $p$, nhưng khi $k$ quá bé ($k \leq 6$), thì đường cong của ta trở thành đường cong **siêu kỳ dị** (supersingular) và với đường cong này, bài toán **DLP** sẽ được giải vô cùng nhanh chóng, và thuật toán tấn công loại đường cong như thế này được gọi là **MOV attack**, đặt theo tên của ba nhà toán học phát minh ra nó (Menezes-Okamoto-Vanstone).

Mình sẽ không đi sâu vào phân tích thuật toán của nó mà chỉ để thuật toán của nó ở đây cho mọi người tham khảo nhé.

:pencil: Thuật toán **MOV attack**:
:::spoiler **MOV attack**

from sage.all import GF, gcd

# https://github.com/jvdsn/crypto-attacks/blob/master/attacks/ecc/mov_attack.py
def attack(P, R, k, max_tries=10):
    """
    Solves the discrete logarithm problem using the MOV attack.
    More information: Harasawa R. et al., "Comparing the MOV and FR Reductions in Elliptic Curve Cryptography" (Section 2)
    :param P: the base point
    :param R: the point multiplication result
    :param k: the embedding degree
    :param max_tries: the maximum amount of times to try to find l (default: 10)
    :return: l such that l * P == R, or None if l was not found
    """
    E = P.curve()
    q = E.base_ring().order()
    n = P.order()
    assert gcd(n, q) == 1, "GCD of base point order and curve base ring order should be 1."

    Ek = E.base_extend(GF(q ** k))
    Pk = Ek(P)
    Rk = Ek(R)
    for i in range(max_tries):
        Q_ = Ek.random_point()
        m = Q_.order()
        d = gcd(m, n)
        Q = (m // d) * Q_
        if Q.order() != n:
            continue

        if (alpha := Pk.weil_pairing(Q, n)) == 1:
            continue

        beta = Rk.weil_pairing(Q, n)
        l = beta.log(alpha)
        return int(l)

    return None

:::
---

### The Curve Is Anomalous (Smart attack)
Sẽ ra sao nếu order của một đường cong $E$ bằng chính xác modulus $p$ luôn nhỉ?

> Nên nhớ rằng với các đường cong thông thường, chúng sẽ được chọn sao cho order của chúng không bao giờ bằng với modulus.

Nhưng nếu **order = modulus** thì khi này đường cong của ta được gọi là **đường cong bất quy tắc** (Anomalous curve) và nó hoàn toàn có thể bị tấn công bởi kiểu tấn công **Smart attack**.

:pencil: Thuật toán của **Smart attack** như sau:
:::spoiler **Smart attack**

from sage.all import *

def SmartAttack(P,Q,p):
    E = P.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])

    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break

    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp

    x_P,y_P = p_times_P.xy()
    x_Q,y_Q = p_times_Q.xy()

    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    return ZZ(k)

:::
---

## ECDSA Attacks
### Not Hashing The Message Before Signing It
Như đã tìm hiểu từ trước thì chữ ký của tin nhắn $m$ sẽ gồm hai giá trị $(r, s)$ thỏa mãn công thức:
$$r \equiv k \times G \pmod p$$

$$s \equiv k^{-1} \times (z + d_A \times r)\mod(p) $$

Trong đó $z$ chính là $L_n$ bit đầu của $\text{HASH}(m)$ với $L_n$ là bit length của order đường cong. Điều đó khiến cho giá trị $z$ rất khó bị giả.

Nhưng nếu ta không chịu băm tin nhắn $m$ trước khi ký? Thì khi này $z$ chính là $L_n$ bit đầu của $m$ luôn, tức nếu $m$ quá lớn, thì thuật toán sẽ không lấy các bit phía sau mà chỉ lấy $L_n$ bit đầu của $m$ mà thôi.

Đây là một lỗ hổng rất nghiêm trọng. Vì bây giờ **một** chữ ký có thể được dùng để xác thực **nhiều** tin nhắn khác nhau, chỉ vì giá trị $z$ hay $L_n$ bit đầu của chúng đều giống nhau hết.

++**Ví dụ**++: Sử dụng đường cong **P-192**, là đường cong có order là một số nguyên tố $192$ bit.

Ta có hai văn bản sau:

"please help me, send $1000 to Le Ha please, he is so broke right now."

Và

"please help me, send $1000 to Quanda now."

Vì không có bước băm, giá trị $z$ mà thuật toán sẽ lấy là $192$ bit đầu của hai văn bản trên, mà cả hai đều bắt đầu với $192$ bit giống nhau là `please help me, send $100`, nên khi này ta đã có được cùng một giá trị $z$ cho cả hai văn bản khác nhau, dẫn đến việc ta hoàn toàn có thể dùng chữ ký của văn bản này để xác thực cho văn bản khác.

---

### Reused Nonces
Một điều tối quan trọng khi thực hiện ký nhiều tin nhắn đó là không được sử dụng lại **nonce** của chữ ký trước, **nonce** chính là giá trị $k$ được tạo ra nhằm mục đích tính $r \equiv G \times k \pmod p$ và $s \equiv k^{-1} \times (z + d_A \times r) \pmod p$.

Vậy nếu ta vẫn chày cối sử dụng lại giá trị $k$ cho lần ký sau thì sao? Khi này ta sẽ có được một hệ phương trình như sau:
$$
\left\{\begin{matrix}
s_1 \equiv k^{-1}.(z_1 + d_A.r) \pmod p \hspace{5mm} (1) \\
s_2 \equiv k^{-1}.(z_2 + d_A.r) \pmod p \hspace{5mm} (2)
\end{matrix}\right.
$$

Lấy $(1)-(2)$ ta được:
$$s_1-s_2 \equiv k^{-1}.(z_1-z_2) \pmod p$$

Vậy là từ phương trình trên ta tính được $k$ rồi:
$$k \equiv \frac{z_1-z_2}{s_1-s_2} \pmod p$$

Có $k$ thì ta thay vào $(1)$ là tính được khóa bí mật $d_A$:
$$d_A \equiv \frac{s_1 . k - z_1}{r} \pmod p$$

Có được $d_A$ thì Hacker có thể giải mã được tin nhắn bí mật mà $A$ gửi cho người khác hoặc người khác gửi cho $A$ rồi. Như vậy chỉ từ một lỗi nhỏ mà đã dẫn đến hậu quả vô cùng nghiêm trọng.

---

### Biased Nonces
Đôi lúc người dùng có thể băm một số giá trị ngẫu nhiên để làm **nonce** vì nó nhanh, tuy nhiên phương pháp này có một vấn đề. Giả sử order của đường cong là một giá trị $n$ khoảng $256$ bit, nhưng lại lựa chọn hàm băm là $\text{SHA-1}$, điều đó khiến cho giá trị của $k$ chỉ đạt được tối đa là $160$ bit, trong phép tính **modulo** thì điều đó tương đương với việc $96$ bit đầu của $k$ là bit $0$, khiến cho $k$ trở nên quá nhỏ so với modulus $n$. Trong những tình huống như vậy, giá trị $k$ của ta sẽ được gọi là **biased nonce** (nonce bị lệch), và nếu như **nhiều tin nhắn** được ký bởi cùng **một** khóa bí mật $d$, ta hoàn toàn có thể sử dụng thuật toán $HNP$ để tìm lại $d$.

Giả sử $l$ bit đầu của các $k_i$ là $0$. Ta có điều kiện của $k_i$ là:
$$|k_i| < 2^{\log_2p-l}$$

Tiến hành biến đổi công thức của $s$ như sau:
$$s_i \equiv k_i^{-1} . (z_i + r_i.d) \pmod p$$

$$\Rightarrow s_i.k_i \equiv z_i + r_i.d \pmod p$$

$$\Rightarrow k_i - (s^{-1}_i.r_i).d + (-s_i^{-1}.z_i) \equiv 0 \pmod p$$

Đây chính là bài toán **HNP**, nếu có đủ $k_i$, ta hoàn toàn có thể tìm lại $d$ được.

Tham khảo thêm một số kiểu tấn công **biased nonce** ở [**đây**](https://eprint.iacr.org/2023/032.pdf).

---

# Challenge Cryptohack

## Parameter Choice
### Elliptic Nodes | (150 pts)
:::spoiler **Source**

from secrets import a, b
from collections import namedtuple
from Crypto.Util.number import inverse, bytes_to_long


FLAG = b"crypto{???????????????????????}"

# Create a simple Point class to represent the affine points.
Point = namedtuple("Point", "x y")

# The point at infinity (origin for the group law).
O = 'Origin'


def check_point(P):
    if P == O:
        return True
    else:
        return (P.y**2 - (P.x**3 + a*P.x + b)) % p == 0 and 0 <= P.x < p and 0 <= P.y < p


def point_inverse(P):
    if P == O:
        return P
    return Point(P.x, -P.y % p)


def point_addition(P, Q):
    if P == O:
        return Q
    elif Q == O:
        return P
    elif Q == point_inverse(P):
        return O
    else:
        if P == Q:
            lam = (3*P.x**2 + a)*inverse(2*P.y, p)
            lam %= p
        else:
            lam = (Q.y - P.y) * inverse((Q.x - P.x), p)
            lam %= p
    Rx = (lam**2 - P.x - Q.x) % p
    Ry = (lam*(P.x - Rx) - P.y) % p
    R = Point(Rx, Ry)
    assert check_point(R)
    return R


def double_and_add(P, n):
    Q = P
    R = O
    while n > 0:
        if n % 2 == 1:
            R = point_addition(R, Q)
        Q = point_addition(Q, Q)
        n = n // 2
    assert check_point(R)
    return R


def public_key():
    d = bytes_to_long(FLAG)
    return double_and_add(G, d)


# Define the curve
p = 4368590184733545720227961182704359358435747188309319510520316493183539079703

gx = 8742397231329873984594235438374590234800923467289367269837473862487362482
gy = 225987949353410341392975247044711665782695329311463646299187580326445253608
G = Point(gx, gy)
Q = public_key()

print(Q)
# Point(x=2582928974243465355371953056699793745022552378548418288211138499777818633265, y=2421683573446497972507172385881793260176370025964652384676141384239699096612)

:::
Challenge không cho ta giá trị $a$ và $b$ nhưng ta hoàn toàn có thể khôi phục được dựa vào hai điểm Challenge cho ta là $G$ và $Q$, thực hiện như sau:

def recover(p, x1, y1, x2, y2): #Truyền Q hay G trước đều được
    a = pow(x1 - x2, -1, p) * (pow(y1, 2, p) - pow(y2, 2, p) - (pow(x1, 3, p) - pow(x2, 3, p))) % p
    b = (pow(y1, 2, p) - pow(x1, 3, p) - a * x1) % p
    return int(a), int(b)

Có được giá trị của $a,b$ là:

a = 64186688762130075872648727143532923412208390610536286437268423112
b = 32579945572763798990069104934898692239152360555014084068553395172709029894

Dựa vào tên của Challenge là **Elliptic Nodes**, mình đoán rằng Challenge này sẽ có liên quan ít nhiều đến điểm kỳ dị, nên khi thử kiểm tra điều kiện:
$$4a^3 + 27b^2$$

Thì quả nhiên $4a^3 + 27b^2 \equiv 0 \pmod p$, nên mình sẽ sử dụng kiểu tấn công **singular curve attack** đã tìm hiểu ở trên để giải **DLP** là có được **Flag**.

:::spoiler **Script**

from sage.all import GF
from Crypto.Util.number import long_to_bytes

# https://github.com/jvdsn/crypto-attacks/blob/master/attacks/ecc/singular_curve.py
def attack(p, a2, a4, a6, Gx, Gy, Px, Py):
    """
    Solves the discrete logarithm problem on a singular curve (y^2 = x^3 + a2 * x^2 + a4 * x + a6).
    :param p: the prime of the curve base ring
    :param a2: the a2 parameter of the curve
    :param a4: the a4 parameter of the curve
    :param a6: the a6 parameter of the curve
    :param Gx: the base point x value
    :param Gy: the base point y value
    :param Px: the point multiplication result x value
    :param Py: the point multiplication result y value
    :return: l such that l * G == P
    """
    x = GF(p)["x"].gen()
    f = x ** 3 + a2 * x ** 2 + a4 * x + a6
    roots = f.roots()

    # Singular point is a cusp.
    if len(roots) == 1:
        alpha = roots[0][0]
        u = (Gx - alpha) / Gy
        v = (Px - alpha) / Py
        return int(v / u)

    # Singular point is a node.
    if len(roots) == 2:
        if roots[0][1] == 2:
            alpha = roots[0][0]
            beta = roots[1][0]
        elif roots[1][1] == 2:
            alpha = roots[1][0]
            beta = roots[0][0]
        else:
            raise ValueError("Expected root with multiplicity 2.")

        t = (alpha - beta).sqrt()
        u = (Gy + t * (Gx - alpha)) / (Gy - t * (Gx - alpha))
        v = (Py + t * (Px - alpha)) / (Py - t * (Px - alpha))
        return int(v.log(u))

    raise ValueError(f"Unexpected number of roots {len(roots)}.")

def recover(p, x1, y1, x2, y2): #Truyền Q hay G trước đều được
    a = pow(x1 - x2, -1, p) * (pow(y1, 2, p) - pow(y2, 2, p) - (pow(x1, 3, p) - pow(x2, 3, p))) % p
    b = (pow(y1, 2, p) - pow(x1, 3, p) - a * x1) % p
    return int(a), int(b)

p = 4368590184733545720227961182704359358435747188309319510520316493183539079703
Gx = 8742397231329873984594235438374590234800923467289367269837473862487362482
Gy = 225987949353410341392975247044711665782695329311463646299187580326445253608
Qx = 2582928974243465355371953056699793745022552378548418288211138499777818633265
Qy = 2421683573446497972507172385881793260176370025964652384676141384239699096612

a, b = recover(p, Gx, Gy, Qx, Qy)

print(long_to_bytes(attack(p, 0, a, b, Gx, Gy, Qx, Qy)))

:::spoiler Flag
**crypto{s1ngul4r_s1mplif1c4t1on}**
:::
### Moving Problems | (150 pts)
:::spoiler **Source**

from sage.all import EllipticCurve, GF
import random
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os

FLAG = b"crypto{??????????????????????????????????????}"

def gen_keypair(G, p):
    n = random.randint(1, (p-1))
    P = n*G
    return n, P

def gen_shared_secret(P, n):
    S = P*n
    return S.xy()[0]

def encrypt_flag(shared_secret: int):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Encrypt flag
    iv = os.urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(pad(FLAG, 16))
    # Prepare data to send
    data = {}
    data['iv'] = iv.hex()
    data['encrypted_flag'] = ciphertext.hex()
    return data

# Define Curve params
p = 1331169830894825846283645180581
a = -35
b = 98
E = EllipticCurve(GF(p), [a,b])
G = E.gens()[0]

# Generate keypair
n_a, P1 = gen_keypair(G, p)
n_b, P2 = gen_keypair(G, p)

# Calculate shared secret
S1 = gen_shared_secret(P1, n_b)
S2 = gen_shared_secret(P2, n_a)

# Check protocol works
assert S1 == S2

flag = encrypt_flag(S1)

print(f"Generator: {G}")
print(f"Alice Public key: {P1}")
print(f"Bob Public key: {P2}")
print(f"Encrypted flag: {flag}")

:::
Đọc tên Challenge xong mình cũng đoán bài này có liên quan đến **MOV attack** rồi nên hướng tiếp cận của mình sẽ liên quan đến MOV attack là chủ yếu.

Đầu tiên mình đi tính **Embedding degree** bằng đoạn code sau:

# p là modulus
# n là order của đường cong
for k in range(1, 7):
        if p ** k % n == 1:
            break

Mình tìm được **k = 2**, vì Embedding degree quá nhỏ nên ta hoàn toàn có thể sử dụng **MOV attack** để khôi phục lại $d$ được.

:::spoiler **Script**

from sage.all import GF, EllipticCurve, gcd
from hashlib import sha1
from Crypto.Cipher import AES

# https://github.com/jvdsn/crypto-attacks/blob/master/attacks/ecc/mov_attack.py
def attack(P, R, k, max_tries=10):
    """
    Solves the discrete logarithm problem using the MOV attack.
    More information: Harasawa R. et al., "Comparing the MOV and FR Reductions in Elliptic Curve Cryptography" (Section 2)
    :param P: the base point
    :param R: the point multiplication result
    :param k: the embedding degree
    :param max_tries: the maximum amount of times to try to find l (default: 10)
    :return: l such that l * P == R, or None if l was not found
    """
    E = P.curve()
    q = E.base_ring().order()
    n = P.order()
    assert gcd(n, q) == 1, "GCD of base point order and curve base ring order should be 1."

    Ek = E.base_extend(GF(q ** k))
    Pk = Ek(P)
    Rk = Ek(R)
    for i in range(max_tries):
        Q_ = Ek.random_point()
        m = Q_.order()
        d = gcd(m, n)
        Q = (m // d) * Q_
        if Q.order() != n:
            continue

        if (alpha := Pk.weil_pairing(Q, n)) == 1:
            continue

        beta = Rk.weil_pairing(Q, n)
        l = beta.log(alpha)
        return int(l)

    return None

p = 1331169830894825846283645180581
a = -35
b = 98
E = EllipticCurve(GF(p), [a,b])
G = E(479691812266187139164535778017, 568535594075310466177352868412)
R = E(1110072782478160369250829345256, 800079550745409318906383650948)
Q = E(1290982289093010194550717223760, 762857612860564354370535420319, 1)
na = int(attack(G, R, 2, max_tries=10))

data = {'iv': 'eac58c26203c04f68d63dc2c58d79aca', 'encrypted_flag': 'bb9ecbd3662d0671fd222ccb07e27b5500f304e3621a6f8e9c815bc8e4e6ee6ebc718ce9ca115cb4e41acb90dbcabb0d'}

shared_secret = int((Q * na)[0])

key = sha1(str(shared_secret).encode()).digest()[:16]
iv = bytes.fromhex(data["iv"])
ct = bytes.fromhex(data["encrypted_flag"])

cipher = AES.new(key=key, mode = AES.MODE_CBC, iv=iv)
print(cipher.decrypt(ct))

:::spoiler Flag
**crypto{MOV_attack_on_non_supersingular_curves}**
:::

## Parameter Choice 2
### A Twisted Mind | (80 pts)
:::spoiler **Source**

import os
from Crypto.Util.number import inverse

FLAG = "crypto{???????????????????????????????}"
LIMIT = 2
TIMEOUT = 120

# Parameters
p = 2**192 - 237
a = -3
b = 1379137549983732744405137513333094987949371790433997718123
order = 6277101735386680763835789423072729104060819681027498877478


def dbl(P1):
    X1, Z1 = P1

    XX = X1**2 % p
    ZZ = Z1**2 % p
    A = 2 * ((X1 + Z1) ** 2 - XX - ZZ) % p
    aZZ = a * ZZ % p
    X3 = ((XX - aZZ) ** 2 - 2 * b * A * ZZ) % p
    Z3 = (A * (XX + aZZ) + 4 * b * ZZ**2) % p

    return (X3, Z3)


def diffadd(P1, P2, x0):
    X1, Z1 = P1
    X2, Z2 = P2

    X1Z2 = X1 * Z2 % p
    X2Z1 = X2 * Z1 % p
    Z1Z2 = Z1 * Z2 % p
    T = (X1Z2 + X2Z1) * (X1 * X2 + a * Z1Z2) % p
    Z3 = (X1Z2 - X2Z1) ** 2 % p
    X3 = (2 * T + 4 * b * Z1Z2**2 - x0 * Z3) % p

    return (X3, Z3)


def swap(bit, P1, P2):
    if bit == 1:
        P1, P2 = P2, P1
    return P1, P2


def scalarmult(scalar, x0):
    R0 = (x0, 1)
    R1 = dbl(R0)
    n = scalar.bit_length()
    pbit = 0
    for i in range(n - 2, -1, -1):
        bit = (scalar >> i) & 1
        pbit = pbit ^ bit
        if pbit:
            R0, R1 = R1, R0
        R1 = diffadd(R0, R1, x0)
        R0 = dbl(R0)
        pbit = bit

    if bit:
        R0 = R1

    if R0[1] == 0:
        return "Infinity"
    return R0[0] * inverse(R0[1], p) % p


class Challenge:
    def __init__(self):
        self.before_input = f"Welcome!\nYou can submit up to {LIMIT} elliptic curve point (x coordinate only).\nYou have {TIMEOUT} seconds to submit the private key in decimal format.\n"
        self.timeout_secs = TIMEOUT
        self.privkey = privkey = int.from_bytes(os.urandom(24), "big")
        self.privkey = min(privkey % order, (order - privkey) % order)
        self.attempts_remaining = 2

    def challenge(self, your_input):
        if "option" not in your_input:
            return {"error": "You must send an option to this server"}

        elif your_input["option"] == "get_pubkey":
            if self.attempts_remaining == 0:
                return {
                    "error": "You cannot submit a point anymore. Now, please submit the private key."
                }

            x0 = int(your_input["x0"])
            pubkey = scalarmult(self.privkey, x0)
            self.attempts_remaining -= 1
            return {"pubkey": pubkey}

        elif your_input["option"] == "get_flag":
            guess = int(your_input["privkey"])
            if guess % order == self.privkey:
                return {
                    "message": "Congratulations, you found my private key!",
                    "flag": FLAG,
                }
            else:
                return {"error": "Sorry, this is not my private key."}
        else:
            return {"error": "You must send an option to this server"}

:::
Làm gì thì làm nhưng mà đầu tiên mình vẫn phải thử factor **order** của đường cong cái đã, kết quả thu được là **smooth number**, cũng gọi là khả quan:

from sage.all import *
p = 2**192 - 237
a = -3
b = 1379137549983732744405137513333094987949371790433997718123
order = 6277101735386680763835789423072729104060819681027498877478

E = EllipticCurve(GF(p), [a, b])
print(factor(E.order()))
# 2 * 11 * 269 * 2985973 * 1631363213 * 123462957881 * 1763644255088983457164385909

> Nhưng mà $d$ rất lớn, lên đến $192$ bit nên ta chưa thể dùng **Pohlig hellman** ngay được.

Phân tích source code, ta biết rằng nó không có các hàm xác thực liệu một điểm ta gửi vào có thuộc đường cong hay không, điều này làm ta nghĩ đến kiểu tấn công **invalid curve attack**.

Tuy nhiên Challenge này sử dụng thuật toán **Montgomery's Ladder** để thực hiện phép nhân điểm, thuật toán này sử dụng cả giá trị $b$ của đường cong, khiến cho ta không thể thực hiện tấn công **invalid curve attack** đã tìm hiểu ở trên được.

Có một điều bất thường là khi mình thử gửi $x_P = 1$ thì server vẫn thực hiện tính toán bình thường, trong khi $x_P = 1$ không phải là một điểm thuộc đường cong của server, vậy có lẽ tồn tại một đường cong ẩn nào đó mà server có thể thực hiện tính toán trên nó?

Nhưng giờ ta kiếm đường cong đó như thế nào nhỉ, sau một hồi tìm tòi thì mình tìm được bài viết này của tác giả [**7rocky**](https://7rocky.github.io/en/ctf/other/ecsc-2023/twist-and-shout/), với tựa đề là một Challenge liên quan đến **Twist** của đường cong. Cụ thể thì ý của tác giả là một điểm có thể không thuộc đường cong $E$ trong $\text{GF}(p)$ nhưng có thể nó sẽ là một điểm thuộc $E$ nhưng nằm trong trường mở rộng $\text{GF}(p^2)$, mình sẽ gọi đường cong này là $E^2$.

Thật vậy, khi mình thử kiểm tra tọa độ $x_P = 1$ thì nó chính xác là một điểm của $E^2$.

from sage.all import *
p = 2**192 - 237
a = -3
b = 1379137549983732744405137513333094987949371790433997718123
order = 6277101735386680763835789423072729104060819681027498877478

E2 = EllipticCurve(GF((p, 2), "k"), [a, b])
print(E2.lift_x(ZZ(1)))

# (1 : 3169895005719880528078946168431073542325434603825229014828*k + 1584947502859940264039473084215536771162717301912614507414 : 1)

>Vì vậy phép tính mà server thực hiện chính là thực hiện trên đường cong này!

Vậy giờ ý tưởng tấn công của ta là gì nhỉ? Khi mình thử factor **order** của điểm sinh $G$ thì được kết quả là một **smooth number**:

from sage.all import *
p = 2**192 - 237
a = -3
b = 1379137549983732744405137513333094987949371790433997718123
order = 6277101735386680763835789423072729104060819681027498877478

E2 = EllipticCurve(GF((p, 2), "k"), [a, b])
G = E2.gens()[0]

print(factor(G.order()))
# 2 * 3^3 * 11 * 269 * 1607 * 693493 * 2985973 * 1483406443 * 1631363213 * 40202856427 * 123462957881 * 1749002286417992230333906793 * 1763644255088983457164385909

Nhưng ta không thể dùng điểm sinh để gửi cho server của ta được vì khi này giá trị $x_G$ của $G$ không phải số thực :cry:

G = (1488207060563033167123485909136821934035875084673707875404*k + 1635212477100538699647234953009642300154940991388821500292 : 594045236145435111010182162753307928725438813479205595081*k + 1255740877487770448539915546941157134226821831891641892037 : 1)

Đọc bài viết của tác giả **7rocky**, ta biết rằng trong trường hữu hạn mở rộng $\text{GF}(p^2)$, tồn tại một đường cong gọi là **Twist**, nó là một loại đường cong đặc biệt, không đồng đẳng với $E$ trong $\text{GF}(p)$ nhưng sẽ đồng đẳng với $E$ trong $\text{GF}(p^2)$, mình sẽ đặt Twist của $E$ là $E_T$.

Ta có thể tìm được **twist bậc hai** của $E$ bằng phương thức `.quadratic_twist(d)` trong **sagemath** với $d$ là một giá trị không có căn bậc hai modulo $p$. Sau đó ta thử factor **order** của $E_T$ thì cũng được một **smooth number**.

from sage.all import *
p = 2**192 - 237
a = -3
b = 1379137549983732744405137513333094987949371790433997718123
order = 6277101735386680763835789423072729104060819681027498877478

E = EllipticCurve(GF(p), [a, b])
d = -1
assert Mod(-1, p).is_square() == false
Twist = E.quadratic_twist(-1)

print(factor(Twist.order()))
# 2 * 3^3 * 1607 * 693493 * 1483406443 * 40202856427 * 1749002286417992230333906793

Ta có hai dữ kiện quan trọng là order của $E$ và order của $E_T$ đều là **smooth number**, nên chắn chắn ta phải tìm cách để sử dụng **Pohlig hellman** rồi.

Ý tưởng tấn công của ta sẽ tìm hai điểm $P, Q$ trên $E^2$ sao cho $\text{Order}(P) = \text{Order}(E)$ và $\text{Order(Q)} = \text{Order}(E_T)$, vì order của chúng đều là smooth number nên ta hoàn toàn có thể tính được $d \mod n_i$ với $n_i$ là order của $E$ và $E_T$, sau đó dùng **CRT** để kết hợp hai nghiệm lại là có được $d$ hoàn chỉnh.

:::spoiler **Script**

from sage.all import *
from pwn import remote
import json

p = 2**192 - 237
a = -3
b = 1379137549983732744405137513333094987949371790433997718123
order = 6277101735386680763835789423072729104060819681027498877478

# tìm d sao cho Q = G * d (mod order(G))
def pohlig_hellman(Q, G):
    d_remainders = []
    small_modulus = []

    n = G.order()
    factors = factor(n)[:-1] # bỏ đi ước cuối nhé
    
    for q, e in factors:
        # nhóm con của Q và G
        small_Q = Q * (n // (q**e))
        small_G = G * (n // (q**e))
        
        small_d = discrete_log(small_Q, small_G, operation = "+")
        
        d_remainders.append(small_d)
        small_modulus.append(q**e)

    d = crt(d_remainders, small_modulus)
    big_modulus = prod(small_modulus)
    
    return d, big_modulus

# Đường cong E GF(p)
E = EllipticCurve(GF(p), [a, b])
# Twist của E

non_square = -1
assert Mod(non_square, p).is_square() == false
twist = E.quadratic_twist(non_square)
# Đường cong E trên GF(p^2)
E2 = EllipticCurve(GF((p, 2), "k"), [a, b])


# giờ ta tìm hai điểm P và Q có order bằng với order của E và twist
P = E2.lift_x(ZZ(randint(1, p)))
while P.order() != E.order():
    P = E2.lift_x(ZZ(randint(1, p)))

Q = E2.lift_x(ZZ(randint(1, p)))
while Q.order() != twist.order():
    Q = E2.lift_x(ZZ(randint(1, p)))

print(f"{P = }")
print(f"{Q = }")

io = remote("socket.cryptohack.org", 13416)
io.recvuntil(b'You have 120 seconds to submit the private key in decimal format.\n')

d_res = []
moduli = []
# Giờ ta gửi P và Q để thực hiện Pohlig hellman
for point in [P, Q]:
    payload = {"option": "get_pubkey", 'x0': int(point[0])}
    io.sendline(json.dumps(payload).encode())
    public_key = json.loads(io.recvline().decode())
        
    # Vì yA chỉ được lấy một trường hợp nên giá trị d có thể bị đổi dấu 
    A = E2.lift_x(ZZ(public_key["pubkey"]))
    
    # A = B * d
    d_remainders, modulus = pohlig_hellman(A, point)
    d_res.append(d_remainders)
    moduli.append(modulus)

# giờ ta sẽ CRT hệ sau là có d, nhưng phải chia 4 trường hợp ra nhé
# d = d_res[0] (mod moduli[0])
# d = d_res[1] (mod moduli[1])

# d = -d_res[0] (mod moduli[0])
# d = d_res[1] (mod moduli[1])

# d = d_res[0] (mod moduli[0])
# d = -d_res[1] (mod moduli[1])

# d = -d_res[0] (mod moduli[0])
# d = -d_res[1] (mod moduli[1])

# 4 trường hợp thì cũng ít, nhưng mà mình code cái này cho nó tổng quát lun, sau này dùng lại
from itertools import product
sign_remainders = []
for signs in product([1, -1], repeat=len(d_res)):
    signed = [sign * val for sign, val in zip(signs, d_res)]
    sign_remainders.append(signed)

private_key = []
for d_r in sign_remainders:
    private_key.append(crt(d_r, moduli))
    
for i in private_key:
    payload = {"option": "get_flag", "privkey": int(i)}
    io.sendline(json.dumps(payload).encode())
io.interactive()

:::spoiler Flag
**crypto{tw1st_s3curity_of_x_0nly_ladder}**
:::
### Checkpoint | (150 pts)
:::spoiler **Source**

from os import urandom
from collections import namedtuple
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import inverse
from hashlib import sha256

FLAG = b"crypto{????????????????????????????????????}"

# Create a simple Point class to represent the affine points.
Point = namedtuple("Point", "x y")
Curve = namedtuple("Curve", "p a b G")
# The point at infinity (origin for the group law).


# NIST P-256
p = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
a = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC
b = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
G = Point(
    0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296,
    0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5,
)
P_256 = Curve(p, a, b, G)

O = "Origin"
def point_inverse(P, C):
    if P == O:
        return P
    return Point(P.x, -P.y % C.p)


def point_addition(P, Q, C):
    if P == O:
        return Q
    elif Q == O:
        return P
    elif Q == point_inverse(P, C):
        return O
    else:
        if P == Q:
            lam = (3 * P.x**2 + C.a) * inverse(2 * P.y, C.p)
            lam %= C.p
        else:
            lam = (Q.y - P.y) * inverse((Q.x - P.x), C.p)
            lam %= p
    Rx = (lam**2 - P.x - Q.x) % C.p
    Ry = (lam * (P.x - Rx) - P.y) % C.p
    R = Point(Rx, Ry)
    return R


def double_and_add(P, n, C):
    Q = P
    R = O
    while n > 0:
        if n % 2 == 1:
            R = point_addition(R, Q, C)
        Q = point_addition(Q, Q, C)
        n = n // 2
    return R


class Server:
    def __init__(self, curve):
        self.C = curve
        self.s = int.from_bytes(urandom(32), byteorder="little")
        self.P = double_and_add(self.C.G, self.s, self.C)

    def ecdh_kex(self, Q, ciphersuite):
        if ciphersuite != "ECDHE_P256_WITH_AES_128":
            raise Exception("Ciphersuite not supported.")
        shared_point = double_and_add(Q, self.s, self.C)
        self.shared_key = sha256(str(shared_point.x).encode()).digest()[:16]

    def send_msg(self, pt):
        iv = urandom(16)
        cipher = AES.new(self.shared_key, AES.MODE_CBC, iv)
        return iv + cipher.encrypt(pad(pt, 16))


class Challenge:
    def __init__(self):
        self.S = Server(P_256)
        client_secret_key = int.from_bytes(urandom(32), byteorder="little")
        client_public_key = double_and_add(self.S.C.G, client_secret_key, self.S.C)
        self.S.ecdh_kex(client_public_key, "ECDHE_P256_WITH_AES_128")
        self.before_input = (
            f"Eavesdropping...\n"
            f"client initiating key agreement :\n"
            f"client->server : {client_public_key}\n"
            f"server->client : {self.S.P}\n"
            f"server->client : {self.S.send_msg(FLAG).hex()}\n"
        )

    def challenge(self, your_input):
        if your_input["option"] == "start_key_exchange":
            if "Qx" not in your_input or "Qy" not in your_input:
                return {"msg": "No public key provided."}
            if "ciphersuite" not in your_input:
                return {"msg": "No ciphersuite provided"}
            try:
                Q = Point(int(your_input["Qx"], 16), int(your_input["Qy"], 16))
                self.S.ecdh_kex(Q, your_input["ciphersuite"])
            except:
                return {"msg": "An error occured, please provide valid inputs."}
            return {"msg": "Key exchange proceeded successfully."}

        if your_input["option"] == "get_test_message":
            return {"msg": self.S.send_msg(b"SERVER_TEST_MESSAGE").hex()}

:::
Phân tích Source, ta thấy rằng lỗ hổng của nó chính là nó không có bước nào để kiểm tra một điểm ta nhập vào có thuộc đường cong hay không. Thêm vào đó, thuật toán nhân điểm mà Challenge sử dụng là thuật toán **Double and add**, không hề sử dụng giá trị $b$ của đường cong.

Vì thế ý tưởng của ta là tìm một giá trị $b$ sao cho order của đường cong mới là **smooth number**, sau đó sử dụng **Pohlig hellman** là có thể tính lại khóa bí mật.

Nhưng mà để tìm được một giá trị $b$ sao cho order của đường cong có nhiều ước nhỏ mà các ước nhỏ đó không được lớn hơn $45$ bit là rất lâu.

Thay vào đó ta sẽ kiếm khoảng $16-17$ giá trị $b$ sao cho đường cong mới có một điểm có **order** $16-17$ bit, ta sẽ gửi các điểm như vậy để server tính toán khóa công khai, mà order của các điểm này khá nhỏ nên ta có thể giải **DLP** khá nhanh, sau đó ta sử dụng **CRT** để kết hợp các giá trị $d \mod n_i$ lại là có được $d$ ban đầu.

Lý do mà ta chọn $16-17$ giá trị $b$ là vì nếu chọn quá nhiều giá trị $b$ thì ta sẽ có đến $2^k$ trường hợp dấu phải xét với $k$ là số giá trị $b$.

Tìm các giá trị $b$ bằng [**script**](https://github.com/elikaski/ECC_Attacks?tab=readme-ov-file#not-verifying-that-a-point-is-on-the-curve) này, mình có chỉnh sửa lại một xíu để phù hợp với challenge:
:::spoiler **Find b**

from sage.all import *
from Crypto.Util.number import long_to_bytes
from Crypto.Util.Padding import pad, unpad
from Crypto.Cipher import AES
import random
from hashlib import sha256

# Select a curve and generator
n = 2**256
p = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
a = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC

# This is the private key of the other side, we don't know it and don't use it!
private_key = random.randrange(n)

def encrypt_data(shared_point, message):
    if shared_point.is_zero():
        x, y = 0, 0
    else:
        x, y = shared_point.xy()
    key = sha256(str(x).encode()).digest()[:16]
    cipher = AES.new(key, AES.MODE_ECB)

    message = pad(message.encode(), 16)
    return cipher.encrypt(message)
def decrypt_data(shared_point, enc_message):
    if shared_point.is_zero():
        x, y = 0, 0
    else:
        x, y = shared_point.xy()
    key = sha256(str(x).encode()).digest()[:16]
    cipher = AES.new(key, AES.MODE_ECB)

    decrypted = cipher.decrypt(enc_message)
    return unpad(decrypted, 16)


def ECDH(A):
    # Send our public key to the other side
    # Have them reach the shared point and
    # Send us an encrypted message using the shared point as key

    # This part takes place remotely and is unknown to the attacker
    shared_point = private_key * A
    message = "Inconceivable!"
    return encrypt_data(shared_point, message)


def brute_force_encrypted_message(A, encrypted_message, max_order):
    # Returns n such that n*A matches the key used to encrypt the message
    for i in range(1, max_order):
        shared_point = i * A
        try:
            # If both padding is correct and all characters are ascii
            # Then it is probably the correct encryption key
            decrypted = decrypt_data(shared_point, encrypted_message)
            decrypted = decrypted.decode()
            return i
        except:
            continue
    raise Exception("Did not find a value for one of the encrypted messages")

order_list = []
Q_list = []
def find_curves_with_small_subgroup(p, a, max_order):
    # Yield tuples of (order, point) such that the point is
    # on a curve with the same a & p values, but different b
    # and the point's order is <= max_order
    orders_found = set()
    b = 0
    while True:
        b += 1
        if b == p:
            # Ran out of b values
            break
        if (4*a**3 + 27*b**2) % p == 0:
            # Curve is singular
            continue

        E = EllipticCurve(GF(p), [a, b])
        for _ in range(100):
            R = E.random_point()
            n = R.order()
            for f, e in n.factor(limit = 2**20):
                if f in orders_found:
                    continue
                if f > max_order:
                    break
                if f in range(2**10, 2**20):
                    # Create a point with order f
                    orders_found.add(f)
                    P = (n // f) * R
                    assert P.order() == f
                    print(f"{(b, P, f) = }")
                    Q_list.append((b, P, f))
                    yield (f, P)

max_order = 2**17
upto = 1
for order, A in find_curves_with_small_subgroup(p, a, max_order):
    upto *= order
    print("Found point with order", order, "so now can find keys of size up to", upto)

    # Send this point as our public key and get an encrypted message from other side
    encrypted_message = ECDH(A)

    # Find the value n such that: private_key = n (mod order)
    key_mod_order = brute_force_encrypted_message(A, encrypted_message, max_order)

    if upto >= n:
        break

print(Q_list)

:::
Ta tìm được $17$ giá trị $b$ thỏa mãn như sau:

# (b, point, order)
tup = [(1, (42175002054995005456032054847634109837867303662168681301823775328618621167257, 6288996052773274040412201979379734305561094315771238104660729610235490947637, 1), 30203), (6, (6916521694035682658992053075537445565363624352836952220952602038623371916311, 115744457910252132470609452006147133035446993203577266408387470384916086810576, 1), 102001), (8, (77177801688308590375281554339899397417008060715610710567469335543154535886705, 56482272201767764731237538221641643594417345014338560713897142910862902169184, 1), 81173), (9, (47034223721829461168018756183871790769531391997619306789768234976326643247188, 36690069098527171645302352091156608424561426366188813858864489931430425383110, 1), 72337), (9, (75867611241594963079296923992435306339863773743108034424194673499749692866234, 113386585066735986822606642693176073228481019212119301188621728278163800568548, 1), 119591), (11, (19586860274784579655299587649139369412746127963221097383745638856655651898653, 23506756512908370884843826409707591477075649717818438083240617620152533296415, 1), 19423), (12, (10284201017848954876928008678653247877572280857921112946804946132993725175179, 40420569947068244273309851366163691484564738277857776362688595870303603587354, 1), 52183), (21, (58893411339232717342928636766596153449829176933471364985984689019374288055282, 88967594578819727566524853729748425661839637170999623086359876721048301159595, 1), 33493), (44, (110493461217465614468627623232377433409210065126508400219960363592442096726843, 55122348430005210628102102776322553271812402494266245356568909691203567141037, 1), 40169), (45, (35938554177401964069979911595078887825898257087923837623686733269582908209128, 11524366179381991622832862533357684466096661348359806791553910444715556523854, 1), 48271), (56, (56761570687336245374057625531084333464888137771292682611740289890578963534878, 33450370200870181145296473112712061026862769454952910310746596602882805839690, 1), 67679), (66, (43810882600301584935214199838313271322146173207288006422267895018035800361127, 44405842419998416758345573858274384725705150184374927168935702777557358552841, 1), 49597), (73, (69815731950837116865486749513863186648302933375407100095031596454884845743692, 94459750075954258816372844475402716662904459615185301469096341198063906889743, 1), 126421), (76, (26235900583225356520135066868962606396134152478202309378665848781557925143560, 55657970105128320732848413162137654823706304262160141309209853597072001074910, 1), 85531), (91, (21180251250242349014208338047366392797219577182480583290292421353404602997473, 37851261500832061839129503770403284127655480750967230036644455606426287614036, 1), 21379), (92, (45376149881473028048370059872608836315356847508569955273199669704191342458484, 3875078093375110800492042110536859108223885838603671789480427323474807245366, 1), 111217), (93, (104404686430647022268382044928462370201938211524330387976602658007918887654500, 102264535239061459146382273757898757218836699584086892982149187675342121406119, 1), 39119)]

Có $b$, ta sẽ gửi đến server để nhận **Public key**, **ciphertext** và giải **DLP** để nhận các giá trị $d \mod n_i$ với $n_i$ là order của đường cong mới:
:::spoiler **Find d remainders**

from sage.all import *
from pwn import *
from json import *
from collections import namedtuple
from Crypto.Cipher import AES
from hashlib import sha256

io = remote("socket.cryptohack.org", 13419)
Point = namedtuple("Point", "x y")
Curve = namedtuple("Curve", "p a b G")

O = "Origin"
p = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
a = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC
b = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
G = Point(
    0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296,
    0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5,
)
P_256 = Curve(p, a, b, G)

io.recvuntil(b"agreement :\n")

Q_server = eval(io.recvline().split(b" : ")[1])
P_server = eval(io.recvline().split(b" : ")[1])
ciphertext_server = io.recvline(keepends=0).split(b" : ")[1].decode()
iv = bytes.fromhex(ciphertext_server[:32])
ct = bytes.fromhex(ciphertext_server[32:])

print(f"{Q_server = }")
print(f"{P_server = }")
print(f"{iv = }")
print(f"{ct = }")

# tìm các điểm cho order nhỏ
tup = [(1, (42175002054995005456032054847634109837867303662168681301823775328618621167257, 6288996052773274040412201979379734305561094315771238104660729610235490947637, 1), 30203), (6, (6916521694035682658992053075537445565363624352836952220952602038623371916311, 115744457910252132470609452006147133035446993203577266408387470384916086810576, 1), 102001), (8, (77177801688308590375281554339899397417008060715610710567469335543154535886705, 56482272201767764731237538221641643594417345014338560713897142910862902169184, 1), 81173), (9, (47034223721829461168018756183871790769531391997619306789768234976326643247188, 36690069098527171645302352091156608424561426366188813858864489931430425383110, 1), 72337), (9, (75867611241594963079296923992435306339863773743108034424194673499749692866234, 113386585066735986822606642693176073228481019212119301188621728278163800568548, 1), 119591), (11, (19586860274784579655299587649139369412746127963221097383745638856655651898653, 23506756512908370884843826409707591477075649717818438083240617620152533296415, 1), 19423), (12, (10284201017848954876928008678653247877572280857921112946804946132993725175179, 40420569947068244273309851366163691484564738277857776362688595870303603587354, 1), 52183), (21, (58893411339232717342928636766596153449829176933471364985984689019374288055282, 88967594578819727566524853729748425661839637170999623086359876721048301159595, 1), 33493), (44, (110493461217465614468627623232377433409210065126508400219960363592442096726843, 55122348430005210628102102776322553271812402494266245356568909691203567141037, 1), 40169), (45, (35938554177401964069979911595078887825898257087923837623686733269582908209128, 11524366179381991622832862533357684466096661348359806791553910444715556523854, 1), 48271), (56, (56761570687336245374057625531084333464888137771292682611740289890578963534878, 33450370200870181145296473112712061026862769454952910310746596602882805839690, 1), 67679), (66, (43810882600301584935214199838313271322146173207288006422267895018035800361127, 44405842419998416758345573858274384725705150184374927168935702777557358552841, 1), 49597), (73, (69815731950837116865486749513863186648302933375407100095031596454884845743692, 94459750075954258816372844475402716662904459615185301469096341198063906889743, 1), 126421), (76, (26235900583225356520135066868962606396134152478202309378665848781557925143560, 55657970105128320732848413162137654823706304262160141309209853597072001074910, 1), 85531), (91, (21180251250242349014208338047366392797219577182480583290292421353404602997473, 37851261500832061839129503770403284127655480750967230036644455606426287614036, 1), 21379), (92, (45376149881473028048370059872608836315356847508569955273199669704191342458484, 3875078093375110800492042110536859108223885838603671789480427323474807245366, 1), 111217), (93, (104404686430647022268382044928462370201938211524330387976602658007918887654500, 102264535239061459146382273757898757218836699584086892982149187675342121406119, 1), 39119)]
count = 0
remainders = []
moduli = []
index = 0

for b, Q, order_Q in tup:
    index += 1
    E = EllipticCurve(GF(p), [a, b])
    Q = E(Q)

    request = {"option" : "start_key_exchange", "ciphersuite" : "ECDHE_P256_WITH_AES_128", "Qx" : hex(Q.xy()[0])[2:], "Qy" : hex(Q.xy()[1])[2:]}
    request = dumps(request).encode()
    io.sendline(request)
    feedback = loads(io.recvline())["msg"]

    request = {"option" : "get_test_message"}
    request = dumps(request).encode()
    io.sendline(request)
    ciphertext2 = loads(io.recvline())["msg"]

    iv2 = bytes.fromhex(ciphertext2[:32])
    ct2 = bytes.fromhex(ciphertext2[32:])

    posible = [Q * _ for _ in range(1, order_Q)]
    posible = set(posible)

    for i in posible:
        key = sha256(str(i[0]).encode()).digest()[:16]
        cipher = AES.new(key = key, mode = AES.MODE_CBC, iv = iv2)
        plaintext = cipher.decrypt(ct2)
        if b"SERVER_TEST_MESSAGE" in plaintext:
            # print("found:", i)
            potential_d = discrete_log(i, Q, operation = "+")
            print(f"Index {index}/17: {potential_d} ≡ d (mod {order_Q})")
            remainders.append(potential_d)
            moduli.append(order_Q)
            break

print(remainders)
print(moduli)
assert len(remainders) == len(moduli)

:::
Bước cuối cùng là thử hết $2^{17}$ trường hợp dấu của `d remainders`, vì $d$ gốc chỉ dài $256$ bit nên ta sẽ thêm một điều kiện là `if d.bit_length() <= 256` để tăng tốc quá trình brute force:
:::spoiler **Solve**

from sympy.ntheory.modular import crt
from itertools import product
from tqdm import tqdm
from Crypto.Cipher import AES
from hashlib import sha256
from sage.all import EllipticCurve, GF

remainders = [11447, 85352, 14608, 51268, 104936, 5715, 14847, 10928, 4007, 1101, 29380, 12553, 5274, 56754, 18436, 49679, 29103]
moduli = [30203, 102001, 81173, 72337, 119591, 19423, 52183, 33493, 40169, 48271, 67679, 49597, 126421, 85531, 21379, 111217, 39119]

assert len(remainders) == len(moduli)

iv = b'\xf4\xb2\x1bh\xf5\xc0\x04a6J$\x04\x08y\x00\xe6'
ct = b'\x8f\xb0\xfa\xf6\xb3L\xdc^\x9b\xfe\x8b<7\xddv"\x00ntgo\xcc\x80\x085\xd9\x93:\x05\xa3\xd4\xdc5\x95\x07p=K\x1b\n\x99b\xf1\xe7\xad\xae\xbd\xbb'
sign_remainders = []

# Duyệt qua tất cả tổ hợp dấu (+1 hoặc -1) cho 17 phần tử
for signs in product([1, -1], repeat=len(remainders)):
    signed = [sign * val for sign, val in zip(signs, remainders)]
    sign_remainders.append(signed)

p = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
a = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC
b = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
E = EllipticCurve(GF(p), [a, b])
Q = E(111287252473095436293967859990912743481926606145513317880347077180777943059780, 
      2331401320082481443791372465872140161970364218775376657599801159788878442472)

for r in tqdm(sign_remainders):
    d = int(crt(moduli, r)[0])
    
    # bước quan trọng, lọc các giá trị nhỏ hơn 256 bit để tìm d
    if d.bit_length() <= 256:
        shared_secret = (Q * d)[0]
        key = sha256(str(shared_secret).encode()).digest()[:16]
        cipher = AES.new(key, AES.MODE_CBC, iv)
        flag = cipher.decrypt(ct)
        if b"crypto{" in flag:
            print(f"{d = }")
            print(flag)
            break

:::spoiler Flag
**crypto{nice_forward_secrecy_you_have_there!}**
:::

## Signatures
### Digestive | (60 pts)
:::spoiler **Source**

import hashlib
import json
import string
from ecdsa import SigningKey

SK = SigningKey.generate() # uses NIST192p
VK = SK.verifying_key


class HashFunc:
    def __init__(self, data):
        self.data = data

    def digest(self):
        # return hashlib.sha256(data).digest()
        return self.data



@chal.route('/digestive/sign/<username>/')
def sign(username):
    sanitized_username = "".join(a for a in username if a in string.ascii_lowercase)
    msg = json.dumps({"admin": False, "username": sanitized_username})
    signature = SK.sign(
        msg.encode(),
        hashfunc=HashFunc,
    )

    # remember to remove the backslashes from the double-encoded JSON
    return {"msg": msg, "signature": signature.hex()}


@chal.route('/digestive/verify/<msg>/<signature>/')
def verify(msg, signature):
    try:
        VK.verify(
            bytes.fromhex(signature),
            msg.encode(),
            hashfunc=HashFunc,
        )
    except:
        return {"error": "Signature verification failed"}

    verified_input = json.loads(msg)
    if "admin" in verified_input and verified_input["admin"] == True:
        return {"flag": FLAG}
    else:
        return {"error": f"{verified_input['username']} is not an admin"}

:::
Phân tích source, ta thấy rằng lỗ hổng nghiêm trọng nhất của nó là nó **không băm** tin nhắn trước khi ký, vì sử dụng **NIST192p** nên giá trị $z$ sẽ là $192$ bit đầu của **msg**, chính là đoạn `{"admin": false, "usernam`.

Vì $z$ chỉ lấy $192$ bit đầu nên ta không cần quan tâm lắm đến việc nhập `ussername` là gì vì nó không ảnh hưởng lắm, thứ ta cần quan tâm là làm sao để `admin` có giá trị `true`.

Cũng đơn giản thôi, ta sẽ gửi request là: `{"admin": false, "username": "a", "admin": true}`, khi này giá trị của `admin` sẽ được ghi đè thành `true` mà giá trị $z$ vẫn là đoạn `{"admin": false, "usernam`.

:::spoiler **Script**

from requests import get

username = "a"
sign = get("https://web.cryptohack.org/digestive/sign/" + username).json()
msg = sign["msg"]
signature = sign["signature"]

# đơn giản là sửa msg lại thành thế này, vì 192 bit đầu của msg chỉ tới {"admin": false, "usernam
msg = '{"admin": false, "username": "a", "admin": true}'

verify = get("https://web.cryptohack.org/digestive/verify/" + msg + "/" + signature).json()
print(verify)

:::spoiler Flag
**crypto{thanx_for_ctf_inspiration_https://mastodon.social/@filippo/109360453402691894}**
:::
### Curveball | (100 pts)
:::spoiler **Source**

import fastecdsa
from fastecdsa.point import Point
from fastecdsa.curve import P256

FLAG = "crypto{????????????????????????????????????}"
G = P256.G
assert G.x, G.y == [0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296,
                    0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5]


class Challenge():
    def __init__(self):
        self.before_input = "Welcome to my secure search engine backed by trusted certificate library!\n"
        self.trusted_certs = {
            'www.cryptohack.org': {
                "public_key": Point(0xE9E4EBA2737E19663E993CF62DFBA4AF71C703ACA0A01CB003845178A51B859D, 0x179DF068FC5C380641DB2661121E568BB24BF13DE8A8968EF3D98CCF84DAF4A9, curve=P256),
                "curve": "secp256r1",
                "generator": [G.x, G.y]
            },
            'www.bing.com': {
                "public_key": Point(0x3B827FF5E8EA151E6E51F8D0ABF08D90F571914A595891F9998A5BD49DFA3531, 0xAB61705C502CA0F7AA127DEC096B2BBDC9BD3B4281808B3740C320810888592A, curve=P256),
                "curve": "secp256r1",
                "generator": [G.x, G.y]
            },
            'www.gchq.gov.uk': {
                "public_key": Point(0xDEDFC883FEEA09DE903ECCB03C756B382B2302FFA296B03E23EEDF94B9F5AF94, 0x15CEBDD07F7584DBC7B3F4DEBBA0C13ECD2D2D8B750CBF97438AF7357CEA953D, curve=P256),
                "curve": "secp256r1",
                "generator": [G.x, G.y]
            }
        }

    def search_trusted(self, Q):
        for host, cert in self.trusted_certs.items():
            if Q == cert['public_key']:
                return True, host
        return False, None

    def sign_point(self, g, d):
        return g * d

    def connection_host(self, packet):
        d = packet['private_key']
        if abs(d) == 1:
            return "Private key is insecure, certificate rejected."
        packet_host = packet['host']
        curve = packet['curve']
        x, y = packet['generator']
        g = Point(x, y, curve=P256)
        Q = self.sign_point(g, d)
        cached, host = self.search_trusted(Q)
        if cached:
            return host
        else:
            self.trusted_certs[packet_host] = {
                "public_key": Q,
                "curve": "secp256r1",
                "generator": G
            }
            return "Site added to trusted connections"

    def bing_it(self, s):
        return f"Hey bing! Tell me about {s}"

    #
    # This challenge function is called on your input, which must be JSON
    # encoded
    #
    def challenge(self, your_input):
        host = self.connection_host(your_input)
        if host == "www.bing.com":
            return self.bing_it(FLAG)
        else:
            return self.bing_it(host)

:::
Yêu cầu của server để lấy được **Flag** rất đơn giản, gửi một điểm $G$ và một giá trị $d$ sao cho $G.d = Q$ là giá trị **Public key** của host `www.bing.com` là được.

Mình nghĩ ngay đến việc gửi giá trị $G = Q$ và lấy $d = 1$ là sẽ có được **Flag**, nhưng server có thêm một bước kiểm tra $d$ có bằng $1$ hay không nên hướng này không có tác dụng.

Vậy tấn công như thế nào nhỉ? Rất đơn giản, chỉ cần gửi $G = Q$ và $d = \text{order}(Q) + 1$ là được, bởi vì:
$$Q . (\text{order}(Q) + 1) = 0 + Q = Q$$

:::spoiler **Script**

from sage.all import *
from pwn import remote
from json import dumps

p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = -3
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b

E = EllipticCurve(GF(p), [a, b])
G = E((0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5))
Q = E(0x3B827FF5E8EA151E6E51F8D0ABF08D90F571914A595891F9998A5BD49DFA3531, 0xAB61705C502CA0F7AA127DEC096B2BBDC9BD3B4281808B3740C320810888592A)

order = int(Q.order())

io = remote("socket.cryptohack.org", 13382)
request = {"curve" : "nist256", "generator" : (int(Q[0]), int(Q[1])), "private_key" : order+1, "host" : "www.bing.com"}
request = dumps(request).encode()

io.sendlineafter(b"library!\n", request)
io.interactive()

:::spoiler Flag
**crypto{Curveballing_Microsoft_CVE-2020-0601}**
:::

### ProSign 3 | (100 pts)
:::spoiler **Source**

import hashlib
from Crypto.Util.number import bytes_to_long, long_to_bytes
from ecdsa.ecdsa import Public_key, Private_key, Signature, generator_192
from datetime import datetime
from random import randrange

FLAG = "crypto{?????????????????????????}"
g = generator_192
n = g.order()


class Challenge():
    def __init__(self):
        self.before_input = "Welcome to ProSign 3. You can sign_time or verify.\n"
        secret = randrange(1, n)
        self.pubkey = Public_key(g, g * secret)
        self.privkey = Private_key(self.pubkey, secret)

    def sha1(self, data):
        sha1_hash = hashlib.sha1()
        sha1_hash.update(data)
        return sha1_hash.digest()

    def sign_time(self):
        now = datetime.now()
        m, n = int(now.strftime("%m")), int(now.strftime("%S"))
        current = f"{m}:{n}"
        msg = f"Current time is {current}"
        hsh = self.sha1(msg.encode())
        sig = self.privkey.sign(bytes_to_long(hsh), randrange(1, n))
        return {"msg": msg, "r": hex(sig.r), "s": hex(sig.s)}

    def verify(self, msg, sig_r, sig_s):
        hsh = bytes_to_long(self.sha1(msg.encode()))
        sig_r = int(sig_r, 16)
        sig_s = int(sig_s, 16)
        sig = Signature(sig_r, sig_s)

        if self.pubkey.verifies(hsh, sig):
            return True
        else:
            return False

    #
    # This challenge function is called on your input, which must be JSON
    # encoded
    #
    def challenge(self, your_input):
        if 'option' not in your_input:
            return {"error": "You must send an option to this server"}

        elif your_input['option'] == 'sign_time':
            signature = self.sign_time()
            return signature

        elif your_input['option'] == 'verify':
            msg = your_input['msg']
            r = your_input['r']
            s = your_input['s']
            verified = self.verify(msg, r, s)
            if verified:
                if msg == "unlock":
                    self.exit = True
                    return {"flag": FLAG}
                return {"result": "Message verified"}
            else:
                return {"result": "Bad signature"}

        else:
            return {"error": "Decoding fail"}

:::
Nhìn vào Source, ta thấy ngay cách mà nó tạo ra **nonce** không hề bình thường, nó tạo nonce bằng cách `randrange(1, n)`, trong khi $n$ là số **giây** hiện tại, điều đó khiến xác suất để ta có được hai lần **nonce** trùng nhau là rất cao.

Khi ta có được **hai chữ ký** khác nhau nhưng sử dụng chung một nonce, ta hoàn toàn có thể tính lại được khóa bí mật $d$ và tạo được một chữ ký cho từ `unlock` và có được **Flag**.

:::spoiler **Script**

from Crypto.Util.number import bytes_to_long
from pwn import *
import json
from hashlib import sha1
from ecdsa.ecdsa import Public_key, Private_key, Signature, generator_192

io = remote("socket.cryptohack.org", 13381)
input = {"option" : "sign_time"}
input = json.dumps(input)

lst = {}

io.recvuntil(b"verify.\n")
while True:
    try:
        io.sendline(input.encode())
        sig = eval(io.recvline())
        
        print(sig)
        
        if sig["r"] not in lst:
            lst[sig["r"]] = sig
        else:
            tup1 = lst[sig["r"]]
            tup2 = sig
            break
    except:
        continue

g = generator_192
p = g.order()

z1 = bytes_to_long(sha1(str(tup1["msg"]).encode()).digest())
z2 = bytes_to_long(sha1(str(tup2["msg"]).encode()).digest())

r = int(tup1["r"], 16)
s1 = int(tup1["s"], 16)
s2 = int(tup2["s"], 16)

k = ((z1 - z2) * pow(s1 - s2, -1, p)) % p
d = ((s1 * k - z1) * pow(r, -1, p)) % p

msg = b"unlock"
hsh = sha1(msg).digest()

pubkey = Public_key(g, g * d)
privkey = Private_key(pubkey, d)

sig = privkey.sign(bytes_to_long(hsh), k)

packet = {"option" : "verify", "r" : hex(sig.r), "s" : hex(sig.s), "msg" : "unlock"}
packet = json.dumps(packet)

io.sendline(packet.encode())
io.interactive()

:::spoiler Flag
**crypto{ECDSA_700_345y_70_5cr3wup}**
:::
### No Random, No Bias | (120 pts)
:::spoiler **Source**

from hashlib import sha1
from Crypto.Util.number import bytes_to_long, long_to_bytes
from ecdsa import ellipticcurve
from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key
from random import randint

G = generator_256
q = G.order()

FLAG = b'crypto{??????????????????}'


def hide_flag(privkey):
    x = bytes_to_long(FLAG)
    p = curve_256.p()
    b = curve_256.b()
    ysqr = (x**3 - 3*x + b) % p
    y = pow(ysqr, (p+1)//4, p)
    Q = ellipticcurve.Point(curve_256, x, y)
    T = privkey.secret_multiplier*Q
    return (int(T.x()), int(T.y()))


def genKeyPair():
    d = randint(1,q-1)
    pubkey = Public_key(G, d*G)
    privkey = Private_key(pubkey, d)
    return pubkey, privkey


def ecdsa_sign(msg, privkey):
    hsh = sha1(msg.encode()).digest()
    nonce = sha1(long_to_bytes(privkey.secret_multiplier) + hsh).digest()
    sig = privkey.sign(bytes_to_long(hsh), bytes_to_long(nonce))
    return {"msg": msg, "r": hex(sig.r), "s": hex(sig.s)}



pubkey, privkey = genKeyPair()
hidden_flag = hide_flag(privkey)

sig1 = ecdsa_sign('I have hidden the secret flag as a point of an elliptic curve using my private key.', privkey)
sig2 = ecdsa_sign('The discrete logarithm problem is very hard to solve, so it will remain a secret forever.', privkey)
sig3 = ecdsa_sign('Good luck!', privkey)

print('Hidden flag:', hidden_flag)
print('\nPublic key:', (int(pubkey.point.x()), int(pubkey.point.y())), '\n')
print(sig1)
print(sig2)
print(sig3)

:::
Đọc tên Challenge thôi cũng đoán được Challenge này liên quan đến **biased nonce** rồi :smile:

Phân tích source, ta biết được rằng $k$ được tính bằng cách sử dụng hàm băm $\text{SHA-1}$ với $d + \text{hash(msg)}$, đúng như lý thuyết đã tìm hiểu ở trên thì khi này giá trị $k$ khá nhỏ so với modulus $p$ vì nó chỉ có giá trị tối đa là $160$ bit mà thôi, trong khi $p$ là số nguyên tố $256$ bit.

Vì khóa bí mật được dùng để ký tới $3$ văn bản khác nhau, nên ta hoàn toàn có thể nghĩ đến việc thiết lập một cơ sở Lattice và sử dụng **LLL** để giải bài toán **HNP**.

Ta biến đổi như sau:
$$
s_i \equiv k^{-1}.(z_i + r_i.d) \pmod p
$$

$$\Rightarrow s_i.k^{-1} \equiv z_i + r_i.d \pmod p $$

$$\Rightarrow k^{-1} - (s^{-1}.r_i).d + (-s^{-1}.z_i) \equiv 0 \pmod p$$

Đây chính là phương trình **HNP** dạng:
$$\beta_i - t_i\alpha + a_i + k_i.p = 0$$

Đặt $t_i = (s^{-1}.r_i)$, $a_i = (-s^{-1}.z_i)$ và $B = 2^{160}$. Ta thiết lập được một cơ sở Lattice $\mathbf{B}$ như sau:
$$
\mathbf{B} = \begin{bmatrix}
p & & & & \\
& p & & & \\
& & p & & \\
t_1 & t_2 & t_3 & B/p & \\
a_1 & a_2 & a_3 & & B \\
\end{bmatrix}
$$

Áp dụng **LLL** với cơ sở trên, ta sẽ được vector ngắn nhất dạng:
$$\mathbf{u} = (\beta_1, \beta_2, \beta_3,\alpha B/p,B)$$

Lấy $\mathbf{u}[3] . p/B$ là có được $d$, bài toán kết thúc.

:::spoiler **Script**

from sage.all import *
from ecdsa.ecdsa import curve_256, generator_256
from hashlib import sha1
from Crypto.Util.number import bytes_to_long, long_to_bytes

modulus = curve_256.p()
a_curve = curve_256.a()
b_curve = curve_256.b()

E = EllipticCurve(GF(modulus), [a_curve, b_curve])

# Lưu ý là phải dùng điểm sinh của nist256, dùng của sage là ăn c
G = E(generator_256.x(), generator_256.y())
p = G.order()

T = E(16807196250009982482930925323199249441776811719221084165690521045921016398804, 72892323560996016030675756815328265928288098939353836408589138718802282948311)
pub_key =  E(48780765048182146279105449292746800142985733726316629478905429239240156048277, 74172919609718191102228451394074168154654001177799772446328904575002795731796)

tup1 = {'msg': 'I have hidden the secret flag as a point of an elliptic curve using my private key.', 'r': '0x91f66ac7557233b41b3044ab9daf0ad891a8ffcaf99820c3cd8a44fc709ed3ae', 's': '0x1dd0a378454692eb4ad68c86732404af3e73c6bf23a8ecc5449500fcab05208d'}
tup2 = {'msg': 'The discrete logarithm problem is very hard to solve, so it will remain a secret forever.', 'r': '0xe8875e56b79956d446d24f06604b7705905edac466d5469f815547dea7a3171c', 's': '0x582ecf967e0e3acf5e3853dbe65a84ba59c3ec8a43951bcff08c64cb614023f8'}
tup3 = {'msg': 'Good luck!', 'r': '0x566ce1db407edae4f32a20defc381f7efb63f712493c3106cf8e85f464351ca6', 's': '0x9e4304a36d2c83ef94e19a60fb98f659fa874bfb999712ceb58382e2ccda26ba'}

z1 = bytes_to_long(sha1(tup1['msg'].encode()).digest())
z2 = bytes_to_long(sha1(tup2['msg'].encode()).digest())
z3 = bytes_to_long(sha1(tup3['msg'].encode()).digest())

r1 = int(tup1["r"], 16)
r2 = int(tup2["r"], 16)
r3 = int(tup3["r"], 16)

s1 = int(tup1["s"], 16)
s1_inv = pow(s1, -1, p)
s2 = int(tup2["s"], 16)
s2_inv = pow(s2, -1, p)
s3 = int(tup3["s"], 16)
s3_inv = pow(s3, -1, p)

# tính a, t để ghép vào cơ sở
t = [r1*s1_inv, r2*s2_inv, r3*s3_inv]
t = [i % p for i in t]
a = [z1*s1_inv, z2*s2_inv, z3*s3_inv] 
a = [i % p for i in a]

# Thiết lập cơ sở
B = 2**160
P = diagonal_matrix(3, [p]*3)
M = P.stack(Matrix(QQ, t))
M = M.stack(Matrix(QQ, a))
M = M.augment(vector(QQ, [0]*3 + [B/p] + [0]))
M = M.augment(vector(QQ, [0]*4 + [B])).dense_matrix()
M = M.LLL()

# tính d
for row in M:
    if int(row[-1]) == B:
        target_vector = vector(row)
        
    elif int(row[-1]) == -B:
        target_vector = -vector(row)

d = int(target_vector[3] * p/B) % p

assert G*d==pub_key
print('\033[93m'+ f"d = {d}" +'\033[0m')

# tính nghịch đảo của d, dùng inverse mod cho đỡ bug
d_inv = inverse_mod(d, p)

# có nghịch đảo rồi thì nhân với T là có Q
FLAG = long_to_bytes(int((T * d_inv)[0])).decode()

print('\033[91m' + f"Flag = {FLAG}" + '\033[0m')

:::spoiler Flag
**crypto{3mbrac3_r4nd0mn3ss}**
:::

## END
> [time=Wed, Apr 16, 2025 2:39 PM]