Hidden Services over Mix

Logos
1

Hidden Services over Mix

Abstract / Summary

Mixnets already provide sender anonymity, and Sphinx-style mixnets support Single-Use Reply Blocks (SURBs), which can act as anonymous return addresses. If one party can send anonymously and the other can reply through a SURB, then building something similar to Tor onion services on top of Mix might be possible.

This research post will mainly revolve around the question:

Can hidden services be built over a mixnet, and if so, how? And what anonymity guarantees can they realistically provide?

Our motivation comes from provider anonymity in Logos Storage. Anonymous downloads can be supported with the current Mix protocol because the downloader can hide behind the mixnet. Provider anonymity is harder. A storage provider needs to be reachable, needs to advertise that it is serving some content, and needs to respond to clients, of which some might be malicious.

The natural starting point is Tor onion services. Tor already has a somewhat mature protocol for making services reachable without exposing their network location. A Tor onion service publishes a descriptor, establishes introduction points, and communicates with clients through rendezvous points. We therefore studied the details of Tor’s hidden service protocol to understand the reasoning behind each component, and then investigated whether the same approach could be adapted to a decentralized Sphinx-style mixnet using the primitives already available in Mix.

The resulting hidden service over Mix protocol has three sub-protocols:

  1. an introduction protocol, so clients can bootstrap contact without learning the service’s address.
  2. a descriptor protocol, so clients can discover how to reach a service.
  3. a rendezvous protocol, so the client and service can continue communicating anonymously.

This gives us a working Tor-style hidden service design over Mix. See the draft specification here for full details. However, the design is vulnerable to a serious problem. In a decentralized mixnet, paths are typically sampled for each packet from the available mix nodes. If an adversary controls some fraction of those nodes, then every newly sampled path has some probability of being fully malicious. For a long-lived hidden service, this probability accumulates over many client interactions. A malicious client can repeatedly contact the service (or collect SURBs) and wait until the service eventually uses a path (or SURB) controlled entirely by the adversary.

In this setting, this changes the question from:

what anonymity guarantees can a hidden service provide?

to:

How long can a hidden service remain anonymous?

It is therefore possible that Tor-style hidden services may not be directly compatible with decentralized mixnets in this form, and further research is required to address this problem or find an alternative approach if the problem is deemed unsolvable. Tor faces the same problem but the severity is much less for Tor since it uses persistent circuits. Additionally, Tor uses the Guard and Vanguard approach (see Tor spec) for its hidden service. These can help delay the expected time until a fully compromised path is chosen, but doesn’t solve the underlying problem. We are currently investigating the guard and vanguard protocols to understand if they can make such attacks infeasible in practice. Another approach to solving the problem is if some nodes are centralized, trusted, or permissioned, then the fully malicious path problem may become easier to manage, but the system then has a centralization problem instead.

The rest of the document is structured as follows. First, we give a high-level overview of the hidden services over Mix protocol. We then describe the three main protocol components: the introduction protocol, the descriptor protocol, and the rendezvous protocol. Finally, we discuss the malicious path problem in more details, as well as planned future work to potentially limit this problem.

High-level overview

The goal is to adapt the Tor-style hidden services to work in a Sphinx-based mixnet, specifically the Logos Mix protocol. The data flows through the mixnet with help from randomly chosen intermediate nodes called introduction and rendezvous points. With the Sphinx-style mixnet, we have SURBs for replies and we can use them to create a bidirectional connection between a client and a service with rendezvous points in the middle.

Definition

Hidden services extend normal mixnet communication by providing anonymity to both communicating parties, i.e. the sender and receiver. In this sense it provides bi-directional anonymity.

The main additional property of a hidden service is that it allows a service to be reachable without exposing its network location. More specifically, an adversary should not be able to reliably link a service identifier or descriptor to the network identity of the node or nodes operating that service.

An adversary may:

  • Observe some of the network traffic,
  • Control some fraction of peers/providers,
  • Control some fraction of mix nodes,
  • Control some fraction of DHT nodes.

Functional Requirements

  • Nodes are able to anonymously serve data. This requires:
    • An anonymous way for nodes to advertize themselves (e.g. on a DHT) as providers for some service/content/datasets.
    • Clients are able to discover these advertized anonymous services and connect to them anonymously
    • Making contents/datasets retrievable without revealing which node(s) are providing/serving it and which nodes are receiving it.
    • The protocol can support any arbitrary applications (with different payload size requirements) running on top of it.

Workflow

We can assume the following parties:

  • service: the hidden service provider. i.e. a node running the hidden services protocol as a service provider.
  • client: a user seeking a service from a hidden service provider.
  • Discovery/DHT: a discovery network that both services and clients can contact to store and retrieve (key → value) records such as a service descriptor.
  • Introduction points: mix nodes that are chosen by the service as contact points and are publicly reachable (we can assume for now that all mix nodes are publicly reachable).
  • rendezvous points: mix nodes chosen by a SURB user to relay a payload to the SURB creator on its behalf.

