Endong Liu

Stay Hungry, Stay Foolish

9 minute read

UCL Course COMP0143 Cryptocurrencies: Prerequisite Cryptography Part IX

Type of Anonymity

Sender Anonymity

Alice sends a message to Bob. Bob cannot know who Alice is.

Receiver Anonymity

Alice can send a message to Bob, but cannot find out who Bob is.

Bi-directional Anonymity

Alice and Bob can talk to each other, but neither of them know the identity of the other.

Third Party Anonymity

Alice and Bob converse and know each other, but third party cannot find this out.

Properties of Anonymity

Unobservability

Alice and Bob communicate, but no one can tell if they are transmitting or receiving messages.

Unlinkability

Message-Level: Two messages sent (received) by Alice (Bob) cannot be linked to the same sender (receiver).

Relationship-Level: One message sent by Alice and received by Bob, where Alice and Bob cannot be linked.

Pseudonymity

All actions can be linkable to a pseudonym but be unlinkable to a principal.

High-latency Anonymity Systems

Naïve Method: Broadcast

Process

One sender can broadcast encrypted messages to many receivers (1-to-N)
such that only the receivers who can decrypt will get the message
but others cannot know which receivers can decrypt.

Pros

  • Simple (can be done by trees, rings, buses, etc.)

  • Receiver Anonymity

Cons

  • Coordination ?

    It is hard for the sender to know all the possible receivers.

  • Sender Anonymity ?

    All receivers can know the sender.

  • Efficiency ?

    Problems in latency (when all receivers receive) and bandwidth (need broadcast)
    especially in a large system (utility will be quite low).

Anonymity Provided by Mix

Process

  1. Multiple senders send messages to a Mix. For example,

    \[\text{Alice} \rightarrow \text{Mix}: \{\ \text{Bob}, \, \text{Msg} \ \}_{pk_{\text{Mix}}}\]

    where the destination and message are encrypted by public key \(pk\) of the Mix.

  2. The Mix decrypt to get the destination and message by its private key \(sk\)

  3. The Mix send the message to the destination. For example,

    \[\text{Mix} \rightarrow \text{Bob}: \text{Msg}\]

Mix Requirements

  • Public Key Encryption

  • Enough Honest Mix Participants

    Can be more secure if there are more honest Mix participants in one round.

  • Bitwise Unlinkability

    Cannot link the corresponding input and output messages of the Mix by bit pattern.

  • Traffic Analysis Resistance

    Cannot link the corresponding inputs and outputs of the Mix by metadata (e.g., address, time, size, etc.).

Pros

  • Sender Anonymity

  • Relationship-Level Unlinkability

    Cannot link the corresponding input and output messages (sender and receiver)

Cons

  • High costs for all requirements

  • Mix itself can be untrusted

  • Other Mix participants can be untrusted

Attacks to Mix

Active Attacks against Bitwise Unlinkability

Tagging Attack

If it is a Mix using Steam Cipher,

\[\{ \ \text{Msg} \ \}_{pk_{\text{Mix}}} := \{\ k \ \}_{pk_{\text{Mix}}}, \ \text{Msg} \, \oplus \, \textit{Stream}_k\]

where \(k\) is a fresh key for this message \(\text{Msg}\).

Then,

  • Adversary can eavesdrop and manipulate the encrypted input (i.e., flipping the last bit)

    \[\{\ \text{Bob}, \, \text{Msg} \ \}_{pk_{\text{Mix}}} \rightarrow \{\ \text{Bob}, \, \text{Msg} \ \}_{pk_{\text{Mix}}} \, \oplus (\ \dots 0001 \ )\]

  • Adversary may find the output like

    \[\text{Mix} \rightarrow \text{Bob}: \text{Msg} \, \oplus \, (\ \dots 0001 \ )\]

Possible Solution

Mixminion (the example designed by George Danezis et al.)

  • Detect modification

    Use cryptographic checksums to protect the message header.

  • Destroy necessary information

    Destroy the addressing information contained in the message header if the message payload is modified by an adversary.

Passive Attacks against Traffic Analysis Resistance

Order Attack

If it is a Mix using First-In-First-Out (FIFO) mechanism,

then adversary can simple counts the number since this Mix sends messages out in the order they came in.

Possible Solution

  • Threshold

    Wait for \(N\) messages and output them in a random order.

  • Pool

    1. There is a pool of \(n\) messages

    2. Wait for \(N\) messages

    3. Output \(N\) out of a total of \(N + n\) messages

    4. Keep \(n\) messages remaining in the pool (back to Step 1)

Untrusted Mix

One key problem of anonymity provided by Mix is the need to trust the Mix itself.

Possible Solution

Mix Cascades

All messages are routed through a preset mix sequence (fixed path).

