CSCV 2025: Crypto01

Tuần vừa rồi, CSCV 2025 đã diễn ra với hai bảng đấu là Jeopardy và Attack-Defense (A&D). Các challenge trong cả 2 bảng, đặc biệt là mảng cryptography (mình rất bất ngờ khi A&D có service crypto), khá là thú vị đối với mình do lượng code cần đọc rất lớn so với các challenge crypto mình thường thấy trong các giải CTF thông thường, nhưng vì vậy mà các challenge này lại khá gần với việc sử dụng crypto trong thực tế.

image alt

Sau đây là lời giải của mình cho service Crypto01 trong bảng A&D. Mọi người có thể tìm thấy script của mình ở đây.

TLDR

Service này có 3 bug chính:

Hàm rejection_sample được sử dụng trong mta.py không random, từ đó có thể đoán được giá trị của beta.
Hàm sha512_256_util không an toàn, từ đó ta xây dựng được proof hợp lệ đối với ProofFac cho các tham số Paillier không an toàn, các tham số này thuận lợi cho việc tính discrete log.
Việc kiểm tra thiếu điều kiện trong ProofMod cho phép ta xây dựng proof đối với Paillier modulus N không an toàn.

Cả 3 bug trên đều dẫn đến việc tính lại được secret key của server.

Chi tiết

Cấu trúc của service

src/
├── GETTING_STARTED.md
├── client.py
├── crypto
│   ├── __init__.py
│   ├── common
│   │   ├── ec.py
│   │   ├── numbers.py
│   │   ├── paillier.py
│   │   └── utils.py
│   └── zkp
│       ├── affg.py
│       ├── enc.py
│       ├── fac.py
│       ├── hash.py
│       ├── logstar.py
│       ├── mod.py
│       ├── mta.py
│       ├── prm.py
│       └── sch.py
├── ecdsa
│   ├── __init__.py
│   ├── aux.py
│   ├── errors.py
│   ├── keygen.py
│   ├── messages.py
│   ├── presigning.py
│   └── signing.py
├── flag.txt
├── main.py
├── party.py
├── patching-note.md
├── requirements.txt
└── simulate.py

Có rất nhiều file trong service này, nhưng mình sẽ tập trung vào một số file chính.

party.py dùng để kết hợp tất cả các bước mà 1 party cần làm khi thực hiện protocol, các bước được định nghĩa trong các file ở folder ecdsa.
simulate.py dùng để mô phỏng cách mà 2 party giao tiếp, từ đó ta biết được mình sẽ gửi gì ở các bước. Với việc codebase lớn, mình sẽ đọc cái này trước để hiểu được protocol hoạt động sao.
Từ main.py, service yêu cầu ta phải đoán được secret key của server để lấy được flag.
Với patching-note.md, ta chỉ có thể patch được các file nằm trong folder crypto/zkp, vì thế ta sẽ tập trung tìm bug ở các file trong folder này.

image alt

Các kĩ thuật

Trước khi đi vào tìm bug, ta sẽ tìm hiểu qua về các kĩ thuật được sử dụng trong service.

Multiplication-to-Addition

Với $a$, $b$ lần lượt là secret input của hai bên $A$ và $B$, Mục đích của giao thức Multiplication-to-Addition (MtA) là chia sẻ cho hai bên giá trị của $a * b$ mà không muốn bên còn lại biết trước, thông qua việc trao đổi các giá trị $\alpha$ và $\beta$ sao cho $$\alpha + \beta = a * b$$

Giao thức này cần sử dụng mã hoá đồng cấu cho việc tính toán, như trong service sử dụng hệ mã Paillier. Sau khi mỗi bên $A$ và $B$ đã tạo ra cặp khoá Paillier, để thực hiện MtA cần trải qua các bước sau:

Bước 1: Bên $A$ gửi $E(a)$ và khoá công khai của mình cho bên $B$, với $E(a)$ là giá trị mã hoá của secret input $a$ thông qua việc $A$ sử dụng khoá bí mật của mình.
Bước 2: Sau khi nhận được $E(a)$, bên $B$ sẽ sinh ngẫu nhiên giá trị $\beta$, tính $c = E(a)^b * E(-\beta)$ và gửi giá trị $c$ cho $A$.
- Nhờ việc sử dụng mã hoá đồng cấu, $c = E(a * b - \beta)$.
- Giá trị $\beta$ xuất hiện để đảm bảo kể cả khi bên $A$ tính $D(c)$ cũng không thể biết được kết quả $a * b$ do không biết giá trị $\beta$.
Bước 3: Bên $A$ sử dụng khóa bí mật của mình để tính $\alpha = D(c) = a * b - \beta$ và gửi giá trị này cho bên $B$.

Từ đó cả hai bên đều có thể tính được $a * b$ thông qua $\alpha$ và $\beta$.

Lưu ý rằng trong thực tế, giao thức này cần được đi kèm với một zk-proofs để đảm bảo các giá trị $\alpha$ và $\beta$ được tính toán chính xác mà vẫn đảm bảo bí mật.

Giao thức này được cài đặt trong zkp/mta.py, sử dụng zk-proofs được cài đặt trong zkp/affg.py.

Fiat-Shamir Heuristic

Mình đã từng nói về Fiat-Shamir Heuristic tại bài viết trước, nên ở đây mình sẽ không trình bày lí thuyết lại nữa. Tất cả các zk-proofs trong zkp đều sử dụng Fiat-Shamir, và hàm hash được sử dụng được định nghĩa trong zkp/hash.py

Giao thức chính

Service này mô phỏng hệ thống chữ kí ngưỡng cho 2 bên (2-to-2 Thresold Signature Scheme), dựa theo giao thức được đề cập trong CGGMP'21. Cấu trúc của giao thức khá là phức tạp, nhưng về cơ bản, để kí một message với giao thức này, ta cần trải qua 4 bước chính, bao gồm:

Key Generation: Mỗi bên sẽ tạo cặp khoá ECDSA, đồng thời tính khoá công khai chung sau khi nhận từ các bên còn lại.
Auxiliary Info: Ở bước này, mỗi bên sẽ tạo các giá trị dùng để tính toán đồng cấu ở bước sau, ở đây là cặp khoá Paillier , sau đó chia sẻ khoá công khai và nhận từ các bên còn lại.
Pre-Signing: Khoá công khai Paillier được nhận từ các bên khác sẽ dùng để tính toán các giá trị cần thiết cho bước sau thông qua giao thức MtA - là phần quan trọng nhất trong bước này.
Signing: Sau khi đã có các giá trị cần thiết, mỗi bên có thể xây dựng một phần chữ kí với message mà các bên đã thoả thuận trước, chữ kí cuối cùng tương ứng với message chính là kết hợp các chữ kí nhận được.

Để đảm bảo không có bên nào gian lận trong việc cung cấp các giá trị dùng trong tính toán cũng như tăng hiệu suất của việc xây dựng chữ kí, CGGMP'21 đã bổ sung hàng loạt zk-proofs trong mỗi bước, kết hợp với fiat-shamir heuristic để giảm khối lượng dữ liệu cần gửi. Các zk-proofs này đều được chú thích ở mục 5 và Appendix A trong paper, và đều được author cài đặt trong src/crypto/zkp

Tuy nhiên, khi các thuật toán zk-proof và fiat-shamir không được cài đặt cẩn thận, attacker có thể xây dựng các zk-proof giả, từ đó thao túng các giá trị được gửi lên và sử dụng để khai thác các thông tin quan trọng.

Exploit

Ở đây mình sẽ trình bày cách attack cũng như cách patch từng bug. Lưu ý rằng điều kiện để mỗi attack hoạt động không phụ thuộc vào các attack còn lại, nghĩa là sau khi patch 1 lỗ hổng thì attack khác vẫn có thể sử dụng. Mình cũng không chắc là đã tìm đủ bug trong bài, nên mình sẽ rất vui nếu mọi người tìm được bug ở chỗ nào khác nữa và inbox cho mình.

1. Sample beta ở MTA