Note: a SURB creator is the party that created the SURB (i.e., the Sphinx header), and a SURB user is the party that uses the SURB to send a payload to the SURB creator. Clients and services play both roles since we use SURBs for bidirectional connection

At a high-level, we can summarize the workflow of Tor-style hidden service over mix as follows:

  • Introduction protocol: establishing introduction points
    • Service establishes multiple intro points anonymously through Mix and supplies these intro points with intro-SURBs. These intro-SURBs allow intro points to forward client requests to the service.
  • Descriptor protocol
    • Service publishes anonymously through Mix a descriptor to the discovery (DHT) which contains information needed for a client to connect to the service as well as addresses of intro points to reach the service, and any other metadata needed to bootstrap the connection. Discovery would store the key -> value mapping as key -> descriptor.
    • Service shares a .mix address with clients out-of-band.
    • Client derives key from the .mix address and fetches the descriptor from discovery/DHT.
  • Introduction protocol: Bootstrapping a connection
    • Client contacts the service via one of the intro points, and includes client-SURBs so the service can reply anonymously.
    • Intro point forwards client request to service using intro-SURBs.
  • Rendezvous protocol
    • After receiving the introduction request, the service replies using a SURB-rendezvous connection. This connection mode allows a SURB user to remain anonymous by routing the packet through a random one-time rendezvous point before it is forwarded using the provided SURB. The service’s reply includes service-SURBs that the client can use for subsequent messages.
    • The client and service communicate over an anonymous bidirectional connection. Each message is sent using a SURB-rendezvous connection, and both sides continue exchanging fresh SURBs as needed.

The following figure summarizes the workflow. All communication shown below is assumed to take place over mix. Solid lines denote forward messages, while dotted lines denote backward messages sent using SURBs.

sequenceDiagram
    autonumber
    participant S as Service
    participant IP as Introduction Point
    participant Disc as Discovery/DHT
    participant C as Client
    participant R as Rendezvous

    Note over S,IP: Establish introduction point
    S->>S: Generate intro-SURBs for intro forwarding
    S->>IP: Register introduction point + supply intro-SURBs

    Note over S,Disc: Publish hidden-service descriptor
    S->>S: Build descriptor {service info, intro points, bootstrap metadata}
    S->>Disc: Publish descriptor

    Note over C,Disc: Client lookup descriptor
    C->>Disc: Lookup descriptor 
    Disc-->>C: Return descriptor

    Note over C,S: Bootstrap via introduction point
    C->>C: Generate client-SURBs
    C->>IP: INTRODUCE{request, client-SURBs}
    IP-->>S: Forward INTRODUCE using stored intro-SURB

    Note over S,C: Service replies using client-SURBs
    S->>S: Process request
    S->>S: Generate service-SURBs for direct connection
    S->>R: SURB-rendezvous{client-SURBs, payload{response, service-SURBs}}
    R-->>C: client-SURBs{response, service-SURBs}

    Note over C,S: Direct anonymous bidirectional connection
    loop Ongoing session
        C->>R: SURB-rendezvous{service-SURBs, payload{request, clientSURBs}}
        R-->>S: service-SURBs{request, clientSURBs}
        S->>R: SURB-rendezvous{client-SURBs, payload{response, service-SURBs}}
        R-->>C: client-SURBs{response, service-SURBs}
    end

1. Introduction protocol

The introduction protocol consists of two main parts:

A. the service establishes introduction points.
B. the client bootstraps a connection through one of those introduction points.

Note: the naming convention used in this mix hidden service protocol follows Tor’s onion services protocol for consistency. However, the contents and processing of these messages are different since they are adapted for the Mix setting.

A. Establishing introduction points

Before a service can announce how it can be reached, i.e., before publishing a descriptor, it must establish introduction points. The service provider establishes a set of mix nodes as introduction points. This is done as follows:

  • Select k random mix nodes from discovery to act as intro points. Discovery should support unbiased random sampling from the set of live mix nodes.
  • build k mix paths, where each path terminates at the selected intro points, i.e. intro points become the exit node.
  • Send theEstablishIntro message to each selected intro point.
  • The default value for k is three, resulting in three intro points.

The EstablishIntro message needs to contain the following:

EstablishIntro {
    auth_key: bytes
    auth_mac: bytes
    sig: bytes
}

