椭圆曲线密码学中的定向故障攻击与防御

### 椭圆曲线密码学中的定向故障攻击与防御 在密码学领域，椭圆曲线密码学（ECC）因其高效性和安全性而被广泛应用。然而，即使是强大的密码系统也可能存在安全漏洞，其中定向故障攻击就是一种潜在的威胁。本文将深入探讨针对 CSIDH 算法的定向故障攻击及其相应的防御措施。 #### 1. 攻击原理与相关算法 在某些攻击场景中，攻击者可能会选择每隔一轮进行攻击。因为在后续轮次中，由于使用的界限限制，大度数的素数不会出现，这降低了连接不同组件的中间相遇复杂度。 ##### SQALE 算法 SQALE 算法仅使用指数界限 $e_i \in \{-1, 1\}$。为了获得足够大的密钥空间，需要更多的素数 $\ell_i$，最小的实例使用 221 个 $\ell_i$。它采用两点策略，通常只需要一轮（但要注意同构计算可能失败，需要额外轮次）。 设 $S^+ = S_{1,+} = \{i | e_i = 1\}$ 和 $S^- = S_{1,-} = \{i | e_i = -1\}$。如果第一轮采样的点具有完整阶，那么第一轮的故障曲线可能是以下几种情况： - EB 的“扭转”：如果两个点都翻转，所有方向都会翻转。 - 曲线 $E^+ = (\prod_{S^+} \ell_i^{-2}) * E_B$，如果正点翻转。 - 曲线 $E^- = (\prod_{S^-} \ell_i^{2}) * E_B$，如果负点翻转。 由于 $|S^+| \approx |S^-| \approx n/2 > 110$，使用暴力或中间相遇方法很难找到与这些曲线的同构。不过，SQALE 随机采样点，部分同构计算会失败，产生接近 $E^{\pm}$ 的故障曲线。攻击者获取足够多的故障曲线后，就能得到所有素数 $\ell_i$ 的方向，而这些方向正是 SQALE 中的秘密密钥。 #### 2. pubcrawl 工具 攻击的后处理阶段需要重建故障 CSIDH 输出之间的连接同构图。pubcrawl 工具通过在同构图中进行中间相遇邻域搜索来解决这个问题，适用于我们考虑的情况。 ##### 算法原理 pubcrawl 实现了一种直接的中间相遇图搜索：同时从每个输入节点生长同构树并检查碰撞，重复此过程直到只剩下一个连通组件。可配置的参数包括允许的同构度数集合（“支持”）、同构步骤的方向（“符号”）、从每个目标曲线开始放弃前的最大同构步骤数（“距离”）以及每个图搜索步骤执行的素数度同构数量（“多重性”）。 ##### 搜索空间大小 在 $\mathbb{Z}^n$ 中，1 - 范数 $\leq m$ 的向量数量为： $G_n(m) = \sum_{k=0}^{m} \binom{n}{k} \binom{m - k + n}{n}$ 在 $\mathbb{Z}_{\geq 0}^n$ 中，1 - 范数 $\leq m$ 的向量数量为： $H_n(m) = \sum_{k=0}^{m} \binom{k + n - 1}{n - 1}$ ##### 实现细节 该工具使用 C++ 编写，利用了现代标准库的特性，特别是哈希表和线程。它将原始 CSIDH 软件的最新版本作为库，以提供底层的同构计算。为了节省时间，跳过了公钥验证。共享数据结构（工作队列和查找表）由简单的互斥锁保护。 在一台配备两个 Intel Xeon Gold 6136 处理器（共 24 个超线程 Skylake 核心）的服务器上，使用 GCC 11.2.0 编译，每个同构步骤的时间在 0.6 到 0.8 核心毫秒之间，具体取决于度数。内存消耗约为每个访问节点 250 字节。 以下是不同 pubcrawl 实例的示例成本估计表： | sign | |support| | distance | 搜索空间基数 | 核心时间 | 内存 | | --- | --- | --- | --- | --- | --- | | both | 74 | ≤4 | 20,549,801 ≈ 2^{24.29} | 4.0 h | 5.1 GB | | both | 74 | ≤5 | 612,825,229 ≈ 2^{29.19} | 5.0 d | 153.2 GB | | both | 74 | ≤6 | 15,235,618,021 ≈ 2^{33.83} | 123.4 d | 3.8 TB | | both | 74 | ≤7 | 324,826,290,929 ≈ 2^{38.24} | 7.2 y | 81.2 TB | | both | 74 | ≤8 | 6,063,220,834,321 ≈ 2^{42.46} | 134.6 y | 1.5 PB | | both | 74 | ≤9 | 100,668,723,849,029 ≈ 2^{46.52} | 2234.5 y | 25.2 PB | | one | 74 | ≤4 | 1,426,425 ≈ 2^{20.44} | 16.6 min | 356.6 MB | | one | 74 | ≤5 | 22,537,515 ≈ 2^{24.43} | 4.4 h | 5.6 GB | | one | 74 | ≤6 | 300,500,200 ≈ 2^{28.16} | 2.4 d | 75.1 GB | | one | 74 | ≤7 | 3,477,216,600 ≈ 2^{31.70} | 28.2 d | 869.3 GB | 可以看出，pubcrawl 的时间和内存消耗与算法访问的节点数量几乎呈线性关系。如果需要，pubcrawl 可以通过同时计算多个输出同构步骤来加速，而不是将 CSIDH 库作为黑盒逐个调用。 #### 3. 哈希版本的攻击 在 Diffie - Hellman 风格的密钥交换中，攻击者可观察到的输出不是共享的椭圆曲线，而是某个派生值。通常，共享椭圆曲线用于通过密钥派生函数计算密钥 $k$，该密钥再用于对称密钥密码学。因此，攻击者只能获得派生值，如 $k = SHA - 256(E_t)$ 或 $MAC_k(str)$（对于某个已知固定字符串 $str$），而不是故障曲线 $E_t$ 的蒙哥马利系数。 之前的攻击策略依赖于不同故障曲线之间的连接，但当只给定派生值时，无法应用同构。不过，只要可观察值是从 $E_t$ 确定性计算得出且不发生碰撞，攻击仍然可以扩展到这种更现实的情况。为了简化，我们将可观察值称为故障曲线 $E$ 的哈希值 $H(E)$。我们假设可以从给定的 $E$ 导出 $H(E)$，但仅根据 $H(E)$ 无法恢复 $E$。 由于无法对哈希值应用同构，我们必须调整攻击策略。给定一组故障曲线，我们不能再生成邻域图，也难以找到这些图之间的连接路径，并且更难学习素数的方向，而素数方向有助于在应用 pubcrawl 时减少同构的可能度数。 但通过频率分析，我们仍然可以将每轮中两个最频繁的新哈希值 $h_1, h_2$ 识别为 $H(E_{r,\pm})$ 的可能哈希值。例如，在 CSIDH 的第一个点出现故障时，两个最常见的哈希值是 $E_{1,\pm}$ 哈希值的最佳猜测；当考虑第二个点的故障时，我们猜测 $H(E_{2,\pm})$ 是第一轮未出现的最常见哈希值。 为了从哈希值 $H(E)$ 恢复 $E$，我们从 $E_B$ 开始进行单边 pubcrawl 搜索，对沿途到达的所有曲线进行哈希处理，直到找到哈希值为 $H(E)$ 的曲线。在实践中，我们以一种方向（或并行使用两种方向）运行 pubcrawl，直到识别出 $H(E_{r,\pm})$。识别出 $E_{r,\pm}$ 后，我们可以在其周围进行小邻域搜索，以识别接近 $E_{r,\pm}$ 的故障曲线 $E_t$ 的哈希值。 与未哈希版本不同，在哈希版本中，我们只能通过从已知曲线 $E$ 进行单边搜索来恢复故障曲线 $E_t$，而不能进行中间相遇攻击。因此，我们无法获得中间相遇带来的平方根加速。尽管成本增加，但这并不意味着无法攻击哈希版本。虽然仅根据 $H(E_{r,\pm})$ 恢复 $E_{r,\pm}$ 的暴力搜索可能非常昂贵，特别是在大域 $\mathbb{F}_p$ 上的 CSIDH 中，但这种搜索的成本始