Security Parameter: the length of sequence \(O(|\text{Mixes}|)\).

Free Routing

All messages are routed through a random sequence of mixes (nested encrypted).

For example,

\[\text{Alice} \rightarrow \text{Mix}_2: \{ \ \text{Mix}_4: \{ \ \text{Mix}_1: \{\text{Bob}, \ \text{Msg} \ \}_{pk_{\text{Mix}_1}} \ \}_{pk_{\text{Mix}_4}} \ \}_{pk_{\text{Mix}_2}}\]

The path is Alice -> Mix_2 -> Mix_4 -> Mix_1 -> Bob.

Security Parameter: the length of sequence \(O(log(|\text{Mixes}|))\).

Requirements

  • Bitwise Unlinkability: Length invariance and Replay prevention.

  • Mix Discovery: Mixers need to be authoritative, comprehensive, and common.

  • Hidden Information: The step number and total path length should be hidden.

Untrusted Mix Participants

Another key problem of anonymity provided by Mix is the need to trust Mix participants.

N - 1 Attack

Process

  1. Wait or flush the Mix.

  2. Block all incoming messages (trickle) and inject messages from the attacker (flood).

  3. Allow only \(1\) message from the benign user but \(N-1\) messages from the attacker.

  4. Identify the output that not belongs to the attacker will belong to the benign user.

Possible Solution

  • Strong Identification: ensure distinct identities (might not be accepted by users).

  • Message Expiration: discard messages after a deadline to prevent the mix flushing.

  • Heartbeat Traffic: route messages to their senders to detect whether messages are blocked or not.

Low-Latency Anonymity Systems

Anonymity Provided by Tor

Alice select a path to Bob which relays a bi-directional stream of traffic.

Tor Users

By default, there are \(3\) hops (Entry, Middle, Exit) to protect users.

User-to-Entry { Entry-to-Middle { Middle-to-Exit { data } } }

Layered encryption prevents linking of inputs and outputs based on traffic content.

Warning
The traffic between Tor network is encrypted, but outputs of Exit are not (for services)
such that IP addresses of Exits can be found (get the blame)
which leads to the number of Exits in Tor network will be lower than other two types.

Tor Servers

Web servers run within the Tor network (domain name encrypted by public key).

By default, there are \(6\) hops ( \(3\) to protect users & \(3\) to protect servers).

Directory Authorities and Mirrors

Network information is

  • collected by directory authorities, and

  • distributed through mirrors

Process

  • Tor nodes publish their information (descriptors) to the directory authorities.

  • Directory authorities negotiate a consensus listing all available Tor nodes,
    and sign under keys of all participating directory authorities.

  • Directory mirrors (most Tor nodes) connect to authorities to retrieve consensus.

  • Tor clients connect to mirrors to receive up to date consensus,
    or bootstrap by connecting to directory authority directly， and then verify digital signatures on consensus.

Applications

  • Ordinary People: avoid unscrupulous marketers, protect children, research sensitive topics.

  • Militaries and Law Enforcement: protect field agents and sources, intelligence gathering, decentralize services.

  • Journalists and Their Audience: preserve safety of journalists working in hostile regimes, resist Internet censorship.

Difference between Mix and Tor

  • Mix uses one public key per message, while

    Tor setups route once (one public key) per connection and use for many cells.

  • Mix needs to wait for filled pool or threshold to defend order attack, while

    Tor has usable web latency (1 -2 second round trip) and short routes (3 hops).

Attacks to Tor

Stream Tracing Attack

Vulnerability

Because of the requirements of low latency, Tor has no batching or threshold
such that packets come out immediately after they come in which makes passive attacks possible.

Main Idea

Adversary observes all inputs and outputs of an onion router
to find that timing of packets are correlated
which helps to link the ingoing and outgoing connections.

Metric-1: Correlation

Match input stream to output stream based on packet counts
by bucketing input and output packets over time (similar timestamp).

\[\textit{Corr} = \sum_i^n \text{IN}_i \cdot \text{OUT}_i\]

Problem: Bucketing operation will decrease the precision.

Metric-2: Template Matching Score

Compute the probability distribution of coming out time for each packet comes in
by using input and delay curve to make template:

  • assign to each output cell the template value \(v_i\) for its output time

  • multiply them together to get a score to compare which matches most

    \[\prod_i^n v_i\]

Fingerprinting Attack

If the attacker has prior knowledge of traffic patterns for specific websites,
the attacker analyzes things like the size and timing of the data packets being sent
between the user and the entry node of the Tor network to identify which site the user is accessing.

Global and Partial View Attack

  • Tor cannot withstand a passive adversary with global view (although too expensive to be practical).

  • Tor cannot withstand a passive adversary with partial view (can see first and last node of the connection).

You may also enjoy