[cap-talk] What Horton cannot do? (Was: mailkey: transfer of accountability...)

[Jed Donnelley]

At 04:23 PM 6/3/2007, James A. Donald wrote:
>Jed Donnelley
>  > > > Uh - but the problem is solved.  Before it wasn't.
>  > > > That seems to me a huge contribution.
>
>James A. Donald:
>  >> Solved in the sense that is important to
>  >> mathematicians. I don't think that Horton is a
>  >> solution that should be very interesting to
>  >> engineers.
>
>Jed Donnelley
>  > Do you mean in the sense that there isn't a
>  > significant market for object/capability systems where
>  > Horton could be deployed?
>
>I think that deploying capabilities through Horton would
>burden them unduly, and adversely impact the performance
>and comprehensibility of the system, with adverse
>consequences for the user interface.

I'm not sure about the "unduly" part.  Firstly as we've
noted, we believe the Horton sort of responsibility
delegation would only happen rarely in capability
systems.  Rarely relative to the vast bulk of capability
communication without responsibility delegation.
We imagine that a responsibility delegation protocol
such as Horton would only be used for communicating
permissions between high level entities/identities
such as people.  I previously mentioned the "give and
take" directory structure that we used at LLNL for
many years to allow capabilities to be communicated
between people.  I believe that facility would be
enhanced with responsibility tracking such as what
Horton provides with negligible negative performance
impact and with no change to the user interface.

I'm sure Horton could be deployed in such a way as
to negatively impact performance and user interfaces,
but with at least one example in mind where there
would be no significant negative impact in either
area, some value add deployment opportunities seem
available.

>  > However, if you are suggesting that the solution is
>  > for some other reason impractical (with two reference
>  > codings), then I would like to hear what your concerns
>  > are.
>
>No you would not like to hear, for I have been
>expressing my concerns, and you do not appear to have
>heard.

It's really difficult for me to know how to respond to
a statement like the above.  It seems to me confrontational
to no positive (e.g. communication) effect.  You notice
in the above that I limited my question to "practical"
concerns as I clarified earlier in my message.  You
then noted above your concern about performance.  I
believe I answered that legitimate concern.  Do you
think there is a chance we can make even limited
progress like that without your telling me what I
would and would not like, that I haven't read and
need to think more about what you've written, and
other such confrontational but otherwise uncommunicative
statements?

>Jed Donnelley
>  >> Repeating from my June 2nd post:
>  >> : :     Let us consider the application of this to
>  >> : :     some real world cases.
>  >> : :
>  >> : :     Let us suppose we manage to get in place an
>  >> : :     email system where all email is authenticated
>  >> : :     by a public key, but...
>  >> : :
>  >> : :     [...]
>  >> : :
>  >> : :     In this situation, what does Horton buy us
>  >> : :     that Rob Meijer's proposal, plus
>  >> : :     authentication does not buy us?
>
>   Jed Donnelley
>  > I don't think Horton contributes anything to that
>  > situation.
>
>Yet it is the problem that Horton is supposed solve.  In
>the scenario, each person issues other people
>capabilities to bypass his spam filter.

I don't believe that is what we designed Horton
to address.  As we've noted, if there is direct
communication available (without a responsibility
transforming filter) then of course capabilities
may be communicated directly.  We imagine this to
be by far the most common situation.  Did somebody
suggest using a mechanism like Horton to limit
the creation of identities ("spammers promptly issue
themselves several billion keys") or to block
communication of capabilities ("Anyone in my social
circle can give one of these authorities to contact
me to anyone in his social circle").  I don't
see Horton as being applicable to these issues
(e.g. dealing with communicating conspirators).

Let me give a simple example of what Horton
is focused on:

Let's say we have a capability for setting off a
fire alarm.  We believe all occupants of the
building should have permission to set off
the alarm.  However, we want to know who
set off the alarm in case there is a false
alarm set off so we can know who to blame.
We may choose to revoke that persons capability
to set off the fire alarm if they abuse the
capability (crying "wolf").

In this case every time there is a new
occupant of the building we use Horton
to delegate them a new instance of the
capability to set off the fire alarm with
their identity labeled as responsible.

When a fire alarm is set off, the request
will come with an identity label.  It may
well be that the person identified by the
label either intentionally or unintentionally
allowed the capability labeled with their
identity to fall into the control of another
person.  This could easily happen.  Suppose
some person implemented a directory server with
nice features that a building occupant
decided to use.  They even used it to store
their fire alarm capability.  We consider
it very (!) unlikely that communication to
and from a directory server would use
the Horton sort of responsibility delegation.
In that case the fire alarm capability stored
in the directory server would be labeled
as the responsibility of the user of the
directory server, and not as the responsibility
of the programmer/admin for the directory
server.  If that programmer/admin had access
to the internal capability store for the
directory server and abused that access, they
could set off the fire alarm and, in effect,
blame the directory server user.

All Horton does is to provide a means for
doing responsibility transforming communications
(what we refer to as delegation responsibility)
of capabilities.  It doesn't limit in any way
how such transformations may or may not be used.
The 'trick' in Horton (the main reason beyond
the base idea to publish the paper) is insuring
that the sender only has access to the capability
that they are responsible for and the receiver
only has access to the capability that they
are responsible for (at least until after
they communicate via Horton).

We hope the building residents don't give their
fire alarm capability to their Solitaire program
(POLA), but that is an issue separate from Horton.
People in the build could chose to delegate
the permission to set off the fire alarm - e.g.
to others outside the building.  When such an
alarm capability is used, it would be labeled
as "Alice delegated to Bob" where Bob might not
be a building resident.  No problem.

>If you say Horton does not contribute anything to that
>situation, it seems doubtful that it contributes
>anything to most such situations.

As I hope you see above, it doesn't.  Whether it
contributes anything of value to any situation will
of course be up to anybody choosing or not choosing
to implement Horton (beyond MarkM's E and Joe-E
reference implementations) or to read or think about
it to decide.  It's already provided considerable
value to me and to others in the meetings discussing
it (e.g.:

http://www.webstart.com/projects/delegating-responsibility/HP-2006-12-01/markm-jed-dr-draft.jpg
http://www.webstart.com/projects/delegating-responsibility/HP-2006-12-01/chip-billf-other.jpg
http://www.webstart.com/projects/delegating-responsibility/HP-2006-12-01/mengw-normh.jpg
http://www.webstart.com/projects/delegating-responsibility/HP-2006-12-01/tyler-marcs-markm-horton1.jpg

) and to many on the cap-talk list.  Of course we hope
our paper is accepted for publication.  It will be
disappointing if that's as far as it goes, but you
never know.  I was quite surprised that the basic
concept in my Distributed Capability Computing
System (DCCS):

http://www.webstart.com/jed/papers/DCCS/

went over 10 years without a serious implementation.  I went
on to use capabilities as data designs in my OS work, so I
didn't need it.  Then some people working on Mach reinvented it:

Dan Julin. Network Server Design, Mach Networking Group, September 1989.
http://www.cs.cmu.edu/afs/cs/project/mach/public/www/doc/abstracts/netmsgserver.html

I don't know if MarkM's "vat" design was independent or not
(MarkM?), but you see the same idea showing up again -
now at least three times over a 30 year time spam.  I consider
that concept to be contributing something.  About Horton,
we will just have to wait and see.  We certainly have no
near term implementation plans.  I hope Mailkey provides
a more immediate contribution.  Do you have publication
and implementation plans?

>James A. Donald:
>  >> So here is the same solution in general terms.
>  >>
>  >> Assume a system such as Zooko's triangle, where all
>  >> entities have public private key pairs...
>
>Jed Donnelley
>  > I'm not sure, but I don't think we have the same view
>  > here.  What do you mean by an "entity"?
>
>Something or someone that controls the corresponding
>private key.  An entity is identified by its public key
>(or hash of its public key), and url or urls by which it
>may be contacted.
>...
>  > If so then I think there is an important distinction
>  > between levels being missed in here somewhere, perhaps
>  > by me though of course I don't see it.  The importance
>  > of Horton lies in the fact that the communicating
>  > entities are active objects (A, B, and C) while the
>  > responsible parties are "identities" (as provided by
>  > the sealer/unsealer pairs, but that we use the
>  > suggestively anthropomorphic names of Alice, Bob, and
>  > Carol for).
>
>I don't see these levels as significant in this context,
>and "significance" is only meaningful in the context of
>real world scenarios, with realistic adversaries.

I described a real world scenario above in the
LLNL "give and take" directory structure.  In that
situation we would imagine that capabilities in the
home and "receive" directories for people would typically
be labeled as the responsibilities of those people.
However, one person, Alice, could choose to
communicate a capability labeled as her responsibility
directly to Bob (not through Horton).  In that case
Bob's invocations would be logged as the responsibility
of Alice.  Bob would not (we hope) receive access to
Alice's "Be Alice" capability (essentially her private
key) and so couldn't act for Alice in general, but
Bob could invoke the capability that Alice
communicated directly with the "Alice is responsible"
label.  Bob may also have capabilities labeled as
"Alice delegated to Bob".

The distinction between active objects (processes,
e.g. deputies) and identities is vital to the
scenarios where we imagine Horton to be useful.
People will likely have identities and some few
active objects may act with the full authority
of people (have their private keys), but most
active objects will only act with some number
of permissions (capabilities) that may be labeled
as the responsibilities of zero, one, or more
people.

>Suggest some realistic scenarios, some of today's
>problems that need solving today, as I have done.  Posit
>a real world scenario where it makes a significant
>difference whether we pass capabilities by the Horton
>mechanism or by secret sharing.

I described the real world scenario that we had at
LLNL.  Unfortunately I don't know of many real world
situations these days where capability communication
is done.  Maybe Alan could comment about whether or
not Horton might prove useful in a situation like
CapDesk.  I don't imagine Horton would be useful
with systems like Polaris or Plash - as those systems
are build on top of traditional ambient authority
systems that already have identity notions build in.
Horton also requires an identity structure to be
useful.  I wouldn't imagine Horton to be useful,
for example, for wideword or the Web Calculus at
this point because there is no readily available
identity mechanism that could be used for those
applications.

>  >> If each key is unique, as is typically the case with
>  >> electronic keys used in office security systems, then
>  >> the owner of a key will be disinclined to share it,
>
>  > Disinclined perhaps, but the owner must necessarily
>  > share the private key (unsealer) with any software
>  > acting with the authority of the owner's identity.
>
>If your unsealer is trojaned, Horton does not help -
>indeed nothing helps.

Of course.  Perhaps we have the same view here?  As
I noted, we imagine Horton only being used for relatively
rare responsibility transforming communication of
capabilities between rather high level identities,
like people.  It's only during such transformations
that the private keys (unsealers) come out to effect
the transformations and then with very controlled
software under controlled situations.  After that
the capabilities with the resulting labels are
shared generally according to POLA - without doing
responsibility delegation.

>  >> whereupon knowing what key opened the lock is in fact
>  >> sufficient information.
>
>  > You lost me with the above.  Sufficient for what?
>  > Sufficient to attribute responsibility to an identity?
>  > How?
>
>Think about it.  Seems perfectly clear to me.

Such is always the case when listening to oneself.
In future I'm going to simply delete such insults
with no communication content.  It doesn't mean
that I'm not reading them and taking offense (insult
away if that's what you wish), it just means that
I'm trying to be polite in responding.  That will
save us both a lot of reading and writing (e.g. what
you don't see below).

>  >> Of course, there is lots of stuff that can only be
>  >> done, or is simplest to do, by passing out keys, by
>  >> delegating capabilities.
>  >
>  > Hmmm.  From my viewpoint those two clauses above:
>  >
>  > 1.  PASSING OUT KEYS (even at that you don't specify
>  > whether they are public keys, private keys, or some
>  > other sort of key such as a metaphoric key in the
>  > sense used in the KeyKOS documentation) and
>  >
>  > 2.  DELEGATING CAPABILITIES.
>  >
>  > are very distinct operations.  If you feel that they
>  > are identical (that is that delegating capabilities is
>  > accomplished by "passing out keys"), then I'm afraid
>  > I'm lost.
>
>For concreteness, and without loss of generality, assume
>a capability is a secret unguessable url.

Fine.  The only slight loss of generality may be
confinement.  I won't worry about that (as I haven't
in many of my implementations).  Such unguessable
URLs are showing up more and more often such as
with Tyler Close's Web Calculus and with Widewords.

>An unguessable secret that enables one to do something is
>ordinarily called a "key" - thus a capability is a
>particular kind of key.

As long as you acknowledge the distinction between
such a "key" (used above in the KeyKOS sense) and
that term used when describing an encryption key.
If I sign a message "I appoint James A. Donald as my
executor." with my private encryption key and send you
that message, I have not given you an encryption
key, but I have given you a permission - a "capability."
Calling that message a "key" is confusing in some
contexts - which is why that terminology hasn't had
continued usage.  I'll try to make sense out of what
I believe to be your overloading of the "key" term.

>Several different such keys -
>one issued to Alice, one issued to Bob, may well do the
>same sort of thing, thus are similar capabilities.  Thus
>with Horton Alice causes a capability similar to her own
>to be issued to Bob, she is sharing a capability in one
>sense, but in another sense, causing a new capability to
>be issued.  In this second sense, the word "key" is more
>meaningful.

I believe the "key" term is more ambiguous as noted above,
though I follow what you said in the above paragraph.
...

--Jed  http://www.webstart.com/jed-signature.html