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.

  • $\begingroup$ could you post your steps to clarify the problem? $\endgroup$ – kelalaka Oct 5 '18 at 6:41

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

  • $\begingroup$ I understand what you're saying and I want to verify this. How do I determine if a pub key is positive or negative? Is it as simple as looking at the MSB and seeing if it's a 1 or am I missing something? With my preliminary tests in pynacl I'm not seeing any correlation between negative and positive pub keys. Actually, it'd be able to verify this just by looking at the sign bit? We should see that sigs are verified correctly when sign bit is 0 for ed25519 pubkey and sigs are not verified when sign bit is 1 on the ed25519 pubkey, correct? If so, what bit is the sign bit? Last bit? $\endgroup$ – Maaz Oct 5 '18 at 19:19
  • $\begingroup$ I'm using the following python program I created: pastebin.com/y5gtJvrR that uses pynacl. It prints out the ed pub key as well as the converted curve key. For example here are two sets of keys one passes? ed pub: ac4942960ed62ce775f6fd145baaa1b22db9a8dccedfe14258dae40a7123cc5e curve pub: 2e1c5c16ded614bcd400406c06dca00c82e2a40010560fc4980817fd7beb2a5f and ed pub: da7ed763d59da9a6bdee2661ba9787dc23d96d84665d71bfbcd5ab39727da7c5 curve pub: 89729d9d276a130a8be6dcd3a0035506e8dbf4b0cccf00ad5b1e30ac2d2ebd79 how can you tell which one will pass? $\endgroup$ – Maaz Oct 5 '18 at 20:56
  • 1
    $\begingroup$ @Maaz the LSB of the edwards public key should be the sign bit. Your first key ends with 0x5E which is even, so it's positive and it should work. The last one ends with 0xC5 which is odd and therefore should be negative and should not work. $\endgroup$ – Ruggero Oct 9 '18 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.