where

  • auth_key
    The hidden service creates a signing key pair for each intro point and places the public key in the auth_key field. A unique key pair must be created for each intro point, i.e. no key pair is ever used with more than one intro point. These keys are used later to sign the EstablishIntro request. The intro points will use the auth_key as a public identifier for the hidden service and map client requests to the hidden service.
    The auth_key serves as a public identifier for the service at a specific introduction point instead of say a random value/cookie. This is because we want a way for intro points to check ownership of this identifier. i.e. intro points will only associate a public identifier to a mix node after checking ownership of this identifier to prevent unauthorized use of the identifier. The hidden service provider proves ownership of the auth_key by signing the message content using the secret key corresponding to that public auth_key.

  • auth_mac
    The auth_mac field contains a MAC of all earlier fields in the message, and keyed by the shared secret/key s derived from the service and intro point Mix path. Since the intro point is the exit/last hop as stated above, it must have a per-hop shared key material with the service i.e. s under the Sphinx packet construction. Refer to the mix specification for more details on how s is derived. This MAC binds the EstablishIntro request to the specific “session” in which it was sent/received.
    The auth_mac in the message provides a form of replay resistance for the EstablishIntro message by binding the message to the session on which it was created, i.e. the session between the two parties with s as their shared key material.
    Without a MAC derived from a unique session key, an attacker could:

    • Replay the exact same signed EstablishIntro on a different intro point leading to unauthorized registration of introduction points.
    • Cause clients to use attacker-controlled or invalid introduction points.

  • sig
    Contains the signature of all message contents, including auth_mac, using the private key corresponding to the auth_key and the domain separation string "establish intro signature".

On receiving an EstablishIntro message, the mix node will verify the signature sig using auth_key, and verify the MAC auth_mac using the shared key s. The mix node must reject the EstablishIntro message and drop the received packet in the following cases:

  • The key auth_key or signature sig are malformed or unsupported.
  • The signature is invalid.
  • The MAC auth_mac is invalid.
  • The mix node is already serving as an intro point for the same auth_key.
  • The mix node has reached its local capacity for hidden services.

If all checks succeed, then the mix node will serve as an intro point for the hidden service and associate the supplied auth_key with a hidden service state i.e., map auth_key -> service_state. Such service_state contains information needed to relay future client introduction messages to the service such as intro-SURBs and other metadata. The intro point can optionally acknowledge success with an IntroEstablished reply message.

B. Bootstrapping through an introduction point

Client behaviour

To bootstrap a connection to a hidden service, the client first fetches and validates the hidden service descriptor as described in the descriptor protocol. After successful validation, the client obtains a list of introduction points, each containing:

  • intro point information info
  • authentication key auth_key
  • service key service_key

The client then proceeds as follows:

  1. Select a random intro point from the list. Clients select an intro point at random to distribute load.
  2. Generate a fresh client encryption key client_key ( unique one for every introduction attempt). This is required for replay prevention since replay tags are derived from client_key.
  3. Derive the shared secret s_intro using the fresh client_key and the service_key for that intro point.
    s_intro = DH.SharedKey(client_key, service_key)
  4. Derives symmetric keys using a KDF with domain-separated SHA256:
    enc_key = SHA256( "hs intro request encryption key" || s_intro)
enc_iv = SHA256( "hs intro request encryption iv" || s_intro)
mac_key = SHA256( "hs intro request mac key" || s_intro)
  5. Construct the request Request which includes the plaintext application-specific request and client-SURBs for the service to reply. The request should contain enough client-SURBs for the service to then build a SURB-rendezvous connection (see rendezvous protocol section).
  6. Encrypt the plaintext request and create a MAC.
    enc_payload = Enc(enc_key, enc_iv, request)
mac = MAC(mac_key, auth_key || client_key || enc_payload)
  7. Create an Introduce1 message:
Introduce1{
    auth_key: bytes
    client_key: bytes
    enc_payload: bytes
    mac: bytes
}

where the encrypted payload enc_payload contains:

Request {
    app_data: bytes
    client_surbs: [SURB]
}

and send it to the chosen intro point. The sphinx packet containing Introduce1 message must also provide SURBs for the intro point to reply (1-2 SURBs would likely be sufficient).
8. If the introduction point accepts the request for forwarding, it must reply with and ack e.g., IntroduceAck { status: Ok }
9. Missing ack or timeout is treated as failure. On failure, the client may retry with a different intro point, but must generate a fresh client_key and a fresh request (i.e. repeat from step 1).
10. Wait for a service reply coming through the SURBs in the request or timeout and start the process again from step 1.
11. On recieved reply from the service, the client creates a SURB-rendezvous connection for its communication with the service.
12. Pass the reply plaintext to the application for further processing.
13. all subsequent communication is done over the created SURB-rendezvous connection session following the steps in the Rendezvous protocol.

Intro point behaviour

The mix node after accepting the role of being an intro point must maintain a state about the service which includes:

  • authentication key auth_key
  • validity/expiry time.
  • a session/state with the service to forward requests that the intro point receives.

The intro point will then act only as a forwarding node:

  1. check for replays (see replay resistance subsection)
  2. uses auth_key to forward incoming requests to an active hidden-service state using the session/state for that service. If auth_key is not found or expired, then the request is dropped.
  3. send an ack (IntroduceAck) to the client using the provided SURB.
  4. send Introduce2 which is simply the forwarded Introduce1 contents.

Service behaviour

A hidden service accepts intro requests only for intro points that it has previously established. For each intro point the service must maintain a state containing the following:

  • authentication key auth_key
  • service key service_key
  • validity/expiry time.
  • a session/state to receive requests routed through the intro point.

