Method for generating tokens for capabilities?

[hawkw]

We need to determine how the kernel will generate tokens to represent capabilities. These are essentially key pairs. Of course, it's necessary to generate capability tokens securely, necessitating some kind of crypto inside the kernel. However, we also want to be able to both generate and verify them quickly, since I suspect both generating and checking capability tokens will become a bottleneck – since it has to happen every time a syscall is performed.

I think we'll want to incorporate some run-specific entropy sources in the capability generation algorithm, to protect against attacks where malicious code saves a legitimately-granted capability for later use, when it is no longer granted that capability.

[hawkw]

@twisted-pear, any thoughts?

[twisted-pear]

Ok, as for the capabilities themselves: Do we really want to implement caps as keys that we check as opposed to "some datastructure the kernel keeps on behalf of a userland process"? Aside from the mentioned performance problems we also run into things like:

• Are we ok with a process arbitrarily sharing it's capabilities? Or how do we prevent that?
• How do we prevent accidental leakage? Timing side-channels etc.
• What about freshness of the tokens? Are they valid forever?

I suspect that you have already looked into capability systems (i haven't) so maybe there are simple answers to these concerns,

The second part is about entropy. Yes, we need an entropy pool in the kernel that is capable to provide us with good randomness. IIRC there are tried and true constructs for such systems where you have a way to seed and regularly reseed such a pool and also check if it has bees seeded at least once and where things like forward-/backward-secrecy are already considered. I'd have to dig through some crypto literature but the names I remember are "Yarrow" and "Fortuna" I think. Not sure if these are still state of the art or if there are now better ways to do it.

Incidentally, using such a system will probably require some sort of cipher or hash function, so it might be prudent to implement a small crypto lib first that gives us access to say AES and SHA-3 primitives.

End braindump.

[hawkw]

I suspect that you have already looked into capability systems (i haven't) so maybe there are simple answers to these concerns,

I've done a little research, but not nearly enough. This is far enough in the future that it's just something I was thinking about.

Do we really want to implement caps as keys that we check as opposed to "some datastructure the kernel keeps on behalf of a userland process"?

I had originally wanted the process to own half of a keypair, but that might be massively over-engineered and just having the kernel do all the bookkeeping could be a better solution.

• Are we ok with a process arbitrarily sharing it's capabilities? Or how do we prevent that?

Not sure. I'm thinking that caps are granted to specific processes and can't be shared. There might be some kind of sharing rules for child processes? This is its' own design issue I think.

• What about freshness of the tokens? Are they valid forever?

Hmm. I think caps definitely can't outlive the lifetime of a process, not sure if they need to be refreshed within its lifespan? I think if the caps are granular enough, it should be reasonable to let a process keep a cap once it's granted once...

[hawkw]

Probably a good starting place for further research is "how does seL4 do it"...

[twisted-pear]

The thing is if we use keys like you suggested, what is to stop a process from giving its key to another process, write it to disk, send it over network etc?

The freshness thing is kinda related to this. We'd need to invalidate keys once a process terminates, but if we already do that kind of bookkeeping...

[hawkw]

The thing is if we use keys like you suggested, what is to stop a process from giving its key to another process, write it to disk, send it over network etc?

My initial thought was some kind of hash function involving the process's PID and the key. I'm not sure how practical that is or if there's some kind of attack based on having a predictable PID. Just a shower thought at this point.

[hawkw]

Having the kernel do all the bookkeeping may end up being a more workable solution. I just find the elegance of handing out capability objects that bundle together permission & behaviour to be really appealing.

[hawkw]

Hmm – and this is probably a terrible idea, just something that popped into my head – what if requesting a cap got you back a sort of kernel mode thunk? Like the kernel basically JITs you a binary blob that performs whatever syscall you wanted...

[twisted-pear]

a quick glance at the seL4 FAQ would suggest that they actually have the kernel do the bookkeeping for caps and don't rely on crypto...

[twisted-pear]

hmmm, but that would allow you to place arbitrary executable stuff in kernel mem, right?

[twisted-pear]

it sounds like an invitation for jit spraying but maybe i'm wrong

[hawkw]

a quick glance at the seL4 FAQ would suggest that they actually have the kernel do the bookkeeping for caps and don't rely on crypto...

I'm getting the sense that's probably the right way to go...which is a shame, crypto is fun.

hmmm, but that would allow you to place arbitrary executable stuff in kernel mem, right?

I was thinking the kernel gives you the code blob, but then there's also the issue that pulling this off would take some black magic with address spaces.

it sounds like an invitation for jit spraying but maybe i'm wrong

I did say this was a bad idea, didn't I? :P

[twisted-pear]

nevertheless, the kernel is the only place where you can implement an entropy pool and it's something very useful for a lot of other things

[hawkw]

yeah we definitely should have a nice source of randomness in kernel space regardless.