Nikos Mavrogiannopoulos nmav@gnutls.org writes:

...

1. Should ecc-curves.h really declare nettle_curve25519? Its' not needed for any of the documented functions, except for obscurities like doing ecdsa (not eddsa) over the curve. It could be moved to ecc-internal, or be marked as internal in some other way. Perhaps renaming to _nettle_ed25519 would be appropriate.

A symbol that is not used can only cause issues. Using however, _nettle_ed25519 would still export the symbol with the current ld script.

It is used internally, but application code doesn't need it for any of the documented functions (with the obscure exception mentioned above).

Hmm. For now, I think I'd prefer to move the declaration to ecc-internal.h. And maybe rethink how if and how we should do a unified interface for ecc operations on different types of curves.

...

2. curve25519_mul should be changed to have a void return type (an earlier implementation failed for inputs which didn't correspond to points on the curve, but instead were points on its twist). But the current implementation, using the Montgomery ladder, doesn't care and computes a well defined result for all inputs.

No idea about this, do you think that a future re-implementation could need an error code?

Not sure. Maybe if there's a significant speedup. There's some potential when optimizing the twisted edwards point operations, but the coordiante transformation also has a cost, so I think it is unlikely to beat the montgomery ladder by a large margin.

...

3. struct ed25519_private_key and struct ed25519_public_key include compile-time constant limb arrays. At least for the public key, this will imply an ABI break if/when we switch to a base 2^51 representations for GF(2^255 - 19). So maybe switch to dynamic allocation for struct ed25519_public_key, or both structs?

I'm not familiar with the other representations, but could there be a one-size fits all structure?

Maybe. On 64-bit machines, the base 2^51 bit trick expands each coordinate from 4 to 5 words. On second thought, that conversion could be done when the point is used, the cost should be negligible compared to the scalar multiplication.

Let me think aloud.

It's not obvious how much to cache in struct ed25519_public_key. The external public key is in compressed form: The y-coordinate and the lest significant bit of the x coordinate, 256 bits total. It must be decompressed by recovering the x coordinate. This is done by ed25519_sha512_set_public_key, and the result is stored in struct ed25519_public_key. And the function returns failure if decompression fails.

When the key is used in ed25519_sha512_verify, there are additional computations that depend on the public key only. The point is used for a scalar multiplication, where the scalar depends on the message. Then the point is expanded into extended coordinates, and a lookup table with 16 entries (2^ECC_MUL_A_EH_BITS). This is currently not cached.

I imagine it's an unusual case is to verify lots of signatures with the same key. So one could go to the other extreme and not cache anything at all, eliminate struct ed25519_public_key, and let ed25519_sha512_verify take the compressed public key a input.

In the other hand, *signing* several messages using the same key seems like a common use case, e.g., an ssh or tls server signing the keyexchange handshake for each connection/session. The work done by ed25519_sha512_set_private_key includes an expensive scalar multiplication. But this is needed only for computing the corresponding public key, which is added into the hashing of the message. So maybe one could have the following simpler ed25519 interface, representing all keys as strings of ED25519_KEY_SIZE octets:

void ed25519_sha512_public_key (uint8_t *pub, const uint8_t *priv);

void ed25519_sha512_sign (const uint8_t *priv, const uint8_t *pub, size_t length, const uint8_t *msg, uint8_t *signature);

int ed25519_sha512_verify (const uint8_t *pub, size_t length, const uint8_t *msg, const uint8_t *signature);

That the public key is an input to ed25519_sha512_sign means that it needs only a single scalar multiplication, and it's up to the caller to compute and possibly cache the needed public key. One could even allow pub to be NULL, and in that case recompute it (which makes the signing take twice the time).

Regards, /Niels

On Wed, 2015-03-11 at 21:08 +0100, Niels Möller wrote:

...

void ed25519_sha512_public_key (uint8_t *pub, const uint8_t *priv);

void ed25519_sha512_sign (const uint8_t *priv, const uint8_t *pub, size_t length, const uint8_t *msg, uint8_t *signature);

int ed25519_sha512_verify (const uint8_t *pub, size_t length, const uint8_t *msg, const uint8_t *signature);

That the public key is an input to ed25519_sha512_sign means that it needs only a single scalar multiplication, and it's up to the caller to compute and possibly cache the needed public key. One could even allow pub to be NULL, and in that case recompute it (which makes the signing take twice the time).

Any comments or opinions on the eddsa interface? I'd like to come to some conclusion fairly soon.

None from me. As it is now this algorithm has no real world usage (non standardized), so I cannot say whether this API is good or not. It looks reasonable, but unless we have any standard using it's purely theoretical. I'd say go for it, and if needed later we add another API.

regards, Nikos

On Thu, Mar 12, 2015 at 8:57 AM, Niels Möller nisse@lysator.liu.se wrote:

Nikos Mavrogiannopoulos nmav@gnutls.org writes:

...

but unless we have any standard using it's purely theoretical. I'd say go for it, and if needed later we add another API.

At least we're working on standardization... See https://datatracker.ietf.org/doc/draft-josefsson-eddsa-ed25519/

That's nice. If this is supposed to be used in certificates, an OID as well as some guidance on how to store the keys in ECPoint format will be required. I'm not sure whether this should be done on this document, but should be done somewhere :)

