20 January 1998

    Date: Mon, 19 Jan 1998 23:53:25 -0800
    From: Wei Dai <weidai@eskimo.com>
    To: cypherpunks@toad.com
    Subject: PipeNet description

    I just got a couple of requests for information about PipeNet and I
    realized that I never did make my final description of it public. The
    attached informal write-up was done shortly after Crypto '96 as a result
    of discussions with Hal Finney, David Wagner, and Eric Hughes. I haven't
    worked on it since then, mostly because the Onion Routing project is doing
    similar work and appears to be much better funded (I did send them a copy
    of this write-up per their request).

    ---

    The Model
    Consider a network of processors which send messages to each other
    asynchronously.  We assume that each node is identified by its public key,
    and that links between nodes are secure.  The adversary may control a
    fixed subset of the nodes.  However all messages between any two honest
    nodes are confidential and always arrive (unmodified) in the order sent
    (this can be achieved with a standard transport level security protocol).

    The Protocol
    The protocol is based on the idea of virtual link encryption.
    After an anonymous connection is established, the originating node sends a
    constant stream of (constant size) packets to a second node at a fixed
    rate. The second node shuffles the packets it receives during a time unit
    and forwards them in random order to others.

    A connection is a path in the network.  The first node in the path is the
    caller, and the last node is the receiver.  The rest are called switches.
    Anonymity in this scheme is asymmetric - the caller is anonymous, but not
    the receiver.  Each node in the path shares a key with the caller and
    knows the nodes immediately in front of and behind it.  Every pair of
    adjacent nodes shares a link id.

    Each switch in the path therefore has a key and two associated ids.  Call
    the id that it shares with the previous node (the one closer to the
    caller) type A, and call the other id type B.  For each id, the switch
    expects exactly one packet tagged with that id in each time unit.  When it
    receives a packet tagged with a type A id, it decrypts that packet with
    the associated key, tags it with the corresponding type B id, and forwards
    it to the next node.  When it receives a packet tagged with a type B id,
    it encrypts the packet with the associated key, tags it with the
    corresponding type A id, and forwards it to the previous node.  The
    forwarding is always done at the end of the time unit, and the order in
    which packets are sent is random.

    For each packet going from the caller to the receiver, the caller must
    multi-encrypt it with the keys it shares with each of the nodes in the
    path, starting with the receiver.  It then sends the packet to the first
    switch tagged with the appropriate link id.  Each switch will strip a
    layer of encryption and forward the packet to the next node.  For a packet
    going from the receiver to the caller, the receiver encrypts it with the
    key it shares with the caller and sends it to the last switch in the path.
    Each switch will add a layer of encryption and forward the packet to the
    previous node.

    To establish a connection, the caller (N0) performs the following steps:
    1.  Select a node (N1) at random and establish a key (K1) and link id (S1)
    with N1.
    2.  Select another node (N2) at random.
    3.  Request that N1 establish a link id (S2) with N2.
    4.  Establish a key (K2) with N2 through N1.
    5.  Request that N1 use K1 to decrypt all messages tagged with S1, tag the
    decrypted message with S2 and forward them to N2.  Also request that N1
    use K1 to encrypt all messages tagged with S2, tag the encrypted messages
    with S1 and forward them to N0.
    6.  Repeat steps 2 to 4 l-2 times.  (Name the i-th node, key, and id Ni,
    Ki, and Si respectively.)
    7.  Repeat steps 2 to 4 a final time, but with the receiver node (Nl)
    instead of a random node.

    Timing
    We assumed earlier that communications links between honest nodes are
    vulnerable to delay attacks.  Therefore we must ensure that link delays do
    not reveal traffic information.  Each node expects one packet from each
    link id in each time unit.  Extra packets are queued for processing in
    later time units.  However, if it does not receive a packet for a link id
    in a particular time unit, it stops normal processing of packets for that
    time unit and queues all packets.  This ensures that any delay is
    propagated through the entire network and cannot be used to trace a
    particular connection.

    The process of making and breaking connections must also not leak
    information.  This can be done by using a protocol analogous to mix-net.
    Link forming/destroying requests are queued and performed in batches in a
    way similar to queuing and mixing of e-mail in a mix-net.