Cortex-M4 backend?

[nickray]

There is a line of research implementing Curve25519 in constant time on Cortex-M4 microcontrollers by using multiply-and-accumulate instructions that this microcontroller has.
To my knowledge, this starts in [1], with an implementation [2] which unfortunately has LG copyrights. The latest I know of is [3], based on [5] and has no copyright restrictions.

While #187 blocks this, would there be interest in adding support for such a backend? Should this happen in this repository?

[1] http://www.cs.haifa.ac.il/~orrd/LC17/paper39.pdf
[2] https://github.com/hayatofujii/curve25519-cortex-m4
[3] https://github.com/BjoernMHaase/fe25519
[4] https://ches.2017.rump.cr.yp.to/fe534b32e52fcacee026786ff44235f0.pdf
[5] https://eprint.iacr.org/2018/286.pdf

[nickray]

Update from my side, I wrote a dedicated library for the Cortex-M4 and Cortex-M33 microcontroller use case, implementing Ed25519 signatures with this approach: https://docs.rs/salty. It's still in alpha release, not every possible optimization is applied, and testing is not sufficient yet.

I intend to add on X25519 agreement (with the same Haase field operations), and AEAD using RustCrypto libraries for the symmetric cryptography and hashes.

Once this reaches maturity, it may make sense to merge this as another backed into dalek, although from the embedded use case point of view, I feel having a smaller library and dependency surface has its merits too.

If one is not interested in these fast field operations, using ed25519-dalek still has the issue of the pre-computed lookup table, which at ~40k is quite large for many microcontrollers. Is it possible to deactivate these? On my side I may explore the space/speed tradeoff, I'm thinking about partial lookup tables.

[isislovecruft]

Hi @nickray! Thanks for writing up all of this. I've also been looking at easier/more modular ways to maintain dalek backends in #287.

Also, I would be happy to provide a more microcontroller-friendly mode to avoid lookup tables in ed25519-dalek, if the space/speed tradeoff is desirable.

[nickray]

Just being able to turn off the lookup tables with a feature flag would be great already.

I'm very sympathetic to the idea of a self-contained "field implementation" definition in terms of traits (even at risk of not overall optimal speed, as criticized in that linked issue - it's great for code comprehension to be able to read modular parts individually).

I originally wanted the curve in salty.rs to be generic over a field implementation with associated Limbs type (instead of selecting backends via feature flags), e.g. to fuzz two implementations against each other, or even just generate docs for both! In my case, "TweetNaCl" is supposed to be the "didactic" backend, vs. the speedy "Haase" with its assembly. However I got myself into a type pickle (https://users.rust-lang.org/t/how-can-i-use-generic-add-trait-in-generic-mul-trait/34652), this might just be my incompetence though :)

[hdevalence]

Adding a NEON field implementation sounds great. It has been inactive for about two years now, and it would be great if someone wants to do it. The best option would probably be to have a FieldElementNeon type using intrinsics and comments that prove correctness of the code. This repository seems like a great place to do that, if you would be interested. Of course, it makes sense to have a small, self-contained library aiming for a specific use-case, so that backend seems orthogonal to salty.

Regarding the tables, since they are defined in curve25519-dalek as consts, they should only appear in the binary if they're actually used. There are actually two tables that may be of concern: the tables for fast constant-time basepoint multiplication (256 points), and the tables for the variable-time double-scalar basepoint/variable-point multiplication used for, e.g., signature verification (64 points, used in double_scalar_mul). So I think that there are no changes required to curve25519-dalek to drop them, just a signature library that doesn't use the tables.

[tarcieri]

I'm using curve25519-dalek on a NEON-capable device (i.MX-6ULZ Cortex-A7) and may be interested in contributing a NEON backend.

[nickray]

OK well since it's close to Christmas and everyone has their wishes... :)

Future plans for salty (intended to stay focused on Cortex-M4/M33/M35P "on USB dongle with potential to be driven via NFC", vs NEON/Cortex-A/R where I think we ended up somehow) are to add backends for NXP LPC55 (definitely) using its CASPER peripheral, and (maybe, eventually) for nRF 5340 using its Arm CryptoCell (which likely more chips will have, eventually, vs the NXP-specific CASPER). And then there's Helium on the horizon, which is supposed to be Neon for Cortex-M. In short, it's a zoo out there in microcontroller land haha.

Maybe instead of maintaining all sorts of backends here it would be easier and more useful to the Rust crypto ecosystem to extract interfaces at various abstraction levels (from ed25519::PublicKey[::{verify_prehashed,...}] for users down to an eventual FieldImplementation for implementors or remixers), and put these traits in a separate crate (maybe under the RustCrypto umbrella?).

Because then a higher-level logic/library that has need for signature or key agreement could depend on those traits (high stability requirements) and a specific implementation crate (possibly Cortex-A and desktop here, Cortex-M in salty, RISC-V... somewhere?). Practically, at minimum this (for me) has use for testing the higher-level logic (e.g. think of a PIV-like "app") on desktop instead of on device. Of course that is Christmassy wishful thinking, I can also stub things out or maintain parallel/modified APIs in salty.

[nickray]

Oh hmm that's dalek-cryptography/ed25519-dalek#80 I guess.