[cap-talk] Capabilities for immutable data

Mon Feb 21 22:49:00 PST 2011

David Wagner <daw at cs.berkeley.edu> wrote:
> Condition 1. Suppose there exists a possible implementation M of the first
> component, that will produce (observable) effect E when composed with R.
> In other words, executing M||R causes effect E.
>
> Condition 2. Suppose there exists another possible implementation M'
> of the first component, that will not produce (observable) effect E when
> composed with R.  In other words, executing M||R does not cause effect E.
>
> Consequence 3. If Conditions 1 and 2 hold, i.e., if there exists two
> implements M,M' of the first module such that (...), then we say that
> the first component can cause effect E, when the second component is
> implemented by R - equivalently, the first has authority to cause E.

Okay, I think that I understand the essence of your specfication. Do let me know if I may have got it correctly.

(Principle of Configured Authority) If M and M' are (possibly identical) implementations of a module (or function) such that M can cause effect E on R while M' cannot cause effect E on R, then M has the authority to cause E on R.

The role of this principle in system design is primarily to ensure that security configurations (or decisions) are not hard-coded. Rather, they must be configured at runtime in a manner that is arbitrary and possibly unknown (even) to the entities implementing the module (white-box examination) or to the entities observing one configration of the module (black-box examination). This principle can be seen as an embodiment of Kerckhoffs's Principle (usually associated with cryptography) in the access control land. This can be a neat and fresh start because we could attempt at bridging the islands of access control and cryptography usign an axiom of this form.

Although I can see the utility of this principle in secure system design, I do not see why it should be applicable to capability systems. In other words, how can the gap between "authority" and "capability" be linked? Today, capability is defined informally as a "unforgeable transferable token." Some property of an object is considered as capability according to this definition while we are interested in the effect that this object can cause on a system than in the object itself.

Since you used the tag "permission" in your SMTP-example description and that tag seems to have widely-used semantics in the ACL literature, there is another question to explore. What is the link between "authority" and "permission"? Can there be an intuitive definition possible for this link? This is interesting because it has long been argued, especially in the capability camp of researchers, that capability systems can be used to implement an ACL-type system and more. If we can provide a formal language to the claim, that would be very helpful.

Kapali Viswanathan
Research Scientist, HPL India
http://www.hpl.hp.com/people/kapali/

Knowledge may be some model of things that are visible to intellect. Wisdom may be something that includes even those that are invisible.
-----Original Message-----
From: cap-talk-bounces at mail.eros-os.org [mailto:cap-talk-bounces at mail.eros-os.org] On Behalf Of cap-talk-request at mail.eros-os.org
Sent: Wednesday, February 23, 2011 1:30 AM
To: cap-talk at mail.eros-os.org
Subject: cap-talk Digest, Vol 83, Issue 26

Send cap-talk mailing list submissions to
        cap-talk at mail.eros-os.org

To subscribe or unsubscribe via the World Wide Web, visit
        http://www.eros-os.org/mailman/listinfo/cap-talk
or, via email, send a message with subject or body 'help' to
        cap-talk-request at mail.eros-os.org

You can reach the person managing the list at
        cap-talk-owner at mail.eros-os.org

When replying, please edit your Subject line so it is more specific
than "Re: Contents of cap-talk digest..."

Today's Topics:

   1. Re: Capabilities for immutable data (David Wagner)
   2. Re: Covert channels (Tim Freeman)
   3. Re: Covert channels (was Re: Capabilities for immutable   data)
      (David Barbour)
   4. Re: Covert channels (David Barbour)
   5. Re: Covert channels (Tim Freeman)

----------------------------------------------------------------------

Message: 1
Date: Mon, 21 Feb 2011 02:02:43 -0800 (PST)
From: David Wagner <daw at cs.berkeley.edu>
Subject: Re: [cap-talk] Capabilities for immutable data
To: cap-talk at mail.eros-os.org
Message-ID: <201102211002.p1LA2hC0015986 at taverner.cs.berkeley.edu>
Content-Type: text/plain; charset=us-ascii