Lỗ hổng đầu tiên nằm ở hàm new_mta trong mta.py, mà cụ thể hơn là cách mà giá trị beta được tạo:

ad/src/crypto/zkp/mta.py:
  75      # This value masks the product gamma_i * k_j.
  76:     beta_neg = gmpy2.mpz(rejection_sample(int(q5), ssid))
  77      beta = q5 - beta_neg

Ta sẽ xem qua cách hàm rejection_sample hoạt động:

def rejection_sample(modulus: int, h: int) -> int:
    """
    Generates a uniformly random integer in [0, modulus-1] from a seed 'h'.
    """
    r = 0
    i = 0
    while r < modulus:
        inb = str(h + i).encode()
        r = (r << 256) | int.from_bytes(hashlib.sha256(inb).digest(), "big")
        i += 1
    return r % modulus

Ta có thể thấy rằng hàm trên hoàn toàn phụ thuộc vào hai giá trị là modulus và h, vậy tức là khi có ssid (tương ứng với biến h), ta hoàn toàn tính lại được beta.

Khi đã biết được beta, việc còn lại là đơn giản. Với biểu thức $\alpha + \beta = k_0 * x_1 \mod q$, trong đó $k_0$ là giá trị mà ta tạo khi bắt đầu bước Presigning, và $\alpha$ nhận được khi giải mã giá trị _D từ server ở bước Presigning - round 3 với khoá bí mật Paillier của ta, ta hoàn toàn có thể tính được $x_1$, tức là khoá bí mật ECDSA của server.

Để tránh lỗi này, cần đảm bảo beta được tạo hoàn toàn random, một cách patch có thể nghĩ đến là thay đổi hàm rejection_sample bằng random.randint như sau:

