A 3 minute read written by
Henrik Walker Moe, Tjerand Silde and Martin Strand
We discussed elliptic curves earlier this month. Today, we look at how to use those to make the internet a bit more user friendly.
Privacy Pass was introduced in 2018 by Alex Davidson, Ian Goldberg, Nick Sullivan, George Tankersley, and Filippo Valsorda in order to reduce the number of CAPTCHA challenges human users would meet online. The basic idea is to allow the user to submit a number of tokens to a server ahead of time. The server will sign these, equivalent to issuing notes with the text "The holder of this token should be considered human, not a bot.". Every time the user visits a website that would have asked for a CAPTCHA, the browser can hand over one of the tokens instead, hence not bothering the user with reading garbled letters or clicking on images of road signs.
To avoid token replication and reuse by bots, one can assign these tokens serial numbers; however, these serial numbers could violate privacy by tracking users across the internet. The authors of Privacy Pass have an elegant solution to this.
By using the Privacy Pass browser extension users can be both authenticated and remain anonymous. Usability is also improved when existing CAPTCHA solutions can be replaced, as the user is already authenticated and doesn't need another verification challenge.
How it works
The Privacy Pass protocol works the following way:
- First, the server side generates an elliptic curve
Ewith a distinguished point
G, secret key
kand a public key
K = kG.
- The browser chooses a random number
t, and generates a point
Ton the curve from
tusing a hash function. It then creates a masked point
P = rT, which it submits to the token issuer.
- The token issuer signs the token by computing a new point
Q = kP. It also provides a Chaum-Pedersen zero-knowledge proof to prove that it was indeed
kwhat was used to sign
P, but without revealing
- The original point
Tis now masked by both
k. The browser can remove
r, so that it is left with the token
W = kT.
- In order to redeem the token, the browser can submit
(t, W)to the website the user wants to visit. The website generates
kT, and verifies that it equals
W. The seed
tis stored in order to prevent the token being used twice.
Security of Privacy Pass
We give some intuition-based arguments for why this protocol achieves its goals:
- In order to manufacture tokens that could be used more than once, the browser would need to generate values
t'such that they both generated the point
T. Hence, the hash function needs to be collision resistant and second preimage resistant. The SHA2 family of hash functions is believed to satisfy these requirements.
ris chosen uniformly at random, the point
P = rTcarries no meaningful information. Likewise, if the discrete log problem is hard on the chosen elliptic curve, then it is infeasible to extract the secret key
kfrom the point
kT. The Chaum-Pedersen proof guarantees that
Qis well-formed. The browser is therefore none the wiser regarding generating tokens.
- Since the points
Qare masked with
Wis independent of these points, the issuing service and the verification service will not be able to trace when a specific token was used, and so the anonymity of the user is guaranteed
Content delivery networks such as Cloudflare or Akamai may record misbehaving IP-addresses to mitigate attacks. However, if you use anonymity tools such as onion routing, your visible IP address may be shared with less honest users, which will in turn make you have to go through the hassle of responding to frequent CAPTCHA requests. Privacy Pass enables you to avoid those without compromising your anonymity.
Tomorrow, we will look at a seemingly different way of using the exact same cryptography, which may also benefit you in 2021.