EdwardsPoint::decompress accepts y higher than field modulo

[paulmillr]

EdwardsPoint::decompress accepts y higher than field modulo

Which is invalid as per RFC8032 5.1.3.

   Decoding a point, given as a 32-octet string, is a little more
   complicated.

   1.  First, interpret the string as an integer in little-endian
       representation.  Bit 255 of this number is the least significant
       bit of the x-coordinate and denote this value x_0.  The
       y-coordinate is recovered simply by clearing this bit.  If the
       resulting value is >= p, decoding fails.

[AnomalRoil]

RFC8032 is about EdDSA, while this repo is really "just" about Curve25519, so I'd argue that this is not an issue for curve25519, but rather for the ed25519 repo.

That being said, it seems that currently https://github.com/dalek-cryptography/ed25519-dalek is directly using the decompress function without doing that check because:

    /// The caller is responsible for ensuring that the bytes passed into this
    /// method actually represent a `curve25519_dalek::curve::CompressedEdwardsY`
    /// and that said compressed point is actually a point on the curve.

Also the struct EdwardsPoint is guaranteed to hold a valid point on the curve:

curve25519-dalek/src/edwards.rs

Lines 199 to 201 in 967d8b6

	let (is_valid_y_coord, mut X) = FieldElement::sqrt_ratio_i(&u, &v);
	if is_valid_y_coord.unwrap_u8() != 1u8 { return None; }

E.g. what if I consider the CompressedEdwardsY value 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f, once decompressed it will give me a point that is equivalent to the point 0x1200000000000000000000000000000000000000000000000000000000000000:

PublicKey(CompressedEdwardsY: [255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 127]), 
EdwardsPoint{
	X: FieldElement51([1765291371327528, 828421974544742, 17095614122396, 1955301457663811, 970631510557499]),
	Y: FieldElement51([2251799813685247, 2251799813685247, 2251799813685247, 2251799813685247, 2251799813685247]),
	Z: FieldElement51([1, 0, 0, 0, 0]),
	T: FieldElement51([250047292302165, 1400796659693882, 307721054203134, 1418429032669878, 1708768494238261])
})

PublicKey(CompressedEdwardsY: [18, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 
EdwardsPoint{
	X': FieldElement51([1765291371327528, 828421974544742, 17095614122396, 1955301457663811, 970631510557499]),
	Y': FieldElement51([18, 0, 0, 0, 0]),
	Z': FieldElement51([1, 0, 0, 0, 0]),
	T': FieldElement51([250047292302165, 1400796659693882, 307721054203134, 1418429032669878, 1708768494238261])
})

And both are equal once converted into affine coordinate, since (X/Z, Y/Z) is equal to (X'/Z', Y'/Z').
(See here to see how you can manually check this.)

It's also worth noticing that the compress function will properly do the reduction, so it just means we are accepting keys that are not properly encoded as per the RFC, but we are not generating them.

On my side I don't really see any issue with that as long as we are using valid points. It's just about its encoding in the end and whether we accept "non-canonical" encodings or not I guess.

[paulmillr]

It's behavior that defies specification. If dalek wants to behave by its own, it's cool, but a note in documentation should be added.

[AnomalRoil]

That's for ed25519-dalek, not for curve25519-dalek IMO.
I was also just providing some context, not saying we shouldn't change it or whatsoever.

[paulmillr]

Right, I should have probably opened it in ed repository...

[burdges]

Issues like this matter primarily for consensus protocols with implementations in other languages. There are other reasons the ed25519-dalek is not ideal for consensus, so the best place maybe https://github.com/ZcashFoundation/ed25519-zebra It does not adhere to the standard or have equivalent libs in other languages, but at least it makes implementing everything you'd want in consensus possible.

[dconnolly]

Issues like this matter primarily for consensus protocols with implementations in other languages. There are other reasons the ed25519-dalek is not ideal for consensus, so the best place maybe https://github.com/ZcashFoundation/ed25519-zebra It does not adhere to the standard or have equivalent libs in other languages, but at least it makes implementing everything you'd want in consensus possible.

There is also at least one implementation in Go that is compatible with the validation criteria implemented in ed25519-zebra and specified in ZIP-215

[kayabaNerve]

I'd personally prefer dalek include a decompress_canonical function due to the application of this outside of just EdDSA, with the hopes it can be more performant than the current solution (reserializing entirely). Such a function would need to check for both lack of reduction and if the sign bit was set for 0.

[tarcieri]

FWIW 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.

Per that description, allowing y to be higher than the field modulus is not correctly implementing step 1 of partial validation

[rozbb]

Ugh yup I think this merits breaking change in ed-

[tarcieri]

The ZIP-215 rules require the current behavior which allows an unreduced y-coordinate:

https://zips.z.cash/zip-0215

It is not required that A and R are canonical encodings; in other words, the integer encoding the y-coordinate of the points may be unreduced modulo 2²⁵⁵-19.

So unfortunately there is a conflict between the ZIP-215 rules and the NIST rules.

Based on some Zulip discussion, one option we're considering is adding a separate set of "strict" methods which implement the NIST validation criteria.

[tarcieri]

My latest recommendation for this issue would be to add EdwardsPoint::decompress_nist which applies the NIST validation criteria, i.e. rejects y-coordinates which overflow the modulus.

That's a purely additive change and not a blocker for a 4.0 release.

[paulmillr]

yeah, sounds good.

what about naming? just nist? it's also rfc8032, innit?

[tarcieri]

Yes, though I imagine people concerned with following particular validation rules are going to be more concerned with NIST than RFC8032

[kayabaNerve]

I'm more concerned with it being strict, not any specific standards. That means not only would it reject anything exceeding the modulus, yet also the negative identity.

[tarcieri]

We can call it "strict" but that's a little nonspecific, especially when NIST has a further set of "strict" verification criteria.

If someone has a better suggestion for a name which covers RFC8032 vs NIST point validation criteria (or can spot any discrepancies between the two) that'd be good to know.

[kayabaNerve]

My highlight wasn't on the naming, yet on the note NIST allows negative identity. Accordingly, I don't care to use a NIST-matching function, I care to use a strict function offering canonicity. While such a check could be added to decompress_nist, it'd no longer be implementing the NIST standards, yet an extended set of criteria (which would likely defeat the purpose).

My proposal is for a decompress_canonical, and a decompress_*standard*.

[tarcieri]

I'm going to close this issue in favor of #626 which is a new feature tracking issue for implementing NIST's validation criteria.

Notably EdwardsPoint::decompress accepting a y-coordinate higher than the field modulus is expected behavior under the ZIP-215 validation criteria which is the intended baseline criteria implemented by these crates, but we can add new APIs that support stricter validation criteria.

So closing this as "working as intended".