[RFC] RSA lib integration

[alt3r-3go]

This is an "request for comments"-type PR to invite a discussion and iron out the details of the RSA library integration.

Context

We've discussed this with the Nitrokey team a while ago (around the end of 2021) and I took a stab at it, then it got paused for several months after this discussion we additionally had with @nickray. Recently @daringer suggested we move ahead anyway, probably in a form of an NK-specific temporary fork, while those TIPs are getting written/implemented. AFAIU this is driven by the desire to have an RSA implementation for NK3, so at least some working solution is valued higher than the ideal one we discussed in that Matrix chat.

Implemented now

RSA2K-PKCS_v1.5 signing/verification and the whole necessary set of helper traits (DeriveKey, etc) + tests for them, that work on a PC. I separately was able to run Trussed and the RSA lib's full set of tests on my nRF52832, but haven't yet tried both of them at once.

Caveats

The PR is still well WIP and has items to discuss (marked as TODO:alt3r-3go in the code). I've based the general approach on the miracl one (#12) and that proved to be quite useful, so kudos to @nickray for such a nice example. Due to one of the TODOs related to the test infra, tests need to be run one by one for now, at the bottom of this description I'm showing a simple script that can be used for that. I haven't included it into the code, but let me know if it's helpful until I close the TODO.

All comments, big and small, as well as suggestions on the TODOs are more than welcome.

Testing script

#!/bin/bash

set -e
set -x

clear && RUST_BACKTRACE=1 cargo test --test rsa2kpkcs rsa2kpkcs_sign_verify -- --nocapture --show-output
RUST_BACKTRACE=1 cargo test --test rsa2kpkcs rsa2kpkcs_generate -- --nocapture --show-output
RUST_BACKTRACE=1 cargo test --test rsa2kpkcs rsa2kpkcs_derive -- --nocapture --show-output
RUST_BACKTRACE=1 cargo test --test rsa2kpkcs rsa2kpkcs_exists -- --nocapture --show-output
RUST_BACKTRACE=1 cargo test --test rsa2kpkcs rsa2kpkcs_serialize -- --nocapture --show-output
RUST_BACKTRACE=1 cargo test --test rsa2kpkcs rsa2kpkcs_deserialize -- --nocapture --show-output
RUST_BACKTRACE=1 cargo test --test rsa2kpkcs rsa2kpkcs_sign_verify -- --nocapture --show-output

[robin-nitrokey]

Thank you for the PR! I did not have a closer look yet but I just want to give you a heads-up that we are already working on a solution for the test issue.

[szszszsz]

@alt3r-3go Hey! I plan to take a look at it this week

[robin-nitrokey]

@alt3r-3go https://github.com/trussed-dev/trussed/pull/31 refactors the client used for the tests and should allow you to execute them normally with cargo test --features virt.

[daringer]

Hey @alt3r-3go,

great work, I will answer (hopefully all) of your TODOs here to have it in one place.

• let's first stick (implementation-wise) to rsa2k only

• generally cfg-feature granularity: I would suggest to have exactly 3 features for RSA: rsa2k, rsa3k and rsa4k

• don't worry about the magic numbers for now, config.rs anyways (as this comment implies) lacks a proper magic-number-management-mechanism

• using this configured numbers for KeyStore is perfectly fine for now - later this would need a compile-time constant (see magic-number-management-mechanism)

• essentially the same argument for signature length, funny though that p256::Verify does not check signature length at all and ed255 does it based on a constant from salty - under the line: this is fine for now

• serialization is perfectly fine with Raw only for now, keep it simple, as long as nothing forces us towards der or asn1der we stay with raw, which anyways implies pkcs#8-der (right?)

• skip sign_blinded for now, to keep it simple (from here)

• rsa takes a hash instead of raw data, this makes it a "prehased" algortihm, thus we should stick to how p256prehashed does it: request.message directly contains the hash.

• sign & verify i.e. the PSS vs. PKCS padding story: p256 also implements two different variants for sign, so RSA should do the same. This means we will have something like rsa2k as feature and then something like:

pub struct rsa2k {}
pub struct rsa2kpss {}
mod rsa2k;

// and then

impl Sign for super::rsa2k {}
impl Sign for super::rsa2kpss {}

impl Verify for super::rsa2k {}
impl Verify for super::rsa2kpss {}

But again: keep it simple and stick to rsa2k (pkcs) first...

Sooo, hope this answers the questions.

Rebasing on top of main also allowed me to run all the tests at once: (thx @robin-nitrokey )

RUST_BACKTRACE=1 cargo test --test rsa2kpkcs --features virt -- --nocapture --show-output

