btd

README

Challenge Bypass Server

This is a TCP server that is compatible with the Privacy Pass browser extension. In particular, the server implements the server-side actions in a 'blind signing' protocol. The protocol is based on a variant of a Verifiable, Oblivious Pseudorandom Function (VOPRF) established by Jarecki, Kiayias and Krawczyk. When adapted to our needs, this scheme allows us to achieve the same goals as a 'Blind RSA' variant but using faster primitives, less bandwidth, and simpler secret-key operational logistics in comparison.

Contents

• Quickstart
• Current functionality
• Overview of design
  • Preliminaries
  • Message formats
    • Issuance request
    • Issue response
    • Redemption request
    • Redemption response
  • Protocol overview
    • NIZK proofs of discrete-log equality
    • Batch proofs
• Team
• Acknowledgements

Quickstart

To run the server:

go run server/main.go --key testdata/p256-key.pem --comm testdata/test-p256-commitment

here, key is the current secret key used for signing, comm is the public commitment to the signing key.

To demo token issuance:

cat testdata/bl_sig_req | nc localhost 2416

Keys that are only valid for verifying token redemptions can be provided in a single .pem file. For example, using:

--redeem_keys testdata/p256-redeem-keys.pem

the signing key, is automatically also used for redemption.

For a full client implementation, and further details on required message formatting and technical considerations, see the browser extension.

Current functionality

• Signs blinded tokens and generates valid batch DLEQ proof
• Verifies redemption tokens

Overview of design

Preliminaries

A message authentication code (MAC) on a message is a keyed authentication tag that can be only be created and verified by the holder of the key.

A pseudorandom function is a function whose output cannot be efficiently distinguished from random output. This is a general class of functions; concrete examples include hashes and encryption algorithms.

An oblivious pseudorandom function (OPRF) is a two-party protocol between sender S and receiver R for securely computing a pseudorandom function f_x(·) on key x contributed by S and input t contributed by R, in such a way that receiver R learns only the value f_x(t) while sender S learns nothing from the interaction. The output of an OPRF on some input t is known as a signature for t.

In this protocol, the edge (also referred to as the server) is the "sender" holding x and the inputs t are the tokens. So the clients don't learn our key and we don't learn the token values.

Message formats

We provide a brief overview of the message types that are sent and received by this plugin. These messages are sent and received in base64 encoding and JSON structs are used where appropriate. These formats differ slightly from those sent/received by the corresponding browser extension which uses intermediate HTTP communications with the edge before messages reach here.

In the following || will denote concatenation.

Issuance request

JSON struct used for requesting signatures on blinded tokens.

