February 2014 - tor-commits - lists.torproject.org

[bridgedb/master] Merge branch 'fix/9988-rm-hashlibnew' into develop
by isis＠torproject.org 04 Feb '14

04 Feb '14

commit 00228a8c3561fa4da0de5501259e7ed7ed7f6615 Merge: f2ecd0d 124db86 Author: Isis Lovecruft <isis(a)torproject.org> Date: Tue Feb 4 00:04:23 2014 +0000 Merge branch 'fix/9988-rm-hashlibnew' into develop lib/bridgedb/Storage.py | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-)

1 0

[bridgedb/master] Merge branch 'fix/9988-apply-patch' into develop
by isis＠torproject.org 04 Feb '14

04 Feb '14

commit a619387402ecc355980bdee035c5f4d043e83799 Merge: 7e03040 fc9fcd6 Author: Isis Lovecruft <isis(a)torproject.org> Date: Fri Jan 31 13:00:35 2014 +0000 Merge branch 'fix/9988-apply-patch' into develop lib/bridgedb/Bridges.py | 4 ++-- lib/bridgedb/Storage.py | 10 +++++----- 2 files changed, 7 insertions(+), 7 deletions(-)

1 0

[bridgedb/master] Merge branch 'feature/7520-social-dist-design_r1' into develop
by isis＠torproject.org 04 Feb '14

04 Feb '14

commit 6384d7b4e33ffa0a8e0339f19571da5fb5b06778 Merge: aa495a9 38cbe89 Author: Isis Lovecruft <isis(a)torproject.org> Date: Wed Jan 29 21:00:55 2014 +0000 Merge branch 'feature/7520-social-dist-design_r1' into develop .../XXX-bridgedb-database-improvements.txt | 260 ++++++++++ doc/proposals/XXX-bridgedb-social-distribution.txt | 496 ++++++++++++++++++++ 2 files changed, 756 insertions(+)

1 0

[bridgedb/master] Update the contents and docs of README and .conf
by isis＠torproject.org 04 Feb '14

04 Feb '14

commit bf3027a8104d19366297db910dc658b491a46603 Author: Matthew Finkel <Matthew.Finkel(a)gmail.com> Date: Sat Feb 1 07:03:37 2014 +0000 Update the contents and docs of README and .conf Further describe some config options Rearrange and regroup some configuration file options Clarify end-user distributor usage --- README | 19 +++++++++++-------- bridgedb.conf | 54 ++++++++++++++++++++++++++++++++---------------------- 2 files changed, 43 insertions(+), 30 deletions(-) diff --git a/README b/README index 0b7bb10..4724594 100644 --- a/README +++ b/README @@ -28,9 +28,10 @@ layer of encryption. #### So how do I use this? Well, probably, you don't. But if you're looking for bridges, you can use -[BridgeDB's web interface](https://bridges.torproject.org), which has -instructions on getting the Pluggable Transports Tor Browser Bundle, as well -as instructions for getting extra Bridges. +[the web interface](https://bridges.torproject.org) of the BridgeDB instance +deployed by the Tor Project, which has instructions on getting the Pluggable +Transports-capable Tor Browser Bundle, as well as instructions for getting +extra Bridges. ## Maintainer Setup @@ -122,8 +123,8 @@ all the updated files in their correct locations. **Requesting Translations for Altered/Added Source Code**: This should be done whenever any of the strings requiring translation -- _("they are formatted - like this") -- are changed, or new ones are added. See - ```lib/bridgedb/I18n.py```. + like this") -- are changed, or new ones are added. + See ```lib/bridgedb/I18n.py```. Translations for Tor Project repos are kept [in a separate repo](https://gitweb.torproject.org/translation.git). You'll @@ -153,7 +154,7 @@ complete, the finished .po files should be placed into the #### Enabling HTTPS Create a self-signed certificate with: - maint/make-ssl-cert + scripts/make-ssl-cert Or, place an existing certificate in the path specified in bridgedb.conf by the ```HTTPS_CERT_FILE``` option, and a private key where ```HTTPS_KEY_FILE``` @@ -233,8 +234,10 @@ such as Twitter. Just connect to the appropriate port. #### To use with email: -Any mail sent to the email port with a subject or a single line _exactly_ -equal to "get bridges" will get answered, assuming the domain is okay. +Any mail sent to the email port with a destination username as defined by the +EMAIL_USERNAME configuration option (default is 'bridge', e.g. bridges@...) +and sent from a yahoo or gmail address (by default, configured with the +EMAIL_DOMAINS option). ### Support Send your questions to isis (A) torproject (circle) org. diff --git a/bridgedb.conf b/bridgedb.conf index bf97077..534a4fe 100644 --- a/bridgedb.conf +++ b/bridgedb.conf @@ -101,13 +101,8 @@ DB_LOG_FILE = "bridgedist.log" # inside are automatically created for you if they do not exist. MASTER_KEY_FILE = "secret_key" -# Filename that contains blocked bridges list. Comment out to disable. -#COUNTRY_BLOCK_FILE = "blocked-bridges" - -# A list of filenames that contain IP addresses (one per line) of proxies. -# All IP-based distributors that see an incoming connection from a proxy -# will treat them specially. -PROXY_LIST_FILES = [] +# File to which we dump bridge pool assignments for statistics. +ASSIGNMENTS_FILE = "assignments.log" #------------------ # Logging Options \ @@ -126,11 +121,21 @@ SAFELOGGING = True LOGFILE_COUNT = 5 LOGFILE_ROTATE_SIZE = 10000000 -# Only consider routers whose purpose matches this string. -BRIDGE_PURPOSE = "bridge" +#------------------------------- +# General Distribution Options \ +#------------------------------------------------------------------------------ +# +# These options are not specific to a certain distributor and they may alter +# the bridge selection process in certain circumstances. +#------------------------------------------------------------------------------ -# File to which we dump bridge pool assignments for statistics. -ASSIGNMENTS_FILE = "assignments.log" +# Filename that contains blocked bridges list. Comment out to disable. +#COUNTRY_BLOCK_FILE = "blocked-bridges" + +# A list of filenames that contain IP addresses (one per line) of proxies. +# All IP-based distributors that see an incoming connection from a proxy +# will treat them specially. +PROXY_LIST_FILES = [] # How many clusters do we group IPs in when distributing bridges based on IP? # Note that if PROXY_LIST_FILES is set (below), what we actually do here @@ -146,6 +151,9 @@ FORCE_PORTS = [(443, 1)] # Only "Stable" is now supported. This is a list of (flag,minimum) tuples. FORCE_FLAGS = [("Stable", 1)] +# Only consider routers whose purpose matches this string. +BRIDGE_PURPOSE = "bridge" + #------------------------------- # HTTP(S) Distribution Options \ #------------------------------------------------------------------------------ @@ -189,6 +197,18 @@ HTTP_UNENCRYPTED_PORT = None # unencrypted connections. HTTP_USE_IP_FROM_FORWARDED_HEADER = False +# How many bridges do we try to give back in an answer by the +# unencrypted HTTP distributor? +HTTP_N_BRIDGES_PER_ANSWER = 3 + +# Options related to recaptcha support. +# Enable/Disable recaptcha +RECAPTCHA_ENABLED = False + +# Recaptcha API keys +RECAPTCHA_PUB_KEY = '' +RECAPTCHA_PRIV_KEY = '' + #------------------------------- # Email Distribution Options \ #------------------------------------------------------------------------------ @@ -286,15 +306,5 @@ RESERVED_SHARE = 2 # A dictionary of {FILENAME: NUMBER} where FILENAME is a string specifying the # filename to store a certain NUMBER (an integer) of bridges in. The number of # bridges here is *not* a share/proportion, as above; instead it's literally -# the number of bridges. +# the number of bridges. See the ``README`` for more details. FILE_BUCKETS = {} - -# Recaptcha Options -# ----------------- - -# Enable/Disable recaptcha -RECAPTCHA_ENABLED = False - -# Recaptcha API keys -RECAPTCHA_PUB_KEY = '' -RECAPTCHA_PRIV_KEY = ''

1 0

[bridgedb/master] Apply patch by ovnicraft to use hashlib rather than sha module.
by isis＠torproject.org 04 Feb '14

04 Feb '14

commit fc9fcd68378f381444d59de474827b0e6216ee81 Author: ovnicraft <tor-assistants(a)lists.torproject.org> Date: Thu Nov 28 19:11:34 2013 +0000 Apply patch by ovnicraft to use hashlib rather than sha module. * FIXES #9988 --- lib/bridgedb/Bridges.py | 4 ++-- lib/bridgedb/Storage.py | 10 +++++----- 2 files changed, 7 insertions(+), 7 deletions(-) diff --git a/lib/bridgedb/Bridges.py b/lib/bridgedb/Bridges.py index f8ec2c3..2bfa288 100644 --- a/lib/bridgedb/Bridges.py +++ b/lib/bridgedb/Bridges.py @@ -10,7 +10,7 @@ import bisect import hmac import logging import re -import sha +import hashlib import socket import time import ipaddr @@ -27,7 +27,7 @@ from bridgedb.parse import networkstatus HEX_FP_LEN = 40 ID_LEN = 20 -DIGESTMOD = sha +DIGESTMOD = hashlib.sha1 HEX_DIGEST_LEN = 40 DIGEST_LEN = 20 PORTSPEC_LEN = 16 diff --git a/lib/bridgedb/Storage.py b/lib/bridgedb/Storage.py index b0dada6..edcc566 100644 --- a/lib/bridgedb/Storage.py +++ b/lib/bridgedb/Storage.py @@ -8,7 +8,7 @@ import logging import binascii import sqlite3 import time -import sha +import hashlib from ipaddr import IPAddress, IPv6Address, IPv4Address import bridgedb.Stability as Stability @@ -262,7 +262,7 @@ class Database: cur.execute("DELETE FROM EmailedBridges WHERE when_mailed < ?", (t,)) def getEmailTime(self, addr): - addr = sha.new(addr).hexdigest() + addr = hashlib.new(addr).hexdigest() cur = self._cur cur.execute("SELECT when_mailed FROM EmailedBridges WHERE " "email = ?", (addr,)) @@ -272,7 +272,7 @@ class Database: return strToTime(v[0]) def setEmailTime(self, addr, whenMailed): - addr = sha.new(addr).hexdigest() + addr = hashlib.new(addr).hexdigest() cur = self._cur t = timeToStr(whenMailed) cur.execute("INSERT OR REPLACE INTO EmailedBridges " @@ -359,7 +359,7 @@ class Database: return True def getWarnedEmail(self, addr): - addr = sha.new(addr).hexdigest() + addr = hashlib.new(addr).hexdigest() cur = self._cur cur.execute("SELECT * FROM WarnedEmails WHERE " " email = ?", (addr,)) @@ -369,7 +369,7 @@ class Database: return True def setWarnedEmail(self, addr, warned=True, whenWarned=time.time()): - addr = sha.new(addr).hexdigest() + addr = hashlib.new(addr).hexdigest() t = timeToStr(whenWarned) cur = self._cur if warned == True:

1 0

[bridgedb/master] Fix typo in bridgedb.persistent module docstring.
by isis＠torproject.org 04 Feb '14

04 Feb '14

commit 7e030403a33a7f69f4b177a03a3fc1afcf7451fa Author: Isis Lovecruft <isis(a)torproject.org> Date: Fri Jan 31 12:35:31 2014 +0000 Fix typo in bridgedb.persistent module docstring. --- lib/bridgedb/persistent.py | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/lib/bridgedb/persistent.py b/lib/bridgedb/persistent.py index 4429ea4..311240a 100644 --- a/lib/bridgedb/persistent.py +++ b/lib/bridgedb/persistent.py @@ -9,7 +9,7 @@ # (c) 2007-2013, all entities within the AUTHORS file # :license: 3-clause BSD, see included LICENSE for information -"""Module for functionality to persistently storing state.""" +"""Module for functionality to persistently store state.""" import copy import logging

1 0

[bridgedb/master] Add draft status and related proposals for XXX-bridgedb-social-distribution.txt.
by isis＠torproject.org 04 Feb '14

04 Feb '14

commit d2a29558b5495950be87e6ccfa58012c8ab6b5d4 Author: Isis Lovecruft <isis(a)torproject.org> Date: Wed Oct 23 11:49:28 2013 +0000 Add draft status and related proposals for XXX-bridgedb-social-distribution.txt. --- doc/proposals/XXX-bridgedb-social-distribution.txt | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/doc/proposals/XXX-bridgedb-social-distribution.txt b/doc/proposals/XXX-bridgedb-social-distribution.txt index 538f6ae..5f44fcf 100644 --- a/doc/proposals/XXX-bridgedb-social-distribution.txt +++ b/doc/proposals/XXX-bridgedb-social-distribution.txt @@ -4,7 +4,9 @@ Filename: XXX-social-bridge-distribution.txt Title: Social Bridge Distribution Author: Isis Agora Lovecruft Created: 18 July 2013 -Status: Open +Related Proposals: 199-bridgefinder-integration.txt + XXX-bridgedb-database-improvements.txt +Status: Draft * I. Overview

1 0

[bridgedb/master] Start explaining the modification to remove Oblivious Transfer.
by isis＠torproject.org 04 Feb '14

04 Feb '14

commit 38cbe89f713b7d70d85576423ff33d27650b7503 Author: Isis Lovecruft <isis(a)torproject.org> Date: Tue Oct 29 20:38:01 2013 +0000 Start explaining the modification to remove Oblivious Transfer. Also add detailed, high-level description of the original usage of OT for bridge distribution, and why this is not needed within the modified threat model. However, it occurred to me while writing out the details that the k-TAA blind signatures (Au, Susilo, et al.) used in the original scheme *also* require a bilinear pairing, and are used independently to the usage of OT for creating the zero-knowledge PoKs of valid blind signatures on user commitments to the values representing the user's numbers of Credits (the coin-like things generated through one's bridges not getting blocked) and the user's timestamp for the last request for an Invite Ticket. As such, the signature scheme must either be re-evaluated and a different scheme used, or else we likely do not save any implementation overhead by ripping out the Oblivious Transfer (although doing so *does* still save on the rather high computational and network bandwidth complexities involved in OT). --- doc/proposals/XXX-bridgedb-social-distribution.txt | 237 +++++++++++++++++--- 1 file changed, 209 insertions(+), 28 deletions(-) diff --git a/doc/proposals/XXX-bridgedb-social-distribution.txt b/doc/proposals/XXX-bridgedb-social-distribution.txt index 541daca..cd211c6 100644 --- a/doc/proposals/XXX-bridgedb-social-distribution.txt +++ b/doc/proposals/XXX-bridgedb-social-distribution.txt @@ -159,9 +159,88 @@ Status: Draft XXX finishme - Modification: allow BridgeDB to be a malicious actor (protecting against it - at this point is too costly, instead we want to eliminate BridgeDB's - ability to obtain a social graph for Tor bridge users.) +**** Which Bridges a User is being given + + + o How many credits a User has + +** IV.A. Modifications + + The original rBridge scheme is modified to model BridgeDB as a potential + malicious actor. Protecting against this at this point in time is too + costly, both in terms of development time, as well as in network bandwidth + and computational overhead. Instead, prioritization should be placed on + eliminating BridgeDB's ability to obtain a social graph for Tor bridge + users, as this is not information it currently possesses. + + The rBridge scheme utilises 1-out-of-m Oblivious Transfer (OT) to allow + BridgeDB to blind a set of m Bridges, letting U pick (and thus learn the + address of) at most one out of the m Bridges. Think of it like a stage + magician waving a fanned deck of cards face down, and asking an audience + member to "pick a card! any card!" While the authors of the original paper + choose Naor and Pinkas' 1-out-of-m OT scheme [2] for its efficiency, they + failed to specify which of Naor and Pinkas' OT schemes ― as there are four + within the referenced paper and several more described elsewhere. For the + sake of continuing the argument against their recommendations to use OT + within the social bridge distribution scheme, it is presumed that the + rBridge authors were referring to the round-optimal 1-out-of-N oblivious + transfer scheme in §4 of that paper. + + During the OT process, for each Bridge in m, BridgeDB creates a Blind + Signature of the Bridge and tags each signature to its corresponding + Bridge, so that if U chooses that Bridge, she will also recieve the + signature. The signature schemes utilised is Au et al.'s k-TAA Blind + Signature scheme, [8] which requires a bilinear pairing (XXX what type?) + and is q-SDH secure in the standard model. That k-TAA scheme is chosen + because it is compatible with Zero-Knowledge Proofs-of-Knowledge (ZKPoK), + such that ZKPoK may be made for k-TAA signatures, as well as for + Commitments. Additionally, Au et al.'s k-TAA signature scheme is a + modification to that proposed by Camenisch and Stadler, i.e. it allows for + signatures on message vectors, provided that a nonce is included with the + message vector. See §VII.B for an open research question regarding k-TAA + signature schemes. + + Next, U creates a Pedersens Commitment (CMT) to the total amount of Credits + owned by U, and another commitment to the last time that U requested an + Invite Ticket. For each of these commitments, U obtains from BridgeDB + another k_-TAA blind signature on the commitment. Then, U constructs her + own Credential, consisting of the Bridge's tagged blind signature, the + blind signature on each of the commitments, and a hash of the nonce that + used as the blinding factor. (The hash of the nonce is included so that + multiple users may not collude to swap portions of their Credentials by + using the same blinding factor.) The Fiat-Shamir transformation is then + used to convert the aformentioned ZKPoK scheme into a Zero-Knowledge + Non-Interactive Proof-of-Knowledge (NIPK) scheme. With this, U send to D + a Proof of their Credential, without revealing any of its contents. + + Every so often, the User requests that BridgeDB update their Credential + with recently earned tokens. XXX finish describing this process + + When one of U's Bridges is "blocked", U notifies BridgeDB of the "block" + and, likely, if she has enough Credits to afford it, requests a new bridge. + In the original rBridge design, BridgeDB is only to acknowledge requests + for new bridges after confirming that the Bridge is indeed blocked. + + This is where the rBridge design begins to do a bit of handwaving. Either + that, or they neglected both to put sufficient effort into defining the + term "blocked", as well as enough thought into precisely how BridgeDB might + check this. Take for example a User behind a corporate firewall which + blocks undentified encrypted protocols: that User will report her Bridges + as "blocked" ― and they are, for her at least ― though for everyone else + they work just fine. BridgeDB can easily check Bridge reachability from + the location of BridgeDB's server, and possibly can check bridge + reachability from various network vantage points around the world (though + doing this without *causing* the Bridge to become blocked when checking + from censoring regions can quickly become quite complex). [9] + +[#]: Au, Man Ho, Willy Susilo, and Yi Mu. + "Proof-of-knowledge of representation of committed value and its + applications." Information Security and Privacy. + Springer Berlin Heidelberg, 2010. + http://web.science.mq.edu.au/conferences/acisp2010/program/Session%2010%20-… + +* V. Design +** V.A. Overview As mentioned, most of this proposal is based upon §IV of the rBridge paper, which is the non-privacy preserving portion of the paper. [1] The @@ -181,28 +260,79 @@ Status: Draft three Bridges, then 1-out-of-m OT is run three times: for each time, the following steps are taken: -* IV. Design + 1. User picks a set of m nonces and uses them to generate point in the + group G__1 via: -** IV.A. Overview + R + yⱼ̍ ⟵―― ℤ*ₚ, where 1 ≤ j ≤ m - As mentioned, most of this proposal is based upon §IV of the rBridge - paper, which is the non-privacy preserving portion of the paper. [0] The - reasons for deferring implementation of §V include: + 2. User computes a Non-Interactive Proof-of-Knowledge (NIPK) of the set + of nonces in the following manner: - - Adding a simpler out-of-band distribution of bridges. Requiring users to - copy+paste Bridge lines into their torrc is ridiculous. + ⎧ ⎛ ₘ ⎞ ₘ ⎡ yⱼ̍⎤ ⎫ + ᴨ₀ = NIPK ⎨ ⎜{yⱼ̍}ⱼ₌₁⎟: ∀ⱼ₌₁⎢ Yⱼ̍ = ɡ₁ ⎥ ⎬ + ⎩ ⎝ ⎠ ⎣ ⎦ ⎭ - - XXX + ⎛ ₘ ⎞ + and sends ⎜{Yⱼ̍}ⱼ₌₁ ⃦ ᴨ₀⎟ to BridgeDB. + ⎝ ⎠ - Modifications: + 3. BridgeDB verifies the NIPK of the set of nonces, ᴨ₀, and then created + a one-time keypair: - - Remove OT, keep blind signatures and Pedersen's Commitments. + R ₛₖ⁰ + sk⁰ ⟵―― ℤ*ₚ, pk⁰ = h - XXX finishme + For each available bridge Bⱼ, BridgeDB randomly selects + + R + eⱼ̊,yⱼ̎ ⟵―― ℤ*ₚ, + + computes 1 + ――――――――― + ⎛ yⱼ̎ Bⱼ ⎞ eⱼ̊ + ₛₖ⁰ + Aⱼ̊ = ⎜ g₀g₁ Yⱼ̍g₃ ⎟ + ⎝ ⎠ + + and tags (Aⱼ̊,eⱼ̊,yⱼ̎) to Bⱼ. -** IV.C. Data Formats + 4. After OT… ZKNIPK… XXX -*** 1. User Credential + Specifically, the 1-out-of-m OT scheme used within the "Part V: rBridge + with Privacy Preservation" section of the paper is described in + "Efficient oblivious transfer protocols" by M. Naor and B. Pinkas. [2] It + requires the use of a bilinear group pairing on a Type-3 supersingular + elliptic curve. + + Unfortunately, there are very few FLOSS libraries which currently exist + for pairing-based cryptography. The one used in the benchmarking section + of the rBridge paper is libpbc [3] from Stanford University. Several + cryptographers have offhandedly remarked to me that I should not use this + library in any deployed system. When I mentioned the need for a vetted + pairing-based cryptographic library to Dr. Tanja Lange, she replied that + she has a graduate student working on it -- though when this new library + will be complete is uncertain. + + libpbc has Python bindings, although pypbc [4] is quite incomplete and + only in py3k. Additionally, pypbc requires dynamic library overloading of + the shared object libraried for both libpbc and libgmp (the Gnu + Multi-Precision library, [5] which allows for calculations of arbitrary + precision on floats). + + Rather than waiting for Dr. Lange's student to complete the new library, + I propose spending some small amount of time (not more than a couple + weeks) creating Python2 bindings for libpbc. From my experience, the + simplest, least error-prone method for creating Python bindings to C + libraries (and with the least amount of effort/knowledge of internal + Python functions involved) is to use CFFI. [7] + + - Pedersens' Commitments + + - For ZKPoK + +** V.C. Data Formats + +*** 1. User Credential A Credential is a signed document obtained from BridgeDB. It contains all of the state required to verify honest client behavior, and is formatted @@ -294,22 +424,73 @@ Status: Draft meeting in München, and he agreed that little-t tor isn't where this code should go. +** VI.B. Anonymous Authentication/Signature Schemes? + + As the property of conditional anonymity of k-TAA blind signatures is not + utilised in any version of the social bridge distribution design, some + research should be done on other Anonymous or Partial signature schemes + which allow signatures to be made on message vectors. The k-TAA + signature scheme used in rBridge, designed by Au et al., [XXX] was based + off of one of Camenisch and Lysyanskaya's signature schemes. (Which one?) + + Of particular interest, the cryptologists Camenisch and Lysyanskaya have + several schemes for various types of anonymous signatures, with varying + properties, as well as "A Formal Treatment of Onion Routing." [XXX] I am + under the impresseion that when they say "anonymous" they mean in the + strong sense (versus other cryptologists who attempt to design signature + schemes with "revocable anonymity", for example, trusted Centralised-PKI + Anonymous Proxy Signature schemes, or signature schemes with "anonymity" + that is revocable by a third party). [XXX] + + Specifically, one paper, "Randomizable Proofs and Delegatable Anonymous + Credentials" by Camenisch and Lysyanskaya could be applicable to + simultaneously ensuring all of the following properties for Invite + Tickets: + + * The Unlinkability of a generated Invite Ticket to one used later for + registration. + * Strong Anonymity for the holders of such Invite Tickets and for their + eventual recipients. Many "unlinkable token" schemes which rely on + blind signatures, i.e. Chaum's tokens, remain vulnerable to a + particular deanonymisation attack if the Signer is modelled as a + "curious" or malicious entity who stores records of the protocol + steps for blind signatures. [XXX explain] + * Unforgeability + * Verifiability + +* VII. Dependencies Upon Other Tor Software +** VII.A. Tor Controllers +*** 1. Proposal #199: Integration of BridgeFinder and BridgeFinderHelper + + The client-side code of BridgeDB will essentially be acting as a + BridgeFinder, and thus BridgeDB will require a client-side mechanism for + communication with various Tor Controllers. This is necessary in order to + present a discovery mechanism whereby a Tor Controller may learn the + current number of Credits and Invite Tickets available to a User, and may + display this information in some meaningful manner. + * References -[0]: http://www-users.cs.umn.edu/~hopper/rbridge_ndss13.pdf -[1]: https://twistedmatrix.com/documents/current/api/twisted.protocols.memcache.… -[2]: http://stackoverflow.com/a/5162203 -[3]: http://findingscience.com/twisted/python/memcache/2012/06/09/txyam:-yet-ano… -[4]: https://pypi.python.org/pypi/txredis -[5]: https://github.com/fiorix/txredisapi -[6]: https://github.com/andymccurdy/redis-py/ -[7]: http://www.dr-josiah.com/2012/03/why-we-didnt-use-bloom-filter.html -[8]: http://redis.io/topics/data-types §"Strings" - -[#]: Naor, Moni, and Benny Pinkas. "Efficient oblivious transfer protocols." +[0]: Ayad, Hanan. "Growth Rate of the Binomial Coefficient." + Lecture Notes on SYDE423 - Computer Algorithm Design and Analysis. + University of Waterloo, Canada, 2008. + http://www.hananayad.com/teaching/syde423/binomialCoefficient.pdf +[1]: http://www-users.cs.umn.edu/~hopper/rbridge_ndss13.pdf +[2]: Naor, Moni, and Benny Pinkas. "Efficient oblivious transfer protocols." Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2001. http://www.wisdom.weizmann.ac.il/%7Enaor/PAPERS/eotp.ps https://gitweb.torproject.org/user/isis/bridgedb.git/tree/refs/heads/featur… - +[3]: https://crypto.stanford.edu/pbc/ + http://repo.or.cz/r/pbc.git +[4]: https://www.gitorious.org/pypbc/pages/Documentation + git@gitorious.org:pypbc/pypbc.git +[5]: http://gmplib.org/ +[6]: https://metrics.torproject.org/formats.html#descriptortypes +[7]: https://bitbucket.org/cffi/cffi +[8]: Au, Man Ho, Willy Susilo, and Yi Mu. "Constant-size dynamic k-TAA." + Security and Cryptography for Networks. + Springer Berlin Heidelberg, 2006. 111-125. + http://ro.uow.edu.au/cgi/viewcontent.cgi?article=10257&context=infopapers +[19]: https://trac.torproject.org/projects/tor/ticket/6396#comment:16

1 0

[bridgedb/master] Start detailing reasoning and proofs for rBridge modifications.
by isis＠torproject.org 04 Feb '14

04 Feb '14

commit adcb1c105465ac4b7479dd412ac36dc2cc6a7eeb Author: Isis Lovecruft <isis(a)torproject.org> Date: Thu Oct 24 18:02:11 2013 +0000 Start detailing reasoning and proofs for rBridge modifications. --- doc/proposals/XXX-bridgedb-social-distribution.txt | 170 +++++++------------- 1 file changed, 62 insertions(+), 108 deletions(-) diff --git a/doc/proposals/XXX-bridgedb-social-distribution.txt b/doc/proposals/XXX-bridgedb-social-distribution.txt index 7274132..541daca 100644 --- a/doc/proposals/XXX-bridgedb-social-distribution.txt +++ b/doc/proposals/XXX-bridgedb-social-distribution.txt @@ -12,7 +12,7 @@ Status: Draft This proposal specifies a system for social distribution of the centrally-stored bridges within BridgeDB. It is primarily based upon Part - IV of the rBridge paper, [0] utilising a coin-based incentivisation scheme + IV of the rBridge paper, [1] utilising a coin-based incentivisation scheme to ensure that malicious users and/or censoring entities are deterred from blocking bridges, as well as socially-distributed invite tickets to prevent such malicious users and/or censoring entities from joining the pool of @@ -114,23 +114,72 @@ Status: Draft assumed to be honest in all protocols, and no protections are taken to protect clients from malicious behaviour from BridgeDB. -** III.A. Modifications +**** Why we should still hide the Credential from BridgeDB: + + Lemma 1: + + A User Credential contains that User's list of Bridges, and thus, in all + probability, it uniquely identifies the User. + + Proof 1: + + For simplicity's sake, if we falsely assume ☥ that the Bridges in a + User's Credential is a constant and static number, then an estimate for + the number of possible Credentials is given by: + + Γ(n+1) + nCₖ = ⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽ + Γ(m+1)Γ(-m+n+1) + ⎛n⎞ + for the binomial coefficient ⎝m⎠, where n is the number of Bridges, m is + the number of Bridges in a User Credential, and Γ is the gamma function. + ⎛5000⎞ + With ⎝ 3 ⎠ there are 2.0820835 x 10¹⁰ possible Credentials, or, roughly + three unique Credentials for every one of the seven billion people alive + on Earth today. The binomial coefficient grows tetrationally for + increasing n and increasing m, [0] and so as the number of Bridge relays + grows over time, and with Users perpetually appending newer Bridges to + their Creditials, the probability of colliding Credentials decreases + tetrationally. Therefore, Credentials are taken to be unique. + + Because the Credentials are uniquely identifying, care should be taken so + that two User Credentials cannot be linked by BridgeDB, as this would allow + BridgeDB to obtain a social graph of the network of Bridge Users. + Therefore, it is necessary to hide the Credential from BridgeDB; otherwise, + when requesting an Invite Ticket, the User openly sending their Credential + to BridgeDB to prove possession of the minimum number of Credits would be + linkable to the created Invite Ticket. + + ---------- + ☥ It would actually be some complicated series of binomial coefficients with + respect to the individual q-binomial coefficients with q being a + differential of the Bridge turnover w.r.t. time. + +*** 1. BridgeDB is permitted to know the following information: - + XXX finishme Modification: allow BridgeDB to be a malicious actor (protecting against it at this point is too costly, instead we want to eliminate BridgeDB's ability to obtain a social graph for Tor bridge users.) + As mentioned, most of this proposal is based upon §IV of the rBridge + paper, which is the non-privacy preserving portion of the paper. [1] The + reasons for deferring implementation of §V include: -*** 1. BridgeDB is permitted to know the following information: + - Adding a simpler out-of-band distribution of bridges. Requiring users to + copy+paste Bridge lines into their torrc is ridiculous. - - + - XXX - XXX finishme + Modifications to the original rBridge scheme: + - Remove Oblivious Transfer, keep blind signatures and Pedersen's Commitments. + rBridge uses 1-out-of-m Oblivious Transfer (OT) in order to allow each + client to choose their own Bridges. Simply put, if a User is to be given + three Bridges, then 1-out-of-m OT is run three times: for each time, the + following steps are taken: * IV. Design @@ -188,107 +237,12 @@ Status: Draft 'LearnedTS': 1382078292.864117}], 'CredentialTS': 982398423, 'TotalUnspentCredits': 10} - -*** XXX other formats - -* V. Databases - -** V.A. Scalability Requirements - - Databases SHOULD be implemented in a manner which is ammenable to using a - distributed storage system; this is necessary because certain types of data - MUST be stored permanently, such as the list of hashes of spent tokens, or - the list of hashes of used invite tickets. - - Additionally, doing so promotes modularisation the components of BridgeDB, - such that the BridgeDistributor XXX can be separated from the backend - storage system, BridgeDB. - -*** 1. Distributed Database System - - A distributed database system SHOULD be used for BridgeDB, in order to - scale resources as the number of Tor bridge users grows. This database - system, hereafter referred to as DDBS. - - The DDBS MUST be capable of working within Twisted's asynchronous - framework. If possible, a Object-Relational Mapper (ORM) SHOULD be used to - abstract the database backend's structure and query syntax from the - Twisted Python classes which interact with it, so that the type of - database may be swapped out for another with less code refactoring. - - The DDBM SHALL be used for persistent storage of complex data structures - such as the bridges, which MAY include additional information from both - the XXX @type-bridge-relay descriptors and the @type-bridge-extra-info - descriptors. - - [#]: https://github.com/couchbase/couchbase-python-client#twisted-api - -**** 1.a. Data Structures which should be stored in a DDBS: - - - RedactedDB - The Database of Blocked Bridges - The RedactedDB will hold entries of bridges which have been discovered - to be unreachable from BridgeDB network vantage point, or have been - reported unreachable by clients. +*** XXX other formats - - - -*** 2. Relational Database Mapping Server - - For simpler data structures which must be persistently stored, such as the - list of hashes of previously seen Invite Tickets, or the list of - previously spent Tokens, a Relational Database Mapping Server (RDBMS) - SHALL be used for optimisation of queries. - - Redis and Memcached are two examples of RDBMS which are well tested and - are known to work well with Twisted. The major difference between the two - is that Memcached is volatile, while Redis supports command for - transferring objects into persistent on-disk storage. There are several - (see Twisted's MemCacheProtocol class [1] [2] or txyam [3] for Memcached, - and txredis [4] or txredisapi [5] for Redis). For non-Twisted Python Redis - APIs, there is redis-py, which provides a connection pool that could - likely be interfaced with from Twisted Python without too much - difficultly. [6] - - In order to further decrease the need for lookups in the backend - databases, Bloom Filters can used to eliminate extraneous - queries. However, this optimization would only be beneficial for string - lookups, i.e. querying for a user's credential, and SHOULD NOT be used for - queries within any of the hash lists, i.e. the list of hashes of - previously seen invite tickets. [7] It might be possible to use Redis' - GETBIT and SETBIT commands to store a Bloom Filter within a Redis cache - system; [8] doing so would offload the severe memory requirements of - loading the Bloom Filter into memory in Python when inserting new entries, - reducing the time complexity to order O(1) from some (polynomial) time - complexity that is proportional to the integral of the number of bridge - users over the rate of change of bridge users over time. - - XXX expire credentials [#] redis key datatype - [#]: http://redis.io/commands/pexpireat - - XXX evaluation on data by calling the sha1 for a serverside Lua script [#] - [#]: http://redis.io/commands/evalsha - - XXX mediawiki notes and references on switching to redis - [#]: https://www.mediawiki.org/wiki/Redis - - XXX using redis as a message queue for job scheduling - [#]: http://www.restmq.com/ - - -**** 2.a. Data Structures which should be stored in a RDBMS - - - User Credentials - - - Invite Tickets - - - Spent Credits - -* VI. Open Questions - -** VI.A. In which component of the Tor ecosystem should the client application code go? - -*** 1. Should this be done as a Pluggable Transport? +* VI. Open Questions +** VI.A. In which component of the Tor ecosystem should the client application code go? +*** 1. Should this be done as a Pluggable Transport? Considerations: @@ -299,7 +253,7 @@ Status: Draft any of the user's application level traffic. However, the clientside system of rBridge must start when TBB (or tor) is started. -**** b. It needs to be able to start tor. +**** 1b. It needs to be able to start tor. This is necessary because the lines: {{{ @@ -310,7 +264,7 @@ Status: Draft settings via SIGHUP. **** 1c. TorLaucher is not the correct place for this functionality. - + I am *not* adding this to TorLauncher. The clientside of rBridge will eventually need to handle a lot of complicated new cryptographic primitives, including commitments and zero-knowledge proofs. This is

1 0

[bridgedb/master] Separate backend database improvements into their own proposal.
by isis＠torproject.org 04 Feb '14

04 Feb '14

commit 92ee780e102f3574f57f18191641a3ca1e9c0af1 Author: Isis Lovecruft <isis(a)torproject.org> Date: Wed Oct 23 18:32:02 2013 +0000 Separate backend database improvements into their own proposal. --- .../XXX-bridgedb-database-improvements.txt | 260 ++++++++++++++++++++ 1 file changed, 260 insertions(+) diff --git a/doc/proposals/XXX-bridgedb-database-improvements.txt b/doc/proposals/XXX-bridgedb-database-improvements.txt new file mode 100644 index 0000000..2d25bd2 --- /dev/null +++ b/doc/proposals/XXX-bridgedb-database-improvements.txt @@ -0,0 +1,260 @@ +# -*- coding: utf-8 ; mode: org -*- + +Filename: XXX-bridgedb-database-improvements.txt +Title: "Scalability and Stability Improvements to BridgeDB: Switching to a + Distributed Database System and RDBMS" +Author: Isis Agora Lovecruft +Created: 12 Oct 2013 +Related Proposals: XXX-social-bridge-distribution.txt +Status: Open + +* I. Overview + + BridgeDB is Tor's Bridge Distribution system, which currently has two major + Bridge Distribution mechanisms: the HTTPS Distributor and an Email + Distributor. [0] + + BridgeDB is written largely in Twisted Python, and uses Python2's builtin + sqlite3 as its database backend. Unfortunately, this backend system is + already showing strain through increased times for queries, and sqlite's + memory usage is not up-to-par with modern, more efficient, NoSQL databases. + + In order to better facilitate the implementation of newer, more complex + Bridge Distribution mechanisms, several improvements should be made to the + underlying database system of BridgeDB. Additionally, I propose that a + clear distinction in terms, as well as a modularisation of the codebase, be + drawn between the mechanisms for Bridge Distribution versus the backend + Bridge Database (BridgeDB) storage system. + + This proposal covers the design and implementation of a scalable NoSQL ― + Document-Based and Key-Value Relational ― database backend for storing data + on Tor Bridge relays, in an efficient manner that is ammenable to + interfacing with the Twisted Python asynchronous networking code of current + and future Bridge Distribution mechanisms. + +* II. Terminology + + BridgeDistributor := A program which decides when and how to hand out + information on a Tor Bridge relay, and to whom. + + BridgeDB := The backend system of databases and object-relational mapping + servers, which interfaces with the BridgeDistributor in order + to hand out bridges to clients, and to obtain and process new, + incoming ``@type bridge-server-descriptors``, + ``@type bridge-networkstatus`` documents, and + ``@type bridge-extrainfo`` descriptors. [3] + + BridgeFinder := A client-side program for an Onion Proxy (OP) which handles + interfacing with a BridgeDistributor in order to obtain new + Bridge relays for a client. A BridgeFinder also interfaces + with a local Tor Controller (such as TorButton or ARM) to + handle automatic, transparent Bridge configuration (no more + copy+pasting into a torrc) without being given any + additional privileges over the Tor process, [1] and relies + on the Tor Controller to interface with the user for + control input and displaying up-to-date information + regarding available Bridges, Pluggable Transport methods, + and potentially Invite Tickets and Credits (a cryptographic + currency without fiat value which is generated + automatically by clients whose Bridges remain largely + uncensored, and is used to purchase new Bridges), should a + Social Bridge Distributor be implemented. [2] + +* III. Databases +** III.A. Scalability Requirements + + Databases SHOULD be implemented in a manner which is ammenable to using a + distributed storage system; this is necessary because many potential + datatypes required by future BridgeDistributors MUST be stored permanently. + For example, in the designs for the Social Bridge Distributor, the list of + hash digests of spent Credits, and the list of hash digests of redeemed + Invite Tickets MUST be stored forever to prevent either from being replayed + ― or double-spent ― by a malicious user who wishes to block bridges faster. + Designing the BridgeDB backend system such that additional nodes may be + added in the future will allow the system to freely scale in relation to + the storage requirements of future BridgeDistributors. + + Additionally, requiring that the implementation allow for distributed + database backends promotes modularisation the components of BridgeDB, such + that BridgeDistributors can be separated from the backend storage system, + BridgeDB, as all queries will be issued through a simplified, common API, + regardless of the number of nodes system, or the design of future + BridgeDistributors. + +*** 1. Distributed Database System + + A distributed database system SHOULD be used for BridgeDB, in order to + scale resources as the number of Tor bridge users grows. This database + system, hereafter referred to as DDBS. + + The DDBS MUST be capable of working within Twisted's asynchronous + framework. If possible, a Object-Relational Mapper (ORM) SHOULD be used to + abstract the database backend's structure and query syntax from the Twisted + Python classes which interact with it, so that the type of database may be + swapped out for another with less code refactoring. + + The DDBM SHALL be used for persistent storage of complex data structures + such as the bridges, which MAY include additional information from both the + `@type bridge-server-descriptor`s and the `@type bridge-extra-info` + descriptors. [3] + +**** 1.a. Choice of DDBS + + CouchDB is chosen for its simple HTTP API, ease of use, speed, and official + support for Twisted Python applications. [4] Additionally, its + document-based data model is very similar to the current archetecture of + tor's Directory Server/Mirror system, in that an HTTP API is used to + retrieve data stored within virtual directories. Internally, it uses JSON + to store data and JavaScript as its query language, both of which are + likely friendlier to various other components of the Tor Metrics + infrastructure which sanitise and analyse portions of the Bridge + descriptors. At the very least, friendlier than hardcoding raw SQL queries + as Python strings. + +**** 1.b. Data Structures which should be stored in a DDBS: + + - RedactedDB - The Database of Blocked Bridges + + The RedactedDB will hold entries of bridges which have been discovered to + be unreachable from BridgeDB network vantage point, or have been reported + unreachable by clients. + + - BridgeDB - The Database of Bridges + + BridgeDB holds information on available Bridges, obtained via bridge + descriptors and networkstatus documents from the BridgeAuthority. Because + a Bridge may have multiple `ORPort`s and multiple + `ServerTransportListenAddress`es, attaching additional data to each of + these addresses which MAY include the following information on a blocking + event: + - Geolocational country code of the reported blocking event + - Timestamp for when the blocking event was first reported + - The method used for discovery of the block + - an the believed mechanism which is causing the block + would quickly become unwieldy, the RedactedDB and BridgeDB SHOULD be kept + separate. + + - User Credentials + + For the Social BridgeDistributor, these are rather complex, + increasingly-growing, concatenations (or tuples) of several datatypes, + including Non-Interactive Proofs-of-Knowledge (NIPK) of Commitments to + k-TAA Blind Signatures, and NIPK of Commitments to a User's current + number of Credits and timestamps of requests for Invite Tickets. + +*** 2. Key-Value Relational Database Mapping Server + + For simpler data structures which must be persistently stored, such as the + list of hashes of previously seen Invite Tickets, or the list of + previously spent Tokens, a Relational Database Mapping Server (RDBMS) + SHALL be used for optimisation of queries. + + Redis and Memcached are two examples of RDBMS which are well tested and + are known to work well with Twisted. The major difference between the two + is that Memcaches are stored only within volatile memory, while Redis + additionally supports commands for transferring objects into persistent, + on-disk storage. + + There are several support modules for interfacing with both Memcached and + Redis from Twisted Python, see Twisted's MemCacheProtocol class [5] [6] or + txyam [7] for Memcached, and txredis [8] or txredisapi [9] for + Redis. Additionally, numerous big name projects both use Redis as part of + their backend systems, and also provide helpful documentation on their own + experience of the process of switching over to the new systems. [17] For + non-Twisted Python Redis APIs, there is redis-py, which provides a + connection pool that could likely be interfaced with from Twisted Python + without too much difficultly. [10] [11] + +**** 2.a. Data Structures which should be stored in a RDBMS + + Simple, mostly-flat datatypes, and data which must be frequently indexed + should be stored in a RDBMS, such as large lists of hashes, or arbitrary + strings with assigned point-values (i.e. the "Uniform Mapping" for the + current HTTPS BridgeDistributor). + + For the Social BridgeDistributor, hash digests of the following datatypes + SHOULD be stored in the RDBMS, in order to prevent double-spending and + replay attacks: + + - Invite Tickets + + These are anonymous, unlinkable, unforgeable, and verifiable tokens + which are occasionally handed out to well-behaved Users by the Social + BridgeDistributor to permit new Users to be invited into the system. + When they are redeemed, the Social BridgeDistributor MUST store a hash + digest of their contents to prevent replayed Invite Tickets. + + - Spent Credits + + These are Credits which have already been redeemed for new Bridges. + The Social BridgeDistributor MUST also store a hash digest of Spent + Credits to prevent double-spending. + +*** 3. Bloom Filters and Other Database Optimisations + + In order to further decrease the need for lookups in the backend + databases, Bloom Filters can used to eliminate extraneous + queries. However, this optimization would only be beneficial for string + lookups, i.e. querying for a User's Credential, and SHOULD NOT be used for + queries within any of the hash lists, i.e. the list of hashes of + previously seen Invite Tickets. [14] + +**** 3.a. Bloom Filters within Redis + + It might be possible to use Redis' GETBIT and SETBIT commands to store a + Bloom Filter within a Redis cache system; [15] doing so would offload the + severe memory requirements of loading the Bloom Filter into memory in + Python when inserting new entries, reducing the time complexity from some + polynomial time complexity that is proportional to the integral of the + number of bridge users over the rate of change of bridge users over time, + to a time complexity of order O(1). + +**** 3.b. Expiration of Stale Data + + Some types of data SHOULD be safe to expire, such as User Credentials + which have not been updated within a certain timeframe. This idea should + be further explored to assess the safety and potential drawbacks to + removing old data. + + If there is data which SHOULD expire, the PEXPIREAT command provided by + Redis for the key datatype would allow the RDBMS itself to handle cleanup + of stale data automatically. [16] + +**** 4. Other potential uses of the improved Bridge database system + + Redis provides mechanisms for evaluations to be made on data by calling + the sha1 for a serverside Lua script. [15] While not required in the + slightest, it is a rather neat feature, as it would allow Tor's Metrics + infrastructure to offload some of the computational overhead of gathering + data on Bridge usage to BridgeDB (as well as diminish the security + implications of storing Bridge descriptors). + + Also, if Twisted's IProducer and IConsumer interfaces do not provide + needed interface functionality, or it is desired that other components of + the Tor software ecosystem be capable of scheduling jobs for BridgeDB, + there are well-tested mechanisms for using Redis as a message + queue/scheduling system. [16] + +* References + +[0]: https://bridges.torproject.org + mailto:bridges@bridges.torproject.org +[1]: See proposals 199-bridgefinder-integration.txt at + https://gitweb.torproject.org/torspec.git/blob/HEAD:/proposals/199-bridgefi… +[2]: See XXX-social-bridge-distribution.txt at + https://gitweb.torproject.org/user/isis/bridgedb.git/blob/refs/heads/featur… +[3]: https://metrics.torproject.org/formats.html#descriptortypes +[4]: https://github.com/couchbase/couchbase-python-client#twisted-api +[5]: https://twistedmatrix.com/documents/current/api/twisted.protocols.memcache.… +[6]: http://stackoverflow.com/a/5162203 +[7]: http://findingscience.com/twisted/python/memcache/2012/06/09/txyam:-yet-ano… +[8]: https://pypi.python.org/pypi/txredis +[9]: https://github.com/fiorix/txredisapi +[10]: https://github.com/andymccurdy/redis-py/ +[11]: http://degizmo.com/2010/03/22/getting-started-redis-and-python/ +[12]: http://www.dr-josiah.com/2012/03/why-we-didnt-use-bloom-filter.html +[13]: http://redis.io/topics/data-types §"Strings" +[14]: http://redis.io/commands/pexpireat +[15]: http://redis.io/commands/evalsha +[16]: http://www.restmq.com/ +[17]: https://www.mediawiki.org/wiki/Redis

1 0