This is really nice! Feels like nearly all of the heavy lifting stuff is done, despite the smaller changes described above (ok ignoring 3k, 4k - but that's totally fine for now). We anyways won't be able to upstream this until RSACrypto / RSA will have proper no_std support (which I cannot fully oversee what is missing at this point)

[alt3r-3go]

Thanks @daringer, that makes a lot of sense and is certainly helpful. I've rebased to the latest main (tests indeed now work with virt, yay! :slightly_smiling_face:) and added a commit that updates the code in accordance with those comments. In a separate commit for readability, will of course be squashed when we're done with the discussion.

[...] we stay with raw, which anyways implies pkcs#8-der (right?)

Other existing ones seem to store pure bytes when using Raw, however as those appropriate enum values are commented out anyway (and the rest simply doesn't fit, like e.g. Cose) we can probably get by for now by treating Raw as "whatever the serialize/deserialize implementation is assuming" and inside those functions I have comments as to the specific format for any future reworks.

[...] until RSACrypto / RSA will have proper no_std support (which I cannot fully oversee what is missing at this point)

As of ~6 months ago, when I actively tested this, it actually was running fine with no_std - I created a small test program for my nRF82532, which essentially included library's PKCS1 and 8 decoding tests, wrapped into proper incantations to run on nRF, and it worked just fine. It did require alloc (is removal of that was what you meant by "proper" here?) and an appropriate allocator implementation though, and alloc-cortex-m worked fine. I'm out of time today to update my test program to try the newer 0.6.1 library version, but I think that (i.e moving to the microcontroller target from PC) would anyway be the next step for this integration, so we'll know soon enough.

[sosthene-nitrokey]

I've rebased it on top of 8e347abf99dba81fca11c5779a473d263a7b0565 in sosthene-nitrokey:rsa-lib-integration-fmt

[szszszsz]

Hey @alt3r-3go ! Is there any chance you would have time to look into this PR again this week?

[alt3r-3go]

@szszszsz I probably could, but what exactly do you have in mind in terms of actions required? It seems to me it's ready to be merged into whatever place we'd designate for this, as per our past discussions, maybe based on the rebased branch that @sosthene-nitrokey mentioned. Are you maybe talking about namely that cargo-fmt commit and rebasing this PR specifically onto it?

[sosthene-nitrokey]

I mean't this PR should be reset to my https://github.com/sosthene-nitrokey/trussed/tree/rsa-lib-integration-fmt branch to resolve merge conflicts.

Sorry it took me so much time to respond, I missed the notification

[sosthene-nitrokey]

I'm not sure what is the best way to serialize public keys. For example the OpenPGP smartcard specification uses it's own serialization format, and to build it we need both e and n separately. I think we should try to avoid having to de-serialize it in the client app.

Maybe we could have two additional serialization formats RsaN and RsaE to get each individualy ? This seems ugly.

[szszszsz]

Hey @sosthene-nitrokey @alt3r-3go ! Just FYI, I've added public key serialization and decryption support below (based on @sosthene-nitrokey 's fork). How to proceed to integrate? I can make a PR to this PR in a few days (feel free to do it earlier if you need it):

• https://github.com/trussed-dev/trussed/compare/6f4b547fe710058033efbb9090bcf5649c7a0494...Nitrokey:trussed:webcrypt-devel-rsa

Edit: @alt3r-3go : Sorry for the delay. Had hot month. I just thought something is still pending to do. Good to hear it's more or less finished! It works for my use case in Nitrokey WebCrypt as well.

[sosthene-nitrokey]

I'm aiso working on a modified branch on top of #51: here

[alt3r-3go]

I'll look into and address specific comments later, but overall it looks like this needs to be merged somewhere, as more and more further changes start to pile up on top. I will rebase this on top of @sosthene-nitrokey's cargo-fmt branch, but let's also define where we want to merge this. One option we discussed before was an NK-owned Trussed fork, at least until mechanisms are in place to address @nickray's concerns cleanly. @daringer (or whoever is the right person to decide?), do you maybe want to create one? If not, how do you folks think we should move forward?

[szszszsz]

@sosthene-nitrokey @daringer @robin-nitrokey We should discuss this tomorrow

[sosthene-nitrokey]

Ok, so we talked about where we are going to go with this PR.

We're going have a version off this PR on the Nitrokey repo here. I already added some fixes that I needed for the OpenPGP card implementation.

With regard to serialization:

Since both OpenPGP and the SE050 secure element use a similar BER-TLV format [^1], we are going to use it for (de)serialization of RSA Key (with an added KeySerialization variant).

In case their is a need for Pkcs (de)serialization, we should keep it with an added KeySerialization variant.

[^1]: For OpenPGP see page 75 and 38, for the SE050, see 4.7.1.2 WriteRSAKey and table 105 (for reading public keys it appears that the SE050 does it similarly with to what I do with 2 commands for reading N and E.

[alt3r-3go]

Good! I see you've already fixed in that new PR the comments posted in this PR. Let me know if you need any further action from me. I also think we can close this PR and continue in the NK repo one - let me know if there are any objections.

[alt3r-3go]

Now that we've got the right place for this PR, let me close it. We can continue in that NK repo if/when needed, please just @-mention me, so that I don't miss the notification.