Fix public key comparison for X25519 and Ed25519

[briansmith]

When we derive the public key from the private key and then compare it to the given public key, we need to compare the two public keys in a smarter way. For example, we're supposed to ignore the high bit of the public key, so the comparison should not compare two public keys as unequal if they differ only in the high bit. I need to double check but I think the comparison needs to mask the high bit and then do a conditional subtraction.

See https://boringssl-review.googlesource.com/c/14365/ and related X25519/Ed25519 discussion for motivation.

[briansmith]

/cc @ranweiler

[ranweiler]

I'll pick this up.

[ranweiler]

@briansmith, after following up on this, I'm not sure if we actually need to do anything here.

1. I think the Ed25519 check in Ed25519KeyPair::from_seed_and_public_key() is correct as-is. Why: for Ed25519, the public key is an encoded point. One coordinate fits into the first 255 bits, and we encode the sign of the other coordinate in the MSB of the last octet (as described in here in RFC 8032). So, the final bit should not be ignored, since it is really part of the point encoding. This is what we do right now.

2. For X25519, the MSB of the final octet of the public key should be zero and input must be masked/ignored for use with the X25519 function, as described here. This is currently accomplished in fe_frombytes() in curve25519.c, seen here. Related discussion from libsodium: jedisct1/libsodium/issues/147.

   But, I don't see where we're doing a public key comparison (like the one in Ed25519) that is sensitive to this. Afaict, what we care about is (a) how we respond to a public key whose final bit is set (reject it? parse as a 256-bit integer and reduce? mask/ignore it?), (b) how we generate public keys. The BoringSSL discussion you linked to is about intentionally doing the "wrong"/"anti-canonical" thing in (b) to ensure peers do the right thing in (a). But, there's no direct equality check of X25519 public keys that I can find (except in tests)— I think we only ever compute with them.

So, I think we're fine as-is, and the only work to be done is in #533. Let me know if I'm missing something!

[briansmith]

RE: Ed25519, you are right. This was my misunderstanding when I filed the original issue.

RE: X25519, eventually we will have such a check in the X25519 code, when we support static (reusable, non-ephemeral) X25519 keys pairs.

For X25519, the MSB of the final octet of the public key should be zero

Zero and one are both valid values for the MSB of the public key, according to the spec. In fact people argued quite vigorously that we should never recommend/require that it is zero.

Anyway, I guess I will close this since it is, effectively, a bug which isn't in the code base yet.

Thanks for looking into it!

[briansmith]

Wait, I remember why I left this open: For Ed25519, you are right that we should compare that the high bits are equal, but we need to compare the equality of the other 255 bits (mod 2**255 - 19). That is, there are ~18 public keys that have two encodings, right?

One thing I meant to look into: How many of those values in [2*255 - 19, 2*256) are actually on the curve? It would be interesting if none of them were on the curve.

[ranweiler]

but we need to compare the equality of the other 255 bits (mod 2**255 - 19).

Ah, I see! So, this is to address a situation where the first 255 bits contain an unreduced encoding of a valid curve coordinate (which may never happen, per your question).

Hmm, so since we're in a prime field p = 2**255 - 19, the interval [p, p+19) is equivalent to [0, 19) (mod p). So, it should be easy to reduce or check if any of the implied points are on the curve. However, independent of that question, in RFC 8032 Section 5.1.3, Step 1, it is written that:

The y-coordinate is recovered simply by clearing [the high] bit. If the resulting value is >= p, decoding fails.

So, as I understand the RFC, we should actually bail if we get an alleged point encoding with an unreduced y-coordinate part. Poking around, I also found this vaguely related patch: I am completely without context for it, but it seems like at least in that context, the preferred approach was not trying to reduce dubious parts of alleged compressed points: https://boringssl-review.googlesource.com/c/7440/

To me that suggests we should just follow the RFC and require the public key's y coordinate part to be reduced, aborting if out of range. In particular, we could then check encoded point equality on raw bytes, without any further arithmetic.

Do you read the RFC the same way I'm reading it? If so, do you feel like there's a strong reason to try to deviate from the RFC and attempt to reduce a seemingly out-of-bounds encoded field element?

[briansmith]

RFC 8032 Section 5.1.3, Step 1,

Excellent! I agree we should do what the spec says.

However, I think X25519 is different in this respect, right?

[briansmith]

https://boringssl-review.googlesource.com/c/7440/

That's for non-Curve25519 things, which have different rules and in particular a single canonical form.

[ranweiler]

However, I think X25519 is different in this respect, right?

Ah, right, for X25519 looks like the spec says:

Implementations MUST accept non-canonical values and process them as if they had been reduced modulo the field prime.

(FYI, I know you are well aware of this— I'm leaving these citations mostly for myself and others).

So, I guess we should still keep this open and in mind when we add a point comparison in supporting static X25519 keypairs (like you said earlier).