作者：Andrew Poelstra

来源：https://diyhpl.us/wiki/transcripts/silicon-salon/anti-exfiltration

本文为作者在 2023 年 Silicon Salon IV 活动上的演讲的转录稿，由 diyhpluswiki 转录为文字。

ChristopherA：Andrew Poelstra 是 Blockstream 的研究总监，这是一个由密码学家、比特币开发者和网络工程师组成的团队，一直在研究比特币协议。他发明了多种比特币可扩展性和隐私性技术，包括 taproot、MuSig、隐形脚本（scriptless scripts）、适配器签名（adaptor signatures） ，以及侧链。我很荣幸，在 Blockstream 工作期间，能与他共事多年。

Andrew：在 Blockstream 的研究部门，我们的密码学研究专注于签名以及签名的变种。我们也开发智能合约的编程语言设计。今天我准备讲讲一个我们开发了多年的签名项目，叫做 “anti-exfiltration（反泄露）”。

用一些公式来开启今天的第一场演讲，不过分吧？这是我要用的唯一一条公式：s = kG + e * xG 。

这是 Schnorr 签名的公式。我想跟各位讲的并不是这个公式的具体内容，或者这些加法和乘法都是怎么回事，而是，你可以将基于椭圆曲线的签名，不论是 ECDSA 签名还是 Schnorr 签名，当成是两个秘密数据片段的线性等式。

（译者注：严格来说，椭圆曲线数字签名常常包含两部分，s 和 R，前者是用私钥生成的并用到了一次性随机数，后者是一次性随机数的公钥，比如 Schnorr 签名是 (R, s) = (R = k.G, s = k + e * x)，式子跟这里写得略有区别。）

很容易看出，其中一段秘密数据是你真正的私钥，跟你的公钥对应的那个；这个密钥对是长期使用的。为了生成签名，你要先生成一个临时的数值，我们称为 “nonce”（直译为 “只用一次的随机数”）。你可以把它看成是一个临时的私钥。这里的前提是，每一个签名都可以表示为一个等式，那么，各位应该还记得 9 年级的线性代数：如果我们有一个方程组，那么，当等式的数量跟未知数的数量恰好一样多的时候，你就能解出这些未知数；但如果等式的数量比未知数要多，那么可能会解不出来，因为未知或是矛盾；如果等式的数量比未知数要少，那么也解不出来，因为可能的解有无数个。只要我们发布的每个签名（等式）都带有（私钥之外的）另一个未知数，也就是未知数的数量总是比等式的数量多一个，那么就没有人可以抽取出你的私钥，因为有 2²⁵⁶ 种可能的解，没人能从这么多种解中找出你的那个私钥。

那么，一个显而易见的推理是，如果在生成某个签名时你没有使用新的 nonce，而是复用了以往的签名中的 nonce ，那么，其他人就能逆转这个矩阵、解出未知数，直接算出你的私钥。大多数人都熟知这个推理，就是在生成 EC 签名时不应该重复使用 nonce 。此外，当两个 nonce 之间存在已知的偏移量时，用过其中一个就不该再用另一个。

甚至，即使你没有重复使用 nonce，只是稍微偏离了完全随机，那么，如果你可以使用这些格（lattice）技术 —— 可以追溯到 2000 年代，Breitner 在 2019 年实现了它们，并且成功从区块链上记录的签名中抽取出许多私钥，原因就在于它们没有使用充分随机的 nonce 。如果你使用 HMAC（基于哈希函数的消息认证码）或是其他更聪明的技巧，你甚至可以让 nonce 产生定向的偏差，让只有一个知道这个 HMAC 的键（key）的攻击者才能观察到这个偏差，然后抽取出私钥，而其他人则看不出什么有什么特别的。

所以，要充分随机地生成 nonce，这是绝对必要的。如果由硬件签名器来生成随机性，那么用户实际上没有任何办法来验证它们。从用户的视角看，硬件签名器就是一个产生签名的黑盒子。你认为自己的硬件签名器是有偏倚的，你可以尝试分析自己的签名，但实际上也没有太多办法。

（译者注：这里的 “偏倚” 以及上文下文中的 “偏差”，通常是对同一个英文词 “bias” 的翻译，其含义是统计学意义上对某种状态的偏离。比如，理想中的随机数是从数是均匀分布的空间中采集出来的，但在一些空间中，数并非均匀分布的，那么从中采集出来的随机数就是有偏的。）

这个问题有不多的集中解决方案。

针对 nonce 挑选问题，标准的解决方案是 “确定性的 nonce 生成”，比如 “RFC 6979” 。已知你能运行哈希函数、持有一个私钥，那么就可以用来生成 nonce 。如果你使用的是 sha2 这样的哈希函数，从经验上看，它的输出是均匀分布的，那么好，这样就永远不会重复使用 nonce 了，因为你总是把待签名的消息也作为哈希函数的输入，这样，一旦要签名的消息改变，nonce 也就改变了。此外，你也不会有任何偏倚，除非它被攻破了。因此，使用确定性 nonce 是可行的。

