ASN.1

ASN.1

[Jarkko Sakkinen]

Hi,

There's one application where it would make a lot of sense to have the
core implementation in Rust, and make it callable from C. It is encoding
and decoding of ASN.1 (DER).

It is essentially hierarchical binary parsing, i.e. exactly kind of
stuff where it is too easy to shoot yourself into foot with C.

So question is how to approach this? How the holding data structure for
holding the deserialized data should represented so that is is also
directly accessible from C?

Maybe not the sexiest application ever, but it is an actual applications
where Rust might weight a lot, also for the C code base ;-)

I'm interested to help with this too as I consume a lot of DER type of
input data... so I know what it should look like to work at all for the
C code. Or do not know at this poinnt, but can verify the sensibility
at minimum :-)

BR, Jarkko

Re: ASN.1

[Miguel Ojeda]

Hi Jarkko,

On Tue, May 21, 2024 at 8:36 AM Jarkko Sakkinen <jarkko@kernel.org> wrote:
>
> So question is how to approach this? How the holding data structure for
> holding the deserialized data should represented so that is is also
> directly accessible from C?

Daniel (Cc'd) is working on in-kernel Rust codecs and is experimenting
with `cbindgen` support to easily provide an API for C code (of
course, you can do it manually too), so you may want to talk :) He
recently wrote this article on it: https://lwn.net/Articles/970565/

The main issue with a parallel implementation is whether the relevant
maintainers will be OK with keeping both versions alive in the kernel.
As usual, some ideas that may help offsetting the maintenance cost may
be showcasing a security benefit, or a performance improvement, or a
complexity reduction, or an avoidance of unsafe code, etc.

Cheers,
Miguel

Re: ASN.1

[Jarkko Sakkinen]

On Tue May 21, 2024 at 5:52 PM EEST, Miguel Ojeda wrote:
> Hi Jarkko,
>
> On Tue, May 21, 2024 at 8:36 AM Jarkko Sakkinen <jarkko@kernel.org> wrote:
> >
> > So question is how to approach this? How the holding data structure for
> > holding the deserialized data should represented so that is is also
> > directly accessible from C?
>
> Daniel (Cc'd) is working on in-kernel Rust codecs and is experimenting
> with `cbindgen` support to easily provide an API for C code (of
> course, you can do it manually too), so you may want to talk :) He
> recently wrote this article on it: https://lwn.net/Articles/970565/
>
> The main issue with a parallel implementation is whether the relevant
> maintainers will be OK with keeping both versions alive in the kernel.
> As usual, some ideas that may help offsetting the maintenance cost may
> be showcasing a security benefit, or a performance improvement, or a
> complexity reduction, or an avoidance of unsafe code, etc.

For me the main use case would be loading of keys (I co-maintain
keyring).

For keyring the ASN.1 C-API is actually quite good in the sense that
callbacks in parsing and sequential encoding are great at not conserving
memory (actually zero consumption almost). In that sense I'm happy with
it.

It is just hard to modify in the sense that it is very prone to
off-by-one errors and such.

Here's an example of a patch set that I wrote over the weekend for
asymmetric keys:

https://lore.kernel.org/linux-integrity/20240521031645.17008-1-jarkko@kernel.org/

In this case I could imagine loading ASN.1 blob by calling Rust
functions. But yeah more like "immediate mode" API rather than "retained
mode" style ;-)

> Cheers,
> Miguel

BR, Jarkko

Re: ASN.1

[Jarkko Sakkinen]

On Tue May 21, 2024 at 6:20 PM EEST, Jarkko Sakkinen wrote:
> On Tue May 21, 2024 at 5:52 PM EEST, Miguel Ojeda wrote:
> In this case I could imagine loading ASN.1 blob by calling Rust
> functions. But yeah more like "immediate mode" API rather than "retained
> mode" style ;-)

Hey, sorry I was mixing things a bit so let me clear this up!

The decoder works as follows. There is a compiler, which generates
bytecode object linked to vmlinux and a header with symbol declaration.
Then there is a asn1_ber_decoder(), which runs the bytecode through a
trivial interpreter with e.g. a key blob as parameter.

And this part is great and it does not really get in the way. All of
kernel uses it to parse ber/der/cer blobs in, and it is somewhat stable,
and super well tested. For decoder the value of Rust is not that great.

Encoder (asn1_encoder.c) is just a set of basic functions, like one
function per tagged type to serialize that type. Most valuable asset
would be to replicate this set in Rust with better defined contraints
etc.

Sorry for longish explanation, just wanted to clear up this story :-)
I.e encoder is higher value asset than the decoder as far as I'm
concerned, despite being much more trivial to implement.

BR, Jarkko

Re: ASN.1

[Jarkko Sakkinen]

