By Yale University.

1 Introduction.

Anonymous participation is often considered a basic right in free societies (Yale Law Journal 1961). The limited form of anonymity the Internet provides is a widely cherished feature (Teich, Frankel, Kling, and Lee 1999; Wallace 1999), enabling people and groups with controversial or unpopular views to communicate and organize without fear of personal reprisal (Stein 2003).

Yet anonymity makes it difficult to trace or exclude misbehaving participants (Davenport 2002). Online protocols providinstronger anonymity, such as mix-networks (Chaum 1981; Adida 2006), onion routing (Goldschlag, Reed, and Syverson 1999; Dingledine, Mathewson, and Syverson 2004), and Dining Cryptographers Networks or DC-nets (Chaum 1988; Waidner and Pfitzmann 1989; Sirer et al.2004; Golle and Juels 2004), further weaken accountability, yielding forums in which no content may be considered trustworthy and no reliable defense is available against anonymous misbehavior.

DISSENT (Dining-cryptographers Shuffled-Send Network) is a communication protocol that provides strong integrity, accountability and anonymity. Members of small, private online groups,whose membership is closed and known to its members, are able to send anonymous messages to each other, to the whole group, or to a non-member, in that the receiver knows that some member sent the message, but no one knows which member.

DISSENT holds members accountable, not by compromising their anonymity but rather by ensuring that communication resources are allocated among all communicating members, and that any disruption results in the identification of some malicious member during a “blame” process. Members are thus unable to corrupt or block other members’ messages, overrun the group with spam, stuff ballots, or create unlimited anonymous Sybil identities (Douceur 2002) or sock puppets (Stone and Richtel 2007) with which to bias or subvert the group’s deliberations.

DISSENT builds on the shuffle of Brickell and Shmatikov (2006a), combining that with DC-net techniques for efficient bulk communication. It uses only readily available cryptographic primitives and handles arbitrarily large messages and unbalanced loads efficiently. Each member sends exactly one message per round, making it usable for voting or assigning pseudonyms with a 1-to-1 correspondence to real group members. DISSENT has limitations, of course. It is not intended for large-scale, “open-access” anonymous messaging or file sharing (Goldschlag, Reed, and Syverson 1999; Clarke, Sandberg, Wiley, and Hong 2000).

DISSENT’s accountability property assumes closed groups, and may be ineffective if a malicious member can leave and rejoin the group under a new (public) identity. Finally, DISSENT’s serialized GMP-SHUFFLE protocol imposes a per-round startup delay that makes DISSENT impractical for latency-sensitive applications. Further discussion on related anonymous communication systems is included in Section 6.

DISSENT was first introduced by Corrigan-Gibbs and Ford (2010). In addition to sketching the protocol and security arguments, they describe practical usage considerations and give the results of several performance experiments based on a prototype implementation. We focus here on a detailed exposition of DISSENT and a rigorous analysis of its security properties.

Indeed, during our analysis of the original protocol, we identified several attacks. For example, anonymity could be broken by replaying protocol inputs in subsequent rounds, by providing at certain points incorrect ciphertexts to some members and correct ones to the rest, or by copying ciphertexts at other points. Accountability for disruption could be avoided by copying the protocol inputs from honest members, and honest members could potentially be falsely accused of disruption by rearranging valid signed messages to create phony logs. Protocol termination could be prevented for some members by causing failures for them while allowing the rest to terminate successfully and thus not participate in a blame process.

See the appendix more details of these attacks. In order to fix these flaws, we made several non-trivial modifications to the original protocol. To prevent replay attacks we added key generation steps. To prevent equivocation attacks we added rebroadcast steps, and have members intentionally cause intermediate protocol failures when equivocation is observed. We add the use of non-malleable commitments to prevent submission duplication, and we add phase numbers to prevent log forgery. Finally, to prevent non-termination of the protocol, we make all steps non-optional, in particular including an opportunity for blame at the end of every execution to ensure accountability.

We are able to give proofs of security for this improved protocol. In particular, we provide rigorous proofs of integrity, accountability, and anonymity. Obtaining a fully secure protocol with proofs required a surprising amount of additional work given the relative simplicity and maturity of the underlying ideas. However, as observed by Wikstrom (2004), the complexity of anonymous ¨ communication protocols has frequently resulted in incomplete proofs and subtle errors (see further discussion in Section 6).

The main contributions of this paper, therefore, are (1) we provide a full description of an improved DISSENT protocol, (2) we present precise definitions of its security properties, and (3) we give rigorous proofs that the protocol satisfies those definitions. Section 2 outlines DISSENT’s framework and security model. Section 3 describes the GMPSHUFFLE protocol, and Section 4 details the GMP-BULK transfer protocol. Section 5 provides formal security properties and their proofs. Section 6 summarizes related work, and Section 7 concludes.

Protocol Overview DISSENT is designed to be used in a group setting. Each member i of the group is associated with a long term public signing key pair (ui; vi). DISSENT provides a shuffled send communication primitive that gives sender anonymity among that group. During each protocol run, every group member i secretly creates a m essage mi and submits it to the protocol. The protocol effectively collects all secret messages, shuffles their order according to some random permutation  that no one knows, and broadcasts the resulting sequence of messages. Each input message mi can have a different length Li.

We present a messaging interface, called the General Messaging Protocol, that DISSENT implements. DISSENT in fact defines two protocols implementing this interface: the GMP-SHUFFLE protocol provides anonymous communication for fixed-length messages, and the GMP-BULK protocol builds on this to provide efficient anonymous communication of arbitrary-length messages.

2.1 The General Messaging Protocol

A Group Messaging Protocol GMP is a 3-tuple of algorithms SETUP(vi), ANONYMIZE (mi; K; nR; ; f) and VERIFY-PROOF(pj; `i). SETUP takes a member’s public signing key vi as input and outputs one or more session nonces nR, a set K of all members’ signing keys, an ordering of members , and optionally a message length L. All group members run the SETUP algorithm before each protocol run to agree on common parameters. Such agreement might be achieved via Paxos (Lamport 1998) or BFT (Castro and Liskov 1999). We emphasize that SETUP does not generate members’ signing keys; rather, it uses long term signing keys submitted by each member.

ANONYMIZE takes a message mi, a set K of members’ signing keys, one or more round noncesnR, an ordering of members , and optionally a flag f as input, and outputs either (SUCCESS; M0i),where M0i is a set of messages, or (FAILURE; BLAMEi ; `i), where BLAMEi is a set of observed misbehaviors, and `i is a log of a protocol run. After agreeing on common parameters, the group runs the ANONYMIZE algorithm. The goal of the algorithm is to anonymously broadcast the set of messages submitted by group members. If a protocol run succeeds for a member, then she outputs the anonymized messages. Otherwise, the protocol run fails and the group member produces a set of blame proof(s) for the member misbehavior(s) responsible for the protocol run failure.

VERIFY-PROOF takes a proof pj of member j’s misbehavior and a log `i as input, and outputs either TRUE indicating that pj is indeed a proof of j’s misbehavior given the observed protocol history represented by log `i , or FALSE otherwise. If a run of

ANONYMIZE fails for member i, then i blames at least one dishonest member j by producing a proof pj of j’s misbehavior and a log `i. VERIFY-PROOF is used to verify that proof pj does in fact indicate misbehavior by j given `i.

2.2 The GMP-Shuffle Protocol

The GMP-SHUFFLE protocol enables the anonymous exchange of equally sized messages. However, it incurs extra communication if only one member wishes to send, and its decrypt-and-shuffle phase is inherently serial. GMP-SHUFFLE builds on a data mining protocol by Brickell and Shmatikov (Brickell and Shmatikov 2006b) to broadcast the input set of fixed-length messages, one from each group member, in an unknown permutation, providing cryptographically strong anonymity. Like many anonymous messaging protocols, the original data mining protocol was vulnerable to untraceable denial-of-service (DoS) attacks by malicious group members. We remove this vulnerability by adding go/no-go and blame phases, which can trace and hold accountable any group member maliciously disrupting the protocol.

In the GMP-SHUFFLE protocol, all members 1; : : : ; N choose their secret messages m1; : : : ; mN of equal length L. Each member has a long lived signing key pair (ui; vi) and knows the ordering of the group and a session nonce nR. For a single run of the protocol, each member generates two key pairs, called inner and outer, and shares the public keys with the group. Each member i iteratively encrypts its message mi using all inner and then all outer public keys. The resulting ciphertext messages are sent to a group leader who strips one layer of encryption from each ciphertext using his outer public key, permutes the messages, and forwards the permuted set to the next member who repeats the process.

Removing all layers of outer encryption yields a set of inner ciphertext messages which member N broadcasts to the entire group. All members inspect the set to verify that their inner ciphertext is present. If all members’ messages are included and every step of the protocol completes successfully, each member releases its inner private key allowing the set of permuted secret messages to be recovered. If any inner ciphertext is missing or corrupted, however, the inner keys are destroyed and the entire group enters a blame phase to find the culprit member(s). Section 3 details the GMP-SHUFFLE protocol and Section 5 demonstrates its security.

2.3 The GMP-Bulk Protocol

The GMP-BULK protocol uses ideas from DC-nets (Chaum 1988; Waidner and Pfitzmann 1989; Sirer et al. 2004; Golle and Juels 2004) to anonymously transmit variable-length messages. In place of the DoS-prone slot reservation systems in prior DC-nets schemes, however, DISSENT leverages its GMP-SHUFFLE protocol to prearrange the DC-nets transmission schedule, guaranteeing each member exactly one message slot per round.

GMP-BULK uses the GMP-SHUFFLE protocol to broadcast an unknown permutation of the message descriptors submitted by each member. Each descriptor di contains the length Li of member i’s message mi, a cryptographic hash of mi, a vector S~ i of seeds sij, where each seed is encrypted with j’s session public key and assigns each member j a pseudorandom bulk ciphertext to transmit,
and a vector H~ i of hashes Hij validating each bulk ciphertext. The shuffled order of the message descriptors indicates the order in which the anonymous senders should transmit their secret messages.

Then, all group members broadcast bit streams based on pseudorandom seeds included in the message descriptors, so that XORing all members’ bit streams together yields a permuted set of all members’ variable-length messages. During a member’s own transmission slot, he transmits his own message XOR’d with the messages he has instructed all other members to generate.

During another group member’s transmission slot, members broadcast a pseudorandom bit string generated from an encrypted seed in the slot’s message descriptor. Cryptographic hashes in the message descriptors enable members to verify the correctness of each others’ bulk transmissions,ensuring message integrity and DoS protection throughout. If any group member sends an invalid bit string, then in a blame phase the owner of that transmission slot uses GMP-SHUFFLE to anonymously broadcast an accusation exposing the faulty group member. The GMP-BULK protocol is detailed in Section 4 and Section 5 proves its security.

2.4 Security Model

We assume the adversary is polynomial-time limited. We allow him to control a colluding subset of group members. We define the rest of the members as honest, in that they run the prescribed algorithms, and their internal states are hidden from the adversary. We assume that communication channels exist between all members, and that they can be observed by the adversary. The security properties we wish the protocol to satisfy are integrity, accountability, and anonymity, as we describe below. Formal definitions of these properties and their proofs are given in Section 5.

To continue reading this long report please go to: http://cryptome.org/2013/09/tor-network-dissent.pdf