The Privacy pass protocol [here] was developed by Cloudflare and is a realization of 'Verifiable, Oblivious Pseudorandom Function' (VOPRF) [1]. This implements a blind-signing methods, and where a token value is blinded onto a curve. With the Privacy Pass protocol, a server (which is an issuer of token) can create a number of blinded tokens, and which can be redeemed at a later time. The client who receives the tokens cannot reuse any previously redeemed tokens. These tokens are generally unforgeable and where a client can prove that a token was issued by the issuer.
Privacy Pass - Implementation of Verifiable, Oblivious Pseudorandom Function' (VOPRF) |
Theory
The server will have published a public key of \(Y = xG\). First the user creates a random token value (\(t\)) and a blinding factor (\(r\)). The value of \(t\) is then hashed onto the curve:
\(T= H_1(t)\)
and then blinded onto the curve with:
\(M = rT\)
This value (\(M\)) is then passed to the server who generates a random value (\(x\)) and computes a new point:
\(Z = xM\)
The server then creates a proof of DLEQ(Z/M == Y/G) [DLEQ proof] and then this and \(Z\) back the user. The user checks the proof, and unblinds \(Z\) to find \(N\):
\(N = (1/r)Z\)
This should give a value of:
\(xT\)
Only the server and the user will know this value.
For redemption, the client takes a request to sign (\(R\)), and computes a hash of it:
\(R=sha256(request)\)
And then selects an unused \(t,N\) value, and calculates a shared key of:
\(sk = H_2(t, N)\)
The usser sends the to the server along with the HTTP request:
\((t, MAC_{sk}(R))\)
The server recalculates R from the request data and checks the double-spend list for t. It then computes:
\(T = H_1(t)\)
\(N = xT\)
\(sk = H_2(t, N)\)
and then checks \(MAC_R\). If it equals the user-supplied value, it will accept it.
Code
Here is the code:
import random import libnum from secp256k1 import is_on_curve, curve, scalar_mult import hashlib import hmac def to_curve(x): while (True): y2=(x * x * x + curve.a * x + curve.b) % curve.p if (libnum.has_sqrtmod(y2,{curve.p:1})): res=libnum.sqrtmod(y2,{curve.p:1}) y=next(res) point = (x,y) if (is_on_curve(point)==False): print("not on curve") return(point) x=x+1 # Can we prove x is used t = random.randint(0, curve.n-1) r = random.randint(0, curve.n-1) # Two base points used T= to_curve(t) M = scalar_mult(r,T) print (f"t={t}\nr={r}\nPoint on curve={M}") # Server now computes: x = random.randint(0, curve.n-1) Z = scalar_mult(x,M) # User unblinds Z to calculate N = (1/r)Z = xT and stores (t, N) inv_r = libnum.invmod(r,curve.n) N = scalar_mult(inv_r,Z) print (f"\nN={N}\n") xT = scalar_mult(x,T) print (f"Checking xT={xT}\n") ############################## # Redemption # ############################## # R for the request they want to make request=b"HTTP Request" R=hashlib.sha256(request) # Calculates a shared key sk = H_2(t, N) N_x,N_y = N sk=hashlib.sha256(t.to_bytes(32,'big')+N_x.to_bytes(32,'big')+N_y.to_bytes(32,'big')).digest() # User sends a pass (t, MAC_{sk}(R)) to the server along with the HTTP request MAC_R = hmac.new( bytearray(sk), request, hashlib.sha256 ) print("Signing: ",MAC_R.hexdigest() ) # Server recalculates R from observed request data and checks the double-spend list for t # Server calculates T = H_1(t), N = xT and sk = H_2(t, N) and then checks MAC_R # Server checks that MAC_{sk}(R) matches the user-supplied value
and here is the elliptic curve code for secp256k1 [code]:
# Code from: https://github.com/andreacorbellini/ecc/blob/master/scripts/ecdhe.py import collections EllipticCurve = collections.namedtuple('EllipticCurve', 'name p a b g n h') curve = EllipticCurve( 'secp256k1', # Field characteristic. p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f, # Curve coefficients. a=0, b=7, # Base point. g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8), # Subgroup order. n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141, # Subgroup cofactor. h=1, ) # Modular arithmetic ########################################################## def inverse_mod(k, p): """Returns the inverse of k modulo p. This function returns the only integer x such that (x * k) % p == 1. k must be non-zero and p must be a prime. """ if k == 0: raise ZeroDivisionError('division by zero') if k < 0: # k ** -1 = p - (-k) ** -1 (mod p) return p - inverse_mod(-k, p) # Extended Euclidean algorithm. s, old_s = 0, 1 t, old_t = 1, 0 r, old_r = p, k while r != 0: quotient = old_r // r old_r, r = r, old_r - quotient * r old_s, s = s, old_s - quotient * s old_t, t = t, old_t - quotient * t gcd, x, y = old_r, old_s, old_t assert gcd == 1 assert (k * x) % p == 1 return x % p # Functions that work on curve points ######################################### def is_on_curve(point): """Returns True if the given point lies on the elliptic curve.""" if point is None: # None represents the point at infinity. return True x, y = point return (y * y - x * x * x - curve.a * x - curve.b) % curve.p == 0 def point_add(point1, point2): """Returns the result of point1 + point2 according to the group law.""" assert is_on_curve(point1) assert is_on_curve(point2) if point1 is None: # 0 + point2 = point2 return point2 if point2 is None: # point1 + 0 = point1 return point1 x1, y1 = point1 x2, y2 = point2 if x1 == x2 and y1 != y2: # point1 + (-point1) = 0 return None if x1 == x2: # This is the case point1 == point2. m = (3 * x1 * x1 + curve.a) * inverse_mod(2 * y1, curve.p) else: # This is the case point1 != point2. m = (y1 - y2) * inverse_mod(x1 - x2, curve.p) x3 = m * m - x1 - x2 y3 = y1 + m * (x3 - x1) result = (x3 % curve.p, -y3 % curve.p) assert is_on_curve(result) return result def scalar_mult(k, point): """Returns k * point computed using the double and point_add algorithm.""" assert is_on_curve(point) if k % curve.n == 0 or point is None: return None if k < 0: # k * point = -k * (-point) return scalar_mult(-k, point_neg(point)) result = None addend = point while k: if k & 1: # Add. result = point_add(result, addend) # Double. addend = point_add(addend, addend) k >>= 1 assert is_on_curve(result) return result def point_neg(point): """Returns -point.""" assert is_on_curve(point) if point is None: # -0 = 0 return None x, y = point result = (x, -y % curve.p) assert is_on_curve(result) return result
A sample run is:
t=53075123635812138534494948189304492775731557192895406712704641738801067525444 Point on curve=(53075123635812138534494948189304492775731557192895406712704641738801067525447, 54624709809775549392627085158798703578016322744414876200988739329318029521343)
Reference
[1] Jarecki, S., Kiayias, A., & Krawczyk, H. (2014, December). Round-optimal password-protected secret sharing and T-PAKE in the password-only model. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 233-253). Springer, Berlin, Heidelberg [paper].