Lox: Protecting the Social Graph in Bridge Distribution (PETS 2023)

Censorship research & publications
1

Lox: Protecting the Social Graph in Bridge Distribution
Lindsey Tulloch, Ian Goldberg
https://censorbib.nymity.ch/#Tulloch2023a
Presentation video
Source code

Lox is a bridge distribution system, a way of allocating scarce bridge resources (such as IP addresses) to users of a circumvention system. The challenge in bridge distribution is making bridges available to honest users, without revealing them all to a censor that wants to block them. To resist infiltration by censors, Lox uses a system of escalating trust levels and invitations by established users. It uses cryptography to keep the social graph of inviters and invitees private. Users that don’t have an invitation can still bootstrap trust through an open-entry system, without a central identity arbiter.

Lox takes ideas from earlier bridge distribution systems. rBridge (2013) and Hyphae (2017) used invitations and anonymous credentials, but did not have a way for users to enter the system other than by being invited. Salmon (2016) introduced the idea of users advancing in trust levels over time, and had a way for new users to enter at trust level 0 without an invitation, but it required interfacing with a non-private third-party identity service, such as Facebook. Lox combines the best features of these other systems: invitations, trust levels, open entry for new users, and privacy of the social graph.

The core cryptographic tool in Lox is an unlinkable anonymous credential. It uses specifically the keyed algebraic MAC credentials of Chase et al. 2013, the same scheme used in Hyphae. A Lox credential represents the attributes:

(ID, Time, Trust level, Bridge bucket, Number of invitations, Number of blockages)

A user exchange credentials with a central server called the Lox Authority. On each interaction, the user reveals to the Lox Authority only the attributes that are necessary for that interaction, keeping the others hidden (Table 3). Each credential is used only once: after being redeemed, the Lox Authority re-issues the user a new credential to be used in the next interaction, with attributes modified as appropriate, and a new random ID.

Users are eligible to upgrade to higher trust levels after their bridges have remained unblocked for certain lengths of time (Table 2). This gives users an incentive to keep their bridges secret and not share them widely. At higher trust levels, users gain a limited number of invitations which they may spend to invite trusted friends into the system. The idea of inheritance is built into Lox; this is what prevents a censor from getting leverage by acting as numerous fake “sock puppet” users. When a new user is invited, they enter at trust level 1 and inherit the same bridges as the user that invited them. This way, a censor does not learn new bridges or gain additional privileges by inviting their own accounts. New users without an invitation enter at trust level 0 and are given bridges from a pool that is separate from the invitation pool. If one of a user’s bridges gets blocked, there is a way for them to migrate to a new unblocked bridge, but a user with too many blockages is considered suspicious and will not be able to advance in trust levels or learn additional bridges from the trusted pool.

2

del

3

“Shadow ban” is not quite the right word, because there are no accounts, or anything like that, that the Lox Authority could use to secretly track a user and give the user different answers from others. That’s the purpose of the anonymous credentials. If the Lox Authority gets hacked, there is no user database or log of who invited whom.

For example, when issuing an invite, the Lox Authority sees an anonymous credential with a number of invitations a = 2. But the Lox Authority does not directly see the value of a (see ℋ in Table 3), because that would enable user tracking. The Lox Authority sees an anonymous credential and a zero-knowledge proof that a > 0, for example. The Lox Authority issues a new credential with a = 1, but it does not know the value a it is giving out; it decrements the attribute under homomorphic encryption.

I admit I don’t understand what makes the cryptography work. It’s possible even my high-level understanding is mistaken; maybe the authors can clarify if so.

To your question about how you know when a bridge is blocked, it’s true that Lox relies on an oracle to tell it when bridges are blocked. My understanding is that defining such an oracle has been a major challenge and is still something of an open problem. I haven’t been involved with it directly, but here are some links:

  • Implement reasonable handling for bridge blocking (#33) · Issues · The Tor Project / Anti-censorship / lox · GitLab
  • #tor-meeting log
    <dcf1> there's some aspects that are assumed to exist and to be plugged into the Lox system, which is what you're doing now with integration
<dcf1> like for example you need a signal when a bridge has been blocked, and to realize that somehow
<dcf1> my impression of the model in the paper is that bridge operators are trusted(?) to report their level of use, and when it goes to zero that indicates a block?
<onyinyang> yes. There are many missing pieces that make the full system tricky in practice, blocking being a major sticking point.
<cohosh_away> that luckily exists with rdsys
<cohosh_away> https://gitlab.torproject.org/cohosh/rdsys-backend-api
<cohosh_away> or rather telling whether bridges are gone does
<cohosh_away> not blocked