Support NIST validation criteria for Edwards points

[tarcieri]

The current implementation uses ZIP-215 rules. We've received requests for stricter validation (#380, #623) which correspond to the NIST validation criteria, namely ensuring that the Edwards y-coordinate doesn't overflow the field modulus, and that the resulting point belongs to the prime order subgroup, which map to the NIST partial and full public key validation rules respectively.

NIST defines public key validation criteria in SP 800-186 Appendix D.1.3: Twisted Edwards Curves:

D.1.3. Twisted Edwards Curves

D.1.3.1. Partial Public Key Validation

Inputs:

1. Edwards curve E_a,d defined over the prime field GF(p)
2. Point Q

Output: ACCEPT or REJECT Q as an affine point on E_a,d.

Process:

1. Verify that both x and y are integers in the interval [0, p−1]. Output REJECT if verification fails.
2. Let Q = (x, y). Verify that (x, y) is a point on E_a,d by checking that (x, y) satisfies the defining equation ax² + y² = 1 + dx²y², where computations are carried out in GF(p). Output REJECT if verification fails.
3. Otherwise, output ACCEPT.

D.1.3.2. Full Public Key Validation

Inputs:

1. Edwards curve E_a,d defined over the prime field GF(p)
2. Point Q

Output: ACCEPT or REJECT Q as a point on E_a,d of order n.

Process:

1. Perform partial public key validation on Q using the procedure of Appendix D.1.3.1. Output REJECT if this procedure outputs REJECT.
2. If Q = (0,1), output REJECT.
3. Verify that nQ = (0,1). Output REJECT if verification fails.
4. Otherwise, output ACCEPT.

Some possibilities for APIs:

• Inherent methods: e.g. EdwardsPoint::decompress_nist_partial / EdwardsPoint::decompress_nist_full
• Single method which accepts an enum specifying the validation criteria: EdwardsPoint::decompress_with(PointValidation::NistPartial)

[rozbb]

I like the latter style. Maybe called EdwardsPoint::validated_decompress. I thought about maybe supporting arbitrary validation routines by defining a trait. But for now I think it suffices to have a fixed enum. Users who want a different kind of validation can just implement their own bytes -> Option<EdwardsPoint> function

[zacknewman]

Until this gets implemented, I would like to write code that conforms to the NIST criteria when validating a CompressedEdwardsY instance. Ignoring the probable overhead, does the below code work?

use curve25519_dalek::edwards::CompressedEdwardsY;
pub fn nist_verify(bytes: [u8; 32]) -> bool {
    // MUST ensure `bytes.len() == 32` before calling.
    const fn x_is_neg(bytes: &[u8]) -> bool {
        bytes[31] > 127
    }
    // MUST ensure `bytes.len() == 32` before calling.
    // MUST ensure `x_is_neg(bytes)` returns `false` as well since we assume the sign bit is not set.
    fn y_is_one(bytes: &[u8]) -> bool {
        const fn is_zero(byte: &u8) -> bool {
            *byte == 0
        }
        bytes[0] == 1 && bytes[1..].into_iter().all(is_zero)
    }
    // MUST ensure `bytes.len() == 32` before calling.
    // MUST ensure `x_is_neg(bytes)` returns `false` as well since we assume the sign bit is not set.
    fn y_is_too_great(bytes: &[u8]) -> bool {
        const fn is_255(byte: &u8) -> bool {
            *byte == 255
        }
        bytes[0] > 236 && bytes[31] == 127 && bytes[1..31].into_iter().all(is_255)
    }
    let slice = bytes.as_slice();
    // Ensures x > -1, (x, y) ≠ (0, 1), and y ∈ [0, 2^255 - 20].
    !(x_is_neg(slice) || y_is_one(slice) || y_is_too_great(slice))
        && CompressedEdwardsY(bytes)
            // Ensures the point is on the curve.
            .decompress()
            .map_or(false, |point| {
                // Ensures the point belongs to the prime order subgroup.
                point.is_torsion_free()
            })
}