Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
stonejiajia opened this issue Jan 21, 2024 · 1 comment
Labels
does not block mainnet For when we make decisions that this will not block mainnet. enhancement New feature or request

Comments

@stonejiajia
Copy link

🐛 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

2024-01-21_13-50

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.

2024-01-21_13-54

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

2024-01-21_23-40

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.

@stonejiajia stonejiajia added the bug Something isn't working label Jan 21, 2024
@damons damons added enhancement New feature or request does not block mainnet For when we make decisions that this will not block mainnet. and removed bug Something isn't working labels Jun 11, 2024
@damons
Copy link

damons commented Jun 11, 2024

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
does not block mainnet For when we make decisions that this will not block mainnet. enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

2 participants