[E-Lang] MintMaker with ACLs

hal@finney.org hal@finney.org
Sat, 3 Feb 2001 20:58:53 -0800

Tyler wrote:
> Hal wrote:
> > [CC list trimmed]
> >
> > Tyler wrote, with regard to the ACL based "mint":
> >
> > > Several very useful design patterns become fatal security holes:
> > > Visitor, Internal Iteration, Observer, Hollywood (don't
> > call me, I'll
> > > call you, eg: SAX), Strategy, ... Essentially, anything
> > that requires
> > > what is traditionally thought of as a callback. In a
> > callback, I can
> > > provide an object that you will in turn invoke. The
> > contents of the
> > > callback are totally at my discretion. In an ACL system,
> > all of these
> > > patterns result in me hijacking your authority to execute
> > arbitrary
> > > code. These patterns are harmless, and very useful, in a
> > capability
> > > system.
> >
> > Can this be addressed by using cooperating processes for
> > these patterns,
> > with remote procedure calls for the callbacks?  In this way we limit
> > the ownership rights from spreading into subroutines.
> Yes, this would work. This solution would require that every principal
> in the application have its own process and that all communication
> between principals take place through RPC. Note that in a well
> designed application (one that observes POLA) there is a one to many
> relationship between actual users and principals. Every time the
> software designer practices encapsulation, another process would need
> to be created. Are you proposing a system in which it is easy and
> efficient to spawn new processes and do synchronous RPC? It seems
> unlikely that this will fit as naturally with the function call
> support of a typical CPU.

When Jonathon Shapiro replied that this was essentially how EROS works,
Tyler added,

> Interesting, it didn't immediately occur to me that Hal had solved the
> problem my making callback objects capabilities.

I am surprised to hear that you consider the use of cooperative processes
in different protection domains to be the introduction of capabilities.
In other contexts you have also described various proposed ways of
addressing ACL problems as being de facto capabilities.  What is it
about my proposal for addressing the callback problem that makes it
look like a capability system?  I didn't say anything about altering the
underlying operating system to add capability functionality.  The powers
of the cooperating processes would still be limited by their identifiers,
which would seem to make it impossible to treat data passed between them
as capabilities.

> > > It is very dangerous to pass messages between UIDs when
> > those messages
> > > may contain objects that can be used as designators. For example,
> > > consider the java.io.File object. If I can pass a message
> > containing a
> > > java.io.File object from my JVM to your JVM, then I can manipulate
> > > arbitrary files in your JVM using your authority. This is classic
> > > confused deputy behaviour. Similar attacks with strings and web
> > > servers have sunk many a web site.
> >
> > This sounds more like a problem with capabilities than
> > something that
> > could happen passing messages between UIDs.  In an ACL system, the
> > permissions are associated with UID, hence no message passed between
> > different UIDs can grant authority.  With a capability
> > system, if you
> > pass a File capability from one UID to another you are
> > allowing access
> > to whatever that capability represents.
> You are misunderstanding. A java.io.File object is not a capability.
> It has a public contructor. It is a designator. The attack is to move
> that designator into another authority domain. This attack does not
> exist in a capability system.

I think I understand what you mean now; you would fool the other authority
domain into performing some harmful action by giving it a designator
(say, a filename) and tricking it into use its powers on that designator,
correct?  This is impossible in capability systems because the designator
limits the power.

This is a good point, but after all you are exploiting a bug in the
program which you are fooling, right?  It was careless and didn't do
things as carefully as it should.  Such bugs are common and fill the CERT
advisory lists.  But they are considered bugs and they can be fixed by
more careful coding.  They are not an inherent property of ACL systems,
rather they are a kind of mistake which shows up in such systems.

Isn't a similar level of carelessness also possible with capabilities?
In this case, a comparable error would be passing the wrong capability
to another process, one which grants more power than you intended.
The remote process could then attack you by attempting to exercise the
additional power in a malicious matter.  Such a bug might not show up
for a long time because the attacker would typically not even try to
exercise more power than it should.

This attack does not exist in an ACL system.  If we had a world built
on capability systems, wouldn't the pages of CERT advisories be full of
cases where excessively powerful capabilities are being passed around?

I can't help wondering whether the supposed advantage of capability
systems with regard to security flaws isn't due more to the unusually
high caliber of the people developing this software than to the inherent
superiority of the methodology.  Once you have the same sort of people
using capabilities who make the colossal blunders we read about, won't
they find new ways of making mistakes?  As the saying goes, you can't
make any system foolproof because fools are so ingenious.

It might be helpful to make a list of the characteristic errors to which
the various protection mechanisms are vulnerable.

> > > In my tirade against ACLs, one of the points I tried to
> > make is that
> > > an ACL design requires a static security policy. This is a good
> > > example of that. Assuming the existence of an IRS, I may not be
> > > willing to accept donations from unknown strangers. It is
> > impossible
> > > for your "Bank" software to support this feature after it has been
> > > deployed. In contrast, a capability based design, like
> > the MintMaker,
> > > can support this feature unmodified. This isn't a question of
> > > anticipating all possible requirements, but of not being forced to
> > > explicitly code all that is permitted.
> >
> > Right, the code I wrote will allow anyone to make a transfer to your
> > account, and it would have to be changed if you wanted to
> > be able to limit
> > that.  It would not be difficult to change it to require
> > the cooperation
> > of both parties in order for a transfer to occur, but your
> > broader point
> > seems to be that a capability system will in general be better able
> > to deal with changes in the requirements without
> > modification to code.
> > I still don't have enough experience to judge whether this is true.
> This example should be enough for you to judge that this is true. In
> fact, just thinking about the nature of the ACL model should prove to
> you that this is true. In the ACL model, the access check takes place
> at the subject. This means the subject has to perform the access
> check. This means that all access checks must be pre-existing in the
> subject. Every time I bring up a new prohibition, you rush to change
> the subject. How many iterations of this would you like to do? I don't
> mean to be rude, but this is an important point, and I am unwilling to
> let it fall to "only time will tell".

It is true that when we identify a new kind of access which needs new kind
of access permissions, modifications are needed to a basic ACL system.
(It's also possible that proxies and similar strategies can play a role
even in an ACL system.)  But my example was such a tiny one that it made
no pretense of identifying all the sorts of access, so when you ask
for a new kind, I have to add it.  An actual ACL based banking system
(of which there are no doubt millions of installations in the world)
probably has a relatively static set of access types.  I think in that
case it will be much more likely that we can deal with desired features
without having to make modifications to the ACL implementation as I had
to in my small example.

Overall though I think you're right that a "classical" ACL system will
do better if the set of access types (not to be confused with the set of
protected objects) is relatively static.

> > > In this design, the only UID that will ever be able to
> > successfully
> > > invoke the transfer() method is the owner of the
> > "sourceAccount". This
> > > is a huge restriction. For example, I don't see how it would be
> > > possible to conduct even a simple two-way trade using
> > this transfer()
> > > method. I have an amount of currency A, you have an
> > amount of currency
> > > B, we don't trust each other, but we want to trade. The problem is
> > > that it's impossible for the principal to delegate
> > authority over a
> > > portion of his balance to a trusted third party who could
> > perform the
> > > trade. The MintMaker of course supports this functionality.
> >
> > How about if each of us simply pays the TTP using
> > transfer(), and the
> > TTP then pays us the appropriate amount?
> How does the TTP know that you paid and how much you paid? The TTP has
> to perform the transfer itself in order to gain this knowledge. Try
> coding up (or even just thinking about) a Market TTP that does not
> suffer from a confused deputy attack.

I was assuming that the TTP would have some way of knowing when it was
paid, and by whom.  My toy example does not record any such account
history information, but in a "real" banking system such data would have
to exist (and would presumably be needed in the MintMaker as well).
People get paid all the time in the real world in just this way, via
account transfers.  They don't find it necessary to give other people
(limited) access to their own accounts in order to pay them.  Real banking
systems seem to be able to handle this problem without becoming vulnerable
to the kind of confused deputy failure shown in your example.

> > > Since I'm talking about duplication right now, I'll also
> > remind you of
> > > the point I was making to David about the space
> > duplication inherent
> > > in his ACL proposal. The computer's stack and heap
> > already contain a
> > > distributed version of the access table (if designators are
> > > authority). An ACL duplicates these table entries in a
> > reified version
> > > of the access table. Note that there is no equivalent to
> > your many UID
> > > arrays in the MintMaker.
> >
> > But in my case, designators are not authority, are they?
> > My designators
> > are account numbers, which do not grant authority to access
> > the account.
> > So I'm not sure whether this duplication problem applies to
> > this example.
> Surely you can see that the ACL approach requires both the
> distribution of designators and the reification of the access table at
> the subject. In a capability system, the access table exists in the
> space taken by the designators.

Yes, I think I see what you mean, there is an element of redundancy.
I don't fully agree that "the computer's stack and heap already contain
a distributed version of the access table" though.  They only contain
information about which accesses are actually in progress at the current
moment.  The collective ACLs contain far more information than this.
Likewise in a capability system, the set of accesses which are in
existence at any given moment is only a subset of the potential ones
which are allowed by the body of code which exists in the system.

Put another way, each system, ACL and capabilities, has code and tables
which will permit certain accesses and prevent others.  At any given
moment, some fraction of the (hopefully!) permitted accesses will be
in existence.  The fact that these accesses are permitted is implied by
the larger body of code which permitted them.  A given access therefore
embodies two facts: a particular process is accessing a particular
resource; and, that particular access is permitted.  It is this second
fact which is redundant with the ACL information.  However I feel that
this fact is also redundant with a capability system which encodes
permission information in a different way, via code rather than tables.

> Should I, and others, assume that you are in agreement with the points
> that you've deleted from my response? You've chosen to not respond to,
> and delete, some of the more important points, while addressing some
> of the less important ones.

I will try to respond to the mail on the omitted topics soon.

> > > > To allow some of the other features Tyler suggests, let us
> > > > extend this
> > > > example with a list of UIDs which are allowed to read
> > the balance:
> > > >
> > > >     // User IDs of those allowed to read balance
> > > >     UIDlist accessUIDs[];
> > > >
> > > >     // Request balance
> > > >     int getBalance (int account)
> > > >     {
> > > >         // See if this user is allowed public access
> > > >         if( ! accessUIDs[account].contains( getuid() ) )
> > > >             return ERROR_INVALIDACCESS;
> > > >         return balance[account];
> > > >     }
> > >
> > > At this point, we can really start to see the exploding size and
> > > number of the ACL lists.
> >
> > Yes, you'd need to have a different list for each kind of
> > authority you
> > choose to grant, and for each resource that is protected.
> > I'm not sure
> > this necessarily should be called an "explosion", though.
> > After all,
> > in a capability system, you'd have a different capability
> > for each kind
> > of authority and for each resource, but I'm sure you'd
> > agree that this
> > does not represent an explosion of capabilities.
> The explosion comes from the complexity of checking the authorization
> procedure. In a capablity design, this check is carried out in tandem
> with the distribution of the designator. By holding onto the passed
> capability, the clients effectively cache the intermediate results of
> this authorization procedure. In an ACL design, you have to check the
> entire authoriziation procedure from start to finish on each
> invocation. The complexity of the checking code is proportional to the
> complexity of the distribution method of the designators. It's really
> nasty if there are multiple possible authorization procedures.
> Your getBalance() method is the first in your ACL design that is
> forced to deal with more than a simple one-to-one authority pass, and
> so is the first to experience ACL explosion.

Earlier you said we would see an explosion in size and number of
ACL lists.  Now you clarify that it is the complexity of checks which
is exploding.  I don't know if either is necessarily true, but certainly
this toy example can't establish the case.  A one line check in getBalance
is a pretty small explosion.  We would need to look at actual ACL systems,
such as bank account systems, to see whether they explode.

One of the strategies used in ACL systems to reduce complexity is to
group processes and apply permissions on a per group basis.  This is often
a very natural way to organize users and processes.  You seldom need or want
to decide access on the basis of the individual process ID, rather you can
use the groups of which it is a member.

> > > > For other features Tyler mentioned like giving my
> > > > accountant the ability
> > > > to read my account history, a similar mechanism would be
> > > > used: introduce
> > > > a new UIDlist for the required permission and check that
> > > > the user ID of
> > > > the requestor is in that list.
> > >
> > > So, do you see how the introduction of additional roles
> > is changing
> > > the actual code for your HalMint, not to mention making it
> > > significantly more complicated? In a capability based
> > design, all you
> > > have to do is let POLA be your guide and make your capabilities as
> > > primitive as possible.
> >
> > It seems to me that some of the same problems arise with capability
> > systems, but you don't count them the same way.  In Mark's
> > original example
> > at http://www.erights.org/elib/capability/ode/
> > ode-capabilities.html#simple-money
> > there is no provision to make the purse balance visible to my
> > accountant. If I give him the capability to the purse, he gets too
> > much power.
> >
> > So I can solve this by creating a new object, a "publicPurse", which
> > holds a pointer (capability) to my purse but which only exports a
> single
> > function, getBalance().  I give a pointer to this object to my
> accountant.
> >
> > New code had to be written to accomplish this task, just as in the
> > ACL example.  But in my case, you counted it as a change to the code
> > and an increase in complexity.  In the capability case, you don't
> seem
> > to count it.
> As Zooko picked up on, its a question of where that new code goes.
> Your ACL solution requires modification of the subject to protect a
> previously unprotected authority. (Hi, David) Whose to say you even
> have the ability to modify the HalMint code? As a user of the HalMint,
> you don't have the ability to change the HalMint.

That's true, and I agree that it can be an advantage to be able to
make these kinds of changes dynamically.  As a programmer I apprecate
the ability to do so.  But what about the average end user?  He's not
going to write code.

One case where I could see this methodology being useful would be if you
had one party providing the base code, and another party customizing it
for an end user.  The customizer could have more flexibility in being
able to modify the behavior of the underlying system, and that would be
good.  However, there's a problem:

> > Yet this code is just as security-critical as the code in the Mint.
> No, it's not. That's the kicker. This prohibition has absolutely
> nothing to do with the proper functioning of the Mint. The Mint is
> only there to ensure that money is neither created nor destroyed
> during transfers. Your ACL design is putting additional requirements
> on the Mint code, and therefore, making it more complicated.

I don't agree that the added code is not security critical.  It's true
that, by the narrow definition of what the Mint does, added code can't
break that if the Mint is properly designed.  But from the end user's
perspective, it is just as important that the add-on code work properly
as for the underlying Mint.  Recall that in this case the add-on was
going to filter the Purse and provide a read-only facet for a third
party.  Obviously if it screws up it could provide a more powerful
capability instead.  That would be disastrous from the POV of the end
user, even though mathematically the Mint was still working perfectly.
If his account is drained he won't care much that the Mint did its job
of ensuring that money was neither created nor destroyed.

>From the end user's perspective, you are expanding the TCB to include
the add-on code.  By facilitating and encouraging modifications in this
way, you gain flexibility at the possible cost of new security holes.
In some contexts this is an appropriate tradeoff, but in others, such
as financial applications, it may be very risky.  It might actually be
better to use a program development methodology which concentrates the
security critical code in one place than one which spreads it out into a
bunch of filters and proxies that can run anywhere.  Maintenance, audits
and security reviews will be more manageable if everything is together.

> >  If
> > you make a mistake, you could be giving too much power to your
> accountant.
> > If you give this capability to the wrong person by accident, you are
> > giving away power you didn't mean to give.  Adding the new
> capability
> > increases the amount of security-critical code and it increases the
> > overall complexity in terms of managing capabilities properly.
> The complexity I was talking about is adding checking of the entire
> getBalance() authority flow to the Mint, where it doesn't belong. The
> capability design isolates this new code away from the Mint.

You're talking about one type of complexity, I'm talking about another.
In gaining the simplicity of keeping the Mint code unchanged, you are
trading off the complexity of having a distributed body of code that you
have to verify.  And even if this code is correct, the management task
for the end user may be increased.  He (perhaps) has to be cognizant of
the fact that he has two capabilities, one which lets someone read his
purse balance and one which lets them modify it.  He has to be sure he
sends the right one to the right person.

Of course ideally much of this can be hidden by proper UI design.
Has there been much work on how a multi-capability system can be best
presented to an end user?  I would speculate that in shifting access
control from the core of the system to the periphery, you risk make the
user's job more difficult.  But I have no idea whether it would work
out that way or not.

> > > Your ACL design gives the illusion of it being easier to add this
> > > feature because it already contains the overhead of keeping a list
> of
> > > all the outstanding accounts. The MintMaker does not impose this
> > > overhead (the MintMaker is vastly more efficient in both space and
> > > time).
> > The overhead was not all the great; the base code was no bigger than
> the
> > MintMaker example (granted it is a toy problem).
> If you write up something that attempts the functionality of the
> MintMaker, the code will be larger. Moreover, the HalMint requires
> storage for all of the ACL lists, and runtime for checking these ACL
> lists. Neither of these are present in the MintMaker.

Well, as I said before, it was a toy example, and the access checks would
probably be a smaller percentage if there were more real work to do.
The true question is whether actual, production systems based on ACLs
have excessive overhead, and whether capability systems will be able to
scale to that point with greater efficiency.  I don't think toy examples
tell us the answer.

> > And the MintMaker has
> > overhead in its own way, in that there must be a capability in
> existance
> > for every purse in the system.  Purses are persistent objects, so
> there
> > is really just as much storage being used for the MintMaker as for
> the
> > design I showed.  I don't see the vast gain in space and time
> efficiency.
> The purses occupy the same amount of storage as your balance array.
> Capabilities are free, they are just pointers. Your ACLs, and the time
> to keep and check them is where the efficiencies are to be made.

The ACLs do take up memory but I claim that the capability system as a
whole embodies the same information in its code, which will take up space
too, as well as requiring time to decide on what permissions to allow
(what capabilities to distribute).  In this small example it looks like
capabilities are more efficient, but I don't know how that will scale.

> > > To add this feature to the MintMaker, you would keep a list of all
> the
> > > created purses in the makePurse() implementation. Another facet on
> the
> > > MintMaker would then allow all of these purses to be assayed. The
> cap
> > > for this facet would be returned at the same time as the "mint"
> facet.
> > Would you be willing to show the code explicitly, as I did for the
> > case?
> define MintMaker(name) :any {
>     define [sealer, unsealer] := BrandMaker pair(name)
>     define all := [  ] toFIFO
>     define mint {
>         to printOn(out) { out print(`<$name's mint>`) }
>         to makePurse(balance : (any >= 0)) :any {
>             define decr(amount : (0..balance)) {
>                 balance -= amount
>             }
>             define purse {
>                 to printOn(out)    { out print(`<has $balance $name
> bucks>`) }
>                 to getBalance :any { balance }
>                 to sprout     :any { mint makePurse(0) }
>                 to getDecr    :any { sealer seal(decr) }
>                 to deposit(amount : integer, src) {
>                     unsealer unseal(src getDecr)(amount)
>                     balance += amount
>                 }
>             }
> 		all += purse
> 		purse
>         }
>     }
>     define irs {
> 		to getBalance(nth : (int >= 0)) : any {
> 			all head(nth) reversed peek getBalance
> 		}
>     }
>     [ mint, irs ]
> }
> I've used the Hydro collection library for my code additions here.
> This library has not yet been integrated into E.

Thanks very much, this helps me to see what is involved.  It is actually
a very small change, which is impressive.

It seems that certain kinds of new security permissions/limitations
require changes to the centralized code, while others can be done by
just adding code outside of the central core.  The former would appear
to be changes that are relatively "universal", like adding a new class of
privileged users (bank managers, say) and giving them some specific access
to all of the purses.  The latter would include changes that can be done
on a per-account basis, where the account owner wants to allow some new
access to his own account.  Does it seem useful to try to characterize
the extensibility properties of capability systems in this way?

Of course in a pure ACL system both categories would require changes to
the central core, which is often a disadvantage but, as I wrote above,
in some cases may actually be preferable.