隆重介绍适用于跨/多厂商硬件私有 Web 认证的零知识证明

几周前,我们推出了用 USB 安全密钥替代 CAPTCHA 人格加密证明(Cryptographic Attestation of Personhood),今天我们宣布了对 设备内置生物识别硬件 的额外支持。在做这项工作时,我们突然想到,硬件证明,即用硬件证明用户的身份或其他属性,可以有更广泛的应用,而不仅仅是 CAPTCHA 替代方案和通过 WebAuthn 的用户身份验证。确实如此,如果某个人自己受信任的设备可以证明其存在,为何他/她需要拥有一个账户来作为证明呢?

WebAuthn 标准中的证明让网站知道你的安全密钥是真实的。它被设计成具有良好的隐私属性,并被写入设备制造商必须遵守的策略中。你的安全密钥发送到网站的信息与无数其他密钥的信息是无法区分的。即便如此,我们还是想做得更好。如果我们把证明从认证中分离出来,那么我们只需要了解你的安全密钥是真实的——我们已经为浏览器设计了一种新的零知识证明来做到这一点。

这是我们为改善整个互联网隐私所做工作的一部分。我们尚未将这种人格证明投入生产,但你可以看到该技术的实际演示。我们已经看到它与 YubiKeys 等一起使用。最重要的是,我们将开源代码,以便每个人都可以从中受益并做出贡献。阅读以下内容以了解详细信息以及后续步骤。

简介

WebAuthn 认证向要求认证的网站识别硬件安全密钥的制造商。它旨在部署于封闭环境中,例如金融机构和内部服务,这些网站与你预先建立了关系。由于登录可识别你的身份,对隐私的影响微乎其微。相比之下,任何使用认证的开放网站(如我们为人格认证所做的那样)都会了解你所用密钥的品牌和型号。

品牌和型号信息似乎没有那么敏感,正如汽车的品牌和型号那样。市场上有大量 2015 款普锐斯(Prius),因此知道你驾驶一辆这样的汽车无助于识别你的身份。但是,当与用户代理、语言偏好、一天中的时间等信息结合起来时,它有助于构建用户的形象——就像人口统计信息、身高、体重和服装与汽车的品牌和型号结合起来后,就能更容易在高速公路上找到特定的汽车。因此,在网站获得这一证明时,浏览器就会进行对话,以确保用户了解网站正在获取可能有助于识别他/她们的信息。Cloudflare 非常重视隐私,希望避免获取任何可以识别你的信息。

浏览器警告示例。‌‌
浏览器警告示例。‌‌

我们从证明中看到的信息证明你的安全密钥的制造商确实制造了该密钥。它是由安全密钥在安全区中保管的私钥所作的数字签名,帶有指向制造商的证书链。这些链使任何服务器都能看到硬件安全密钥是真实的。对于人格加密证明,我们想要的只是一点:你拥有一个值得信任的硬件安全密钥,并且不用提供有关制造商或型号的任何详细信息。

在过去,证明在只有少数几家制造商被认可的环境中使用。例如,大型金融机构相当保守。在这种环境中,披露制造商是必须的。在开放的供应商设计中,我们不想向任何特定制造商提供特权,而只是想知道密钥是值得信任的。

可信度由 FIDO 元数据服务确定。这是为制造商维护根证书的 FIDO2 联盟提供的一项服务。当这些密钥被泄露时,它们会在 FIDO 系统中列出。我们有自动脚本来下载这些根并将它们插入到我们的软件版本中。这可确保我们在新制造商出现或旧设备因攻击者提取密钥或密钥处理不当而遭到泄漏时始终保持最新状态。

值得称赞的是,FIDO 联盟要求不少于 10 万台设备共享一个证明密钥,对设备匿名集大小设置下限,以最大限度地减少信息收集的影响。可惜的是,实际情况并非总是如此。一些制造商永远达不到以上批量,用户不应该为保护他们的隐私而涌向最大的制造商。Cloudflare实施了强有力的隐私政策来管理我们使用这些信息的方式,但我们更希望完全不知道你的密钥的制造商。正如我们删除了不再需要的 cookie,并在我们自己无法看到的情况下记录客户调试自己防火墙规则的日志数据一样,我们一直在设法减少我们可以看到的信息。

