x509-cert: support parsing X.509 certificates with no allocations

[DemiMarie]

WebPKI supports this, as does my own barebones-x509 crate.

[tarcieri]

See ample related discussion in #689 for the encoding side of things.

We pretty much went in the opposite direction in #765 and leaned further into the existing hard dependency on alloc.

[tarcieri]

In some other crates, notably spki and the latest prereleases of pkcs8, we do abstract over the owned and borrowed forms using generics:

https://docs.rs/pkcs8/0.11.0-rc.1/pkcs8/struct.PrivateKeyInfo.html

This has the following forms, one of which has a lifetime and the other does not:

• https://docs.rs/pkcs8/0.11.0-rc.1/pkcs8/type.PrivateKeyInfoRef.html
• https://docs.rs/pkcs8/0.11.0-rc.1/pkcs8/type.PrivateKeyInfoOwned.html

We could potentially do something like that with x509-cert as well, though we already use generics to carry a profile ZST, so it might become a lot of generic parameters, which makes the API more cumbersome.

[dishmaker]

In benchmarks x509-cert Decode is the slowest (but does Encode very fast).

Figure: x509-cert slowest (red), cryptography-x509 fastest

https://bencher.dev/perf/rasn/plots

Now there is opportunity to use alloc::Cow, as Tony refactored Ref types #1921

[tarcieri]

Curious what that benchmark actually looks like. Other implementations may be deferring processing of things x509-cert processes eagerly.

I'd also be curious what the hotspots in x509-cert.

[dishmaker]

Benchmark code:
https://github.com/librasn/rasn/blob/0a65d9a5699037ec19a706ce1f776ecc87d94b90/benches/criterion.rs#L42-L46

pyca cryptography-x509:
https://github.com/pyca/cryptography/blob/d20fcd0b439c6140772413aae589e3c617b39ac1/src/rust/cryptography-x509/src/certificate.rs#L40

[xyzzyz]

I saw other discussion on this topic, and I understand that the current design is crucial to making builder implementation simple and consistent.

What do you think about having a separate CertificateRef<'a> type, though, that only support parsing from existing DER bytes, and does not support building using a builder (or, really, any other way of creating instances)? On embedded devices, where this no_std, no_alloc scenario would be most useful, one rarely needs to create new certificates anyway, typically one only needs to verify a cert chain against trusted CA, and all of those are obtained by parsing DERs.

If someone posted a pull request with such feature, would you be willing to accept it? It would introduce new alloc feature, hide existing code that requires alloc behind it, and introduce new CertificateRef type that uses *Ref types from der crate where appropriate.

[tarcieri]

Ideally we could avoid the duplication of a separate type and leverage generics instead, making CertificateRef a type alias, similar to how the pkcs8 crate works: https://docs.rs/pkcs8/0.11.0-rc.6/pkcs8/index.html#types

Though a separate type could be considered as a last resort. Since we already have a Profile generic and the family of types we'd use for storing the document is unrelated, it seems like we'd be talking about tacking on a second generic parameter to Certificate, which seems a bit complicated on its own.

[dishmaker]

Having alloc and ref type aliases would have an obvious flaw of not supporting half-owned, half-ref certificates.

On the other hand, Cow cert would be useful for editing ref-parsed cert and replacing one field with some owned string, for example.

Personally, i use Cow ASN.1 DER for editing structures in egui in a browser under WASM.

Parsing and allocating 60 times a second, just to edit one Utf8String, would totally destroy GUI performance.

[tarcieri]

@dishmaker we could consider making the allocating structure Cow-based. Generics would permit both a fully owned type as well as Cow based. But whatever we do there is orthogonal to the no-alloc use case.

[xyzzyz]

I think that leveraging generics is definitely viable. It would be hard to make this change in a backward-compatible way, though. x509_cert is still on 0.x.x version, so it would not be against SemVer, but obviously existing users might not be particularly excited about their code breaking on update.

How do you weigh this concern vs code duplication resulting from introducing separate CertificateRef type?

[tarcieri]

We’re currently making breaking changes so that’s fine, but we will ideally start wrapping up soon

[xyzzyz]

@tarcieri would you (or some other RustCrypto developer/maintainer) be interested in contracted work for delivering this "X.509 certificates for no_std, no alloc environment" functionality? My organization is very interested in it.

[tarcieri]

I don't have time to work on this, sorry, though there are other users who might potentially be interested.