Do you reject points that are not in the main subgroup?

[alexqrid]

Hi! Your lib is used in solana-go-sdk project - https://github.com/rayzub/solana-go-sdk/blob/492f11d95038fc6dcb9a4ea1c5815d67cc54ad4a/common/public_key.go#L74 to check whether the key is on the curve. I've been trying to implement the same check on php and used standard function sodium_crypto_sign_ed25519_pk_to_curve25519 which is calling libsodium C lib, and for the same payload your lib finds appropriate key on the curve The payload is {129, 4, 5, 6, 7, 9, 13, 14, 20, 21, 148, 37, 166, 39, 44, 47, 49, 182, 183, 186, 82, 89, 92, 94, 226, 99, 106, 118} (hex: 4dc95e3c28d78c48a60531525e6327e259b7ba0d2f5c81b694052c766a14b625), and

_, err := new(edwards25519.Point).SetBytes(p.Bytes())

is calculated without any errors, but libsodium fails to find it.

I've reported the issue to the libsodium @jedisct1 answered me:

This point is on the edwards25519 curve, but not in the correct subgroup. You can easily check that multiplying it by the prime group order doesn't lead to the neutral element. crypto_core_ed25519_is_valid_point() returns false and the point is rejected by all arithmetic operations. Not just crypto_sign_ed25519_pk_to_curve(). crypto_sign_keypair() will never generate such point. It's not a valid Ed25519 public key. Other implementations may not check this, because the check requires extra CPU cycles. Libsodium does.

I am not familiar with all this curve math, but want to check that it's not a serious error in your implementation. Is it somehow related to #33 ?

[jedisct1]

curve25519 is twist secure. Omitting that check is usually not going to have security implications. There is no standard document on how to map an Ed25519 public key into an X25519 public key, so this is implementation-dependent.

For a function expecting an Ed25519 key (not an arbitrary Edwards25519 point), such check can catch bugs in implementations and protocols. If the point is not on the group generated by the standard Ed25519 base point, it means that there's no secret counterpart to that public key, which is unlikely to be expected.

[FiloSottile]

filippo.io/edwards25519 is a low level edwards25519 library, so I believe it's correct for SetBytes to only check the curve equation. Checking prime order group membership is #33. Closing as duplicate.

(I don't think this is related to twist security. Points on the twist are not on the curve, and will fail SetBytes. X25519 is a DH function designed to work on both Curve25519 and its twist to skip all public key validation, but this library implements pure edwards25519.)

P.S. I agree that Ed25519-to-X25519 is unspecified but I'd argue that doing prime order checks in it is a bit weird since X25519 is specified not to do them on public keys.