[blocked upstream] Evaluate hash-to-field options

[ggutoski]

Currently we convert a 32-byte hash digest to an integer modulo the curve order n via from_digest or from_bytes_reduced functions provided by RustCrypto. These functions do a naive reduction mod n, which produces a biased sample: some values are twice as likely to occur as others. Is this acceptable? If not, what to do about it?

References

• Section 5 of draft-irtf-cfrg-hash-to-curve-11 - Hashing to Elliptic Curves

[ggutoski]

The ECDSA implementation in k256 crate from RustCrypto also does naive reduction mod n:

Message hashed here: https://docs.rs/k256/0.9.6/src/k256/ecdsa/sign.rs.html#84

    fn try_sign(&self, msg: &[u8]) -> Result<S, Error> {
        self.try_sign_digest(Digest::chain(S::Digest::new(), msg))
    }

Message scalar derived from hash digest in ECDSA here: https://docs.rs/k256/0.9.6/src/k256/ecdsa/sign.rs.html#115

let msg_scalar = Scalar::from_digest(digest);

Note that from_digest is part of the hazmat module for ecdsa: FromDigest in ecdsa::hazmat - Rust. "Hazmat" means "hazardous material"---check out all the warnings here: ecdsa::hazmat - Rust.

Scalar::from_digest implemented here: https://docs.rs/k256/0.9.6/src/k256/arithmetic/scalar.rs.html#370-379

Self::from_bytes_reduced(&digest.finalize())

and Scalar::from_bytes_reduced docs here: https://docs.rs/k256/0.9.6/src/k256/arithmetic/scalar.rs.html#218-223

/// Subtracts the modulus when the byte array is larger than the modulus.

and here's the low-level arithmetic code just to prove that I'm not lying: https://github.com/RustCrypto/elliptic-curves/blob/2178da6034a42794c09da380812c12cf80e95f42/k256/src/arithmetic/scalar/scalar_4x64.rs#L215-L229

    /// Parses the given byte array as a scalar.
    ///
    /// Subtracts the modulus when the byte array is larger than the modulus.
    pub fn from_bytes_reduced(bytes: &[u8; 32]) -> Self {
        // Interpret the bytes as a big-endian integer w.
        let w3 = u64::from_be_bytes(bytes[0..8].try_into().unwrap());
        let w2 = u64::from_be_bytes(bytes[8..16].try_into().unwrap());
        let w1 = u64::from_be_bytes(bytes[16..24].try_into().unwrap());
        let w0 = u64::from_be_bytes(bytes[24..32].try_into().unwrap());
        let w = [w0, w1, w2, w3];

        // If w is in the range [0, n) then w - n will underflow
        let (r2, underflow) = sbb_array_with_underflow(&w, &MODULUS);
        Self(conditional_select(&w, &r2, !underflow))
    }

[tarcieri]

Relevant issues:

• k256: Add non-biased/non-zero constructors to Scalar RustCrypto/elliptic-curves#432
• elliptic-curve: hash-to-curve support RustCrypto/traits#481

[ggutoski]

We'll follow the lead of RustCrypto here. This issue can stay in a holding pattern for now until the dust settles.

[tarcieri]

I opened a PR to add a Reduce trait to the elliptic-curve crate, generic around an integer size allowing multiple impls to permit hash-to-scalar using either a narrow and wide reduction, selected by the size of the input:

RustCrypto/traits#768

Would appreciate any feedback.

[milapsheth]

During an offline discussion, we discussed that Bitcoin seems to also hash the message to a scalar by naive reduction modulo n. Since the signature we create has to be a valid Bitcoin signature too, we can't change use another hash-to-field function for the message itself.
Although, this issue still applies to some ZK proofs. Since, we can't do it for the message, there's probably no benefit in switching the hash-to-field implementation for other parts of the protocol.