EdDSA and new curves

[bytemare]

EdDSA and new curves

[rben-dev]

Hi,

After a rather long integration effort, we have pushed a beta version of EdDSA (25519 and 448) signature algorithms on a dedicated branch eddsa-sm2: https://github.com/ANSSI-FR/libecc/tree/eddsa-sm2

As previously discussed in the post, EdDSA has been implemented using isogenies between Twisted Edwards / Montgormey / Weierstrass curves : although this induces a performance hit, this has the great advantage of keeping the library's scalar multiplication and addition formulas unique and sound (inheriting all the protections put there).

The current implementations of ed448 and ed25519 follow RFC8032 (https://datatracker.ietf.org/doc/html/rfc8032) in all its variants (pure, with context, pre-hashed) and should pass the provided test vectors.

There is still work in progress on the signature and verification init / update / final APIs as pure EdDSA needs to process twice the input message during signature, and hence a "streaming" mode is not possible. We plan to somehow improve our current API to be compatible with such algorithms that do not support message streaming.

Regards,

[rben-dev]

EdDSA is now stable and has been merged upstream.

[rben-dev]

Hi,

Sorry for leaving this issue empty for so long. Please find some explanations hereafter.

libecc is currently designed/built using curves with a short-Weierstrass equation form at its core (i.e. for points addition and doubling formulas). Edwards curves (the family of curves encompassing Ed25519) and Montgomery curves (the family of curves encompassing Curve25519) use different formulas, hence the complexity of adding such curves to libecc "as is".

The optimal way of adding such curves to libecc without new formulas implementation would be to exploit the isomorphisms that exist between Weierstrass / Edwards / Montgomery curves (see https://tools.ietf.org/id/draft-struik-lwip-curve-representations-00.html#rfc.appendix.A.1 for the mappings implementations), this would require some development work and integration.
Another way of adding these curves would be to integrate new formulas, but this will require more work in the "curve" layer as libecc has many routines using the Weierstrass form as a hypothesis (on the other hand, using dedicated formulas will benefit from the inherent security claims of Ed25519 and Curve25519, regarding side channels, fault injections and so on).

Finally, on top of the "curves" layer the EdDSA signature scheme will have to be implemented in the "signature" layer (this is not the most complex task as this signature algorithm is very close to the existing EC*DSA schemes).

For now, we primarily seek stability and security for the existing code base. Adding Ed25519, Curve25519 and EdDSA are indeed future work but with lower priority (although we completely understand the need for such an integration).

I hope that these explanations make things clearer!
Regards,

[rben-dev]

As a follow up, the new signature and verification init / update / final APIs (supporting message "streaming" and "non-streaming" modes) have been integrated and tested on the eddsa-sm2-newapi branch: https://github.com/ANSSI-FR/libecc/tree/eddsa-sm2-newapi (other improvements and additions to the library are also included).

We plan to merge it to the master branch in the next weeks after some more reviews and tests, but it should be usable and stable by now.

Regards,

[GoodiesHQ]

I know this is old, but would adding in these curves be challenging? Ed25519 and Curve25519 would be fantastic.