Privacy Pass: Bypassing Internet Challenges Anonymously

一些私货

为啥读论文儿

真正的一手资料，比书籍更强的时效性和专业性
启发思维和反常理的结论
读书与工作环境的影响

读论文儿的一些方法

搜论文：google scholar: https://scholar.google.com/
读新不读旧？查论文反引：

image

经典永流传，引用数：https://harzing.com/resources/publish-or-perish/os-x

image

站在巨人的肩膀上，跟踪大佬的研究路径 dblp：https://dblp.org/

image

论文质量？看发表期刊/会议的水平：CCF官网：A B C 分级 https://www.ccf.org.cn/Academic_Evaluation/By_category/

image

英语看不懂？chrome插件划词翻译

image

数学符号？。。。无能为力，只能慢慢积累
关键部分：Introduction！

正题：Privacy Pass

原文：https://www.petsymposium.org/2018/files/papers/issue3/popets-2018-0026.pdf

为啥看他

Google Chrome上的新功能，Trust Token：https://web.dev/trust-tokens/#sample-api-usage，Privacy Pass是其Token生成与消费的基础密码协议

image

Privacy Pass拓展在10月发布了v3版本：https://github.com/privacypass/challenge-bypass-extension
CloudFlare 作为世界最大的CDN厂商最早开发了Privacy Pass体系，已经使用了三年
优点：
- 最主要作用：大规模减少网络上的Challenge（人机挑战）的流量
保护用户隐私的token，即服务端验证token时并无法定位具体用户
用户可验证下发token不是被中间人或恶意服务伪造
token即使泄露也将快速消费完，无记忆性
缺点：

LET'S DISCUSS

背景知识

一个群儿

群是一个集合，有四个主要性质(封闭性，结合律，单位元，逆元)；但我们只讨论他的一个性质：阶

定义一个群的阶N为：任意群里的一个元素他对自己做N次定义群的运算后会等于他自己，则该群的阶为N

我们不搞抽象的，我们想一个具体的模乘群： $\mathbb{Z}_p = \{1, 2, ..., p-1\}$ , p为质数，其阶就为p

为啥？费马小定理，具体就不证明了：

image

VOPRF

可验证遗忘性伪随机数发生器(Verifiable oblivious pseudorandom function)：用人话说就是就是一个算法协议，他通过一个秘钥K和种子S来产生伪随机数R，而S是由一个消息M产生；该算法虽然产生了R，但他并不知道M是什么（遗忘性），但产生的R是可以验证一定来自该秘钥K产生的（可验证）

零知识证明ZKP

是实现VOPRF可验证性的重点：如何不告诉你秘钥K的值确定产生的伪随机数是来自秘钥K？

阿里巴巴的故事

image

阿里巴巴证明自己拥有能打开CD之间的石门的咒语

盗贼站在A，阿里巴巴在B点随机选择前往C或者D
盗贼到B点，随机让阿里巴巴从C或者D走出来，假如他不知道咒语，他也有50%的成功率
重复该实验N次，他连续成功的概率将越来越低，直到到达一个可信的范围

离散对数问题

DH密码协议所依赖的数学难题：

计算 $x, y, a \in \mathbb{Z}_p,\ y = a^x\ mod\ p$ 是简单的，但计算 $x = log_ay$ 是困难的

消息验证码MAC

用人话说就是A与B共享一个秘钥K，A给B发送一个消息m，同时用这个秘钥K和m进行计算生成一个消息验证码c，将m和c打包发给B。由于B也拥有秘钥K，他可以用相同的算法对收到的消息m’计算消息验证码c’，比较c与c’来判断m’有没有遭到篡改。

比较典型的算法是HMAC与GMAC，由于MAC的前提需要有共享秘钥，GMAC通常与AES结合使用，即AES-GCM模式。

协议分析

image

恐怖吗？我尽量用自己的理解用人话来描述这个协议吧🙄，就不细说具体的严格证明(我也没太看明白，民科罢了)

如何证明我拥有一个离散对数的解

DLEQ(Discrete log equivalence proofs)：有一组公开的数： $(X,\ Y) \in \mathbb{Z}_p, Y = X^k$ ，阿里巴巴如何证明自己拥有私钥k值？

盗贼给阿里巴巴一个数 $P \in \mathbb{Z}_p$
阿里巴巴计算 $Q = P ^ k$
阿里巴巴随机生成一个数 $t \in \mathbb{Z}_p$
阿里巴巴计算 $A = X ^ t, B = P ^ t, c = Hash(X, Y, P, Q, A, B)$
阿里巴巴计算 $s = t - ck$ , 最后把 $D_k = (Q, s, c)$ 给盗贼
盗贼计算 $A' = Y^cX^s, B' = P^cQ^s, c' = Hash(X, Y, P, Q, A', B')$
盗贼判断 $c\ ?= c$ ，若成立，则本次验证通过；且盗贼无法通过 $s,c => k$ （两个未知数，解不出）；也无法通过 $Q => k$ （离散对数难题）

证明很简单：

$A' = Y^cX^s = X^{ck}X^{-ck}X^{t} = X^t = A$

