search

RustCrypto / RSA

RSA implementation in pure Rust
Apache License 2.0
536 stars 148 forks source link

[WIP]: switch to crypto-bigint for decryption #394

Open dignifiedquire opened 9 months ago

dignifiedquire commented 9 months ago

Very, very WIP

Uncomplete, unordered task list

Tests

tarcieri commented 8 months ago

@dignifiedquire FYI: https://docs.rs/crypto-primes/0.6.0-pre.0/crypto_primes/

bradjc commented 8 months ago

Is there any plan to support the Uint non-alloc type?

tarcieri commented 8 months ago

@bradjc it should be possible in the future (see #51) and crypto-primes has been updated to support both with generic algorithms.

However, it will be difficult, so a first pass should probably focus on getting a heap-allocated implementation working.

nicolasauler commented 8 months ago

Is there work still happening here or is this issue blocked? How can the community help? My pipelines are still breaking in the security audit due to the Marvin Attack vuln

tarcieri commented 8 months ago

I can potentially pick up this PR or https://github.com/RustCrypto/crypto-bigint/pull/403

How can the community help?

@nicolasauler I haven't had time to check out #400 yet, but if you'd like to confirm it's working as expected that would be helpful. It implements the tooling for the attack and so far we've managed to confirm that while this PR is an improvement it doesn't seem to entirely close the sidechannel.

My pipelines are still breaking in the security audit due to the Marvin Attack vuln

You should be able to ignore RUSTSEC-2023-0071 in e.g. .cargo/audit.toml for now (provided you're using cargo-audit).

But yes, we're in the same boat where several of the @RustCrypto repos are currently labeled "insecure" due to this vulnerability.

bradjc commented 7 months ago

Is it reasonable to say the implementation is fairly close, and that the remaining items would only result in minor fixes?

tarcieri commented 7 months ago

I can potentially pick up this branch if @dignifiedquire is too busy. It looks like there's still a decent number of things to do, though the tests appear to be broken due to a [patch.crates-io] directive pointing at the local filesystem

dignifiedquire commented 7 months ago

though the tests appear to be broken due to a [patch.crates-io] directive pointing at the local filesystem

this is just pointing at this branch on my machine: https://github.com/RustCrypto/crypto-bigint/tree/feat-expand-mul

dignifiedquire commented 7 months ago

The big changes needed to make this performant enough, is the work I started to allow different width of bigints to be operated on, as we are currently wasting a lot of time in operating on much larger values than we need to. Everything else is mostly done.

So any help with that on the cryptobigint front would be appreciated.

tarcieri commented 7 months ago

@dignifiedquire perhaps we should get an initial working implementation landed then follow up on performance separately?

dignifiedquire commented 7 months ago

@dignifiedquire perhaps we should get an initial working implementation landed then follow up on performance separately?

We could, but performance of this crate is already not great, and it goes down by at least a factor of 2 :(

tarcieri commented 7 months ago

Better than a sidechannel vulnerability that leaks the private key!

MasterAwesome commented 6 months ago

@bradjc it should be possible in the future (see #51) and crypto-primes has been updated to support both with generic algorithms.

However, it will be difficult, so a first pass should probably focus on getting a heap-allocated implementation working.

Is there work required in any of the dependencies that are blocking non-alloc types from being used? If there is, I can try a stab at it parallelly.

dignifiedquire commented 6 months ago

@tarcieri you are right, I will try and pull out the version that worked for a first release

tarcieri commented 6 months ago

@MasterAwesome the dependencies are largely ready to go, including crypto-primes.

The hard part will be making the implementation of rsa generic around the underlying integer type, and that's something we can't really even begin to explore until we have it fully migrated to crypto-bigint in any capacity.

tarcieri commented 6 months ago

@MasterAwesome in terms of something that would generally help with the migration, there are various avenues for crypto-bigint performance improvements to be explored: https://github.com/RustCrypto/crypto-bigint/pull/403

dignifiedquire commented 5 months ago

Update:

done

next steps

dignifiedquire commented 5 months ago

Almost all tests are broken, but num-bigint is not used anymore, all code is moved to crypto-bigint now

pinkforest commented 5 months ago

Fixing for sede De/Serialize for BoxedUint - some TODO left there

Also serde(skip) needs a default as it's not Option<> n_params

The rest seems to be test data input migration - the previous had some str radix parse and be needs exact length

dignifiedquire commented 2 months ago

Most tests are passing at this point, outstanding failures seem to fall into two categories

tarcieri commented 1 month ago

@dignifiedquire I think it'd be good to land a spike / PoC of this even if all the algorithms aren't yet implemented, since it would unblock splitting up the work on (re)implementing those

gogo2464 commented 1 month ago

@tarcieri can I be assigned to the poc please? I would like to gain experience.

EDIT: I did not undertand the message yet. If the exploit is already made, yes I can read it. Just do not reinvent the whell. I was already working on.

EDIT2: Can you just provide me as much tools as possible please? I am currenyly reading the doc of marvin-tool

gogo2464 commented 1 month ago

I can see difference but I would like a tool or a procedure to analyze the time spent. I am currently working with callgrind and kcachegrind.

dignifiedquire commented 1 month ago

@tarcieri most things are working now 🎉

I would appreciate some help with debugging the last failures, seems the proptests are discovering some roundtrip issues in the encoding/decoding and the last regular test that is a problem is dealign with a 2049bit key

dignifiedquire commented 1 month ago

and also feel free to start to review the code/fix up anything you think needs improving

kjvalencik commented 3 weeks ago

This is awesome! I'm excited to see this PR progressing so much.

seems the proptests are discovering some roundtrip issues in the encoding/decoding and the last regular test that is a problem is dealign with a 2049bit key

I looked into this for a few minutes and these two appear to be different cases of the same problem. crypto-bigint uses 64-bit limbs, which requires it to round higher on number of bytes. For example, with a 2049-bit key it's 264 instead of 257; leading to more padding in the serialized version. This may be the same thing causing round-trip problems.