When the hidden service receives an Introduce2 message from an introduction point, it processes it as follows:

  1. check for replays (see replay resistance subsection)
  2. Validate that the auth_key matches the intro point’s assigned auth_key. If not, drop the request.
  3. Validate that the client_key is well-formed, and derive the shared secret s_intro.
  4. Derive enc_key, enc_iv, and mac_key in the same way as the client.
  5. Validate the mac in the Introduce2 message. If verification fails, drop the request.
  6. decrypt the encrypted payload enc_payload and process the plaintext request by local service.
  7. create a session over a SURB-rendezvous connection for subsequent communication (see rendezvous protocol section).

Replay resistance

Replay resistance is required to prevent an adversary from resending previously valid intro messages in order to:

  • DOS/spam the service by repeatedly sending a valid looking intro request message, and possibly consuming all SURBs stored at the intro point (this is dependent on how SURBs are managed).
  • DOS/spam the service by triggering repeated processing of the packet at the hidden service.
  • Consume client-SURBs stored at the hidden service end.
  • Create duplicate application requests.

In this protocol, replay resistance is achieved by the following:

  • Binding to auth_key: the MAC in Introduce1 is computed over auth_key || client_key || enc_payload, therefore, an attacker cannot move a valid encrypted intro payload from one intro point to another or change auth_key without invalidating MAC.
  • Client tags: The intro point and service must maintain replay cache/table of previously seen client tags for each service-intro session/state. These client tags are computed as client_tag = H(client_key). When a request is received by either the intro point or service, they will check the existence of such tag in the local cache/table. If not present, record the tag in the cache/table and continue processing. If present, the request must be dropped with no further processing. The local cache for each service-intro session can be flushed when it expires or gets terminated (i.e. when auth_key is no longer assigned to a service/intro).

Note: these replay preventions are not sufficient for DOS/spam prevention. An additional (pluggable) component is needed for DOS/spam prevention. This will be specified in the future.

2. Descriptor protocol

A hidden service descriptor is a signed object that the service publishes anonymously to the discovery/DHT in order for clients to learn how to reach the hidden service. The descriptor is generated by the service after it has established its introduction points. Publishing the descriptor effectively makes the service available and ready to accept connections.

Remark: we are assuming here that there exists an Anonymous discovery protocol with the following properties:

  • An anonymous way to query the DHT, i.e. the ability to find and retrieve a value that corresponds to the query key anonymously.
  • An anonymous way to publish a (key, value) pair to the discovery/DHT nodes.
  • Discovery/DHT nodes must validate the published (key, value) pair according to the specification in this document.
  • The above might require discovery/DHT nodes to extend the protocol with a specific publish() call, e.g. publish_descriptor().

At a high level, the descriptor requires the following:

  • A persistent service identifier that the service can distribute to clients or publish publicly. This must be derived from a long-term identity key for the service.
  • A deterministic period-specific identifier for the descriptor which can be used as the key in the key -> value mapping used in the discovery/DHT. Such identifier/key must be derived from the long-term identity key for the service together with the current epoch (time period), and should also include public epoch-specific entropy so that descriptor placement is not fully predictable in advance.
  • The descriptor must contain the information clients need in order to reach the hidden service, including intro points and the public keys needed for encryption and authentication.
  • The descriptor must be signed using the derived epoch-specific key to make it time/epoch-bound, i.e. its validity is tied to a specific epoch/time period.

The following subsections describe these requirements in more detail and specify how the descriptor is constructed and published to the discovery/DHT. However, as can be observed, we require multiple keys, therefore, we first summarize their definitions and uses in the following:

  • Identity key (hs_id): A “master” signing keypair used as the long-term identity for a hidden service. This key is not used on its own to sign anything, and only used to generate blinded keys. The public part of this key is encoded in the hidden service identifier (the .mix address).
  • Blinded keys (bk): A signing keypair derived from hs_id and used as the descriptor signing key. For each epoch i a different blinded key bk_i is generated.
  • Discovery key (disc_key): An index in the DHT or DHT-like discovery which maps (disc_key -> value). It is derived from bk_i, epoch i, and public entropy e.
  • Intro authentication key (auth_key): A short-term signing keypair created by the service for each intro point.
  • Service encryption key (service_key): A short-term encryption keypair created by the service for each intro point and included in the descriptor. It is used by the client to encrypt requests toward the service via an intro point.
  • Client encryption key (client_key): A short-term encryption keypair created by the client and included in requests toward the service via an intro point. It is used to generate a shared secret between the client and service when encrypting the request payload to the service.

Note: signing keys are keys generated using \mathsf{Sig.KeyGen()} while encryption keys are generated using \mathsf{DH.KeyGen()}. See the spec for more details.

Hidden service identifier (Mix address)

A hidden service requires a stable identifier analogous to Tor’s onion address. This identifier can then be distributed to clients out-of-band.

The mix address must be constructed using the service long-term public identity key hs_id:

