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

Support NIST validation criteria for Edwards points #626

Open
tarcieri opened this issue Feb 12, 2024 · 2 comments
Open

Support NIST validation criteria for Edwards points #626

tarcieri opened this issue Feb 12, 2024 · 2 comments

Comments

@tarcieri
Copy link
Contributor

tarcieri commented Feb 12, 2024

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 Ea,d defined over the prime field GF(p)
  2. Point Q

Output: ACCEPT or REJECT Q as an affine point on Ea,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 Ea,d by checking that (x, y) satisfies the defining equation ax2 + y2 = 1 + dx2y2, 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 Ea,d defined over the prime field GF(p)
  2. Point Q

Output: ACCEPT or REJECT Q as a point on Ea,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
Copy link
Contributor

rozbb commented Feb 15, 2024

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
Copy link

zacknewman commented Apr 16, 2024

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()
            })
}

tarcieri added a commit that referenced this issue Sep 19, 2024
Removes the previous warning that points are unvalidated: they're
validated using the ZIP-215 rules, which allows unreduced y-coordinates.
Points are ensured valid by performing decompression, which finds a
solution to the curve equation, or returns an error.

Adds references to ZIP-215 and #626
which is an issue about potentially adding support for the RFC8032/NIST
validation criteria in the future.
rozbb pushed a commit that referenced this issue Sep 19, 2024
Removes the previous warning that points are unvalidated: they're
validated using the ZIP-215 rules, which allows unreduced y-coordinates.
Points are ensured valid by performing decompression, which finds a
solution to the curve equation, or returns an error.

Adds references to ZIP-215 and #626
which is an issue about potentially adding support for the RFC8032/NIST
validation criteria in the future.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants