[E-Lang] MintMaker with ACLs

Tyler Close tclose@oilspace.com
Thu, 1 Feb 2001 14:44:02 -0000


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.

> > 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.

> > 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".

> > 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.

> > 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.

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.

> > > 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.

> > > 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.

> 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.

>  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.

> > 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.

> 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.

> > 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
ACL
> 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.

Tyler