regards, Nikos

...

...

...

...

"NM" == Niels Möller nisse@lysator.liu.se writes:

NM> An object identifier for the algorithm is definitely needed. If at NM> all possible, I think public keys should be represented as plain NM> strings of 32 octets, with no additional wrapping.

I'm sure there will be some disagreement from those with something to sell. There always is. But one does hope sense will win out and the above will win.

-JimC

Nikos Mavrogiannopoulos nmav@gnutls.org writes:

...

2. curve25519_mul should be changed to have a void return type (an earlier implementation failed for inputs which didn't correspond to points on the curve, but instead were points on its twist). But the current implementation, using the Montgomery ladder, doesn't care and computes a well defined result for all inputs.

No idea about this, do you think that a future re-implementation could need an error code?

I've done this change now. In the documentation, I now say that the output is undefined for inputs on the twist curve. Which I think is fine for diffie-hellman: if you don't trust your partner to do his/her part of the diffie-hellman exchange correctly (and authenticate the messages you receive), you can't expect the generated session key to be secure or useful, no matter how curve25519_mul computes the shared secret.

After optimizing the twisted edwards point operations, one could try the alternative implementation using a (somewhat expensive) change of coordinates to the twisted edwards curve, followed by a scalar multiplication there (which should be slightly faster than the Montgomery ladder), and then a change back to the original coordinates.

It seems questionable that can be faster, and unlikely that it's going to be singificantly faster. So if that strategy is ruled out by benchmarks, we can document that the output for all possible inputs is what's computed by the Montgomery ladder.

Regards, /Niels

Nikos Mavrogiannopoulos nmav@gnutls.org writes:

I only follow in the high level, but wouldn't it be better for this function to be allowed fail if there are cases could fail? Even if the current version doesn't, a future version could detect a broken peer (but not malicious) and that is better than just ignoring it.

I think it's a desirable property of curve25519, as implemented using the Montgomery ladder, that no "point validation" is needed (even if I don't understand the fine details in why point validation is needed for many other curves). So

1. I like the interface with no return value, and I'd like to keep it unless there's some *significant* performance gain using some other method. And every eliminated return value makes the Nettle API simpler.

2. I think it is unlikely that the Montgomery method will be beaten. I discussed it briefly with djb before switching to the current implementation. The thing is that with twisted Edwards, an addition (8M) or a doubling (3M + 4S) is significantly faster than one step of the Montgomery ladder (5M + 4S). But for a scalar multiply we need 255 doublings + a bunch of additions (sligthly more than 64, with a 4-bit window size) + cost of point decompression + cost of side-channel silent table lookups. And the total is likely higher than for the 255 Montgomery steps in the current implementation.

It's just that I'm a bit anxious to commit to using Montgomery ladder in future versions until I have done some benchmarks of my own. Maybe I should stop worrying about that, and document the output fully for all possible inputs? In the unlikely case that it turns out later to be a mistake, we *can* do an API break and fix it later.

Regards, /Niels