XEdDSA support?

[LoupVaillant]

I’ve recently been approached about adding this feature to Monocypher. The use case is pretty simple: we have existing X25519 keys, and we would like to use them to sign stuff.

The problem with that is that the way EdDSA is constructed, the private key is first hashed, and decomposed into two parts: a secret scalar, and a secret seed for further hashes. The equivalent of the X25519 private key is the secret scalar, not the original private key. And of course, recovering that original private key is impossible, since it would require a preimage attack on SHA-512/256. XEdDSA gets around the problem by slightly modifying the original EdDSA scheme.

I have an objection, though. This use case is driven by backwards compatibility (existing keys). If instead we were willing to generate fresh keys, we could start with EdDSA keys, and convert them to X25519 format for key exchanges. This would have the same advantage of using one set of keys for everything, without the need to implement anything special.

Implementing all we need for XEdDSA is not hard. As for the code, I expect something between 25 to 35 additional SLOC. The real problem is deciding whether we should do it at all. @fscoto, do you have an opinion on this?

[covert-encryption]

(originally posted on the Covert issue but moving here)

It may need a few more than 25 lines of code in C but not much space at all because you already pay for the heavy parts in the Ed25519 signatures, and it could be another optional module like the ed25519 support is, to avoid making the main library bigger. Not sure whether modularity of hashes, incremental updates etc. gain anything here.

I gather you only need scalarmult in Ed25519 (ge_scalarmult_base?) but the sign needs to be calculated as well (for A, so it can be stored in the high bit of s and later restored). And for verification you need conversion of Mont pk to Edwards (a few lines very similar to the opposite conversion function). But as you mention, secret keys cannot be converted to Ed25519, instead in this algorithm you just use the Montgomery secret scalar directly (with clamping).

The hashes are the same as in EdDSA (SHA-512 + reduce). For calculating r you need to add a fixed 32-byte prefix of feffffff...ff as a static constant (one line of code for the array, one for the hash update) but don't mind the other hashn functions, as no other prefixed versions are used.

See the implementation in Covert or Signal (noting the latter is AGPL, so only viewed for ensuring compatibility of implementation).

[fscoto]

Re-reading the Modern Crypto archives on XEdDSA that seems to have been the place of its creation, I don't see anything that sticks out against XEdDSA as an algorithm.

For the sake of keeping my own assumptions consistent, I'd intended to summarize EdDSA and XEdDSA first, but the differences are numerous:

1. XEdDSA converts a Montgomery key to an Edwards key (always the one with the compressed representation such that the sign bit is even), namely on verification it takes a Montgomery u-coordinate as public key;
2. XEdDSA requires 64 random bytes Z, which are appended to the secret scalar (derived from the key) and the message on the first pass; this can be trivially emulated in crypto_sign_update() (and this kind of hedged signature is, in fact, the whole reason crypto_sign_update() was not removed prior to Monocypher 3.0.0);
3. XEdDSA requires that there be a 32-byte 0xfeffff... input block in the first pass before the secret scalar, which crypto_sign_update() cannot do.

XEdDSA thus differs from EdDSA in significant ways that implementers cannot easily emulate given the API that Monocypher exposes. Implementing it requires understanding Monocypher's internals at least a little bit. It also means dealing with the really finicky bignum/field element stuff to get the key conversion going.

The most important thing I want to know: Who else has implemented XEdDSA? Where is it found in the wild? It is evidently sufficiently uncommon that libsodium does not outright provide a function for it. Signal is a major protocol, however, but as far as I can tell, also the only notable user of XEdDSA (and the only user I know other than the people who have approached you about this in the first place). Monocypher should not provide off-beat algorithms for the sake of having it, especially considering we just rejected #226 with this reasoning.

Secondly, I want to know: How much does this affect the implementation complexity? The public-key signature code is by far the most complex piece of code in the entire thing with its super generic vtable construction. Not only does XEdDSA deviate in the hashing parts, it also requires new key conversion routines, which means touching more bignum/curve stuff. This puts the new batches of code somewhat remote of what Cure53 has reviewed and what is a simple and obvious change following that. While I understand that the audit is not a stamp of approval, in practice, people rely on it as such. Making significant changes thereafter worries me. So I'd rather avoid anything that gets anywhere near the complex signature code in the first place unless you can reassure me that the implementation is trivial to get right. This especially worries me since it either requires another layer of abstraction on top of what's already a wedding cake to account for XEdDSA key hashing or requires sections of redundant code that may each individually be changed down the line with its equivalent then being forgotten about.

libsodium ended up not implementing XEdDSA in favor of providing functions to do manual scalar multiplication on the edwards25519 (scalarmult_ed25519() and scalarmult_ed25519_base()). It's possible, however, to manually build XEdDSA with what libsodium provides since it gives access to scalar multiplication (including cofactorless/unclamped scalar multiplication), point addition/subtraction, random group element sampling. The libsodium documentation recommends going from edwards25519 to curve25519 instead.

