Adding Ed25519/EdDSA

[jack-fortanix]

Description

• Type: Question

Question

This is not a duplicate of #388. We would like to contribute a Ed25519/EdDSA implementation to mbedtls. However before we begin work I would like to ask for your opinion on how it should be done, so that we can create a PR that would be acceptable to upstream.

My inclination would be to make use of an existing public domain constant time implementation such as ref10. However my impression, based on how the x25519 code is done, is that you prefer to use bignum arithmetic. Would you prefer I convert Edwards to Montgomery and use existing Montgomery logic? Or add new explicit formulas for Edwards curves? Either way I assume I would be adding a new configuration ECP_EDWARDS and adding a ecp_curve_type of ECP_TYPE_EDWARDS.

EdDSA has some unusual behavior with regards to handling the message (see https://tools.ietf.org/html/rfc8032#section-5.1.6). I planned on surfacing "Pure" EdDSA by having the application call pk_sign with a digest of MBEDTLS_MD_NONE and the "hash" field consisting of the arbitrary length message which is subsequently hashed with SHA-512 as described in RFC 8032. Would this API be acceptable?

Also, if you would prefer new Edwards specific formulas, do you have an opinion on which coordinate system to use? http://www.hyperelliptic.org/EFD/g1p/auto-edwards.html

We'd also like to add the PKIX encodings specified in https://tools.ietf.org/html/rfc8410. Just wanted to check that these would also be accepted.

[yanesca]

Hi @jack-fortanix,

Mbed TLS has a mechanism to provide alternative implementations for cryptographic primitives and we encourage users to use it when they want to use alternative implementations. However, existing public domain implementations are not something that we usually accept as a contribution and I can't promise for sure that this would get accepted. If this would be your preferred option, then please let me know and I'll find it out for you.

Converting to Montgomery coordinates comes with a much smaller code size, implementing explicit formulas results in faster computations and consumes less battery. Either or both could be acceptable. If you decide to implement both, then please add a compile time switch that chooses between them.

Yes, adding a new configuration option and curve type will probably be necessary.

I don't have an opinion on which representation to use. @mpg do you have a preference?

I think it would be acceptable to work around the limitations of the API like this, just make sure that you update the documentation accordingly.

Yes, I think we would like to accept the PKIX encodings as well.

Could you please base your changes on Mbed Crypto repository and submit a PR there when you are ready? Could you please submit a separate PR for the PKIX encodings in this repository?

Thank you for considering to contribute to Mbed TLS!

[nscnd]

Hi @jack-fortanix

Did you ever took the time to work on this ? I would be very interested to see what you have come up with (if you have something to show).

Thanks,

[tobysunx]

Hi @jack-fortanix Did you ever took the time to work on this ?

Thanks,

[jmegevand]

Hello What is the status of this feature ?

[KanPlus]

@jack-fortanix I was very interesting , what is the status currently?

[aurel32]

Hi @yanesca

As the work seem to have been stalled, I have also started to look at that myself.

Converting to Montgomery coordinates comes with a much smaller code size, implementing explicit formulas results in faster computations and consumes less battery. Either or both could be acceptable. If you decide to implement both, then please add a compile time switch that chooses between them.

The Montgomery curve support in MbedTLS is implemented for the ECDH algorithm, which only requires the x coordinate. This allows implementing the scalar multiplication (in ecp_mul_mxz) using a ladder. In order to use the existing code for EdDSA, we would need to convert the Montgomery points into Edwards points. This means we need to recover the y Montgomery coordinate after the ladder, as it will define the x Edwards coordinate and we need to know its sign to differentiate between the two possible points. Such algorithm exists. They however requires to get access to the RP value in the ecp_mul_mxz function and to know the y coordinate of the Montgomery base point. The first requirement probably means that the recovery mechanism has to be implemented in the ecp_mul_mxz function, which will also impact the ECDH case in terms of code size and performance. The second requirement means that the ecp_get_type can't identify anymore the curve type based on the coordinate types. Anyway as discussed later below, this is an issue for implementing EdDSA.

I would welcome advises on that, however, I have also looked at implementing twisted Edwards curve support using explicit formulas. I have a basic implementation outside of mbedTLS, but still using mbedTLS functions as much as possible able to sign, that I have verified using the RFC test vectors. This implementation uses projective coordinates and uses the add-2008-bbjlp to implement point addition. I haven't implemented point doubling yet and instead reused the addition (there is no explicit formula for differential addition and doubling on EFD for the twisted Edwards curves), as I do not care about performances at this stage.

I have started to look at integrating the part of that code that would end up into ecp.c and ecp_curves.c at code, but I would need a few advises:

• As said above, after adding the twisted Edwards curve, we can't use the coordinate types to differentiate the curve type. One option is to explicitly test for grp->id in ecp_get_type, at least for the two twisted Edwards curves (ed25519 and ed448) to differentiate them from the short Weierstrass curves. The other option is to add a new member to struct mbedtls_ecp_group to represent the curve type.
• The mbedtls_ecp_keypair type and the related functions (mbedtls_ecp_gen_key, mbedtls_ecp_read_key, mbedtls_ecp_check_pub_priv) assume that the secret key is a scalar and that the public key is a curve point that is obtained by the scalar multiplication of the base point by the secret key. This is only partially true for the EdDSA algorithm, which employs point compression and SHA512 hashes to manipulate those. That said the private key can still be stored in a scalar, and the public key in an (uncompressed) point. Would that be an acceptable solution?
• Somehow related, the mbedtls_ecp_mul_restartable function first checks the scalar with mbedtls_ecp_check_privkey and the point with mbedtls_ecp_check_pubkey, and they are used differently in the EdDSA context. There are two scalar multiplications in the EdDSA signing algorithm, one to compute the public key, which has some bits set or cleared the same way than the Montgomery case. The other is used to multiply the SHA512 of the message and the right half part of the SHA512 of the private key. The scalar can take any value. I believe we should therefore make mbedtls_ecp_check_privkey to always pass for twisted Edwards curves. For mbedtls_ecp_check_pubkey, I believe we can just check that the point is on the curve. Does it sounds ok?

With answers to these questions, I guess I can move forward in implementing EdDSA support directly into MbedTLS, although I believe there are many more questions to come.

[aurel32]

In case it helps answering the questions, my current work is available there: https://github.com/aurel32/mbedtls/tree/eddsa

Note however that it is work in progress and thus this branch is frequently rebased.

[tqolf]

In case it helps answering the questions, my current work is available there: https://github.com/aurel32/mbedtls/tree/eddsa

Note however that it is work in progress and thus this branch is frequently rebased.

Thanks for you work. what about high-level APIs, e.g. ed25519_gen_keypair/ed25519_sign/ed25519_verify ?

Addtional, performance of your implementation based on mbedtls_mpi can do 500 ecp_mul/ED25519 per second in my machine, but implementation ported from SUPERCOP can reach 27000+ signs/s(with sha512 from mbedtls). Have you considered to do like this, since code size will not grow much.

[aurel32]

In case it helps answering the questions, my current work is available there: https://github.com/aurel32/mbedtls/tree/eddsa Note however that it is work in progress and thus this branch is frequently rebased.

Thanks for you work. what about high-level APIs, e.g. ed25519_gen_keypair/ed25519_sign/ed25519_verify ?

I have pieces of code able to sign, that said I can't implement merge them in MbedTLS until there is a decision what is exactly stored in the mbedtls_ecp_keypair struct, hence my questions above.

Addtional, performance of your implementation based on mbedtls_mpi can do 500 ecp_mul/ED25519 per second in my machine, but implementation ported from SUPERCOP can reach 27000+ signs/s(with sha512 from mbedtls). Have you considered to do like this, since code size will not grow much.

First of all I haven't done any optimization yet, my current goal is to have something that is correct and works. For example I haven't implemented point doubling yet. It's also possible to do inversion on Twisted Edwards cuves using x^-1 = x^(p-2) mod p, while I have simply been using mbedtls_mpi_inv_mod

The second point is that MbedTLS uses many blinding techniques to avoid leaks via side channel. In that specific case I have used the same randomizing technique as for the Montgomery curve implementation and that costs 2 inversions per ecp_mul. You can disable that by not passing a random generator to ecp_mul.

[yanesca]

Hi @aurel32,

Thank you very much for your work! We very much would like to have EdDSA in Mbed TLS and your contribution is much appreciated.

This is a relatively big contribution and we would like to make sure that both of your and our efforts result in successful integration of your code. The bigger the code, the bigger the risk that some unforeseen eventuality prevents us from completing the integration. Therefore I suggest that we don't handle this feature as a single PR, but break it up to more and integrate them one by one.

I suggest the following breakdown:

1. Edwards curve arithmetic
2. EdDSA signature algorithm
3. EdDSA support in TLS
4. ECDH Edwards representation (trading performance for code size)

Each of these would be a separate PR, and they would include extensive testing for the added functionality. We would start with the first one and a new PR would only be raised, after the previous has been merged.

This way, you could do as big a part of this effort as you wish and could contribute the maximum amount even if we fail to align our timelines at some later point.

Do you think you could raise a PR about the first part? It would facilitate conversation and make it easier to give initial feedback and design review. Rebases (force pushes) are Ok too as long as you give a heads up to the reviewers and post a link to a branch with the pre-rebase state.

You are asking very good questions and since they are related to the design of this new feature I think that it would be best to discuss them on the developer mailing list. Could you please write an email with your design questions to the list?

[yanesca]

Hi @vxfury

Thank you for your suggestion and thank you for taking interest in Mbed TLS!

Addtional, performance of your implementation based on mbedtls_mpi can do 500 ecp_mul/ED25519 per second in my machine, but implementation ported from SUPERCOP can reach 27000+ signs/s(with sha512 from mbedtls). Have you considered to do like this, since code size will not grow much.

Our ECC implementations are in general slower than the fastest available, for example the Everest Curve25519 is 20x faster than the Mbed TLS one (for now). As @aurel32 mentioned, one of the reasons for this is the coordinate blinding we use as a side channel attack countermeasure.

The other reason is that the Mbed TLS implementations share the Bignum module and don't have dedicated finite field arithmetic (NIST curves are optionally accelerated by optimised modular reduction, but still rely on Bignum code).

Because of this, there is not much difference in code size when comparing ECC primitives individually, but it shows when the application needs several of them. It is arguable if this does worth the performance penalty, but the current Mbed TLS philosophy is to take this trade-off.

Just to justify not being in a hurry to change this approach: Bignum itself leaves much room for optimisation even while retaining some level of universality. I think that making these optimisations would make performance comparable in environments where the blinding countermeasures are not necessary. Further enhancements to Bignum would reduce the use cases where blinding is necessary.

[aurel32]

Hi @aurel32,

Thank you very much for your work! We very much would like to have EdDSA in Mbed TLS and your contribution is much appreciated.

This is a relatively big contribution and we would like to make sure that both of your and our efforts result in successful integration of your code. The bigger the code, the bigger the risk that some unforeseen eventuality prevents us from completing the integration. Therefore I suggest that we don't handle this feature as a single PR, but break it up to more and integrate them one by one.

Yes, indeed that makes sense.

I suggest the following breakdown:

1. Edwards curve arithmetic

2. EdDSA signature algorithm

3. EdDSA support in TLS

4. ECDH Edwards representation (trading performance for code size)

Ok. I haven't necessary planned to work on point 3 and 4, but I guess I can have a look and/or someone can jump in to help.

Each of these would be a separate PR, and they would include extensive testing for the added functionality. We would start with the first one and a new PR would only be raised, after the previous has been merged.

This way, you could do as big a part of this effort as you wish and could contribute the maximum amount even if we fail to align our timelines at some later point.

Do you think you could raise a PR about the first part? It would facilitate conversation and make it easier to give initial feedback and design review. Rebases (force pushes) are Ok too as long as you give a heads up to the reviewers and post a link to a branch with the pre-rebase state.

Yes, I guess the Edwards curve arithmetic part is mostly ready. It mostly misses test vectors for ed448, I need to extract them from the RFC. I don't know if it is worth implementing point doubling at this point, it should not be very difficult. Also do you consider mbedtls_ecp_point_write_binary and mbedtls_ecp_point_read_binary as part of the arithmetic? I have only implemented the former. The point recovery part needed for the latter is a bit more tricky, but I already have a piece of code for ed25519.

I'll polish all of that this week-end and I'll send the PR.

You are asking very good questions and since they are related to the design of this new feature I think that it would be best to discuss them on the developer mailing list. Could you please write an email with your design questions to the list?

I wasn't aware of this mailing list, it looks relatively recent. I have just subscribed. My questions about the first PR concern ecp_get_type on one side and mbedtls_ecp_check_pubkey and mbedtls_ecp_check_privkey. I'll send them there once I have submitted the PR, I believe it would be easier to understand the question once there is a bit of code available.

[aurel32]

I don't know if it is worth implementing point doubling at this point, it should not be very difficult.

Don't worry about that, I just implemented it, it was pretty straightforward.

[yanesca]

Ok. I haven't necessary planned to work on point 3 and 4, but I guess I can have a look and/or someone can jump in to help.

I didn't mean to imply that we expect you to do all of these steps, I was just trying to provide a breakdown that is helpful whatever scope of contribution you have in mind. Point 1 and 2 are already a big undertaking and we are very grateful for your contribution!

Also do you consider mbedtls_ecp_point_write_binary and mbedtls_ecp_point_read_binary as part of the arithmetic? I have only implemented the former. The point recovery part needed for the latter is a bit more tricky, but I already have a piece of code for ed25519.

I think that it would make sense to implement plain non-compressed read and write for the sake of unit testing. I think the compressed point I/O could belong to either part I don't have strong opinions on that.

I'll polish all of that this week-end and I'll send the PR.

I'll send them there once I have submitted the PR, I believe it would be easier to understand the question once there is a bit of code available.

Thank you very much!

[aurel32]

I'll polish all of that this week-end and I'll send the PR.

I have just done that in PR #3245.

[nick-lifx]

This is cool. We currently use separate libraries for ordinary crypto (SSL and so on) and Ed25519, and we need to support Ed25519 as our cloud facing APIs depend on it in quite a few places. We are also trying to minimize code size as it is pretty tight for some of our products. So it will be extremely handy to have an Ed25519 implementation that reuses MbedTLS internals. For our use case we aren't as concerned with the specialised arithmetic version, we prefer as much code reuse as possible. So thanks for your hard work @aurel32 and of course the MbedTLS team. I look forward to integrating this in due course. If I get time I could try to help.

[532910]

I'm begging you, please don't forget about ED448 (:

[fire]

What can we do to prioritize this in the next sprint?

[yanesca]

Hi @fire,

@aurel32 has a PR up that is the first step toward this feature: https://github.com/ARMmbed/mbedtls/pull/3245

The review of this PR is on the roadmap for 21Q3: https://developer.trustedfirmware.org/w/mbed-tls/roadmap/

This will only provide the Edwards curve arithmetic, it will take a bit longer until a full EdDSA feature will be available.

What can we do to prioritize this in the next sprint?

I don't think there is anything we can do in this timeframe, but in general there might be a way to make this feature land somewhat faster: @aurel32 is already contributing the code, the only thing we are short on is review capacity. If you would like to help out and become an Mbed TLS reviewer, please let me know. (We don't have a well defined process for this yet and we would need to have a discussion about it. Also, this would involve reviewing all kinds of Mbed TLS PRs not necessarily only EdDSA related ones.)

[bkmgit]

It may be helpful to review https://github.com/novifinancial/ed25519-speccheck

[fire]

It is now February 2023. Can someone summarize what the state of this is?

[gilles-peskine-arm]

Unfortunately, we still haven't found a slot to review EdDSA in our roadmap. Review bandwidth has been our bottleneck for years and still is.

[awakecoding]

Hi, we are also looking into Ed25519 support as we migrate to mbedTLS 3.x, and it's kind of a bummer that it isn't already there. Any update on this?

[gilles-peskine-arm]

Unfortunately it's very unlikely that we can add EdDSA support before the second half of 2024. Please check our roadmap for updates.