难搞的是，对用户来说，硬件签名器就是一个黑盒子，也许它用了 RFC 6979，也许它没有，作为用户你并没有办法判定出来。也许你可以重新生成签名，看看它是不是恰好跟你期待的确定性算法匹配。但也有可能，签名被注入了一次性的随机数，这也很好，但你同样无法验证。

在密码学世界里，每当你遇上一个问题，是其他人因为无法获得你不希望他们获得的秘密数据而无法验证，那么有一个标准的解决方案，就是 “零知识证明（ZKP）”。ZKP 是一种密码学构造，你可以证明一些语句是真正，比如 “这个签名是用一种确定性 nonce 算法生成的”。你不会揭晓自己的私钥，也不会揭晓 nonce，两者都会保持机密。

在 5、6 年以前，生成 ZKP 是非常昂贵的，它们采用了复杂的密码学，实现也很复杂。现在，感谢密码货币世界的许多团队的大量研究，在商用的计算硬件上生成 ZKP 也是可行的了。在 10 年前，没人敢这么期待。

但是，如果你是在一块安全芯片或者硬件签名器上，生成这样的证据依然不现实。另一个问题是，这些证据的工作原理是， 你需要保护一些永久的秘密数据，所以你使用临时的随机数据来保护它。所以， ZKP 自身也有 nonce 。如果你要用一个 ZKP 来证明另一个 ZKP 是合法生成的，那么就会有这个无限追溯问题 —— 一直追溯最终那个的 nonce 。

这些 ZKP 不会出现在区块链上，这是好事。但我们希望有一个更好、更高效的解决方案，自身不需要 nonce 的那种。

一种解决方案是 —— 在本演讲剩下的环节中，我们都假设，主机计算机和硬件签名器不会同时被攻破，也不会勾结来偏转 nonce，不论你做什么 —— 这是一个简单的想法：如果主机也有自己的密钥，硬件签名器也有自己的密钥，那会怎么样？它们可以产生一个多重签名。

在 EC 多重签名方案中，两个参与者在公钥建立阶段结合他们的私钥，然后在签名的时候结合它们的 nonce。他们都贡献一些随机性。如果一方尝试偏移，另一方可以把这个偏移取消掉，没人能看得出来。它需要主机也有一个私钥。

标准的比特币钱包工作流程要求硬件签名器持有一个种子，然后从这个种子确定性地派生出密钥。这个想法是，你可以生成无限数量的密钥，而另一个硬件签名器也能够复现出来。也就是你能在另一个硬件签名器上做到同样的事。

即便不提 nonce 偏倚，使用两个硬件签名器也有一些好处 —— 其中一个被攻破，甚至就是有 nonce 偏倚，也不怕。你可以购买来自两个不同品牌的不同签名器。

但现在，密钥管理问题的复杂度倍增了。你需要备份更多密钥。想要使用两个硬件签名器，你首先必须购买更多硬件。而且，这些协议也不那么成熟。其中还有一些实现的复杂性。

如果你只使用一个硬件签名器，你希望使用主机作为另一个参与者，那么 —— 这些主机计算机通常不是为安全地保管密码学材料而设计的呀。

这种方案的一个变体是，（主机）不使用强大的 EC 私钥，而是使用一个密语（passphrase），但这样会增加用户复杂性。可能会遇到勒索软件，不交赎金你就会失去自己的密钥。

那我有什么好主意？我的想法使用了跟多重签名一样的前提，就是有两个参与者，他们将各自的随机性混合在一起，从而避免偏倚。关键在于，在这种通过 nonce 侧信道来泄露私钥的场景中，我们不需要关注私钥本身的偏倚。后者是密钥生成过程我们要注意的问题，我们希望自己的私钥不会泄露，也不是来自一些只有 32 比特熵的 Debian 随机数生成器（或者类似的蠢东西）。经验熵来说，似乎我们也不在乎在私钥中出现的少量偏倚。只有在 nonce 中，才有可能微小的偏倚都会变成世界末日。

好了，我们要实现的是多签名的一种弱形式 —— 参与者们不结合密钥，而只在签名时结合 nonce 。酷的地方在于，因为 nonce 是一次性的，使用之后就可以丢弃。所以，我们可以让主机计算机来生成随机数，甚至不需要是很强的随机数 —— 主机计算机可以生成它，然后传给硬件签名器，硬件签名器要以主机可以验证的方式混合这个随机数，然后生成签名；然后主机就可以丢弃掉这些随机数。

我们管这套解决方案叫 “anti-exfil”（或 “anti-exfiltration”）。“Kleptography” 是关于通过秘密侧信道来盗窃信息的密码学分支。我建议你看看这个维基百科页面，这是罕见的 90 年代密码朋克研究课题。我们将名字改成 “exfiltration”，是因为这是现在更广为人知的术语。