$B' = Q^cP^s = P^{ck}P^{-ck}P^t = P^t = B$

仅当 $s = t - ck$

以上证明形式可以被表述为 $D_k \leftarrow \mathsf{DLEQ}_k(X, Y, P, Q)$

推广到发送多个数的乘积，Batch-DLEQ：

该结论可以同时推广到一次通过n个数字 $P_i$ 乘积，一次完成 $D_k$ 的生成:

验证者随机生成的n个随机数 $c_1, c_2, ..., c_n$ 并保存下来，同时发送 $P_1^{c_1} ,P_2^{c_2}, ..., P_n^{c_n}$
证明者计算 $\{Q_i\}_{i \in [n]} = \{(P_i^{c_i})^k\}; \\ M = P_1^{c_1} \cdot P_2^{c_2}...\cdot P_n^{c_n}; \\ Z = M^k = (P_1^{c_1})^k \cdot (P_2^{c_2})^k...\cdot (P_n^{c_n})^k$
把替换成上面的 $P,Q$ , 完成证明值 $\bar{D}_k \leftarrow \mathsf{DLEQ}_k(X, Y, M, Z)$ ;
证明者一次把 $Q_1, Q_2, ... , Q_n, \bar{D}_k$ 发给验证者，验证者使用DLEQ验证方法完成验证

特点：

效率高，一次完成多次签名，同时可证明
Batch-DLEQ的遗忘性：上面 $c_1, c_2, ..., c_n$ 可以让证明者并无法获取具体的 $Pi$ 值；此时 $c_1, c_2, ..., c_n$ 被称为盲化因子
Batch-DLEQ的可验证性：由DLEQ保证

结论：Batch-DLEQ实现了一个VOPRF

此时由n个随机数组成的DLEQ被称为n-DLEQ，用符号通常表示为(用Pi，Qi来替代了上面的M，Z) $\bar{D}_k \leftarrow n\text{-}\mathsf{DLEQ}_k(X, Y, \{P_i\}_{i \in [n]}, \{Q_i\}_{i \in [n]})$

Privacy Pass正式协议

整个协议其实分为两个阶段，简单来说就是，Token组签署下发阶段和Token组赎回阶段

Token组签署下发阶段

服务器发起挑战
客户端响应挑战，并根据Batch-DLEQ的第一步，随机生成n个随机数 $P_1, ... ,P_n,$ 和n个盲化因子 $c_1, c_2, ..., c_n$ , 保存下来，同时完成上面M的计算，将M随挑战响应回复给服务器
服务器验证挑战，若验证失败则协议结束
服务器验证挑战成功，计算Z，完成 $\bar{D}_k \leftarrow n\text{-}\mathsf{DLEQ}_k(X, Y, \{P_i\}_{i \in [n]}, \{Q_i\}_{i \in [n]})$ 并下发结果
客户端验证下发结果，验证该Token的合法性
去盲化： $\{P_i^k\}_{i \in [n]} = \{Q_i^{1/c_i}\}_{i \in [n]}$ , 将 $(P_i, P_i^k)$ 成对保存下来，形成n个Token

这一阶段主要保证了

Token的可验证性：Token一定来自可信服务端，无法被中间人伪造
Token的隐私性：因为盲化因子的存在，消费Token时并不知道原本的随机数 $P_i$ ，即使服务器记录了这些M也无法追踪客户端

这正是VOPRF的特性

Token组赎回

即客户端消费Token：

服务器下发挑战，预期的计算结果为 $R'$
客户端取出一个Token，使用一个协议好的哈希函数计算出MAC所使用的key $K = H(P_i, P_i^k)$
计算挑战结果 $R$ , 并计算MAC： $C = MAC_{K}(R)$ ，将两者和 $P_i$ 一起响应给服务端
服务端先验证 $R ?= R'$ ，若不通过则挑战失败
服务器取出计算私钥 $k$ , 计算MAC所需秘钥 $K' = H(P_i, P_i^k)$
服务器计算对应MAC值， $C' = MAC_{K'}(R')$
挑战响应成功当且仅当 $C == C'$

主要优点

一次有感挑战后，可以完成多次无感挑战，提升体验，减少消耗
验证结果可验证，是来自拥有Token的用户

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,293评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,604评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,958评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,729评论 1赞 277
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,719评论 5赞 366
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,630评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,000评论 3赞 397
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,665评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,909评论 1赞 299
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,646评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,726评论 1赞 330
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,400评论 4赞 321
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,986评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,959评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,197评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 44,996评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,481评论 2赞 342

Privacy Pass: Bypassing Internet Challenges Anonymously

一些私货

为啥读论文儿

读论文儿的一些方法

正题：Privacy Pass

为啥看他

背景知识

一个群儿

VOPRF

零知识证明ZKP

阿里巴巴的故事

离散对数问题

消息验证码MAC

协议分析

如何证明我拥有一个离散对数的解

推广到发送多个数的乘积，Batch-DLEQ：

Privacy Pass正式协议

Token组签署下发阶段

Token组赎回

推荐阅读更多精彩内容