ad/src/crypto/zkp/mta.py:
  75      # This value masks the product gamma_i * k_j.
  76:     beta_neg = gmpy2.mpz(random.randint(1,int(q5))
  77      beta = q5 - beta_neg

Script để attack trong trường hợp này là exp1.py.

2. Hash function

Lỗ hổng thứ hai bắt đầu từ hàm sha512_256_util trong hash.py

from typing import List
import hashlib

HASH_INPUT_DELIMITER = b"$"


def sha512_256_util(h, in_data: List[bytes]) -> bytes:
    """Helper function to hash a list of byte strings."""
    if not in_data:
        return None
    data = bytearray()
    for b in in_data:
        data.extend(b)
        data.extend(HASH_INPUT_DELIMITER)
    h.update(data)
    return h.digest()


def sha512_256(*in_data: bytes) -> bytes:
    """Computes the SHA-512/256 hash of one or more byte strings.

    Inputs are unambiguously joined with a delimiter before hashing to prevent
    collisions between different combinations of inputs (e.g., H(a,b) != H(ab)).
    """
    h = hashlib.new("sha512_256")
    return sha512_256_util(h, list(in_data))

Hàm sha512_256 dùng để tính giá trị băm SHA-512/256 từ một list các bytes data theo công thức $$h = H(\texttt{data[0]} || \texttt{DELIM} || \texttt{data[1]} || … || \texttt{data[n]})$$

Tuy nhiên, với việc chỉ dùng $ để phân tách các phần, ta có thể dễ dàng xây dựng collision với hàm băm này thông qua việc xây dựng các data với cấu trúc hợp lí, ví dụ như:

>>> in_data_0 = [b"giap", b"giap$giap"]
>>> in_data_1 = [b"giap$giap", b"giap"]
>>> sha512_256(*in_data_0).hex()
'90649e133df6dc70d1fb6ae0adee23b37e9299bffcbfa069ce48bcfad6dfff9c'
>>> sha512_256(*in_data_1).hex()
'90649e133df6dc70d1fb6ae0adee23b37e9299bffcbfa069ce48bcfad6dfff9c'

image alt

Ta sẽ lợi dụng lỗ hổng này để xây dựng ProofPrm hợp lệ từ bộ ba giá trị (s_, t_, N_), với t_ và N_ được chọn tùy ý. ProofPrm yêu cầu ta chứng minh được với input (s, t, N) thì s là một phần tử được sinh ra bởi t trong modulo N. Trong service này, ProofPrm được cài đặt ở prm.py, và được sử dụng trong bước Auxiliary Info - round 3.

Để xây dựng proof với t_ và N_ tùy ý, ta cần để ý cách ProofPrm sử dụng Fiat-Shamir để tạo proof và verify:

ad/src/crypto/zkp/prm.py:
  38          # 2. Compute Fiat-Shamir challenge. The hash interface expects standard ints.
  39:         e = sha512_256i(*([ssid, int(s), int(t), int(N)] + [int(val) for val in A]))
  40  

  86          # Recompute the Fiat-Shamir challenge.
  87:         e = sha512_256i(*([ssid, s, t, N] + self.A))
  88

Sẽ ra sao nếu tất cả các giá trị trong A đều bằng alpha? Khi đó, ta có thể lợi dụng lỗ hổng ở hàm hash, để xây dựng dãy A_ với hai kiểu phần tử là alpha và beta = int(a || $ || a), với a là giá trị của alpha khi chuyển sang byte và int là hàm để chuyển từ bytes sang số nguyên. Với việc thiết kế giá trị alpha và beta như trên và gán vào chỉ số tùy ý trong mảng A, giá trị của e không thay đổi, từ đó ta hoàn toàn có thể chọn giữa alpha và beta sao cho thỏa mãn điều kiện ở từng round.

Với ý tưởng trên, ta sẽ thực hiện các bước sau để tạo proof hợp lệ với input là $(t, N)$:

Với giá trị $\tau < |\mathbb{Z}_{ord(t)}|$, đặt $\alpha = t^\tau \mod N$ và cố định $Z_i = \tau$.
Tính $$\beta = int(\texttt{a} || \texttt{DELIM} || \texttt{a})$$ với $\texttt{a} = bytes(\alpha)$ và đặt $s = \frac{\alpha}{\beta} \mod N$.
Tìm kiếm giá trị $0 < l < 80$ sao cho với $l$ giá trị A là $\alpha$ và $n - l$ giá trị A là $\beta$, số lượng challenge bit $e_i = 0$ tính từ e đúng bằng $l$, ta có thể gán A[i] = alpha với $e_i = 0$ và A[i] = beta với $e_i = 1$.

Như vậy, ta đã xây dựng được ProofPrm với bộ $(s, t, N)$, trong đó $t$ và $N$ tùy ý. Để kiểm tra tính đúng đắn, ta có thể thử với từng trường hợp của challenge bit:

$e_i = 0: t^{Z_i} = t^{\tau_i} = \alpha * s^0 = \alpha \mod N$.
$e_i = 1: t^{Z_i} = t^{\tau_i} = \beta * s^1 = \beta * \frac{\alpha}{\beta} = \alpha \mod N$.

Khi đã xây dựng được ProofPrm với bộ số (s_, t_, N_), ta sẽ chú ý đến ProofAffg thứ hai của server ở bước Presigning - round 2, là kết quả khi thực hiện xong giao thức MtA:

    def round2(self, msg_j_r1: PresigningRound1Message) -> PresigningRound2Message:
        ...

        # MtA for sharing xi * k_j
        mtaX = new_mta(
            self.ssid,
            self.ec,
            self.K_j_ct,
            int(self.xi),
            self.Xi,
            self.paillier_pub_j,
            self.paillier_pub_i,
            int(self.paillier_pub_j.n),
            int(self.sj),
            int(self.tj),
        )
        self._beta_ij = gmpy2.mpz(mtaX.beta)

        ...

        return PresigningRound2Message(
            Gamma=self.Gamma_i,
            D=mtaG.Dji,
            _D=mtaX.Dji,
            F=mtaG.Fji,
            _F=mtaX.Fji,
            psi_affg_gamma=mtaG.Proofji.to_bytes_parts(),
            psi_affg_xi=mtaX.Proofji.to_bytes_parts(),
            psi_logstar_gamma=proof_logstar.to_bytes_parts(),
        )

Khi thực hiện MtA để chia sẻ giá trị x1 * k_0 (x1 là ECDSA private key của server, k_0 là giá trị bí mật của ta), ProofAffg có thực hiện phép toán mà sử dụng cả x1 và bộ số (s_, t_, N_) của ta để tính S:

class ProofAffg:
        ...

    @staticmethod
    def new_proof(
        ...
    ) -> "ProofAffg":
        """Generates a new zero-knowledge proof for the Aff-g relation."""
        ...

        E = (gmpy2.powmod(s, alpha, NCap) * gmpy2.powmod(t, gamma, NCap)) % NCap
        S = (gmpy2.powmod(s, x, NCap) * gmpy2.powmod(t, m, NCap)) % NCap #  <----
        F = (gmpy2.powmod(s, beta, NCap) * gmpy2.powmod(t, delta, NCap)) % NCap
        T = (gmpy2.powmod(s, y, NCap) * gmpy2.powmod(t, mu, NCap)) % NCap

        ...

Ta sẽ sử dụng giá trị S để khôi phục ECDSA private key của server. Ta có $$\begin{align}S = s^x * t^m \mod N \ (1)\end{align}$$

Ở bước tạo ProofPrm ở trên, ta đã chứng minh được có thể xây dựng được proof với bộ số (s_, t_, N_) tùy ý, và để có thể tìm được x ở trên, ta nên chọn cặp (t_, N_) thỏa mãn:

N_ = p_ * q_, trong đó p_ và q_ là 2 số nguyên tố sao cho p_ - 1 và q_ - 1 smooth. Cần đảm bảo số bit của p_ và q_ đủ lớn để có thể tạo ProofFac một cách hợp lệ (Nằm ở bước Auxiliary - round out).
t_ = 1 mod p_ sao cho s_ != 1 mod p

Với các điều kiện như trên, ta có thể biến đổi $(1)$ như sau: $$\begin{align} S &= s^x * t^m \mod N \newline S^{q - 1} &= s^{x * (q - 1)} * t^{m * (q - 1)} \mod N \newline S_p &= s_p^x \mod p \end{align}$$

và giải discrete log để tìm $x$. Dựa theo việc chọn p_ và q_ ở trên, việc giải discrete log vô cùng dễ dàng với sagemath.

Một điều cần lưu ý khi tạo ProofPrm là cần đảm bảo beta trong khoảng từ 1 đến N. Thông qua việc chọn N_ là tích của hai smooth prime, ta hoàn toàn có thể tính được $\tau$ sao cho $\texttt{len(bytes(alpha))} < 1024$, từ đó xây dựng được beta thỏa mãn.

Cuối cùng, để patch lỗ hổng này, ta có thể chỉnh sửa hàm sha512_256_util như sau

ad/src/crypto/zkp/hash.py:
   7  def sha512_256_util(h, in_data: List[bytes]) -> bytes:
   8      """Helper function to hash a list of byte strings."""
   9      if not in_data:
  10          return None
  11      data = bytearray()
  12:     for b in in_data:
  13          data.extend(b)
  14          data.extend(HASH_INPUT_DELIMITER)
  15          data.extend(len(b).to_bytes(4, "big"))
  16      h.update(data)
  17      return h.digest()

image alt

Mình hoàn toàn tin rằng lỗ hổng này lấy cảm hứng từ $\alpha$-shuffle attack của TSSHOCK, một attack khá nổi tiếng trong TSS. Các attack còn lại trong paper cũng khá thú vị, và mình nghĩ mọi người nên thử.

Script để attack trong trường hợp này là exp2.py.

3. Thiếu điều kiện ở `ProofMod`

Để khôi phục được ECDSA private key của server trong attack này cần khá nhiều bước, vì thế ta sẽ chia nhỏ các việc cần làm.

ProofMod

Lỗ hổng xuất phát từ việc ProofMod không kiểm tra đủ các điều kiện cần đối với input, dẫn đến việc ta có thể xây dựng proof mới với N tùy ý.

Để giải thích kĩ hơn, ta hãy xem qua cách ProofMod hoạt động. ProofMod được cài đặt ở mod.py.

Về bản chất, ProofMod giúp ta chứng minh được prover biết $N = p * q$ mà không tiết lộ $p, q$, và theo như đoạn code trên, để biết ProofMod cho input $N$ có hợp lệ hay không, các mệnh đề sau sẽ được kiểm tra:

$N$ lẻ
$Z_i^N = Y_i \mod N$
$X_i^4 = (-1)^{a_i} * W^{b_i} * Y_i \mod N$

với $i = 1..\texttt{Iterations}$, $a_i, b_i$ là challenge được tạo từ Fiat-Shamir.

Khi đọc lại paper CGGMP'21, mình chú ý rằng $\prod^{mod}$ có yêu cầu rằng $gcd(w, N) = 1$, tuy nhiên trong code lại không có đoạn kiểm tra này. Câu hỏi đặt ra là liệu điều này có ảnh hưởng gì đến protocol không ?

Giả sử $gcd(W, N) = q$, trong ProofMod.new_proof ta thấy với mỗi giá trị $Y_i$, $X_i = \sqrt[4]y_i \mod N$ với $y_i = (-1)^{a_i} * W^{b_i} * Y_i$. Việc tính căn bậc 4 của 1 số trong modulo $N$ khi không biết $p$ và $q$ là rất khó. Nhưng khi $gcd(W, N) = q$, việc tính $X_i$ chỉ cần thực hiện trên modulo $p$, việc này hoàn toàn khả thi nếu như $p$ là số nguyên tố có dạng $4k + 3$.

Với ý tưởng trên, ta có thể xây dựng ProofMod cho $N = q * p_0 * … * p_i$, thông qua việc đặt $W = p_0 * … * p_i$ và $q$ là số nguyên tố có dạng $4k + 3$ và $p_i$ là các số nguyên tố 16 bit. Ta sẽ thấy ý nghĩa của việc đặt $N$ như vậy ở các bước sau.

Bước này được thực hiện ở hàm fake_mod_proof trong script của mình. Ta sẽ thực hiện việc tạo ProofMod giả ở bước Auxiliary - round 1.

`ProofEnc` và `ProofLogstar`

ProofEnc và ProofLogstar lần lượt được sử dụng ở Presigning - round 2 và round 3.

ProofEnc đảm bảo rằng ta biết được message $k$ và giá trị ngẫu nhiên $\rho$ đối với bản mã Paillier $K = Enc(k, \rho)$. Khi ta chọn Paillier modulus là $N_0$ với cấu trúc như trên, ta có thể xây dựng ProofEnc với $k = 0$ và $K = Enc(\frac{N_0}{p_i}, \rho)$ qua các bước sau:

Đặt $\alpha = 1$, thực hiện tính các giá trị $S, A, C$ như bình thường.
Tính challenge $e$ thông qua Fiat-Shamir, nếu như $e % p_i = 0$ thì tiếp tục tính $z_1, z_2, z_3$ như bình thường và kết thúc, còn không thì tăng giá trị $\alpha$ và tính lại các giá trị $A$ và $C$. Do $p_i$ nhỏ nên tỉ lệ tìm được $e$ là khá lớn, vì thế bước này sẽ có tỉ lệ thành công cao.

Ta sẽ chứng minh các giá trị được tạo trên là proof hợp lệ thông qua việc kiểm tra các điều kiện:

$$\begin{aligned}(1 + N_0)^{z_1} * z_2^{N_0} &= (1 + N_0)^{z_1} * (r * \rho^e)^{N_0} &\mod N_0^2 \newline &= (1 + N_0)^{\alpha} * (r * \rho^e)^{N_0} &\mod N_0^2 \newline &= ((1 + N_0)^\alpha r^{N_0}) * (\rho^{e N_0}) &\mod N_0^2 \newline &= ((1 + N_0)^\alpha r^{N_0}) * ((1 + N_0)^{\frac{N_0}{p_i} e} * p^{e N_0}) &\mod N_0^2 \newline &= A * K^e &\mod N_0^2 \newline \newline s^{z_1} * t^{z_3} &= s^{\alpha} * t^{\gamma + e * \mu} &\mod N_1 \newline &= (s^\alpha t^\gamma) * t^{e * \mu} &\mod N_1 \newline &= C * S^e &\mod N_1 \end{aligned}$$

Vậy ta đã thành công xây dựng được ProofEnc.

Đối với hàm ProofLogstar, về bản chất nó khá giống với việc kết hợp ProofEnc và ProofSch, do đó ta có thể áp dụng logic tương tự như trên để xây dựng ProofLogstar hợp lệ.

Bước này được cài đặt ở hàm fake_enc_proof và fake_logstar_proof.

MtA

Trở lại với giao thức MtA, tương tự với attack 1, ta vẫn sẽ tập trung vào giá trị _D của server gửi về ở bước Presigning - round 3, nhưng sẽ sử dụng theo một cách khác. Ở bước trên, ta đã gửi $K = Enc(\frac{N_0}{p_i}, \rho)$, từ đó sau khi decrypt giá trị _D, ta sẽ có $$\alpha = \frac{N_0}{p_i} * x_1 - \beta \mod N_0$$

Với biểu thức trên, ta hoàn toàn có thể khôi phục lại một phần thông tin của $x_1$, cụ thể như sau: $$\begin{aligned} \alpha &= \frac{N_0}{p_i} * x_1 - \beta \mod N_0 \newline -\alpha_i &= \beta \mod \frac{N_0}{p_i} = \beta \ (\beta \approx q^5 < \frac{N_0}{p_i}) \newline \frac{N_0}{p_i} * x_1 &= \alpha - \alpha_i \mod N_0 \newline x_1 &= \frac{\alpha - \alpha_i}{\frac{N_0}{p_i}} \mod p_i \end{aligned}$$

Từ đó, lặp lại các bước ở trên với $p_i$ khác nhau, ta có thể sử dụng CRT để khôi phục hoàn toàn $x_1$ và gửi lên server.

image alt

Trái ngược với việc attack, việc vá lỗ hổng này khá đơn giản, ta chỉ cần bổ sung thêm điều kiện làm cho bước xây dựng ProofMod của ta thất bại:

ad/src/crypto/zkp/mod.py:
  162  
  163          if is_quadratic_residue(W, N) == 1:
  164              return False
  165:         if int(gmpy2.gcd(W, N)) != 1:
  166              return False
  167          if not (0 < W < N and all(0 < z < N for z in Z) and all(0 < x < N for x in X)):
  168              return False

Lỗ hổng này đã từng xuất hiện trong thực tế, gây ảnh hưởng rất lớn đối với các bên sử dụng TSS. Trong paper đính kèm, các tác giả còn chỉ ra thêm nhiều kiểu attack tương ứng với mỗi protocol khác nhau, và các attack cũng khá là thú vị, mọi người có thể xem qua và cài đặt lại thử.

Việc tấn công khá là phức tạp và cần nhiều bước, vì vậy mình nghĩ đây là bug khó nhất trong bài để attack. Script để attack trong trường hợp này là exp3.py

Cảm nghĩ cá nhân

8 tiếng cho service này là quá ít, kể cả với người đã từng đọc qua TSS và các bug liên quan.
Việc vá các lỗ hổng khá đơn giản, trái ngược hoàn toàn với việc attack.
Lỗ hổng đầu tiên khá là dễ để tìm thấy và tấn công, nhưng hai lỗ hổng sau thì cần tốn khá nhiều thời gian để có hướng đi và cài đặt.
Nhiều code quá…

CSCV 2025: Crypto01

TLDR

Chi tiết

Cấu trúc của service

Các kĩ thuật

Multiplication-to-Addition

Fiat-Shamir Heuristic

Giao thức chính

Exploit

1. Sample beta ở MTA

2. Hash function

3. Thiếu điều kiện ở ProofMod

ProofMod

ProofEnc và ProofLogstar

MtA

Cảm nghĩ cá nhân

3. Thiếu điều kiện ở `ProofMod`

`ProofEnc` và `ProofLogstar`