[Bug] Efficient Handling of the Infinity Point in Jacobian Curve Addition

[stonejiajia]

🐛 Bug Report

Efficient Handling of the infinity point in jacobian curve addition and doubling

Summary:

Referring to CVE-2017-7781 that a https://blog.intothesymmetry.com/2017/08/cve-2017-7781cve-2017-10176-issue-with.html post discussing vulnerabilities in Jacobian addition misuse. They used a madd-2004-hmv implementation to calcuate jacobian addition, missing the situtation U1 == U2

Similarly, in SnarkVM, SnarkVM use the add-2007-bl method for this calculation. An issue arises when calculating two points (X1, Y1, Z1) and (X2, Y2, Z2) represented in Jacobian coordinates. The condition S1 != S2 is missed, leading to this point at infinity.

https://github.com/AleoHQ/snarkVM/blob/testnet3/curves/src/templates/short_weierstrass_jacobian/projective.rs#L437

        if u1 == u2 && s1 == s2 {
            // The two points are equal, so we double.
            self.double_in_place();
        } else {
            // If we're adding -a and a together, self.z becomes zero as H becomes zero.

According to the referenced https://eprint.iacr.org/2021/1595.pdf infinity points in projective coordinates are represented as (0:1:0). When S1 != S2, the method should return infinity, and the remaining portion of the calculation not be processed.

Fortunately, if the case of s1 != s2 is ignored and the process continues, the outcome will still yield z3 = 0, which means the final result is still the point at infinity.

Same efficient way to calculate doubling, if Y == 0, return POINT_AT_INFINITY https://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Jacobian_Coordinates

Proof-of-Concept

use snarkvm_curves::templates::short_weierstrass_jacobian::Projective;
use snarkvm_curves::traits::{AffineCurve, ProjectiveCurve};
use snarkvm_fields::One;
use snarkvm_curves::ModelParameters;
use snarkvm_curves::bls12_377::Bls12_377G1Parameters;
use snarkvm_fields::Field;
use snarkvm_utilities::TestRng;
use snarkvm_utilities::rand::Uniform;

fn main() {
    let one = <Bls12_377G1Parameters as ModelParameters>::BaseField::one();
    let two = one + one;
    let inverse = two.inverse().unwrap();
    println!("multiplicative inverse test: {:?}", inverse);

    let x_1 = two;
    let y_1 = two;
    let z_1 = two;

    let x_2 = two;
    let y_2 = -two;
    let z_2 = two;

    let mut p1: Projective<Bls12_377G1Parameters> = Projective::new(x_1, y_1, z_1);
    let p2 = Projective::new(x_2, y_2, z_2);

    p1 += p2;
    println!("p1: {:?}", p1);

    let rng = &mut TestRng::default();
    let mut p3: Projective<Bls12_377G1Parameters> = Projective::rand(rng);
    let p4 = Projective::new(p3.x, -p3.y, p3.z);
    p3 += p4;
    println!("p3: {:?}", p3);
}

Impact

This issue does not pose a security threat and cannot be exploited. It is a matter of achieving a more efficient calculation of the point at infinity.

[damons]

Is this really a bug? Per the impact, it's more of an optimization. Marking as such. Also, not going to hold mainnet for this.