[WIP]: switch to crypto-bigint for decryption

[dignifiedquire]

Very, very WIP

Uncomplete, unordered task list

• [x] switch internal storage for RsaPrivateKey
• [x] switch internal storage for RsaPublicKey
• [x] switch all code to use the new decrypt implementation
• [x] update public traits using BigUint to return owned versions
• [x] fix blinding implementation
• [x] switch decryption algorithm with precompute to use crypto-bigint ops
• [x] go through other algorithms and update what can be done without having primality checks implemented
• [ ] review & update code for constant time operation
• [ ] review & update code for performance
• [ ] benchmarks

Tests

• [x] algorithms::pad::tests::test_left_pad
• [x] algorithms::pkcs1v15::tests::test_non_zero_bytes
• [x] algorithms::rsa::tests::recover_primes_works
• [x] key::tests::build_key_from_p_q
• [x] key::tests::build_key_from_primes
• [x] key::tests::invalid_coeff_private_key_regression
• [x] algorithms::generate::tests::key_generation_128
• [x] key::tests::key_generation_128
• [x] algorithms::generate::tests::test_impossible_keys
• [x] algorithms::generate::tests::key_generation_multi_3_256
• [x] algorithms::generate::tests::key_generation_multi_4_64
• [x] key::tests::key_generation_multi_4_64
• [x] key::tests::reject_oversized_private_key
• [x] key::tests::test_from_into
• [x] key::tests::key_generation_multi_3_256
• [x] key::tests::test_serde
• [x] oaep::decrypting_key::tests::test_serde
• [x] oaep::encrypting_key::tests::test_serde
• [x] oaep::tests::test_decrypt_oaep_invalid_hash
• [x] oaep::tests::test_decrypt_oaep_invalid_hash_traits
• [x] oaep::tests::test_encrypt_decrypt_oaep
• [x] oaep::tests::test_encrypt_decrypt_oaep_traits
• [x] pkcs1v15::decrypting_key::tests::test_serde
• [x] pkcs1v15::encrypting_key::tests::test_serde
• [x] pkcs1v15::signature::tests::test_serde
• [x] pkcs1v15::signing_key::tests::test_serde
• [x] pkcs1v15::tests::test_decrypt_pkcs1v15
• [x] pkcs1v15::tests::test_decrypt_pkcs1v15_traits
• [x] pkcs1v15::tests::test_encrypt_decrypt_pkcs1v15
• [x] pkcs1v15::tests::test_encrypt_decrypt_pkcs1v15_traits
• [x] pkcs1v15::tests::test_sign_pkcs1v15
• [x] pkcs1v15::tests::test_sign_pkcs1v15_digest_signer
• [x] pkcs1v15::tests::test_sign_pkcs1v15_signer
• [x] pkcs1v15::tests::test_sign_pkcs1v15_signer_sha2_256
• [x] pkcs1v15::tests::test_sign_pkcs1v15_signer_sha3_256
• [x] pkcs1v15::tests::test_unpadded_signature
• [x] pkcs1v15::tests::test_unpadded_signature_hazmat
• [x] pkcs1v15::tests::test_verify_pkcs1v15
• [x] pkcs1v15::tests::test_verify_pkcs1v15_digest_signer
• [x] pkcs1v15::tests::test_verify_pkcs1v15_signer
• [x] pkcs1v15::verifying_key::tests::test_serde
• [x] pss::blinded_signing_key::tests::test_serde
• [x] pss::signature::tests::test_serde
• [x] pss::signing_key::tests::test_serde
• [x] algorithms::generate::tests::key_generation_1024
• [x] pss::test::test_sign_and_verify_pss_blinded_hazmat
• [x] pss::test::test_sign_and_verify_pss_hazmat
• [x] pss::test::test_sign_and_verify_roundtrip
• [x] pss::test::test_sign_and_verify_roundtrip_blinded_digest_signer
• [x] pss::test::test_sign_and_verify_roundtrip_blinded_signer
• [x] pss::test::test_sign_and_verify_roundtrip_digest_signer
• [x] pss::test::test_sign_and_verify_roundtrip_signer
• [x] pss::test::test_sign_blinded_and_verify_roundtrip
• [x] pss::test::test_verify_pss
• [x] pss::test::test_verify_pss_digest_signer
• [x] pss::test::test_verify_pss_hazmat
• [x] pss::test::test_verify_pss_signer
• [x] algorithms::generate::tests::key_generation_multi_5_64
• [x] pss::verifying_key::tests::test_serde
• [x] key::tests::test_negative_decryption_value
• [x] key::tests::key_generation_multi_5_64
• [ ] pss::test::test_sign_and_verify_2049bit_key
• [x] key::tests::key_generation_1024
• [x] algorithms::generate::tests::key_generation_multi_8_576
• [x] key::tests::key_generation_multi_8_576

[tarcieri]

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

[bradjc]

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

[tarcieri]

@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]

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]

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]

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

[tarcieri]

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]

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]

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]

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

[dignifiedquire]

@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]

Better than a sidechannel vulnerability that leaks the private key!

[MasterAwesome]

@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]

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

[tarcieri]

@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]

@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]

Update:

done

• merged latest master
• switched back to fixed sizes
• updated to crpyto-bigint alpha.12

next steps

• figure out why 3 tests are failing
• integrate prime number generation

[dignifiedquire]

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

[pinkforest]

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

• https://github.com/RustCrypto/crypto-bigint/pull/587

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

• https://github.com/RustCrypto/RSA/pull/425

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