Fw: EROS: expressibility question

[shapj@us.ibm.com]

Jack:

I apologize that it has taken so long for me to reply.  IBM has been gearing up
for our "fall plan" process, which is when we decide what to fund next year, and
I have been frantically working on proposals.  Here are some answers to your
questions, some of which we may want to go back and forth on.

> Also would you appreciate typo reports on essays? some minor ones "the"
> for "they" etc.

All corrections are welcome.  Anything that makes this stuff easier to read and
internalize is a benefit, and is appreciated.

> Also any chance on putting a simple summary of the EPL next to it as on
> the GPL preamble or the QPL (Qt TrollTech license). Helps us lay folk.

It's a good idea.  It is possible that we will simply switch to GPL, so I'm
holding off on "improvements" to the current license until that is decided.
Thanks for the suggestion.

> I read alot of the docs both on the eros site and linked to it, and am
> still having a problem with one aspect: how to enforce expressibility.
>
> Specfically: how to efficiently determine whether a number is a legitimate
> capability or not. What prevents the agent from making something up? Is
> crypto that efficient?

If you are asking about how EROS handles this, then there is a basic confusion.
Rather than try to guess what you asked, let me answer both how what you ask is
done and why in EROS it is not necessary to do this. If I am unnecessarily
tutorial in doing so, please forgive me.

Given that you have decided to build a capability system, the most basic
requirement is that capabilities should not be forgeable.  That is, it should
not be possible for an application to simply "make one up" out of whole cloth.
There are four basic techniques for achieving this:

sparsity:  capabilities are chosen out of a large space (say 128 bit integers)
in a well-randomized fashion.  Because of the size of the space it is very
difficult to guess them.  This solution is subject to guesses with a low
probability of success.

encryption: capabilities are encrypted using some sort of public key technology.
To be valid, the capability must decrypt successfully when the system (or the
service) uses the private key.  This technique is also subject to guessing, but
encrypted capabilities are generally much larger than sparse capabilities, and
guessing them becomes correspondingly harder.

partitioning: capabilities simply never live in the application's data area, and
the application has no ability to directly write them.  In consequence, guessing
is impossible.  Even if you get the bits right, you can't cause them to be
interpreted as a capability.

tagging: the memory has an extra bit attached to each word indicating whether or
not that word contains a capability.  The tag bit is maintained by the hardware,
and attempts to write data values at that word cause the bit to be turned off by
the hardware.

EROS is a partitioned capability system.  In consequence, capabilities cannot
simply be "invented".  No crypto is involved -- protection is assured by the
operating system.


Please let me know if you would like me to expand on this.

Jonathan S. Shapiro, Ph. D.
IBM T.J. Watson Research Center
Email: shapj@us.ibm.com
Phone: +1 914 784 7085  (Tieline: 863)
Fax: +1 914 784 7595