Hi, this is a reply to an email I found in the l4-hurd mail archive [http://lists.gnu.org/archive/html/l4-hurd/2005-10/msg00020.html]. I'm not on the list, sorry.
On Fri, 2005-10-07 at 23:01 -0400, Jonathan S. Shapiro wrote:
/ > > And, do we need the second one / / > > to be provided by idl4? I say, usually the server will not trust its / / > > client and this it's useless, as the server will not use the new handle./ / / / You are making an incorrect assumption. In general, what you say is/ / true, but if the server can authenticate the validity of a capability,/ / there is no reason not to use it./
...
The more general solution comes from something we call a "constructor". A "foo constructor" is a server that knows how to create new copies of the "foo" program. Every constructor inserts a unique, unforgeable, and undisclosable capability into the process structure of the process that it creates. This capability is called the "brand". Each constructor uses a different brand from all other constructors.
In EROS, there is a kernel capability that performs (approximately) the following operation:
interface ProcessTool extends key { bool identify(entry_cap_t someProc, cap_t brand); }
Given an entry capability to a process and a second capability, the kernel checks whether the second capability is equal to the existing brand in the process. If so, it returns true, else it returns false.
By construction, only constructors hold ProcessTool capabilities. However, if you hold a capability to a foo constructor, and you also hold an entry capability, you can turn to the foo constructor and ask "is this an entry capability to some process that you created?" That is: is it an entry capability to an authentic instance of "foo"?
This authentication pattern is enormously important for many of the security arrangements that we are able to achieve in EROS. One of my largest concerns about L4sec is that the L4sec team does not (yet) see that this operation is important. Without an operation like this, it is impossible (or at least, we do not see how) to build robust third-party trust contracts.
Jonathan, yes so far L4.Sec does not support such an operation. We thought about (I think Bernard Kauer and Marcus Brinkmann already had a discussion on this topic on l4-hackers) adding a compare operation on endpoints which allows you to match identity of two endpoint capability (compare permissions provided). So far we are not sure whether such an operation is really needed or whether you want to construct systems the way you do. The fundamental issue is that a potentially trusted capability is handed to a server by a not completely trusted source (the client C).
We thought briefly about two general solutions to this problem: 1) obtain a version of this capability from a trusted source, or, 2) prepare and defend against potential misbehavior of the invoked server.
ad 1: This solution assumes a network of trusted "name"-servers and protocols that require the client C in order to share a capability with some other process S that it establishes this sharing with the target of the capability (D). C can do so by giving its name to S to D and asking D to share the rights S can then request a capability to D from its trusted nameservers and ask for the shared capability provided it trusts D.
Please keep in mind that we did not build such a system yet and that it is only a preliminary and potentially not working solution.
ad 2: Alternatively the server can prepare to defend against misbehavior of D. In L4.Sec the receiver of an IPC controls the location where an incoming message is placed. Thus it can select an area of its address space so that even if D replies with bogus content, S is not harmed. It remains, however, the problem of blocking S. An easy way to defend against blocking attacks is to fork of a thread for this particular client's request and let it invoke the pot. untrusted capability on behalf of the client. Other thread invoking the same server are not affected by this blocking.
Again please keep in mind that both are preliminary solutions. We have still to construct a system on top of L4.Sec. Also please note that L4.Sec is not a fixed API but has experimental status and that we welcome both suggestions for improvement and requirements. However, you will find that features will be added only if they cannot be implemented on top of L4.Sec with a reasonable effort. This is one of the fundamental rules which in my opinion contributed to the success of L4. So please apologize my stubbornness in this point. Compare might be such a feature which will get added if we find no way to achieve what Jonathan listed in his mail.
Best regards
Marcus Völp
At Thu, 13 Oct 2005 14:13:21 +0200, Marcus Völp voelp@os.inf.tu-dresden.de wrote:
Jonathan, yes so far L4.Sec does not support such an operation. We thought about (I think Bernard Kauer and Marcus Brinkmann already had a discussion on this topic on l4-hackers) adding a compare operation on endpoints which allows you to match identity of two endpoint capability (compare permissions provided). So far we are not sure whether such an operation is really needed or whether you want to construct systems the way you do. The fundamental issue is that a potentially trusted capability is handed to a server by a not completely trusted source (the client C).
It is true that this is a property of Jonathans example. But in my discussion with Bernhard we established, I think, that the lack of a cmp operation also prevents other scenarios, including:
Invoking RPCs that have capabilities as arguments (for example a server-side copy operation).
Reference monitoring. In this case, trust is not necessarily involved, although it can be.
We thought briefly about two general solutions to this problem:
- obtain a version of this capability from a trusted source, or,
- prepare and defend against potential misbehavior of the invoked server.
ad 1: This solution assumes a network of trusted "name"-servers and protocols that require the client C in order to share a capability with some other process S that it establishes this sharing with the target of the capability (D). C can do so by giving its name to S to D and asking D to share the rights S can then request a capability to D from its trusted nameservers and ask for the shared capability provided it trusts D.
Please keep in mind that we did not build such a system yet and that it is only a preliminary and potentially not working solution.
If your "name" is a simple string of binary octets, then you are talking about unprotected capability systems, which don't offer adequate security.
If your "name" is a capability to an endpoint, then you are talking about a capability server, and that requires a cmp operation because you have to provide the capability you "name" as an argument to the request to retrieve a "trusted copy".
So, with reasonable assumptions, such a design requires a cmp operation at least. But please note: I have tried, quite hard, to make this work. Although I believe you can formally satisfy all logical requirements (ie, race-free protocols to do all the operations you want to do), the effort required is not reasonable, nor is the result usable. This applies to all variants of L4 I have heard so far, including Espen's work and the L4.sec work. Maybe someone smarter than me can fix that, but in my view this requires more changes to L4 than the addition of a cmp operation.
BTW, the protocol you describe doesn't even work, as in L4.sec there is no way for "C" to name "S" in its request to "D". Introducing such names, which would have to be authenticated, is impossible if C and S have a certain asymmetric trust relationship. However, there _are_ protocols which work, and I have worked them out (you can ask me for more details). They all require RPCs in which capabilities are passed as arguments and can be identified by the receiver, for example using a cmp operation.
Also, this proposal does not address the general case where an operation must be performed on more than one capability, like server side copy operations.
ad 2: Alternatively the server can prepare to defend against misbehavior of D. In L4.Sec the receiver of an IPC controls the location where an incoming message is placed. Thus it can select an area of its address space so that even if D replies with bogus content, S is not harmed. It remains, however, the problem of blocking S. An easy way to defend against blocking attacks is to fork of a thread for this particular client's request and let it invoke the pot. untrusted capability on behalf of the client. Other thread invoking the same server are not affected by this blocking.
This proposal achieves nothing. First of all, there is no benchmark that tells you when you have waited long enough and the capability should be rejected, for example because the destination blocked too long. But even more seriously, there is no benchmark to decide when the capability is good and its implementation be trusted. Thus, this proposal does not achieve the original goal at all.
It's nice that I can create a new thread to restrict the damage caused by a blocking RPC partner. But it has nothing to do with what you want to achieve in Jonathans example.
Again please keep in mind that both are preliminary solutions. We have still to construct a system on top of L4.Sec. Also please note that L4.Sec is not a fixed API but has experimental status and that we welcome both suggestions for improvement and requirements. However, you will find that features will be added only if they cannot be implemented on top of L4.Sec with a reasonable effort. This is one of the fundamental rules which in my opinion contributed to the success of L4. So please apologize my stubbornness in this point. Compare might be such a feature which will get added if we find no way to achieve what Jonathan listed in his mail.
You addressed this note to Jonathan, but I hope you will not mind if I share my opinion on it. From my perspective, it is totally fine that you are conservative in what you adopt for your design and implementation. It's also fine to have a focus on certain aspects of the system and leave other aspects completely aside.
But I am rather puzzled by your suggested preliminary solutions. The first doesn't work, and the second doesn't address the problem at all. At least to me they don't offer any insight into the following questions:
1. Is the design pattern actually desirable?
2. If yes, can it be _efficiently_ supported by the L4 architecture with a reasonable effort?
Thanks, Marcus
Marcus Brinkmann wrote:
Maybe someone smarter than me can fix that, but in my view this requires more changes to L4 than the addition of a cmp operation.
As I said, the fact that we did not include a cmp operation yet is simply because we were not sure to need it. Once you convince us cmp is in, provided it opens no further security leaks.
BTW, the protocol you describe doesn't even work, as in L4.sec there is no way for "C" to name "S" in its request to "D". Introducing such names, which would have to be authenticated, is impossible if C and S have a certain asymmetric trust relationship. However, there _are_ protocols which work, and I have worked them out (you can ask me for more details). They all require RPCs in which capabilities are passed as arguments and can be identified by the receiver, for example using a cmp operation.
It would be great if you could provide us these protocols. Actually that is what we are currently searching for to determine whether the proposed architecture will work out.
Also, this proposal does not address the general case where an operation must be performed on more than one capability, like server side copy operations.
I know this proposal is not complete and we can find various scenarios where it seems not to work. With regard to server side copy we are not quite sure yet whether we need such an operation. But this again assumes some system structure which performs the copy in a server that can savely invoke capabilities.
ad 2: Alternatively the server can prepare to defend against misbehavior of D. In L4.Sec the receiver of an IPC controls the location where an incoming message is placed. Thus it can select an area of its address space so that even if D replies with bogus content, S is not harmed. It remains, however, the problem of blocking S. An easy way to defend against blocking attacks is to fork of a thread for this particular client's request and let it invoke the pot. untrusted capability on behalf of the client. Other thread invoking the same server are not affected by this blocking.
This proposal achieves nothing. First of all, there is no benchmark that tells you when you have waited long enough and the capability should be rejected, for example because the destination blocked too long. But even more seriously, there is no benchmark to decide when the capability is good and its implementation be trusted. Thus, this proposal does not achieve the original goal at all.
It's nice that I can create a new thread to restrict the damage caused by a blocking RPC partner. But it has nothing to do with what you want to achieve in Jonathans example.
I don't agree here. The proposal is to be able to decide on the trust of a capability after invoking it and avoiding the damage when it turned out not to be trusted. This has nothing to do with blocking time but more with a server structure that acts for and on behalf of a client.
Jonathan's example (I assume you refer to the example where the server has to decide whether or not to leak secure data) works by requesting the not yet trusted target of the capability to authenticate itself (e.g., via the kernel protected badge send with the reply IPC) and to leak information only after the knowing that the server is trusted.
Again please keep in mind that both are preliminary solutions. We have still to construct a system on top of L4.Sec. Also please note that L4.Sec is not a fixed API but has experimental status and that we welcome both suggestions for improvement and requirements. However, you will find that features will be added only if they cannot be implemented on top of L4.Sec with a reasonable effort. This is one of the fundamental rules which in my opinion contributed to the success of L4. So please apologize my stubbornness in this point. Compare might be such a feature which will get added if we find no way to achieve what Jonathan listed in his mail.
You addressed this note to Jonathan, but I hope you will not mind if I share my opinion on it. From my perspective, it is totally fine that you are conservative in what you adopt for your design and implementation. It's also fine to have a focus on certain aspects of the system and leave other aspects completely aside.
You misunderstood me here. The above solutions describes our current vaque direction at what systems we want to build on top. It does not mean that we leave other aspects completely aside. We just have no resources right now to look at them all. I hope when analysing your protocols we will have the use cases we need to decide whether the current API will work or how it must be adapted. The note above is not addressed to Jonathan only, I just wanted to point out that we will continue trying to keep the kernel interface small because this is in my opinion one of the reasons for L4's success.
But I am rather puzzled by your suggested preliminary solutions. The first doesn't work, and the second doesn't address the problem at all. At least to me they don't offer any insight into the following questions:
- Is the design pattern actually desirable?
I don't know yet. We did not yet design / build a system of a scale which would allow us to answer this question. We are right now looking into such a system and we would welcome any contributions and a detailed understanding of your envisaged system.
- If yes, can it be _efficiently_ supported by the L4 architecture
with a reasonable effort?
Since the answer to the first question is a don't know we should not talk about efficiency yet. If a system structure cannot efficiently be supported by L4 we need to understand why and if it turns out to be the kernel which causes the inefficiency we will change it. Do you have any numbers for your architecture where you find L4 to be the bottleneck (assuming the functions you need were added).
Marcus
At Mon, 17 Oct 2005 12:55:09 +0200, Marcus Völp voelp@os.inf.tu-dresden.de wrote:
As I said, the fact that we did not include a cmp operation yet is simply because we were not sure to need it. Once you convince us cmp is in, provided it opens no further security leaks.
Unfortunately by now I am almost convinced that even introducing cmp() is insufficient, mostly because of performance and code complexity issues. So I may not be the best person to argue in favor of cmp().
BTW, the protocol you describe doesn't even work, as in L4.sec there is no way for "C" to name "S" in its request to "D". Introducing such names, which would have to be authenticated, is impossible if C and S have a certain asymmetric trust relationship. However, there _are_ protocols which work, and I have worked them out (you can ask me for more details). They all require RPCs in which capabilities are passed as arguments and can be identified by the receiver, for example using a cmp operation.
It would be great if you could provide us these protocols. Actually that is what we are currently searching for to determine whether the proposed architecture will work out.
You can start with my presentation at the LSM in Dijon. I make no apologies for its deficiencies: I am sure there is a lot in there that can embarrass me, so please apply good will liberally :)
You can find slides and an audio recording here:
http://medias.2005.libresoftwaremeeting.org/topics/os/
Porting the GNU/Hurd to the L4 microkernel, by Marcus Brinkmann Abstract [en] - Abstract [fr] - Slides [pdf] - Audio recording [ogg]
I am making a lot of assumptions in this work, many of which may not apply to yours. I am happy to further elaborate on it. This is probably best done in answering specific questions.
Also, this proposal does not address the general case where an operation must be performed on more than one capability, like server side copy operations.
I know this proposal is not complete and we can find various scenarios where it seems not to work. With regard to server side copy we are not quite sure yet whether we need such an operation. But this again assumes some system structure which performs the copy in a server that can savely invoke capabilities.
Certainly we are making a lot of assumptions. After all, we only want to implement one system, and not ten. So we make assumptions that seem appropriate to us for the type of system we want to build. I am happy to explain, and to some extend defend, the assumptions we make, should you find them suspicious.
Note that the copy operation was only an example. We use such an operation in our physical memory server design that implements trusted buffer objects, so we can make logical copies of page frames. I really can't imagine any other way to do this securely but by invoking one operation on two objects implemented by the same server.
The talk above contains another example where an operation needs to be invoked on two objects: The authentication server in our system implements ACL based authentication. The client provides an identifying capability to the server, and the server makes a call to its trusted authentication server handle, providing the clients capability and a capability that should be returned to the client (again, an operation that needs to be invoked on two capabilities at the same time). Note that the server can impose as the client to another server, but this is not a problem as the object is not directly returned, but given to the trusted auth server, where (only) the client can retrieve it.
ad 2: Alternatively the server can prepare to defend against misbehavior of D. In L4.Sec the receiver of an IPC controls the location where an incoming message is placed. Thus it can select an area of its address space so that even if D replies with bogus content, S is not harmed. It remains, however, the problem of blocking S. An easy way to defend against blocking attacks is to fork of a thread for this particular client's request and let it invoke the pot. untrusted capability on behalf of the client. Other thread invoking the same server are not affected by this blocking.
This proposal achieves nothing. First of all, there is no benchmark that tells you when you have waited long enough and the capability should be rejected, for example because the destination blocked too long. But even more seriously, there is no benchmark to decide when the capability is good and its implementation be trusted. Thus, this proposal does not achieve the original goal at all.
It's nice that I can create a new thread to restrict the damage caused by a blocking RPC partner. But it has nothing to do with what you want to achieve in Jonathans example.
I don't agree here. The proposal is to be able to decide on the trust of a capability after invoking it and avoiding the damage when it turned out not to be trusted. This has nothing to do with blocking time but more with a server structure that acts for and on behalf of a client.
Jonathan's example (I assume you refer to the example where the server has to decide whether or not to leak secure data) works by requesting the not yet trusted target of the capability to authenticate itself (e.g., via the kernel protected badge send with the reply IPC) and to leak information only after the knowing that the server is trusted.
I am not sure this is about leaking secure data, and I can't really follow your description of what the server does. Maybe this is just because I don't understand the terms you used in the way you use them. Maybe it helps if I say in my words what I think Jonathan's example achieves and how it does it.
The "sender" sends a capability to the "receiver". Now the objective for the receiver is to establish if it can "trust" this capability. Here this means: The receiver wants to be able to trust the _implementation_ of the capability. Ie, it wants to make sure that this capability is really implemented by the exact trusted system service it wants it to be implemented by.
For this purpose, the receiver can invoke a capability to the trusted system server which it already holds (for example, which it was given at process creation time), passing the "unknown" capability as an argument. _If_ the trusted system server has created the capability, it can now identify it via a kernel protected badge, and send a positive or negative reply in the response message.
Note that _not_ the "not yet trusted target" is asked to authenticate itself. Rather, an already trusted target is asked to identify the not yet trusted target by means of the identify operation, which is invoked on the server side.
Such an identify operation is also mentioned as an example in my talk. In fact, it is the basis for the reference monitor as well as the authentication server.
Note however that in my talk I often shortcut the process: The following two are analogous:
1. You first identify the untrusted capability as a trusted capability using a known trusted capability, then you perform an operation on it.
This is how it is done in EROS.
2. You combine both operations into a single one that is invoked on the known trusted capability and takes the untrusted capability as an argument.
This is how it is done in the Hurd (so far).
Here maybe you will find something reasonable: In the Hurd design we did, we never actually "use" the previously untrusted capability directly. We only use it as an authentication handle. This is merely a syntactical difference, though. The design pattern is exactly the same.
- Is the design pattern actually desirable?
I don't know yet. We did not yet design / build a system of a scale which would allow us to answer this question. We are right now looking into such a system and we would welcome any contributions and a detailed understanding of your envisaged system.
Fair enough. I developed the protocols from scratch (in cooperation with Neal Walfield), based on what we wanted to do in the Hurd. On this basis alone I would have little confidence that we are on the right track. But in hindsight I found similar design patterns in Shapiros work (EROS), which has a much better analytical foundation than our work. I submit the emergence of the same design pattern in two independent systems as one piece of evidence for its usefulness :)
- If yes, can it be _efficiently_ supported by the L4 architecture
with a reasonable effort?
Since the answer to the first question is a don't know we should not talk about efficiency yet.
From that perspective, I agree.
If a system structure cannot efficiently be supported by L4 we need to understand why and if it turns out to be the kernel which causes the inefficiency we will change it. Do you have any numbers for your architecture where you find L4 to be the bottleneck (assuming the functions you need were added).
No, because we halted the implementation for a reevaluation of the design decisions we made. The major reason we believe that performance will be inappropriate is at this point not primarily the cmp operation, but it is the lack of a copy operation for mappings. If you look at my protocols, this imposes an additional IPCs and system calls in the RPC path for every capability that should be copied from one process to another. As capability copy is expected to be ubiquituous, this is a discouraging result.
If I would assume that a copy operation is implemented, and a cmp operation is available, then that might be an opportunity to have another look. However, from a purely aesthetical design-intuition point of view, cmp() looks like a band-aid to me. There are two concerns and then a bit: To actually use cmp() efficiently, the client needs to supply a guess as to for which object it has supplied the capability. Otherwise the server can't find it in O(1). Not a big deal, but its cumbersome and increases the message size, and makes multiplexing more complex. Also, Espen argued convincingly that you really want to have the translation happen on the IPC path, and not after receiving the message, to reduce system call overhead. Because of this I found the ID objects Espen proposed a more convincing approach. However, the devil was in the detail, and there were a couple of important optimizations and small feature extensions required to make it all fit together (for example for efficient "return capabilities" we would want a new map item which would auto-destruct on the next mapping---things like that).
To accept any of this however, you need to come a certain way along with us, accepting some of our assumptions, at least preliminary. In return, I would easgerly listen to alternative proposals that don't give up on the general goal (a protected capability system that allows to implement secure operating systems).
It's some months since I looked at all this the last time, but it's all slowly coming back to me as if it was yesterday. Now I'll shut up and wait for your questions. :)
Thanks, Marcus
Hi,
If you look at my protocols, this imposes an additional IPCs and system calls in the RPC path for every capability that should be copied from one process to another. As capability copy is expected to be ubiquituous, this is a discouraging result.
Is it really? My Guess would be that in typical use, capability passing of any kind should happen seldom enough not to make a few more IPCs/syscalls critical... But well, I guess I'm overlooking something :-)
-antrik-
At Tue, 18 Oct 2005 01:26:10 +0200, olafBuddenhagen@gmx.net wrote:
Hi,
If you look at my protocols, this imposes an additional IPCs and system calls in the RPC path for every capability that should be copied from one process to another. As capability copy is expected to be ubiquituous, this is a discouraging result.
Is it really? My Guess would be that in typical use, capability passing of any kind should happen seldom enough not to make a few more IPCs/syscalls critical... But well, I guess I'm overlooking something :-)
Well, it depends. You may be right. By careful optimization, we can probably use revocable copies (ie, simple mappings) in L4 for many operations. Especially when sending capabilities from a client to a server, which would include the important I/O path and container use.
This is with the Hurd server design that we had in mind so far. But in this design so far we haven't even tried to leverage the capability system to its full extent. In fact, we are making pretty poor use of it. If you opt for a different system architecture, it may be different. For example, process instantiaton (spawn or fork) requires many capability copies even in our current plans. Creating new processes is an important operation in the EROS operating system to enforce confinement policies.
Thanks, Marcus
Hi,
For example, process instantiaton (spawn or fork) requires many capability copies even in our current plans. Creating new processes is an important operation in the EROS operating system to enforce confinement policies.
I see a flaw in this reasoning: If you start more processes due to a finer grained design -- which is probably a Good Thing (TM) -- then the individuall processes do less, so you need only few capabilities for each one... We'd need to make the rest of the process startup *very* efficient, to make it matter even for a "hello world" process. (Would be desirable, but I doubt it is achievable.)
I still can't think of any realistic scenario, where capability passing would be so common as to make a few hundred clock cycles per operation really relevant. Of course, that doesn't mean none exist...
-antrik-
On Thu, 2005-10-20 at 02:31 +0200, olafBuddenhagen@gmx.net wrote:
Hi,
For example, process instantiaton (spawn or fork) requires many capability copies even in our current plans. Creating new processes is an important operation in the EROS operating system to enforce confinement policies.
I see a flaw in this reasoning: If you start more processes due to a finer grained design -- which is probably a Good Thing (TM) -- then the individuall processes do less, so you need only few capabilities for each one... We'd need to make the rest of the process startup *very* efficient, to make it matter even for a "hello world" process. (Would be desirable, but I doubt it is achievable.)
I still can't think of any realistic scenario, where capability passing would be so common as to make a few hundred clock cycles per operation really relevant. Of course, that doesn't mean none exist...
I think You have to distinguish between user-level capabilities, representing user-level objects and kernel capabilities which name kernel objects, such as communication points. For kernel capabilities there may be a very frequent transfers, in particular in the case of sessionless protocols, where a capability for the answer must be transfered on every IPC because of the unidirectional nature of communication points.
l4-hackers@os.inf.tu-dresden.de
-
Alexander Warg -
Marcus Brinkmann -
Marcus Völp -
olafBuddenhagen＠gmx.net