Skip to content

Security questions about normalize_signature #12

@defkit

Description

@defkit

schnorr/src/lib.nr

Lines 132 to 158 in 07ab027

// this method reduces the signature to the range [0, BN254_Fq_MODULUS)
fn normalize_signature(sig_e: EmbeddedCurveScalar) -> EmbeddedCurveScalar {
let mut hi = sig_e.hi;
let mut lo = sig_e.lo;
// get the quotient
let q = unsafe { __get_quotient(hi, lo) };
let MODULUSmq = (BN_P_m[q].0, BN_P_m[q].1);
let MODULUS = BN_P_m[1];
// remove MODULUS * q from lo/hi
let borrow = unsafe { __gt(MODULUSmq.0, lo) };
// rlo, rhi is the signature without the multiple of MODULUS
let rlo = lo - MODULUSmq.0 + borrow as Field * TWO_POW_128;
let rhi = hi - borrow as Field - MODULUSmq.1;
// now we validate that rlo and rhi are positive
rlo.assert_max_bit_size::<128>();
rhi.assert_max_bit_size::<128>();
// validate that rlo, rhi is smaller than MODULUS
// if the lo is larger than the modulus lo we have to get a borrow
let borrow = unsafe { __gt(rlo, MODULUS.0) };
let rplo = MODULUS.0 - rlo + borrow as Field * TWO_POW_128;
let rphi = MODULUS.1 - rhi - borrow as Field;
// check that rplo and rphi are positive
rplo.assert_max_bit_size::<128>();
rphi.assert_max_bit_size::<128>();
EmbeddedCurveScalar::new(rlo, rhi)
}

  1. Why we normalize sig_e but don't normalize sig_s?

    schnorr/src/lib.nr

    Lines 77 to 78 in 07ab027

    let reduced_sig_e = normalize_signature(sig_e);
    let r = multi_scalar_mul([g1, public_key], [sig_s, reduced_sig_e]);
  2. Why q and borrow are unconstrained? It seems like it might be broken by malicious prover
  3. It seems that
    rhi.assert_max_bit_size::<128>();
    is not strict enough, because if $rhi = 2^{127}$ it still overflows BN254 scalar field order

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions