ReFresco 05: Rationale on using caps as reply-to addresses
==========================================================

A number of times in discussions of Caprice, people have questioned
the use of caps as reply-to addresses for method calls requiring
responses, and in general for messages requiring error reporting.  In
particular, people have wondered why we don't tag messages calls with
simple sequence numbers (like CORBA does), and expressed doubt and
confusion at my implication that Caprice clients may create and throw
away caps on every method call.  So, I want to give a canonical
response to these concerns.

I suspect that often a cap will be thrown away after receiving a
single message, yes.  I know, I know, this sounds horribly wasteful.
But it's not like caps are in short supply; there are quite a few
bitstrings out there, after all.  (If caps were in short supply, is
wouldn't just be an engineering annoyance, it would be an immediate
security hole.  So I don't feel bad about depending on their
plentitude.)  Besides which, it's the right way to do things.

Let me expand on this.  Fundamentally, I want to send out a message,
and get back a response.  A security-relevant question is, who do I
want to get a response from?  It isn't good if just anyone can reply
to my message; it doesn't matter how much I trust the recipient if I
can never tell whether I'm talking to them or not.  Essentially, I
want to give the recipient, and only the recipient a new ability they
didn't have before: to respond to the particular message I just sent.
In a capability system, this is exactly what we call "granting a
capability".  So I create a new cap and send it to them.  This has
lots of advantages in terms of simplicity and reasoning about the
system, because the ability to reply follows exactly the same security
model as everything else -- there's no special case.  E.g., the
recipient automatically has the option of delegating their response to
someone else; they just pass along the cap.  (One could think of this
as a variant on the tail-call optimization, I suppose.)

Besides which, let's think about what happens if we add sequence
numbers.  I'll assume that this means that instead of passing a cap
for replies to come to, we're either identifying the request using a
pair (connection, sequence number) or a pair (cap, sequence number).
Let's call this pair (C, S), I don't care which version we use.

Scenario 1: Say I send two messages:
    Me -> Message1(C, S_1) -> Alice
    Me -> Message2(C, S_2) -> Bob  
    Alice -> Reply1(C, S_1) -> Me
    Bob -> Reply1(C, S_1) -> Me  
All is well.

Scenario 2: I send a message to Alice:
    Me -> Message1(C, S_1) -> Alice 
But Alice isn't interested in dealing with it (perhaps Alice is a
fulfilled promise), so she forwards it on to Carl:
    Alice -> Message1(C, S_1) -> Carl           
Who replies:
    Carl -> Reply1(C, S_1) -> Me
All is well.

Scenario 3: I send two messages:
    Me -> Message1(C, S_1) -> Alice
    Me -> Message2(C, S_2) -> Mallory
Mallory has a guess that I've been talking to Alice, and doesn't like
the response Alice is going to give.  So Mallory uses his (legitimate)
knowledge of S_2 to guess S_1, and sends back a mock reply to Alice's
message, before Alice can:
    Mallory -> Reply1(C, S_1) -> Me
As far as I can tell, this is just like Scenario 2, and I trust
Mallory's malicious packet.  I lose.

Conclusion: S_1 and S_2 need to be chosen such that knowing S_2
doesn't help you in guessing S_1.  Obviously we can't use "sequence
numbers" literally; it would work to instead choose S_1 and S_2
randomly, if they're chosen from a large enough space.  4 bytes might
be enough, since there probably aren't many requests outstanding from
a single client at once.  But now you've reinvented caps, just a
parallel, incompatible system of them.  This means special cases
everywhere, etc.  (Think about when Alice wants to delegate to Carl.
She may not want to simply pass the message on directly; perhaps Alice
wants to know about errors encountered in reaching Carl, and insulate
me from them.  So Alice passes my cap in to Carl as a method argument
and sticks some cap of her own in the magic reply-to field.  But if
reply-to caps are different from other caps, then this requires a way
to marshal the special reply-to caps.)