同时,我们需要确保响应我们请求的设备是真正的安全密钥,而不是自动程序运行的某种软件仿真。尽管我们不关心它具体是哪个密钥,但我们想要知道这个密钥确实符合我们的安全要求,并且没有遭到泄漏。从本质上讲,我们希望在不了解任何其他信息的情况下证明凭据的合法性。这种匿名凭据问题并不新鲜,许多解决方案已被提出,一些甚至已得到部署。

然而,这些方案通常要求实施凭据证明的硬件或软件在设计时就要将某一种方案考虑在内。我们无法直接去说服制造商在几个月内添加功能,更不用说取代世界上所有的硬件身份验证安全密钥了。相反,我们必须寻找与现有硬件兼容的解决方案。

零知识证明概要介绍

乍看之下,我们似乎面对一个不可能的任务。我如何能证明我知道某件事而不用告诉你它是什么呢?但有时这是可能的。如果我声称有信箱的钥匙,你可以将信放到信箱内并离开,让我看信。如我声称知道你的电话号码,你可以要我打电话给你。这种证明叫做零知识证明,通常缩写为 ZKP。

零知识证明的一个经典示例是向某人展示你知道《寻找威利》(Where’s Wally)中的威利在哪里。若你能在图中指出威利,就能告诉别人威利的具体位置。但是,如果你用一大张纸盖住图片,仅留一个小洞露出威利,那么别人只能看到威利在图中某处,但不清楚具体在哪里。他们会知道你知道威利在哪里,但他们自己不知道威利在哪里。