• <blind-token> is a randomly sampled, blinded elliptic curve point (this point is sent in compressed format as defined in Section 2.3.3 of http://www.secg.org/sec1-v2.pdf). The blind is also randomly sampled with respect to the same group.

• <contents> is an array of N <blind-token> objects.

• <Issue-JSON-struct>:

  {
      "type": "Issue",
      "contents": "<contents>",
  }
  

• <Wrapped-Issue> is the message that is actually received:

  {
      "bl_sig_req": "base64(<Issue-JSON-struct>)",
  }
  

Issue response

Marshaled array used for sending signed tokens back to a client.

• <signed-tokens> is an array of compressed elliptic curve point, as above, that have been 'signed' by the edge.

• <proof> is a base64 encoded JSON struct containing the necessary information for carrying out a DLEQ proof verification. In particular it contains base64 encodings of compressed elliptic curve points G,Y,M,Z along with response values R and C for streamlining the proof verification. See below for more details.

• <M> and <Z> are base64 encoded compressed elliptic curve points. <C> is a base64 encoded array of bytes used for checking completeness.

• <batch-proof> is a JSON struct of the form:²

  {
      "proof":"<proof>",
      "M":"<M>",
      "Z":"<Z>",
      "C":"<C>",
  }
  

² Other VRF implementations use different notation to us. We have tried to coincide as much as possible with these works.

• <Batch-DLEQ-Resp>:

  "batch-proof=" || <batch-proof>

• Issue response:

  base64(<signed-tokens> || <Batch-DLEQ-Resp>)

Redemption request

Primary client request that is verified by btd

• <token> is an original token generated for an issuance request.

• <shared-point> is the corresponding unblinded, signed point received from an issuance response. This point is SEC1 encoded.

• <shared-info> is some shared information that is used for deriving a HMAC key (usually a host header and a http path)

• HMAC() is a HMAC function that uses SHA256

• <derived-key> is the derived key output by:

  HMAC("hash_derive_key", <token>, <shared-point>)

• <request-binding> is the output of the following:

  HMAC("hash_request_binding", <derived-key>, <shared-info>)

• <Redeem-JSON-struct>:

  {
      "type":"Redeem",
      "contents":"<request-binding>"
  }
  

• <Wrapped-Redeem> is the JSON struct that is actually received:

  {
      "bl_sig_req":"base64(<Redeem-JSON-struct>)",
      "host":"<host>"
      "http":"<http-path>"
  }
  

Redemption response

Server response header used if errors occur. If this header is sent the plugin discards all stored tokens.

• <resp-val> is the value returned by btd on verification. Returns "success" on successful verification. If an error has occurred then it takes the value 5 or 6, where 5 is a connection error and 6 is a token verification error.

Protocol overview

We detail a 'blind-signing' protocol written by George Tankersley that uses a VOPRF to contruct per-token shared keys for a MAC over each redemption request. This hides the token values themselves until redemption and obviates the need for public key encryption. A full technical overview of this protocol can be read here.

Given a group setting and three hashes H_1, H_2, H_3 we build a commitment to a random token per request using a secret key x held by the edge servers. H_1 and H_2 are hash functions onto, respectively, the group and {0, 1}^λ where λ is a security parameter. The edge (or server) also publishes publicly a generator G along with a commitment (or 'public key') Y = xG (in the code we use H instead of Y but use Y to avoid conflict with the hash functions that we use). The pair (G,Y) is used for generating discrete-log equivalence proofs (DLEQs). We provide a brief overview of the how DLEQs are generated and verified below.

1. Client generates random token t and a blinding factor r.
2. Client calculates T = H_1(t) and sends M = rT to the edge along with a CAPTCHA solution.
3. Edge validates the solution and computes Z = xM = rxT and a DLEQ proof π dependent on the output of H_3 over G,Y,M,Z and other group elements -- see below for more details.
4. The edge returns (Z,π) to the client.
5. Client unblinds Z to retrieve N = r^(-1)Z = xT and stores the pair (t,N).
6. When the client wants to redeem a token it presents (t, MAC(request-binding-data)) where request-binding-data is made of information observable by the edge that is unique(ish) to that particular request.
7. The edge uses T as a double-spend index and recalculates N using x. Then it can validate the MAC using the shared key.
8. We know that a matching commitment value is valid because generating it requires access to x.

NIZK proofs of discrete-log equality

In step (3.) above, we call for a zero-knowledge proof of the equality of a discrete logarithm (our edge key) with regard to the returned token Z that the client receives. This allows the client to verify that the same key x is being used to 'sign' all tokens that are sent to the edge.

The protocol naturally provides Z = xM in the edge response. To ensure that the edge has not used unique x value to tag users, we require them to publish a public key, Y = xG, as mentioned above. We can now use a Chaum-Pedersen proof [CP93] to prove in zero knowledge that log_G(Y) == log_M(Z). We note this as DLEQ(Z/M == Y/G).

The proof follows the standard non-interactive Schnorr pattern. For a group of prime order q with orthogonal generators M, G, public key Y, and point Z:

1. Prover chooses a random nonce

    k <--$-- Z/qZ
   

2. Prover commits to the nonce k with respect to both generators

    A = kG, B = kM
   

3. Prover constructs the challenge

    c = H_3(G,Y,M,Z,A,B)
   

4. Prover calculates response

    s = k - cx (mod q)
   

5. Prover sends (c, s) to the verifier

6. Verifier recalculates commitments

    A' = sG + cY
    B' = sM + cZ
   

7. Verifier hashes

    c' = H_3(G,Y,M,Z,A',B')
   

   and checks that c == c'.

If all users share a consistent view of the tuple (G,Y) for each key epoch, they can all prove that the tokens that every client has been issued share the same anonymity set with respect to x. One way to ensure this consistent view is to pin one key at a time in each copy of the client and use software update mechanisms for rotation. A more flexible way is to pin a reference that allows each client to fetch the latest version of the key from a trusted location. We currently use the former method but plan to migrate to the latter in the near future.

Batch proofs

In practice, the issuance protocol operates over sets of tokens rather than just one. A system parameter, m, determines how many tokens a user is allowed to request per valid CAPTCHA solution. Consequently, users generate (t_1, t_2, ... , t_m) and (r_1, r_2, ... , r_m); send (M_1, M_2, ... , M_m) to the edge; and receive (Z_1, Z_2 ... , Z_m) in response.

Generating an independent proof of equality for each point implies excess overhead in both computation and bandwidth consumption. Therefore, we employ a batch proof to show consistent key usage for an entire set of tokens at once. The proof is a parallelized Schnorr protocol for the common-exponent case taken from [Hen14] and adapted for non-interactivity:

Given (G, Y, q); (M_1,...,M_m), (Z_1, ... ,Z_m); Z_i = k(M_i) for i = 1...m

1. Prover calculates a seed using:

    z = H_3(G, Y, M_1, ... , M_m, Z_1, ... , Z_m)
   

2. Prover initializes PRNG(z) and samples from it to non-interactively generate

    c_1, ... , c_m <--$-- Z/qZ.
   

3. Prover generates composite group elements M and Z

    M = (c_1*M_1) + (c_2*M_2) + ... + (c_m*M_m)
    Z = (c_1*Z_1) + (c_2*Z_2) + ... + (c_m*Z_m)
   

4. Prover sends proof

    (c, s) <-- DLEQ(M/Z == Y/G)
   

5. Verifier recalculates the PRNG seed from protocol state, generates the composite elements, and checks that c' == c as in the single-element proof above.

We can see why this works in a reduced case.

For (M_1, M_2), (Z_1, Z_2), and (c_1, c_2):

Z_1 = x(M_1)
Z_2 = x(M_2)
(c_1*Z_1) = c_1(x*M_1) = x(c_1*M_1)
(c_2*Z_2) = c_2(x*M_2) = x(c_2*M_2)
(c_1*Z_1) + (c_2*Z_2) = x[(c_1*M_1) + (c_2*M_2)]

So the composite points will have the same discrete log relation x as the underlying individual points.

Team

• Alex Davidson
• Ian Goldberg
• Nick Sullivan
• George Tankersley
• Filippo Valsorda

Acknowledgements

We'd like to thank Dan Boneh for suggesting OPRFs in the first place; Ian Goldberg for his extensive advice and the batch proof; and Brian Warner, Zaki Manian, Tony Arcieri, Isis Lovecruft, Henry de Valence, Trevor Perrin, Yan Zhu, Peter Wu, Zi Lin and several anonymous others for their valuable help, input, and review.

Documentation

Index

• Variables
• func DecodeByteArrays(encoded []byte) ([][]byte, error)
• func EncodeByteArrays(values [][]byte) ([]byte, error)
• func HandleIssue(conn *net.TCPConn, req BlindTokenRequest, key []byte, keyVersion string, ...) error
• func HandleRedeem(conn *net.TCPConn, req BlindTokenRequest, host, path string, keys [][]byte) error
• func MarshalRequest(request interface{}) ([]byte, error)
• func RedeemToken(req BlindTokenRequest, host, path []byte, keys [][]byte) error
• type BlindTokenRequest
• type BlindTokenRequestWrapper
• type DoubleSpendList
  • func NewDoubleSpendList() *DoubleSpendList
  • func (d *DoubleSpendList) AddToken(token []byte)
  • func (d *DoubleSpendList) CheckToken(token []byte) bool
  • func (d *DoubleSpendList) Reset()
• type IssuedTokenResponse
  • func ApproveTokens(req BlindTokenRequest, key []byte, keyVersion string, G, H *crypto.Point) (IssuedTokenResponse, error)
• type ReqType

Variables

var (
	ErrInvalidMAC                = errors.New("binding MAC didn't match derived MAC")
	ErrNoDoubleSpendList         = errors.New("bloom filter is not initialized")
	ErrDoubleSpend               = errors.New("token was already spent")
	ErrTooManyTokens             = errors.New("ISSUE request contained too many tokens")
	ErrTooFewRedemptionArguments = errors.New("REDEEM request did not contain enough arguments")
	ErrUnexpectedRequestType     = errors.New("unexpected request type")
	ErrInvalidBatchProof         = errors.New("New batch proof for signed tokens is invalid")
	ErrNotOnCurve                = errors.New("One or more points not found on curve")

	// XXX: this is a fairly expensive piece of init
	SpentTokens = NewDoubleSpendList()
)

Functions

func DecodeByteArrays

func DecodeByteArrays(encoded []byte) ([][]byte, error)

DecodeByteArrays decodes JSON of the fromat produced by EncodeByteArrays.

func EncodeByteArrays

func EncodeByteArrays(values [][]byte) ([]byte, error)

EncodeByteArrays turns [][]byte into JSON with base64-encoded byte blobs.

func HandleIssue

func HandleIssue(conn *net.TCPConn, req BlindTokenRequest, key []byte, keyVersion string, G, H *crypto.Point, maxTokens int) error

HandleIssue deals with token issuance requests. It receives a slice of byte slices representing blinded curve points in the Contents field of a BlindTokenRequest. Approval consists of multiplying each point by a "secret key" that is a valid scalar for the underlying curve. After approval, it encodes the new points and writes them back to the client along with a batch DLEQ proof. Return nil on success, caller closes the connection.

func HandleRedeem

func HandleRedeem(conn *net.TCPConn, req BlindTokenRequest, host, path string, keys [][]byte) error

HandleRedeem deals with redemption requests. The Contents field of a redemption request should be a tuple of (token-preimage, HMAC_{sharedKey}(request-data)), where request-data is a concatenation of the other fields supplied in the request (currently Host header and the requested HTTP path). On successful validation, we write the ASCII string "success" back to the supplied connection and add the token preimage to a double-spend ledger. Internal semantics are still return nil on success, caller closes the connection.

func MarshalRequest

func MarshalRequest(request interface{}) ([]byte, error)

func RedeemToken

func RedeemToken(req BlindTokenRequest, host, path []byte, keys [][]byte) error

RedeemToken checks a redemption request against the observed request data and MAC according a set of keys. keys keeps a set of private keys that are ever used to sign the token so we can rotate private key easily It also checks for double-spend. Returns nil on success and an error on failure.

Types

type BlindTokenRequest

type BlindTokenRequest struct {
	Type     ReqType  `json:"type"`
	Contents [][]byte `json:"contents"`
}

{ type : (Issue|Redeem), contents : list of b64-encoded blinded points }

type BlindTokenRequestWrapper

type BlindTokenRequestWrapper struct {
	Request []byte `json:"bl_sig_req"`
	Host    string `json:"host,omitempty"`
	Path    string `json:"http,omitempty"`
}

This is a transport format induced by internal systems. It should be irrelevant to third-party implementations. { bl_sig_req : b64-encoded request from client }

type DoubleSpendList

type DoubleSpendList struct {
	// contains filtered or unexported fields
}

func NewDoubleSpendList

func NewDoubleSpendList() *DoubleSpendList

Amongst a profusion of bloom filter variants, this one at least uses a strictly bounded amount of memory. Ideally you would use something better. Napkin estimates: 10M * 8-bit buckets ~ 80MB with 1/1000000 asymptotic false positive rate.

func (*DoubleSpendList) AddToken

func (d *DoubleSpendList) AddToken(token []byte)

func (*DoubleSpendList) CheckToken

func (d *DoubleSpendList) CheckToken(token []byte) bool

func (*DoubleSpendList) Reset

func (d *DoubleSpendList) Reset()

type IssuedTokenResponse

type IssuedTokenResponse struct {
	Sigs    [][]byte `json:"sigs"`
	Proof   []byte   `json:"proof"`
	Version string   `json:"version"`
}

Contains response to Issue request (incl. signed tokens, DLEQ proof and key version)

func ApproveTokens

func ApproveTokens(req BlindTokenRequest, key []byte, keyVersion string, G, H *crypto.Point) (IssuedTokenResponse, error)

ApproveTokens applies the issuer's secret key to each token in the request. It returns a struct of values containing:

• signed tokens
• a batched DLEQ proof
• a string determining the version of the key that is being used

type ReqType

type ReqType string

var (
	ISSUE  ReqType = "Issue"
	REDEEM ReqType = "Redeem"
)