pk, sk <- Sig.KeyGen()
hs_id = pk
checksum = H("hidden-service-checksum" | hs_id)[:2]
mix_add = base32(hs_id | checksum)

where H is the hash function used (e.g. SHA265), pk is the public key generated from a signature scheme with key blinding, and checksum is truncated to two bytes before adding it to mix_add. The checksum is included only to detect accidental errors and does not provide authentication.

Optionally, the human-readable string .mix may be appended:

[mix_add].mix

Periodic descriptor publication

Descriptors must be published periodically to the discovery/DHT network. Every time a hidden service publishes its descriptor, it sets a validity time e.g. 180 minutes (3 hours). The purpose of periodic publication is to ensure that the descriptor is “fresh”.

Aside from this validity time window, we need epochs which decide where the descriptor is stored in the DHT. I.e., the descriptor is stored at different locations over time, so that the same small set of discovery nodes does not remain responsible for the service indefinitely. This makes targeted denial-of-service (DOS) attacks against the hidden service more difficult.

Discovery provides a key -> value mapping, where the key determines the region of the DHT in which the mapping is stored. Only discovery nodes whose identifiers are close to that key (in the DHT space) are expected to store the descriptor. Therefore, that key must be different on each epoch.

The key -> value mapping in this protocol:

  • the value is the hidden-service descriptor.
  • the discovery key (disc_key) is a deterministic epoch-specific value derived from hs_id, the current epoch (epoch), and a public epoch-specific randomness value (e). We’ll discuss later how this key is derived.

Epochs and Descriptor Lifetime

Hidden-service descriptors are bound to:

  • Descriptor epoch: determines which blinded service keys bk and disc_key locations are used.
  • Descriptor lifetime: determines how long a published descriptor remains usable in the DHT before it must be refreshed.

These are simplified versions of what Tor uses and removes all the unnecessary complications, which are not relevant to the Mix setting.

Descriptor Epoch

Each epoch is identified by interval_num and length.

The default length is:

length = 86400 seconds  // 1 day

The interval_num is derived from Unix time. Let L be the period length in seconds, and let t be the current Unix timestamp in seconds. The current interval_num is:

interval_num = floor(t / L)

Therefore interval_num covers the time interval:

[interval_num * L, (interval_num + 1) * L)

Descriptor Lifetime

The descriptor lifetime controls how long a published descriptor remains usable in the DHT cache. After this lifetime expires, DHT nodes should treat the descriptor as expired and no longer return it to clients.

By default, the descriptor lifetime is:

10800 seconds = 180 minutes

Services must periodically refresh/republish descriptors before they expire. Republishing a descriptor does not necessarily change its epoch, it only refreshes the descriptor’s availability in the DHT. To do this, the service samples a random time value between 60 to 120 minutes, and republishes the descriptor to the DHT.

Descriptor Overlap

To tolerate network delays, and clients using slightly different views of time, services should publish descriptors for overlapping epochs. This overlap ensures that a service remains reachable.

Epoch-specific blinded keys

The descriptor requires an epoch-specific discovery key (disc_key), but it also requires the descriptor to be authenticated in a way that is bound to both the service identity (hs_id) and to the current epoch. The protocol uses epoch-specific blinded signing keys (bk) derived from the long-term service identity key (hs_id) using key blinding (see the spec for more details).

Blinded keys
Let epoch_i denote the current epoch. The service performs key blinding as follows:

(sk, pk) = Sig.KeyGen()
hs_id = pk
r_i = H("key blinding" || hs_id || epoch_i)
(sk_i, pk_i) = Sig.BlindKey(pk, sk, r_i)
bk_i = pk_i

The blinded key (bk_i) derivation for clients is defined as follows:

hs_id = decode_base32(mix_add)
r_i = H("key blinding" || hs_id || epoch_i)
bk_i = Sig.BlindPk(hs_id, r_i)

Since epoch_i is predictable, blinded signing keys bk_i can be generated in advance.

Discovery keys
The epoch-specific discovery key disc_key is derived from the blinded public key bk_i, the current epoch, and a public epoch-specific randomness value:

e = get_public_entropy(epoch_i)
disc_key = H("discovery key" || bk_i || e_i)

where e is public epoch-specific entropy, for example a randomness beacon, block hash, or other agreed public entropy source. Including the public entropy e ensures that descriptor placement is not determined solely by public long-term service identity and epoch. This makes the storage location less predictable in advance and reduces the risk that an attacker can precompute and target the responsible discovery/DHT nodes for a future epoch.

The disc_key will then be used to publish or retrieve the descriptor from discovery/DHT. More details on discovery and client behaviour is discussed in the next sections.

Summary
This design provides the following properties:

  • Periodic re-publication of the descriptor with a unique epoch-specific disc_key to avoid DoS attacks (different descriptor location in each epoch).
  • disc_key is bound to a signing key (bk_i) used to sign the descriptor.
  • The descriptor is signed using bk_i and valid only for epoch i.
  • bk_i is be bound to hs_id through key blinding, i.e. ownership of hs_id implies ownership of bk_i.
  • Knowledge of hs_id is sufficient for clients to derive the epoch-specific disc_key for the descriptor and query the discovery/DHT.

