Crate challenge_bypass_ristretto
source ·Expand description
§challenge-bypass-ristretto
A rust implemention of the privacy pass cryptographic protocol using the Ristretto group.
This library utilizes the wonderful curve25519-dalek which is a pure-Rust implementation of group operations on Ristretto.
It is only an implementation of the cryptographic protocol, it does not provide a service or FFI for use by other languages.
This crate is still a work in progress and is not yet recommended for external use.
§FFI
This library exposes some functions intended to assist FFI creation but does not implement a FFI itself.
For FFI see challenge-bypass-ristretto-ffi.
§Blinded Tokens
As originally implemented in the challenge bypass server and extension repositories, blinded tokens enable internet users to anonymously bypass internet challenges (CAPTCHAs).
In this use case, upon completing a CAPTCHA a user is issued tokens which can be redeemed in place of completing further CAPTCHAs. The issuer can verify that the tokens are valid but cannot determine which user they were issued to.
This method of token creation is generally useful as it allows for authorization in a way that is unlinkable. This library is intended for use in applications where these combined properties may be useful.
A short description of the protocol follows, a more detailed writeup is also available.
The blinded token protocol has two parties and two stages. A client and issuer first perform the signing stage, after which the client is able to derive tokens which can later be used in the redemption phase.
§Signing
The client prepares random tokens, blinds those tokens such that the issuer cannot determine the original token value, and sends them to the issuer. The issuer signs the tokens using a secret key and returns them to the client. The client then reverses the original blind to yield a signed token.
§Redemption
The client proves the validity of their signed token to the server. The server marks the token as spent so it cannot be used again.
§Use
WARNING this library has not been audited, use at your own risk!
§Example Usage
See tests/e2e.rs
.
§Benchmarks
Run cargo bench
§Security Contract
This software attempts to ensure the following:
- The signing server / issuer cannot link the blinded token it sees during signing with the token preimage or other info that is used at the time of redemption.
- The client cannot create a valid signed token without performing the VOPRF protocol with the server. Each protocol run produces a single valid token which cannot be used to create additional valid tokens.
Given that:
- The client keeps the blind secret, at time of issuance only sends the blinded token and at time of redemption only sends the payload, verification signature and token preimage. The client verifies the DLEQ proof that tokens were signed by a public key which was committed to previously and not a key unique to the user. The client ensures that other out of band markers like IP addresses cannot be used to uniquely link issuance and verification.
- The server keeps the signing key secret. The server marks a token preimage as spent after the first successful redemption.
§Features
By default this crate uses std
and the u64_backend
of curve25519-dalek. However it is no-std
compatible and the other curve25519-dalek
backends can be selected.
The optional features include base64
and serde
.
base64
exposes methods for base64 encoding / decoding of the various structures.serde
implements the serdeSerialize
/Deserialize
traits.
§Development
Install rust.
§Building
Run cargo build
§Testing
Run cargo test
§Cryptographic Protocol
§Notation
We have tried to align notation with that used in the paper Privacy Pass: Bypassing Internet Challenges Anonymously sections 3 and 4.
§Description
Let \(\mathbb{G}\) be a group (written multiplicatively) of prime order \(q\) with generator \(X\). In this implementation we are using Ristretto.
Let \(\lambda\) be a security parameter.
The protocol requires three hashing functions, they are assumed to be random oracles:
\(H_1() \rightarrow \mathbb{G}\) which hashes to the group, it must ensure the discrete log with respect to other points is unknown.
In this implementation we are using RistrettoPoint::from_uniform_bytes
which uses Elligator2.
\(H_2() \rightarrow \{0,1\}^{\lambda}\) which hashes to bitstrings.
\(H_3() \rightarrow \{0,1\}^{\lambda}\) which hashes to bitstrings.
§Setup
The server generates a signing keypair, consisting of a secret key, \(k\), which is a random Scalar
and a commitment to that secret key in the form of a PublicKey
.
\(Y = X^k\)
§DLEQ Proof
A DLEQProof
seeks to show that for some \(Y = X^{k_1}\) and some
\(Q = P^{k_2}\) that \(k_1 = k_2\).
To do so the prover first generates a random Scalar
\(t\) and commits
to it with respect to \(X\) and \(P\).
\(A = X^t\)
\(B = P^t\)
The prover then computes \(c = H_3(X, Y, P, Q, A, B)\) and \(s = (t - ck) \mod q\).
The DLEQProof
\((c, s)\) is then sent to the verifier.
The verifier computes \(A’\), \(B’\), and \(c’\) then verifies \(c’\) equals \(c\).
\(A’ = X^s \cdot Y^c = X^{t-ck} \cdot X^{ck} = X^t\)
\(B’ = P^s \cdot Q^c = P^{t-ck} \cdot P^{ck} = P^t\)
\(c’ = H_3(X, Y, P, Q, A’, B’)\)
\(c’ \stackrel{?}{=} c\)
§Batch Proof
It is possible to construct a BatchDLEQProof
over m
instantiations
of the original DLEQ proof if \(X\) and \(Y\) remain constant.
First the prover calculates \(w\) which is used to seed a PRNG.
\(w \leftarrow H(X, Y, \{ P_i \} _{i \in m} ,\{ Q_i \} _{i \in m })\)
Next, m
Scalar
s are sampled from the seeded PRNG.
\(c_1, \ldots , c_m \leftarrow PRNG(w)\)
The prover generates the composite elements.
\(M = P_1^{c_1} \cdot \ldots \cdot P_m^{c_m}\)
\(Z = Q_1^{c_1} \cdot \ldots \cdot Q_m^{c_m}\)
A normal DLEQProof
is then constructed and sent to the user.
\((c, s) \leftarrow DLEQ_k(X, Y, M, Z)\)
The verifier recalculates \(w\), samples m
Scalar
s and re-computes \(M\) and
\(Z\).
Finally the verifier checks the DLEQProof
as described above.
§Signing
The user generates N pairs (referred to as Token
s) which each consist
of a random value and a random blinding factor.
The random value \(t\) we’ll refer to as a TokenPreimage
.
The random blinding factor \(r\) is a Scalar
.
Given the hash function \(H_1\) we can derive a point T
.
\(T = H_1(t)\)
The user blinds each Token
forming a BlindedToken
, point \(P\), by performing a scalar multiplication.
\(P = T^r\)
The user sends the N BlindedToken
s to the server.
The server signs each BlindedToken
using it’s SigningKey
, resulting in a SignedToken
, point \(Q\).
\(Q = P^k = T^{rk}\)
The server also creates a BatchDLEQProof
showing all BlindedToken
s were signed
by the same SigningKey
as described above.
The user receives N SignedToken
s from the server as well as the
BatchDLEQProof
.
The user verifies the proof and uses the original blinding
factor \(r\) from the corresponding Token
to unblind each
SignedToken
.
This results in N UnblindedToken
s, each consisting of the unblinded signed point \(W\)
and the TokenPreimage
, \(t\).
\(W = Q^{1/r} = T^k\)
§Redemption
At redemption time, the user takes one UnblindedToken
and derives the
shared VerificationKey
, \(K\).
\(K = H_2(t, W)\)
The user uses the shared VerificationKey
to “sign” a message, \(R\)
and sends the TokenPreimage
and resulting MAC VerificationSignature
to
the server.
\(MAC_K(R)\)
The server re-derives the UnblindedToken
from the TokenPreimage
and it’s SigningKey
. Then it derives the shared VerificationKey
and checks the included VerificationSignature
.
\(T’ = H_1(t)\)
\(W’ = (T’)^k\)
\(K’ = H_2(t, W’)\)
\(MAC_K(R) \stackrel{?}{=} MAC_{K’}(R)\)
If the verification succeeds then the server checks \(t\), the TokenPreimage
,
to see if it has been previously spent. If not, the redemption succeeds
and it is marked as spent.