Viswanathan, Kapaleeswaran (HP Labs India) wrote:
> First, I would like to rephrase the above description slightly without
> losing its exact meaning. I would then like to put forth my query.
>
> Condition 1. There exists a module M that can produce (observable)
> effect E when part of a system R -- denoted by M||R.
> Condition 2. There exists a module M' that cannot produce (observable)
> effect E when part of the system R -- denoted by M'||R.
> Consequence 3. Therefore, M||R can produce effect E.

Hmm.  That's not how I think of it, so let me try a re-phrasing.

The system consists of two components wired together.  We're given the
implementation of the second component.  Imagine the first component
has not yet implemented.  We want to understand what effects the first
component has the ability to cause, given the implementation of the
second component.  (Imagine that the first component will be written by
Alice, and the second component has already been written by Bob.  So,
Alice controls the code for the first component, but not the code for the
second component.  We want to know what Alice could do, if she wanted.
Therefore, we fix the code of the second component and consider all
possible ways that Alice could write code for the first component,
and use this to explore what power Alice has.)

To formalize this, fix the implementation of the second component, and
let R denote this implementation.  Then, we examine all possible ways
of implementing the first component; M and M' might denote two possible
implementations of the first component.  Now, with those definitions,
suppose we are in situation where the following two conditions apply:

Condition 1. Suppose there exists a possible implementation M of the first
component, that will produce (observable) effect E when composed with R.
In other words, executing M||R causes effect E.

Condition 2. Suppose there exists another possible implementation M'
of the first component, that will not produce (observable) effect E when
composed with R.  In other words, executing M||R does not cause effect E.

Consequence 3. If Conditions 1 and 2 hold, i.e., if there exists two
implements M,M' of the first module such that (...), then we say that
the first component can cause effect E, when the second component is
implemented by R - equivalently, the first has authority to cause E.

Notice the distinction between a component and its implementation?
They are not equivalent.  There are many ways that a component can
be implemented.  It's tempting to use the letter M to represent both
the component and its implementation, but that can be confusing, so
in this note I've tried to be more careful to avoid that.

Example: The second component R is a SMTP server, which accepts email
messages over an incoming TCP connection and writes the email message
to the appropriate user's mailbox file.  The first component is given
permission to open a TCP connection to the SMTP server.  Intuitively, the
first component has authority to cause an email message to be appended
to Janice's mailbox file.  Do you see why?  Let M = an implementation
of the first component which contacts the SMTP server and sends an
email destined to Janice, and let M' = an implementation of the first
component which does nothing.  Let E = the effect of appending a message
to Janice's mailbox file.  Then M||R causes E, but M'||R does not cause E,
so we can conclude the first component has the authority to cause E.

------------------------------

Message: 2
Date: Mon, 21 Feb 2011 10:14:52 -0800 (PST)
From: Tim Freeman <tim at fungible.com>
Subject: Re: [cap-talk] Covert channels
To: rmeijer at xs4all.nl, cap-talk at mail.eros-os.org, capibara at xs4all.nl
Cc: daw at cs.berkeley.edu
Message-ID: <20110221.101452.130581459.tim at fungible.com>
Content-Type: Text/Plain; charset=us-ascii

On Mon, February 21, 2011 03:03, Tim Freeman wrote:
> A lot of covert channels seem to concern time, so if you're trying to
> block them then access to the computer's current time of day should be
> considered security-sensitive.  If you get the operating system to
> only give out the time to highly trusted code, then the services that
> disclose the time of day are going to only work if they're given the
> capability to get the current time.  Minimizing use of that capability
> is going to get rid of that particular covert channel.

From: "Rob Meijer" <capibara at xs4all.nl>
>I'm not quite comfortable with this assertion.

You're arguing with something I didn't say.  I think you do agree that
minimizing ability to access the current time blocks the specific
covert channel that was proposed.  You don't agree that it blocks all
covert channels, but I didn't say that.

>To me the base premise should be that any "incompletely partitioned
>shared resource" could eventually be used as a (covert/side/whatever
>you like to call it) communication channel using some ingenious
>modulation technique.

That's a worthwhile generalization, and I agree.

>That means that if you don't want two entities to be able to communicate,
>you must not allow these two entities access to the same incompletely
>partitioned shared resource. Given the current technology, this is
>currently virtually impossible to do.

I propose to parition all of those shared resources, since it seems to
be necessary for what appears to be a worthwhile purpose.  Maybe I'm
not getting your point yet -- I'd call it "not done yet", not
"virtually impossible to do".  Is there some virtually impossible
aspect to this that I haven't seen?

I mean, I agree that it's difficult in the sense that none of us are
likely to get it done part time in the evenings after finishing our
day jobs.  However, if another Linus Torvalds comes by and make this a
priority like Linux is/was to him, or a real business is created that
employs multiple sane, talented, and committed people doing it for
their day jobs, it would be done in a few years, right?

We don't get there by calling it virtually impossible and stopping
work before starting.  Listing all of the reasons it's virtually
impossible would be constructive.

>I don't think that the assertion that all modulation techniques require
>access to system time to work is proven to be valid.

That's not an argument against what I meant.  I meant:

* The first few covert channels that came to mind used access to the
  system time.
* Therefore restricting that access is an obvious thing to do,
* Restricting access to the system time does protect against the
  proposed covert channel even though I did not explicitly think of it.

This supports the conclusion that the covert channel problem is
solvable since solving some instances of it accidentally solves
others.

First we make a list of the incompletely partitioned shared resources,
then we figure out what to do about each one.

------------------------------

Message: 3
Date: Mon, 21 Feb 2011 10:41:45 -0800
From: David Barbour <dmbarbour at gmail.com>
Subject: Re: [cap-talk] Covert channels (was Re: Capabilities for
        immutable       data)
To: "General discussions concerning capability systems."
        <cap-talk at mail.eros-os.org>
Message-ID:
        <AANLkTik=gCA7Spc7hZdvyrZmQixwq1UPyDoTof47OyUB at mail.gmail.com>
Content-Type: text/plain; charset=UTF-8

On Sun, Feb 20, 2011 at 11:20 PM, David Wagner <daw at cs.berkeley.edu> wrote:
> Before going into the details, let me ask: is this approach intended
> to prevent untrusted code from transmitting on a covert channel, or
> from listening on a covert channel?

I didn't get started with temporal semantics 'intending' to take care
of covert channels. I just wanted a way to coordinate a large number
of concurrent systems that was not vulnerable to disruption,
starvation, or priority inversion. Nor do they take care of all covert
channels (e.g. hash values). That they happen to allow reasoning and
control of a particular class of channels is a useful coincidence.

>
> It sounds like a process can still modulate load, by either busy-looping
> or doing nothing

Indeed. This technique works best if you have a good estimate of how
long actions *should* take, and you regulate their temporal properties
externally rather than trusting the internal properties of the code.
That means it works well for functions and procedures, but not so much
for full processes. Attempts to modulate load won't really affect what
others on the network observe unless you push load to near 100%.

My threat model for untrusted code might be a bit different than you
are imagining. I favor something closer to web-app/service mashups as
the primary model for code distribution, and those are generally not
confined: the shards of code you receive can arrive carrying
capabilities to remote services, to one another, and to common unum
capabilities. You generally aren't worried about "covert channels" in
these cases because the overt channels are nice and wide. Users will
generally have a decent idea of how much information they are willing
to entrust to the web-app providers.

