MEGA加密系统的密钥恢复攻击解析

### MEGA加密系统的密钥恢复攻击解析 #### 1. 攻击基础与初步分析 在MEGA加密系统的攻击场景中，我们旨在恢复目标明文块。通过公式 \(B \equiv 248^{-1} \cdot (d^{*}-22047 - 1) \pmod{R}\) 来实现这一目标，前提是 \(|R|_b \geq 128\)。 ##### 1.1 攻击成本 - **最坏情况**：在线攻击的主要成本是 \(\sum_{i \in I}(r_i - 1)\) 次登录尝试。当 \(n \leq 19\) 时，该值上限约为 \(n \cdot (2^8 - 1) \approx 2^{12.24}\)。 - **平均情况**：对于每个 \(i\)，预计步骤 2a 大约经过 \(\frac{1}{2} \cdot 2^8\) 次试验后结束。因此，当 \(n \leq 19\) 时，总体上限变为 \(n \cdot 2^7 \approx 2^{11.24}\)。 ##### 1.2 攻击中止概率 攻击在收到错误 \(\perp6\) 时会中止。当解密后的 \(d^{*}= d' + 2^{48} \cdot B\) 满足 \(\gcd(d^{*}, (p^{*}-1)(q^{*}-1)) \neq 1\) 时，会返回此错误。由于 \(d^{*}\) 按构造为奇数，错误仅在以下至少一种情况成立时产生： - \(d^{*} \equiv 0 \pmod{r_i}\) 对于至少一个 \(r_i\)； - \(d^{*} \equiv 0 \pmod{p'_j}\) 对于至少一个 \(p'_j | p'\)； - \(d^{*} \equiv 0 \pmod{q'_k}\) 对于至少一个 \(q'_k | q'\)。 由于 \(p'_j\) 和 \(q'_k\) 是大素数，这些情况导致攻击中止的概率可忽略不计。然而，每个因子 \(r_i\) 仅为 8 位，假设 \(B\) 是随机的，攻击因 \(d^{*} \equiv 0 \pmod{r_i}\) 对于至少一个 \(r_i\) 而中止的概率，在 \(n \leq 19\) 时上限约为 \(n \cdot 2^{-7} \approx 0.15\)。 ##### 1.3 攻击正确性 假设攻击未中止，在解密过程中，客户端会计算 \(m = {c^{*}_{i,x}}^{d^{*}} \bmod N^{*} = (g_i)^{x \cdot d^{*}} \bmod N^{*}\)。若 \(m = (g_i)^{t_i} \bmod N^{*}\)，即 \(x \cdot d^{*} \equiv t_i \pmod{r_i}\)，零填充后的 \(m\) 的第二个字节将为 00，客户端会向服务器返回 \((\perp2, 254)\)；否则，客户端很可能返回 \(\perp3\)。因此，攻击能够恢复目标明文块。 #### 2. 完整版本攻击策略 为提高第二次攻击的运行时间和成功率，我们采用以下策略。 ##### 2.1 策略思路 增加因子 \(r_i\) 的位长，这提高了预计算阶段找到合适 \(t_i\) 值的概率，但也意味着可能有多个这样的值。因此，需要修改在线攻击部分，以确定对于给定的 \(x\)，是哪个 \(t \in T_i\) 值导致了预期错误。 ##### 2.2 预计算步骤 1. 选取 \(\{r_0, \ldots, r_{n - 1}\}\)，其中每个 \(r_i\) 是素数且 \(|r_i|_b = 12\)，\(n\) 满足 \(R = \prod_{i = 0}^{n - 1} r_i\) 且 \(|R|_b \geq 128\)，即 \(11 \leq n \leq 12\)。设 \([B]_{kM}\) 为目标密文块。 2. 找到素数 \(p^{*}\) 和 \(q^{*}\)，使得 \(|p^{*}|_b = |q^{*}|_b = 1024\)，且 \(p^{*}= 2 \cdot (\prod_{i = 0}^{\lceil n/2 \rceil - 1} r_i) \cdot p' + 1\)，\(q^{*}= 2 \cdot (\prod_{i = \lceil n/2 \rceil}^{n - 1} r_i) \cdot q' + 1\)，其中 \(p'\) 和 \(q'\) 是 2 - 4 个大素数的乘积。将 \(p^{*}\) 和 \(q^{*}\) 编码为字节字符串。 3. 设置 \(N^{*}= p^{*} \cdot q^{*}\) 和 \(G = (\mathbb{Z}/N^{*}\mathbb{Z})^{\times}\)。 4. 对于 \(i \in \{0, \ldots, n - 1\}\)： - 找到 \(G\) 中阶为 \(r_i\) 的 \(g\)，例如通过随机采样 \(h \in G\) 并计算 \(g = h^{(p^{*}-1)(q^{*}-1)/r_i} \bmod N^{*}\) 直到 \(g \neq 1\)。 - 初始化 \(T_i = \varnothing\)。 - 对于 \(t \in \{1, \ldots, r_i - 1\}\)： - 计算 \(g' = \text{ZeroPad}(g', N^{*})\)，其中 \(g' = g^t \bmod N^{*}\)。 - 若 \(g'[1] = 00\)，将 \(t\) 加入 \(T_i\)；否则，若 \(g'[17 : \alpha]\)（\(\alpha \geq 28\)）是长度为 11 的有效 UTF - 8 字符串，保存 \(g_i = g'\)，\(a = t\) 和 \(uh^{*}_i = g'[17 : \alpha]\)。 - 若 \(T_i = \varnothing\) 或 \(a\) 未定义，则重新进行预计算。 - 通过将 \(T_i\) 中的每个 \(t\) 替换为 \(t \cdot a^{-1} \bmod r_i\) 来移动 \(T_i\)，确保 \(T_i\) 中的值相对于新生成元 \(g_i\) 而非 \(g\)。 5. 计算 \(u^{*}= (q^{*})^{-1} \bmod p^{*}\) 并编码为字节字符串 \(u^{*}\)，使得 \(|u^{*}|_b = 1024\)。 6. 计算 \(d' = 2^{2047} + 2^{48 + 128} \cdot \delta + 1\)，其中 \(\delta < R\) 且 \(d' \equiv 0 \pmod{R}\)。将其编码为字节字符串 \(d'\)，使得 \(|d'|_b = 2048\)。 7. 获得 \(ct^{*}= \text{Stitch}(q^{*}, p^{*}, d', u^{*}, [B]_{kM})\)。 ##### 2.3 成功率与成本 - **成功率**：增加因子位长后，对于每个因子 \(r_i\)，步骤 3(c)ii 找到至少一个合适 \(t\) 的概率为 \(1 - (1 - 2^{-8})^{r_i - 1}\)，当 \(2^{11} < r_i < 2^{12}\) 时，该值大于 0.9996。对于所有 \(n \leq 12\) 个因子，此概率仍大于 0.99。随机 11 字节字符串是有效 UTF - 8 字符串的概率约为 0.001634，因此每个因子 \(r_i\) 找到至少一个此类字符串的概率大于 0.9648，所有因子的此概率至少为 0.65。 - **成本**：此版本需测试每个 \(r_i\) 的所有可能 \(t\) 值，最多检查 \(n \cdot 2^{12} \approx 2^{15}\) 个 \(g^t\) 值。素数生成是一次性成本，可在对多个用户的攻击中复用。构建密文 \(ct^{*}\) 最多需要使用 15 次 ECB 加密预言机。 ##### 2.4 在线攻击步骤 1.