Note: if we care about keeping keys offline we can add an additional descriptor signing keys in the same way as Tor. For now we can simply sign the descriptor with the blinded key.

Descriptor components

The descriptor is split into two main parts:

(1) Outer Layer
Contains metadata needed for discovery/DHT nodes to validate it before storing it. This outer layer of the descriptor contains the following fields:

  • validity: an unsigned integer specifying how long (in seconds) the descriptor should remain valid.
  • revision_counter: version counter for the descriptor. Allows the service to revise the descriptor. If discovery/DHT receives multiple descriptors for the same key, it keeps the one with the higher revision counter.
  • inner_layer: An encrypted blob data type containing salt, encrypted data, and MAC.
  • signature: A signature over all previous fields, made using the blinded signing key bk_i for the current epoch i. signature is a tuple containing the pk used to sign and the signature:
    sig = Sig.Sign(bk_i.sk, "mix-hs-desc-outer" || validity || revision_counter || inner_layer)
signature = Signature.new(bk_i.pk, sig)

Signature {
    signing_key: bytes
    sig: bytes
}

We can summarize the content of the outerlayer as follows:

OuterLayer {
    validity: uint
    revision_counter: uint
    inner_layer: EncryptedBlob
    signature: Signature
}

EncryptedBlob {
    salt: bytes
    blob: bytes
    mac: bytes
}

See below for how EncryptedBlob is created and what its contents are.

(2) Inner Layer
An encrypted data blob EncryptedBlob containing the actual connection details needed to reach the service. The encryption provides confidentiality against entities that don’t know the identity key of the hidden service (hs_id) such as the discovery/DHT nodes.

To encrypt the inner layer, we first need to derive a symmetric encryption (stream cipher) key, IV, and MAC key from information known to both the service and client.
First, we generate a random salt and then use it with hs_id, bk_i, and revision_counter to create a shared secret input:

secret_input = "inner layer" || salt || hs_id || bk_i || revision_counter

Then we use a key derivation function (KDF) to generate the needed key materials. For KDF, we use domain-separated SHA256 with the output truncated to 128-bits. Once we have the key material, we can encrypt with a stream cipher e.g. AES-128-CTR, and create a MAC e.g. with HMAC-SHA-256. These schemes are already used by the Mix protocol and can work here as well.

We can summarize the steps to encrypt the inner layer (i.e. the EncryptedBlob) as follows:

salt = random()
secret_input = "inner layer" || salt || hs_id || bk_i || revision_counter
enc_key = SHA256("blob encryption key" || secret_input)
enc_iv = SHA256("blob iv" || secret_input)
mac_key = SHA256("blob mac key" || secret_input)
blob = streamcipher.enc(inner_layer, enc_key, enc_iv)
mac = mac(salt || blob, mac_key)
encrypted_blob = EncryptedBlob.new(salt, blob, mac)

The plaintext of this inner layer contains the following fields:

  • intro_points: A list of intro point objects IntroPoint, each containing:
    • info: A MixPubInfo object containing mix routing information and public key for the intro point. The contents of this object depend on how mix routing is implemented, but in general it should contain sufficient information to create a sphinx packet with the intro point as the exit.
    • auth_key: the authentication key for clients to use at this intro point.
    • service_key: an encryption key service_key for clients to use to encrypt requests for the service, routed through the intro point.
InnerLayer {
    intro_points: seq[IntroPoint]
}

IntroPoint {
    info: MixPubInfo
    auth_key: bytes
    service_key: bytes
}

MixPubInfo {
    peer_id: PeerId
    multi_addr: MultiAddress
    mix_pk: bytes
}

Creating descriptors

To publish a hidden service descriptor, the service will follow these steps:

  1. Determine the current epoch, and the validity time period for the descriptors.
  2. Create a hidden service public identity hs_id and derive the mix address.
  3. Use hs_id to create the blinded key bk_i for the current epoch.
  4. Create a descriptor object with inner and outer layers using intro point information.
  5. derive the discovery key disc_key.
  6. publish the descriptor anonymously to discovery/DHT.
  7. Before the descriptor validity period expires, republish the descriptor. When the epoch changes, derive the new bk_i and disc_key, starting from step 3.

Discovery Node Processing

  • Deserialize, extract the outer layer, and check if the outer layer is well-formed.
  • If the node has a descriptor for this hidden service (i.e. same disc_key), the revision_counter of the uploaded descriptor must be greater than the revision_counter of the stored one.
  • The descriptor (validity) is within the acceptable range of 30 - 720 minutes.
  • The discovery key disc_key is derived correctly from the blinded key in signature.
  • The descriptor outer layer signature is valid.

If any of these outer layer validity checks fail, the discovery/DHT node must reject the descriptor. The descriptor is only stored for the validity time period specified in the descriptor.