On Tue May 21, 2024 at 9:01 PM EEST, Jarkko Sakkinen wrote:
> On Tue May 21, 2024 at 6:20 PM EEST, Jarkko Sakkinen wrote:
> > On Tue May 21, 2024 at 5:52 PM EEST, Miguel Ojeda wrote:
> > In this case I could imagine loading ASN.1 blob by calling Rust
> > functions. But yeah more like "immediate mode" API rather than "retained
> > mode" style ;-)
>
> Hey, sorry I was mixing things a bit so let me clear this up!
>
> The decoder works as follows. There is a compiler, which generates
> bytecode object linked to vmlinux and a header with symbol declaration.
> Then there is a asn1_ber_decoder(), which runs the bytecode through a
> trivial interpreter with e.g. a key blob as parameter.
>
> And this part is great and it does not really get in the way. All of
> kernel uses it to parse ber/der/cer blobs in, and it is somewhat stable,
> and super well tested. For decoder the value of Rust is not that great.
>
> Encoder (asn1_encoder.c) is just a set of basic functions, like one
> function per tagged type to serialize that type. Most valuable asset
> would be to replicate this set in Rust with better defined contraints
> etc.
>
> Sorry for longish explanation, just wanted to clear up this story :-)
> I.e encoder is higher value asset than the decoder as far as I'm
> concerned, despite being much more trivial to implement.

For the patch set I'm working on I do have good solution. I only need to
encode this:

RsaPubKey ::= SEQUENCE {
	n INTEGER ({ rsa_get_n }),
	e INTEGER ({ rsa_get_e })
}

And nice thing is that e is always 65537 and length of e is always 3
i.e. {3} serialized so it is serialized as

	static const u8 EXPONENT[5] = {0x02, 1, 0x01, 0x01, 0x01};

Sequence and n can be expressed along the lines of

	/* Last two bytes are filled with 16-bit big-endian length: */
	u8 sequence[] = {0x30, 0x82, 0x00, 0x00};
	u8 n_head[] = {0x02, 0x82, 0x00, 0x00};

So I just copy stuff in order:

1. sequence
2. n_head
3. n (contents)
4. e

And this is along the line what I'm actually going to do because it is
stable for the use case. However, it would be nice that instead of such
sudoku there would be super stable Rust functions to take care of
writing these. This particular use case is sorted and I'll be fine, but
these pop up from time to time in different situations.

The problem with encoders I found for Rust from crates.io is that they
are like too bounded to the type system of Rust by implementing
conversion traits (From, Into etc.) available. Instead of this approach
for it might be more feasible to have dummy functions with no mangling
in the symbols like encode_sequence, encode_integer etc. You can always
use these dummy global functions to implement those fancy traits and
provide bridge for C at the same time and direct as possible access to
the actual functionality.

I think this is simple but very nice and usable pattern for bridging
from C to Rust provided services.

BR, Jarkko

Re: ASN.1

[Alex Gaynor]

Hi Jarkko,

I'm one of the maintainers of https://crates.io/crates/asn1/. Based on
that experience, if you want to implement a DER encoder in Rust, I
think it'd make more sense to write the type-code in Rust, and then
expose symbols to C like `encode_rsa_pub_key`. This should be simpler,
but also more efficient (fewer allocations).

For what it's worth, rust-asn1 is _intended_ to be usable from the
kernel/embedded targets. It's no_std. It currently relies on alloc,
but I'd be happy to accept PRs to make it work with the kernel's
approach to fallible allocation (it currently does support fallible
allocation, but using the reserve APIs).

Alex

On Tue, May 21, 2024 at 2:55 PM Jarkko Sakkinen <jarkko@kernel.org> wrote:
>
> On Tue May 21, 2024 at 9:01 PM EEST, Jarkko Sakkinen wrote:
> > On Tue May 21, 2024 at 6:20 PM EEST, Jarkko Sakkinen wrote:
> > > On Tue May 21, 2024 at 5:52 PM EEST, Miguel Ojeda wrote:
> > > In this case I could imagine loading ASN.1 blob by calling Rust
> > > functions. But yeah more like "immediate mode" API rather than "retained
> > > mode" style ;-)
> >
> > Hey, sorry I was mixing things a bit so let me clear this up!
> >
> > The decoder works as follows. There is a compiler, which generates
> > bytecode object linked to vmlinux and a header with symbol declaration.
> > Then there is a asn1_ber_decoder(), which runs the bytecode through a
> > trivial interpreter with e.g. a key blob as parameter.
> >
> > And this part is great and it does not really get in the way. All of
> > kernel uses it to parse ber/der/cer blobs in, and it is somewhat stable,
> > and super well tested. For decoder the value of Rust is not that great.
> >
> > Encoder (asn1_encoder.c) is just a set of basic functions, like one
> > function per tagged type to serialize that type. Most valuable asset
> > would be to replicate this set in Rust with better defined contraints
> > etc.
> >
> > Sorry for longish explanation, just wanted to clear up this story :-)
> > I.e encoder is higher value asset than the decoder as far as I'm
> > concerned, despite being much more trivial to implement.
>
> For the patch set I'm working on I do have good solution. I only need to
> encode this:
>
> RsaPubKey ::= SEQUENCE {
>         n INTEGER ({ rsa_get_n }),
>         e INTEGER ({ rsa_get_e })
> }
>
> And nice thing is that e is always 65537 and length of e is always 3
> i.e. {3} serialized so it is serialized as
>
>         static const u8 EXPONENT[5] = {0x02, 1, 0x01, 0x01, 0x01};
>
> Sequence and n can be expressed along the lines of
>
>         /* Last two bytes are filled with 16-bit big-endian length: */
>         u8 sequence[] = {0x30, 0x82, 0x00, 0x00};
>         u8 n_head[] = {0x02, 0x82, 0x00, 0x00};
>
> So I just copy stuff in order:
>
> 1. sequence
> 2. n_head
> 3. n (contents)
> 4. e
>
> And this is along the line what I'm actually going to do because it is
> stable for the use case. However, it would be nice that instead of such
> sudoku there would be super stable Rust functions to take care of
> writing these. This particular use case is sorted and I'll be fine, but
> these pop up from time to time in different situations.
>
> The problem with encoders I found for Rust from crates.io is that they
> are like too bounded to the type system of Rust by implementing
> conversion traits (From, Into etc.) available. Instead of this approach
> for it might be more feasible to have dummy functions with no mangling
> in the symbols like encode_sequence, encode_integer etc. You can always
> use these dummy global functions to implement those fancy traits and
> provide bridge for C at the same time and direct as possible access to
> the actual functionality.
>
> I think this is simple but very nice and usable pattern for bridging
> from C to Rust provided services.
>
> BR, Jarkko
>


-- 
All that is necessary for evil to succeed is for good people to do nothing.

Re: ASN.1

[Jarkko Sakkinen]

On Wed May 22, 2024 at 3:04 PM EEST, Alex Gaynor wrote:
> Hi Jarkko,
>
> I'm one of the maintainers of https://crates.io/crates/asn1/. Based on
> that experience, if you want to implement a DER encoder in Rust, I
> think it'd make more sense to write the type-code in Rust, and then
> expose symbols to C like `encode_rsa_pub_key`. This should be simpler,
> but also more efficient (fewer allocations).
>
> For what it's worth, rust-asn1 is _intended_ to be usable from the
> kernel/embedded targets. It's no_std. It currently relies on alloc,
> but I'd be happy to accept PRs to make it work with the kernel's
> approach to fallible allocation (it currently does support fallible
> allocation, but using the reserve APIs).
>
> Alex

Right, I need to experiment with that just in user space first.

It seemed like most "productized" crate from all that I found.

Yeah, and it is true that also crate could be as rusty as hell,
and then just make bridge shim that hides all that ;-) That is
probably better way around.

Thanks for the response!

BR, Jarkko

Re: ASN.1

[Jarkko Sakkinen]

On Wed May 22, 2024 at 3:56 PM EEST, Jarkko Sakkinen wrote:
> On Wed May 22, 2024 at 3:04 PM EEST, Alex Gaynor wrote:
> > Hi Jarkko,
> >
> > I'm one of the maintainers of https://crates.io/crates/asn1/. Based on
> > that experience, if you want to implement a DER encoder in Rust, I
> > think it'd make more sense to write the type-code in Rust, and then
> > expose symbols to C like `encode_rsa_pub_key`. This should be simpler,
> > but also more efficient (fewer allocations).
> >
> > For what it's worth, rust-asn1 is _intended_ to be usable from the
> > kernel/embedded targets. It's no_std. It currently relies on alloc,
> > but I'd be happy to accept PRs to make it work with the kernel's
> > approach to fallible allocation (it currently does support fallible
> > allocation, but using the reserve APIs).
> >
> > Alex
>
> Right, I need to experiment with that just in user space first.
>
> It seemed like most "productized" crate from all that I found.
>
> Yeah, and it is true that also crate could be as rusty as hell,
> and then just make bridge shim that hides all that ;-) That is
> probably better way around.
>
> Thanks for the response!

If we want to considering getting your code to land to the kernel I
would start with the decoder as it already delivers, as an
*experimental* feature. Then when it is landed it would not be
as huge stretch to move forward with the encoder.

Basically how Rust ASN.1 could work out for kernel is pretty trivial to
describe:

1. Add a new Kconfig flag: e.g. CONFIG_ASN1_RUST. This flag could be a
   subflag of CONFIG_ASN1 and by default obviously disabled.
2. Import asn1 code to kernel and make it build as part of vmlinux.
3. Implement a shim for C with zero or at least minimal changes to the
   developer experience. I.e. you can drop your asn1 file to the subsystem
   directory and some small tweaks to Makefile and you are set.
4. Update MAINTAINERS. I think this should have own entry and probably
   you would be the best possible person to have M-entry. I could add
   myself R-entry (reviewer) because I'm the end customer :-)

If we would get this far and get this to also mainline then it would
be also a huge step towards encoding as then it would be just adding
another feature without infrastructural madness involved ;-)

BR, Jarkko

Re: ASN.1

[Jarkko Sakkinen]

On Wed May 22, 2024 at 4:49 PM EEST, Jarkko Sakkinen wrote:
> If we want to considering getting your code to land to the kernel I
> would start with the decoder as it already delivers, as an
> *experimental* feature. Then when it is landed it would not be
> as huge stretch to move forward with the encoder.

About the encoder. It is relatively new and has only caller, and I'm not
sure if we care about it that much.

In my case I just did:

static int tpm2_key_rsa_encode(const struct tpm2_key_rsa *key, u8 *buf)
{
	int pub_len = key->pub_len;
	const u8 *pub = key->pub;
	u8 *start = &buf[4];
	u8 *work = &buf[4];
	u32 seq_len;

	work[0] = 0x02;			/* INTEGER */
	work[1] = 0x82;			/* u16 */
	work[2] = pub_len >> 8;
	work[3] = pub_len & 0xff;
	work = &work[4];
	memcpy(work, pub, pub_len);
	work = &work[pub_len];
	work[0] = 0x02;			/* INTEGER */
	work[1] = 3;			/* < 128 */
	work[2] = 1;			/* 65537 */
	work[3] = 0;
	work[4]	= 1;
	work = &work[5];
	memset(work, 0, 8);
	seq_len = work - start;
	buf[0] = 0x30;			/* SEQUENCE */
	buf[1] = 0x82;			/* u16 */
	buf[2] = seq_len >> 8;
	buf[3] = seq_len & 0xff;

	return seq_len + 4;
}

Not the prettiest looking but it does the job and is actually easy
to verify :-) Decoder is on the other hand old and mature and makes
more sense both in implementation and architecture.

Looking back it was my mistake to let that encoder into the mainline,
I did not use it because it did not make sense to me, or at least
less sense than above, which practically never changes and is easy
to also later verify and fix, despite being somewhat archaic.

Given this if we want to work on ASN1_RUST experimental feature, I
can create a patch that open codes the call site in trusted_tpm2.c
and thus ASN1_ENCODER can be droper entirely. It is not a priority
but could be part of the patch set, or Git branch, which adds
ASN1_RUST.

So what I might do to move forward is early next month to start
with such patch and create asn1rust branch to my tree at:

https://git.kernel.org/pub/scm/linux/kernel/git/jarkko/linux-tpmdd.git

And then start looking at the crate and perhaps post here a more
refined suggestion how to move forward.

Early next month because I have a conference demo to do (actually
in Rust but not kernel related) by the end of the month.

The reason I'm concerned about the topic is that keyring has literally
billions of users dependent on it (mostly without knowing but it is used
practically in any Linux installation) and I know that Rust side needs
ASN.1 eventually, so I want to make sure that the integration path works
for us.

So let's now pretend that encoder did not exist and focus only on
decoder :-)

Sounds like a plan? 

BR, Jarkko

Re: ASN.1

[Jarkko Sakkinen]

On Thu May 23, 2024 at 10:00 AM EEST, Jarkko Sakkinen wrote:
> On Wed May 22, 2024 at 4:49 PM EEST, Jarkko Sakkinen wrote:
> > If we want to considering getting your code to land to the kernel I
> > would start with the decoder as it already delivers, as an
> > *experimental* feature. Then when it is landed it would not be
> > as huge stretch to move forward with the encoder.
>
> About the encoder. It is relatively new and has only caller, and I'm not

*only single caller.

BR, Jarkko

Re: ASN.1

[Jarkko Sakkinen]

On Thu May 23, 2024 at 10:00 AM EEST, Jarkko Sakkinen wrote:
> On Wed May 22, 2024 at 4:49 PM EEST, Jarkko Sakkinen wrote:
> Given this if we want to work on ASN1_RUST experimental feature, I
> can create a patch that open codes the call site in trusted_tpm2.c
> and thus ASN1_ENCODER can be droper entirely. It is not a priority
> but could be part of the patch set, or Git branch, which adds
> ASN1_RUST.

Not necessarily entirely, that was an overkill statement, but
mostly have only dynamic stuff in it and improve the C API to
be good match of whatever done in encoding side on Rust. I.e.
no regrets for picking it but it needs to mature, and I think
this rust opt-in would also do good for C implementation.

Just writing the notes so that I recall all this some weeks
from now ;-)

BR, Jarkko