The web-app model covers most of the silly 'toy' examples you might
envision. We don't worry about Solitaire because we're using a
Solitaire web-app. If it needs network access to leaderboards or a
persistence service, it can darn well use something hosted on Google
or Amazon. The storage local to each host is used more for orthogonal
persistence and distributed (or replicated) database services instead
of user-controlled filesystems.

So where does 'untrusted code' come in? Well, obviously the web-app
code cannot be fully trusted. But that isn't a big deal, since the
users aren't under the illusion that it is confined, and they know who
provided it. They can trust the app with not-so-sensitive information.
But there are cases where a web-app might want to grab an algorithm
from some other service as opposed to sending data to the service.
E.g. you don't want to request each letter from your font server
asking for a glyph (as that would leak data to the font service), so
instead you request a huge map of glyphs to process locally.

Ultimately, the sort of code I actually need to confine is usually the
sort of short-running, easily estimated code that temporal semantics
is effective at confining.

Regards,

David

------------------------------

Message: 4
Date: Mon, 21 Feb 2011 10:54:01 -0800
From: David Barbour <dmbarbour at gmail.com>
Subject: Re: [cap-talk] Covert channels
To: "General discussions concerning capability systems."
        <cap-talk at mail.eros-os.org>
Message-ID:
        <AANLkTing9CX1fMZoOAjCZcEwxYT=RxF2xiFhaVGdk6uR at mail.gmail.com>
Content-Type: text/plain; charset=UTF-8

On Sun, Feb 20, 2011 at 6:46 PM, David Wagner <daw at cs.berkeley.edu> wrote:
> Tim Freeman ?wrote:
>> A lot of covert channels seem to concern time, so if you're trying to
>> block them then access to the computer's current time of day should be
>> considered security-sensitive.
>
> I would classify that approach under the category of 'crippling
> the functionality or usefulness of your computer system'.

It wouldn't be a problem if you allowed access to logical time.

I do limit access to even logical time through a capability - albeit,
an unum, which means even untrusted web-app code has access to it. The
reason is more for easy unit-testing than security.

>
> [Time] is used pervasively in network protocols (TCP has timeouts
> all over the place).

If you ever give untrusted code direct access to network protocols,
you clearly aren't worried about covert channels.

Dave

------------------------------

Message: 5
Date: Mon, 21 Feb 2011 10:57:15 -0800 (PST)
From: Tim Freeman <tim at fungible.com>
Subject: Re: [cap-talk] Covert channels
To: cap-talk at mail.eros-os.org, daw at cs.berkeley.edu
Message-ID: <20110221.105715.244762856.tim at fungible.com>
Content-Type: Text/Plain; charset=us-ascii

>1. I would classify that approach under the category of 'crippling
>the functionality or usefulness of your computer system'.

That's plausible.  You'd certainly need a lot of new primitives to
replace access to the current time if you wanted to write something
like TCP.  I'm sure I don't know most of those new primitives, but I
hint at one candidate primitive below.

>2. Blocking an application's access to time of day may successfully
>prevent the application from listening on a covert channel, but it
>doesn't prevent it from transmitting on a covert channel.  The latter
>is a serious problem.

I agree.

Transmitting on a covert channel based on the timing of outgoing
messages would be impaired by getting rid of a primitive like

   Transmit message X now

and replacing it with a primitive like:

   Transmit message X Z milliseconds after message Y was received, or
      fail with a security exception if the specified time has already
      passed.

If the computation that chooses Z and the computation that sent Y
don't have access to the secrets you're trying to protect, and the
security exceptions don't happen often, then maybe with the right
implementation we could arrange for the timing of the message to give
out no information about the secrets.

I don't know whether doing things on a schedule like this would be
crippling in practice.

------------------------------

_______________________________________________
cap-talk mailing list
cap-talk at mail.eros-os.org
http://www.eros-os.org/mailman/listinfo/cap-talk

End of cap-talk Digest, Vol 83, Issue 26
****************************************