00

How theory guides the attack’s direction?

  1. Parameters that an attacker can manipulate.
  2. The least effort way to manipulate parameters.
  • [Wz]₁, [Wzω]₁are under the attacker’s control. To be clear, the attacker can manipulate [Wz]₁, [Wzω]₁but the attacker does not know the inside true values Wz, Wzω.
  • u = hash(transcript) where hash acts as a random oracle, so it’s technically outside the attacker’s control.
  • x is part of a trusted setup that no one (including the prover and verifier) is assumed to know.
  • F and E are computed by the verifier (not attacker) in a complicated multi-steps process, so let’s ignore them.

Why does the attack work in practice?

The root cause

  1. The verifier checks whether [Wz]₁, [Wzω]₁ are on the elliptic curve or not. [Wz]₁ = 0, [Wzω]₁ = 0 are not valid points on the curve. However, the verifier does not stop immediately when it sees invalid points. It continues the execution, but it excludes the invalid 0 points in some further computations. The amazing thing is that while [Wz]₁ = 0, [Wzω]₁, P[1] = 0 are excluded in some further computations, they’re included in the crucial computation with pairing which allows the attack to work. If the program returns false immediately once it sees invalid points, the attack would fail.
  2. In the elliptic curve code, there is another check to reject the infinity point. However, according to the code, P[1] = 0 is not infinity. The is_point_at_infinity method checks whether the most significant bit of the P[1] is 1, but P[1] = 0’s most significant bit is 0. Hence P[1] = 0 bypasses the infinity point check.
  3. In the computation process, there is a method that computes the inverse of 0 mod p. The method doesn’t check for 0 input. It uses Fermat’s little theorem, i.e., it uses the equation x^(p — 1) = 1 mod p or x^(p — 2). x = 1 mod p or x^(p — 2) is the inverse of x mod p. However, when x = 0, x^(p — 2) = 0 which means that the inverse of 0 is 0. This isn’t even correct mathematically because the inverse of 0 mod p shouldn’t exist. If the inverse method rejects 0, the attack would again fail.
  4. Now, the array (P[0], P[1]) = (P[0] ≠ 0, P[1] = 0) are in projective coordinates (x, y, z). The projective coordinate is often just an intermediate representation for optimization purposes. After finishing the computation, the projective coordinates go through a process called normalization to eliminate z (i.e. to make z = 1) and goes back to affine coordinate (x, y) ~ (x, y, 1). The code does not normalize points individually, instead it batch-normalizes an array of points together where P[1].z = 0 will affect P[0]. The vulnerable code outputs (P[0], P[1]) = (0, 0), i.e., it turns non-zero point P[0] into a 0 point. For instance, here is the output from the program

Acknowledgements

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Quan Thoi Minh Nguyen

Quan Thoi Minh Nguyen

Senior security engineer. Formerly @Snap, @Google. Black Hat Speaker USA 2021, ASIA 2022. Personal account. https://github.com/cryptosubtlety