Skip to contentSkip to conversation

ASN.1

DISCUSSION Jarkko Sakkinen 4 participants 11 messages May 21, 2024 – May 23, 2024 Rust

lore
Share & tools
lore
#0 lore raw

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

#1 lore raw

Hi Jarkko,

Quoted 4 lines · Jarkko Sakkinen

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

#2 lore raw
Quoted 13 lines · Miguel Ojeda

Hi Jarkko,

Quoted 4 lines · Jarkko Sakkinen

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/

Quoted 5 lines

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/[email protected]/

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 ;-)

Quoted 2 lines

Cheers,
Miguel

BR, Jarkko

#3 lore raw
Quoted 4 lines · Jarkko Sakkinen

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

#4 lore raw
Quoted 17 lines · Jarkko Sakkinen
Quoted 4 lines · Jarkko Sakkinen

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.

Quoted 8 lines

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

#5 lore raw

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

Quoted 74 lines · Jarkko Sakkinen
Quoted 17 lines · Jarkko Sakkinen
Quoted 4 lines · Jarkko Sakkinen

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.

Quoted 8 lines

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

Signature · 1 line
All that is necessary for evil to succeed is for good people to do nothing.
#6 lore raw
Quoted 8 lines · 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).

Quoted 7 lines

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

#7 lore raw
Quoted 19 lines · Jarkko Sakkinen
Quoted 8 lines · 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).

Quoted 7 lines

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.

Quoted 7 lines

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

#8 lore raw
Quoted 4 lines · Jarkko Sakkinen

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

#9 lore raw
Quoted 7 lines · Jarkko Sakkinen
Quoted 4 lines · Jarkko Sakkinen

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

#10 lore raw
In reply to Jarkko Sakkinen
Quoted 6 lines · Jarkko Sakkinen

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