Alert Source Discuss
🚧 Stagnant Standards Track: ERC

ERC-3450: 用于 BIP-39 助记词的标准化的 Shamir 密钥共享方案

Authors Daniel Streit (@danielstreit)
Created 2021-03-29
Discussion Link https://ethereum-magicians.org/t/erc-3450-standard-for-applying-shamirs-to-bip-39-mnemonics/5844

Table of Contents

简单总结

一种将 Shamir 密钥共享方案应用于 BIP-39 助记词的标准算法。

摘要

一种标准化的方法，将一个 BIP-39 助记词分割成 N 个 BIP-39 助记词，称为 shares，这样需要 T 个 shares 才能恢复原始助记词，并且在少于 T 个 shares 的情况下，除了其大小外，不会泄露关于原始助记词的任何信息。

动机

我们希望让不太懂技术的用户更容易安全地存储密钥。

目前，许多用户使用 BIP-39 助记词来存储其密钥所基于的熵值。这些助记词是一个单一的故障点。如果丢失，用户可能永远无法重新获得由密钥锁定的资产的访问权限。如果被盗，恶意行为者可以窃取资产。

Shamir 密钥共享方案直接解决了这个问题。它创建了密钥的“shares”，这样可以使用一个子集来恢复密钥，但前提是达到了最小 shares 阈值。如果没有达到最小值，则不会泄露关于原始密钥的任何信息。

Shamir 密钥共享方案的一个问题是没有规范的、标准的实现。这使得恢复面临风险，因为工具可能会随着时间的推移而改变。

在这里，我们提出一个标准化的 Shamir 密钥共享方案的实现，专门应用于 BIP-39 助记词，以便用户可以轻松地创建其助记词的 shares，销毁原始助记词，适当地存储 shares，并在以后自信地恢复原始助记词。

规范

Shamir 密钥共享方案

Shamir 密钥共享方案是一种密码学方法，用于将一个密钥分成 N 个唯一的部分，其中需要任意 T 个部分来重构密钥。

首先，构建一个 T − 1 次多项式 f。然后，每个 share 都是多项式曲线上的一个点：一个整数 x，以及它对应的 y 点 f(x)。

使用任意一组 T 个 shares（或点），可以使用多项式插值恢复初始多项式。

在构造初始多项式时，密钥存储为 x0 的系数，其余系数随机生成。

BIP-39 助记词

BIP-39 是一个常见的标准，用于将熵存储为单词列表。对于人机交互来说，它比熵的原始二进制或十六进制表示更容易使用。

BIP-39 助记词编码两部分数据：原始熵和该熵的校验和。校验和允许验证助记词，确保用户正确输入。

生成助记词

助记词必须以 32 位的倍数编码熵。熵越多，安全性越高，但句子长度会增加。我们把初始熵长度称为 ENT。允许的 ENT 大小为 128-256 位。

首先，生成一个 ENT 位的初始熵。通过取其 SHA256 哈希的前 ENT / 32 位来生成校验和。这个校验和被附加到初始熵的末尾。接下来，这些连接的位被分成 11 位的组，每个组编码一个从 0-2047 的数字，作为单词列表的索引。最后，我们将这些数字转换为单词，并将连接的单词用作助记词句子。

下表描述了初始熵长度 (ENT)、校验和长度 (CS) 和生成的助记词句子 (MS) 的长度（以单词为单位）之间的关系。

CS = ENT / 32
MS = (ENT + CS) / 11

|  ENT  | CS | ENT+CS |  MS  |
+-------+----+--------+------+
|  128  |  4 |   132  |  12  |
|  160  |  5 |   165  |  15  |
|  192  |  6 |   198  |  18  |
|  224  |  7 |   231  |  21  |
|  256  |  8 |   264  |  24  |

恢复熵

可以通过反转上述过程来恢复初始熵。助记词被转换为位，其中每个单词被转换为 11 位，表示它在单词列表中的索引。熵部分在上面的表格中定义，基于助记词的大小。

单词列表

本规范仅支持 BIP-39 英语单词列表，但将来可能会扩展。

请参阅 单词列表。

将 Shamir 方案应用于 BIP-39 助记词

为了确保 shares 是有效的 BIP-39 助记词，我们：

  1. 将目标 BIP-39 助记词转换为其底层熵
  2. 将 Shamir 方案应用于熵
  3. 将每个结果 share 的 y 值转换为 BIP-39 助记词

通过在应用 Shamir 方案之前转换为熵，我们从初始密钥中省略了校验和，允许我们在将 share y 值转换为助记词时为每个 share 计算一个新的校验和，确保它们根据 BIP-39 有效。

当将 Shamir 方案应用于熵时，我们将它分别应用于熵的每个字节，并且 GF(256) 被用作底层的有限域。字节被解释为 GF(256) 的元素，使用多项式表示，运算以 Rijndael 不可约多项式 x8 + x4 + x3 + x + 1 为模，遵循 AES。

Share 格式

一个 share 代表了由用于分割密钥的底层多项式描述的曲线上的一个点。它包括两部分数据：

  • 一个 ID：share 的 x 值
  • 一个 BIP-39 助记词：由助记词表示的 share 的 y 值

创建 Shares

输入：BIP-39 助记词，share 数量 (N)，阈值 (T)