这里的前提是，主机会提供一个随机挑战给硬件签名器，后者将微调自己采集到的 nonce 以承诺这个挑战，并且主机可以验证这个微调；这样一来，它就重新随机化了 nonce 并消除了偏离。我们将固定一种哈希函数，这样，即使主机的随机数的质量不是那么高，我们也可以作一次完全的重随机化。只要攻击者没有同时攻破产生原始未调整 nonce 的硬件签名器以及主机，那么就不能从 nonce 中抽取任何信息。

我们直接跳到末尾，有一些关于技术问题的彩蛋幻灯片。

https://blog.blockstream.com/anti-exfil-stopping-key-exfiltration/

https://github.com/opentimestamps/python-opentimestamps/pull/14

这是在我们（Blockstream）制造的 Jade 硬件签名器上实现的 anti-exfil 协议。

在我为这个演讲作准备的时候，我发现了一个 2017 年的旧实现，当时我尝试把这个协议（使用承诺方案）塞进 OpenTimestamps 协议中。 Opentimestamps 协议的用处是，你希望证明一些数据在某个日期之前已经存在，所以你把它承诺到一棵巨大的默克尔树中，然后你把对这个默克尔根的承诺发布到比特币区块链。因为比特币区块的时间戳要伪造是很昂贵的，所以，你就让自己的数据的承诺出现在了比特币区块链上，从而证明这个数据在这个区块挖出之前就已经存在，也就是给出了单向的时间戳证据。在 2017 年，我曾经想过使用这种 nonce 调整技巧，只不过不是用随机数据来调整，而是用我想要盖上时间戳的数据来调整。这样，你就得到了这种 anti-exfil 技术。如果你遍历这里所有的承诺结构，你会从区块链找到签名、然后找到默克尔树，这样就得到了一种免费的时间戳服务，你无法区分这个时间戳承诺跟普通的 nonce 公开值有什么区别。而这样一来，对区块链空间的占用就从 32 字节降到了 0 字节。好吧，只是对 anti-exfil 的简单历史回顾。

Jade 没有安全芯片。它的工作模式有两种。一种是，不在设备中保存私钥，每次打开设备时都要自己输入一次种子词。 另一种模式是，我们使用另一种密码学技术，使用用户的 PIN 码来加密私钥然后存储下来；用户需要与 PIN 码服务器交互，从而 PIN 码服务器能够强制执行 PIN 码的试错限制，并且 PIN 码服务器并不知道这个 PIN 码到底是什么（你也可以运行自己的 PIN 码服务器，只要你想）。我们成功地外包并且训练出了其他人的一些服务端 …… 这是另一套协议，也是开源的。 Jade 自身是用 C 语言编写的。至于 anti-exfil 协议，它是专门为解决一个问题而设计的，但你可以阅读源代码。我们已经有了一些设计说明书。它也在 libsec256k1-zkp 代码库中实现了，它也被 Jade 所用的 GDK 库调用了 —— 我们有一个通用的钱包代码库叫做 “GDK” 。它（anti-exfil）需要调整 PSBT ，就像 MuSig 签名需要的那样，我们甚至可以在 PSBT 中复用一些 MuSig 字段。

为了运行这套协议，我们不再能像原来那样使用半轮交互 —— 主机给出待签名的交易，然后收取签名；我们需要添加额外一轮交互，从而主机能够发送一个挑战，然后收取 nonce；然后主机再发送随机数，收取签名。所以我们需要一个额外的字段。这里有个前提 —— PSBT 也许不是实现这套协议的正确层级。但也许是。PSBT 通常用于让多个参与者一起产生一笔交易，它也被硬件签名器用于跟主机通信。 这是一个参与者，但有些分裂 —— 主机和硬件签名器明明是同一个人，所以他们可以在传输过程中添加任何东西。我们还没有为 PSBT 提出插件。

（译者注：在最终的 “Anti-exfil” 协议中，主机先给出随机数 t 的哈希值 h(t)，签名器先生成设备 nonce k0 = h(e, m, h(t)) 并回传这个设备 nonce 的公钥 K0 = k0.G；然后主机给出 t，签名器制作最终 nonce k = k0 + t，并用它来生成签名 (R, s)；主机用 R = K0 + t.G 来验证自己提供的随机性被用在最终 nonce 中。实际上，签名器为了不在这个交互过程中泄露私钥，必须总是为同一个 t 给出相同的 k0.G ，只要能实现这一点，也可以不使用 h(e, m, h(t)) 这样的确定性生成算法，主机无法检查出来，但从资源使用量角度考虑，最优的办法就是使用确定性生成。）

选择 nonce 攻击的讨论书：

https://github.com/stepansnigirev/chosen_nonce_demo/blob/master/HD_key.ipynb

（完）