有时找到威利不是问题(来源:https://commons.wikimedia.org/wiki/File:Where%E2%80%99s_Wally_World_Record_(5846729480).jpg)
有时找到威利不是问题(来源:https://commons.wikimedia.org/wiki/File:Where%E2%80%99s_Wally_World_Record_(5846729480).jpg)

密码学家设计了大量零知识证明以及将它们连接在一起的方法。将它们连接在一起的核心部分是承诺,一个加密信封。承诺防止篡改创建时放入其中的值,稍后可开启以显示放入其中的内容。我们在现实生活中使用承诺机制。魔术师可在信封中密封一张纸,向观众保证他不能触碰或篡改它,然后让人打开信封,揭示他的预测。在无声拍卖中,人们将竞价放入密封的信封中,然后一起打开,确保没有人能在看到其他人的竞价后调整其自己的竞价。

一种利用承诺的简单协议是抛硬币。假设爱丽丝和鲍勃要抛硬币,但其中一人有几个双面头像的 25 美分硬币,另一人每次抛硬币都能得到想要的那一面。使抛硬币对双方都公平的唯一办法是,让两人都以一种能确保任一方都诚实的方式来进行,从而获得公平的抛硬币结果。但如果他们直接抛硬币并交换结果,无论谁最后抛,都可以假装得到了符合预期的结果。

使用承诺机制解决了这个问题。爱丽丝和鲍勃没有说出他们的结果,而是交换对结果的承诺。然后他们打开承诺。因为他们交易了承诺,所以他们都不能假装得到了不同的结果,如果那样做,打开承诺时就会被发现。

承诺像电线一样将零知识证明联系在一起,从简单的证明生成更大、更复杂的证明。通过证明承诺中的值具备不同零知识证明的两个不同属性,我们就能证明两个属性对该值都成立。这让我们可以将诸如“一个承诺中的值是另外两个承诺中的值的和”与“一个承诺的值出现在列表中”的陈述的证明链接到更加复杂和有用的陈述中。因为我们知道如何证明诸如"当且仅当其他两个承诺都为 1 时这个承诺为 1"与"当这两个承诺中任何一个为 1 时这个承诺为 1"的陈述,我们就有了证明任何陈述的基础。这些通用技术可以为任何陈述生成零知识证明,尽管默认情况下它将非常缓慢和复杂。

我们的浏览器零知识证明系统

在人格加密认证中,服务器向浏览器发送硬件安全签名,证明其真实性。正如纸上签名可以确保签名者看到并签名一样,数字签名可以确保签名者的身份。在我们使用零知识证明时,客户端不会发送签名,而是发送一个证明,证明该签名是由服务器提供的列表中的密钥产生的。

由于我们仅向服务器发送证明,服务器只知道证明的存在,而不知道哪一个硬件安全密钥生成它。这保证了隐私,因为有关安全密钥的识别信息永不离开浏览器。但我们需要确保证明和验证的执行能大规模高效执行,以提供一个可部署的解决方案。

我们研究了很多潜在机制,包括 SNARKS 。不幸的是,SNARK 的代码大小、工具链要求和证明的复杂性令人望而却步。 SNARKS 的安全性所依赖的假设比我们最终采用的机制要复杂得多。显然,这是一个活跃的研究领域,今天最好的技术不一定是未来最好的技术。

对于我们支持的硬件安全密钥,证明中的数字签名是由椭圆曲线数字签名算法 (ECDSA) 生成的。 ECDSA 本身类似于我们使用的许多零知识证明。它从签名者计算椭圆曲线上随机值 x 的点 \(R=kG\) 开始。然后签名者获取点的 x 坐标(写为 r) 、他们的私钥和消息的哈希值,并计算值s 。值对 (r, s) 就是签名。验证者使用 r s 以及公钥重新计算 R,然后检查 x 坐标是否与 r 匹配。

不幸的是,通常提出的验证方程涉及一些需要将值从一种形式转换为另一种形式的操作。在零知识证明中,这些操作既复杂又昂贵,有很多步骤。我们必须避开这个限制才能使我们的系统正常工作。为了将 ECDSA 转换为我们可以使用的方案,我们的证明者改为发送 R,并提交一个由 r s 计算的值  z ,以简化验证方程。任何人都可以在不使用任何秘密知识的情况下获取 ECDSA 签名并将其转换为我们调整方案的签名,反之亦然,因此它与 ECDSA 一样安全。

由于我们要证明的陈述有两个部分——“消息由密钥签名”和“密钥在列表中”——很自然地,证明该陈述的问题也分成两个部分。首先,证明者证明承诺内部的密钥签署了消息,然后证明者证明提交的密钥在列表中。验证者同样检查这两部分,如果两部分都有效,则表明证明有效。

为了证明签名在某个密钥下验证,我们必须使用一个椭圆曲线点是另一个密钥已知幂的证明。这个证明是一个简单直接的零知识证明,但某些步骤本身需要零知识协议来证明正确添加点和正确完成运算。这一证明消耗证明生成和验证的大部分时间。一旦这个证明得到验证,验证者就知道该消息是由承诺的公钥签名的。

下一步,证明者查找其密钥在列表中的位置,然后证明其密钥处于列表中的这个位置上。为此,我们使用由 Groth 和 Kohlweiss 开发的零知识证明。他们的证明首先承诺其承诺在列表中位置的二进制扩张。接着,证明者证实存在这样的证明,并提供有关其证明方法的一些额外信息。有了这些额外信息和证明后,如果承诺的是列表中的值,则双方计算的多项式的结果都为零。对于这样复杂的任务而言,这段代码令人意外地简短

计算多项式显示我们的承诺值为零。
计算多项式显示我们的承诺值为零。

然后,验证者检查 Groth-Kohlweiss 证明,确认承诺的密钥在列表中,并且确保被签名的消息确是其本身。这是一个非常高效的证明,即使列表大小增加:每个列表元素完成的工作也只是乘法。如果一切都匹配,则我们知道签名是由足够安全的安全密钥生成的,仅此而已。如果不匹配,我们就知道存在错误。

设计更加有效的曲线

我们将关于 ECDSA 签名的陈述转化为关于 P-256 椭圆曲线上的点的陈述,然后转化为关于 P-256 定义域中的算术陈述。如果我们有一个大小与字段大小匹配的组,这些语句更容易证明,因此我们必须找到一个。这提出了一个有趣的挑战,因为它与我们通常在密码学中做事的方式相反。如果您想了解我们如何解决它,请继续阅读,否则请跳过

在椭圆曲线加密技术中,我们大多时候会从一个方便的基域开始,搜索具备我们应用的适当属性的素数阶或近素数阶的椭圆曲线。通过这种方式,我们可以选择具有便于计算机硬件的属性的素数。需要配对友好的曲线时,我们通常会在计算机上搜索其参数由已知多项式给出的曲线。

不过,我们这里想要的是具有给定点数的曲线,因此不得不使用一些相当高级的数论机制来确定这条曲线。如此做法对我们的零知识证明尽可能有效发挥巨大作用用。

椭圆曲线和复平面

椭圆曲线在复数域上分布特别良好。椭圆曲线与环面同构。所有复数曲线与使用复数表示的环面同构,但某些曲线带有不止一个洞。

不同的椭圆曲线通过围绕环面的两个方向相对于彼此的厚薄来区分。如果我们想象在圆环上的孔周围切片,我们会看到我们可以通过取一个矩形并将两侧粘合起来得到一个圆环。有一个说明性视频,展示粘贴圆环的样子。

我们可以想象将整个平面折叠起来,使每个矩形都排列起来。如此一来,这些矩形的角都在原点上对齐。这些角组成一个格,我们总是可以缩放和旋转格的生成器之一使其变成 1。

从这个角度来看,复数的加法变成了圆环上的加法,就像整数模 2 的加法是整数的加法,然后对模 2 化简。但是对于椭圆曲线,我们习惯用代数方程进行加法和减法,也适用于曲线本身。这个分析图如何与代数图相互作用?

通过大量经典的复杂几何计算,我们发现它们是密切相关的。格上的复值函数环由魏尔施特拉斯(Weierstrass) \(\mathcal{P}\) 函数及其导数生成。它们满足形式为 \(y^2=x^3+ax+b\) 的代数方程,并且参数 \(a\) 和 \(b\) 是格参数的函数。椭圆曲线上点的代数加法的经典公式由此而来。

参数之一是 j 不变量,它是比 \(\tau\) 更有算术意义的不变量。\(j\) 不变量是椭圆曲线的不变量:产生相同格的 \(\tau\) 值产生相同的 j 不变量,而它们可能具有不同的 \(a\) 和 \(b\)。\(j\) 有很多表达式,其中一个是

https://dlmf.nist.gov/23.15#E7

复数乘法和类数

假设我们取格 \(\{1, i\}\)。这个格乘以 \(i\) 会得到 \(\{i,-1\}\),它会生成相同的点集。这是例外情况,只有当我们所乘以的数字满足二次方程时才会发生。格的元素与该二次方程的解紧密相关。

与这样一个格相关的是一个判别式:与这个示例相关的二次域的判别式。对于我们关于 i 的示例,判别式是 \(-4\),二次方程的判别式是 \(x^2+1\)。例如,如果我们改为取 \(\sqrt{-5}\) 并考虑格 \(\{1, \sqrt{-5}\}\),则判别式将是 \(-20\),即 \(x^2-5\) 的判别式。注意,判别式有不同定义,改变符号并加上 2 的各种幂。

从椭圆曲线到自身的映射称为自同态。大多数椭圆曲线只是用整数乘法作为自同态。但部分曲线有额外的自同态。例如,如果我们将格 \(\{1, i\}\) 变成一个椭圆曲线,我们会得到 \(y^2=x^3+x\)。现在这条曲线有一个额外的自同态:如果我将 y 赋给 \(iy\),并将 \(x\) 赋给 \(-x\),我会得到一个满足曲线方程 \((-iy)^2=(-x)^3-x\) 的点。进行两次这样的映射会产生与反转一个点相当的效果,而且两次乘以 i 会将一个复数 z 发送到 -z,这并非巧合。因此,这个额外的自同态和乘以 i 满足同一个方程。具有额外的自同态称为复数乘法,因为它与一个复数相乘。当椭圆曲线所在的格具有复数乘法时,该椭圆曲线也具有复数乘法,反之亦然。

任何一组数学对象都带有问题,具有复数乘法的椭圆曲线也不例外。我们可以问,对给定判别式多少个椭圆曲线具有复数乘法。这个数字如何随着判别式的增大而增大?虽然进行了多年研究和计算机实验,其中一些疑问至今仍然悬而未决。解答它们的关键是格与算术之间的联系。

在 19 世纪初,高斯(Gauss)研究了二元二次型,即 \(ax^2+bxy+cy^2\) 形式的方程。如果存在 x 和 y 的整数系数替换项,并以其中之一取代对方,则该等二次型被认为是等价的。这是一个核心概念,除了化简二元二次型的算法外,高斯还证明了一个将给定判别式的二元二次型归为一组的合成定律。

后来的数论学家发展了这一概念,将二次型与唯一因式分解的失败联系起来。\(x^2+5y^2\) 和 \(2x^2+2xy+3y^2\) 都是判别式 \(-20\) 的二次型,这与 \(\mathbb{Z}[\sqrt{-5}]\) 中唯一因式分解失败相关。

当我们将二元二次型视为平面中向量的长度时,每个格给出一个二元二次型直至等价。因此,给定判别式的带复数乘法椭圆曲线对应给定判别式的二元二次型类,其与二次域中的算法相关联。因此,三个看起来截然不同的问题具有相同的答案。

为什么复数乘法对找到曲线很重要

如果我们取一个带有整系数的椭圆曲线并在素数域中考虑它,则会得到一个额外的自同态:弗罗贝尼乌斯(Frobenius)自同态,其中 \(x\rightarrow x^p\),\(y\rightarrow y^p\)。这一自同态满足一个二次方程,该二次方程的线性项是点数减去 \(p+1\)。

如果椭圆曲线具有复数乘法,则还有另一种自同态,即我们从复数乘法得到的自同态。但是椭圆曲线只能带有一个额外的自同态,除非它是超奇异椭圆曲线。超奇异曲线非常罕见。所以弗罗贝尼乌斯自同态和复数乘法的自同态一定是相同的。因为我们是从复数乘法开始的,我们知道弗罗贝尼乌斯必须满足的二次方程,因而知道点数。

我们的征程到此为止:要找到具有给定阶数的椭圆曲线,为小 \(D\) 找到方程 \(t^2+Dy^2=4N\) 的整数解,再令 \(p=N-t+1\) 以检查它是不是素数。然后,将 \(D\) 的 Hilbert 类多项式分解为 p 的乘积,取其中一个根模 \(p\) 作为椭圆曲线的 \(j\) 不变量。我们可能需要进行二次扭转才能获得正确的点数,因为 \(t\) 仅被确定了正负号。

这给了我们有效证明 P-256 基域上的关系所需的曲线。所有这些数学运算都会生成一个可以在几分钟内运行的脚本,并产生具备我们所需阶数的曲线。

我们的劳动结晶

完成所有这些工作之后,还需要进行大量额外的工程工作,以通过少许优化使证明更快运行。我们可以在几秒钟内生成证明,并在几百毫秒内对其进行验证。这一速度已足够满足实践需要,也就是说,想要验证安全密钥的安全性的网站可以如愿,不会对隐私有负面影响。

使用我们技术的网站只需要了解,签名是否由一个认证密钥在其所提供的列表上的令牌生成的。与直接使用 WebAuthn 不同,它们不会获得任何更详细的信息,即使制造商意外使批量变得过小也无妨。与其使用基于策略的方法来保护用户隐私,我们移除了麻烦的信息。

后续工作——社区努力!

我们的演示表明,我们能基于零知识证明来增强隐私保护。我们正在不断改进,添加更多的性能和安全特性。但是,只有拥有在每个浏览器中都可以使用的隐私保护 WebAuthn 扩展,让用户确信自己的数据不会离开浏览器,我们的任务才算完成。

我们已经做到的是演示可能做到什么:使用零知识证明来将 WebAuthn 认证变成一个在设计上平等对待每一个制造商、保护用户隐私并可被每一个网站使用的系统。大规模使用证明而产生的用户隐私挑战是可以解决的。

要形成高质量、可靠的系统,需要远远不止核心加密技术方面的见解。为了使用户体验不涉及有关我们零知识证明丢弃的信息,我们需要与浏览器进一步集成。我们还需要一种安全的方法,以便不在我们列表中的设备的用户将其密钥发给我们,并表明其值得信任;需要一种方法来确保该列表未被滥用以尝试确定密钥。

此外,这种验证方法比旧的验证方法更加重量级,因此实施该方法的服务器需要集成速率限制和其他保护措施以防滥用。SNARKS 在这方面具备巨大优势,但代价是演示的代码体积太大。最终将这些改进纳入 web 生态系统的核心部分,需要与用户、浏览器和其他参与者合作,找到对他们有效的解决方案。如果你希望为这个过程作出贡献,欢迎通过电子邮件 [email protected] 与我们联系。

我们的加密人格证明向用户提供了一种更简单的方式来证明他们是人类,并且比很多 CAPTCHA 替代方案或提供商更能保护隐私。然而,我们对现状并不满意,已找到一种方法来运用高级加密技术改善用户隐私。我们的工作表明零知识证明可以增强现实世界协议提供的隐私。