输出：N 个 Shares，每个 share 包括一个 ID，{ x 0 < x < 256 }，和一个与输入助记词长度相同的 BIP-39 助记词
  1. 检查以下条件：
    • 1 < T <= N < 256
    • 助记词根据 BIP-39 有效
  2. 恢复助记词的底层熵 作为一个字节向量
  3. 定义值：
    • 令 E 为助记词熵的字节向量表示
    • 令 n 为 E 的长度
    • 令 coeff1, … , coeffT - 1 为属于 GF(256)n 的字节向量，从适合生成加密密钥的源随机、独立地以均匀分布生成
  4. 为每个 share 评估多项式
    • 对于从 1 到 N 的每个 x，评估多项式 f(x) = E + coeff1x1 + … + coeffT - 1xT - 1，其中 x 是 share ID，f(x) 是 share 值（作为字节向量）
  5. 使用 f(x) 作为底层熵，为每个 share 生成一个助记词
  6. 返回每个 share 的 ID 和助记词

恢复助记词

为了恢复原始助记词，我们从给定的 share 集合（或多项式上的点）插值一个多项式 f 并评估 f(0).

多项式插值

给定一组 m 个点 (xi, yi)，1 ≤ i ≤ m，使得没有两个 xi 值相等，则存在一个在每个点 xi 处取值 yi 的多项式。满足这些条件的最低次数的多项式是唯一确定的，可以使用下面给出的拉格朗日插值公式获得。

由于 Shamir 密钥共享方案分别应用于共享助记词熵的 n 个字节中的每个字节，我们将 yi 作为 n 值的向量，其中 yi[k] = fk(xi)，1 ≤ k ≤ n，并且 fk 是方案的第 k 个实例中的多项式。

Interpolate(x, {(xi, yi), 1 ≤ i ≤ m})

输入：所需的索引 x，一组索引/值向量对 {(xi, yi), 1 ≤ i ≤ m} &subseteq; GF(256) × GF(256)n

输出：值向量 (f1(x), … , fn(x))

f_k(x) = \sum_{i=1}^m y_i[k] \prod_{\underset{j \neq i}{j=1}}^m \frac{x - x_j}{x_i - x_j}

恢复助记词

输入：一组 m 个 Shares

输出：原始助记词

  1. 恢复每个 share 的助记词的底层熵 作为一个字节向量
  2. 计算 E = Interpolate(0, [(x1, y1),…,(xm, ym)]), 其中 x 是 share ID，y 是 share 的助记词熵的字节向量
  3. 使用 E 作为底层熵，生成一个助记词 并返回它

理由

字段选择

选择字段 GF(256) 是因为该字段的算法很容易在任何编程语言中实现，并且由于它在 AES 密码中使用，因此许多实现已经可用。虽然使用 GF(256) 需要我们将助记词转换为其作为字节向量的底层熵，但这也很容易实现，并且它的许多实现以各种编程语言存在。

也考虑了 GF(2048)。使用 GF(2048)，我们可以将 Shamir 的方案直接应用于助记词，使用单词索引作为值。这将使我们能够避免将助记词转换为其底层熵。但是，生成的 shares 将不是有效的 BIP-39 助记词 - 校验和部分将不是熵的有效校验和。并且，解决这个问题会增加相当大的复杂性。

另一种选择是 GF(2n)，其中 n 是熵的大小（以位为单位）。我们仍然会将助记词转换为熵，然后将 Shamir 的方案应用于整个熵，而不是应用于值的向量。这种方法的缺点是我们需要为每个助记词强度使用不同的字段以及相关的不可约多项式。此外，这将需要处理一些语言中可能难以处理的非常大的数字。

有效的 Share 助记词和 Share ID

本规范生成的 shares 除了 BIP-39 助记词外，还包括一个 ID。

其他选项可以将 share ID 编码到助记词中，从而简化存储 - 只需要存储助记词。

一种可能性是将 ID 存储在助记词中代替校验和。这种方法的缺点是 shares 将不是_有效_的 BIP-39 助记词，因为助记词的“校验和”部分与“熵”部分不匹配。具有有效 BIP-39 助记词的 shares 很有用，因为它们与任何其他助记词无法区分。并且用户可以以各种模糊的方式存储 ID。

恢复时的验证

我们决定_不_在恢复原始助记词时包含验证机制。这会向潜在的攻击者泄露更少的信息。在他们获得 T + 1 个 shares 之前，没有任何迹象表明他们已经获得了所需数量的 shares。

我们可以通过将一个随机系数替换为原始助记词的校验和来提供恢复验证。然后，当恢复原始助记词和多项式时，我们可以验证校验和系数是否是恢复的助记词的有效校验和。

测试用例

即将推出。

所有实现必须能够：

  • 使用给定的 numShares 和 threshold 分割和恢复每个 mnemonic。
  • 从给定的 knownShares 恢复 mnemonic。

安全注意事项

本规范生成的 shares 除了 BIP-39 助记词外，还包括一个 ID。这提出了两个安全问题：

用户必须保留这个 ID 才能恢复原始助记词。如果 ID 丢失，或者与 share 助记词分离，则可能无法恢复原始助记词。（暴力恢复可能或不可能，取决于对 share 数量和阈值的了解程度）

额外的数据可能会暗示攻击者存在其他密钥以及它们存储的方案。因此，ID 应以一种模糊其使用的方式存储。

版权

版权及相关权利通过 CC0 放弃。

Citation

Please cite this document as:

Daniel Streit (@danielstreit), "ERC-3450: 用于 BIP-39 助记词的标准化的 Shamir 密钥共享方案 [DRAFT]," Ethereum Improvement Proposals, no. 3450, March 2021. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-3450.