Verifying EdDSA signatures using xedDSA verify function.

Question

I'm running into a problem where I generate signatures using a library like pynacl's (https://pynacl.readthedocs.io/en/stable/signing/) ed25519 implementation and then when I verify it using xedDSA's verify function (https://github.com/signalapp/curve25519-java/blob/master/android/jni/ed25519/additions/xeddsa.c#L45) it passes sometimes and fails other times.

This seems to be related to the priv/pub key pair that generates the signatures. Once a keypair generates a signature that the xedDSA function can verify, all subsequent signatures are also validated correctly from the same keypair. I'm converting the ed25519 public key that is given by pynacl into a curve25519 pub key (verify_key.to_curve25519_public_key()), which I then pass into the xedDSA function.

In the intro here: https://signal.org/docs/specifications/xeddsa/#curve25519

It is stated that an ed25519 signature will be correctly verified by a xedDSA verify function. But this is not the case here.

Can anyone tell me exactly why this is happening? I'm quite confident it has something to do with the key generation and the subsequent conversion of the ed pubkey to a curve pubkey. But I don't know enough about crypto to pinpoint the issue.

Answer 1

From your link:

XEd25519 signatures are valid Ed25519 signatures and vice versa, provided the public keys are converted with the birational map.

Unfortunately, the vice-versa is wrong.

XEd25519 works by requiring the private key to be positive in the sense that it will produce a positive edwards public key. This is obtained by negating the private key if it produces a public key with negative $x$. (negative and positive in the sense of LSB as in ed25519)

This is assumed to hold in verification but it doesn't if the signature was generated with ed25519.

More specifically, in ed25519 you can have both positive and negative public keys $A$. Then your signature is computed as: $R = rB, s = r + ha$ Note that in ed25519 you have that $A = aB$. Verification is done by verifying that $R = sB - hA$.

In ed25519 this works because $R = rB = (r + ha)B - h(aB)$.

However, when using XEd25519 things changes as the public key are implicitly assumed to be positive (curve25519 lacks the sign information so some assumption should be made), so you would have end up with a sign bit flip in the verification equation: $rB \neq (r + ha)B - h*(-A)$.

So you could verify in this way only signatures made by an ed25519 key pair with a positive public key.

Fixes: I think that you could probably be ok in testing $R = (r + ha)B \pm hA$ which will hold in one of two cases if the signature is valid, but I guess that would be a problem when your implementation uses a double base scalar multiplication which is pretty common for signature verification. A better idea would be to replace XEd25519 with qDSA which is a more natural way to do signatures over Montgomery curves