Improved pure-Rust cryptographic implementations

[tarcieri]

Hello! I'm one of the leads of https://github.com/RustCrypto

First let me start by saying I've read this:

We're currently still in the process on making the ARM® CryptoCell-310 embedded in the Nordic nRF52840 chip work to get hardware-accelerated cryptography. In the meantime we implemented the required cryptography algorithms (ECDSA, ECC secp256r1, HMAC-SHA256 and AES256) in Rust as a placeholder. Those implementations are research-quality code and haven't been reviewed. They don't provide constant-time guarantees and are not designed to be resistant against side-channel attacks.

I am also chasing down a security reference manual for a different chip from a different vendor and encountering bugs in their web site so I totally get it.

All that said, I'm wondering if you'd consider using some slightly better implementations of various algorithms than you are currently using. I was eyeing things like this in particular:

https://github.com/google/OpenSK/blob/f91d2fd/libraries/crypto/src/aes256.rs#L108

I'm aware table-based lookups in SBoxes are less of a sidechannel issue on this chipset owing to what I believe is an absence of data cache, but perhaps it'd generally be better to provide a bitsliced version anyway unless you have reasons not to do so.

I just wanted to note there's one available in the aes-soft crate, which may not be the most performant one in the world but is at least Apache 2.0+MIT licensed:

https://github.com/RustCrypto/block-ciphers/blob/master/aes/aes-soft/src/bitslice.rs

If you're amenable to this kind of thing, we would love to collaborate on high-quality pure Rust cryptography implementations, particularly ones with a focus on embedded targets, and where there are gaps in Rust as a language today for these purposes, we're also working on addressing them and would love to collaborate on that too.

Anyway, this is a very interesting project and I'm sure you're looking forward to getting the CryptoCell going!

[roycewilliams]

I know that the stated purpose of the Rust implementations is to be placeholders - but with an eye towards future multi-platform support, keeping the soft implementations available for porting to platforms with different onboard crypto hardware might have longer-term value as well.

[gendx]

Hello, thanks for the heads up!

The current AES implementation is definitely just a textbook placeholder (although with comprehensive correctness unit tests), and aes-soft sounds like it could be a good replacement (provided it compiles fine and that performance & code size are reasonable for our use case). I have a few questions (e.g. unit tests) but better ask directly on the corresponding repository.

