[noise] Cap'n Proto case (was: Potential redesign?)

[Trevor Perrin]

On Fri, Mar 20, 2015 at 9:50 PM, Kenton Varda <kenton at sandstorm.io> wrote:
>
> I think this is a step in the right direction, but I'm not sure if I see
> quite yet how Cap'n Proto would use this. In our case, with introductions,
> we have a symmetric situation:
> 1) Alice sends messages to Bob and Carol introducing them to each other.
> 2) Upon receiving the introductions, Bob and Carol can immediately begin
> sending messages to each other, without waiting for any round trips.

Sure, let's try to work that out - I think there's a lot of variables,
so some questions:

 - Once Bob and Carol are introduced, do they remember the session and
reuse it when introduced by other parties, or when re-introduced?
 - Is the session specific to a particular resource, or do all
Bob<->Carol communications flow through a single session?
 - This is really symmetric?  Either Bob or Carol can send the first message?
 - Once Bob is introduced to Carol, does he immediately have the power
to introduce others to Carol, or is it OK to require some (how much?)
communication with Carol first?
 - Assuming Alice is passing around Bob and Carol's prekeys for
forward secrecy, would you rather have these be reusable and
time-based (which requires time sync), or one-time-use (more
book-keeping and communication).
 - Do the first messages exchanged between Bob and Carol need as much
forward secrecy as later messages?
 - How long-lived are these sessions?
 - Can Bob and Carol later re-establish sessions on their own?


> I'm not quite sure how to apply any of the handshakes you've specified in
> this symmetric situation -- they all mention an "initiator" and a
> "responder" which appear to be treated asymmetrically.
>
> Would it make any sense to have a symmetric handshake like:
>
>   (i = initial prekey)
>   HandshakeEE(s, i, rs, ri)
>     -> e, dhei, dhes, s, dhsi
>     <- e, dhei, dhes, s, dhsi

If you're imagining these messages are sent simultaneously - not in
sequence - then I'd view that as just two BoxXE messages setting up
two separate sessions (one for each direction):

BoxXE(s, rs, re):
  e, dhee, dhes, s, dhse

(I was assuming Box messages could set up a session (not just
Handshake messages), but this isn't clear in doc.)


> Maybe the above can be simplified because both sides know each other's 's'
> already...
>
>   (i = initial prekey)
>   HandshakeEE(s, i, rs, ri)
>     -> e, dhei, dhes, dhsi
>     <- e, dhei, dhes, dhsi

Yeah, it might also be overkill to use both "prekey" ephemerals and
fresh ephemerals, so you could have Alice provide Bob and Charlie with
each other's static keys and prekey ephemerals, and then both parties
initialize the session as:

Bob:     dhee, dhes, dhse
Charlie: dhee, dhse, dhes

But you still have to figure out handling of prekeys:
 - do the parties automatically exchange a handful of them on connecting?
 - are they time-based?

Also, there's some potential benefit to signing the prekey with static
key, which I'll explain in a separate post.

If you could sacrifice on the forward-secrecy for initial messages, or
your desire for 0-RTT connection, this would be easier, but -
tradeoffs.


> Or perhaps we should make the introducer explicit:
>
>   (A/B/C = Alice/Bob/Carol)
>   (sX = static key of X)
>   (eXY = ephemeral public key of X used in session with Y)
>   (n = random nonce generated by Alice)
>   HandshakeABC
>     A->B (preexisting session) sC, n, eCA
>     A->C (preexisting session) sB, n, eBA
>     B->C n, e, dhe(eCA), dhes, dhs(eCA)
>     C->B n, e, dhe(eBA), dhes, dhs(eBA)
>
> In other words, the session between Bob and Carol initially uses the
> ephemeral public keys originally used with Alice, and then switches to new
> ephemeral keys as soon as they are received.

I think that would make it hard to destroy your old ephemerals though,
if you're expected to use them for introductions.


> Also, forgive my noobishness, but I'm not quite sure I understand from the
> document how the PRF chain interacts with streams moving in both directions.
> Is there just one PRF chain for both streams,

For the Handshake** messages I'm assuming yes - there's one PRF chain,
and the messages are ordered, and chained together.

The earlier Noise pipe assumed that after the handshake, the chain
would be "forked" into sending and receiving directions for
bidirectional streams.

I assume we'd still want that capability, but perhaps we could have
other post-handshake options - if this is used with a request/response
protocol, you could keep using a single state to process messages, or
you could switch to a more complex ratcheting protocol like Axolotl.

So I think the post-handshake part of the design remains unclear,
though we could try to make it more general.


> with some sort of ordering
> defined between messages in opposite directions, or is there a separate PRF
> chain for each direction? In the latter case (which is highly preferable),
> how does the responder's ephemeral key get integrated into the sender's
> outgoing PRF chain, and how does the responder know when this has happened?
> For instance, in HandshakeXE, I assume that the initiator's messages should
> eventually be encrypted in a way that integrates the responder's ephemeral
> key, but clearly this cannot start happening until one round trip has
> completed. It's unclear to me how the initiator signals to the responder
> that it has completed the handshake and integrated the responder's ephemeral
> key.

After the initiator receives the responder's message, the initiator's
PRF chain will have integrated all the DH results, so the next message
the initiator sends will be based on those, thus "confirming" that the
handshake was completed successfully.


> I also have a more abstract and opinionated question: In Cap'n Proto's case,
> the "static" keys are per-process. A process generates a new key when it
> starts up and that key never leaves its address space. Moreover, we
> encourage process lifetimes to be limited to a day or less (and in Sandstorm
> we will actually have forced restarts).

Hmm, I don't understand how you're going to bootstrap trust - if
parties are choosing new static keys every day you obviously can't
configure any static trust relationships.

Is there going to be some sort of PKI or something?

Trevor