We discussed elliptic curves earlier this month. Today, we look at how to use those to make the internet a bit more user friendly.
4 min read
By Henrik Walker Moe, Tjerand Silde, Martin Strand
December 21, 2020
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.
The Privacy Pass protocol works the following way:
Ewith a distinguished point
G, secret key
kand a public key
K = kG.
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.
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
Tis now masked by both
k. The browser can remove
r, so that it is left with the token
W = kT.
(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.
Image courtesy of Cloudflare, Inc. (1.)
We give some intuition-based arguments for why this protocol achieves its goals:
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.
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.
(1.) "The orange cloud logo is a registered trademark of Cloudflare, Inc. This blog post is not sponsored by or affiliated with Cloudflare, Inc."