If I understood correctly, ECDSA was also implemented recently (so we didn't have it under the radar). Is it still under development or also reaching some usable state?

We also had a look at https://github.com/dalek-cryptography, which implements some crypto algorithms in pure Rust (our placeholders use subtle for comparisons), but unfortunately there was no support for P-256 which is mandated by the FIDO2 specs (hence our re-implementation of ECDSA).

In general, I'm glad to see that RustCrypto is getting traction as a wide collection of crypto algorithms. It seems that quite a bit of algorithms have been added in the past months :) For embedded use cases at least, it definitely makes sense to focus efforts on one set of high-quality implementations that are easy to compile (self-contained, pure-Rust), with comprehensive testing (leveraging Rust's easy-to-use #[test]), best-effort constant-time (up to whatever the Rust compiler can guarantee) and eventually audited / vetted by the community.

Speaking of which, in terms of governance, is the RustCrypto project in any way affiliated to (or in scope of) the Rust Secure Code Working Group (or are there any plans towards it once the implementation is mature enough)?

[tarcieri]

Glad to hear it! Some specific responses:

If I understood correctly, ECDSA was also implemented recently (so we didn't have it under the radar). Is it still under development or also reaching some usable state?

That repository doesn't contain an implementation of ECDSA yet, and only provides reusable signature and key types which are generic over elliptic curves.

I've definitely been considering adding an ECDSA implementation (generic over Weierstrass curves), especially as the p256 crate now includes a field arithmetic implementation (contributed by @str4d), but is something I haven't gotten around to yet.

Speaking of which, in terms of governance, is the RustCrypto project in any way affiliated to (or in scope of) the Rust Secure Code Working Group (or are there any plans towards it once the implementation is mature enough)?

I'm one of the leads of the Secure Code WG, but beyond that there's no specific direct affiliation between the two. There is, however, an open application for a Cryptography WG.

[gendx]

Thanks for the clarification on ECDSA.

Indeed a Cryptography WG would be relevant to coordinate these efforts, looking forward to having one started!

[tarcieri]

FYI, we now have a (newly implemented and at this point low-level) ECDSA/P-256 on top of some fairly nice and modern pure-Rust curve arithmetic (complete Weierstrass formulas based on projective arithmetic):

https://github.com/RustCrypto/elliptic-curves/pull/84/files

Notably it provides you the choice of using constant time inversions or a faster variable-time inversion with random blinding as a alternative method for accelerating the implementation on embedded targets.

I’d call the ECDSA implementation “bleeding edge” at this point but we do hope to both get more eyes on it and improve testing quality relatively soon, as well as implementing things like RFC6979 and extensions to it which incorporate added randomness to mitigate fault attacks.

[gendx]

Thanks for the heads up!

I’d call the ECDSA implementation “bleeding edge” at this point but we do hope to both get more eyes on it and improve testing quality relatively soon, as well as implementing things like RFC6979 and extensions to it which incorporate added randomness to mitigate fault attacks.

Having a brief look, I agree that there could be more testing.

We took care to have extensive testing in the current OpenSK implementation, for example:

• Test vectors, notably with Wycheproof (though we could add more as well of course).
• Unit tests for basically all arithmetic operations. Half of the lines of code in this folder are unit tests (example), and we could still add some more. Maybe a lot of these tests (e.g. associativity, commutativity, etc.) are redundant with end-to-end test vectors, but on the other hand unit tests are not expensive to setup in Rust, so there isn't a reason not to have them either.
• There are also some edge cases for e.g. point validation.

Even with that, I think we could still add even more tests to cover more edge cases, so it's still "research quality" code.

[bunnie]

Just dropping a note here -- over at Xous, we vendored in the OpenSK code and refactored the crypto crate to use the RustCrypto implementations (including the tests, which also includes the Wycheproof suite).

Xous is different enough from Tock that I don't think it makes sense to try any sort of pull request, but in case anybody is interested in trying out OpenSK with the RustCrypto versions of all the ciphers, you might want to have a look around this crate for some hints on how to do it:

https://github.com/betrusted-io/xous-core/tree/main/apps/vault/libraries/crypto

[kaczmarczyck]

Thanks for the notice! Are there commits before and after crypto migration? I'd be interested in binary size.

[bunnie]

Ah, that's a good question. Actually, we never tried it using the native libraries. I just gave it a whirl to see if it'd compile swapping your original libraries back in and fixing up some dependencies -- and it looks like some nightly features are required, which we don't support in our OS as we run on stable only.

So the short answer is no, we never built OpenSK for our platform using your version of the cryptography libraries. I think the size comparison might not be fair anyways, because we have hardware accelerators for AES and SHA2 which we shim over the RustCrypto standard APIs (you can toggle the hardware acceleration on or off by either selecting our crate or the standard crate).

This is the size of our final "app" based on OpenSK though, which includes some UI/UX functions and USB routines, and a whole bunch of debug still:

27    IniE: entrypoint @ 00087146, loaded from 005cfd4c.  Sections:
        Loaded from 005cfd4c - Section .rodata: 54264 bytes loading @ 00010100 flags: NONE
        Loaded from 005dd144 - Section .eh_frame_hdr: 2100 bytes loading @ 0001d4f8 flags: NONE
        Loaded from 005dd978 - Section .eh_frame: 7204 bytes loading @ 0001dd2c flags: NONE
        Loaded from 005df59c - Section .text: 445788 bytes loading @ 00020950 flags: EXECUTE
        Loaded from 0064c2f8 - Section .sdata: 68 bytes loading @ 0008e6b0 flags: WRITE
        Loaded from 0064c33c - Section .sbss: 92 bytes loading @ 0008e6f4 flags: WRITE | NOCOPY
        Loaded from 0064c398 - Section .bss: 452 bytes loading @ 0008e750 flags: WRITE | NOCOPY

This is for a riscv32imac target. I'd guess about...150-180k of the .text is OS overhead, so the actual size of the OpenSK code is around 280-ish kiB.

[kaczmarczyck]

I that case, that's hard to compare. At some point in the future, we will peek at hardware crypto and then also take a closer look at other libraries. Thanks!

[tarcieri]

@bunnie sidebar, but I'm curious how the traits are working for you in the context of a cryptographic accelerator.

We've been interested in looking at alternative designs for embedded devices which would enable parallel pipelining between a cryptographic accelerator and a general-purpose MCU, for the purposes of doing things like encryption and authentication in parallel.

This issue discusses potentially using async for this purpose (i.e. interrupt handling for cryptographic accelerator completion events), although that's just one potential design: RustCrypto/traits#304

[tarcieri]

Re: code size, I hope p256 and p384 are relatively small compared to other implementations. We don't yet leverage large constants like basepoint tables, although when we do, we'll make sure to feature gate them so embedded implementations can shut them off for code size savings

[bunnie]

I that case, that's hard to compare. At some point in the future, we will peek at hardware crypto and then also take a closer look at other libraries. Thanks!

Maybe this nm dump could be somewhat helpful:

00050d5a 0000b9f6 t vault::ux::start_ux_thread::{{closure}}
0002dc6a 00007ac8 t vault::ctap::CtapState<R,CheckUserPresence>::process_command
00073c92 000079e6 t <p256::arithmetic::projective::ProjectivePoint as core::ops::arith::Mul<&p256::arithmetic::scalar::Scalar>>::mul
00026d52 00005fc0 t vault::main::{{closure}}
000827ce 000033e6 t sha2::sha256::compress256
000368ec 000032fe t ctap_crypto::ecdsa::SecKey::sign_rfc6979
00067988 00003114 t elliptic_curve::public_key::PublicKey<C>::from_sec1_bytes
00046426 000029e0 t vault::ctap::response::<impl core::convert::From<vault::ctap::response::ResponseData> for core::option::Option<cbor::values::Value>>::from
0005fa2c 000015bc t cbor::reader::Reader::decode_complete_data_item
0007b678 00001598 t p256::arithmetic::scalar::Scalar::mul
000255f0 0000152e t vault::main
00042a94 00000eaa t vault::ctap::CtapState<R,CheckUserPresence>::assertion_response
00087414 00000dd2 t dlmalloc_xous::dlmalloc::Dlmalloc<A>::malloc
000727c4 00000c9e t p256::arithmetic::field::FieldElement::mul
0008078a 00000bdc t pddb::Pddb::list_keys
0002cd12 00000bd2 t vault::ctap::storage::PersistentStore::init
0004c3c2 00000bc8 t vault::ctap::storage::deserialize_credential
00040e4a 00000b72 t alloc::collections::btree::map::BTreeMap<K,V>::insert
0006c804 00000b72 t alloc::collections::btree::map::BTreeMap<K,V>::insert
0005d6cc 00000b2a t aes::vex::aes256::set_encrypt_key_inner_256
0003a8dc 00000ae0 t pddb::Pddb::get
0005e1f6 00000a30 t aes::vex::aes256::aes256_dec_key_schedule
00061870 000009d8 t cbor::writer::Writer::encode_cbor
00048e06 000009c0 t <T as core::convert::Into<U>>::into
0004a328 000008a8 t <alloc::collections::btree::map::BTreeMap<K,V> as core::clone::Clone>::clone::clone_subtree
0004393e 000008a8 t alloc::collections::btree::map::BTreeMap<K,V>::insert
000704ae 000008a4 t gam::Gam::register_ux
00066ed4 00000832 t ctap_crypto::cbc::cbc_decrypt
00066530 0000080e t ctap_crypto::cbc::cbc_encrypt
00035732 00000800 t vault::ux::request_permission_inner
0004bb00 000007c2 t core::slice::sort::partition
0006b9ec 00000752 t ctap_crypto::ecdsa::Signature::to_asn1_der
000403a6 00000740 t vault::ctap::storage::PersistentStore::store_credential
0006f096 000006e2 t xous_ipc::buffer::Buffer::to_original
000419bc 000006e2 t vault::ctap::storage::PersistentStore::filter_credential
0004f8d4 000006dc t <core::iter::adapters::GenericShunt<I,R> as core::iter::traits::iterator::Iterator>::next
0004209e 000006ac t core::slice::sort::recurse
0006b2fc 000006a6 t ctap_crypto::ecdsa::SecKey::from_bytes
0008bc08 00000684 t std::panicking::rust_panic_with_hook
0007215e 00000666 t p256::arithmetic::field::FieldElement::to_bytes

It gives a hint at least as to the rough size of the "big" functions.

[kaczmarczyck]

If I read this correctly, the numbers are still hard to compare. For example, our decode_complete_data_item only takes 1.2KiB in cargo bloat. This is probably because we compile with opt-level = "z" and other rustc flags to optimize binary size. The real test is to replace the crypto libraries inside OpenSK it seems.

[bunnie]

@bunnie sidebar, but I'm curious how the traits are working for you in the context of a cryptographic accelerator.

We've been interested in looking at alternative designs for embedded devices which would enable parallel pipelining between a cryptographic accelerator and a general-purpose MCU, for the purposes of doing things like encryption and authentication in parallel.

This issue discusses potentially using async for this purpose (i.e. interrupt handling for cryptographic accelerator completion events), although that's just one potential design: RustCrypto/traits#304

Looking over at the issue...it looks like the question is how do you get your CPU to do something while the crypto runs, especially in an accelerator.

I think the short answer is, generally I've only found marginal benefit in adding the async overhead to a single primitive, and so we have lived comfortably within the existing blocking traits. This is for two reasons:

1. In many cases the cryptographic routines consume "most" of the compute time (even when hardware accelerated), and the result of the computation blocks any downstream interaction. So in the case you can do a little bit more with a callback on completion, but in the big picture the higher-level flow is blocking until you have a result from the cryptographic operation anyways. So, in the end, the async primitives just add overhead waiting for the thing you're already waiting on.
2. Additional context: our OS is fully multithreaded and has process isolation via virtual memory. So our UX does not block while we wait for a big digital signature check to run, for example -- the pre-emptive thread scheduler will ensure that the UX thread gets a time slice while the driver does the busy-wait on the completion of a big hash, for example. So we don't need fine-grained cooperative multi-tasking between our cryptographic operations and non-dependent operations such as UX state.

The downside of our cooperative multitasking is that the cost of message passing overhead is non-zero. Here's a benchmark example:

TEST_MAX_LEN = 256 (random length) / TEST_ITERS = 1000: hw 6.968ms/hash, sw 3.987ms/hash
TEST_MAX_LEN = 512 (random length) / TEST_ITERS = 1000: hw 7.332ms/hash, sw 5.485ms/hash
TEST_MAX_LEN = 8192 (random length) / TEST_ITERS = 1000: hw 10.528ms/hash, sw 40.631ms/hash
TEST_MAX_LEN = 16384 (random length) / TEST_ITERS = 1000: hw 15.262ms/hash, sw 80.053ms/hash

For short hashes (256 bytes), software completes faster than hardware. Above 1k or so, the hardware accelerator starts to see benefits (and it's incredibly beneficial when say, checking the signature on a 6MiB binary blob). The benchmark includes all OS messaging overhead -- so for the hardware accelerator, the data has to be serialized and sent to the hash engine, where as the software implementation runs its code directly in the process space of the caller. So in the end we don't do fine-grained async on the crypto primitives.

However, the little I've seen of the Tock implementation you're running, it looks like the multitasking is cooperative?...I noticed from the very top down in your UX flows you're passing timers and having to explicitly call functions to update them, so my guess is you don't have cooperative multitasking? I am not terribly familiar with Tock. In which case I can see a very different design need for the trait implementations...

[bunnie]

If I read this correctly, the numbers are still hard to compare. For example, our decode_complete_data_item only takes 1.2KiB in cargo bloat. This is probably because we compile with opt-level = "z" and other rustc flags to optimize binary size. The real test is to replace the crypto libraries inside OpenSK it seems.

Ah yes. good point. Here is the output with opt-level = "z" (our default is max speed):

00040148 00007068 t vault::ux::start_ux_thread::{{closure}}
00029086 00004f3a t vault::ctap::CtapState<R,CheckUserPresence>::process_command
00031c26 00002b7c t vault::ctap::command::Command::deserialize
00025b7a 000028f0 t core::ops::function::FnOnce::call_once{{vtable.shim}}
00038f04 00001e04 t vault::ctap::response::<impl core::convert::From<vault::ctap::response::ResponseData> for core::option::Option<cbor::values::Value>>::from
00023d18 000017f0 t vault::main
0005ecb4 0000139a t sha2::sha256::compress256
00056fb0 00001180 t p256::arithmetic::scalar::Scalar::mul
0002e85e 00000d28 t ctap_crypto::ecdsa::SecKey::sign_rfc6979
00061bda 00000cba t dlmalloc_xous::dlmalloc::Dlmalloc<A>::malloc
00035df6 00000b38 t core::slice::sort::recurse
00036a96 00000a62 t vault::ctap::CtapState<R,CheckUserPresence>::assertion_response
0005973c 00000844 t p256::arithmetic::field::FieldElement::mul
00050030 000007fc t elliptic_curve::public_key::PublicKey<C>::from_sec1_bytes
000528e0 000007fa t ctap_crypto::ecdsa::Signature::to_asn1_der
0005a50c 000007b4 t <p256::arithmetic::projective::ProjectivePoint as core::ops::arith::Mul<&p256::arithmetic::scalar::Scalar>>::mul
00028502 00000794 t vault::ctap::storage::PersistentStore::init
0003533c 0000074c t vault::ctap::storage::deserialize_credential
0004b550 00000702 t cbor::reader::Reader::decode_complete_data_item
00066142 0000067a t std::panicking::rust_panic_with_hook
0004a328 0000061c t alloc::collections::btree::map::BTreeMap<K,V>::insert
000374f8 000005fe t alloc::collections::btree::map::BTreeMap<K,V>::insert
0005d7b0 000005ce t pddb::Pddb::list_keys
000547f0 00000598 t xous_ipc::buffer::Buffer::to_original
00051eca 00000598 t ctap_crypto::cbc::cbc_decrypt
00051576 0000058c t ctap_crypto::cbc::cbc_encrypt
0003ad08 00000542 t <T as core::convert::Into<U>>::into
0003f1a4 0000053a t <core::iter::adapters::GenericShunt<I,R> as core::iter::traits::iterator::Iterator>::next
0003147e 000004d8 t vault::ux::request_permission_inner
00064538 00000496 t <std::sys::xous::stdio::PanicWriter as std::io::Write>::write
000592b4 00000488 t p256::arithmetic::field::FieldElement::from_bytes
0004d2cc 00000466 t <str as core::fmt::Debug>::fmt
0002fe5e 00000462 t pddb::Pddb::get
0006160a 00000456 t dlmalloc_xous::dlmalloc::Dlmalloc<A>::check_tree
0003bf30 00000450 t <T as core::convert::TryInto<U>>::try_into
000256d8 0000041e t vault::repl::Repl::redraw

decode_complete_data_item takes 1.75k with z option. Still maybe too far off for a comparison because of the difference between the codegen backends, unfortunately.

[bunnie]

fwiw, s gets us better code size than z:

0003e49c 000064b6 t vault::ux::start_ux_thread::{{closure}}
00026be4 00006364 t vault::ctap::CtapState<R,CheckUserPresence>::process_command
00023512 00002902 t vault::main::{{closure}}
000373b6 00001bcc t vault::ctap::response::<impl core::convert::From<vault::ctap::response::AuthenticatorGetInfoResponse> for cbor::values::Value>::from
000549ae 0000143c t p256::arithmetic::scalar::Scalar::mul
0005c710 0000133e t sha2::sha256::compress256
0002d698 00000df8 t ctap_crypto::ecdsa::SecKey::sign_rfc6979
0004d2d2 00000dc8 t elliptic_curve::public_key::PublicKey<C>::from_sec1_bytes
0005f39a 00000cd6 t dlmalloc_xous::dlmalloc::Dlmalloc<A>::malloc
00056d5e 00000c7e t p256::arithmetic::field::FieldElement::mul
0002241a 00000b48 t vault::main
0003443c 00000a7c t vault::ctap::CtapState<R,CheckUserPresence>::assertion_response
00033824 00000a48 t core::slice::sort::recurse
00025e14 000009d8 t vault::ctap::storage::PersistentStore::init
00058196 000007d2 t <p256::arithmetic::projective::ProjectivePoint as core::ops::arith::Mul<&p256::arithmetic::scalar::Scalar>>::mul
0003b53c 0000079e t vault::ctap::storage::deserialize_credential
0003ad7c 00000776 t core::slice::sort::partition
00048742 000006e2 t cbor::reader::Reader::decode_complete_data_item
00052cba 0000067e t gam::Gam::register_ux
000638c2 0000067a t std::panicking::rust_panic_with_hook
0005b42c 0000066c t pddb::Pddb::list_keys
00051e4a 00000656 t gam::api::_::<impl rkyv::Deserialize<gam::api::Return,__D> for <gam::api::Return as rkyv::Archive>::Archived>::deserialize
0004764a 00000650 t alloc::collections::btree::map::BTreeMap<K,V>::insert
0004f7f0 00000648 t ctap_crypto::cbc::cbc_decrypt
0004f1b4 0000063c t ctap_crypto::cbc::cbc_encrypt
00036d82 00000634 t <T as core::convert::Into<U>>::into
00034eb8 00000624 t alloc::collections::btree::map::BTreeMap<K,V>::insert
00032a82 000005f4 t vault::ctap::storage::PersistentStore::store_credential
00033232 000005f2 t vault::ctap::storage::PersistentStore::filter_credential
00056210 00000570 t p256::arithmetic::field::FieldElement::to_bytes
00032448 0000056e t vault::ctap::storage::PersistentStore::new_creation_order
00022f62 000004f4 t vault::repl::Repl::redraw
0002fec4 000004e8 t vault::ux::request_permission_inner
0002ecd6 000004b8 t pddb::Pddb::get
0004a748 00000466 t <str as core::fmt::Debug>::fmt
0005edca 00000456 t dlmalloc_xous::dlmalloc::Dlmalloc<A>::check_tree
000362c4 00000450 t vault::ctap::pin_protocol_v1::check_and_store_new_pin
00061d2c 0000042c t <std::sys::xous::stdio::PanicWriter as std::io::Write>::write

in this case decode_complete_data_item drops ever so slightly to 1.72k. Just FYI!

[kaczmarczyck]

Small update: We now have a test implementation on the develop branch that runs on RustCrypto, you can try it with

cargo +nightly test --release --features std,rust_crypto --manifest-path libraries/opensk/Cargo.toml

I can experiment with RustCrypto on Nordic after we merge #580 and we can compile the embedded version of OpenSK with a newer nightly. I will come back with speed and binary size numbers then.

@bunnie This should also make it easier to have newer OpenSK versions in Xous in the future.

[kaczmarczyck]

You can now have an OpenSK with RustCrypto. Add the --rust-crypto flag to your deploy call. From the experimental results below,

For speed and binary size tradeoff, there is a discussion in #625. It suggests we can immediately replace AES, while still fittingall boards. Summary:

Speed in ms / iter (-Oz -> -O3 (our implementation)):

AES and SHA now beats our implementation, but ECDSA is still slower. I wonder why key generation is so slow though.

	Our impl	-Oz	-O3
Aes256::encrypt_block	0.21	0.55	0.37
Aes256::decrypt_block	1.28	0.55	0.40
Sha256::digest(32 bytes)	0.18	0.24	0.15
Ecdsa::SecretKey::random	3.51	356.84	221.50
Ecdsa::SecretKey::public_key	114.62	0.03	0.03
Ecdsa::SecretKey::sign	194.89	402.95	240.11

Binary size

Full RustCrypto increases the binary size over the 128 kB limit, means you can't have an upgradable OpenSK as of now. Using -Oz increases binary size by 23 kB. Our Cargo.toml is set to compile the crypto crates with -O3 though, so if you keep these options, you increase size by additional:

• aes: +2.1 kB
• sha2: +3.7 kB
• p256: +7.0 kB