Compatibility note: Minor version bump required.

Documentation note: I'll write the necessary pages, of which there will be multiple.

[covert-encryption]

As a background, our application uses existing keypairs of other software, in particular those generated by Age Encryption, which only exist in Curve25519 format. Also, for implementation it is much simpler to convert all keys to Montgomery format and then forget any Ed25519 keys that may have been used for sourcing them (e.g. SSH keys, also supported by both Age and Covert).

The very specific reason why we are using Monocypher is because it implements things that Sodium doesn't (dirty points and elligator).

[LoupVaillant]

Secondly, I want to know: How much does this affect the implementation complexity?

The only way to know is for me to actually implement the thing, and submit a pull request (that’s my plan for #218 as well).

[LoupVaillant]

Monocypher now supports XEdDSA.

Well, almost. Right now users still need to do a bit of work. But at least they won't need to poke at the internals of Monocypher. First, let's take a look at the signing scheme:

calculate_key_pair(k):
    E = kB
    A.y = E.y
    A.s = 0
    if E.s == 1:
        a = -k (mod q)
    else:
        a = k (mod q)
    return A, a

xeddsa_sign(k, M, Z):
    A, a = calculate_key_pair(k)
    r = hash1(a || M || Z) (mod q)
    R = rB
    h = hash(R || A || M) (mod q)
    s = r + ha (mod q)
    return R || s

So we start from a private X25519 key k, and deduce an EdDSA key pair (a,A). For the public key that's straightforward, just do the scalarmult, and set the sign of the x coordinate to "positive" (A.s = 0). With Monocypher, this is most easily done thus:

uint8_t k[32];  // X25519 secret key
uint8_t K[32];  // X25519 public key
uint8_t A[32];  // XedDSA public key
crypto_x25519_public_key(K, k);
crypto_x25519_to_eddsa(A, K);

Doing the scalar multiplication in Edwards space is faster, but we need to trim the scalar and set the sign bit manually:

uint8_t t[32];
uint8_t E[32];  // "regular" EdDSA public key
uint8_t A[32];
crypto_eddsa_trim_scalar(t, k);
void crypto_eddsa_scalarbase(E, t);
memcpy(A, E, 32);
A[31] &= 0x7f;

Flipping the sign of k is more problematic: it is the opposite sign of the trimmed private key k, and there are several ways to represent it. I guess they mean to reduce it modulo q, but then there is no further trimming:

uint8_t a[32];
crypto_eddsa_trim_scalar(a, k);
if ((E[31] & 0x80) != 0) {
    uint8_t zero[32] = {0} ;
    uint8_t q_m1[32] = { /* omitted */ } ;
    crypto_eddsa_mul_add(a, k, q_m1, zero);
} else {
    memcpy(a, k, 32);
}

Which is an awkward reuse of mul_add(), and requires a magic constant to work. Yuck. We could make it nicer by adding a helper function or providing calculate_key_pair() itself, but I'm not sure we should: XEdDSA remains (in my opinion) a very niche use case, and what we have now, though ugly, remains possible.

The signing function itself is fairly straightforward. Note the way it generates its nonce r:

r = hash1(a || M || Z) (mod q)

As far as I can tell the use of the random number Z is entirely redundant. I'm not sure why they have added it at all, it could as well be set to zero. Also, later in the specs, they suggest pre-hashing the message to avoid having to process it twice (if it's too big), but then we could just reduce Z modulo q instead (mind the scary ECDSA nonce reuse), or just remove the message from the hash (safer), or hash a prefix of the message instead of the entire message (safest). Then there's their domain separation thing (hence the "1" in hash1()), which I'm not sure is actually needed.

The rest is our regular EdDSA signature, including the end when we generate the second part of the signature:

s = r + ha (mod q)

I almost missed it, but this part right here is the actual reason why we needed to conditionally flip the sign of a: for verification to work we need aB = A, and if we don't flip the sign we would get aB = −A half the time, and verification would fail for those unlucky public keys.

---

Then we have verification:

xeddsa_verify(u, M, (R || s)):
    if u >= p or R.y >= 2|p| or s >= 2|q|:
        return false
    A = convert_mont(u)
    if not on_curve(A):
        return false
    h = hash(R || A || M) (mod q)
    Rcheck = sB - hA
    if bytes_equal(R, Rcheck):
        return true
    return false

Now Monocypher can easily do the same: just use crypto_x25519_to_eddsa() and crypto_ed25519_check() in the obvious way. Some caveats apply for some edge cases (see #248 for exactly why), but for normal signature verification where the only question is whether the signature is legit or not, it doesn't matter.