Note: Descriptors could pass these checks but still have an invalid inner layer. However, the discovery is not able (not expected) to validate the encrypted inner layer of the descriptor.

Client Processing

The mix address mix_add should be sufficient for clients to query the discovery/DHT and fetch the descriptor. Therefore, clients will extract the public identity key hs_id from the mix address and use it to derive the epoch-specific blinded key.

The process can be summarized as follows:

  • Client receives the .mix address out-of-band
  • Validate the .mix address using the checksum.
  • Extract the public identity key hs_id from the .mix address.
  • Determine the current epoch.
  • Derive the blinded key bk_i for the current epoch
  • Derive the discovery key disc_key.
  • Query the discovery/DHT using disc_key to retrieve the descriptor.
  • Validate the returned descriptor by:
    • Validate the outer layer in the same way as a discovery/DHT node (see “Discovery Node Processing” section above).
    • Check that signature.signing_key == bk_i
    • Derive the secret_input for the inner layer
    • Use KDF to generate inner layer decryption keys (stream cipher key, IV, MAC key).
    • Decrypt the inner layer data blob, and check its MAC.
  • Proceed with the intro protocol to establish a SURB-rendezvous connection to the hidden service.

3. Rendezvous protocol

After the bootstrapping a connection through an intro point, the client and hidden service can communicate directly using SURBs since each party has SURBs from the other. At this point, introduction points are no longer involved in the communication path unless the session fails and the client needs to re-bootstrap through an introduction point. However, since each party cannot be sure that the SURBs are safe to use and could contain a malicious mix path, a different type/mode of connection is needed which we refer to here as a "SURB-rendezvous" connection.

To describe this, we can abstract the mix connections as three types of connections, each providing different anonymity properties:

  1. Forward connection: provides sender anonymity but doesn’t hide the destination from the sender.
  2. SURB-reply connection: provides anonymity to the SURB creator not the SURB user.
  3. SURB-rendezvous connection: provides anonymity to both the SURB creator and the user.

The Mix protocol already supports both 1 and 2 above. The goal here is to design a solution for 3.

SURB-rendezvous Connection

A SURB-rendezvous connection is a connection mode in which packets are sent using another party’s SURB, but only after the sender first routes the SURB packet through a sender-chosen mix prefix path.

To illustrate this better, let’s denote the sender (SURB user) S and receiver/exit (SURB creator) E.

  • S chooses a random mix node as a rendezvous point R and builds a mix path to it and prepares a Sphinx packet P1.
  • S places both the SURB and the message (encrypted with a shared secret z) intended for E in the payload of P1, adds a flag to indicate that the packet is SURB-rendezvous (we’ll discuss this later), and sends the Sphinx packet.
  • R receives the payload and sees the SURB-rendezvous flag, so it parses the payload to get the SURB and message.
  • R uses the SURB to create a Sphinx packet with the given message as its payload, pad it (since it would be smaller than a Sphinx payload), and sends the packet.
  • E receives the packet and recognizes the packet since it created the SURB and processes it as a normal SURB-reply. The result would be an encrypted message under z + padding.
  • E removes the padding and decrypts using z.

Note: in here, rendezvous points can used once, or multiple times which would then be similar to Tor which maintain a circuit to the rendezvous points. Although in here, the client and service would have different rendezvous points.

If we assume that possession of the SURB by itself binds the reply/message to the sender/session, then we can modify the above approach slightly. We can drop the need for the shared secret and use the reply key in the SURB. Then, R only need to use the header and the already encrypted message as payload.

This type of connection is not yet supported in Mix and so we don’t have a flag for it to indicate how an exit (rendezvous points) should process it. In the future we will likely have a better way to encode packet processing behaviour in the Sphinx header. However, for now we can rely on the reserved internal hidden service protocol codec (e.g. "/mix/hiddenservices/1.0.0").

Creating a SURB-rendezvous connection
For parties A and B to connect over SURB-rendezvous connection, they must obtain:

  • a SURB from the other party
  • a shared secret s

These should be exchanged out of band e.g. through the intro protocol.
Then each party must maintain a state:

RendezvousState {
    incoming_surbs: [SURB]
    outgoing_surbs: [SURB]
    shared_secret: bytes
}

where:

  • incoming_surbs are the set of SURBs we expect the other party messages to come from.
  • outgoing_surbs are the set of SURBs we can use to send a message to the other party.
  • shared_secret is the shared secret we have with the other party.

This state must be maintained in order to create packets and process incoming packets as we will see next.

Creating a SURB-rendezvous packet
To send a message m (a Sphinx payload) to E using a SURB created by E, the mix node must:

  • Choose a random mix node (rendezvous point) R (must not be E), create a mix path and prepare a Sphinx packet P.
  • Use the internal hidden service protocol codec as the codec for the payload.
  • Pad m to a fixed size j so that inner_payload has fixed pre-defined size.
  • Apply one layer of encryption to m using a shared secret s between sender and E. This layer of encryption can be thought as a “virtual hop” where you take m as the sphinx payload ( i.e., \delta) and apply one LIONESS encryption using the shared secret s.
  • Place the SURB and the encrypted m in the message type:
    Rendezvous {
    surb: bytes,
    inner_payload: bytes
}
  • Place the codec and Rendezvous message in the payload of P.

Exit/Rendezvous processing behaviour
For an exit which in this case is a rendezvous point to process a SURB-rendezvous packet, it must identify it first by:

  • parse the payload as (codec, msg)
  • sees the codec as the internal hidden service protocol codec.
  • identify the msg as Rendezvous

Then the exit node must:

  • use the SURB to create a Sphinx header.
  • use the inner_payload in the Rendezvous message + padding (to Sphinx payload size) as the Sphinx payload.
  • send the Sphinx packet.

Receiver processing behaviour
A mix node that receives a SURB reply must map that SURB to an existing SURB-rendezvous connection. If none exist, drop the packet.
If a SURB-rendezvous connection exists, then:

  • start with normal SURB processing.
  • take the first j bytes as the inner_payload and drop the rest (the padding).
  • use the stored shared secret to apply one layer of decryption to inner_payload.
  • pass the message to the application layer to process it.

Note: again here we use a shared secret but we can easily adapt this to use reply_key instead.

Limitations and open problems

The design above gives a Tor-style hidden service construction. It is however, missing some additional components such as:

  • Denial of service.
  • Restricted discovery mode.
  • SURB management.

These can be solved with proper designs possibly adapting what Mix has, e.g., RLN. The most serious open problem that we identified is the malicious path problem which is discussed in the following section.

The malicious path problem

In a mixnet, anonymity relies on the assumption: a path is safe if at least one node on the path is honest. If all nodes on the path are malicious, the adversary is able to link the sender to the receiver, or the hidden service identifier to its network identity.

If an adversary controls a fraction f of the mix nodes and each path has length l, then the probability that one randomly selected path is fully malicious is approximately:

p = f^l

For example, if the adversary controls 10% of the mix nodes and paths have length 3:

p = 0.1^3 = 0.001

That is one fully malicious path in one thousand independently sampled paths (1/1000). For a single message, this is small. For a hidden service, it is much more serious.

A hidden service is a long-lived (possibly public) reachable target. A malicious client can repeatedly contact the service. Each contact can cause the service to create or use fresh paths, fresh SURBs, or fresh rendezvous points. Over time, the adversary gets many chances to control a fully malicious path.

If each attempt has a compromise probability p, then after n independent attempts the probability of at least one compromised attempt is approx:

P = 1 - (1 - p)^n

With p = 0.001:

\begin{aligned} n = 1,000 &\Rightarrow P \approx 63\% \\ n = 3,000 &\Rightarrow P \approx 95\% \\ n = 5,000 &\Rightarrow P \approx 99\% \end{aligned}

One can see how this is a serious problem because of the accumulating risk over repeated malicious interactions. The problem can appear in several places in the protocol:

  • when the service establishes introduction points and supplies intro-SURBs.
  • when the service replies to clients.
  • when the service generates service-SURBs for client-service communication using the SURB-rendezvous connection.

Note that here the adversary does not necessarily need to attack the service by repeated interaction. If a malicious intro point, client, or other party can repeatedly obtain SURBs from the service, then it has many opportunities to observe a SURB whose path is fully malicious. Over time, this turns SURB into another attack vector.

The small packet size also helps the attacker in this setting because sending and receiving large data would require chunking it and sending each chunk in a separate packet with a newly sampled path. Current packet size is \approx 4KB, meaning that a fully malicious path would be very likely with >10MB assuming p = 0.001.

Tor Guards and vanguards Protocols

Tor does not sample completely fresh independent paths for every circuit. Entry guards exist because repeatedly choosing fresh entry (first hop) relays would eventually give an adversary a chance to become the first hop of a user’s circuit. Onion services also use additional guard and vanguard nodes to reduce the risk of guard discovery and related attacks (see Tor spec).

A similar approach may work for hidden services over Mix. Instead of choosing all mix paths independently, a hidden service could use a stable set of guard nodes. It could also use a second layer of vanguard nodes, so the paths are constrained through a smaller, longer-lived set of selected nodes.

This changes the risk. If the service initially chooses honest guards or vanguards, the adversary gets fewer chances. If the service chooses both malicious guards and vanguards, the service becomes exposed to the malicious path attack. This is not a complete solution. It delays the risk, it does not eliminate it. Whether this makes the attack impractical in the hidden service over Mix setting is still an open question and is something we are currently investigating. Recent work seems to suggest that guard-style approach can significantly improve time to “first compromise” in stratified mixnets (see the paper: Stopping Silent Sneaks: Defending against Malicious Mixes with Topological Engineering). This still needs to be simulated/evaluated for the hidden service setting and for the free-route Mix.

References

Sphinx Packet Format and Single-Use Reply Blocks (SURBs)

Mix Protocol

Tor Hidden Services

2 Likes